The Combinatorial Bottleneck of Explainability
To trust a machine learning model's prediction, we often want to know how much each input feature contributed to the outcome. The gold standard for this type of credit assignment is the Shapley value (and its model-explanation variant, SHAP). Derived from cooperative game theory, the Shapley value is uniquely desirable because it is the only attribution method that satisfies a set of core mathematical axioms ensuring fairness.
However, calculating exact Shapley values comes with a severe computational penalty. To find the true importance of a single feature, you must evaluate how the model's prediction changes when that feature is added to every possible subset of other features. For a model with $d$ features, this requires evaluating the model across $2^d$ combinations.
Because of this combinatorial explosion, computing exact feature attributions is generally NP-hard or #P-hard. In practice, practitioners almost always resort to sampling approximations. While approximations work well for simple cases, they introduce statistical noise and variance—flaws that can lead to unstable or misleading explanations in high-stakes domains like medicine or drug discovery.
A growing body of research addresses this bottleneck by asking a fundamental question: Can we design or compile models such that exact feature attributions can be computed in polynomial time? The answer is yes. By exploiting specific structural properties of models or data distributions, we can bypass the $2^d$ brute-force search entirely.
The Core Insight: Distributivity and Factorization
To understand why structural tractability is possible, consider a simple mathematical analogy. Suppose you want to compute the sum of all possible products of a set of variables:
$$\sum_{S \subseteq \{x_1, x_2, x_3\}} \prod_{i \in S} x_i$$
Evaluating every subset individually requires exponential time. However, due to the distributive property of algebra, this entire sum can be refactored into a simple product:
$$(1 + x_1)(1 + x_2)(1 + x_3)$$
By expanding the expression into a factored form, we reduce an exponential number of additions to a linear number of multiplications.
This is the foundational trick behind polynomial-time feature attribution. If a machine learning model's internal architecture allows us to "push" the summation over feature subsets inside its mathematical operations, we can compute exact attributions in polynomial time (often quadratic $O(d^2)$ or linear $O(d)$).
Knowledge Compilation and Circuit Structure
One of the most rigorous environments for this approach is the domain of logical and probabilistic circuits. Instead of explaining an arbitrary "black box," researchers compile classifiers into structured representations that guarantee efficient queries.
In The Tractability of SHAP-Score-Based Explanations for Classification over Deterministic and Decomposable Boolean Circuits, Marcelo Arenas et al. demonstrated that exact SHAP scores can be computed in polynomial time for Boolean classifiers, provided they exhibit two structural properties:
- Determinism: No two paths through the circuit can be true for the same input.
- Decomposability: Sub-circuits operate on strictly disjoint sets of variables.
When a circuit is decomposable, the features are independent within their respective sub-trees, allowing the exponential subset summation to factorize neatly. When it is deterministic, the probabilities of different paths do not double-count the same underlying states. In a follow-up work, On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results, the authors proved that these two properties define a strict computational boundary: removing either property immediately causes the problem to escalate back to #P-hardness, rendering even close approximations intractable.
This architectural strategy extends naturally to probabilistic models. Guy Van den Broeck et al. showed in On the Tractability of SHAP Explanations that tractable probabilistic circuits—such as decomposable deterministic negation normal forms—can be leveraged to compute both expected values and exact feature attributions in polynomial time, providing a clear path to maintaining exact explainability without sacrificing model expressivity.
Exploiting Multiplicative and Tensor Structures
For continuous models like Support Vector Machines (SVMs), Gaussian Processes, and Neural Networks, tractability is achieved by exploiting algebraic structures like product kernels and tensor decompositions.
Consider kernel methods that rely on Radial Basis Function (RBF) or Laplacian kernels. These are product kernels, meaning the kernel evaluation over a vector can be factored into a product of independent kernel evaluations over individual features. In Computing Exact Shapley Values in Polynomial Time for Product-Kernel Methods, Majid Mohammadi et al. introduced an algorithm (PKeX-Shapley) that exploits this multiplicative structure. By refactoring the kernel's internal math, the authors reduced the complexity of exact Shapley computation to quadratic time ($O(d^2)$) relative to the number of features, bypassing sampling noise entirely.
The authors extended this insight to Gaussian Processes in Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes, demonstrating that if a Gaussian Process utilizes orthogonal additive kernels, exact local and global Shapley values can be computed in $O(d^2)$ time. Similarly, for SVMs with RBF kernels, Andrea Mastropietro et al. developed the SVERAD algorithm, which scales linearly with the number of support vectors and quadratically with features, opening up exact interpretation for high-dimensional biological datasets (Calculation of exact Shapley values for explaining support vector machine models using the radial basis function kernel).
When a model does not naturally possess a product structure, we can approximate its local behavior using a structured surrogate. In Tractable Shapley Values and Interactions via Tensor Networks, Farzaneh Heidari et al. proposed representing local model behaviors as a Tensor Network (TN). By combining this low-rank tensor representation with a polynomial interpolation trick, the authors compressed the combinatorial search space down to linear time ($O(d)$), enabling the rapid calculation of both individual feature attributions and higher-order feature interactions. Even in deep neural networks, the authors of Scalable, Axiomatic Explanations of Deep Alzheimer's Diagnosis from Heterogeneous Data showed that transforming network layers into probabilistic representations can collapse the computational complexity of axiomatic attribution from exponential to quadratic.
Bounded Overlap and Structured Distributions in Trees
Tree-based architectures, such as decision trees and random forests, are often celebrated for their transparency. However, computing formal, probabilistic explanations for them can still be computationally intractable if the features interact in complex ways.
The tractability of tree-based explanations depends heavily on how features are shared across different branches. In On Computing Probabilistic Explanations for Decision Trees, Alexander Kozachinskiy et al. isolated a structural metric called the split number, which quantifies the degree of feature overlap between a specific subtree and the rest of the model. When this split number is bounded, it implies a high degree of local independence, which the authors proved allows both minimum and minimal probabilistic explanations to be computed in polynomial time. This aligns with work by Xuanxiang Huang et al., who showed that determining whether a feature belongs to a valid explanation is solvable in polynomial time for tree-based decision graphs, whereas it remains NP-hard for general logic formulas (On Efficiently Explaining Graph-Based Classifiers).
[General Logic Formulas] [Standard Decision Trees] [Constrained Trees / Circuits]
---------------------------- ---------------------------- ------------------------------
Complexity: NP-hard / #P-hard Complexity: Often Intractable Complexity: Polynomial Time
Features interact globally High feature overlap (Splits) Bounded splits / Decomposable
Beyond the structure of the model itself, the structure of the data distribution plays a critical role. Standard polynomial-time SHAP calculations for trees often assume that all input features are independent—an assumption rarely met in the real world. To bridge this gap, Reda Marzouk et al. demonstrated in On the Tractability of SHAP Explanations under Markovian Distributions that if feature correlations are structured as a first-order Markov chain, exact SHAP values can still be computed in polynomial time for decision trees and weighted automata.
Finally, tailoring algorithms to specific loss functions can yield massive efficiency gains. For tree-boosting models evaluating quadratic losses (like $R^2$), Zhongli Jiang et al. introduced Q-SHAP, an algorithm that accelerates Shapley value calculations to make exact attribution practical for high-dimensional datasets where traditional combinatorial methods fail (Fast Calculation of Feature Contributions in Boosting Trees).
Summary
The frontier of polynomial-time feature attribution shifts the focus of explainable AI away from post-hoc approximations and toward structural design. Whether by enforcing determinism and decomposability in logical circuits, exploiting the multiplicative nature of product kernels, or bounding feature overlap in trees, these methods prove that we do not have to choose between mathematical precision and computational efficiency.
Key Foundational Work
On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results (2023) — contributed 4 concept elements to this direction.
Calculation of exact Shapley values for explaining support vector machine models using the radial basis function kernel (2023) — contributed 3 concept elements to this direction.
The Tractability of SHAP-Score-Based Explanations for Classification over Deterministic and Decomposable Boolean Circuits (2021) — contributed 2 concept elements to this direction.