# Eliminating The Impossible, Whatever Remains Must Be True

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 78 references that are in the map.
- First posted on arXiv 20 Jun 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparison](https://mlsanity.com/paper/1703.00512/) (2017)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [On Guaranteed Optimal Robust Explanations for NLP Models](https://mlsanity.com/paper/2105.03640/) (2021)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [Can I Trust the Explainer? Verifying Post-hoc Explanatory Methods](https://mlsanity.com/paper/1910.02065/) (2019)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Foundations of Symbolic Languages for Model Interpretability](https://mlsanity.com/paper/2110.02376/) (2021)
- [Computing Optimal Decision Sets with SAT](https://mlsanity.com/paper/2007.15140/) (2020)
- [On Quantifying Literals in Boolean Logic and Its Applications to Explainable AI](https://mlsanity.com/paper/2108.09876/) (2021)
- [MLIC: A MaxSAT-Based framework for learning interpretable classification rules](https://mlsanity.com/paper/1812.01843/) (2018)
- [Recursive Online Enumeration of All Minimal Unsatisfiable Subsets](https://mlsanity.com/paper/1708.00400/) (2017)
- [IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2001.01891/) (2020)
- [A Scalable Two Stage Approach to Computing Optimal Decision Sets](https://mlsanity.com/paper/2102.01904/) (2021)
- [Sufficient reasons for classifier decisions in the presence of constraints](https://mlsanity.com/paper/2105.06001/) (2021)

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)
- [From Robustness to Explainability and Back Again](https://mlsanity.com/paper/2306.03048/) (2023)
- [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [On Formal Feature Attribution and Its Approximation](https://mlsanity.com/paper/2307.03380/) (2023)
- [Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation](https://mlsanity.com/paper/2408.03915/) (2024)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [Most General Explanations of Tree Ensembles (Extended Version)](https://mlsanity.com/paper/2505.10991/) (2025)
- [On Computing Relevant Features for Explaining NBCs](https://mlsanity.com/paper/2207.04748/) (2022)
- [Logic-Based Explainability: Past, Present & Future](https://mlsanity.com/paper/2406.11873/) (2024)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [The Pros and Cons of Adversarial Robustness](https://mlsanity.com/paper/2312.10911/) (2023)
- [AR-Pro: Counterfactual Explanations for Anomaly Repair with Formal Properties](https://mlsanity.com/paper/2410.24178/) (2024)
- [Complexity of Faceted Explanations in Propositional Abduction](https://mlsanity.com/paper/2507.14962/) (2025)
- [On Explaining Proxy Discrimination and Unfairness in Individual Decisions Made by AI Systems](https://mlsanity.com/paper/2509.25662/) (2025)
- [Uncovering Bugs in Formal Explainers: A Case Study with PyXAI](https://mlsanity.com/paper/2511.03169/) (2025)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)
- [Efficient & Correct Predictive Equivalence for Decision Trees](https://mlsanity.com/paper/2509.17774/) (2025)
- [Leveraging Association Rules for Better Predictions and Better Explanations](https://mlsanity.com/paper/2510.18628/) (2025)
- [Bridging AI and Clinical Reasoning: Abductive Explanations for Alignment on Critical Symptoms](https://mlsanity.com/paper/2602.13985/) (2026)
- [Fairness of Classifiers in the Presence of Constraints between Features](https://mlsanity.com/paper/2605.00592/) (2026)
- [Representative Sets in Propositional Abduction](https://mlsanity.com/paper/2607.21183/) (2026)

## Abstract (arXiv)

The rise of AI methods to make predictions and decisions has led to a pressing need for more explainable artificial intelligence (XAI) methods. One common approach for XAI is to produce a post-hoc explanation, explaining why a black box ML model made a certain prediction. Formal approaches to post-hoc explanations provide succinct reasons for why a prediction was made, as well as why not another prediction was made. But these approaches assume that features are independent and uniformly distributed. While this means that "why" explanations are correct, they may be longer than required. It also means the "why not" explanations may be suspect as the counterexamples they rely on may not be meaningful. In this paper, we show how one can apply background knowledge to give more succinct "why" formal explanations, that are presumably easier to interpret by humans, and give more accurate "why not" explanations. In addition, we show how to use existing rule induction techniques to efficiently extract background information from a dataset, and also how to report which background information was used to make an explanation, allowing a human to examine it if they doubt the correctness of the explanation.