📊 statistics

Axiomatic Foundations of Counterfactual Explanations

This paper introduces an axiomatic framework that establishes impossibility and representation theorems to systematically characterize five distinct families of counterfactual explanations, thereby bridging the gap between local and global interpretability in autonomous systems.

Original authors: Leila Amgoud, Martin Cooper

Published 2026-02-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Leila Amgoud, Martin Cooper

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 are standing in front of a mysterious, high-tech vending machine. You put in your money, press a button, and it gives you a soda. But then, you ask, "Why didn't I get a juice?"

Most current AI explainers try to answer this by looking at your specific transaction. They say, "Well, you put in $1.00, but the juice costs $1.50." This is a local explanation. It's helpful, but it only tells you about this one specific moment.

The paper you provided, "Axiomatic Foundations of Counterfactual Explanations" by Amgoud and Cooper, argues that we've been looking at this problem too narrowly. They built a new "rulebook" (an axiomatic framework) to categorize all possible ways an AI can explain its decisions, not just the ones we usually see.

Here is the breakdown of their findings in simple terms:

1. The Two Big Families of Explanations

The authors discovered that all counterfactual explanations (answers to "Why not?") fall into two main camps, like two different ways of solving a puzzle:

The "Necessary" Camp (The Missing Piece):
- The Logic: "If you remove this specific thing, the result changes."
- The Metaphor: Imagine a cake that didn't rise. A necessary explanation says, "The cake didn't rise because you forgot the baking powder." If you hadn't forgotten the powder, the cake might have risen. It identifies the critical ingredient that was present and caused the current outcome.
- The Catch: Sometimes, there is no single "missing piece." For example, if a loan was denied because of a complex mix of low income and bad credit, removing just one might not be enough to guarantee a "yes." In these cases, necessary explanations might not exist at all.
The "Sufficient" Camp (The Magic Switch):
- The Logic: "If you add or change this specific thing, the result will definitely change."
- The Metaphor: Imagine a light switch. A sufficient explanation says, "If you flip this switch, the light turns on." It doesn't matter what else is happening in the room; flipping the switch guarantees the change.
- The Catch: There are often many switches you could flip. You could flip the switch, or you could replace the bulb, or you could bring in a flashlight. This type of explanation guarantees a result, but it can be overwhelming because there are so many options.

2. The Five Types of Explanations

The authors didn't just stop at "Necessary" vs. "Sufficient." They broke these down into five distinct types based on how strict or broad the rules are. Think of these as different "personalities" of explainers:

Global Necessary (The Rulebook Keeper):
- What it does: Explains the entire machine, not just your specific order. It says, "This machine always gives soda if the button is red."
- Who it helps: People who want to understand the system's overall logic.
- Limitation: It might not exist if the machine is too chaotic (e.g., sometimes red gives soda, sometimes juice).
Local Necessary (The Specific Detective):
- What it does: Looks at your order and says, "For your specific case, the fact that you are wearing a hat is why you got soda."
- Who it helps: People who want to know exactly what about them caused the result.
- Limitation: Like the global version, it might not exist if your situation is too unique.
Global Sufficient (The "What If" Simulator):
- What it does: Looks at the whole machine and says, "If anyone presses the blue button, they get juice."
- Who it helps: People who want to know what changes would guarantee a different outcome for anyone.
- Limitation: It might suggest changes that aren't part of your current situation (e.g., "If you were a robot...").
Local Sceptical (The Strict Skeptic):
- What it does: Looks at your order and says, "If you change your hat to a completely new item (one you don't currently have), you will get juice."
- Who it helps: People who want to know what new things they could do.
- Limitation: It might not exist if there are no new items that guarantee a change.
Local Credulous (The Optimist):
- What it does: Looks at your order and says, "If you change your hat to a different hat (even one that looks similar), you might get juice."
- Who it helps: This is the type most current AI tools use. It's the most flexible and guarantees you will get an answer.
- Limitation: It's less "discriminating." It might suggest a change that works for you but wouldn't work for someone else.

3. The "Impossible" Rules

The paper proves a fascinating mathematical fact: You cannot have it all.

They showed that certain combinations of "good qualities" (like being guaranteed to exist, being the shortest answer, and being strictly true for everyone) are mathematically incompatible.

Analogy: It's like trying to build a car that is simultaneously the fastest, the safest, and the cheapest. The laws of physics (or in this case, logic) say you have to pick two.
The Result: If you want an explanation that always exists (guaranteed), you have to give up on it being the "shortest" or "most specific" possible. If you want the "shortest" explanation, you might get an answer that doesn't exist for some people.

4. Why This Matters

Before this paper, most AI tools were just "Local Credulous" explainers (Type 5). They were like the Optimist: they always gave you an answer, but they didn't tell you if that answer was the only way, or if it was the best way.

This paper provides a map. It tells us:

If you want to understand the system's rules, look for Global Necessary reasons.
If you want to know exactly what changed your outcome, look for Local Necessary reasons.
If you just want any possible way to get a different result, look for Local Credulous reasons.

Summary

The authors didn't invent a new AI tool; they invented a taxonomy (a classification system). They proved that there are five fundamentally different ways to explain "Why not?" and that no single tool can be the best at all of them at once. They also showed that most current tools are just one specific type (the "Optimist" or Credulous type), and we are missing out on other, potentially more useful types of explanations that could be built if we knew the rules.

Technical Summary: Axiomatic Foundations of Counterfactual Explanations

Problem Statement
The paper addresses a critical gap in the literature on Explainable AI (XAI). While counterfactual explanations (answering "why not" questions) have emerged as a compelling method to improve trust in autonomous systems, existing research suffers from two main limitations:

Lack of Systematic Classification: Most existing work focuses on a single type of local counterfactual (tailored to individual instances) without systematically studying alternative types.
Neglect of Global Explanations: There is insufficient attention paid to global counterfactuals, which aim to explain a model's overall reasoning process rather than just individual predictions.
Consequently, the theoretical trade-offs between local and global counterfactuals, and between different definitions of "closeness" or "validity," remain poorly understood.

Methodology
The authors propose an axiomatic framework to systematically define, compare, and characterize counterfactual explainers. This approach, common in theoretical science, builds a system upon a set of clearly stated axioms (basic properties) to derive representation theorems.

Formal Setting: The framework operates on a classification theory $T = \langle F, dom, C \rangle$ (features, domains, classes) and a classifier $\kappa$ . A query is defined as $Q = \langle T, \kappa, x \rangle$ .
Axioms: The paper introduces nine axioms grouped into three categories:
- General Properties: Success (non-empty output), Non-Triviality (no empty sets), Equivalence (same class $\to$ same explanation), and Feasibility (explanations are subsets of the instance).
- Necessary Reasons Properties: Coreness (explanations contain only core literals) and Sceptical Validity (removing the explanation guarantees a class change).
- Sufficient Reasons Properties: Novelty (explanations contain no literals from the original instance), Strong Validity (presence of explanation guarantees a class change), and Weak Validity (replacing values with the explanation yields a different class).
Analysis: The authors use these axioms to prove impossibility theorems (showing certain combinations are incompatible) and representation theorems (establishing one-to-one correspondences between axiom subsets and families of explainers).

Key Contributions
The paper makes six primary contributions:

Axiomatic Framework: Introduces a framework grounded in nine axioms to define counterfactual explainers.
Impossibility Theorems: Proves that no single explainer can satisfy certain combinations of axioms simultaneously (e.g., Success, Non-Triviality, and Coreness are incompatible).
Characterization of Compatible Sets: Fully characterizes all compatible sets of axioms.
Representation Theorems: Establishes one-to-one correspondences between specific axiom subsets and five distinct families of explainers, uncovering five fundamentally different types of counterfactuals:
- Global Necessary Reasons (GNR): Feature-value combinations that distinguish a class from all others (satisfy Coreness, Non-Triviality).
- Local Sceptical Necessary Reasons (SNR): Subsets of an instance that distinguish it from all other instances with a different decision (satisfy Feasibility, Sceptical Validity).
- Global Sufficient Reasons (GSR): Feature-value combinations whose presence guarantees a different class (satisfy Strong Validity).
- Local Sceptical Sufficient Reasons (SSR): New feature values not in the instance that guarantee a different decision (satisfy Novelty, Strong Validity).
- Local Credulous Sufficient Reasons (CSR): Feature-value combinations that distinguish an instance from some instance with a different decision (satisfy Novelty, Weak Validity).
Taxonomy of Existing Work: Formally characterizes existing explainers within this taxonomy. The paper finds that nearly all existing local explainers fall under the family of Credulous Sufficient Reasons (CSR). The global explainers proposed in prior work [2] correspond to Global Necessary Reasons (GNR). This analysis reveals three previously unrecognized types (SNR, GSR, SSR).
Complexity Analysis: Analyzes the computational complexity of generating these explanations, distinguishing between decision problems (checking if an explanation is valid) and finding problems (generating an explanation).

Results

Classification: The five types of counterfactuals are divided into two fundamental forms: Necessary Reasons (what must be absent to change the decision) and Sufficient Reasons (what must be present to change the decision).
Existence and Compactness:
- Necessary reasons (GNR, SNR) and Sceptical Sufficient Reasons (SSR) are not guaranteed to exist for every query.
- Credulous Sufficient Reasons (CSR) and Global Sufficient Reasons (GSR) are guaranteed to exist.
- Necessary reasons are compact (conveying the full range of changes via a minimal set of literals), whereas sufficient reasons are non-compact (enumerating all possible changes).
Human Preference: The paper argues that necessary reasons, when they exist, align better with human preferences for short, concise explanations compared to the often numerous and verbose sufficient reasons.
Complexity:
- For Boolean classifiers, deciding if an explanation is valid ($DECIDEEXP$) is $O(n)$ for CSRs, SNRs, and sparsity-based explainers, but co-NP-complete for GNRs, GSRs, SSRs, and cardinality/distance-based explainers.
- Finding an explanation ($FINDEXP$) is NP-hard for most families (including GNR, CSR, SNR, GSR), though it can be solved with at most $n$ calls to a SAT oracle for most cases.

Significance
The paper claims to provide the first axiomatic framework for counterfactual explanations. Its significance lies in:

Theoretical Rigor: Moving beyond empirical evaluation to a principled, objective comparison of explainers based on the axioms they satisfy.
Unification and Discovery: Unifying existing local explainers under the CSR family while formally identifying and defining three new types of counterfactuals (SNR, GSR, SSR) that were previously unrecognized.
Model-Agnostic Generality: The framework is applicable across diverse settings and classifier types.
Foundation for Future Work: By characterizing the space of possible explainers, the framework allows for the future design of explainers that satisfy specific combinations of desirable properties (e.g., actionability, fairness, diversity) within a specific counterfactual type.

The authors conclude that while necessary reasons are theoretically appealing for their conciseness, sufficient reasons are more robust in terms of existence. The framework provides the necessary tools to navigate these trade-offs systematically.