SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
Authors: Reda Marzouk
Shahaf Bassan
Guy Katz
Venue: NeurIPS 2025 poster ()
Keywords: Tensor networks
Tensor trains
explainability
explainable AI
XAI
SHAP
Shapley values
interpretability
game theory
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: A complexity-theoretic analysis of exact, tractable SHAP explanations for Tensor Networks and their implications for other ML models

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.

SHAP Meets Tensor Networks:
Provably Tractable Explanations with Parallelism
Reda Marzouk"
LIRMM, UMR 5506, University of Montpellier, CNRS
mohamed waw.ourkuuuuttttteeeee.
Shahaf *
Guy Katz
The Hebrew University of Jeursalem shahaf. bassan@mail wuwji.a.. ac.
The Hebrew University of Jeursalem g katz@mail. hujinaiiiiijii.... auji.ac ac, il
Abstract
Although Shapley additive explanations (SHAP) can 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, 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, introduce general framework for computing provably exact SHAP explanations for general TNs with arbitrary structures. Interestingly, Tensor Train (TT) structure, SHAP
we show that, when TNs are restricted computation can be performed in woly-logarithmic time using parallel computa- tion. Thanks the expressiveness power of TTs. this complexity result can be generalized to many other popular ML models such as decision trees, tree ensem- bles, linear models, and linear RNNs, therefore tightening previously reported complexity results for these families of models. Finally, by leveraging reductions of binarized neural networks Tensor Network representations, we demonstrate that SHAP computation can become efficiently tractable when the network's '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.
Introduction
Shapley additive explanations (SHAP) (75 represent widely adopted method for obtaining post- hoc explanations for decisions made by ML models. However, one of its main limitations lies in its computational intractability [22] 106 82). While some frameworks mitigate this intractabil- ity using sampling heuristics or approximations, such KerneISHAP (75 42 FastSHAP [63].
32 or leverage score sam- pling [8). others focus on exact SHAP computations, by leveraging structural properties of certain model families to derive polynomial-time algorithms, such as the popular TreeSHAP (76 algorithm,
DeepSHAP [37] Monte Carlo-based methods [31 116
85
50
51
and its variants 114
86).
However, exact SHAP frameworks are confined to relatively simple models, such as tree-based models. For more expressive models like neural networks, where explanations are often most critical,
Equual Contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

NP- Fr-HHrdness results have unfortunately been shown to hold [066 82] In this work, we conduct complexit-ttheorete analysis of the problem of computing exact SHAP explanations for the class of Tensor Networks (TNs), a broader and more expressive class of models compared to previously studied models such as tree-based models or linear models.
Tensor Networks. Originally introduced in the field of Quantum physics [24]. TNs have gradually
gamnered attention of the ML community where they were employed model various ML tasks, ranging from classification and regression tasks [89] TOT 98 34
36 53 to probabilistic modeling [S]]
93 102
96 52 90], dimensionality reduction 777 and model compression [54]. From the perspective
of explainable AI, the study of TNs is interesting in two ways. First, TNs offer powerful modeling framework with function approximation capabilities comparable to certain families of neural networks [4]4 Second, the structured physics- insspire architecture of TNs enables the derivation of efficient, theoretically grounded solutions of XAI-related problems 73 95 These two properties make TNs an interesting family of models that enjoy two arguably sought-after desiderata of ML models in the field of explainability: (i) high expressiveness; and (ii) enhanced transparency
99
Contributions. In this work, we provide a computational complexity-theorees analysis of the problem of SHAP computation for the family of TNs. Following the line of work in (76 on tractable SHAP computation for simpler models, our main technical contributions are as follows:
6
15
66 81
58
1. SHAP for general TNs. We introduce a framework for computing provably exact SHAP explanations for general TNs with arbitrary structure, offering the first exact algorithm for generating SHAP values in this model class.
2. SHAP for Tensor Trains (TTs). We provide a deeper computational study of the SHAP problem for the particular class of Tensor Trains (TTs), a popular subfamily of TNs that ex- hibits better tractability properties than general TNs. Interestingly, we show that computing SHAP for the family of TTs is not only computable in polynomial-time but also belongs to the complexity class NC, i.c. it can be computed in poly-logarithmic time using parallel computation. This complexity result bridges a significant expressivity gap by establishing the tractability of SHAP computation for a model family that is significantly more expressive than those previously known to admit exact SHAP algorithms, while also demonstrating its efficient parallelizability.
3. From TTs to improved complexity bounds for SHAP across additional ML models. Via reduction to TTs, we show that the NC complexity result can be extended to the problem of SHAP computation for a wide range of additional popular ML models, including tree ensembles, decision trees, linear RNNs, and linear models, across various distributions, thus tightening previously known complexity results. This advancement benefits SHAP computa- tion for these models in two key ways: (i) it enables substantially more efficient computation through poly-togarithmie parallelism, and (ii) it broadens the class of distributions used to compute SHAP's expected value, which captures more complex feature dependencies than those employed in current implementations.
4. From TT's to SHAP for Binarized Neural Networks (BNNs). Finally, through reductions from TTs, we reveal new complexity results for computing SHAP for BNNs via parame- terized complexity 48 46). a framework for assessing how structural parameters impact computational hardness. We find that while SHAP remains hard when depth is fixed, becomes polynomial- time computable when width is bounded - highlighting width as the main computational bottleneck. We then further strengthen this insight by proving that fixing both width and sparsity (via the reified cardinality) renders SHAP efficiently tractable, even for arbitrarily large networks. This opens the door to a new, relaxed class of neural networks that permit efficient SHAP computation.
Beyond these core complexity results, which form the central focus of our work, our contributions also shed light into two novel complexity-therred aspects of SHAP computation that, to the best of our knowledge, have not been explored in prior literature:
When is computing SHAP efficiently parallelizable? To the best of our knowledge, this is the first work to provide a complexity-theorete analysis of the computational parallelizability of SHAP computation. Our work provides a tighter complexity bound for many previously known tractable SHAP configurations by investigating conditions under which SHAP computation can be parallelized to achieve polylogarithmie-tng -imetthiiiiiieeeeeeeeee complexity. Notably, we show that this is achievable for several
2

---

classical ML models, including decision trees, tree ensembles, linear RNNs, and linear models paving the way for a line of future research in this direction.
What is the computational bottleneck of SHAP computation for neural networks? To the best of knowledge, while prior work has established that computing SHAP for general neural networks is computationally hard [106 82), our work presents the first fine-grained analysis of how different structural parameters influence this complexity. Focusing on binarized neural networks, we show that SHAP becomes efficiently computable when both the network's 's width and sparsity are fixed, whereas it remains hard even with constant depth. We believe this insight paves the way for further exploration of neural network relaxations that enable efficient SHAP computation and invites broader theoretical investigation into other structural parameters and architectures where SHAP may be tractable.
Due to space constraints, we include only brief outlines of some proofs in the main text, with complete proofs provided in the appendix.
Preliminaries
Notation. For integers (i, with S n, let ež denote the one-hot vector of length n with in the i-th position and O elsewhere. The vector 1, E R denotes the vector equal to 1 everywhere. For integers m and n, we use the notation m 6bn def
[m]] ... x [m]] where [m]] 21.2..... m].
times
Complexity classes. In this work, will assume familiarity with standard complexity classes such as polynomial time (P), and nondeterministic polynomial time (NP and coNP). We further analyze the complexity class #P, which captures the number of accepting paths of a nondeterministic polynomial- time Turing machine, and is generally regarded as significantly "harder" than NP (7]. Moreover, we analyze the complexity class NC, which includes problems solvable in poty-logarithmic time using a polynomial number of parallel processors, typically on a Parallel Random Access Machine (PRAM) [39] (see the appendix for full formalization). Intuitively, problem is in NC if it can be efficiently solved in parallel. While NC S P is known, it is widely believed that NC ç P [7]. The class NC is further divided into subclasses NC for some integer k. The parameter k designates the logarithmic order of circuits that solve computational problems in NC For example, NC! contains problems solvable with circuits of logarithmic depth, while NC² allows circuits of quadratic logarithmic depth, capturing slightly more complex parallel computations.
Finally, work also draws concepts from parameterized complexity theory 46 48). In this framework, problems are evaluated based on two inputs: the main input size n and an additional measure known as the parameter k, with the aim of confining the combinatorial explosion to k rather than n. We focus on the three most commonly studied parameterized complexity classes: (i) FPT (Fixed-Pare Parammeer Tractable), comprising problems solvable time g(k) o(1) for some computable function g. implying tractability when k is small; (ii) XP (slice-wise Polynomial), where problems can be solved in time (k)) with polynomial degree that may grow with k. thus offering weaker tractability guarantees than FPT; and (iii) para-NP, which captures problems with the highest sensitivity to k. where problem is para-NP- -a-rrd if it remains NP-hard even when k is fixed to constant. It is widely believed that FPT Ç XP Ç para-NP (46).
Shapley values. Let Pin, Dout 2 1 be two integers. Fix a discrete input space D = [Ni] x [N2] x
X [N....) model M IID Ruoat, and a probability distribution P over D.. For input instance x (I1, T2 ...., Fran) E ID, the SHAP attribution vector assigned to the feature E [ntn] is defined
as:
di (M, ScImEnlr0)
Σ W(S)- (VM(E, (Kata. E R gout
(I)
where W(S) del [S]!(nin 15|-
We assume the common marginal (or interventional) value function:
axp
For j E [Nou]. the j-th component of Φ x, P) represents the attribution of feature i to the j-th output of the model on input x.
Var(x, P) : E.-r M (xs, x's)
62 103
3

---

3 Tensors, Tensor Networks and Binarized Neural Networks
3.1 Tensors
tensor is a cilliiddmensional array that generalizes vectors and matrices to higher dimensions, referred to indices. The dimensionality of tensor, i.c. the number of its indices, defines its order. Elements of a tensor E IR Xd. are denoted T.....d. For j [n], the slice 1
a vector in Rdd whose k-th entry is equal to T 1.,5, 1.5.5 for E [dy]. A key operation over tensors is the contraction operation, which generalizes matrix multiplication to high-order tensors. Formally, given two tensors T()) Id:x...xd and T(2) Id x... and two indices (i,j) [n] x [m], such that d; = d The contraction operation between T() and T(2) over their respective indices and produces another tensor, denoted T x(x))) T(2), over pdix..... x.... xd.+ xd., xd, x...xx, xd, x xd..xdm such that:
(TU) (is) T1z)
a1 1592) 1 bi 1: Io
The contraction operation over single pair of shared indices as defined above can be generalized to sets of shared indices in a natural fashion: For a set S C [n] x [m]] the multi-leg contraction operation between (1) and ( over S, denoted T x T applies leg contraction to all pairs of indices in S. Note that this operation commutative the result of the operation doesn't 't depend on the contraction order.
bood (c) Tensor Train (TT)
(a) Tensor of order 4 (one node with four free indices)
(b) General Tensor Network (TN)
Figure 1: Illustrations of (1) A tensor of order 4, (2) A general TN comprising 4 tensors of order and free indices, and (3) A tensor train (TT).
3.2 Tensor Networks (TNs)
TNs provide structured representation of high-order tensors by decomposing them into intercon- nected collections of lower-order tensors bound by the contraction operation. TNs can be modeled as a graph in which each node corresponds to a tensor and each edge corresponds an index. Edges that are incident to only one node represent free indices of the overall tensor, while edges shared between two nodes represent contracted indices (see Figure (5b). The tensor encoded by the network is obtained by carrying out all contractions prescribed by the graph structure. This representation of high-order tensors can be advantageous because the storage requirements and computational cost scale with the ranks of the intermediate tensors and the network topology, rather than with the full dimensionalityy of the original tensor.
Tensor Trains (T's). General TNs with arbitrary topologies can be computationally challenging to handle [TTO) 100). TTs form subclass of TNs with one-dimensional topology that exhibits better tractability properties (92). A TT decomposes a high-order tensor into a linear chain of third-order "ccores" (see Figure 5ch. Formally, a TT T is a TN parametrized as [T),.... T."), where each core ( E IR4 xx The TT T corresponds to a tensor in Rdox N2 x... N. xd. obtained by contraction.
T T()() x(3.1) T ((31)) ... ((3.1) (a)
By convention, when da (resp. d.,) is equal to 1, the tensor core (1) (resp. T(e)) is matrix (i.e., Tensor of order 2).

---

3.3 Binarized Neural Networks (BNNs)
Binarized Neural Nenwork (BNN) neural network which both the weights and activations are constrained to binary values, typically {-1,+1}, In BNN, each layer performs sequence of operations: (i) linear transformation, (ii) batch normalization, and (iii) binarization. Formally, for an input vector {-1,+1}", the output y [-1,+1}* of layer is computed as follows [11:
p + B, y = sign(z'),
z = x z' 7
0
W E (-1,+1)mxy, b E R and 7. 3, ,. E R are the batch normalization parameters. The sign function is applied element-wise, mapping positive inputs to +1 and con-positive inputs to -1.
Reified Cardinality Representation of BNNs. In Section 6 we analyze how network sparsity affects the complexity of computing SHAP for BNNs, using the reified cardinality parameter from [64]. A reified cardinality constraint is a binary condition of the form (Zi=1 Ki 2 Rt). where I; are Boolean variables and R is the reified cardinality parameter. In BNNs, each neuron is encoded with such a constraint: for binary inputs Ij and weights Wij E f1,1, +1), define lij = Ii if way = +1, and
ki = - otherwise. The output yi is then: < 45 2 Ra) where R2 is derived from the neuron's 's bias and normalization. Jía and Rinard 664 showed that all BNNs can be expressed this way, and that constraining R; during training improves formal verification efficiency.
4 Provably Exact SHAP Explanations for TNs: A General Framework
In this section, we introduce a general framework for computing provably exact SHAP explanations for TNs with arbitrary structures, which provides the backbone of more tractable SHAP computational solutions. We begin by formalizing the problem and transitioning from the classic SHAP formulation an equivalent tensorized representation that facilitates our proofs.
tensorized representation of Shapley values. We adopt an equivalent tensorized form of the
SHAP formula Equation (
by defining the Marginal SHAP Tensor (M,.P) E RX XBour as:
(a, i) E D X [na]]:
(MPP) der @T xx TT) 2.
(TM,,IT'
(2)
The Marginal SHAP Tensor summarizes the full SHAP information of the model M, and will play a crucial role in the technical development of this paper. Given V(M.P), The SHAP Matrix of the input (#1, Inaa D is obtained using the straightforward contraction operation:
( x,, TP) (MMPP) xs
c o .... exnen
Nag
(3)
where S del kk; : E [Tem + 11].
SHAP Computation (Problem Statement).
Given two integers Nin, Nout 2 1, a finite domain D. a TN model TM E R.N..... Xhout mapping D to RBout, a TN TPP E N implementing a probability distribution over D. and an instance x D. The objective to construct the SHAP Matrix &(T M xx, TP) E Ru Xnout
where: ((TM 22, TP).
del (T xx TP) (Equation (.).
The complexity is measured in terms of the input and output dimensions Min: Routs the volume of the input space max N;, and the total number of parameters of TM and
:E(n:.]
The first step toward the derivation of exact SHAP explanations for general TNs builds on a reformu- lation of the Marginal SHAP Tensor (Equation (2) highlighted in the following proposition:
Proposition 1. Define the modified Weighted Coalitional tensor W E R X2 such that
V(i, $1,...,, Sm..) E [nan] [2]m it holds that Wis (s 1 I if 8; 1, and
W W ((s In..) otherwise. Moreover, define the marginal value tensor (MMP)
5

---

Algorithm The construction of the Marginal SHAP Tensor
Input: Two TNs TM and T
Output:
The Marginal SHAP Tensor (MM,P)
1: Construct the modified Weighted Coalitional Tensor W (Lemma))
2:
Construct the Marginal Value Tensor ((M,P) (Lemma
3:
return W xg ((M,P) (Equation (12)
B Xnoue, such that V(z, 8) E DD X (2)en it holds that V.M.P) de Var(z, 3; P). Then we have
that:
T(M.P) = W x (M.P)
where S der { 1, nin + 1): & [minn]
Proposition expresses the Marginal SHAP Tensor (M, as contraction of two tensors: the modified Weighted Coalitional Tensor and the Marginal Value Tensor. This leads to natural algorithm construct V(M,P); First construct W and ((M,P), then contract them in Equation (12) (Algorithm D. Figure 2a illustrates the resulting TN of this process.
To complete the picture, we need to show how to construct both tensors V (Step 1) and ((MP)) (Step 2). We split the remainder of this section into two segments, each of which is dedicated to outlining their structure and the running time of their construction.
Step 1: Constructing the modified Weighted Coalitional Tensor. The Tensor W simulates the computation of weights associated with each subset of the input features in the SHAP formulation (Equation ① ). A key observation consists of noting that this tensor admits an efficient representation as (sparse) TT constructible in O(1) time using parallel processors:
Lemma 1. The modified Weighted Coalitional Tensor W. admits TT representation: [g .g..,... ,..., "...,g((in)]] g(md)) where g()) R x2xn?,, g( x2xx? for any [2. nin. 1], and
g(maa E RRT.,x2 x2 Moreover, this TT representation is constructible in O(log(n.n) time using O (m))) parallel processors.
Step 2: Constructing the Marginal Value Tensor. The goal of the second step is to construct the Marginal Value Tensor ((M.P) from the TNs TM and TP. The following lemma shows how this Tensor can be constructed by means of suitable TN contractions:
Lemma 2. Let TM and TP be TNs implementing the model M and the probability distribution P. respectively. Then, the marginal value tensor (MM,,P) can be computed as:
(M o...o (M....((mnn)) (mmn)) Xs, T Xsa TP
where S₁ and S2 are instantiated such that for all k E {1,2) it holds that: Ss def [na,]], and for any [n,,], the (sparse) tensor (11) Mx2xN is constructible in O(1) time using O(N?) parallel processors.
()
The collection tensors (M (ig(m..) can be interpreted as routers simulating the interventional mechanism in the Marginal SHAP formulation: Depending on the value assigned its third index (which is binary), it routes the feature value of either its value in the input instance to explain x or from one drawn from the data generating distribution T feed the model's input.
5 Provably Exact and Tractable SHAP for TTs, and Other MIL Models
In this section, we show that SHAP values can be computed in polynomial time for the specific case of Tensor Train (TT) models. Interestingly, we prove that the problem also lies in NC, meaning can also be solved in polylogarithmic time using parallel computation. This result is established in Subsection 5.T Then, in Subsection 5.2) we demonstrate how this finding can leveraged - via reduction - to tighten complexity bounds for several other popular ML models.

---

T M
Thosi
7
7
7
Rout
Mla
g(2)
g
ga
g
g19)
M
M
2g (5
Zy
M
M
M
27
21g
2gg
TP
p01
pta
p
(a) General TNs
(b) Tensor Trains (TT)
Figure 2: The construction of the (M, TN for model of 3 features. The general case: Both T and T are general TNs with arbitrary structures; The TT case: Both TM and T are TTs.
5.1 Provably exact and tractable SHAP explanations for TTs
The computational complexity of computing SHAP for general TNs, as discussed in the previous section, naturally depends on the structural properties of the TNs T and T implementing the model to explain and the data generating distribution, respectively. We begin by presenting general worst-case negative result, showing that the problem is #P--Hard when no structural constraints are imposed on the tensor networks.
Proposition 2. Computing Marginal SHAP values for general TNs is #P-Hard.
Proof Sketch. The result is obtained by reduction from the #CNF-SAT problem (The problem of counting the number of satisfying assignments of a CNF boolean formula Essentially, it leverages two facts: (i) the model counting problem is polynomially reducible to the SHAP problem [66]. (ii) A polynomial-tine -ime algorithm to construct an equivalent TN to given CNF boolean formula. The full proof can be found in Appendix D
Interestingly, the problem however, becomes tractable when we restrict both TM and T to lie within the class of Tensor Trains (TT's. To establish this result, begin with key observation: the marginal SHAP tensor (M,P) itself admits representation
TT. Formally:
Theorem Let TM
[I(1] "...,.... I(( 'I and T [p(1] ..... p(mun]] be TTs corresponding to the model to interpret and the data- talla-generating distribution, respectively. Then, the Marginal SHAP Tensor T (M, can be represented by TT parametrized as:
[M x (4.2, x(3.2) P(1) x (222) ""."",,,,,....i (( x (1.2) (4.2))((mna) (ma)) X2,,2) p((in) ((2,2) (1an)
(5)
where the collection of Tensors ha((ns.) and (M and Lemma 2 respectively.
(
implicitly defined in Lemma !
Proof Sketch. The result is obtained by plugging the TT corresponding to V (Lemma 1 and (M,))
(Lemma 2 into Equation [2] and performing suitable arrangement of contraction ordering of the resulting TN. Figure 2b provides a visual description of how the TT structure of the SHAP Value Tensor (MMP) emerges when both TM and TP are TTs.
Efficient parallel computation of SHAP for TTs. Theorem showss [ssows values for TTs reduces to contracting the Marginal SHAP Tensor - TT with rank-1 tensor representing the input (Equation 3) TT contraction is well-studied problem with efficient parallel algorithms that run poly-logarithmic time [33 80), typically using a parallel scan over adjacent tensors. Leveraging this and the fact that matrix multiplication is in NC (28). following:
that computing exact SHAP
prove the
Proposition Computing Marginal SHAP for the family of TT's lies in NC?.
Proof Sketch. A parallel procedure to solve this problem runs as follows: First, compute in parallel tensor cores in Equation (20). Given that Matrix Multiplication is in NC1, this operation is also in
NC!. Second, following [80), parallel scan strategy will be applied to contract the resulting TT
7

---

41
start
Q
G(2)
F2
start -+0'0
(a) Decision tree
(b) Lattice of finite-state machines
(c) Tensor Train representation
Figure Conversion of decision into an equivalent Tensor Train (TT). (a) simple decision tree with two binary input features, (b) its equivalent lattice of finite-state automata, where each automaton encodes a distinct path leading to leaf labeled 1, and (c) the corresponding TT representation with three free legs: 31, z2.for inputs and y for the output. The tensor cores G |R and
G 22x2x2 have ranks equal to the number of automata in the lattice, i.e rank(G()) 2 for ? {1,2}
using a logarithmic depth of matrix multiplication operations. This second operation is performed by a circuit whose depth scales as (log (na))) yielding the result (see Appendix D
5.2 Tightening the complexity results of SHAP computations in many other ML models
Thanks to the expressive power of Tensor Trains (TTs), many widely used ML models such tree ensembles, decision trees, linear models, and linear RNNs - can be reduced to TTs. This reduction allows us to significantly tighten the known complexity bounds for these models. This improvement crucial for two main reasons:
(i) It shows that computing SHAP values for all these models is not only polynomial-tnn time solvable but also the complexity class NC, enabling efficient parallel computation.
(ii) It demonstrates that Marginal SHAP can be computed under TT-based distributions class distributions more expressive than those previously considered, englobing independent (6]
empirical [06), Markovian 81 Hidden Markov distributions 82 and Born Machines (22
formalize this in the following theorem:
Theorem 2. Computing Marginal SHAP values for decision trees, tree ensembles, linear models, and linear RNNs under the distribution class of TT's lies NC?.
The proof of Theorem 2 can be found in Appendix E It proceeds by constructing NC-reduction procedures that transform each of these ML models (L.e. Decision Trees, Tree Ensembles, Linear Models and Linear RNNs) into equivalent TTs.
For illustrative purposes, we show in figure 3 an example of such construction for a simple binary decision tree converted into an equivalent TT representation. The construction proceeds through an intermediate automata- basoa representation, where the DT is transformed into lattice of finite state automata which admits natural and compact parametrization in TT format. This construction can be implemented by means of uniform family of boolean circuits with polynomial size and poly-logarithmic depth (see Appendix for the formal details of this construction).
We believe that this result could be of interest to practitioners willing to scale the computation of SHAP explanations to large dimensions by leveraging parallelization under data generating distributions that capture sophisticated dependencies between input features.
6 A Fine-Grained Analysis of SHAP Computation for BNNs
In this section, we reveal an additional intriguing connection between our complexity results for TNs and Binarized Neural Networks (BNNs). This connection enables what is, to the best of our knowledge, the first fane--rriiinn analysis of how particular structural parameters of a neural network affect the complexity of computing SHAP values.
We begin by noting that for non-quantized neural network, even the seemingly simple case of single sigmoid neuron with binary inputs has been shown to be intractable for SHAP computation [06]]]] 82

---

Rai =1
41
Ru
222
N
N2
3
3/3
Au
16
Ru =
23
(a) Structure of BNN M with layers (R = 3)
(b) 2-dim TN representations of M's Layers
2
X
No
8
M
X
26
3
(c) Contraction of Layer 3 with Layer
(d) Contraction of Layer with Layer 1
Figure 4: In Figure 4a Rig denotes the reified cardinality parameters of the neurons. In Figures 4b
4c
and 4d
the numbers above the edges indicate tensor index dimensionality.
In contrast, we show that by quantizing the weights and transitioning to a BNN, tractability can be achieved sereed-tthe - though this tractability critically depends on the network's different structural parameters.
We carry out this analysis using the framework of parameterized complexity [48] 46), a standard approach in complexity theory for understanding how various structural parameters influence com- putational hardness. Specifically, we focus on three key parameters: (i) the network's 's width, (ii) its depth, and (iii) its sparsity. The main result of this analysis is captured in the following theorem:
Theorem 3. Let P be either the class of empirical distributions, independent distributions, or the class of TTs. We have that:
1. Bounded Depth: The problem of computing SHAP for BNNs under any distribution class P is PARA-NP-HARD with respect to the neiwork's depth parameter.
2. Bounded Width: The problem of computing SHAP for BNNs under any distribution class P is in XP with respect to the width parameter.
3. Bounded Width and Sparsity. The problem of computing SHAP for BNNs under any distribution class P is in FPT with respect to the width and reified cardinality parameters.
Key takeaways from these fine-grained results. Theorem Scaptures several notable insights into the complexity of computing exact SHAP values for BNNs:
1. Even shallow networks are hard. Computing SHAP values for BNNs remains NP-Hard even when the network depth is fixed a constant. In fact, intractability arises already with a single hidden layer, underscoring that reducing the network's 's depth does not alleviate the computational hardness of SHAP.
2. Narrow networks make it easier. However, when the width of the neural network is fixed to a constant, computing SHAP for BNN becomes polynomial (as falls within the class XP), highlighting width potential relaxation point for improving tractability.
3. Narrow and sparse networks are efficient. Finally, by fixing both the network's width and sparsity, we obtain an even stronger result: fixed-pane peremparrmeter tractability (FPT). This implies that computing SHAP is efficiently tractable even for arbitrarily large networks so long as these parameters remain small, regardless of the network's 's depth, input dimensionality, number of non-linear activations.
This shows that width drives the shift from intractability to tractability in SHAP for BNNs, and that adding sparsity bounds can fully tame complexity even in high-dimensional settings.
Proof Sketch (Theorem The first part follows from a direct reduction from ASA any CNF formula can be encoded by depth-2 2 BNN, and computing SHAP for CNF formulas is HarHard [106).

---

The second and third parts rely on more involved construction: converting a BNN into an equivalent Tensor Train (TT), inspired by [72.. Each BNN layer is represented as 2D tensor network, and these are contracted backwards into a TT. Figure an equivalent TT runs DR poly(D, Nln, max; N:)) time, where W, D, and R are the width, depth, and reified cardinality of the BNN. The last two items of Theorem follows immediately from this runtime complexity by definition of XP and FPT (see section 2). and the fact that SHAP for TTs is in NC (Proposition
this process. The compilation of BNN into
7 Limitations and Future Work
While our work represents a notable step toward understanding the computational landscape of SHAP, it remains focused on specific settings, and many other settings could naturally be explored. Future research could extend our analysis to additional model classes, such as Tree Tensor Networks [35. SHAP variants [103], and relaxations approximations that enhance tractability for more expressive models than those studied here. We also acknowledge existing critiques of SHAP 770 our goal is not to defend its axiomatic foundations but analyze the complexity of a widely adopted ex explanation method. Exploring the complexity of obtaining alternative value function definitions (71). SHAP variants [2] or other attribution indices [T0 presents exciting directions for future work.
57
99 49 25];
Conclusion
In this work, we present the first provably exact algorithm for computing SHAP explanations for the class of Tensor Networks. Moreover, we prove that for the particular subclass of Tensor Trains, this computation can be carried out not only polynomial time but also in polylogarithmic time using parallel processors. This result closes significant expressivity gap in tractable SHAP computation by extending tractability to a significantly more expressive model family than previously known. Building on this expressivity, our approach also yields new insights into the complexity of computing SHAP for other popular MI. models including decision trees, linear models, linear RNNs, and tree ensembles - by enabling improved distribution modeling. Furthermore, these results offer, by reduction, a novel fove fine-grained analysis of the tractability barriers in computing SHAP for binarized neural networks, identifying width as central computational bottleneck. Together, we believe that these findings significantly advance our understanding of the computational landscape of SHAP, highlighting both inherent limitations and new opportunities, and hence paving the way for future research.
saallliiiaabiity-retttet complexity bounds and more expressive
Acknowledgments
This work was partially funded by the European Union (ERC, Verileel, 101112713). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This research was additionally supported by a grant from the Israeli Science Foundation (grant number 558/24).
References
[1] Omer Abramovich, Daniel Deutch, Nave Frost, Ahmet Kara, and Dan Olteanu. Banzhaf Values for Facts in Query Answering. In Proc. 2nd ACM on Management of Data (PACMMOD), pages 1-26, 2024.
[2] Federico Adolfi, Martina Vilas, and Todd Wareham. The Computational Complexity of Circuit Discovery for Inner Interpretability. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
[3] Borja Aizpurua, Samuel Palmer, and Román Orús. Tensor Networks for Explainable Machine Learning in Cybersecurity. Neurocomputing, 639:130211, 2025.
10

---

[4] Mazen Ali and Anthony Nouy. Approximation Theory of Tree Tensor Networks: Tensorized Multivariate Functions, 2024. Technical Report.
[5] Guy Amir, Shahaf Bassan, and Guy Katz. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation. In Proc. 27th European Conf. Artificial Intelligence (ECAI), pages 818-825, 825, 2024.
[6] Marcelo Arenas, Pablo Barcelo, Leopoldo Bertossi, and Mikael Monet. On the Complexity of SHAP-Score-Basee Explanations: Tractability via Knowledge Compilation and Non- Approximability Results. Journal of Machine Learning Research (JMLR), 24(63):1-58, 2023.
[7] Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
[8] Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, and Pierre Marquis. On Preferred Abductive Explanations for Decision Trees and Random Forests. In Proc. 31st Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 643-650, 2022.
[9] Gilles Audemard, Steve Bellart, Louenas Boumia, Frédéric Koriche, Jean-Maric Lagniez, and Pierre Marquis. Trading Complexity for Sparsity in Random Forest Explanations. In Proc. 36th AAAI Conf. on Artificial Intelligence, pages 5461-5469, 2022.
[10] P Barceló, R Cominetti, and M Morgado. When is the Computation of a Feature Attribution Method Tractable? 2025. Technical Report. /ttpps://arii..orrrrr wttp:/iwwwrrr/b//////aaaa abs///bs//2/00 02356
[11] Pablo Barceló, Mikaël Monet, Jorge Pérez, and Bernardo Subercaseaux. Model Interpretability Through the Lens of Computational Complexity. In Proc. 34th Conf. on Neural Information Processing Systems (NeurPPS), pages 15487-15498, 2020.
[12] Pablo Barceló, Alexander Kozachinskiy, Miguel Romero, Bernardo Subsercaseaux, and José Verschae. Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. In Proc. 3rd ACM on Management of Data, number 2, pages 1 1-26, 2025.
[13] Clark Barrett and Cesare Tinelli. Satisfiability Modulo Theories. Springer, 2018.
[14] Shahaf Bassan and Guy Katz. Towards Formal XAI: Formally Approximate Minimal Ex- planations of Neural Networks. In Proc. 29th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pages 187-207, 2023.
[15] Shahaf Bassan, Guy Amir, Davide Corsi, Idan Refaeli, and Guy Katz. Formally Explaining Neural Networks within Reactive Systems. In Proc. 23rd Conf. on Formal Methods in Computer-Aided Design (FMCAD), pages 1-13, 2023.
[16] Shahaf Bassan, Guy Amir, and Guy Katz. Local Global Interpretability: Computational Complexity Perspective. In Proc. 41st Int. Conf. on Machine Learning (ICML), 2024.
[17] Shahaf Bassan, Guy Amir, Meirav Zehavi, and Guy Katz. What makes an Ensemble (Un) Interpretable? Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
[18] Shahaf Bassan, Yizhak Yisrael Elboher, Tobias Ladner, Matthias Althoff, and Guy Katz. Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations. In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025.
[19] Shahaf Bassan, Ron Eliav, and Shlomit Gur. Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons. In Proc. 13th Int. Conf. Learning Representations (ICLR), 2025.
[20] Shahaf Bassan, Shlomit Gur. Sergey Zeltyn, Konstantinos Mavrogiorgos, Ron Eliav, and Dimosthenis Kyriazis. Self-Explaining Neural Networks for Business Process Monitoring. 2025. Technical Report, hhttps://arXin www.aaawwwv....ggbaa arg/abs/2503 18067
[21] Shahaf Bassan, Michal Moshkovitz, and Guy Katz. Additive Models Explained: A Computa- tional Complexity Approach. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025.
11

---

[22] Leopoldo Bertossi, Jordan Li, Maximilian Schleich, Dan Suciu, and Zografoula Vagena. Causality-based Explanation of Classification Outcomes. In Proc. of the 4th Int. Workshop on Data Management for End-to-End Machine Learning. 2020.
[23] Leopoldo Bertossi, Benny Kimelfeld, Ester Livshits, and Mikaël Monet. The Shapley Value in Database Management. ACM Sigmod Record, pages 6-17, 2023.
[24] Jacob Biamonte. Lectures on Quantum Tensor Networks. 2020. Technical Report. https
/ ///axivv.rrr/ wttp://wrrgaaab//1...00000
[25] Gagan Biradar, Yacine Izza, Elita Lobo, Vignesh Viswanathan, and Yair Zick. Axiomatic Aggregations of Abductive Explanations. In Proc. of the 38th AAAI Conf. on Artificial Intelligence, number 10, pages 11096-11106 2024.
[26] Guy Blanc, Jane Lange, and Li- Yang Tan. Provably Efficient, Succinct, and Precise Expla- nations. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pages 6129-6 0141, 2021.
[27] Sebastian Bordt and Ulrike von Luxburg. From Shapley values Generalized Additive Models and Back. In Proc. 26th Int. Conf. on Artificial Intelligence and Statisties (AISTATS), pages 709-745, PMLR, 2023.
[28] Allan Borodin, Joachim von zur Gathen, and John E. Hopcroft. Fast Parallel Matrix and GCD Computations. Information and Control, 52(3):241-256, 1982.
[29] Louenas Bounia and Frederic Koriche. Approximating Probabilistic Explanations via Super- modular Minimization. In Proc. 39th Conf. on Uncertainty in Artificial Intelligence (UAT), pages 216-225, 2023.
[30] Marco Calautti, Enrico Malizia, and Cristian Molinaro. On the Complexity of Global Necessary Reasons Explain Classification. 2025. Technical Report. https::/arxiw.org//ttt wtt.oorg//bbb///////o 06766
[31] Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial Calculation of the Shapley Value Based on Sampling. Computers & Operations Research, 3665):1726-1730, 2009.
[32] Siu Lun Chau, Robert Hu, Javier Gonzalez, and Dino Sejdinovic. RKHS-SHAE Shapley Values for Kernel Methods. Proc. of the 36th Conf. on Neural Information Processing Systems (NeurIPS), pages 13050-13063, 2022.
[33] Siu Lun Chau, Krikamol Muandet, and Dino Sejdinovic. Explaining the Uncertain: Stochastic Shapley Values for Gaussian Process Models. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), 2023.
[34] Cong Chen, Kim Batselier, and Ngai Wong. Chapter 8 Tensor Network Algorithms for Image Classification. In Yipeng Liu, editor, Tensors for Data Processing, pages 249-291. Academic Press, 2022.
[35] Hao Chen and Thomas Barthel. Machine learning with tree tensor networks, ep rank constraints, and tensor dropout. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12): 7825-7832, 2024.
doi: 10. 10.1109/PAAMM2224.333333
[36] Hao Chen and Thomas Barthel. Machine Learning With Tree Tensor Networks, CP Rank Constraints, and Tensor Dropout. IEEE Trans. Pattern Anal. Mach. Intell., 46(12):7825-732. December 2024. ISSN 0162-8828.
[37] Hugh Chen, Scott Lundberg, and Su-In Lee, Explaining Models by Propagating Shapley Values of Local Components. Explainable Al in Healthcare and Medicine: Building Culture of Transparency and Accountability, pages 261-270, 2021.
[38] Lu Chen, Siyu Lou, Keyan Zhang, Jin Huang, and Quanshi Zhang. HersanyiNet: Computing Accurate Shapley Values in a Single Forward Propagation. In Proc. 40th Int. Conf. on Machine Learning (ICML), pages 4804-4822 2023.
12

---

[39] Stephen A Cook. Towards Complexity Theory of Synchronous Parallel Computation. In Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook, pages 219-244, 2023.
[40] Martin C Cooper and João Marques-Silvas Tractability of Explaining Classifier Decisions. Artificial Intelligence, 2023.
[41] Matthieu Courbariaux, Itay Hubara, Daniel Soudry, Ran El- Vaniv,, and Yoshua Bengio. Bi- narized Neural Networks: Training Deep Neural Networks with Weights and Activations Constrained to +1 or -1. Technical Report. https://axxiv..rr/ abs/ 1etp./102..oo 02830
[42] Ian Covert and Su-In Lee. Improving KemeISHAP: Practical Shapley Value Estimation via Linear Regression. Proc. 24th Int. Conf. on Artificial Intelligence and Statislics (AISTATS), pages 1-9, 2021.
[43] Adnan Darwiche and Auguste Hirth. On the Reasons Behind Decisions. In Proc. 24th European Conf. on Artifical Intelligence (ECAI), pages 712-720, 2020.
[44] Adnan Darwiche and Chunxi Ji. On the Computation of Necessary and Sufficient Explanations. In Proc. 36th AAAI Conf. on Artificial Intelligence, pages 5582-5591, 2022.
[45] Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mikaël Monet. Computing the Shapley Value of Facts in Query Answering. In Proc. Int. Conf. Management of Data (MOD), pages 1570-1583, 2022.
[46] Rodney G Downey and Michael Ralph Fellows. Parameterized complexity. Springer Science & Business Media, 2012.
[47] James Enouen and Yan Liu. InstaSHAP: Interpretable Additive Models Explain Shapley Values Instantly. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
[48] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006.
[49] Daniel Fryer, Inga Strümke, and Hien Nguyen. Shapley Values for Feature Selection: The Good, the Bad, and the Axioms. leee Access, 9: 9:144352-14436 2021.
[50] Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Hammer. SHAP-IQ: Unified Approximation of Any-Order Shapley Interactions. In Proc. 37th Conf. on Neural Information Processing Systems (NeurIPS), pages 11515-11551, 2023.
[51] Fabian Fumagalli, Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Hammer. KemelSSAA--QQ Weighted Least Square Optimization for Shapley Interactions. In Proc. 41st Int. Conf. on Machine Learning (ICML), pages 14308-14342, 2024.
[52] Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Fisert, and Ignacio Cirac. Expressive Power Tensor--Nttorrk Factorizations for Probabilistic Modeling. In Proc. 33rd Conf. on Neural Information Processing Systems (NeurIPS), 2019.
[53] Carys Harvey, Richie Yeung, and Konstantinos Meichanetzidis. Sequence Processing with Quantum-Inspired Tensor Networks. Scientific Reports, 15(1):7155, 2025. doi: 10. 1038/ -41598--22-84295-22
[54) Kohei Hayashi, Taiki Yamaguchi, Yohei Sugawara, and Shin-ichi Maeda. Exploring Unex- plored Tensor Network Decompositions for Convolutional Neural Networks. In Proc. 33rd Conf. on Neural Information Processing Systems (NeurIPS), 2019.
[55] Tom Heskes. Evi Sijben, Ioan Gabriel Bucur, and Tom Claassen. Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models. In Proc. 34th Conf. Neural Information Processing Systems (NeurLPS), pages 4778-4789 2020.
[56] John F. Hoperoft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson, 3rd edition, 2006.
13

---

[57] Xuanxiang Huang and Joao Marques Silva. On the Failings of Shapley Values for Explainabil- ity. Int. Journal of Approximate Reasoning (IJAR). 171:109112, 2024.
[58] Xuanxiang Huang and Joao Marques-Silvae Updates on the Complexity of SHAP Scores, In Proc. of the 33rd Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 403 403-412, 2024.
[59] Alexey Ignatiev. Towards Trustable Explainable AI. In Proc. 29th Int. Joint Conf. on Artificial Intelligence (ICCAI), pages 5154-5158, 2020.
[60] Alexey Ignatiev, Nina Narodytska, and Joao Marques-Silva. Anduction-basel Explanations for Machine Learning Models. In Proc. 33rd AAAI Conf. on Artificial Intelligence, pages 1511-1519, 2019.
[61] Yacine Izza, Xuanxiang Huang, Antonio Morgado, Jordi Planes, Alexey Ignatiev, and Joao Marques-Silke Silla.. implementation. In Proc. 21st Ins. Conf. on Principles of Knowledge Representation and Reasoning (KR), pages 475-486, 2024.
Explanations: Theoretical Underpinnings & Efficient
[62] Dominik Janzing, Lenon Minorics, and Patrick Blöbaum. Feature Relevance Quantification in Explainable AI: A causal Problem. In Proc. 23rd Int. Conf. Artificial Intelligence and Statistics (AISTATS), pages 2907-2916 2020.
[63] Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lec, and Rajesh Ranganath. FastSHAP: Real-time Shapley Value Estimation. In Proc. 9th Int. Conf. on Learning Repre- sentations (ICLR), 2021.
[64] Kai Jia and Martin Rinard. Efficient Exact Verification of Binarized Neural Networks. In Proc. 34th Conf. on Neural Information Processing Systems (NeurIPS), pages 1782-1795, 2020.
[65] Helen Jin, Anton Xue, Weiqiu You, Surbhi Goel, and Eric Wong. Probabilistic Stability Guarantees for Feature Attributions. 2025. Technical Report. |tttps://arxvv..rgg/ /bs/
2504. 13787
[66] Ahmet Kara, Dan Olteanu, and Dan Suciu. From Shapley Value to Model Counting and Back. In Proc. 2nd ACM on Management of Data (PACMMOD), pages 1 1-23, 2024.
[67] Pratik Karmakar, Mikaël Monet, Pierre Senellart, and Stéphane Bressan. Expected Shapley- like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases. In Proc. 2nd ACM on Management of Data (PACMMOD), pages 1-26, 2024.
[68] Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel Kochenderfer. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In Proc. 29th Int. Conf. on Computer Aided Verification (CAV), pages 97-117, 2017.
[69] Sven Kruschel, Nico Hambauer, Sven Weinzierl, Mathias Kraus, Sandra Zilker, and Patrick Zschech. Challenging the iifffrmance-lnterrrraaalli Trade-Off: An Evaluation of Inter- pretable Machine Learning Models. Business & Information Systems Engineering, 2025.
[70] Elizabeth Kumar, Suresh Venkatasubramannian, Carlos Scheidegger, and Sorelle Friedler. Problems with Shapley-Value-baseee Value-based Explanations as Feature Importance Measures. In Proc. 37th Int. Conf. on Machine Learning (ICML) pages 5491-5500, 2020.
[71] Olivier Létoffé, Xuanxiang Huang, and Joao Marques-Silva. Towards Trustable SHAP Scores. In Proc. 39th AAAI Conf. on Artificial Intelligence, number 17, pages 18198-18208, 2025.
[72] Sujie Li, Feng Pan, Pengfei Zhou, and Pan Zhang. Boltzmann Machines as Two-Dimensional Tensor Networks. Phys. Rev. B, 104:075154, 2021.
[73] Yuhan Liu, Wen-Jun Li, Xiao Zhang, Maciej Lewenstein, Gang Su, and Shi-Ju Ran. Entanglement-based feature extraction by tensor network machine learning. Frontiers in Applied Mathematics and Statisties, Volume 7 2021, 2021. ISSN 2297-4687. doi: 10. 10.3389/Fams..00 2021.716044
[74] Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag. The Shapley Value of Tuples in Query Answering. Logical Methods in Computer Science, 1021.
14

---

[75] Scott M. Lundberg and Su-In Lee. A Unified Approach to Interpreting Model Predictions. In Proc. 31st Conf. on Neural Information Processing Systems (NeurIPS), pages 4765 46744774, 2017.
[76] Scott M. Lundberg, Gabriel G. Erion, Hugh Chen, Ankur De, Jonas J. Lee, Stephanie Mat- tox, Jared A. Harris, Karlina J. Grimsman, and et al. From Local Explanations to Global Understanding with Explainable Al for Trees. Nature Machine Intelligence, 2(1):56-67, 2020.
[77] Linjian Ma and Edgar Solomonik. Cost-Efficient Gaussian Tensor Network Embeddings for Tensor-Struutuure Inputs. In Proc. 36th Conf. on Neural Information Processing Systems (NeurlPS), pages
2022.
[78] Joao Marques-Silva. Logic-based Explainabilityy in Machine Learning. In Proc. 18th Int. Summer School of Reasoning Web. Causality, Explanations and Declarative Knowledge, pages 24-104, 2023.
[79] Joao Marques-Site Silva and Xuanxiang Huang. Explainability is NOT Game Communications of the ACM, pages 66-75, 2024.
[80] Eric Martin and Chris Cundy. Parallelizing Linear Recurrent Neural Nets Over Sequence Length. In Proc. 6th Int. Conf. on Learning Representations (ICLR), 2018
[81] Reda Marzouk and Colin De La Higuera. On the Tractability of SHAP Explanations under Markovian Distributions. In Proc. of the 41st Inf. Conf. on Machine Learning (ICML), pages 34961-34986, 2024.
[82] Reda Marzouk, Shahaf Bassan, Guy Katz, and De la Higuera. On the Computational Tractabil- ity of the (Many) Shapley Values. In Proc. 28th Int. Conf. Artificial Intelligence and Statistics (AISTATS), 2025.
[83] Jacob Miller, Guillaume Rabusseau, and John Terilla. Tensor Networks for Probabilistic Sequence Modeling. In Proc. 24th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pages 3079-3087, 2021.
[84] Rory Mitchell, Eibe Frank, and Geoffrey Holmes. GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensembles. arXiv preprint arXiv:2010.13972, 2020. Technical Report. https: /trrps://rxxi...o org/ abs /0.00.
[85] Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling Permutations for Shapley Value Estimation. Journal of Machine Learning Research (JMLR), 23(43): -46,
2022.
[86] Maximilian Muschalik, Fabian Fumagalli, Barbara Hammer, and Eyke Hüllermeier. Beyond Tre:SHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles. In Proc. 38th AAAI Conf. on Artificial Intelligence, number 13, pages 14388-14396, 2024.
[87] Maximilian Muschalik, Fabian Fumagalli, Paolo Frazzetto, Janine Strotherm, Luca Hermes, Alessandro Sperduti, Eyke Hüllermeier, and Barbara Hammer. Exact Computation of Any- Order Shapley Interactions for Graph Neural Networks. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
[88] Christopher Musco and R. Teal Witter. Provably Accurate Shapley Value Estimation via Leverage Score Sampling. In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025.
[89] Alexander Novikov, Dmitrii Podoprikhin, Anton Osokin, and Dmitry P. Vetrov. Tensorizing Neural Networks. In Proc. 29th Conf. on Neural Information Processing Systems (NeurIPS),
pages 442-450, 2015.
[90] Georgii Novikov, Maxim E Panov, and Ivan V Oseledets. Tensor-Train Density Estimation. In Proc. 37th Conf. on Uncertainty in Artificial Intelligence (UAI), pages 1321-1331, 2021.
[91] Sebastian Ordyniak, Giacomo Paesani, and Stefan Szeider. The Parameterized Complexity of Finding Coneise Local Explanations. Proc. 32nd Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 3312-3320, 2023.
15

---

[92] I. V. Oseledets. Tensor-Train Decomposition. SIAM Journal on Scientific Computing, 33(5):
2295-2317, 2011.
[93] Vasily Pestun and Yiannis Vlassopoulos. Tensor Network Language Model, 2017. Technical Report.
http//bbs111..... 10248
[94] Guillaume Rabusseau, Tianyu Li, and Doina Precup. Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning. In Proc. 22nd Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pages 1630-1639, 2019.
[95] Shi-Ju Ran and Gang Su. Tensor Networks for Interpretable and Efficient Srantum-Inspirre Machine Learning. Computing, 2:0061, 2023.
[96] Martin Roa-Villes Roal-Sillss,ss, Xuanzhao Gao, Sander Stuijk, Henk Corporaal, and Jin-Guo Liu. Probabilistic Inference in the Era of Tensor Networks and Differential Programming. Phys. Rev. Res., 6:033261, 2024.
[97] Cynthia Rudin. Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead. Nature Machine Intelligence. 165):206-215 215, 2019.
[98] Raghavendra Selvan and Erik B. Dam. Tensor Networks for Medical Image Classification. In Proc. Int. Conf. on Medical Imaging with Deep Learning (MIDL), 2020.
[99] Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling LIME and SHAP: Adversarial Attacks on Post Hoc Explanation Methods. In Proc. AAAI/ACM Conference on AI, Ethics, and Society (AIES), pages 180-186, 2020.
[100] Mihail Stoian, Richard M. Milbradt, and Christian B. Mendl. On the optimal linear contraction order of tree tensor networks, and beyond. SIAM Journal on Scientific Computing, 46(5):6677 B668, 2024. doi: 17862
URL https://doo....... org
/0rgg/1..00 10. 1137 23M16128666222
[101] E. M. Stoudenmire and David J. Schwah. Supervised Learning with Tensor Networks. In Proc. 30th Conf. on Neural Information Processing Systems (NeurIPS), page 4806-4814, 2016.
[102] Zhan Su, Yuqin Zhou, Fengran Mo, and Jakob Grue Simonsen. Language Modeling Using Tensor Trains, 2024. Technical Report. httpp:::/aativ...rggeegree/
2405. 2405.04590
[103] Mukund Sundararajan and Amir Najmi. The Many Shapley Values for Model Explanation. In Proc. 37th Int. Conf. on Machine Learning (ICML), pages 9269-9277, 2019.
[104] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The Shapley Taylor Interaction Index. In Proc. 37th Int. Conf. on Machine Learning (ICML), pages 9259-9268, 2020.
[105] Muhammad Taufiq, Patrick Blöbaum, and Lenon Minorics. Manifold Restricted Interventional Shapley Values. In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pages 5079-5106, 2023.
[106] Guy Van den Broeck, Anton Lykov, Maximilian Schleich, and Dan Suciu. On the Tractability of SHAP Explanations. Journal of Artificial Intelligence Research (JAIR), 72:861-8888 2021.
[107] Stephan Wäldchen, Jan Macdonald, Sascha Hauch, and Gitta Kutyniok. The Computational Complexity of Understanding Binary Classifier Decisions. Journal of Artificial Intelligence Research (JAIR), 70:351-387, 2021.
[108] Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. Beta-Crown: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Robustness Verification. In Proc. 35th Conf. on Neural Information Processing Systems (NeurIPS), pages 29909-29921, 2021.
[109] Haoze Wu, Omri Isac, Aleksandar Zeljić, Teruhiro Tagomori, Matthew Daggitt, Wen Kokke, Idan Refaeli, Guy Amir, Kyle Julian, Shahaf Bassan, et al. Marabou 2.0: A Versatile Formal Analyzer of Neural Networks. In Proc. 36th Int. Conf. on Computer Aided Verification (CAV), pages 249-264, 2024.
16

---

[110] Jianyu Xu, Ling Liang, Lei Deng, Changyun Wen, Yuan Xie, and Guoqi Li. Towards polynomial algorithm for optimal contraction sequence of tensor networks from trees. Phys. Rev. E. 100:043309, Oct 2019. doi: 10.1 10.1103/PhysRevE, 100.043300 URL https
//link. apt...pps..rr. opw.or.//o.//0..//////
Pww.s///hysee..... 100. 043309
[111] Anton Xue. Rajeev Alur, and Eric Wong. Stability Guarantees for Feature Attributions with Multiplicative Smoothing. Proc. 37th Conf. Neural Information Processing Systems (NeurIPS), pages 13388-62413, 2023.
[112] Jilei Yang. Rui Zhang, Cong Li, Meng Zhang, Chao Zhang, Tao Zhang, and Chao Zhang Fast Tre:SHAP: Accelerating SHAP Value Computation for Trees. 2021. Technical Report. lttps://arxivv
2b09 2109. 098477
[113] Jinqiang Yu, Graham Farr, Alexey Igmatiev, and Peter J Stuckey. Anytime Approximate Formal Feature Attribution. In Proc. 27th Int. Conf. on Theory and Applications of Satisfiability Testing (SAT), pages 30-1, 2024.
[114] Peng Yu, Chao Xu, Albert Bifet, and Jesse Read. Linear TreeSHAP. In Proc. 36th Conf. Neural Information Processing Systems (NeurIPS), pages 32112-32123, 2022.
[115] Artjom Zern, Klaus Broelemann, and Gjergji Kasneci. Interventional SHAP Values and Interaction Values for Piecewise Linear Regression Trees. In Proc. of the AAAI Conf. Artificial Intelligence, number 9, pages 11164-11173, 2023.
[116] Erik Štrumbelj and Igor Kononenko. Explaining Prediction Models and Individual Predictions with Feature Contributions. Knowledge and Information Systems, 41(3):647-665, 2014.
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction directly represent the proofs developed in this work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We provide dedicated Limitations section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
18

---

Owing to space limitations, the main paper presents only sketch of central proofs, with the complete versions of all proofs in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA].
Justification:
This is theoretical work, experimental reproducibility is not relevant.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
19

---

Answer: [NA]
This a theoretical work, so providing open access to data and code is not applicable.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips. //nips.c//pil wwcppblicgguticcccccccceoe.oo.pe /etgguddsse/CeSbbbiiiinn Stt.SSbbbiiiiooooiiiii.io for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA].
Justification:
This is theoretical work, and no hyperparameter details needed.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA].
Justification: This is theoretical work, so such statistical tests are not required.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
20

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
This is a theoretical work, so no details on computational resources are required.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes].
Justification: We have read the NeurIPS Code of Ethics Guidelines and ensured that our paper fully complies with them.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: While we recognize the potential social implications of interpretability. our work primarily theoretical in nature and, as such, does not pose any direct social conse- quences.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
21

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: Our work is theoretical; therefore, safeguards are not applicable.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
This work is theoretical; therefore, assets of this type are not relevant.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
22

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]-
Justification:
This work theoretical; therefore, assets of this type are not relevant.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA].
Justification: This work is theoretical; no such crowdsourcing experiments were conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: This work is theoretical; no such user study experiments were conducted.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
23

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA].
Justification: This is a theoretical study and does not involve any non-standard use of LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
24

---

Appendix
The appendix is organized as follows:
Appendix provides extended related work that relevant to this work.
Appendix B provides the technical background, including descriptions of the model families studied in this work, as well as other technical tools - such as Copy Tensors and Layered Deterministic Finite Automata (LDFAs) used in the proofs of various results presented in the paper.
Appendix C provides proofs related to the exact SHAP computation for Tensor Networks with arbitrary structures, namely Proposition |
Lemma 1 and Lemma
Oppendix(Dproviiine the proof of the #P-Hardness of computing SHAP for general TNs (Proposition 2). along with a proof of the NC complexity result for the case of TT's (Proposition B).
Appendix presents the proof of Theorem 2 detailing the NC reductions from the SHAP computa- tion problem for decision trees, tree ensembles, linear models, and linear RNNs the corresponding SHAP problem for Tensor Trains (TTs).
Appendix F provides proofs the fine-grained analysis of BNNs and their connection TNs (Theorem
A Extended Related Work
This section offers an expanded discussion of related work, with particular emphasis key complex- ity results established in prior studies.
SHAP values. Building the original SHAP framework introduced by [75 for explaining machine learning predictions, a substantial body of subsequent work has explored its application across a wide range of XAI settings. This includes the development of numerous SHAP variants [I03] 62 55],
adaptations that align SHAP with underlying data manifolds [49 1051. and extensions that attribute
higher-order feature interactions [50 104 86). From the computational perspective, variety
of statistical approximation techniques have been proposed to improve scalability [50] 104] 86
87 alongside model-specific implementations for classes such linear models (75). tree-based
models 114 84 212
86 76), additive models [47 21 277, and kernel methods [3, 33 Closer to
our line of work, recent efforts aim to construct neural network architectures that support efficient computation of SHAP values [87] 38 Finally, several parallel research threads have highlighted
important limitations and potential failure modes of SHAP across different settings 44 57
70 79]
The computational complexity of SHAP. Notably, [06] study SHAP when the value function is defined via conditional expectations and establish both tractability and intractability results across various ML model classes. Building on this, 6 generalize these findings, showing that tractabil- ity for SHAP using conditional expectations coincides precisely with the class of Decomposable Deterministic Boolean Circuits, and further prove that both decomposability and determinism are necessary for tractable computation. More recently, [8] extend the analysis beyond independent feature distributions to Markovian distributions, which was later generalized to HMM-distributed features
82 alongside an exploration of additional SHAP variants such baseline and marginal SHAP as well as both local and global computation settings. Furthermore, (58) [2) distinguish between the complexity of SHAP for regression versus classification tasks. Other, more tangen- tial but relevant extensions of these complexity studies include analyzing SHAP computations in 66 671, as well as investigating the complexity of alternative attribution schemes beyond Shapley values such as Banzhaf values []] and other cooperative -ame-thecoettc values [10. In contrast, our work significantly broadens existing complexity results by considering much more expressive classes for both the underlying prediction models and the data distributions. Moreover, we are the first to provide a complexity- -theoretc analysis of the parallelizability of SHAP, as well as fine-gra grained complexity bounds for computing SHAP values in families of neural networks.
database settings [5] 74 23
25

---

Formal XAL More broadly, this work lies within the emerging area of formal explainable Al (formal which seeks derive explanations for machine learning models that come with
XAI) 78 14.
mathematical guarantees
59
14 43
18
60
20
65
29
Explanations in this setting
are typically produced through automated reasoning techniques, such as SMT solvers [13 (e.g., for explaining tree ensembles (9] and neural network verifiers [68]
109 [08] (e.g., for explaining neural
networks [5). Since computing explanations with provable guarantees is often computationally intractable, central line of work in formal XAI focuses on analyzing the computational complexity of explanation problems ||
26
B Background
This section begins by formally introducing the ML models examined in this work. It then presents the concept copy tensors, followed by an introduction to Layered Deterministic Finite Automata (LDFAs). Both copy tensors and LDFAs are structures used to support several proof' throughout the appendix.
B.1 Model Formalization
B.1.1 Decision Trees
We define a decision tree (DT) as directed acyclic graph that represents function f ID + [c]. where с
the number of classes. The tree structure encodes this function as follows: Each internal node v is associated with unique binary input feature from {I...., n1; (ii) Each internal node has most outgoing edges, corresponding to values in [k] assigned to the feature at o; (iii) Along any path a, each feature appears at most once; (iv) Each leaf node is labeled with class from [c]. Given an input x ID, the DT defines unique path a from the root to a leaf, where f (xx is the class label at the leaf. The size of the DT, denoted [f]. is the total number of edges in the graph. To allow modeling flexibility, the order of variables can differ across paths a and , but no variable repeats within a single path.
B.1.2 Decision Tree Ensembles
There are several wsta-established architectures for tree ensembles. Although these models mainly differ in how they are trained, our focus is on post-hoc interpretation, so we concentrate on differences in the inference phase. In particular, we analyze ensemble families that apply weighted- schemes during inference- - this includes boosted ensembles such as XGBoost. When all weights are cqual, our framework also captures majority-voting ensembles, like those used in bagging methods such as Random Forests. Conceptually, of individual decision trees. Formally, it is specified by the tuple ([T))e [w; (eemem))) where (Ti) denotes a collection of decision trees (the ensemble), and { {w; Jegm is a set of real-valued weights. The model T is applied to regression tasks and the function it computes is defined as follows:
ensemble tree model T is defined as weighted sum
m
fr xnd
Σ
w; (f1,,....
(6)
B.1.3 Linear RNNs and Linear Regression Models.
Recurrent Neural Networks (RNNs) are neural models specifically designed to handle sequential data, making them ideal for tasks involving time-dependent or ordered information. They are widely used in applications such language modeling, speech recognition, and time series prediction. A (second-order) linear RNN is a sub-class of RNNs, that models non-linear multiplicative interactions between the input and the RNN's hidden state. Formally, second-linear RNN R is parametrized by the tuple- < ho. To W, W.U. U, b, O >
where:
* hn E IR:: is the initial state vector.
TTe E Rdxaxd; Second-order interaction tensor capturing the multiplicative interactions between 2040 and h (1)
h-
26

---

E MN by an RNN is performed sequentially from W RdxN; The input matrix
U R ddxd; The state transition matrix
R4: The bias vector
O NxMout The observation matrix
The parameter d is referred to as the size of the RNN, and N the vocabulary size.
The processing of vector left to right according to the equation:
h: = T X(1,1) h ((2.1) e, + We, + +hh-1+
y = 0 hnn..
Where h is the hidden state vector of the RNN after reading the prefix Fi.y of the input sequence, and y is the model's output for the input instance
Second-order linear RNNs, as defined above, generalize two classical ML models, namely first-order linear RNNs and Linear Regression Models. When the second-order interaction tensor T is set the zero tensor, then the family of second-orde linear RNNs reduced to the family first-order linear RNNs.. If, in addition, the matrix U is equal to the identity matrix, then second-order linear RNN is reduced to linear regression model.
We use three main tensor operations in this work:
(a) Tensor of order 4 (one node with four free indices)
(b) General Tensor Network (TN)
(c) Tensor Train (TT)
Figure 5: Illustrations of (1) A tensor of order 4, (2) A general TN comprising 4 tensors of order and 3 free indices, and (3) A tensor train (TT).
B.2 Elements of Tensor Algebra: Operations over Tensors, Copy Tensors
B.2.1 Operations over Tensors
In this article, we mainly use three operations over Tensors:
Operation Contraction. Given two Tensors T()) E rdd1x...xd and T(2) E x..dd, and two indices (i,j) [n] x [m], such that d, = d' The contraction of Tensors 7() and T(2) over indices and j produces another tensor, denoted (1) x(x)) T(2), over d 1xd1 xx..xd,, xd x.. xd, x xd such that:
(T()) ((is) )(2))
def
a1....Gi-1.. a........ bi.... by-1 -
(2) Thrmnny k i.....
ai 1.k. 11
We slightly abuse notation and generalize single-leg contraction to mulli-leg contraction. For a set S [n] x [m]. the multi-leg contraction (1) x ((2) applics leg contraction to all index pairs in This operation is commutative the result doesn't depend on contraction order.
Operation 2: Outer Product. Given two Tensors (1) JRd1x...xee and ((2) E x
The Tensor Outer product (1)) and T(2) produces a Tensor, denoted T(1) T(2), in
Id X xd, x..' whose parameters are given as follows:
(1 (2)) 01.... on b... (1)
Tar...a -bi....mm
27

---

Operation 3: Reshape. Let T E Rdxxd2xmxxd be tensor of order n, and let [m1, m2..... mm]
be a list of positive integers such that mi + m2 + + my = n. Define: p(i) def
Ei=l mi, q(i) Σi= my and Dj I1 dz. Then, the reshape operation, denoted produces a new tensor T & RRDx DDDDDDDDxe DDxx.xD via a bijection between the multi-index (f1,...,3n) of T and (J1,...,JKy of T'. For each group i, the combined index
mi,
reshape(T,
is: J, 1 Σ j=p(1) -14-1111 1)] di) and set (JJ,....., T(i........ 2n). This
mapping is bijective and preserves the number of elements.
B.2.2 Copy Tensors
In the field of TNs, copy tensor, also known as delta tensor or Kronecker tensor [24], a special type of tensor that enforces equality among its indices. It ensures that all connected indices must take the same value, making it essential for modeling constraints where multiple indices must be identical. This tensor is widely used in operations requiring synchronized index values across different parts of a network. In our context, will be employed to simulate BNNs using TNs (Section[F), as well as in the proof of the HP-Hardness of computing Marginal SHAP for General TNs (subsection D.Ip. Formally, for n 2 1, the elements of the order-n copy tensor, denoted A (m) defined over the index set [d) are given by:
{
if i2 =... in
A
(n) aan
(7)
otherwise
(a) Copy tensor A (4)
(b) Tensor- Train decomposition of A (4).
Figure 6: (a) The copy tensor (4) enforces index-equality among its n legs. (b) Its exact TT
representation is chain of 4 tensor cores, each black node with one "physical" leg (down) and two "bond" legs (horizontal), enforcing i _... in.
In TN diagrams, a copy tensor is traditionally depicted as a black dot with n edges, where each edge represents of its indices (Figure
Copy Tensors as Tensor Trains (TTs). The explicit construction of the copy tensor A (n) scales exponentially with n. Fortunately, as shown in [7). the copy tensor A (n) admits an exact length TT decomposition
(k) E -
ro = rn =1, nh (1
(8)
With the following elements:
(
a = [ap-1 = ix] [[a = is]
(9)
Where ag On 1, and each ag is (l,..., d}. Hence, we have the following:
A
(n) A....n
Σ
L Po
(()
(10)
Since each core enforces (ik-1 = is or,, the only nonzero term in the sum occurs when in thereby exactly reproducing the copy tensor.
28

---

B.3 Layered Deterministic Finite Automata (LDFAs).
Layered Deterministic Finite Automaton (LDFA) restricted form of deterministic finite automaton [56] with a strict layered structure. Let Σ = [N] be a finite input alphabet. An LDFA over defined as a tuple,
A= (L, ( 2.
where:
L 2 is the number of layers;
For each / [E], S; is finite set of states layer 1, and the total of states is Q -Wi S
ô is partial transition function:
8: {(s or) St, a E 1 S
such that for each o), 8(s, σ)) is uniquely defined if a transition exists, and otherwise undefined;
of E S1 is the unique initial state, located in the first layer;
Fy S St is the set of accepting states, all located in the final layer.
The I.FA processes sequences of length L. A sequence w = 0102 or or accepted if there exists such that
sequence of states sf. 82. ....... *
$ = 5 5(s1-1 ,t), for all 1, 1,...,,, N,
and +1 E Fr. By construction, transitions only go forward one layer at time, making the automaton acyclic and enforcing a strict pipeline topology.
LDFAs as TTs. Layered Deterministic Finite Automata (LDFAs) admit natural and efficient representation the Tensor Train (TT) format. Given an LDFA A = (L, (Si) Σ, 6, 8 Fr.) over the alphabet Σ = [N], we construct a sequence of tensor cores ( Y where each core g() is sparse binary 3-dimensional tensor encoding the transition map from layer I I 1. Each core g()) has dimensions corresponding |Si] x [N] [S++1], where an entry G 8') 1 if and only if 8(s, o) = s' (i.e. the transition from the state to the state s' is valid after reading the inpit a.
(I1,..., TL) be Using the TT representation of LDFAs, the acceptance of the input alternatively computed as:
f(x) = c ((11)) g(t) ((311) . x(3.1) ... ((3,1) g(4) N
xs (e o eN
eF,
where S dh ((1,)) : E [4]].
It's worth noting that the conversion from an LDFA to its TT representation can be performed in polynomial time with respect the number of layers L and the total number of states Σ SSt since each transition is represented by single non-zero entry in a sparse tensor core. This TT encoding enables the efficient representation and manipulation of the automaton using TN operations.
LDFAs. Given LDFAs A (L, (,)),,, 5 ,Ft) and (22) (I., (SP) 1=,, E, 52, 22,5,, .1 Ff) with identical input alphabet and number of input layers, the product (1) and (2),, denoted AA) A is a LDFA with the following parameterization:
Product Operation
1 (2) L, (S) S 8' x 2 (5)
0.2 0.2),
FL x F?)
where for any / E [L] and any pair of states (s} 3f) E S x S7 and E H, we have:
(0) x 82) ((s) x 8 σ) (s). o), (s)
The function computed by the LDFA (1) A (2) is equal to [A() LAw LA [T] Concretely, the product operation on LDFAs computes the intersection of two LDFAs. Equivalently,
29

---

when LDFAs encode clauses, this operation corresponds to the conjunction of those clauses. Note that the product operation over LDFAs is commutative.
In the context of our work, we are interested in efficient encodings of the product of multiple LDFAS into a single TN. Fix an integer & 2 1 and let ] be K LDFAs sharing the same input alphabet and the same number of layers. We aim constructing TN that computes the function: fAO) X ....facc If we restrict our TN representation to be in TT format, a naive construction of an equivalent TT consists of applying the Kronecker product over transition maps of all these LDFAs [81]. The state space of the resulting LDFA from this operation scales exponentially with respect to K. However, for general TNs, one can prove that the product over LDFAs admits an efficient encoding in polynomial time:
Lemma 1. There exists a polynomial algorithm that takes as input a set of K LDFAs { ]KE[K] sharing the same inpul alphabet E,, and the same number of layers I. and outputs TN equivalent to A x ... x (K). The complexity is measured in terms of K, the alphabet size, and the number of states of the input LDFAs.
The key building block for proving Lemma is is the copy tensor introduced in the previous section. Specifically, for each layer / E [4]. the tensor obtained by contracting the copy tensor A (K) with the 1-th tensor cores of the TT representations of the LDFAs matches the transition map of the resulting LDFA produced by the product operation. We show this fact in the following proposition. To ease exposition, we restrict our result for the case K = 2. Thanks to the commutative property of the product operation over LDFAs, the general case follows by induction.
Proposition 1. Let A and A be two LDFAS (sharing the same input alphabet and the same num- ber of layers) parametrized TT format as [[ ....,,,..)) and [g (g...)...... g.2.)) respectively. Then, the TT is parametrized as:
LA (3) ((2.1) g(.l) ((.1) ((2.1) ,...., A(3) x(2.1) G(I.)) ((,11) g
(11)
is equivalent to A x 122))
Fr)) be two LDFAs sharing the same input alphabet Σ and the same number of layers L. We show that each layer / E [L- 1], the TT whose parameterization is given in equation (II) simulates exactly the dynamics governed by the transition map of the product LDFA (1)) x 1 at layer 4, namely of x 57.
Proof. Let (1)) = (I, {S E, ,8
0.1 .F) and A = (I, E,, E,,
More formally, denote [g(L.)),. , and [g(2.1),..... g ((2 the TT parametrizations of (1) and 22, respectively. We need to show that, for any (4i, 441, 0, (1+1) E [S|] x [Si+1] x Σ x
[S/] x [5(+1)), we have:
A (3) ((2.1) gl..)) ((.,) gia.))
= i1+il in = [ 0) = -111l 166 -)
= =[ x 8²) ((),))), = (
jr+ )]
where 82, 88, 81 82 refer to the transition map of A(2) and (1) x 12) respectively.
We have:
A (3) (2,1) g(l.)) x(31)) g(2.))
Σ
A 00 o" Mi
(0',0")EIZ
(2.01) (2.1)
(0'( = i+1] -182(1,))) = jiti]
Now, we are ready to prove lemmal) 1
Proof. (Lemmal) 77 Proposition I shows that one can construct a TT equivalent to the product of LDFAs (A(k)) ]KEjK] whose tensor core at layer I are parametrized as:
A (K) x(2.1) ((I.)) x(3.1)
((K+1,1) ((K+1.))
30

---

T 1
22
T4
Figure 7: The structure of TN equivalent the product operation of LDFAS (whose TT represen- tations are depicted in green). The number of layers equal to =. The tensors in the bottom (in black) correspond the TT representation of the copy tensor.
A naive construction of the tensor A (K) scales exponentially with respect to K. However, constructing using TT format (as discussed the previous section) can done in (ppoly(EE), K)) running time.
Using the TT representation of copy tensors, the resulting TN that computes the product LDFA A(1) x... x A(K) has 2-dimensional grid structure whose width is equal to the number of layers and whose height equal to K. This TN structure can be constructed in polynomial time with respect to the size of the LDFAs, K, [E], and T.. Figure provides graphical illustration of this construction.
C Computing Marginal SHAP for General TNs
This section presents the proof of correctness the framework introduced in section to compute exactly Marginal SHAP scores of TNs with arbitrary structures. Specifically, we prove Proposition Lemma I and Lemma 2
I
This section is organized into three parts, each devoted one of these
results.
C.1 Proof of Proposition] 1
Recall the statement of Proposition
Proposition. Define the modified Weighted Coalitional tensor W E B x28 such that V(i, 81,.... 8ma)) [nan) [2] it holds that Wast.....oo
W(s mm if 8, 1, and def ((s Imn) otherwise. Moreover, define the marginal value tensor ((M,)) (M del VMr s; P). Then have 1Dx2 Xnout such that V(x, 8) [2]@n it holds that Va.a.
W Wasgemeee
that:
T(MP) = V x V(M.P)
(12)
where S del {(ko 1, non + 1) &o |ninl]
Proof. We first define the swap(..)) operation. For E N, binary vector E {0, 1)" and E [n]. swap(s, i) returns a binary vector of dimension a equal to s everywhere except for the i-th element where it is equal to 1.
31

---

We rewrite the vector 6s 2, P) (Equation as follows:
T = $i(M,
Σ
W(s) (M swap(s, (ir PI]
(E min
8,=0
Σ
W(s) 8) =E(0,1)00n
Σ
W(s) (M
# (0,1)) mn
81=0
W(s,i) (,r(,, =E(
Σ
(13)
(8)
if 8, = (Feature to explain is part of the coalition)
where: (s)
(s) otherwise (Feature to explain is not part of the coalition)
A contraction of the modified Weighted Coalitional Tensor W with the Marginal Value Tensor (MM across the dimensions defined by the set S (defined in the proposition statement) straightforwardly
yields Equation (12).
C.2 The construction of the modified Weighted Coalitional Tensor W (Lemma)
Recall the statement of Lemma
Lemma. The modified Weighted Coalitional Tensor W admits a TT representation: "....,,(unn]] where G()) Re R2xni, g(t) E <2n1x2x44 for any i [2, 11, and glama) R= x2, Moreover, this TT representation is constructible in (log((mm)) time using
O (m))) parallel processors.
The definition of the Marginal SHAP Coalitional Tensor is:
- W3 Innn) W(5 - In..)
if 5
V(i, 51 Sman) [Mau]] X [2 8
W W1.81
(14)
otherwise
Note the existence of coordinate shift from the boolean representation that lies in (0, 13 to TN representation which lies in [2), hence the subtraction by the vector I,,.. To distinguish between both representations, we use the notation in the sequel to refer to the TN representation of boolean values.
Remark.
In the remainder of this section, shall provide the exact construction of the tensor cores (Gr hefea.) implicitly mentioned in the lemma statement, followed by a proof its correctness and its associated notation.
complexity. Before that, introduce
Notation. For a vector E [2]". we denote |5] the number its elements equal to 1, and 1 R the vector composed of its first & elements. We define the function A that takes as input vector s E [2] and integer i N, and outputs if [(s, = 1) V (n i 1)), -1 otherwise. The function A can be alternatively defined using the recursive formula:
(a) if =i
Yo E [2] A (So, i)
(3,
otherwise
where A(e, i) 1 (c refers to the trivial vector of dimension 0)
High-Level Steps of the Construction. The general idea of the construction is to build a TT that simulates the computation of the modified Weighted Coalitional Tensor by processing its input (i, $1, $2,.... Sm..) from left to right in a similar fashion to state machines. The introduction of each new element šy in the sequence updates the state of the computation by adjusting the weight corresponding to the size of the coalition of features seen so far and retaining the relevant information required for the processing of subsequent elements.
Intuitively, two pieces of information need to be kept throughout the computation performed by the state machine:
32

---

The feature to explain i: This information is provided at the beginning of the computation by the first leg of the tensor W and will be stored throughout the computation, using simple copy operation. This information is needed to flip the sign when the position in the sequence is reached (Equation 14).
The size of the coalition k. Elements of the modified Weighted Coalitional Tensor depend the size of the coalition. This information needs to be updated throughout the processing of the input sequence. Assume at step i E [nan]. the size of the coalition formed from the first features is equal to k:
If 8; 1 (feature is not part of the coalition), we transition the state & to the next step, and we normalize the weight of the coalition accordingly,
If 8; (feature is part of the coalition), transition to the state & + 1, and normalize the weight of the coalition accordingly.
Based on this description, we propose a TT representation of W that maintains an internal state encoded matrix GU) R XMin, The semantics of the element Gi in the matrix reflect the description described above.
(()
Construction of the core tensors {g(*) [ig]n..) For simplicity, we assume that the core tensors are of order 5, so that the internal state encoding takes matrix format and holds the semantics outlined in the above description. The transition to core tensors of order 3 as in the TT format can be performed through a suitable reshape operation. The parameterization of the core tensors {g ]ie(n... is given follows:
The core tensor (1);
1. $1
(feature is not part of the coalition):
{ (-1)0k=l]_ (nin 1)1 if -ink =1
otherwise
2. If 8 (feature is part of the coalition):
G,2 - 10 -(0
(nin - 2] i =2
otherwise
The core tensors (g6) bie (0)3
If 3 (feature is not part of the coalition):
(-1---
g
if f'= otherwise
K.I.P.
(15)
2. & = (feature is part of the coalition):
(k+1)
if = +
(16)
otherwise
The rightmost core tensor of the TT is obtained by contracting g (P..) with the ones matrix 1 (The matrix whose all elements are equal to 1) at the pair of leg indices (4, 1) and (5, 2).
Correctness. The proposed construction designed such a way that captures dynamics outlined in the description above. The state machine maintains sparse matrix equal to zero everywhere except for the element (i, k) where i corresponds to the feature to explain, and à the number of already processed features in the coalition. The following proposition formalizes this fact:
33

---

Proposition 2. Fix an integer nin 2 1. For any E [nan], E [nsn]. (1, E [nam]] and
(81,'- ,5))))))))))))))) E [2], we have:
0
(g0) X(3.1) g(2) ... ((3.1)
E IR Rin X
1,31
:
0_
(17)
where:
(- (-1)A(513)),
Ban Mnin B1g 1)
if 151.11 h
GusBasl
otherwise
Proof. Fix nin 2 1. The proof proceeds by induction on j.
Base Case. Assume j 1. Let i E [Man]. (1, k)) E [re..] and 81 E [2]. Equation 17 construction of (())
holds by
General Case, Assume Equation 17 holds for j [Min - 1], need to show that it's also valid for ++1.
Let k1) E [nm]]² and ( 85+1) E [2]++1. For better readability, we adopt the following notation in the sequel:
HD) def g()) ((31)) G( x ... ((3,1) g(1
By the induction assumption, we have:
H (++1)
|an = (-11)((313.))
(nin
181 1)!
g()
j!
where the second equality is obtained by the induction assumption. We first handle the case when H(++1
11....8/111.. O.
By construction of g(++1, we have:
(1 (k= (31j4z1)
(++1 9 Figli.
H--1
1. =0 0
Next, we analyze the case: = i |1:541| k. We split into two cases:
Case 8j+1 = (The feature j + 1 is not part of the coalition): In this case, note that: $11/41l |s1z]-
We have:
(1+1) 1 Sp = ((12g)))))) |ssy (nin 181 1)! (-1)li=5+1)
j!
j
|sig+1/! (nin |81:/+1| 1)!
(-11)((1511)))
(j+
Case 8341 = 2 (The feature j + is not part of the coalition). In this case, note that: |s1941| = |s1y] + 1, and A(s1.41, i) (ss
We have:
(1+1)
( (-1) (-15s(11))11)))
s1yl1 (nin - |s15+41|!!
S1.411l
j! s1//1l! (nin - |s1541l
(j+1)
(Nin (819+1l)
(- (+1)5(1)))1)))
1)!
(j+1) 1)!
34

---

(j are extremely sparse. By leveraging this sparsity property, each core tensor can be constructed in ((1) time using ( ) parallel processors. By parallelizing the construction all core tensors, this leads to a number of (m parallel processors. Yet, it should be observed that the construction of the leftmost tensor G(1) requires computation of the factorial terms (Min 1)! and (Man 2)!. This operation can be performed using a parallel scan strategy using (1 parallel processors with (llog((sn)) running time.
Complexity. The core tensors (g [jf(mu)]
To summarize, the total computation of the TT corresponding to the modified Weighted Coalitional Tensor requires ((n))) parallel processors and runs O (I.))) time.
C.3 The construction of the Marginal SHAP Value Tensor (MM.)) (Lemma
The objective of this section is to prove the Lemma 2 Recall the statement of this lemma:
Lemma. Let T M and TP be two TNs implementing the model M and the probability distribution P. respectively. Then, the marginal value tensor (MM,P) can be computed as:
[M o o...o ((m xs, TM X8 T
where:
S1 and S2 are instantiated such that for all ks E {1,2) it holds that: S {(5 - k) -i,)) [mm]]..
For any E [non] (a, 8, o²) E [M.] [2] x [N, 02, we have:
M
if (o" A = 1) (o" (o" =d= otherwise
(18)
Before providing the proof Lemma we first introduce an operator which will be useful for the proof:
The do operator 82
Let S be finite set. The do operator takes input triplet (a,, s, o') e S [2] x S and returns if s = 1, o' otherwise. The collection of Tensors M parametrized as in
Equation (8) can be seen as rensorized representations of the do operator [82]. When S [[V.], we
have, for any sa, o',a") E [N:] x [2] x [N:] x [Na]. M a.0",a" n 1 if and only of = 8,
By induction, for any (I, s, x") E II
2 ns2 we have:
(M ..... (m)n)
Vi [nm] do(z, St, x.,2
(19)
2,8,2'
Now, we are ready to provide the proof of Lemma
Proof. (Lemma)) 2) Let (I, s,y) E B
[2] Smin x [nout], we have:
(MM.P) = ERPNT
M (11))/
EN'NTP
Σ (ML)) o... o... z.0.'
T.M
Le
EgITT [MM o... xs, TM
I.0.2' yy
ΣTe T o..")) XS. TM
2,9,0'
Z'ED
= -[MM0))
((M.))..... o... oMMin) xs, T X9, T
x.8.3
35

---

0.1
start
8
%
80
%
$0
si
$
si
s
0.1
0,1
0,1
Figure 8: An LDFA that accepts the set of satisfying assignments of the disjunctive clause: C' In -g 84. The lowest states the grid (1o7, oÿ; st, of) tracks the satisfiability the running assignment. Satisfying assignments are those that reach the state sf
D Computing Marginal SHAP for Tensor Trains
This section contains the proof of the HP-Hardness of computing SHAP for General TNs (Proposition 2) as well as proof of the fact that SHAP for TTs is in NC.
D.1 SHAP for general TNs is #P-Hard
Proposition
states following:
Proposition. Computing Marginal SHAP scores for general TNs #P-HARD.
Proof. The proof builds on known connections between model counting and the computation of SHAP values. Recall that, given a class classifiers C, model counting refers to the problem of determining the number of inputs classified as positive by classifier in C. The following classical lemma established by both [106] and 66:
Lemma Given a class of classifiers C, the model counting problem for is polynomial-tine reducible to the problem of computing Marginal SHAP values for the class C under the uniform distribution.
We note that although the original lemma addresses different value function, specifically the Conditional SHAP variant based on conditional expectations - the Marginal SHAP and Conditional SHAP formulations coincide under the feature independence assumption [103). Consequently, the hardness result established in that setting also applies to the general Marginal SHAP case.
Now, prove Proposition| 2 using Lemma 2 classical result complexity theory that the model counting problem for CNF' #P-Complete .7. Our goal is to reduce this problem the model counting problem for TNs:
the class of CNF formulas proxy. It is
Lemma 3. There exists a polynomial- time algorithm that takes as input an arbitrary CNF formula + and produces a TN that computes an equivalent Boolean function.
Proof. Let & CNF formula composed of L clauses. The reduction proceeds as follows: For each clause, construct equivalent Layered Deterministic Finite Automaton (LDFA). This transformation can performed linear time with respect to the number variables the clause (see Figure for illustrative example). Then, construct the TN that corresponds to the product of the resulting LDFAs. This TN simulates the conjunction over all clauses of the formula The polynomial time complexity of this procedure is guaranteed by Lemma
The proof of Lemma combined with our earlier claims, completes the proof of Proposition
Proof. (Proposition 2 By Lemma the model counting problem for CNTs is polynomially reducible to computing Marginal SHAP values under the uniform distribution. Lemma 3 ensures that any CNF formula is reducible in polynomial time into equivalent TN. Moreover, the uniform input distribution can be encoded as a product of rank-one tensors in linear time with respect to the number of input variables; for instance, by the tensor } (cf + <g) reduction and proves the aa-Hardness computing Marginal SHAP scores for general TNs. [
(e eς). This completes the
36

---

D.2 Marginal SHAP for TT's is in NC
In this section, we provide the details the algorithmic construction to compute the exact marginal SHAP value for TTs in poly-logarithmic time using polynomial number of parallel processors.
The algorithmic construction we propose stems its correctness from Theorem T which states the following:
Theorem. Let = [I()) [(mn) and T pinna) be two TT's corresponding to the model to interpret and the dlata-generatin distribution, respectively. Then, the Marginal SHAP Tensor T PM) can be represented by TT parametrized as:
[
.....
[M x (4.2) I(1) (3322 p()) ((2 g()), ,.....,,M(..... (mEn) ((a
m(n) (332) plaan) ((2.2) ((mand]
(20)
where the collection of Tensors {g(() hxe(ne.) and {M FxE(ne))) are implicitly defined in Lemmal and Lemma respectively.
!
Theorem is a corollary of Proposition 1: Replace V with its TT parametrization (Lemma and replace 7 and T with their corresponding TT parametrizations in the formulation of the Marginal Value Tensor in Lemma
Next, our focus shall be placed on the computational aspect of computing Marginal SHAP scores for TT's by leveraging the result of Theorem to show that this problem is in NC.
Denote:
TM [I ,..., I(..),,( TT model such that, for each E [nen]. Z is in N,, (da,1 = and d = nout).
TT implementing a probability distribution over ID such that, for each i E [min]. p(i) is in RRd xdpa++ (dr,1 = dp = 1),
TP = _
An input instance x= (II....,
Tman)
D.
In light of Theorem as follows:
a typical parallel scan procedure to compute the matrix 4 (TM ,x, TP) runs
Level O. Compute in parallel the following Rin tensors. For i E [man]:
H6 M ((4)))
(() (33 p(i) x (2,2) (+) ((1,1) Nr e [ xndp, x (21)
Level 1 to (nn( At step
j
E (log(n:n).l) Il, perform a contraction operation over
Neighboring Tensors. For
Bin 2
H = H
2-111) j-1 xs H3-1
(22)
where S def {(7 k. [3]]
By Theorem the produced matrix the last step equal ( ,x, TP).
Complexity. Each tensor contraction operation in Equations 21 and 22 requires
most O ntt max das, max dp..)
At level 0, we need to perform in parallel Nin operations of this kind upgrading the number of required parallel processors to O
(E[r.a] sE(naa]
n max dar max dp.;) As for the running time, the depth of the circuit perform-
sE[nial
vE(Nen)
ing the tensor contractions is bounded by (log(n..)) + log( max dM.)) + log( max dp,;) vE(n...]
xE(nra] The depth of the total circuit to compute Marginal SHAP for TTs is thus bounded by log((m))) [log(rum) + log( max d + log( max dp,)]] (E(nin]
:E(ni.]
37

---

E Tightening Complexity Results for Other ML Models
In this section, we employ NC reductions to show that the problem of computing Marginal SHAP scores for certain popular model classes (Linear RNNs, decision trees, ensemble trees, and linear models) lies also in NC² (Theorem2) 2).
An NC reduction a type of many-one reduction where the transformation function from instances of problem A to instances of problem B is computable by a uniform family of Boolean eircuits with polynomial size and polylogarithmic depth. This ensures that the reduction itself can be performed efficiently in parallel. A crucial property the class NC is its closure under NC reductions: if problem A is NC-reducible to problem B, and B is in NC, then A is also in NC (7]
E.1 Reduction from Linear RNNs and Linear Models to TTs.
We assume without loss of generality that N1 N₂ ... Nn This assumption reflects the practical use of RNNs, such as in Natural Language Processing (NLP) applications, where elements of the sequence are assumed to belong to finite vocabulary.
Linear RNNs and TTs. General TTs can be seen non-stationary generalizations of Linear RNNs at a fixed window. Interestingly, Rabusseau el al. [94] showed that stationary TTs are strictly equivalent to second-order linear RNNs (see section B for formal definition of second-order linear RNNs). Indeed, reformulating the equations governing the dynamics second-order linear RNNs in tensorized format, it can be shown using careful algebraic calculation that:
h+ [1]
(f 11 x(.1)
h
((2,1) ex
(23)
Where it holds that:
/ INNN B(N++)xN
IN
TER T is such that:
1. KiEEeAAjEEN
Tajs:
Teg =
{
-iiid+injell
W
Trgs
0
3. lriE
U 0
T:z
All the other elements are set to 0.
The additional dummy neuron at dimension d + (whose value is always equal to 1) is added to the model to account for additive terms present in the linear RNN dynamics equation.
Consequently, a second-order linear RNN R at bounded window n4n is equivalent to the stationary T parametrized as:
( (2.1) 1) x(.1
[oo] 1
- x(221) W..., ((11)
W) (T...(7
O (3.1) ON++1 ]
(24)
Reduction and Complexity. The SHAP computational problem for Linear RNNs under TT distributions takes as input an RNN R of size d mapping sequences of elements in [N] to Reue an input sequence x = (II,..., Imng E [N] and 7 and outputs the SHAP Matrix & (RR x, TP) E _ XRout (Equation) ).
38

---

Fix an input instance (.). Our objective is to construct in poly-logarithic time using poly- nomial number of parallel processors input instance of the SHAP problem for TTs: (T ,, T such that (RR, x. T = @ I JP). The detailed reduction strategy of the SHAP problem of Linear RNNs to the SHAP problem of TT's is detailed as follows:
T.).
Reduction of and TP: The input instance and the tensor T are mapped trivially to the instance 7 and the tensor TP of the input instance of the SHAP problem for TTs. This operation runs in constant time using a linear number of parallel processors with respect to Rin and the size of T
Reduction of the linear RNN R: Equation 24 hints at straightforward strategy to reduce linear RNNs into equivalent TT's at bounded window:
Apply the tensor contraction operation:
T ((21)) I. This operation runs in
(log((N) using (d² N) parallel processors
-Cmpute Leftmost and Rightmost matrices:
-
ha
Leftmost Matrix H(); H() H (1.1)
*
This operation runs in (log(d)) using (d N) parallel processors.
Rightmost Matrix: H(()))) 7. x (3,1)
ON+1
This operation runs in (log(d)) using O N) parallel processors.
Run in parallel O N df) parallel workers place in the input tape of the SHAP problem for TT's the following TT:
M(,, H....,H (ann)
2)times
The total reduction strategy runs in ((max(log(A))oogg) using O(nnn . dl + (TD)) parallel processors.
E.2 Reduction from Tree Ensembles to TTs.
The objective of this subsection is to show that computing SHAP for Tree Ensembles is NC-reducible to the SHAP problem for TTs.
We first note the fact that if computing SHAP for DT's is efficiently parallelizable, then so is Ensemble Trees. Indeed, by the linearity property of the SHAP score, computing SHAP for Ensemble Trees is obtained as a weighted sum of SHAP scores of the trees forming the ensemble. This operation adds (llg((N) depth to the circuit that computes SHAP scores of single DTs, where N refers to the number of trees in the ensemble. This implies the following fact:
Fact. Fix a distribution class P. Computing Marginal SHAP for the class of Decision Trees under P is in NC implies computing Marginal SHAP for Ensemble Trees is also in NC.
In light of this fact, we dedicate the rest of this section to examining the specific case of DT's and their reduction into TTs.
Decision Trees as Disjoint DNFs. We first propose a representation of Tree-based models. This representation has been shown to be more amenable parallelization and forms the core of the pre- processing step as the GPUTreeSHAP algorithm [84). Define the following collection of predicates:
where E [nan], and j E [N,] DT T can be equivalently represented as a disjoint DNF formula over the predicates {Púj [E((...).E(NN)) 81:
Φ C C.VCVV...vv.
39

---

where CL is conjunctive clause.
Clauses (C₂) jer satisfy the disjointness property: For different clauses, the intersection of their satisfying assignments is empty. The conversion of Decision Trees into equivalent Disjoint DNFs has been shown
in polynomial time with respect to the number of edges of the DDT.
In the sequel, we assume that DTs are represented using the Disjoint DNF formalism. In practice, the conversion of a DT into this format can be performed offline (in polynomial time), and stored as such, the same fashion the GPUTreeSHAP Algorithm [8].
We begin by showing how DTs can be encoded in TT format. We assume an arbitrary ordering X1..... Xua. of imput features of the DT:
Proposition 3. DT' T encoded as a disjoint DNF Ør = C1 .... V CL is equivalent to a TT parametrized as:
I ((.1) 1 I(2) ..... I(mm 1), I((mm) x(3.1) 1r.
(25)
such that for I E [nan], the tensor I E BRINNxL is such that:
1 -0==1 {o
if (pi E Cx Ai VVj [M]] Py & C;
otherwise
Proof. Let 7 be a a DT, and 4 - C1 .... V Cr. be its equivalent representation into a disjoint DNF format. For [nin]. we shall use the notation C denote the restriction of the clause to include only predicates in (pis)ig.
We claim that for any [144]] and any (I1, (21,..., IN, as:
D, the TT length k) parametrized
[I(t] ((13) LL, (12)
[()]
is such that:
Fiik F C+
I 22
Ii F ct If this claim holds, then for k = and by the disjointness property of Φr, we have for any x , Tnaa)
fr(11......) T
T 1
which completes the proof of the proposition.
We prove this claim by induction k.
Base case: For k = 1, fix (I1,4) 1) E [N1] [4]. By construction of (()), we have:
(I ((111) 1n)ig, Σ
(()
I'E[T]]
=I(1) -.i.11 1 = [(eess E [N) (P1 e
:Ij E Cl
[ -cl
General Case, Assume the claim holds for k, we show that also holds for +
Let (I1,.. 2b41) E [Ni] .... x [Na-1] and I E [Z]. We have:
I Im
Σ I PELLL]
I
=In I0tt1)
=[ F c+1 [(Pearn E Ct)
VVj E [Ni]: (P(++I) E GJ) vVj e [k+ 11:::ppae Pa+ny E Ci]
= -| - cut11]
40

---

Reduction and Complexity. Proposition suggests the following strategy reduce DT encoded as a Disjoint DNF into an equivalent TT.
Fix Disjoint DNF Φy C1 v... V Cz. The granularity of the parallelization strategy is the literal level: Each parallel processor is dedicated to processing a specific literal Pij in a clause C
If literal Pij appears in the clause C₁ the processor sets the value I to The correctness of this parallel schema is guaranteed by Proposition 3 The running time complexity of this parallel procedure is O(1). The number of parallel processors (L 7Tkm)
F Computing Marginal SHAP for BNNs
In this section, we present the proof of Theorem 3 which provides fine-grained parameterized complexity for the problem of computing SHAP for BNNs. Recall this theorem's 's statement:
Theorem. Let P be either the class of empirical distributions, independent distributions, the class of TTs. We have that:
1. Bounded Depth: The problem of computing SHAP for BNNs under any distribution class P is PARA-NP-HARD with respect to the network's 'ss depth parameter.
2. Bounded Width: The problem of computing SHAP for BNNs under any distribution class P is in XP with respect to the width parameter.
3. Bounded Width and Sparsity. The problem of computing SHAP for BNNs under any distribution class P is in FPT with respect to the width and reified cardinality parameters.
We split this section into two parts: The first part is dedicated to proving that computing SHAP for BNNs with bounded depth remains intractable. The second part provides the details of a procedure that builds an equivalent TT to given BNN. The complexity analysis of this procedure will yield the results of items (2) and (3) of the Theorem.
F1 SHAP for BNNs with constant depth is intractable
We will demonstrate that computing SHAP values for BNNs remains intractable even when the network is restricted to depth of just one. Proposition 4. Given BNN B with one hidden layer, and some inpul x, then it holds that computing SHAP for B and #P-Hard.
Proof. We prove that computing SHAP values for Binarized Neural Network (BNN) with just single hidden layer is already #P-Hard. Specifically, this shown via a reduction from the counting variant of the classic 3SAT problem namely, #3SAT which is known to be #P-Hard 7
We begin by referencing the result of (6), which showed that computing SHAP values for model and input even under the simple assumption that the distribution D, is wniform, is as hard as model counting for f. Consequently, if model counting for is Ha-Hard, is SHAP computation this follows directly from the efficiency axiom under uniform distributions. Therefore, to establish #P-Hardsess of SHAP for model f. it suffices reduce from model with known #P-Hard model counting (e.g., 3CNF formula). Since uniform distributions are a special case of independent distributions and significantly simpler than structured models like tensor trains (TTs), the hardness results extend naturally our setting well.
Consider a 3-CNF formula á 4 A... A bms where each clause literals: t; := x, V 2z ZY.. We construct Binarized Neural Network (BNN) B with a single hidden layer over the input space (-1, 1 setting that already implies hardness for more general discrete domains. Each input neuron of the BNN corresponds to variable in é. so the input layer has n neurons. The hidden layer contains m neurons, one for each clause in Φ. For clause t,, if a variable Jj appears positively, we connect input neuron j to hidden neuron i with weight +1; if it appears negatively, the weight is -1. Each hidden neuron is assigned a bias of 2. Finally, we add a single output neuron with bias of -(m - }))
disjunction of three
3
41

---

We now show that every satisfying assignment to 6 yields "True" output in B, and every unsatisfying assignment yields "False". A clause t, is satisfied if at least one of its variables evaluates to True. This occurs either when non-negated variable is assigned 1 (a "double-positive" case) or when negated variable is assigned to the corresponding hidden neuron, since input and weight signs align. Thus, if any variable in & satisfies the clause, the corresponding neuron receives at least one input of 1. With a bias of 2. even the remaining two inputs contribute -1 each, the total input is 2 = 2\2 > 0, so the step function outputs 1. Therefore, satisfied clauses activate their corresponding neurons. Finally, since the output neuron has a bias of (mm }), outputs 1 if and only all m hidden neurons are active, meaning all clauses satisfied.
(a "double-negative" case). In the BNN, both cases contribute
Since we have shown that each satisfying assignment of the BNN corresponds to a satisfying assignment of Φ, follows that the model counting problem is the same for both. Therefore, for this BNN with only a single hidden layer, and by the result of 6 computing SHAP is #P-Hard.
F.2 Compiling BNNs into Equivalent TTs
In this section, we provide the details of the procedure of compiling BNNs into Equivalent TT', to show that the problem of computing SHAP for BNNs in bounded width (resp. bounded width and sparsity) is in XP (resp. FPT).
F2.1 Warm Up: Compilation of single-neuron BNN with Depth into TT.
As an initial step, present in this subsection construction for representing the activation function of a single neuron in a BNN using TTs. This construction serves as a basic building block for simulating multi-layered BNN architectures by means of the TT formalism.
Let w (w..... w E 1] be the weight parameters of BNN with a single output neuron Nout. Its activation as computed using the reified cardinality representation is given as:
nout (T1,
Inj R)
=
4
R
(26)
where: its reified cardinality parameter, and 4g def
w. w;=1
-
otherwise
To understand how the construction of an equivalent TT simulate this BNN operates, will employ the LDFA formalism previously introduced in subsection B.3
The main idea of this construction is to build an LDFA whose states function counters, tracking the number of satisfied literals {4 hisj)) (Equation (26). When this count exceeds the specified cardinality threshold R. the output neuron Nout activated; otherwise, it remains inactive. Crucially, the number of states at each layer in LDFA scales linearly with the parameter R.
Formally, the LDFA that simulates the neuron nout (Equation (26) is given as follows:
Number of layers: nI,
State space: For each layer E [n], S = {0, Rt} The initial state: sb (The state Layer corresponding to 0)
Transition function: For layer / E [n 1].
(1+1) 8++1
if R?) [[w] 1o otherwise
A =)]
8(s!)) .0)
St
The final state: s
F.2.2 Compilation of single Layer into TT.
In this section, we will move from BNNs with a single neuron into multi-layered BNNs. We will show how one can construct a TT equivalent to a given BNN O(R" -poly(D, max N, nin).
sE[nsa]
where Ri is the reified cardinality parameter of the network, W its width, and D its depth.
42

---

The construction will proceed in two steps:
From Multi-Layered BNN into a BNN with one hidden layer. this step, we convert deep BNN into an equivalent BNN with one hidden layer.
2. From BNN with one hidden layer into an equivalent TT. The resulting BNN with one hidden layer from the first step then converted into an equivalent TT.
Next, we will provide details of how to perform each of these steps.
Multi-Layered BNNs into BNNs with one hidden layer. There are many ways to convert multi-layered BNN into an equivalent BNN with one hidden layer. In the main paper, we propose a technique that collapses the network's depth progressively from the last layer up to the first layer. This technique has the advantage of better scaling with respect to the network's ' depth: Leveraging parallelization, this operation can be performed in Ollog (D)) using a similar parallel scan strategy presented in section D A simpler method consists at settling for building lookup table that maps the set of possible activation values of neurons in the first layer to the model's s output. This lookup table can be built by enumerating all possible activation patterns of the first hidden layer and evaluating the model's output via a network's 's forward propagation operations. This operation runs in O poly(D)) time.
BNNs with one hidden layer into TTs. Given a BNN with one hidden layer whose width equal to 1. The conversion to an equivalent TT can be achieved by remarking that BNN with one hidden layer can compiled into an equivalent DNF formula whose number of clauses is O(2W)).
Let B be a BNN with one hidden layer over nin variables, and W1 be the width of the first hidden layer. Denote:
n -m ): the set of its hidden layer neuron activation predicates,
W (0, (0,1) A Binary Tensor that maps the input to the activation pattern of the first hidden layer, i.e.
W; 1 if A 15(21 (,(21....,, Fren) (27)
((E ........0
Fnia Fram i1, iw;) E D x 1low: W
0 otherwise
E {0, 10,"" A binary tensor that arranges the lookup table (computed the first step) that maps each activation pattern n to the model's output.
The function computed by the BNN B can be written as:
fn(. Dnen)
Σ
W
- -Tsy...
(28)
expresses the function computed by the BNN B as contraction of two tensors: W and T. The tensor is nothing but rearrangement of the lookup table constructed in the first step in a tensorized format. The construction of T requires O(2W1) running time. On the other hand, even when the network's 's width is small, a naive construction of the tensor W (Equation (27p) may scale exponentially with the dimension of the input space. What will show next is how, in bounded width and sparsity regime, this tensor admits TT representation of size O
Equation 288
poly(n,,,N))
Construction of the tensor W. A first observation about the tensor W is that it encodes CNF formula whose clauses correspond to activations of neurons n. On the other hand, in the context of BNNs, clauses are represented using reified cardinality constraints.
The construction procedure of TT equivalent the tensor W runs as follows:
1. For each neuron Nij. we construct its equivalent LDFA A using the procedure outlined as a warm-up at the beginning of this section. The size of the layer's state space of each of these LDFAs is bounded by (R) (R refers the network's 's reified cardinality parameter).
43

---

2. Construct the resulting TT corresponding to the product of the LDFAs {AA he([]]] (sub- section B.3}. while keeping the rightmost core tensor with legs open, thereby ignore the final states reached by the TT.
Leveraging the Kronecker product operation over Finite State Automata [8] to perform product operations, the TT equivalent to the product of W1 LDFAs (whose state space is bounded by constant R) can be constructed in O RR")) time. Consequently, the entire construction produces TT whose size is bounded by O(R": Min N). The running time complexity of the procedure is also bounded by O(R Din N).
44


Reviews:
[{"review_id": "3mrT4ZBCHD", "reviewer": "Reviewer_MUYn", "summary": "Unfortunately, this paper falls outside my area of expertise. While I’m familiar with SHAP values, this paper focuses on theoretical results involving tensor networks and is filled with tensor operator formulations, a topic with which I have very limited experience.\n\nDespite multiple readings, I find the paper extremely difficult to follow, which makes it challenging for me to provide a meaningful or fair review. I believe a reviewer with a stronger background in tensor networks or operations and quantum theory would be better suited for the task.\n\nThank you for your understanding.", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "N/A", "was_revised": true, "final_justification": "As I noted in my review, this paper falls outside my area of expertise. Please do not consider my rating.", "rebuttal": "We appreciate the reviewer’s time, honesty, and feedback. We agree that several of our proofs involve highly technical and non-trivial tensor constructions, which may be challenging for readers unfamiliar with the field. That said, we believe that the figures, formalizations, and high-level intuitions included in the paper do help convey some of these concepts. Still, we fully agree that these aspects can be further refined in the final version, especially given the additional page allowance.\n\nWhile the implications of our results may be more immediately evident to researchers working on Tensor Networks, we also emphasize that our work has broad and significant relevance for the SHAP community. This includes extending configurations where SHAP can be computed exactly to popular ML models under substantially more general distributional assumptions using efficient parallelized algorithms.  Additionally, a novel fine-grained analysis of SHAP complexity for neural networks based on their inherent structural parameters was also presented. \n\nThese contributions are clearly stated and presented in the introduction, conclusion, and throughout the main text, making them accessible even to SHAP researchers who may not engage deeply with every technical proof found in the appendix or the more rigorous sections. Nonetheless, we agree that refining the proof sketches, intuitive figures, and illustrations in the final version will enhance our paper’s accessibility.\n\n We thank the reviewer once again for this valuable input."}, {"review_id": "ym8xut5oUb", "reviewer": "Reviewer_ycjs", "summary": "This paper explores the complexity of computing (marginal) SHAP scores in tensor networks (TNs), and specific sub-classes, such as tensor trains (TTs), as well as binarized neural networks (BNNs). In Section 4, a general framework for computing SHAP scores in TNs is considered, where the SHAP score is expressed as a contraction of two tensors (Proposition 1), which allows to formulate Algorithm 1 to compute SHAP scores as a contraction of two tensors. Section 5 then discusses the complexity of this computation, where Proposition 2 shows that it is #P hard in general. Theorem 1 then establishes that if both $T^M$, and $T^P$ are TTs, then the SHAP tensor can also be expressed as a TT, which then yields that its complexity lies in NC (Proposition 3). As a consequence, decision trees, ensembles of decision trees, linear models and RNNs, can be expressed as TTs and are thus in NC (Theorem 2). Lastly, Section 6 discusses the computational complexity for BNNs, where it is shown (Theorem 3) that for any depth BNN computing SHAP scores is intractable, but narrow and particularly sparse narrow networks have lower complexity.", "questions": "- In Eq. 1 you define $\\phi_i(M,x,P)$, which is then replaced in Section 4 by $\\phi_i(T^M,x,T^P)$. Could you explain this new notation more carefully, e.g. what is $T^M,T^P$?\n- What is the definition of $e^{N_1}_{x_1}$?\n- What is the formal notion of sparsity used for BNNs?", "limitations": "The authors discuss limitations of their work.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- Exploring the complexity of SHAP scores for complex classes of networks is interesting\n- The paper uses rigorous mathematical notation, and carefully distinguishes the complexity classes\n\n**Weaknesses**\n- The paper is very theoretical and abstract, and offers limited practical implications. E.g. the results shown in Theorem 2 for decision trees etc. were already known. Clearly, the class of TTs is more general, but there seems to be little practical implications from this generalization.\n- For readers unfamiliar with TNs and TTs, the paper is generally very hard to follow. In my case, the illustrations did barely help to understand the general structure of TNs. Moreover, the paper claims that decision trees etc. can be expressed as TNs but does not explain further how this is possible. I guess that such simple examples could help the reader understand this abstract class of models.\n- I appreciate the analysis of BNNs, but I would have expected a more practical approach here: What are the implications of this result in practice? What are the costs of enforcing theses constraints in BNNs, e.g. how much would this affect performance? Could you construct such BNNs and compute the SHAP scores, and evaluate the empirical complexity in terms of the parameters?\n\n**Minor**\n- typo line 272, \"in in\"", "was_revised": true, "final_justification": "While this paper is still very theoretical and hard to follow, I think that the contribution is interesting to the community. I appreciate the authors comments and changes, and I am leaning towards acceptance now. I won't increase my score further due to the limited practical implications, and my limited understanding of the technical details.", "rebuttal": "We thank the reviewer for their valuable and constructive feedback and for acknowledging the significance of the theoretical contributions of our work. See our response below.\n\n**Implications of theoretical results for TTs and the novelty of their generalizability to other ML models**\n\nWe appreciate the reviewer’s recognition of the novelty of our tractability result for SHAP within the class of TNs, which we believe is a significant contribution to the explainable AI community in general and to those focused on studying Tensor Networks in particular. The reviewer expressed concern about its practical relevance, suggesting that the results of Theorem 2 are already known. We respectfully clarify that this is not the case. Results of Theorem 2 advance the existing literature in two  ways, with clear practical implications: \n\n*First, improved expressive distribution modeling.* Our result shows that SHAP can be computed efficiently under distributions modeled by Tensor Trains (TTs), thereby relaxing prior distributional assumptions for exact Marginal SHAP computation. While recent work proves tractability for tree ensembles under Hidden Markov Models (HMMs) [1], our result extends this to distributions modeled by TTs. Notably, probabilistic TTs with non-negative weights coincide with HMMs, but general probabilistic TTs with arbitrary weights have been proven to be strictly more expressive [2]. This added expressiveness is important in practice, where incorporating realistic feature dependencies in the SHAP computation improves the quality of the delivered SHAP explanations [3–6].\n\n*Second, parallelizability across model classes:* Theorem 2 implies that SHAP can be efficiently parallelized for models with expressiveness up to that of TTs. One interesting corollary of our constructive proof of practical interest yields a generalized version of GPUTreeSHAP [7], extending its parallel GPU-enabled parallelized computation from empirical to more expressive distributions, such as HMMs and Born Machines [8].\n\n**More intuitive explanations of TNs and TTs and connections with tree ensembles** \n\nWe thank the reviewer for this feedback. While the main paper and the appendix include illustrations and intuitions for TNs and TTs, we acknowledge that the highly technical nature of our treatment may pose challenges for readers less familiar with these models.\n\nTo address this, we propose to improve the exposition in the main text by taking advantage of the available extra page to provide a more accessible introduction to TNs and TTs. Regarding our claim that tree ensembles can be transformed into equivalent TTs, we kindly invite the reviewer to read section D.2. in the appendix for formal details of how tree ensembles are NC-reducible to TTs. In the final version of the paper, we will make sure to include a simple visual example in the main paper illustrating how decision trees (and ensemble trees more generally) can be represented using TNs, to help ground the abstract formalism in concrete, familiar models.\n\nWe believe these additions will significantly enhance the readability and pedagogical clarity of the paper.\n\n**The practicality of the analysis of BNNs**\n\nWe thank the reviewer for their appreciation of our theoretical results on BNNs. We agree that these findings provide a novel fine-grained understanding of structural parameters in neural networks that influence the computation of Shapley values. While the impact of such structural parameters on the *learning* capabilities of neural networks is a central topic in deep learning theory (see, e.g., [9]), our work introduces a new theoretical perspective by linking them to interpretability/explainability considerations, and specifically, to the computation of Shapley-based explanations. While we agree that exploring the practical implications of our result is a natural next step, our primary goal in this work is to lay the theoretical groundwork for understanding which structural parameters of neural networks — particularly, *depth*, *width*, and *sparsity* — contribute to computational bottlenecks in explaining their predictions. In this sense, our contribution is theory-driven, aiming to characterize inherent complexity constraints that arise in BNNs from a structural standpoint.\n\nInvestigating how these structural constraints can be incorporated into training pipelines without significantly degrading predictive performance, in order to obtain trained networks with provably efficient SHAP computations, is an important avenue for future work. We view our results as a foundation for such efforts.\n\n**Reply to questions**\n\n- In the preliminaries section, SHAP values are defined with respect to an arbitrary ML model $M$ and an arbitrary input distribution $P$. In Section 4, these are instantiated as $T^M$ and $T^P$, denoting the same objects (model and distribution) but implemented by TNs.\n\n- $e_{x_{i}}^{N_{i}}$ correspond to the one-hot vector of dimension $N_{i}$ where the element indexed by $x_{i}$ is equal to $1$. Intuitively, it refers to a single input feature fed to a TN model.\n \n- The notion of sparsity adopted in our work corresponds to the *reified cardinality parameter*, a structural measure introduced in [10] and briefly discussed in Section 3.3 (Lines 167–174). This parameter arises from an equivalent reified cardinality representation of BNNs and serves as a proxy for their sparsity. As shown in [10], constraining this parameter during training yields neural networks whose properties can be formally verified with remarkably efficient runtime performance.\n\n[1] On the Computational Tractability of the (Many) Shapley Values (Marzouk et al., AISTATS 2025)\n\n[2]   Expressive Power of Tensor-Network Factorizations for Probabilistic Modeling (Glasser et al., NeurIPS 2019)\n\n[3] Feature Synergy, Redundancy, and Independence in Global Model Explanations using SHAP Vector Decomposition (Ittner et al., arXiv 2021)\n\n[4] Multicollinearity Correction and Combined Feature Effect in Shapley Values (Basu et al., arXiv 2020)\n\n[5] Explaining Individual Predictions When Features Are Dependent: More Accurate Approximations to Shapley Values (Aas et al., arXiv 2021)\n\n[6] Explaining predictive models with mixed features using Shapley values and conditional inference trees (Redelmeier et al., arXiv 2020)\n\n[7] GPUTreeShap: Massively Parallel ExactCalculation of SHAP Scores for Tree Ensembles (Mitchell et al., arXiv 2020)\n\n[8] Tensor Networks for Probabilistic Sequence Modeling (Miller et al., AISTATS 2021)\n \n[9] Width is Less Important than Depth in ReLU Neural Networks (Vardi et al., COLT 2022)\n\n[10] Efficient Exact Verification of Binarized Neural Networks. (Jia et al., Neurips 2020)"}, {"review_id": "hEap4lgv7P", "reviewer": "Reviewer_BJdq", "summary": "The paper proves that Marginal SHAP values of a Tensor Trains (TT) model over a discrete domain can be efficiently computed with a parallel algorithm. It is also argued that TTs are expressive enough to represent Linear, Tree Ensembles, Linear-RNNs, so the results hints at a new algorithm that could rival existing ones (e.g. TreeSHAP) .", "questions": "## Data Distribution as a TT\nLooking at the references provided at lines 267-269, it is not immediately clear to me that independent and empirical distributions can be modeled as a TT. It would help to provide a technical discussion (similar to Section D of the appendix) on how various distributions can be represented within this class of functions. This additional discussion should state clear assumptions about the data.\n\n## Comparisons to Existing Algorithms\nWhile I understand that the paper's contributions are meant to be mainly theoretical, it would be pertinent to highlight the practical \nbenefits of using Algorithm 1 on Tree Ensembles compared to TreeSHAP, LinearTreeSHAP, GPUTreeSHAP etc.\n\n## Extended discussion on SHAP Tractability\nThere is ongoing work on designing new Neural Network architecture that have tractable Shapley Values [1]. While the current paper studies a different class of functions, the reference [1] and others within should be added in a **Related Work** section.\n\n## Discretized Features\nA fundamental assumption made by the Algorithm is that the feature $i$ has been discretized into $N_i$ values. This can be true for certain tree ensembles such as Histogram Gradient Boosted Trees which discretize features in order to efficiently compute statistics while varying the split threshold. However, this is not true for Random Forests for instance. Could the authors clarify the types of Tree Ensembles for which Algorithm 1 is relevant?\n\nMoreover, the value $N_i$ can potentially be very large (for example $N_i=255$ by default if I use sklearn https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.HistGradientBoostingClassifier.html). How would Marginal SHAP Tensor scale \nif I varied $N_i$?\n\n[1] Chen, Lu, et al. \"HarsanyiNet: Computing Accurate Shapley Values in a Single Forward Propagation.\" International Conference on Machine Learning. PMLR, 2023.", "limitations": "The assumptions that features are discretized needs to be discussed in more depth. Also, it is not clear in which settings the data can be modeled with a TT.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "# Strengths\n- The work offers an original perspective on computing Marginal Shapley Values for a variety of models. \n- The paper is technically sound and the theoretical section (2, 3, & 4) are well written.\n- Theorem 1 is of both theoretical interest since it regroups a variety of ML models (.e.g. Tree Ensembles, Linear RNN), but also of potential practical interest because it suggests a parallel algorithm for computing Shapley values.\n\n# Weaknesses\n- It is assumed that the both the model and data distribution can be represented by a TT. While it proven in Appendix D that linear models \nand tree ensembles can be represented with TT,  no such proofs are provided for realistic data distributions.\n-  The paper does not compare Algorithm 1 (either empirically or theoretically)  to existing algorithms such as TreeSHAP, and its variants \nLinearTreeSHAP [1], and GPUTreeSHAP [2]. \n\n\n## Minor Comments\n- At line 191, i do not think that the expression $\\mathbb{R}^{n_{in}\\times 2^{\\otimes n_{in}}}$ is correct. Indeed, \n$2^{\\otimes n_{in}}$ should be $2^{n_{in}}$ since you are counting the number of elements in the set $[2]^{\\otimes n_{in}}$. Same thing at line 194.\n- Algorithm 1 is not necessary and could be removed to increase the space. The method is already clear from the discussion at lines 197-200.\n- $\\mathcal{T}^M$ first introduced at Equation (2) is defined later at line 186. Introducing $\\mathcal{T}^M, \\mathcal{T}^P$ before Equation (2) in Section 4 would improve the flow.\n\n[1] Bifet, Albert, Jesse Read, and Chao Xu. \"Linear tree shap.\" Advances in Neural Information Processing Systems 35 (2022): 25818-25828.\n\n[2] Mitchell, Rory, Eibe Frank, and Geoffrey Holmes. \"GPUTreeShap: massively parallel exact calculation of SHAP scores for tree ensembles.\" PeerJ Computer Science 8 (2022): e880.", "was_revised": true, "final_justification": "Increased my score to \"accept\" given the author rebuttal, which adressed all my concerns.", "rebuttal": "We thank the reviewer for their valuable and constructive feedback and for acknowledging the significance of the theoretical contributions of our work. See our response below.\n\n**How can TTs model empirical and independent distributions?**\n\nWe thank the reviewer for this valuable comment. The concern regarding the absence of a detailed proof for representing empirical and independent distributions using TTs is indeed valid. We would like to clarify our decision in this regard.\n\nRather than reproducing a complete formal treatment, we chose to reference existing work [1], where this result is effectively established. Specifically, the cited work provides explicit constructions for converting both empirical and independent distributions into equivalent Hidden Markov Models (HMMs). Separately, it is well-known that HMMs are a particular instance of TTs [2]. This work is also referenced in our paper. Taken together, these two facts directly imply that empirical and independent distributions can be efficiently represented using TTs.\n\nIncluding a full proof of this fact, similar to those for other ML models in Appendix D, would have introduced a level of redundancy in our manuscript, given the availability of these results in prior work. For the sake of conciseness, we opted to cite the relevant literature instead.\n\nMoreover, we would like to point out that the expressive power of TTs extends well beyond these cases: TTs can model Markovian distributions [1] (and, by extension, $n$-gram models with reasonably small $n$), HMMs (as discussed above), uniform Matrix Product States (MPS), and Born Machines [3].\n\nWe thank the reviewer for raising this concern. To address any potential ambiguity, we will make the connection between these classes of distributions and their representation using TTs in light of the relevant literature more explicit in the final version of the manuscript.\n\n**Comparison with other TreeSHAP variants**\n\nWe thank the reviewer for requesting a comparative discussion. As summarized in the table below, our results improve upon the existing TreeSHAP variants reported in the literature across two dimensions: the complexity class of the SHAP computation algorithm and the class of probability distributions under which exact computation is feasible in reasonable time.\n\n\n   To clarify, traditional TreeSHAP algorithms (TreeSHAP, Linear TreeSHAP, Fast TreeSHAP), operate in polynomial time and generally fall within the $\\mathbf{P}$ complexity class. The GPUTreeSHAP algorithm [6] improves computational efficiency by exploiting parallelization and fits within the $\\mathbf{NC}$ complexity class. All these variants, however, focus primarily on empirical distributions. One of the key findings of our work, in contrast to existing TreeSHAP literature, is that it is possible to design fast, parallel algorithms for computing SHAP values for ensemble trees under significantly richer dependency structures.\n\nIn summary, our method advances the state of the art by enabling efficient, parallelizable exact SHAP computations for ensemble trees under a substantially wider family of distributions, which is critical for capturing realistic data dependencies in practice. This represents a significant theoretical and practical improvement over the existing methods.\n\n\n |  | **P** |   **NC\\*** |\n|:----------:|:----------:|:----------:|\n| **Empirical**  | (Linear) TreeSHAP [4,5]  | GPUTreeSHAP [6]  |\n| **TTs (HMMs, Markovian, Empirical etc.)**  | Marzouk et al.'25\\*\\* [1]  | Ours  |\n\n \n\\* $\\scriptsize{\\text{Note that the complexity class NC is included in P. Moreover, it is conjectured that this inclusion is strict.}}$\n\n\\*\\* $\\scriptsize{\\text{Work in [1] proved the tractability of computing Marginal SHAP of Ensemble Trees under the family of HMM distributions}}$\n\n**Tractable SHAP computation in Neural Networks**\n\nThank you for this valuable feedback. We appreciate you pointing out this relevant line of work on neural network architectures with tractable Shapley value computation. In the final version of the paper, we will incorporate a more refined Related Work section that takes into account the reference you cited, as well as other related contributions in this direction, in order to better situate our approach within the broader literature.\n\n**SHAP for Ensemble Trees: Discrete vs Continuous Features**\n\nWe thank the reviewer for raising this important point regarding the treatment of continuous features. While our theoretical analysis is developed under the assumption of a finite discrete feature space, our results also extend to cover SHAP computation of Decision Trees with axis-aligned split nodes of input continuous features.\n\nIn axis-aligned decision trees, continuous features are typically handled through threshold-based splits of the form  $x_i \\leq t$ or $x_i > t$. Each such condition can be viewed as a Boolean predicate, which may be explicitly introduced as a binary variable. By transforming continuous features into collections of such threshold predicates, the problem can be reformulated over discrete Boolean variables — consistent with the setting of our theoretical framework.\n\nCrucially, this transformation preserves the core structural properties that our complexity analysis relies upon. The number of threshold predicates is upper-bounded by the number of internal nodes in the ensemble, as each corresponds to a unique threshold condition. As a result, the total number of introduced variables remains polynomial in the size of the ensemble, and our **NC** parallel complexity result continues to hold under this extended setting. \n\nRegarding scalability with respect to $ N_i $, we note that the number of parallel processors required by our construction does not depend explicitly on this parameter. Instead, the parallelism level scales linearly with the number of input features $ n_{\\text{in}} $ and the number of paths $L$ in the decision tree. More specifically, the total number of parallel processors required in our construction is upper bounded by $ O(n_{\\text{in}} \\cdot L) $ (see section D.2 in the appendix, lines 1305-1311). \n\n[1] On the Computational Tractability of the (Many) Shapley Values (Marzouk et al., AISTATS 2025)\n\n[2] Expressive Power of Tensor-Network Factorizations for Probabilistic Modeling (Glasser et al., NeurIPS 2019)\n\n[3] Tensor Networks for Probabilistic Sequence Modeling (Miller et al., AISTATS 2021)\n\n[4] From Local Explanations to Global Understanding with Explainable AI for Trees (Lundberg et al., Nature 2020)\n\n[5] Linear TreeSHAP (Yu et al., Neurips 2022)\n\n[6] GPUTreeShap: Massively Parallel ExactCalculation of SHAP Scores for Tree Ensembles (Mitchell et al., arXiv 2020)"}, {"review_id": "MYBxM0erZV", "reviewer": "Reviewer_KnUF", "summary": "In this paper, the authors consider the problem of computing the SHAP\nscore for tensor networks. In particular, they prove that computing\nthe SHAP score for general tensor networks is #P-hard. Then they\nconsider the class of tensor trains, and show that for this class the\nSHAP score can be computed not only in polynomial time, but also in\nNC, which implies that it can be computed in time (log(n))^k for a\nfixed constant k, assuming access to a polynomial number of parallel\nprocessors. The authors use this result to strengthen the tractability\nresults for well-known ML models such as tree ensembles, decision\ntrees, linear RNNs, and linear models, concluding that for all these\nmodels the SHAP score can be computed in NC (under tensor-train-based\ndistributions), which again implies that this computation is highly\nparallelizable. Finally, the authors consider binarized neural\nnetworks and show that the SHAP score can be computed in polynomial\ntime if the network width is bounded.", "questions": "Q1 In Proposition 3, the authors prove that the computation of the\nSHAP score is in NC for the family of tensor trains. This implies that\nsuch a computation is in NC^k for some k. The value of k is important\nto understand the complexity of the parallel algorithm, so it should\nbe included in the paper.\n\nQ2 What is the size of the circuits used in the proof of Proposition\n3? These circuits are of size n^c for a fixed c, and again it is\nimportant to know what the value of c is.\n\nQ3 What is the width of the circuits used in the proof of Proposition\n3? It is important to mention this in the paper as it tells us the\namount of parallelism needed to compute the SHAP score in\npoly-logarithmic time.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nS1 The paper presents a fairly complete study of the complexity of\ncomputing the SHAP score for useful ML models. In particular, it\nproves that the SHAP score can be computed in polynomial time for the\nclass of tensor trains.\n\nS2 The authors consider the possibility of parallelizing the\ncomputation of the SHAP score, which is a useful way in practice to\nreduce the computation time. In particular, they prove that the\ncomputation of the SHAP score is highly parallelizable for the class\nof tensor trains, from which they conclude that the same holds for\nother well-known and widely used ML models.\n\nWeaknesses:\n\nW1 The paper is very dense, and it could benefit from some examples\nand extra proof sketches. I understand the issue with the paper is the\nlack of space, but still, the authors could have tried to save some\nspace to give a more thorough explanation of the polynomial-time\nalgorithm for tensor trains, and why it is highly parallelizable. This\nintuition is something that the readers would appreciate.", "was_revised": true, "final_justification": "I am satisfied with the authors’ answers to the reviewers’ comments. I still believe this paper makes a significant contribution, so I keep my acceptance score.", "rebuttal": "We thank the reviewer for their thorough, valuable, and constructive feedback and for acknowledging the significance of our work. See our detailed response below.\n\n**Improving the presentation and adding proof sketches**\n\nWe thank the reviewer for acknowledging the theoretical contributions of our work. We agree that the slightly dense presentation in some parts of our work stems directly from the highly complex tensor-related technicalities involved in some of our proofs. Although our work already includes several illustrative and high-level examples in both the main text and appendix, we agree that adding more intuitive examples as well as proof sketches for central results, such as the efficient computation of Shapley-based explanations for the class of TTs and their parallelizability, would improve the clarity and accessibility of the paper. In response to this valuable suggestion, we plan to incorporate these additions in the final version, especially given the additional page allowance, as we agree they will strengthen the presentation of our results.\n\n**The width and depth of circuits for parallelized SHAP Computations**\n\nWe thank the reviewer for highlighting these points. While some of these aspects are addressed in the appendix (e.g., lines 1214-1220), we fully agree that they are important and will incorporate a discussion of them in the main text in the final version.\n\nFormally, let us define the parameter $ n_{\\text{in}}$ as the number of input features (the dimension of the input space) and let the terms $r_M$ and $r_P$ represent the maximal ranks of the TTs corresponding respectively to the model being explained and the probability distribution over the inputs. More precisely, the rank refers to the largest dimension among the tensor cores constituting each Tensor Train.\n\nAccordingly, we have that the *width* of the circuit for computing marginal SHAP values for TTs is bounded by:\n  \n  $$ O\\big(n_{\\text{in}}^{5} \\cdot r_M \\cdot r_P\\big) $$\n\nOn the other hand, the *depth* of the circuit computing Marginal SHAP values for TTs is bounded by:\n\n$$ O\\left(\\log(n_{\\text{in}}) \\cdot \\big[\\log(n_{\\text{in}}) + \\log(r_M) + \\log(r_P)\\big]\\right) $$ \n\nTherefore, the problem of computing SHAP values for TTs belongs to the class $\\text{NC}^{2}$. This complexity class includes many widely studied classic parallelizable problems such as *matrix multiplication* and *context-free grammar recognition*.\n\n As such, our complexity results open up the door for leveraging both theoretical and practical insights developed for these problems in the context of SHAP computation. This observation is relevant for a very broad range of ML models, namely, those with expressivity no greater than that of TTs, as well as for expressive representations of distributions that can also be modeled by TTs. We thank the reviewer again for highlighting this point and agree that incorporating a discussion of it into the main text will strengthen the final version."}]

Author rebuttal:

Meta-review: This paper studies the computational complexity of computing marginal Shapley values, and it focuses on the case of functions given by tensor networks and tensor trains in particular. The authors show that while computing Shapley values for tensor networks is #P hard in general, it can be computed in polynomial time (and in parallelized way) for tensor trains, which generalize decision trees, ensembles, linear models, and linear RNNS. The paper also shows that Shap is tractable for binarized networks if the width is bounded but remains hard with constant depth.

**Strengths**:
- Solid theoretical contribution
- Nice generalization of functions with tractable (and parallelizable) computation of marginal Shap.
- Potential implications for parallel implications for a broad class of functions (TTs).

**Weaknesses**
- Somewhat too abstract presentation and dense.
- Limited comparison to existing algorithms.
- The implications for better implementation are potential benefits, but the practical immediate benefits are limited.

**Discussion phase**:

This paper received 3 reviews (plus one, with minimal confidence). The discussion period was highly productive: the authors have clarified the position of their contribution in light of prior work, have promised to improve the presentation with clearer examples, visualizations, and proof sketches. The authors also made clarifications about their assumptions and their applicability. 

**Conclusion**

The discussions above were well received by reviewers, who generally raised their scores and are supportive of the acceptance of this paper. I concur.
Decision: Accept (poster)