# On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 60 references that are in the map.
- First posted on arXiv 16 Apr 2021.

## 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)
- [Towards Causal Representation Learning](https://mlsanity.com/paper/2102.11107/) (2021)
- [Problems with Shapley-value-based explanations as feature importance measures](https://mlsanity.com/paper/2002.11097/) (2020)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [CausalWorld: A Robotic Manipulation Benchmark for Causal Structure and Transfer Learning](https://mlsanity.com/paper/2010.04296/) (2020)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [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)
- [When Explainability Meets Adversarial Learning: Detecting Adversarial Examples using SHAP Signatures](https://mlsanity.com/paper/1909.03418/) (2019)
- [On Tractable Representations of Binary Neural Networks](https://mlsanity.com/paper/2004.02082/) (2020)
- [An Interpretable Model with Globally Consistent Explanations for Credit Risk](https://mlsanity.com/paper/1811.12615/) (2018)
- [A Multilinear Sampling Algorithm to Estimate Shapley Values](https://mlsanity.com/paper/2010.12082/) (2020)
- [Causality-based Explanation of Classification Outcomes](https://mlsanity.com/paper/2003.06868/) (2020)
- [Generating Counterfactual and Contrastive Explanations using SHAP](https://mlsanity.com/paper/1906.09293/) (2019)
- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [On Symbolically Encoding the Behavior of Random Forests](https://mlsanity.com/paper/2007.01493/) (2020)
- [Efficient Computation of the Shapley Value for Game-Theoretic Network Centrality](https://mlsanity.com/paper/1402.0567/) (2014)
- [Smoothing Structured Decomposable Circuits](https://mlsanity.com/paper/1906.00311/) (2019)
- [Connecting Knowledge Compilation Classes and Width Parameters](https://mlsanity.com/paper/1811.02944/) (2018)

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

- [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)
- [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023)
- [On Formal Feature Attribution and Its Approximation](https://mlsanity.com/paper/2307.03380/) (2023)
- [On the Tractability of SHAP Explanations under Markovian Distributions](https://mlsanity.com/paper/2405.02936/) (2024)
- [From SHAP Scores to Feature Importance Scores](https://mlsanity.com/paper/2405.11766/) (2024)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases](https://mlsanity.com/paper/2401.06493/) (2024)
- [ExplainerPFN: Towards tabular foundation models for model-free zero-shot feature importance estimations](https://mlsanity.com/paper/2601.23068/) (2026)
- [A Refutation of Shapley Values for Explainability](https://mlsanity.com/paper/2309.03041/) (2023)
- [Refutation of Shapley Values for XAI -- Additional Evidence](https://mlsanity.com/paper/2310.00416/) (2023)
- [UbiQTree: Uncertainty Quantification in XAI with Tree Ensembles](https://mlsanity.com/paper/2508.09639/) (2025)
- [Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilation](https://mlsanity.com/paper/2303.06516/) (2023)
- [On the Complexity of Global Necessary Reasons to Explain Classification](https://mlsanity.com/paper/2501.06766/) (2025)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [Attribution-Scores in Data Management and Explainable Machine Learning](https://mlsanity.com/paper/2308.00184/) (2023)
- [Logic-Based Explainability: Past, Present & Future](https://mlsanity.com/paper/2406.11873/) (2024)
- [When is the Computation of a Feature Attribution Method Tractable?](https://mlsanity.com/paper/2501.02356/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [The Distributional Uncertainty of the SHAP score in Explainable Machine Learning](https://mlsanity.com/paper/2401.12731/) (2024)
- [The Explanation Game -- Rekindled (Extended Version)](https://mlsanity.com/paper/2501.11429/) (2025)
- [Feature Relevancy, Necessity and Usefulness: Complexity and Algorithms](https://mlsanity.com/paper/2505.09640/) (2025)
- [Interaction Tensor SHAP](https://mlsanity.com/paper/2512.05338/) (2025)
- [Neural Dynamic Data Valuation via Stochastic State-Adjoint Trajectories](https://mlsanity.com/paper/2404.19557/) (2024)
- [The Sets of Power](https://mlsanity.com/paper/2410.07867/) (2024)
- [Rigorous Feature Importance Scores based on Shapley Value and Banzhaf Index](https://mlsanity.com/paper/2508.11959/) (2025)
- [TT-FSI: Scalable Faithful Shapley Interactions via Tensor-Train](https://mlsanity.com/paper/2601.01903/) (2026)
- [NetworkNet: A Deep Neural Network Approach for Random Networks with Sparse Nodal Attributes and Complex Nodal Heterogeneity](https://mlsanity.com/paper/2604.11673/) (2026)
- [Towards Rigorous Explainability by Feature Attribution](https://mlsanity.com/paper/2604.15898/) (2026)
- [Reconciling Consistency-Based Diagnosis with Actual-Causality-Based Explanations](https://mlsanity.com/paper/2605.08688/) (2026)

## Abstract (arXiv)

In Machine Learning, the mathsfSHAP-score is a version of the Shapley value that is used to explain the result of a learned model on a specific entity by assigning a score to every feature. While in general computing Shapley values is an intractable problem, we prove a strong positive result stating that the mathsfSHAP-score can be computed in polynomial time over deterministic and decomposable Boolean circuits. Such circuits are studied in the field of Knowledge Compilation and generalize a wide range of Boolean circuits and binary decision diagrams classes, including binary decision trees and Ordered Binary Decision Diagrams (OBDDs). We also establish the computational limits of the SHAP-score by observing that computing it over a class of Boolean models is always polynomially as hard as the model counting problem for that class. This implies that both determinism and decomposability are essential properties for the circuits that we consider. It also implies that computing mathsfSHAP-scores is intractable as well over the class of propositional formulas in DNF. Based on this negative result, we look for the existence of fully-polynomial randomized approximation schemes (FPRAS) for computing mathsfSHAP-scores over such class. In contrast to the model counting problem for DNF formulas, which admits an FPRAS, we prove that no such FPRAS exists for the computation of mathsfSHAP-scores. Surprisingly, this negative result holds even for the class of monotone formulas in DNF. These techniques can be further extended to prove another strong negative result: Under widely believed complexity assumptions, there is no polynomial-time algorithm that checks, given a monotone DNF formula varphi and features x,y, whether the mathsfSHAP-score of x in varphi is smaller than the mathsfSHAP-score of y in varphi.