# Informative Post-Hoc Explanations Only Exist for Simple Functions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 61 references that are in the map.
- First posted on arXiv 15 Aug 2025.

## Builds on (most cited first, 30 of 42)

- [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)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [SmoothGrad: removing noise by adding noise](https://mlsanity.com/paper/1706.03825/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Towards Robust Interpretability with Self-Explaining Neural Networks](https://mlsanity.com/paper/1806.07538/) (2018)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI](https://mlsanity.com/paper/2201.08164/) (2022)
- [Problems with Shapley-value-based explanations as feature importance measures](https://mlsanity.com/paper/2002.11097/) (2020)
- [Evaluating and Aggregating Feature-based Model Explanations](https://mlsanity.com/paper/2005.00631/) (2020)
- [The Disagreement Problem in Explainable Machine Learning: A Practitioner's Perspective](https://mlsanity.com/paper/2202.01602/) (2022)
- [Debugging Tests for Model Explanations](https://mlsanity.com/paper/2011.05429/) (2020)
- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Human-Centered Explainable AI (XAI): From Algorithms to User Experiences](https://mlsanity.com/paper/2110.10790/) (2021)
- [Counterfactual Explanations Can Be Manipulated](https://mlsanity.com/paper/2106.02666/) (2021)
- [Explaining the Explainer: A First Theoretical Analysis of LIME](https://mlsanity.com/paper/2001.03447/) (2020)
- [Impossibility Theorems for Feature Attribution](https://mlsanity.com/paper/2212.11870/) (2022)
- [Which Explanation Should I Choose? A Function Approximation Perspective to Characterizing Post Hoc Explanations](https://mlsanity.com/paper/2206.01254/) (2022)
- [General Pitfalls of Model-Agnostic Interpretation Methods for Machine Learning Models](https://mlsanity.com/paper/2007.04131/) (2020)
- [Fairwashing Explanations with Off-Manifold Detergent](https://mlsanity.com/paper/2007.09969/) (2020)
- [From Shapley Values to Generalized Additive Models and back](https://mlsanity.com/paper/2209.04012/) (2022)
- [Framework for Evaluating Faithfulness of Local Explanations](https://mlsanity.com/paper/2202.00734/) (2022)
- [Post-Hoc Explanations Fail to Achieve their Purpose in Adversarial Contexts](https://mlsanity.com/paper/2201.10295/) (2022)
- [Are Perceptually-Aligned Gradients a General Property of Robust Classifiers?](https://mlsanity.com/paper/1910.08640/) (2019)
- [What Makes a Good Explanation?: A Harmonized View of Properties of Explanations](https://mlsanity.com/paper/2211.05667/) (2022)
- [Automated Test Generation to Detect Individual Discrimination in AI Models](https://mlsanity.com/paper/1809.03260/) (2018)

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

- [Tractable Shapley Values and Interactions via Tensor Networks](https://mlsanity.com/paper/2510.22138/) (2025)
- [We Need Explanation Cards to Connect Explanation Algorithms to the Real World](https://mlsanity.com/paper/2606.16786/) (2026)

## Abstract (arXiv)

Many researchers have suggested that local post-hoc explanation algorithms can be used to gain insights into the behavior of complex machine learning models. However, theoretical guarantees about such algorithms only exist for simple decision functions, and it is unclear whether and under which assumptions similar results might exist for complex models. In this paper, we introduce a general, learning-theory-based framework for what it means for an explanation to provide information about a decision function. We call an explanation informative if it serves to reduce the complexity of the space of plausible decision functions. With this approach, we show that many popular explanation algorithms are not informative when applied to complex decision functions, providing a rigorous mathematical rejection of the idea that it should be possible to explain any model. We then derive conditions under which different explanation algorithms become informative. These are often stronger than what one might expect. For example, gradient explanations and counterfactual explanations are non-informative with respect to the space of differentiable functions, and SHAP and anchor explanations are not informative with respect to the space of decision trees. Based on these results, we discuss how explanation algorithms can be modified to become informative. While the proposed analysis of explanation algorithms is mathematical, we argue that it holds strong implications for the practical applicability of these algorithms, particularly for auditing, regulation, and high-risk applications of AI.