Tractable Shapley Value Attribution for Deep Learning Explanations

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2603 papers716 conceptsfrozen 2026-10-04

In the effort to open the "black box" of modern machine learning, researchers have converged on a gold standard for fairness: the Shapley value. Borrowed from cooperative game theory, this metric provides a mathematically rigorous way to distribute "payouts" (a model's prediction) among "players" (the input features).

As Scott M. Lundberg and Su-In Lee established in A Unified Approach to Interpreting Model Predictions, Shapley values are unique because they are the only attribution method that satisfies a set of desirable axioms, such as consistency and local accuracy. However, they come with a devastating catch: calculating them exactly requires evaluating a model on every possible subset of features—an exponential task that becomes impossible as soon as a model has more than a few dozen inputs.

The central challenge of this research direction is overcoming this combinatorial explosion to make rigorous explanations practical for deep neural networks, large language models, and high-dimensional datasets.

The Combinatorial Wall

To understand why Shapley values are so expensive, imagine explaining a sentiment classifier for a 10-word sentence. To find the "fair" contribution of the third word, you must see how the model reacts to that word in every possible context: by itself, paired with the first word, paired with the first and second, and so on. For $n$ features, there are $2^n$ such combinations.

As Mikaël Monet and colleagues demonstrate in The Tractability of SHAP-scores over Deterministic and Decomposable Boolean Circuits, this problem is fundamentally #P-hard. This means that for general models, we cannot simply wait for faster computers; we must change how we compute the values.

Exploiting Model Structure for Exact Solutions

One way to bypass the $2^n$ requirement is to look inside the model's architecture. If we know how the model processes information, we can sometimes calculate the sum of all marginal contributions without visiting every subset individually.

  • Tree-based Models: Peng Yu and Albert Bifet introduced Linear TreeShap, which reduces the complexity of explaining decision trees to linear time relative to the tree's depth.
  • Kernel Methods: For models using specific mathematical kernels (like RBF), Majid Mohammadi and Krikamol Muandet developed PKeX-Shapley, which achieves polynomial-time exact attribution by leveraging the properties of product kernels.

Intelligent Approximation and Sampling

When the model's internal structure is too complex (like a Transformer), researchers turn to sophisticated sampling. The goal is to estimate the Shapley value using only a tiny fraction of the $2^n$ possible subsets.

Marco Ancona and Cengiz Öztireli proposed Deep Approximate Shapley Propagation (DASP), which uses uncertainty propagation to estimate contributions in polynomial time. More recently, Fan Yang and Mengnan Du introduced SHEAR (Accelerating Shapley Explanation via Contributive Cooperator Selection), which uses a "Shapley chain rule" to identify and prioritize only the most influential feature interactions, drastically reducing the number of model evaluations needed.

Moving from Post-hoc to Intrinsic Interpretability

A radical shift in this field is the move away from "post-hoc" explanations (explaining a model after it is trained) toward intrinsic interpretability. Here, the model is designed from the ground up to produce Shapley values as part of its standard operation.

In HarsanyiNet, Quanshi Zhang and Lu Chen redesigned neural network neurons to represent "Harsanyi interactions." This allows the network to output exact Shapley values in a single forward pass. Similarly, AutoGnothi by Shaobo Wang uses side-tuning to enable black-box models like Transformers to generate their own theoretically grounded explanations with minimal overhead.

Beyond Simple Attribution

Once Shapley values become computationally cheap, they can be used for more than just "explaining" a prediction; they can be used to improve the model itself:

  1. Model Pruning: William Barr Held and Diyi Yang showed in Shapley Head Pruning that identifying and removing "harmful" attention heads using Shapley values can actually increase a multilingual model's performance.
  2. Regularization: Qisen Cheng and Shuhui Qu developed SHAPNN, which uses Shapley values as a penalty during training, forcing the model to focus on truly important features rather than noise.
  3. Reinforcement Learning: In RSA2C, Hangguan Shan and colleagues use these attributions to prioritize state dimensions, making RL agents more stable and interpretable.

By transforming the Shapley value from a theoretical ideal into a tractable computational tool, this research direction ensures that as our models grow more complex, our ability to understand and trust them can keep pace.

Papers in this version

Showing 60 of 603 papers.

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 1, frozen text):

@misc{lacuna_tractable_shapley_value_attribution_for__90a41130_v1,
  title = {Tractable Shapley Value Attribution for Deep Learning Explanations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tractable-shapley-value-attribution-for-deep-learning-explanations/rdr_90a41130cd5842b6b38576442349f47b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}