# Probabilistic Sufficient Explanations

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 21 May 2021.

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

- [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)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [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)
- [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 Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [On Tractable Computation of Expected Predictions](https://mlsanity.com/paper/1910.02182/) (2019)
- [The Struggles of Feature-Based Explanations: Shapley Values vs. Minimal Sufficient Subsets](https://mlsanity.com/paper/2009.11023/) (2020)
- [Learning Logistic Circuits](https://mlsanity.com/paper/1902.10798/) (2019)
- [What to Expect of Classifiers? Reasoning about Logistic Regression with Missing Features](https://mlsanity.com/paper/1903.01620/) (2019)
- [Handling Missing Data in Decision Trees: A Probabilistic Approach](https://mlsanity.com/paper/2006.16341/) (2020)
- [On Robust Trimming of Bayesian Network Classifiers](https://mlsanity.com/paper/1805.11243/) (2018)

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

- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (2022)
- [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022)
- [VeriX: Towards Verified Explainability of Deep Neural Networks](https://mlsanity.com/paper/2212.01051/) (2022)
- [On the Computation of Necessary and Sufficient Explanations](https://mlsanity.com/paper/2203.10451/) (2022)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)
- [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective](https://mlsanity.com/paper/2502.02719/) (2025)
- [Probabilistic Stability Guarantees for Feature Attributions](https://mlsanity.com/paper/2504.13787/) (2025)
- [Scaling Probabilistic Circuits via Monarch Matrices](https://mlsanity.com/paper/2506.12383/) (2025)
- [Provably Precise, Succinct and Efficient Explanations for Decision Trees](https://mlsanity.com/paper/2205.09569/) (2022)
- [A New Class of Explanations for Classifiers with Non-Binary Features](https://mlsanity.com/paper/2304.14760/) (2023)
- [On Computing Relevant Features for Explaining NBCs](https://mlsanity.com/paper/2207.04748/) (2022)
- [Even-if Explanations: Formal Foundations, Priorities and Complexity](https://mlsanity.com/paper/2401.10938/) (2024)
- [Sufficient and Necessary Explanations (and What Lies in Between)](https://mlsanity.com/paper/2409.20427/) (2024)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [On Spectral Properties of Gradient-based Explanation Methods](https://mlsanity.com/paper/2508.10595/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Explainability as statistical inference](https://mlsanity.com/paper/2212.03131/) (2022)
- [Value-Based Rationales Improve Social Experience: A Multiagent Simulation Study](https://mlsanity.com/paper/2408.02117/) (2024)
- [Bound Propagation meets Constraint Simplification: Improving Logic-based XAI for Neural Networks](https://mlsanity.com/paper/2603.01923/) (2026)
- [Pruning-Based Extraction of Descriptions from Probabilistic Circuits](https://mlsanity.com/paper/2311.13379/) (2023)
- [Slice and Explain: Logic-Based Explanations for Neural Networks through Domain Slicing](https://mlsanity.com/paper/2602.22115/) (2026)

## Abstract (arXiv)

Understanding the behavior of learned classifiers is an important task, and various black-box explanations, logical reasoning approaches, and model-specific methods have been proposed. In this paper, we introduce probabilistic sufficient explanations, which formulate explaining an instance of classification as choosing the "simplest" subset of features such that only observing those features is "sufficient" to explain the classification. That is, sufficient to give us strong probabilistic guarantees that the model will behave similarly when all features are observed under the data distribution. In addition, we leverage tractable probabilistic reasoning tools such as probabilistic circuits and expected predictions to design a scalable algorithm for finding the desired explanations while keeping the guarantees intact. Our experiments demonstrate the effectiveness of our algorithm in finding sufficient explanations, and showcase its advantages compared to Anchors and logical explanations.