# Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 66 of its 102 references that are in the map.
- First posted on arXiv 7 Aug 2024.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Interpretable Explanations of Black Boxes by Meaningful Perturbation](https://mlsanity.com/paper/1704.03296/) (2017)
- [A Benchmark for Interpretability Methods in Deep Neural Networks](https://mlsanity.com/paper/1806.10758/) (2018)
- [Generalized ODIN: Detecting Out-of-distribution Image without Learning from Out-of-distribution Data](https://mlsanity.com/paper/2002.11297/) (2020)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Input complexity and out-of-distribution detection with likelihood-based generative models](https://mlsanity.com/paper/1909.11480/) (2019)
- [Feature relevance quantification in explainable AI: A causal problem](https://mlsanity.com/paper/1910.13413/) (2019)
- [Visualizing Deep Neural Network Decisions: Prediction Difference Analysis](https://mlsanity.com/paper/1702.04595/) (2017)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [Explaining Image Classifiers by Counterfactual Generation](https://mlsanity.com/paper/1807.08024/) (2018)
- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [The Out-of-Distribution Problem in Explainability and Search Methods for Feature Importance Explanations](https://mlsanity.com/paper/2106.00786/) (2021)
- [Marabou 2.0: A Versatile Formal Analyzer of Neural Networks](https://mlsanity.com/paper/2401.14461/) (2024)
- [Provable Guarantees for Understanding Out-of-distribution Detection](https://mlsanity.com/paper/2112.00787/) (2021)
- [Verification of Deep Convolutional Neural Networks Using ImageStars](https://mlsanity.com/paper/2004.05511/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [An Abstraction-Based Framework for Neural Network Verification](https://mlsanity.com/paper/1910.14574/) (2019)
- [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)
- [Evaluations and Methods for Explanation through Robustness Analysis](https://mlsanity.com/paper/2006.00442/) (2020)
- [An SMT-Based Approach for Verifying Binarized Neural Networks](https://mlsanity.com/paper/2011.02948/) (2020)
- [Discretized Integrated Gradients for Explaining Language Models](https://mlsanity.com/paper/2108.13654/) (2021)
- [Interpretation of NLP models through input marginalization](https://mlsanity.com/paper/2010.13984/) (2020)

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

- [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)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Self-Explaining Neural Networks for Business Process Monitoring](https://mlsanity.com/paper/2503.18067/) (2025)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [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)
- [On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI](https://mlsanity.com/paper/2601.09455/) (2026)

## Abstract (arXiv)

The ability to interpret Machine Learning (ML) models is becoming increasingly essential. However, despite significant progress in the field, there remains a lack of rigorous characterization regarding the innate interpretability of different models. In an attempt to bridge this gap, recent work has demonstrated that it is possible to formally assess interpretability by studying the computational complexity of explaining the decisions of various models. In this setting, if explanations for a particular model can be obtained efficiently, the model is considered interpretable (since it can be explained ``easily''). However, if generating explanations over an ML model is computationally intractable, it is considered uninterpretable. Prior research identified two key factors that influence the complexity of interpreting an ML model: (i) the type of the model (e.g., neural networks, decision trees, etc.); and (ii) the form of explanation (e.g., contrastive explanations, Shapley values, etc.). In this work, we claim that a third, important factor must also be considered for this analysis -- the underlying distribution over which the explanation is obtained. Considering the underlying distribution is key in avoiding explanations that are socially misaligned, i.e., convey information that is biased and unhelpful to users. We demonstrate the significant influence of the underlying distribution on the resulting overall interpretation complexity, in two settings: (i) prediction models paired with an external out-of-distribution (OOD) detector; and (ii) prediction models designed to inherently generate socially aligned explanations. Our findings prove that the expressiveness of the distribution can significantly influence the overall complexity of interpretation, and identify essential prerequisites that a model must possess to generate socially aligned explanations.