SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism

AI summary

Overview

• Research area: Explainable AI (Shapley additive explanations, SHAP), computational complexity theory, and tensor-network machine learning.
• Technical level: Advanced. The paper assumes familiarity with complexity classes (P, NP, #P, NC, FPT, XP, para-NP), parameterized complexity, tensor contractions, and tensor-train decompositions.
• Scope: A complexity-theoretic analysis of exact SHAP computation for Tensor Networks, showing a #P-hard general case, an NC² parallel algorithm for Tensor Trains, tightened bounds for several ML models, and a fine-grained width/depth/sparsity analysis for binarized neural networks.

What This Paper Is About

SHAP is a widely used method for explaining model predictions, but exact SHAP values are NP-hard to compute for expressive models such as neural networks, exactly the models where explanations are most needed. This paper asks whether Tensor Networks — a model class broader and more expressive than the trees and linear models that current exact SHAP algorithms handle — admit provably exact SHAP computation, and under what structural conditions that computation becomes tractable or parallelizable. The authors answer yes for Tensor Trains, and use reductions to map out which neural-network parameters (width, depth, sparsity) actually drive the hardness.

Key Contributions

1. SHAP for general TNs. The paper introduces the first framework for computing provably exact SHAP explanations for general Tensor Networks with arbitrary structure, built on a tensorized reformulation of the SHAP formula (the Marginal SHAP Tensor) decomposed into a Modified Weighted Coalitional Tensor and a Marginal Value Tensor.

2. SHAP for Tensor Trains in NC. For Tensor Trains — a one-dimensional-topology subfamily of TNs — the paper shows SHAP computation is not only polynomial-time but lies in NC², i.e. solvable in poly-logarithmic time using a polynomial number of parallel processors, narrowing the expressivity gap between models with known exact SHAP algorithms and more expressive ones.

3. Tightened bounds for other ML models via reduction to TTs. Decision trees, tree ensembles, linear models, and linear RNNs are reduced to TTs, showing their Marginal SHAP computation lies in NC² across distribution classes that are more expressive than those previously considered.

4. Fine-grained SHAP analysis for Binarized Neural Networks. Using parameterized complexity and BNN-to-TT reductions, the paper shows SHAP for BNNs is para-NP-hard with respect to depth, in XP with respect to width, and in FPT with respect to width plus reified cardinality — identifying width, not depth, as the primary bottleneck.

Main Findings

• General TNs are hard. Computing Marginal SHAP values for general TNs is #P-Hard (Proposition 2). The proof reduces from #CNF-SAT, exploiting the polynomial reducibility of model counting to the SHAP problem and the polynomial-time construction of an equivalent TN from a CNF Boolean formula.

• TNs admit a tensorized SHAP formulation. Proposition 1 expresses the Marginal SHAP Tensor as a contraction 𝒯^(M,P) = 𝒲̃ ×_S 𝒱^(M,P), where 𝒲̃ is the Modified Weighted Coalitional Tensor and 𝒱^(M,P) is the Marginal Value Tensor.

• The weight tensor has a compact TT representation. Lemma 1 shows 𝒲̃ admits a TT representation whose first core is in ℝ^(n_in × 2 × n_in²), intermediate cores in ℝ^(n_i² × 2 × n_i²), and the last core in ℝ^(n_in² × 2). This representation is constructible in O(log(n_in)) time using O(n_in³) parallel processors.

• The marginal value tensor is built from "routers." Lemma 2 shows 𝒱^(M,P) is obtained by contracting sparse tensors ℳ^(i) ∈ ℝ^(N_i × 2 × N_i^⊗2) with 𝒯^M and 𝒯^P. Each ℳ^(i) is constructible in O(1) time using O(N_i²) parallel processors and acts as a router selecting either the instance value x or a value drawn from 𝒯^P for each feature.

• TTs give a TT-structured SHAP tensor. Theorem 1 shows that when both 𝒯^M and 𝒯^P are TTs, the Marginal SHAP Tensor is itself a TT, built by contracting the model core, distribution core, router core, and weight core at each position.

• SHAP for TTs is highly parallelizable. Proposition 3 places Marginal SHAP computation for TTs in NC². The procedure computes tensor cores in parallel (in NC¹, since matrix multiplication is in NC¹), then applies a parallel scan whose circuit depth scales as O(log²(n_in)).

• Bounds tighten for four other model families. Theorem 2 states that Marginal SHAP for decision trees, tree ensembles, linear models, and linear RNNs under the class of TT distributions lies in NC², via NC-reduction procedures that convert each model into an equivalent TT. The illustrative decision-tree construction (Figure 3) passes through a lattice of finite-state automata, producing cores G^(1) ∈ ℝ^(2×2) and G^(2) ∈ ℝ^(2×2×2) with rank 2.

• Broader distribution classes. The TT-based distribution class used here is described as more expressive than previously considered classes, englobing independent, empirical, Markovian, Hidden Markov distributions, and Born Machines.

• Width, not depth, drives BNN hardness. Theorem 3 covers three cases for BNNs under empirical, independent, or TT distribution classes: (1) Bounded depth — para-NP-Hard with respect to depth; (2) Bounded width — in XP with respect to width; (3) Bounded width and sparsity — in FPT with respect to width and reified cardinality. Intractability arises already with a single hidden layer, while fixed width plus sparsity makes SHAP efficiently tractable even for arbitrarily large networks.

• BNN-to-TT compilation cost. The proof sketch reports that compiling a BNN into an equivalent TT runs in O(R^W · poly(D, n_in, max_i N_i)) time, where W is the width and R relates to the reified cardinality parameters.

• First parallelizability analysis of SHAP. The authors state this is the first work providing a complexity-theoretic analysis of the computational parallelizability of SHAP computation.

• Not reported. The provided content does not report wall-clock runtime experiments, dataset sizes, or empirical accuracy benchmarks; the contributions are theoretical. Proofs are stated as sketches in the main text with complete proofs placed in the appendix, which is not included in the supplied content.

Methodology in Plain English

The authors treat SHAP computation as an object to be built and manipulated, rather than sampled. They first rewrite the standard SHAP formula in tensor form: instead of computing each feature's attribution separately, they define a single high-dimensional array (the Marginal SHAP Tensor) that stores attribution vectors for every possible input, every feature, and every output. This array is then factored into two pieces — one that carries the combinatorial SHAP weights, and one that carries the model's expected values under the data distribution — and the answer is obtained by contracting them.

To build the expected-value piece, they introduce small sparse "router" tensors, one per input feature, that decide whether a given feature keeps its value from the instance being explained or takes a value drawn from the data distribution. This reproduces the marginal (interventional) value function inside the tensor graph.

They then analyze how hard this contraction is. For arbitrary tensor networks, they show it is #P-hard by translating a Boolean formula counting problem into a tensor network. When the network is restricted to a linear chain (a Tensor Train), the contraction becomes a sequence of small matrix multiplications, which can be done with a parallel scan — a standard technique that finishes in logarithmic depth, placing the problem in NC².

Because many classical ML models can be rewritten as Tensor Trains, the same algorithm and complexity bound carry over to them. For binarized neural networks, the team compiles each layer into a small two-dimensional tensor network, contracts the layers backwards into a Tensor Train, and then applies the NC² procedure. Finally, they measure how the resulting cost depends on network size parameters — width, depth, and sparsity — using parameterized complexity to distinguish constant-factor tractability (FPT) from weaker guarantees (XP) and outright intractability (para-NP).

Why This Matters

Impact on research. The paper extends exact SHAP tractability from tree-based and linear models to a substantially more expressive class, and it reframes the SHAP hardness question from a binary "hard or not" statement into a fine-grained map of which structural parameters are responsible. It also opens a new line of inquiry — the parallel complexity of XAI computations — by showing that several classical models' SHAP values can be computed in poly-logarithmic parallel time.

Real-world applications.

• Explaining compressed or tensors-decomposed models, given TNs' established use in model compression and dimensionality reduction.
• Explaining models under complex feature dependencies, since the TT distribution class covers Markovian, Hidden Markov, and Born Machine distributions that capture dependencies beyond independent features.
• Formal verification and certification of binarized neural networks, since the reified cardinality representation used for the complexity analysis is drawn from work on improving verification efficiency.
• Explainability for settings where large numbers of attributions must be produced at once, which is where the parallel NC² result becomes practically relevant.

Industry relevance. Model-compression pipelines, quantized/binarized deployment on constrained hardware, and regulated domains that require consistent, reproducible (exact rather than sampled) explanations are the most direct beneficiaries. The width-vs-depth insight also gives practitioners a concrete architectural signal: for BNNs, shrinking width and enforcing sparsity buys tractable explanations in a way that shrinking depth does not.

Future Directions

• Identifying other tractable architectures. The authors explicitly invite broader theoretical investigation into structural parameters and architectures beyond those studied where SHAP may be tractable.
• New neural-network relaxations. The FPT result suggests a relaxed class of networks — bounded width plus bounded sparsity — that permits efficient SHAP computation; characterizing and training such networks is left open.
• Extending parallelizability results. The paper frames the polylogarithmic-time results for decision trees, tree ensembles, linear RNNs, and linear models as "paving the way" for a future research direction on when SHAP is efficiently parallelizable.
• Sharper parameterized bounds. The BNN analysis distinguishes para-NP, XP, and FPT regimes; refining these boundaries and testing other structural parameters (beyond width, depth, and reified cardinality) is a natural continuation.

Target Audience

This paper is aimed at researchers in explainable AI and computational complexity who work on exact attribution algorithms, and at theorists interested in tensor networks, parameterized complexity, and parallel algorithms. It also serves machine-learning practitioners concerned with compressed, quantized, or binarized models who need to know when exact SHAP is feasible and how to scale it. Readers without a background in complexity classes and tensor contractions will find the main text's proof sketches and figures more accessible than the full arguments, which are deferred to the appendix.

Authors’ abstract

Although Shapley additive explanations (SHAP) can be computed in polynomial time for simple models like decision trees, they unfortunately become NP-hard to compute for more expressive black-box models like neural networks - where generating explanations is often most critical. In this work, we analyze the problem of computing SHAP explanations for *Tensor Networks (TNs)*, a broader and more expressive class of models than those for which current exact SHAP algorithms are known to hold, and which is widely used for neural network abstraction and compression. First, we introduce a general framework for computing provably exact SHAP explanations for general TNs with arbitrary structures. Interestingly, we show that, when TNs are restricted to a *Tensor Train (TT)* structure, SHAP computation can be performed in *poly-logarithmic* time using *parallel* computation. Thanks to the expressiveness power of TTs, this complexity result can be generalized to many other popular ML models such as decision trees, tree ensembles, linear models, and linear RNNs, therefore tightening previously reported complexity results for these families of models. Finally, by leveraging reductions of binarized neural networks to Tensor Network representations, we demonstrate that SHAP computation can become *efficiently tractable* when the network's *width* is fixed, while it remains computationally hard even with constant *depth*. This highlights an important insight: for this class of models, width - rather than depth - emerges as the primary computational bottleneck in SHAP computation.