Research map / Learning theory and algorithms / Prediction and decision losses
SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that exact Marginal SHAP for tensor networks is #P-hard in general, but in NC^2 for tensor trains, extends this to trees, ensembles, linear models and linear RNNs, and gives width/sparsity parameterized results for binarized neural networks.
Problem
Computing exact SHAP values is NP-hard for expressive black-box models such as neural networks, and prior tractable exact algorithms cover only simple models like trees and linear models.
Approach
Tensorizes the marginal SHAP computation as a contraction of a modified weighted coalition tensor with a marginal value tensor, shows that for tensor trains this yields a TT that can be contracted with a parallel scan (NC), reduces tree ensembles, decision trees, linear models and linear RNNs to TTs, and compiles BNNs into TTs whose cost depends on width and reified cardinality.
Key results
- Marginal SHAP for general tensor networks is #P-hard, while for tensor trains it lies in NC^2 (polylogarithmic time with polynomially many parallel processors).
- Decision trees, tree ensembles, linear models and linear RNNs under tensor-train distributions are shown to lie in NC^2 via reductions to tensor trains.
- BNN SHAP is para-NP-hard with respect to depth, in XP for bounded width, and in FPT for bounded width and reified cardinality.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Represent arbitrary-structure Tensor Networks with the exact SHAP framework | Tensor Networks · General Tensor Networks | SHAP computation complexity | Mixed |
| Restrict both the model and distribution to Tensor Trains | SHAP computation · Tensor Trains | SHAP computation complexity | Helped |
| Reduce decision trees, tree ensembles, linear models, and linear RNNs to equivalent Tensor Trains | SHAP computation for classical model families · Decision trees, tree ensembles, linear models, and linear RNNs; TT distributions | SHAP computation complexity | Helped |
| Fix network depth to a constant | BNN SHAP computation · BNNs; any distribution class P | SHAP computation complexity | Hurt |
| Bound network width | BNN SHAP computation · BNNs; any distribution class P | SHAP computation complexity | Helped |
| Bound network width and reified cardinality | BNN SHAP computation · BNNs; any distribution class P | SHAP computation complexity | Helped |
Surprising findings
- Even a depth-2 (single hidden layer) BNN makes SHAP NP-hard, so depth alone does not give tractability.
- Width, not depth, is identified as the main computational bottleneck for SHAP in BNNs.
Limitations
- Purely theoretical; no empirical experiments or implementation evaluation are reported.
- Tractability for BNNs requires fixing width and sparsity (reified cardinality), which restricts the model class.
- Results are for marginal (interventional) SHAP with the stated distribution classes; other value functions are left to future work.
Experimental setup
Builds on: TreeSHAP marginal SHAP value function reified cardinality constraints for BNNs
Closest papers by meaning
- Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations (ICML 2025 · similarity 0.88)
- SHAP values via sparse Fourier representation (NeurIPS 2025 · similarity 0.88)
- On the Tractability of SHAP Explanations under Markovian Distributions (ICML 2024 · similarity 0.87)
- Shaping Up SHAP: Enhancing Stability through Layer-Wise Neighbor Selection (AAAI 2024 · similarity 0.86)
- Convolutions and More as Einsum: A Tensor Network Perspective with Advances for Second-Order Methods (NeurIPS 2024 · similarity 0.86)
- InstaSHAP: Interpretable Additive Models Explain Shapley Values Instantly (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.