🤖 AI

An XAI View on Explainable ASP: Methods, Systems, and Perspectives

This survey provides an XAI-guided overview of existing explanation methods and tools for Answer Set Programming, mapping them to user needs while identifying current gaps and outlining future research directions.

Original authors: Thomas Eiter, Tobias Geibinger, Zeynep G. Saribatur

Published 2026-06-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thomas Eiter, Tobias Geibinger, Zeynep G. Saribatur

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 built a very smart, logical robot to solve a complex puzzle. You give it a set of rules (like a recipe), and it spits out a solution. But sometimes, the robot gives you an answer that surprises you, or worse, it refuses to give an answer at all. You ask, "Why did you do that?" or "Why can't you solve this?"

This paper is a guidebook for asking those questions to Answer Set Programming (ASP) systems. ASP is a type of "Symbolic AI" that uses strict logical rules (like a super-precise recipe book) to solve problems. Unlike modern "neural network" AIs that are often black boxes (you put data in, magic happens, and you get an answer), ASP is transparent by nature because it follows clear, written rules.

However, even with clear rules, the logic can get tangled. This paper surveys the different "tools" and "methods" we have to explain what the robot is thinking. The authors, Thomas Eiter, Tobias Geibinger, and Zeynep G. Saribatur, organize these tools based on two main perspectives: Local and Global.

The Two Types of Questions

Think of the ASP system as a detective solving a case.

1. Local Explanations (The "Specific Case" Detective)

The Question: "I have a specific solution (a specific answer set). Why is this fact true in this solution?" or "Why is this fact false?"
The Analogy: Imagine you are looking at a specific photo of a crime scene. You ask, "Why is the suspect holding an umbrella?" The tool looks at the specific rules that led to that umbrella being in the photo.
The Tools: The paper lists several ways to do this:
- Justification Trees: Like a family tree, but for logic. It shows how one fact "descends" from other facts and rules.
- Support Graphs: A map showing which rules "supported" a decision.
- Contrastive Explanations: This is like asking, "Why did the suspect wear an umbrella instead of a hat?" The tool explains the difference between the actual outcome and a hypothetical "what if" scenario.

2. Global Explanations (The "Big Picture" Detective)

The Question: "Why does the robot never give an answer?" or "Why does the robot always include this fact in every single solution?"
The Analogy: Imagine you are looking at the entire rulebook of the detective. You ask, "Why is it impossible to solve this case?" or "Why is the suspect always guilty, no matter what?"
The Tools:
- Debugging: If the robot crashes (no solution), these tools act like a mechanic finding the broken part of the engine. They look for "Minimal Unsatisfiable Sets"—the smallest group of rules that are fighting each other and causing the crash.
- Abstraction: This is like zooming out on a map. If the map is too crowded to see the problem, you blur out the small streets and only look at the highways. This helps find the core reason why the system is stuck.

The Current State of the Toolbox

The paper acts as a review of the "toolshed" available to ASP users. Here is what they found:

We have many tools for "Why is X true?" There are many ways to explain why a specific fact appears in a solution (Local).
We are missing tools for "Why is the solution optimal?" If the robot picks the "best" solution based on some preferences, explaining why it's the best is currently very hard.
The "Language Gap": Many of these explanation tools work well on simple rules. But real-world problems often use advanced features like "disjunction" (A or B), "aggregates" (counting things), or "weak constraints" (preferences). The paper notes that many explanation tools cannot handle these advanced features yet. It's like having a wrench that only fits small bolts, but your machine has giant bolts.
The "System Divide": You often have to choose between a tool that explains a specific solution (Local) or a tool that explains why the whole system is broken (Global). You rarely get a tool that does both seamlessly.

The Human Element (Cognitive Aspects)

The authors also point out that just having the technical answer isn't enough; the explanation must be understandable to a human.

Too Much Information: If you have a massive program with thousands of rules, showing the user the entire "family tree" of logic is overwhelming. The paper suggests we need better ways to "summarize" or "abstract" these explanations, perhaps by hiding the boring details and showing only the core logic.
Talking to Non-Experts: Most tools output technical graphs or lists of rules. The paper suggests using Large Language Models (LLMs) (like the AI you are talking to now) to translate these technical "robot languages" into plain English. Imagine the robot saying, "I chose the umbrella because it was raining," instead of showing a complex graph of logical rules.

The Bottom Line

This paper is a map of the current landscape of "Explainable ASP." It tells us:

We are good at explaining specific, local decisions.
We are struggling with explaining why systems fail completely or why they choose the "best" option among many.
We need better tools that can handle complex, real-world rule types.
We need to make it human-friendly by summarizing complex logic and translating it into natural language.

The authors conclude that while we have a rich variety of methods, no single tool fits every need yet. The future of ASP explanation lies in bridging the gap between complex logical reasoning and human understanding, perhaps by using new AI technologies to act as translators.

Technical Summary: An XAI View on Explainable ASP

Problem Statement

Answer Set Programming (ASP) is a prominent declarative reasoning paradigm in symbolic AI, valued for its rule-based formalism which is inherently more interpretable than subsymbolic approaches like neural networks. Despite this, the "black box" nature of solver outputs remains a barrier to adoption in industry and society, particularly as Explainable AI (XAI) gains prominence. Users often struggle to understand the reasoning mechanisms behind specific solver results (answer sets) or the general behavior of a program (e.g., why no solution exists).

While previous surveys (e.g., Fandinno and Schulz, 2019) have cataloged specific explanation techniques, they often focus on narrow settings (e.g., "why is atom $a$ in answer set $I$ ?"). There is a lack of a comprehensive, user-centric overview that maps diverse user questions to existing theoretical approaches and tools, identifies gaps in current coverage, and aligns ASP explanation capabilities with the broader XAI distinction between local and global explanations.

Methodology

The authors conduct a survey of ASP explanation approaches guided by an XAI perspective. The methodology involves:

Categorization: Structuring the landscape of explanations into Local Explanations (concerning a specific computed answer set) and Global Explanations (concerning the general behavior of the program or the set of all answer sets).
Question-Driven Analysis: Identifying a comprehensive list of typical user questions (Q1–Q8) ranging from "Why is literal $\ell$ in $I$ ?" to "Why does the program have no answer sets?" and "Why is $I$ optimal?".
Mapping and Reduction: Analyzing how existing methods (labeled M1–M15) and systems (e.g., xASP2, xclingo, s(CASP), UCOREXPLAIN) address these questions. The authors also identify where questions can be reduced to other solvable problems (e.g., reducing "why $a \in I$ " to "why a modified program is unsatisfiable").
Gap Identification: Evaluating the coverage of current tools against language features (disjunction, aggregates, choice rules, weak constraints) and user needs (scalability, cognitive load, interaction).

Key Contributions

The paper provides a structured taxonomy of ASP explanation methods and highlights the following specific contributions:

1. Taxonomy of Explanation Types

Local Explanations: Focus on deriving the presence or absence of atoms in a specific answer set $I$ $I$ .
- Justifications (M1–M4): Includes offline justifications (derivation graphs), ABA-based justifications (argumentation trees), causal justifications (algebraic terms), and rule-based justifications from solver traces.
- Extended Justifications (M5): Unit-provable unsatisfiable subsets (1-PUS) used in UCOREXPLAIN to find minimal rule sets explaining a literal.
- Support Graphs (M6): Used by xclingo, linking atoms to rules that support them, allowing natural language annotations.
- Witnesses (M7): Solver-independent stepwise logical derivations.
- Contrastive Explanations (M8): Explains why a set of atoms $E$ is in $I$ rather than a set $F$ , using counterfactuals (Eiter et al., 2023).
Global Explanations: Focus on program behavior without a specific answer set.
- Why-not Provenance (M9): Identifies program modifications needed to change truth values.
- Top-down Computation (M10): Goal-directed justification trees (e.g., s(CASP)).
- Proof Systems (M11): Calculi for skeptical entailment (why an atom is in every or no answer set).
- Debugging (M12–M14): Techniques like meta-encodings (spock), Minimal Unsatisfiable Sets (MUS), and interactive stepping to explain inconsistencies.
- Abstraction (M15): Over-approximation techniques to "zoom in" on unsatisfiable parts by omitting irrelevant details.

2. Analysis of User Questions (Q1–Q8)

The paper maps specific user queries to available methods:

Q1 (Why $\ell \in I$ ?): Covered by most local methods (M1–M7).
Q2 (Why $\ell \in I$ but $\ell' \notin I$ ?): Addressed by contrastive explanations (M8) or reduction to unsatisfiability.
Q3 (Why is $I$ optimal?): Currently lacks native support; reducible to explaining the non-existence of a better answer set.
Q4–Q6 (Global existence/non-existence): Addressed by provenance, proof systems, and debugging/abstraction methods.
Q7–Q8 (Quantitative/Collective behavior): Identified as gaps. Current tools cannot natively explain why a property holds across a collection of answer sets or why a program has a specific number of answer sets.

3. Tool and Language Support Analysis

The authors evaluate existing tools against ASP language extensions (Table 2):

Disjunction: Poorly supported; most tools (LABAS, s(CASP), xASP2) do not handle disjunctive rules well due to complexity in explanation generation.
Choice Rules & Aggregates: Partially supported (e.g., xASP2, xclingo, UCOREXPLAIN), but often with restrictions.
Weak Constraints: Generally unsupported for explanation purposes, with DWASP being a notable exception for debugging.
Solver Dependency: A mix of solver-dependent (e.g., xclingo, s(CASP)) and solver-independent (e.g., LABAS, Causal Justifications) approaches exists.

Results and Findings

Coverage: Most user questions can be answered natively or by reduction to unsatisfiability (explaining why a program has no answer sets).
Limitations:
- Language Gaps: Disjunction and weak constraints remain significant hurdles for explanation tools.
- Scalability: Most methods are post-hoc and operate on ground programs, leading to high computational complexity for large problems.
- Cognitive Load: Explanations for inconsistencies (debugging) are often technical (rule sets) and difficult for non-experts to interpret.
- Missing Scenarios: No current method addresses questions regarding the quantity of answer sets or properties holding across multiple answer sets simultaneously.
Interoperability: There is a "system divide" where users must choose between local or global explanation tools, lacking a unified framework.

Significance and Future Directions

The paper positions itself as a guide for both researchers and non-expert ASP users, aiming to bridge the gap between theoretical explanation capabilities and practical user needs.

Significance:

It establishes a unified XAI framework for ASP, distinguishing between local and global reasoning.
It highlights that explaining inconsistency (unsatisfiability) is a critical stepping stone for universal explanation approaches, as many questions reduce to this form.
It identifies the need for concise and interpretable explanations, suggesting that abstraction and step-wise reasoning are vital for reducing cognitive effort.

Future Research Directions:

Cognitive Aspects: Developing methods to present inconsistencies (e.g., via hidden "lemmas" or cliques in graph coloring) in a way understandable to non-experts.
Interaction: Integrating Large Language Models (LLMs) to translate technical explanations (e.g., MUS) into natural language and to parse user queries.
Scalability: Incorporating explanation techniques directly into solvers to handle non-ground programs and large-scale problems.
New Question Types: Developing dedicated solutions for questions regarding the quantity of answer sets and collective behaviors (Q7, Q8).

The authors conclude that while a rich landscape of methods exists, no single tool fits all needs, and future work must address language support, scalability, and the cognitive interpretation of complex logical reasoning.