ExplAIner: A Declarative Query Language for Explaining Classification Models

• URL: http://arxiv.org/abs/2607.06407v1
• Date: Tue, 07 Jul 2026 15:36:51 GMT
• Title: ExplAIner: A Declarative Query Language for Explaining Classification Models
• Abstract summary: We develop a declarative query language for explaining black-box models called ExplAIner.<n>We show that ExplAIner can express a broad family of explanation notions, including abductive, contrastive, feature-based, and distance-based queries.<n>We also introduce Opt-FOIL, an optimization-oriented fragment of ExplAIner for computing explanations that are minimal with respect to strict partial orders.
• Score: 12.44009629083712
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The XAI community has studied a wide range of queries and scores for explaining predictions of ML models. From a data management perspective, this proliferation of explanation notions calls for declarative query languages in which such notions can be specified, combined, and analyzed uniformly. In this paper, we develop such a framework for Boolean models. We first revisit FOIL, an interpretability query language for black-box models, and show that it has two fundamental limitations: it cannot express central optimality-based explanation queries, and its evaluation problem over decision trees is hard for every level of the polynomial hierarchy. We then introduce ExplAIner, a query language based on FOIL with an extended vocabulary and a layered structure. We show that ExplAIner can express a broad family of explanation notions, including abductive, contrastive, feature-based, and distance-based queries. We also prove that the evaluation problem for each query in ExplAIner belongs to the Boolean hierarchy over every class of Boolean models for which some basic predicates can be evaluated in polynomial time. In particular, that property holds for deterministic and decomposable Boolean circuits. Finally, we introduce Opt-FOIL, an optimization-oriented fragment of ExplAIner for computing explanations that are minimal with respect to strict partial orders, and prove that its evaluation problem is in $\mathrm{FP}^{\mathrm{NP}}$ under the same tractability assumptions. These complexity results have 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. This is particularly relevant in formal XAI, where SAT solvers have been successfully used to compute explanations for several classes of ML models.

Related papers

• Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding [7.088503833248158]
  The adoption of artificial intelligence (AI) within real-world applications has raised a lot of concerns regarding their trustworthiness.<n>The field of eXplainable AI (XAI) has emerged with the objective of providing explanations to the users about the decisions made by AI systems.
  arXiv  Detail & Related papers  (2026-09-04T09:33:00Z)
• TopBench: A Benchmark for Implicit Prediction and Reasoning over Tabular Question Answering [80.93487993878836]
  A common class of real-world queries is implicitly predictive, requiring the inference of unobserved answers from historical patterns rather than mere retrieval.<n>These queries introduce two challenges: recognizing latent intent and reliable predictive reasoning over massive tables.<n>We introduce TopBench, a benchmark consisting of 779 samples across four sub-tasks, ranging from single-point prediction to decision making, treatment effect analysis, and complex reasoning.
  arXiv  Detail & Related papers  (2026-04-30T16:22:51Z)
• ReasonX: Declarative Reasoning on Explanations [7.744846780771137]
  ReasonX is an explanation tool based on expressions (or, queries) in a closed algebra of operators over theories of linear constraints.<n>Users can express background or common sense knowledge as linear constraints.
  arXiv  Detail & Related papers  (2026-02-27T08:50:02Z)
• OrLog: Resolving Complex Queries with LLMs and Probabilistic Reasoning [51.58235452818926]
  We introduce OrLog, a neuro-symbolic retrieval framework that decouples predicate-level plausibility estimation from logical reasoning.<n>A large language model (LLM) provides plausibility scores for atomic predicates in one decoding-free forward pass, from which a probabilistic reasoning engine derives the posterior probability of query satisfaction.
  arXiv  Detail & Related papers  (2026-01-30T15:31:58Z)
• Effective Instruction Parsing Plugin for Complex Logical Query Answering on Knowledge Graphs [51.33342412699939]
  Knowledge Graph Query Embedding (KGQE) aims to embed First-Order Logic (FOL) queries in a low-dimensional KG space for complex reasoning over incomplete KGs. Recent studies integrate various external information (such as entity types and relation context) to better capture the logical semantics of FOL queries. We propose an effective Query Instruction Parsing (QIPP) that captures latent query patterns from code-like query instructions.
  arXiv  Detail & Related papers  (2024-10-27T03:18:52Z)
• A Uniform Language to Explain Decision Trees [6.658444706223188]
  We show that our proposed logics can express not only a variety of interpretability queries considered by previous literature, but also allows users to specify different objectives the sought explanations should optimize for. We provide a SAT-based implementation of the evaluation for OPT-DT-FOIL that is expressive on industry-size decision trees.
  arXiv  Detail & Related papers  (2023-10-18T00:07:38Z)
• A Neuro-Symbolic Framework for Answering Graph Pattern Queries in Knowledge Graphs [17.93455358818447]
  Most neuro-symbolic query processors are constrained to tree-like graph pattern queries. We introduce a framework for answering arbitrary graph pattern queries over incomplete knowledge graphs.
  arXiv  Detail & Related papers  (2023-10-06T21:31:17Z)
• Query Structure Modeling for Inductive Logical Reasoning Over Knowledge Graphs [67.043747188954]
  We propose a structure-modeled textual encoding framework for inductive logical reasoning over KGs. It encodes linearized query structures and entities using pre-trained language models to find answers. We conduct experiments on two inductive logical reasoning datasets and three transductive datasets.
  arXiv  Detail & Related papers  (2023-05-23T01:25:29Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• Foundations of Symbolic Languages for Model Interpretability [2.3361634876233817]
  We study the computational complexity of FOIL queries over two classes of ML models often deemed to be easily interpretable. We present a prototype implementation of FOIL wrapped in a high-level declarative language.
  arXiv  Detail & Related papers  (2021-10-05T21:56:52Z)
• Text Modular Networks: Learning to Decompose Tasks in the Language of Existing Models [61.480085460269514]
  We propose a framework for building interpretable systems that learn to solve complex tasks by decomposing them into simpler ones solvable by existing models. We use this framework to build ModularQA, a system that can answer multi-hop reasoning questions by decomposing them into sub-questions answerable by a neural factoid single-span QA model and a symbolic calculator.
  arXiv  Detail & Related papers  (2020-09-01T23:45:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.