# Auditing Local Explanations is Hard

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 28 references that are in the map.
- First posted on arXiv 18 Jul 2024.

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

- [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)
- [SmoothGrad: removing noise by adding noise](https://mlsanity.com/paper/1706.03825/) (2017)
- [Interpretation of Neural Networks is Fragile](https://mlsanity.com/paper/1710.10547/) (2017)
- [On the Robustness of Interpretability Methods](https://mlsanity.com/paper/1806.08049/) (2018)
- [Manipulating and Measuring Model Interpretability](https://mlsanity.com/paper/1802.07810/) (2018)
- [Explanations can be manipulated and geometry is to blame](https://mlsanity.com/paper/1906.07983/) (2019)
- [Explainable Machine Learning in Deployment](https://mlsanity.com/paper/1909.06342/) (2019)
- [Sanity Checks for Saliency Metrics](https://mlsanity.com/paper/1912.01451/) (2019)
- [How can I choose an explainer? An Application-grounded Evaluation of Post-hoc Explanations](https://mlsanity.com/paper/2101.08758/) (2021)
- [Framework for Evaluating Faithfulness of Local Explanations](https://mlsanity.com/paper/2202.00734/) (2022)
- [Towards falsifiable interpretability research](https://mlsanity.com/paper/2010.12016/) (2020)
- [Post-Hoc Explanations Fail to Achieve their Purpose in Adversarial Contexts](https://mlsanity.com/paper/2201.10295/) (2022)
- [Towards the Unification and Robustness of Perturbation and Gradient Based Explanations](https://mlsanity.com/paper/2102.10618/) (2021)
- [Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks](https://mlsanity.com/paper/2210.13915/) (2022)
- [Statistical stability indices for LIME: obtaining reliable explanations for Machine Learning models](https://mlsanity.com/paper/2001.11757/) (2020)
- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [Revisiting The Evaluation of Class Activation Mapping for Explainability: A Novel Metric and Experimental Analysis](https://mlsanity.com/paper/2104.10252/) (2021)
- [A Formal Approach to Explainability](https://mlsanity.com/paper/2001.05207/) (2020)
- [MeLIME: Meaningful Local Explanation for Machine Learning Models](https://mlsanity.com/paper/2009.05818/) (2020)
- [The Right Tool for the Job: Open-Source Auditing Tools in Machine Learning](https://mlsanity.com/paper/2206.10613/) (2022)

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

- [Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective](https://mlsanity.com/paper/2502.02719/) (2025)
- [GNN Explanations that do not Explain and How to find Them](https://mlsanity.com/paper/2601.20815/) (2026)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [ExpProof : Operationalizing Explanations for Confidential Models with ZKPs](https://mlsanity.com/paper/2502.03773/) (2025)
- [Evaluating Explanations: An Explanatory Virtues Framework for Mechanistic Interpretability -- The Strange Science Part I.ii](https://mlsanity.com/paper/2505.01372/) (2025)
- [Informative Post-Hoc Explanations Only Exist for Simple Functions](https://mlsanity.com/paper/2508.11441/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Learning Conditional Averages](https://mlsanity.com/paper/2602.11920/) (2026)

## Abstract (arXiv)

In sensitive contexts, providers of machine learning algorithms are increasingly required to give explanations for their algorithms' decisions. However, explanation receivers might not trust the provider, who potentially could output misleading or manipulated explanations. In this work, we investigate an auditing framework in which a third-party auditor or a collective of users attempts to sanity-check explanations: they can query model decisions and the corresponding local explanations, pool all the information received, and then check for basic consistency properties. We prove upper and lower bounds on the amount of queries that are needed for an auditor to succeed within this framework. Our results show that successful auditing requires a potentially exorbitant number of queries -- particularly in high dimensional cases. Our analysis also reveals that a key property is the ``locality'' of the provided explanations -- a quantity that so far has not been paid much attention to in the explainability literature. Looking forward, our results suggest that for complex high-dimensional settings, merely providing a pointwise prediction and explanation could be insufficient, as there is no way for the users to verify that the provided explanations are not completely made-up.