⚛️ quantum physics

SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism

This paper introduces a framework for computing provably exact SHAP explanations for Tensor Networks, demonstrating that while the problem is generally hard, it becomes poly-logarithmically tractable via parallel computation for Tensor Train structures, thereby revealing that model width—not depth—is the primary computational bottleneck for SHAP in binarized neural networks.

Original authors: Reda Marzouk, Shahaf Bassan, Guy Katz

Published 2026-03-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Reda Marzouk, Shahaf Bassan, Guy Katz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but mysterious, black box. You put data in, and it gives you an answer (like "This loan should be approved" or "This email is spam"). You want to know why it made that decision. Which specific pieces of information (features) mattered most?

This is where SHAP comes in. Think of SHAP as a fair referee that goes through every possible combination of clues to see how much each clue contributed to the final verdict.

However, there's a problem: For simple models (like a basic decision tree), the referee can do the math quickly. But for complex, modern AI models (like deep neural networks), the math becomes so huge that it would take longer than the age of the universe to calculate the exact answer. It's like trying to count every single grain of sand on a beach by hand.

This paper, "SHAP Meets Tensor Networks," introduces a new way to solve this counting problem, making it fast and even parallelizable (like having a whole army of referees working at once).

Here is the breakdown using simple analogies:

1. The Problem: The "Grain of Sand" Nightmare

Imagine you are trying to explain a complex decision made by a neural network. To do this perfectly (exactly), you have to check every possible scenario.

The Old Way: If the network is complex, the number of scenarios is so massive that it's impossible to finish the job. It's like trying to find a specific needle in a haystack the size of a galaxy.
The Result: We usually have to settle for "guesses" (approximations) because the exact math is too hard.

2. The New Tool: Tensor Networks (The "Lego" Solution)

The authors focus on a specific type of model called Tensor Networks (TNs).

The Analogy: Think of a giant, complex 3D sculpture made of millions of Lego bricks. It's hard to understand the whole thing at once.
The Trick: A Tensor Network breaks that giant sculpture down into a chain of smaller, manageable Lego blocks connected together. Instead of looking at the whole galaxy-sized haystack, you look at a neat, organized line of Lego blocks.

The paper shows that if we represent our AI models as these Lego chains, we can finally do the exact SHAP math without getting stuck.

3. The Star Player: Tensor Trains (The "Assembly Line")

Among all the ways to arrange these Lego blocks, the authors found a specific arrangement called a Tensor Train (TT).

The Analogy: Imagine a standard Lego sculpture is a messy pile. A Tensor Train is like an assembly line. The blocks are connected in a single, straight line, one after another.
The Superpower: Because they are in a straight line, you can process them incredibly fast.
- Sequential: You can do it one by one.
- Parallel (The Big Win): Even better, because the line is so structured, you can split the work among thousands of computers working at the exact same time.
- The Result: What used to take years can now be done in a fraction of a second. The paper proves this mathematically, showing that for these "Train" models, the explanation problem belongs to a special "fast lane" of computer science (called NC).

4. The "Aha!" Moment: Width vs. Depth

One of the most surprising discoveries in the paper concerns Binarized Neural Networks (AI models that only use 1s and -1s, like a light switch).

The Old Belief: People thought the depth (how many layers deep the network is) was the main reason explanations were hard. They thought if you just made the network shallow (fewer layers), it would be easy to explain.
The New Insight: The paper proves that depth doesn't matter much. You can have a very deep network, and if it's narrow (not many neurons side-by-side), it's actually easy to explain!
The Bottleneck: The real enemy is Width. If the network is too wide (too many neurons working side-by-side), the math explodes.
The Metaphor: Imagine a hallway.
- Depth is how long the hallway is. Walking down a long hallway is fine.
- Width is how many people are trying to walk through the door at the same time. If the hallway is narrow, only a few people can pass, and it's easy to manage. If the hallway is wide and packed with thousands of people, it's a chaotic mess (computationally hard).
- Conclusion: To make AI explainable, we don't necessarily need to make the models shallower; we just need to keep them narrow and sparse (few connections).

5. Why This Matters for You

Trust: This allows us to get exact explanations for complex AI models, not just guesses. We can finally say, "We are 100% sure this feature caused the decision," rather than "We think it probably did."
Speed: Because the math can be done in parallel (using many processors at once), we can explain decisions in real-time.
Design: It gives AI engineers a new rule of thumb: If you want your AI to be explainable, design it to be "narrow" rather than just "shallow."

Summary

The paper is like finding a secret shortcut through a maze.

The Maze: Explaining complex AI is usually a dead end (too hard).
The Map: They found that if you draw the AI as a "Tensor Train" (a straight line of Lego blocks), the maze disappears.
The Vehicle: You can drive through this new path at lightning speed using parallel computers.
The Lesson: The width of the AI matters more than its depth. Keep it narrow, and you can understand it perfectly.

This work bridges the gap between "powerful but unexplainable" AI and "understandable but weak" AI, giving us the best of both worlds.

1. Problem Statement

Shapley Additive Explanations (SHAP) are a gold standard for explaining Machine Learning (ML) model predictions. However, computing exact SHAP values is generally NP-hard for expressive black-box models like neural networks. While exact algorithms exist for simpler models (e.g., decision trees via TreeSHAP), they do not scale to complex architectures. Existing solutions often rely on sampling heuristics (e.g., KernelSHAP) which introduce approximation errors.

The paper addresses the following core questions:

Can we compute provably exact SHAP explanations for a broader class of expressive models?
Under what structural conditions can SHAP computation be efficiently parallelized (achieving poly-logarithmic time)?
What are the specific computational bottlenecks (depth vs. width vs. sparsity) for neural networks?

2. Methodology

The authors introduce a framework that bridges Explainable AI (XAI) and Tensor Networks (TNs), a mathematical formalism originally from quantum physics used for model compression and abstraction.

A. Tensorized SHAP Formulation

The authors reformulate the SHAP definition into a tensorized representation.

Marginal SHAP Tensor ( $T^{(M,P)}$ ): They define a tensor that encapsulates the SHAP values for all features and inputs.
Decomposition: They prove that this tensor can be constructed by contracting two components:
1. A Modified Weighted Coalitional Tensor ( $\tilde{W}$ ), representing the combinatorial weights of feature subsets.
2. A Marginal Value Tensor ( $V^{(M,P)}$ ), representing the expected model output over subsets of features.
Algorithm: The exact SHAP value is computed by contracting these tensors with the input instance.

B. The Tensor Train (TT) Restriction

While general Tensor Networks are computationally hard, the authors focus on Tensor Trains (TTs), a specific 1D topology of TNs.

They demonstrate that if both the model ( $M$ ) and the data distribution ( $P$ ) are represented as TTs, the resulting Marginal SHAP Tensor is also a TT.
Parallelization: Tensor contraction for TTs is a well-studied problem solvable via parallel scan algorithms. The authors leverage this to show that SHAP computation for TTs falls into the complexity class NC (specifically $NC^2$ ), meaning it can be solved in poly-logarithmic time using a polynomial number of parallel processors.

C. Reductions and Parameterized Complexity

Reductions: The authors show that many popular ML models (Decision Trees, Tree Ensembles, Linear RNNs, Linear Models) can be reduced to equivalent Tensor Trains.
Binarized Neural Networks (BNNs): They analyze BNNs using Parameterized Complexity. They convert BNNs into TTs by representing neurons as Layered Deterministic Finite Automata (LDFAs) and using "copy tensors" to simulate the network logic. This allows them to analyze how specific structural parameters (width, depth, sparsity) affect tractability.

3. Key Contributions

General Framework for Exact SHAP in TNs:
- Introduced the first algorithm to compute provably exact SHAP values for general Tensor Networks with arbitrary structures.
- Proved that for general TNs, the problem is #P-Hard (intractable).
Tractability and Parallelism for Tensor Trains (TTs):
- Proved that for TTs, SHAP computation is not only in P (polynomial time) but in NC (specifically $NC^2$ ).
- This implies SHAP for TTs can be computed in poly-logarithmic time ( $O(\log^k n)$ ) using parallel hardware, a significant improvement over sequential polynomial time.
Tightened Complexity Bounds for Standard Models:
- By reducing Decision Trees, Tree Ensembles, Linear Models, and Linear RNNs to TTs, the authors established that SHAP for these models is also in NC.
- This allows for massive parallelization of exact SHAP for these models and supports more complex feature dependency distributions (beyond independence) during computation.
Fine-Grained Analysis of Neural Networks (BNNs):
- Depth is not the bottleneck: Even with fixed (constant) depth, computing SHAP for BNNs remains NP-Hard.
- Width is the bottleneck: If the network width is fixed, the problem moves to XP (slice-wise polynomial), becoming tractable.
- Width + Sparsity = FPT: If both width and sparsity (measured by reified cardinality) are fixed, the problem becomes FPT (Fixed-Parameter Tractable). This means SHAP can be computed efficiently even for arbitrarily large networks, provided they are narrow and sparse.

4. Key Results

Model Class	Complexity Class	Parallelizability	Key Insight
General TNs	#P-Hard	No	Intractable without structural constraints.
Tensor Trains (TTs)	NC ( $NC^2$ )	Yes (Poly-log time)	Exact SHAP is efficiently parallelizable.
Decision Trees / Ensembles	NC ( $NC^2$ )	Yes	Tightened bounds; enables parallel exact SHAP.
Linear RNNs / Models	NC ( $NC^2$ )	Yes	Extends parallel tractability to sequential models.
BNNs (Fixed Depth)	PARA-NP-Hard	No	Depth reduction does not solve intractability.
BNNs (Fixed Width)	XP	Limited	Width is a primary bottleneck.
BNNs (Fixed Width + Sparsity)	FPT	Yes	Efficiently tractable for narrow, sparse networks.

5. Significance and Impact

Bridging Expressivity and Tractability: The work closes a significant gap in XAI theory. It identifies a model family (TTs) that is significantly more expressive than trees (capable of approximating complex functions) yet admits exact, parallelizable SHAP computation.
Hardware Efficiency: By placing SHAP computation in the NC class, the paper provides a theoretical foundation for utilizing modern parallel hardware (GPUs, TPUs) to generate exact explanations for complex models, moving beyond slow sampling approximations.
Redefining Neural Network Tractability: The analysis of BNNs shifts the focus from "depth" (often cited as the source of complexity) to width and sparsity. This suggests that designing "narrow and sparse" neural networks could be a viable strategy for building inherently explainable AI systems.
Distribution Flexibility: The TT framework allows computing SHAP under Markovian or Hidden Markov distributions, capturing complex feature dependencies that current TreeSHAP implementations (which often assume independence) cannot handle.

In conclusion, this paper establishes that by viewing ML models through the lens of Tensor Networks, specifically Tensor Trains, we can achieve provably exact, highly parallelizable, and efficient SHAP explanations for a broad class of models, fundamentally changing our understanding of the computational limits of model interpretability.