On the Tractability of SHAP Explanations

SHAP is the dominant method for explaining machine learning predictions. It’s used across academia and industry, embedded in toolkits, cited in regulatory discussions, and deployed in medical software. However, it turns out that for many of the most common models, computing SHAP exactly is not just slow; it is provably, mathematically impossible to do efficiently. That’s not merely a practical complaint about scale; it’s a theorem. Van den Broeck, Lykov, Schleich, and Suciu set out to map exactly where that impossibility exists, and where it doesn’t. The result is one of the cleaner complexity papers in explainable artificial intelligence: a precise accounting of when SHAP can be trusted to be computable and when it cannot. Let’s start with what SHAP actually is. The idea comes from cooperative game theory, specifically from the Shapley value, which is a classical method for dividing the total payoff of a coalition among its members. Lundberg and Lee imported that idea into machine learning in 2017. They treat the features of a model as players, consider the model’s prediction as the payoff, and use the Shapley averaging procedure to assign each feature a contribution score. In concrete terms, a feature’s SHAP score is the average, across every possible subset of the other features, of how much the model’s prediction changes when that feature joins the subset. You can imagine every coalition, measure the marginal contribution of the feature to each one, and average it. Strumbelj and Kononenko, along with Datta, Sen, and Zick, had earlier argued that this game-theoretic framing satisfies desirable fairness-like axioms that other attribution methods do not. This principled foundation is why SHAP took over. However, the definition immediately creates a computational burden: to compute those scores, you must evaluate the model’s expected output across many subsets of features. The question the paper poses is simple and had not been answered: can you actually do that efficiently? The first setting the paper analyzes is the one most implementations use as a shortcut: the fully factorized distribution, where features are assumed to be independent of each other. Independence is supposed to simplify the problem, but it does not — in a precise sense. Theorem 2 establishes a polynomial-time equivalence: computing SHAP under a fully factorized distribution is exactly as hard as computing the expected value of the model under that same distribution. It’s not harder, and it’s not easier — it’s the same problem. One direction follows from the identity connecting expectation and SHAP scores: the model’s expected value equals the model’s prediction at a given instance, minus the sum of all the SHAP scores. The other direction is constructive; given an oracle for expectations, you can recover every SHAP score with a linear number of oracle calls and a cubic-time linear algebra step. This equivalence is the load-bearing result of the paper. Everything else follows from it. Because computing SHAP under independence reduces to computing expectations, whether SHAP is tractable for a given model class depends entirely on whether expectations are tractable for that class. Here, the paper delivers the key blow: Theorem 6 proves that computing the expected value of a logistic regression model, one of the most widely used models in machine learning, under the uniform data distribution is #P-hard. The proof reduces the number-partitioning counting problem to the expectation of a logistic model, using a logistic function with carefully chosen weights and an error parameter that is small enough so that the expectation determines whether a partition solution exists. From Theorem 2, it immediately follows that computing exact SHAP scores for logistic regression under independent features is also #P-hard. The shortcut was supposed to be the easy case, but it isn’t. The second setting the paper analyzes strips the model down to almost nothing and asks whether the hardness could be coming from model complexity. It isn’t. The authors study naive Bayes distributions, which is a classic probabilistic model where features are conditionally independent given a class variable, while using literally the simplest possible classifier: the function that just returns the class variable’s value. This model has no hidden complexity whatsoever. Yet computing its SHAP score over a naive Bayes distribution is NP-hard and #P-hard. The proof again reduces from number partitioning, constructing conditional probabilities in the naive Bayes network so that whether the partition problem has a solution is equivalent to whether the SHAP value of the class variable exceeds a threshold. The hardness, in other words, lies entirely in the distribution. The model is trivial; the distribution is not; and that’s enough. This finding inverts a natural intuition that simpler models are easier to explain. The paper explicitly defines the reach of this result: the same intractability extends to bounded-treewidth Bayesian networks, Markov networks, factor graphs, and decomposable probabilistic circuits, all of which can represent naive Bayes dependencies. The third escape hatch the paper closes is the most practically tempting. Forget theoretical distributions entirely, a practitioner might say; just use the actual training data as the distribution — the empirical distribution. That’s what TreeSHAP, the widely used efficient implementation, approximates. Theorem 12 shuts this down. For the class of empirical distributions represented as binary matrices, computing SHAP is polynomial-time equivalent to calculating the expectation of positive partitioned two-CNF formulas — a class of logical formulas — under quasi-symmetric distributions. A quasi-symmetric distribution is a fully factorized distribution where probabilities take only two possible values. The expectation problem for this formula class is #P-hard, as established by Provan and Ball in 1983, and the equivalence transfers that hardness directly to empirical SHAP. The dataset has only finitely many rows; that finiteness turns out not to help. Corollary 13 states the result flatly: SHAP over the empirical distribution is #P-hard in relation to the size of the dataset. The paper also pinpoints what TreeSHAP is actually doing: it’s efficient because it computes expectations under a distribution defined by the tree structure of the model, rather than the exact conditional expectations that SHAP requires. The gap between TreeSHAP and exact SHAP is not a numerical approximation; it’s a different quantity, and the paper makes that distinction precise. Taken together, these three results — independence doesn’t help for logistic regression, simplifying the model doesn’t help over naive Bayes, and using the training data doesn’t help either — form a coherent picture. The hardness of SHAP isn’t limited to exotic settings; it appears in the most natural configurations that practitioners actually use. The paper does not leave the field without a positive map. Corollary 5 identifies model classes where SHAP is computable in polynomial time under fully factorized distributions: linear regression, decision and regression trees, random forests and additive tree ensembles, factorization machines and regression circuits, and Boolean functions represented as decomposable negation normal form circuits or binary decision diagrams. For these classes, expectations are tractable — linear regression by mean imputation, trees by summing over root-to-leaf paths, and circuits by weighted model counting. Because SHAP reduces to expectation, the efficiency carries through. Bounded-treewidth CNF formulas also fall under this category since low treewidth, meaning the dependency structure is close enough to a tree, allows compilation into tractable circuit representations. The algorithmic cost of turning an expectation oracle into exact SHAP scores is a linear number of oracle calls plus cubic-time linear algebra. For model families where expectations are linear in the circuit representation size, computing SHAP is linear in that size and polynomial in the number of features. The practical design message is direct: if you want provably exact SHAP, you may need to constrain your model family — choose trees, linear models, or low-complexity circuits — not just your distributional assumptions. Every SHAP explanation deployed in a product, a clinical decision tool, or a regulatory audit is either approximating something that is #P-hard to compute exactly, or it is computing a different quantity than the SHAP definition specifies. The paper’s complexity map does not imply that explanations are useless. It indicates that the gap between what practitioners compute and what SHAP actually requires is not merely a computational inconvenience; it’s a structural feature of the problem. Slack and colleagues in 2020 showed that approximation-based SHAP can produce counterintuitive explanations; the theoretical results here explain why. Van den Broeck and colleagues conclude by framing that map as a guide: the tractable islands they identified — probabilistic circuits, symmetric probability spaces, low-treewidth structures — are the areas where future work on provably exact, efficient explanations should be directed. The hard cases are now precisely known, and that’s where the work begins. This lecture was created by ennepō. Go to https://ennepo.ai to Discover, Create and Follow the latest research in your field. Read when you can. Listen when you want to.