# Provably efficient, succinct, and precise explanations

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 1 Nov 2021.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [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)
- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Robust and Stable Black Box Explanations](https://mlsanity.com/paper/2011.06169/) (2020)
- [Interpretability via Model Extraction](https://mlsanity.com/paper/1706.09773/) (2017)
- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [On Validating, Repairing and Refining Heuristic ML Explanations](https://mlsanity.com/paper/1907.02509/) (2019)
- [Interpreting Models via Single Tree Approximation](https://mlsanity.com/paper/1610.09036/) (2016)
- [Top-down induction of decision trees: rigorous guarantees and inherent limitations](https://mlsanity.com/paper/1911.07375/) (2019)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [Universal guarantees for decision tree induction via a higher-order splitting criterion](https://mlsanity.com/paper/2010.08633/) (2020)

## Built on by (most cited first, 30 of 32)

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [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)
- [Robust Explanation Constraints for Neural Networks](https://mlsanity.com/paper/2212.08507/) (2022)
- [Eliminating The Impossible, Whatever Remains Must Be True](https://mlsanity.com/paper/2206.09551/) (2022)
- [Feature Necessity & Relevancy in ML Classifier Explanations](https://mlsanity.com/paper/2210.15675/) (2022)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Stability Guarantees for Feature Attributions with Multiplicative Smoothing](https://mlsanity.com/paper/2307.05902/) (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)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [A Psychological Theory of Explainability](https://mlsanity.com/paper/2205.08452/) (2022)
- [Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations](https://mlsanity.com/paper/2501.06078/) (2025)
- [Interpretability Guarantees with Merlin-Arthur Classifiers](https://mlsanity.com/paper/2206.00759/) (2022)
- [Anytime Approximate Formal Feature Attribution](https://mlsanity.com/paper/2312.06973/) (2023)
- [Probabilistic Stability Guarantees for Feature Attributions](https://mlsanity.com/paper/2504.13787/) (2025)
- [Provably Precise, Succinct and Efficient Explanations for Decision Trees](https://mlsanity.com/paper/2205.09569/) (2022)
- [Cardinality-Minimal Explanations for Monotonic Neural Networks](https://mlsanity.com/paper/2205.09901/) (2022)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [A Query-Optimal Algorithm for Finding Counterfactuals](https://mlsanity.com/paper/2207.07072/) (2022)
- [A Theory of Interpretable Approximations](https://mlsanity.com/paper/2406.10529/) (2024)
- [Interpretability Can Be Actionable](https://mlsanity.com/paper/2605.11161/) (2026)
- [On Computing Relevant Features for Explaining NBCs](https://mlsanity.com/paper/2207.04748/) (2022)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [On Deciding Feature Membership in Explanations of SDD & Related Classifiers](https://mlsanity.com/paper/2202.07553/) (2022)
- [Learning Model Agnostic Explanations via Constraint Programming](https://mlsanity.com/paper/2411.08478/) (2024)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Finding Safe Zones of policies Markov Decision Processes](https://mlsanity.com/paper/2202.11593/) (2022)
- [The Computational Complexity of Concise Hypersphere Classification](https://mlsanity.com/paper/2312.07103/) (2023)

## Abstract (arXiv)

We consider the problem of explaining the predictions of an arbitrary blackbox model f: given query access to f and an instance x, output a small set of x's features that in conjunction essentially determines f(x). We design an efficient algorithm with provable guarantees on the succinctness and precision of the explanations that it returns. Prior algorithms were either efficient but lacked such guarantees, or achieved such guarantees but were inefficient. We obtain our algorithm via a connection to the problem of sl implicitly learning decision trees. The implicit nature of this learning task allows for efficient algorithms even when the complexity of f necessitates an intractably large surrogate decision tree. We solve the implicit learning problem by bringing together techniques from learning theory, local computation algorithms, and complexity theory. Our approach of "explaining by implicit learning" shares elements of two previously disparate methods for post-hoc explanations, global and local explanations, and we make the case that it enjoys advantages of both.