On Formal Counterfactual Explanations
Organizations: Monash University, Australia · ICREA & IIIA-CSIC, Spain
Abstract
Counterfactual explanations are often seen as counterfactual conditionals under closest-world semantics, requiring one to reason over all minimally distant counterexamples. In contrast, formal XAI typically relies on feature-based abductive explanations (AXps) and contrastive explanations (CXps), which admit efficient computation and a minimal hitting-set duality. This paper bridges these perspectives by (i) characterizing closest-world counterfactual explanations explicitly as a disjunctive normal form over all minimally distant counterexample instances, and (ii) introducing conjunctive counterfactual explanations (CFXps), a subclass of counterfactual antecedents restricted to conjunctions of feature literals that guarantee prediction change. The paper establishes structural results connecting CXps, AXps and CFXps: every CXp induces an AXp for its witness instance, and every CXp together with a witness AXp induces a CFXp whose support is precisely determined by that AXp. These theoretical results yield a modular approach for computing CFXps using existing AXp/CXp machinery. Experiments on a representative set of benchmarks using tree ensembles and neural networks show that CFXp extraction is practically efficient. Compared with popular point-based counterfactual explainers, CFXps generally require no more feature changes and can guarantee the counterfactual prediction beyond a single instance.
Figures & tables
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
| Model | Explanation | Size | Time (s) |
|---|---|---|---|
| XGBoost | AXp | 9.043/ 0 8 | 1.529/0.266 |
| XGBoost | CXp ( ) | 1.972/ 0 1 | 0.783/0.184 |
| XGBoost | CFXp support ( ) | 8.240/ 0 7 | – |
| XGBoost | CFXp certificate ( ) | 10.212/ 0 8 | 2.098/0.500 |
| XGBoost | CWC worlds | 117.770/19 | 51.872/2.168 |
| ReLU | AXp | 19.734/15 | 0.238/0.075 |
| XGBoost | ReLU | |||||||
| Dataset | D | GS | W | D | GS | W | ||
| ann-thyroid | 21 | 3 | 99.0 | 98.5 | 100 | 52.5 | 53.0 | 100 |
| appendicitis | 7 | 2 | 94.3 | 97.2 | 100 | 92.5 | 100 | 100 |
| biodegradation | 41 | 2 | 89.0 | 97.5 | 100 | 98.0 | 100 | 100 |
| divorce | 54 | 2 | 90.7 | 74.7 | 100 | 48.0 | 96.0 | 100 |
| ecoli | 7 | 5 | 100 | 100 | 100 | 100 | 100 | 100 |
Counterfactual Explanations
Counterfactual explanations show how changing an input could alter a model’s prediction, supporting model understanding, auditing, and actionable recourse.
See all 123 papers