Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding

• URL: http://arxiv.org/abs/2609.04931v1
• Date: Fri, 04 Sep 2026 09:33:00 GMT
• Title: Solving Hard XAI Queries Based on a Compiled Dual-Rail Encoding
• Abstract summary: 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.
• Score: 7.088503833248158
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The widespread adoption of artificial intelligence (AI) within real-world applications has raised a lot of concerns regarding their trustworthiness, especially in critical applications. The field of eXplainable AI (XAI) has emerged with the objective of providing explanations to the users about the decisions made by AI systems. Several explanations for boolean classifiers have been introduced in the literature, including abductive and contrastive explanations, each giving a different insight on the decision of the classifier. However, computing an explanation for a decision of a boolean classifier is a hard problem in general. One way to deal with this complexity is to rely on a compiled representation of the classifier for which each explanation can be computed efficiently. Unfortunately, we prove in this paper that several classes of abductive explanations, remain hard to compute even for Ordered Binary Decision Diagrams, one of the most tractable subsets of the knowledge compilation map. Included in such classes are shorter abductive explanations or abductive explanations that include the explainee's preferences. To recover the benefits of working with compiled representations, we show that a proper representation of the dual-rail encoding of the classifier can be used to compute efficiently these classes of explanations.

Related papers

• ExplAIner: A Declarative Query Language for Explaining Classification Models [12.44009629083712]
  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.
  arXiv  Detail & Related papers  (2026-07-07T15:36:51Z)
• On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI [5.172213041663734]
  We show that in many cases, generating explanations is computationally hard.<n>We discuss the implications for the XAI community and for policymakers seeking to regulate explanations in AI.
  arXiv  Detail & Related papers  (2026-01-14T13:02:24Z)
• Informative Post-Hoc Explanations Only Exist for Simple Functions [12.017822772474576]
  We introduce a general, learning-theory-based framework for what it means for an explanation to provide information about a decision function.<n>We show that many popular explanation algorithms are not informative when applied to complex decision functions.<n>We argue that it holds strong implications for the practical applicability of these algorithms, particularly for auditing, regulation, and high-risk applications of AI.
  arXiv  Detail & Related papers  (2025-08-15T12:46:18Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a curriculum-based logical-aware instruction tuning framework, named LACT.<n>Specifically, we augment the arbitrary first-order logical queries via binary tree decomposition.<n> Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods, achieving the new state-of-the-art.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• Understanding and Mitigating Classification Errors Through Interpretable Token Patterns [58.91023283103762]
  Characterizing errors in easily interpretable terms gives insight into whether a classifier is prone to making systematic errors. We propose to discover those patterns of tokens that distinguish correct and erroneous predictions. We show that our method, Premise, performs well in practice.
  arXiv  Detail & Related papers  (2023-11-18T00:24:26Z)
• On Computing Probabilistic Abductive Explanations [30.325691263226968]
  The most widely studied explainable AI (XAI) approaches are unsound. PI-explanations also exhibit important drawbacks, the most visible of which is arguably their size. This paper investigates practical approaches for computing relevant sets for a number of widely used classifiers.
  arXiv  Detail & Related papers  (2022-12-12T15:47:10Z)
• Complementary Explanations for Effective In-Context Learning [77.83124315634386]
  Large language models (LLMs) have exhibited remarkable capabilities in learning from explanations in prompts. This work aims to better understand the mechanisms by which explanations are used for in-context learning.
  arXiv  Detail & Related papers  (2022-11-25T04:40:47Z)
• On Deciding Feature Membership in Explanations of SDD & Related Classifiers [0.685316573653194]
  The paper shows that the feature membership problem (FMP) is hard for $SigmaP$ for a broad class of classifiers. The paper proposes propositional encodings for classifiers represented with Sentential Decision Diagrams (SDDs) and for other propositional languages.
  arXiv  Detail & Related papers  (2022-02-15T16:38:53Z)
• Discrete Reasoning Templates for Natural Language Understanding [79.07883990966077]
  We present an approach that reasons about complex questions by decomposing them to simpler subquestions. We derive the final answer according to instructions in a predefined reasoning template. We show that our approach is competitive with the state-of-the-art while being interpretable and requires little supervision.
  arXiv  Detail & Related papers  (2021-04-05T18:56:56Z)
• This is not the Texture you are looking for! Introducing Novel Counterfactual Explanations for Non-Experts using Generative Adversarial Learning [59.17685450892182]
  counterfactual explanation systems try to enable a counterfactual reasoning by modifying the input image. We present a novel approach to generate such counterfactual image explanations based on adversarial image-to-image translation techniques. Our results show that our approach leads to significantly better results regarding mental models, explanation satisfaction, trust, emotions, and self-efficacy than two state-of-the art systems.
  arXiv  Detail & Related papers  (2020-12-22T10:08:05Z)
• SCOUT: Self-aware Discriminant Counterfactual Explanations [78.79534272979305]
  The problem of counterfactual visual explanations is considered. A new family of discriminant explanations is introduced. The resulting counterfactual explanations are optimization free and thus much faster than previous methods.
  arXiv  Detail & Related papers  (2020-04-16T17:05:49Z)

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.