🤖 AI

ExplAIner: A Declarative Query Language for Explaining Classification Models

This paper introduces ExplAIner, a declarative query language that unifies various explanation notions for Boolean classification models and establishes that its evaluation is tractable via a fixed number of SAT solver calls, while its optimization-oriented fragment, Opt-FOIL, enables computing minimal explanations with polynomial calls.

Original authors: Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild, Bernardo Subercaseaux

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marcelo Arenas, Pablo Barceló, Diego Bustamante, Jose Caraball, María Alejandra Schild, Bernardo Subercaseaux

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but mysterious, robot that makes decisions. Maybe it decides who gets a loan, or if a medical scan looks suspicious. You ask the robot, "Why did you say 'yes' to this specific person?"

The robot doesn't just give you a simple reason. It has a black box inside. To understand it, researchers have invented dozens of different ways to ask questions: "What is the smallest reason?" "What if we changed one thing?" "Which features were absolutely necessary?"

This paper argues that having so many different ways to ask questions is messy. It's like having a thousand different keys for a thousand different locks, when you really just need a universal keyring. The authors want to create a universal language (a query language) where you can ask any of these questions using the same set of rules, and they want to know exactly how hard it is for a computer to answer them.

Here is the breakdown of their journey, using some everyday analogies:

1. The Old Tool: FOIL (The "Broken Flashlight")

The researchers first looked at an existing tool called FOIL. Think of FOIL as a flashlight you use to look inside the robot's black box.

The Problem: The flashlight is too weak. It can't shine on the "smallest" or "best" reasons (like finding the minimum number of features needed). It's like trying to find the smallest pebble in a pile of sand with a flashlight that only shows you big rocks.
The Danger: Worse, the flashlight is too powerful in a bad way. Asking it certain questions makes the computer's brain explode. The math shows that for some questions, the computer would have to check an impossible number of possibilities, even for simple models like decision trees. It's like asking a calculator to count every grain of sand on a beach; it takes too long.

2. The New Tool: ExplAIner (The "Smart, Layered Map")

To fix this, the authors built a new language called ExplAIner. Imagine this as a high-tech, layered map of the robot's decision-making process.

Layer 1 (The Atomic Layer): This is the basic geography. It knows how to compare pieces of information (like "this piece has 3 missing parts, that one has 5"). The authors proved this layer is easy to read; a computer can handle it instantly.
Layer 2 (The Quantified Layer): This layer asks questions about the robot's behavior. "If I fill in these missing parts, does the robot always say yes?" or "Does it always say no?" This layer is a bit harder, but still manageable (it falls into a category called NP, which means it's hard but solvable with a smart search).
Layer 3 (The Full ExplAIner): This is the top layer where you combine everything. You can ask complex questions like, "Is there a reason that is both minimal and involves feature X?"
The Magic: The authors proved that even with these complex questions, the computer doesn't need to go crazy. It can answer them by asking a "helper" (a SAT solver, which is like a super-smart puzzle solver) a fixed number of times. It's like having a librarian who can find any book in the library by asking the head librarian exactly three questions, no matter how big the library is.

3. The Optimization Tool: Opt-FOIL (The "Efficient Chef")

There's a catch. Just because you can ask the question (check if a reason exists) doesn't mean you can easily find the specific answer (the actual reason). It's like knowing a perfect cake recipe exists, but not knowing how to bake it without burning the kitchen down.

To solve this, they created a special subset of their language called Opt-FOIL.

The Concept: This is like a chef who doesn't just look for any cake, but specifically the smallest cake that still tastes good, or the cake with the least sugar.
The Result: They proved that for these specific "best possible" questions, the computer can actually find the answer efficiently. It can do this by asking the "helper" (the puzzle solver) a number of times that grows reasonably with the size of the problem (polynomial time). It's like the chef having a step-by-step guide that guarantees a perfect cake without burning the kitchen.

4. Why This Matters (The "Universal Keyring")

The main takeaway is that the authors have created a standardized framework for explaining AI.

Uniformity: Instead of writing a new computer program for every type of explanation (abductive, contrastive, feature-based), you just write a query in this new language.
Safety: They mathematically proved that these queries won't crash the computer. They stay within a "safe zone" of complexity, meaning they can be solved using standard, powerful tools (SAT solvers) that are already used in the industry.
Flexibility: You can mix and match different types of explanations. You can ask for the smallest reason, the biggest reason, or a reason that ignores a specific feature (like gender), all using the same rules.

Summary Analogy

Imagine the AI model is a locked treasure chest.

FOIL was a key that sometimes didn't fit (couldn't find the smallest reason) and sometimes jammed the lock so hard it broke the door (too complex to compute).
ExplAIner is a master keyring. It has different keys for different locks (different types of explanations), but they all fit the same mechanism. The authors proved that using these keys won't break the lock.
Opt-FOIL is a specialized tool on that ring that not only opens the chest but also automatically finds the smallest keyhole or the most valuable gem inside, doing so quickly and efficiently.

The paper doesn't claim this will cure diseases or predict the stock market tomorrow. It simply says: "We have built a better, safer, and more organized way to ask 'Why?' to AI models, and we have mathematically proven that our new way works without breaking the computer."

Technical Summary: ExplAIner: A Declarative Query Language for Explaining Classification Models

1. Problem Statement

The field of Explainable AI (XAI) has produced a proliferation of distinct explanation notions, scores, and queries (e.g., abductive, contrastive, feature-necessity, counterfactuals). From a data management perspective, this diversity lacks a unified framework. Current approaches often require designing separate algorithms for each explanation task. The paper posits that a declarative query language is needed to specify, combine, and analyze these notions uniformly.

However, existing foundational languages face two critical limitations:

Expressiveness: They often fail to capture central optimality-based explanation notions (e.g., minimum abductive explanations).
Complexity: Their evaluation problems can be intractable, reaching high levels of the polynomial hierarchy (PH), making them impractical for implementation using standard SAT-based engines.

The core challenge is to design a logic that balances sufficient expressiveness to capture a broad family of explanation queries with controlled evaluation complexity (specifically, tractability via SAT solvers, corresponding to the Boolean hierarchy over NP).

2. Methodology and Framework

The authors develop a framework for explaining Boolean models (functions $M: \{0, 1\}^n \to \{0, 1\}$ ) by treating models as structures over which queries are evaluated. The methodology proceeds in three stages:

2.1 Analysis of FOIL

The paper first revisits FOIL (First-Order Interpretability Logic), a model-agnostic logic treating models as black boxes with access to positive instances and the subsumption relation ( $\subseteq$ ) over partial instances.

Expressiveness Limitation: The authors prove that FOIL cannot express the query for minimum abductive explanations (mAXp), even when restricted to decision trees. This is demonstrated using Ehrenfeucht-Fraïssé games to show that FOIL cannot distinguish between models where a minimum explanation exists and those where it does not, based solely on subsumption.
Complexity Limitation: The evaluation problem for FOIL over decision trees is shown to be hard for every level of the polynomial hierarchy ( $\Sigma^P_k$ -hard). This implies that FOIL cannot be evaluated with a polynomial number of calls to an NP oracle, rendering it unsuitable for practical SAT-based evaluation.

2.2 Introduction of ExplAIner

To address these limitations, the authors introduce ExplAIner, a layered first-order logic with an extended vocabulary.

Vocabulary Extension: ExplAIner adds a binary relation $\preceq$ that compares partial instances based on the number of defined features (cardinality). The authors prove that $\subseteq$ and $\preceq$ are independent; neither can be defined in terms of the other over decision trees.
Layered Structure:
1. Atomic Layer: Formulas over $\{\subseteq, \preceq\}$ . These depend only on the structure of partial instances, not the model. Evaluation is in P (polynomial time) and validity is decidable via reduction to Presburger arithmetic.
2. Quantified Layer: Extends the atomic layer with predicates AllPos and AllNeg (checking if all completions of a partial instance are classified positively/negatively) and guarded quantifiers. Guarded quantifiers restrict universal quantification to partial instances with exactly one defined feature. If AllPos and AllNeg are tractable (in P) for a model class, evaluation of this layer is in NP.
3. Full ExplAIner Layer: Allows Boolean combinations of formulas from the quantified layer. This layer captures the entire Boolean Hierarchy (BH) over NP.

2.3 Introduction of Opt-FOIL

Recognizing that evaluation (checking if an instance is an explanation) differs from computation (finding an explanation), the authors define Opt-FOIL.

Mechanism: Opt-FOIL is a fragment of ExplAIner augmented with a minimization operator (min) over definable strict partial orders.
Syntax: A formula $\Psi = \min[\varphi, \rho]$ computes an instance $x$ satisfying a logical specification $\varphi$ that is minimal with respect to a strict partial order $\rho$ .
Syntax Decidability: The paper provides an algorithm (based on Presburger arithmetic) to verify whether a given atomic formula defines a strict partial order, ensuring Opt-FOIL has a decidable syntax.

3. Key Contributions and Results

3.1 Limitations of FOIL

Theorem 3.1: No FOIL formula can define the minimum abductive explanation query over decision trees.
Theorem 3.4: For every level $k$ of the polynomial hierarchy, there exists a fixed FOIL formula whose evaluation over decision trees is $\Sigma^P_k$ -hard.

3.2 Expressiveness and Complexity of ExplAIner

Expressiveness: ExplAIner successfully encodes a wide range of explanation notions, including:
- Weak/Abductive/Minimum Abductive Explanations (wAXp, AXp, mAXp).
- Weak/Contrastive/Maximum Contrastive Explanations (wCXp, CXp, mCXp).
- Minimum Change Required (MCR) and Maximum Change Allowed (MCA).
- Necessary and Relevant Features (NF, RF).
Complexity Bounds:
- Atomic Layer: Evaluation is in P.
- Quantified Layer: If AllPos and AllNeg are in P, evaluation is in NP. There exist queries in this layer that are NP-complete over decision trees.
- Full Layer: If AllPos and AllNeg are in P, evaluation is in the Boolean Hierarchy (BH). Specifically, for every level $BH_k$ , there is an ExplAIner query that is $BH_k$ -hard over decision trees.
- Applicability: These bounds hold for decision trees, deterministic decomposable negation normal form (d-DNNF) circuits, 2CNF, and Horn CNF.

3.3 Computational Guarantees of Opt-FOIL

Theorem 5.3: If AllPos and AllNeg are in P, the computation problem for any Opt-FOIL formula is in FPNP (functions computable in polynomial time with a polynomial number of calls to an NP oracle).
Algorithm: The computation involves constructing a path in the strict partial order. Since the length of such paths is polynomially bounded (Lemma 5.5), the algorithm terminates with a polynomial number of SAT solver calls.
Strict Containment: Assuming the polynomial hierarchy does not collapse, Opt-FOIL is strictly contained in ExplAIner, which is strictly contained in FOIL (with extended predicates). This confirms that Opt-FOIL sacrifices some expressive power (e.g., it cannot express certain non-optimality queries that ExplAIner can) to gain computational tractability for finding answers.

4. Significance and Claims

The paper claims that ExplAIner and Opt-FOIL provide a principled, declarative foundation for formal XAI.

Uniformity: They offer a single language to specify diverse explanation notions, allowing for the combination of criteria (e.g., finding a common explanation for multiple instances).
Tractability: By restricting the logic to layers where evaluation is in the Boolean hierarchy and computation is in FPNP, the framework aligns with the capabilities of modern SAT solvers. This is crucial because formal XAI often relies on SAT encodings for models like decision trees and d-DNNF circuits.
Separation of Concerns: The framework separates the logical specification of explanation queries from the representation-dependent complexity of evaluation. This allows the same query language to be applied to different model classes (trees, circuits) provided they support efficient consistency checks (AllPos/AllNeg).

The authors conclude that while FOIL serves as a foundational theoretical tool, it is inadequate for practical implementation due to its high complexity and limited expressiveness regarding optimality. ExplAIner and Opt-FOIL resolve these issues, enabling the specification and efficient computation of explanations for Boolean models.