ExplAIner: Declarative Query Language for Model Explanations

ExplAIner, a declarative query language for explaining classification models, was submitted to arXiv on 7 Jul 2026 as arXiv:2607.06407 by Marcelo Arenas and five coauthors. The paper frames ExplAIner as a FOIL-based language with an extended vocabulary and layered structure that can express a broad family of explanation notions for Boolean models.

What is ExplAIner and what can it express?

ExplAIner is a query language that extends FOIL and, according to the authors, can express abductive, contrastive, feature-based and distance-based explanation queries. The paper presents ExplAIner as having an extended vocabulary and layered structure compared with FOIL, and explicitly lists those four families of explanation notions as within its expressive scope.

ExplAIner is presented as a unifying declarative framework aimed at the proliferation of explanation notions in XAI. The authors position it to specify, combine and analyze explanation queries uniformly over Boolean classification models.

How does ExplAIner compare with FOIL on expressiveness and complexity?

ExplAIner addresses two limitations the authors identify in FOIL: FOIL cannot express central optimality-based explanation queries, and FOIL’s evaluation problem over decision trees is hard for every level of the polynomial hierarchy. By contrast, every query in ExplAIner has an evaluation problem that belongs to the Boolean hierarchy, provided basic predicates on the target Boolean model can be evaluated in polynomial time.

The paper uses that tractability assumption to make concrete complexity claims. In particular, the Boolean-hierarchy membership holds for deterministic and decomposable Boolean circuits. That is, the authors prove that ExplAIner queries are in a lower and more structured complexity class than the hard FOIL decision-tree evaluation cases they highlight.

What is Opt-FOIL and what are its algorithmic implications?

Opt-FOIL is an optimization-oriented fragment of ExplAIner designed to compute explanations that are minimal with respect to strict partial orders, and its evaluation problem is placed in FP^NP under the same tractability assumptions the paper uses elsewhere. The authors state that this yields a direct algorithmic consequence: a fixed ExplAIner query can be evaluated with a fixed number of calls to a SAT solver, while a notion of explanation specified in Opt-FOIL can be computed with a polynomial number of such calls.

That connection to SAT solvers is underscored in the paper as particularly relevant to formal XAI, where SAT solvers have already been used to compute explanations for several classes of ML models.

Why it matters

ExplAIner converts a scattered set of XAI explanation notions into a single declarative language and gives complexity bounds that map those notions to familiar algorithmic tools. Placing ExplAIner evaluation in the Boolean hierarchy, and Opt-FOIL in FP^NP, clarifies when and how SAT-based techniques can be applied. For researchers building formal explanation tools, those complexity guarantees define which model classes and explanation types are amenable to practical solver-backed implementations.

What to watch

Look for implementations and benchmarks that apply ExplAIner and Opt-FOIL to deterministic and decomposable Boolean circuits, since the paper proves tractability results in those settings. Also watch for follow-up work that converts the stated SAT-call bounds into concrete solver-based procedures and empirical run-time results.

References in the paper include the arXiv identifier arXiv:2607.06407 and the submission date 7 Jul 2026. The author list is Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild and Bernardo Subercaseaux.