# Axiomatic Foundations of Counterfactual Explanations

arXiv: https://arxiv.org/abs/2602.04028 · HTML: https://mlsanity.com/paper/2602.04028/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 61 references that are in the map.
- First posted on arXiv 3 Feb 2026.

## Builds on (most cited first, 25 of 25)

- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Counterfactual Fairness](https://mlsanity.com/paper/1703.06856/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negatives](https://mlsanity.com/paper/1802.07623/) (2018)
- [Interpretable Counterfactual Explanations Guided by Prototypes](https://mlsanity.com/paper/1907.02584/) (2019)
- [Counterfactual Explanations and Algorithmic Recourses for Machine Learning: A Review](https://mlsanity.com/paper/2010.10596/) (2020)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [Benchmarking and Survey of Explanation Methods for Black Box Models](https://mlsanity.com/paper/2102.13076/) (2021)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [If Only We Had Better Counterfactual Explanations: Five Key Deficits to Rectify in the Evaluation of Counterfactual XAI Techniques](https://mlsanity.com/paper/2103.01035/) (2021)
- [On the Fairness of Causal Algorithmic Recourse](https://mlsanity.com/paper/2010.06529/) (2020)
- [Decisions, Counterfactual Explanations and Strategic Behavior](https://mlsanity.com/paper/2002.04333/) (2020)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [Black Box Explanation by Learning Image Exemplars in the Latent Feature Space](https://mlsanity.com/paper/2002.03746/) (2020)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [A Few Good Counterfactuals: Generating Interpretable, Plausible and Diverse Counterfactual Explanations](https://mlsanity.com/paper/2101.09056/) (2021)
- [Counterfactual Explanations for Machine Learning: Challenges Revisited](https://mlsanity.com/paper/2106.07756/) (2021)
- [Promoting Counterfactual Robustness through Diversity](https://mlsanity.com/paper/2312.06564/) (2023)
- [A unified logical framework for explanations in classifier systems](https://mlsanity.com/paper/2105.14452/) (2021)
- [Understanding Individual Agent Importance in Multi-Agent System via Counterfactual Reasoning](https://mlsanity.com/paper/2412.15619/) (2024)
- [Abductive explanations of classifiers under constraints: Complexity and properties](https://mlsanity.com/paper/2409.12154/) (2024)
- [Counterfactual Explanations for Model Ensembles Using Entropic Risk Measures](https://mlsanity.com/paper/2503.07934/) (2025)

## Built on by (most cited first, 1 of 1)

- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)

## Abstract (arXiv)

Explaining autonomous and intelligent systems is critical in order to improve trust in their decisions. Counterfactuals have emerged as one of the most compelling forms of explanation. They address ``why not'' questions by revealing how decisions could be altered. Despite the growing literature, most existing explainers focus on a single type of counterfactual and are restricted to local explanations, focusing on individual instances. There has been no systematic study of alternative counterfactual types, nor of global counterfactuals that shed light on a system's overall reasoning process. This paper addresses the two gaps by introducing an axiomatic framework built on a set of desirable properties for counterfactual explainers. It proves impossibility theorems showing that no single explainer can satisfy certain axiom combinations simultaneously, and fully characterizes all compatible sets. Representation theorems then establish five one-to-one correspondences between specific subsets of axioms and the families of explainers that satisfy them. Each family gives rise to a distinct type of counterfactual explanation, uncovering five fundamentally different types of counterfactuals. Some of these correspond to local explanations, while others capture global explanations. Finally, the framework situates existing explainers within this taxonomy, formally characterizes their behavior, and analyzes the computational complexity of generating such explanations.