# On the Tractability of SHAP Explanations

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

## Key facts

- Cited by 92 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2020.

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

- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Additive MIL: Intrinsically Interpretable Multiple Instance Learning for Pathology](https://mlsanity.com/paper/2206.01794/) (2022)
- [Leveraging Explanations in Interactive Machine Learning: An Overview](https://mlsanity.com/paper/2207.14526/) (2022)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [Tractable Regularization of Probabilistic Circuits](https://mlsanity.com/paper/2106.02264/) (2021)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [Explaining Predictive Uncertainty with Information Theoretic Shapley Values](https://mlsanity.com/paper/2306.05724/) (2023)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [Explainability is NOT a Game](https://mlsanity.com/paper/2307.07514/) (2023)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Pixel-Grounded Prototypical Part Networks](https://mlsanity.com/paper/2309.14531/) (2023)
- [Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning](https://mlsanity.com/paper/2301.09138/) (2023)
- [Accelerating Shapley Explanation via Contributive Cooperator Selection](https://mlsanity.com/paper/2206.08529/) (2022)
- [Unfooling Perturbation-Based Post Hoc Explainers](https://mlsanity.com/paper/2205.14772/) (2022)
- [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023)
- [Evaluating the Values of Sources in Transfer Learning](https://mlsanity.com/paper/2104.12567/) (2021)
- [Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation](https://mlsanity.com/paper/2408.03915/) (2024)
- [Compositional Probabilistic and Causal Inference using Tractable Circuit Models](https://mlsanity.com/paper/2304.08278/) (2023)
- [On the Tractability of SHAP Explanations under Markovian Distributions](https://mlsanity.com/paper/2405.02936/) (2024)
- [A Compositional Atlas for Algebraic Circuits](https://mlsanity.com/paper/2412.05481/) (2024)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [Ensembles of Random SHAPs](https://mlsanity.com/paper/2103.03302/) (2021)
- [From SHAP Scores to Feature Importance Scores](https://mlsanity.com/paper/2405.11766/) (2024)
- [ProtoS-ViT: Visual foundation models for sparse self-explainable classifications](https://mlsanity.com/paper/2406.10025/) (2024)
- [SHAP values via sparse Fourier representation](https://mlsanity.com/paper/2410.06300/) (2024)
- [Investigating the Duality of Interpretability and Explainability in Machine Learning](https://mlsanity.com/paper/2503.21356/) (2025)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)

## Abstract (arXiv)

SHAP explanations are a popular feature-attribution mechanism for explainable AI. They use game-theoretic notions to measure the influence of individual features on the prediction of a machine learning model. Despite a lot of recent interest from both academia and industry, it is not known whether SHAP explanations of common machine learning models can be computed efficiently. In this paper, we establish the complexity of computing the SHAP explanation in three important settings. First, we consider fully-factorized data distributions, and show that the complexity of computing the SHAP explanation is the same as the complexity of computing the expected value of the model. This fully-factorized setting is often used to simplify the SHAP computation, yet our results show that the computation can be intractable for commonly used models such as logistic regression. Going beyond fully-factorized distributions, we show that computing SHAP explanations is already intractable for a very simple setting: computing SHAP explanations of trivial classifiers over naive Bayes distributions. Finally, we show that even computing SHAP over the empirical distribution is #P-hard.