Polynomial Time Algorithms for Shapley Value Estimation

649 concepts442 papers2 proposals

When we ask a machine learning model to explain its prediction, we are essentially asking for a fair credit assignment problem. If a model predicts a high risk of heart disease based on a patient's age, blood pressure, and cholesterol, how much credit does each feature deserve?

In cooperative game theory, the Shapley value provides the unique mathematically rigorous solution to this problem. As established by Scott M Lundberg et al. in their foundational work on A Unified Approach to Interpreting Model Predictions, Shapley values are highly desirable because they uniquely satisfy a set of intuitive axioms, such as fairness and consistency.

However, computing them exactly introduces a massive computational hurdle: a combinatorial explosion. To find the true marginal contribution of a single feature, you must evaluate how the model behaves across every possible subset of all other features. For a model with $d$ features, this requires evaluating the model $2^d$ times. If $d=10$, we need 1,024 evaluations—trivial for a modern computer. But if $d=100$, or if we are dealing with image pixels where $d$ is in the thousands, exact calculation becomes completely intractable.

To bridge the gap between theoretical rigor and practical viability, a major research direction focuses on bypassing this exponential bottleneck, transforming an $O(2^d)$ problem into a tractable polynomial-time operation.


Structural Tractability: Bypassing the Exponential Sum

One of the most powerful ways to beat the combinatorial explosion is to exploit the mathematical structure of the underlying model. If a model's internal functions can be factorized, we can compute exact Shapley values without ever evaluating all $2^d$ subsets individually.

Product-Kernel Methods

For instance, consider kernel-based models like Support Vector Machines or Gaussian Processes that use product kernels (such as RBF or Laplacian kernels). In Computing Exact Shapley Values in Polynomial Time for Product-Kernel Methods, Majid Mohammadi et al. introduced PKeX-Shapley.

The core intuition here is that because a product kernel factorizes across input dimensions, the expectation over feature subsets can also be factorized. Instead of computing a massive joint sum over combinations, the algorithm computes a series of independent, low-dimensional integrals. This algebraic shortcut collapses the exponential complexity into polynomial time, yielding perfectly exact attributions without the noise of random sampling. The authors extended this structural insight in Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes, demonstrating that for FANOVA Gaussian Processes, exact Shapley values can be extracted in a mere $O(d^2)$ quadratic time.

Tensor Networks

A similar philosophy applies to complex multi-dimensional interactions. In Tractable Shapley Values and Interactions via Tensor Networks, Farzaneh Heidari et al. introduced TN-SHAP.

Instead of treating the model as a black box, the authors represent the local behavior of a model as a Tensor Network (TN). Tensor networks break down a massive, high-dimensional tensor (representing all feature interactions) into a chain of smaller, interconnected low-rank tensors. By leveraging a polynomial interpolation trick on this network, they contract the tensors sequentially. This avoids the exponential explosion entirely, dropping the cost of calculating both Shapley values and higher-order feature interactions down to linear $O(d)$ time.


Advanced Approximation and Variance Reduction

When we cannot assume a specific model structure, we must treat the model as a black box and rely on sampling subsets of features. However, naive sampling suffers from high variance, meaning the explanations change every time you run them. Recent breakthroughs reframe how we sample to achieve rapid convergence.

Control Variates

To stabilize sampling-based estimators like KernelSHAP, Jeremy Goldwasser et al. proposed ControlSHAP in Stabilizing Estimates of Shapley Values with Control Variates.

The intuition behind a control variate is simple: if you want to estimate something complex and noisy, find a correlated proxy that you can compute easily, and use it to cancel out the noise. The authors use a local Taylor expansion of the model as the proxy. Because the linear trend is captured exactly by the Taylor expansion, the sampler only needs to evaluate the highly non-linear residuals. This reduces the variance of the estimates by up to 90% without adding significant computational overhead.

[Raw Model Output] ---> High Variance Sampling (Slow Convergence)
       ^
       | (Subtract Linear Proxy via Taylor Expansion)
       v
[Residual Variance] ---> Low Variance Sampling (Fast Convergence)

Sparse Fourier Representations

Another perspective treats the subset selection process as a boolean function mapping a binary vector (where $1$ means a feature is present and $0$ means it is absent) to a model prediction. In SHAP values via sparse Fourier representation, Ali Gorji et al. introduced FourierSHAP.

By transforming this boolean function into the frequency domain using a Fourier representation, the authors show that most real-world models are "low-degree" or sparse in their feature interactions. By approximating the model with a sparse set of Fourier coefficients, they derive a closed-form formula that evaluates Shapley values near-instantaneously, bypassing iterative sampling entirely.

Optimization with Momentum

Rather than treating estimation as a pure sampling problem, it can also be framed as an optimization task. In SIM-Shapley: A Stable and Computationally Efficient Approach to Shapley Value Approximation, Wangxuan Fan et al. developed SIM-Shapley. They reframe the game-theoretic attribution problem as a stochastic optimization task, utilizing momentum to smooth out the gradient steps taken during subset sampling. This approach accelerates convergence by up to 85% compared to standard implementations.


Provable Efficiency in Deep Learning

Deep neural networks present a unique challenge: they are non-linear, high-dimensional, and lack the clean factorization of kernel methods. To scale Shapley values to deep architectures, researchers rely on clever propagation techniques and rigorous sample complexity bounds.

In Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Value Approximation, Marco Ancona et al. introduced Deep Approximate Shapley Propagation (DASP). DASP avoids evaluating explicit feature subsets by leveraging uncertainty propagation. By treating the presence or absence of an input feature as a random variable, the authors propagate the mean and variance of these feature distributions layer-by-layer through the network. This allows them to approximate the marginal contributions of all features simultaneously in a single forward-backward pass, achieving polynomial-time scaling for deep models.

For practitioners who prefer model-agnostic sampling, understanding the exact boundaries of efficiency is critical. To address this, Tyler Chen et al. established the first non-asymptotic sample complexity bounds for KernelSHAP in A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values. Their mathematical framework provides strict theoretical guarantees on exactly how many samples are required to reach a target precision, allowing these estimators to scale reliably to high-dimensional datasets like image classification networks.

By shifting the paradigm from brute-force combinatorial evaluation to structural factorization, variance reduction, and uncertainty propagation, this research direction ensures that game-theoretic interpretability can scale alongside the growing complexity of modern artificial intelligence.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 461 papers
  2. Version 1 · 2026-10-04 · 603 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_explosion_in_feature_attri_90a41130,
  title = {combinatorial explosion in feature attribution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-explosion-in-feature-attribution/rdr_90a41130cd5842b6b38576442349f47b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_combinatorial_explosion_in_feature_attri_90a41130_v2,
  title = {combinatorial explosion in feature attribution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-explosion-in-feature-attribution/rdr_90a41130cd5842b6b38576442349f47b/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake