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.

How can TTs model empirical and independent distributions?

We 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.

Rather 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.

Including 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.

Moreover, 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].

We 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.

Comparison with other TreeSHAP variants

We 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.

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.

In 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.

* $\scriptsize{\text{Note that the complexity class NC is included in P. Moreover, it is conjectured that this inclusion is strict.}}$

** $\scriptsize{\text{Work in [1] proved the tractability of computing Marginal SHAP of Ensemble Trees under the family of HMM distributions}}$

Tractable SHAP computation in Neural Networks

Thank 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.

SHAP for Ensemble Trees: Discrete vs Continuous Features

We 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.

In 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.

Crucially, 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.

Regarding 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).

[1] On the Computational Tractability of the (Many) Shapley Values (Marzouk et al., AISTATS 2025)

[2] Expressive Power of Tensor-Network Factorizations for Probabilistic Modeling (Glasser et al., NeurIPS 2019)

[3] Tensor Networks for Probabilistic Sequence Modeling (Miller et al., AISTATS 2021)

[4] From Local Explanations to Global Understanding with Explainable AI for Trees (Lundberg et al., Nature 2020)

[5] Linear TreeSHAP (Yu et al., Neurips 2022)

[6] GPUTreeShap: Massively Parallel ExactCalculation of SHAP Scores for Tree Ensembles (Mitchell et al., arXiv 2020)

I want to thank the authors for addressing my concerns. For that I will increase my score to "borderline accept". I still want to follow up on some of the points that were brought up.

Regarding the modeling of distributions as a TT. I went through the Appendix 5 of the reference [1] and I now understand how empirical distributions over binary features can be modeled as a HMM. I still think the paper could benefit from sharing some of the intuition without reproducing the proof. I think it is elegant to view an empirical distribution over 8 features as a random binary sequence 00110001 with stade transition probabilities ( e.g. P(001->0010) and P(001-> 0011)) computed by counting how many time a prefix occurs. Perhaps this intuition and the relationship with TT could be conveyed visually in an effective manner.

On scalability w.r.t $N_i$, although the number of parallel processes for the method is independent of this quantity, I would expect the amount of work per process to depend on $N_i$. For instance the tensors $\mathcal{M}^{(i)}$ has a last dimension of size $N_i^2$. How would a TT contraction algorithm avoid the complexity of summing across this dimension? I think my problem is that I do not understand the complexity of parallel TT contractions algorithms (memory complexity, number of processes, amount of work per processes). Adding an extended explanation of parallel TT contraction, as suggested by W1 of Reviewer KnUF could help.

[1] On the Computational Tractability of the (Many) Shapley Values (Marzouk et al., AISTATS 20

We thank the reviewer for their thorough, valuable, and constructive feedback and for acknowledging the significance of our work. See our detailed response below.

Improving the presentation and adding proof sketches

We 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.

The width and depth of circuits for parallelized SHAP Computations

We 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.

Formally, 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.

Accordingly, we have that the width of the circuit for computing marginal SHAP values for TTs is bounded by:

$O\big(n_{\text{in}}^{5} \cdot r_M \cdot r_P\big)$

On the other hand, the depth of the circuit computing Marginal SHAP values for TTs is bounded by:

$O\left(\log(n_{\text{in}}) \cdot \big[\log(n_{\text{in}}) + \log(r_M) + \log(r_P)\big]\right)$

Therefore, 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.

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.

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.

Implications of theoretical results for TTs and the novelty of their generalizability to other ML models

We 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:

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].

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].

More intuitive explanations of TNs and TTs and connections with tree ensembles

We 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.

To 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.

We believe these additions will significantly enhance the readability and pedagogical clarity of the paper.

The practicality of the analysis of BNNs

We 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.

Investigating 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.

Reply to questions

• 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.

• $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.

• 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.

[1] On the Computational Tractability of the (Many) Shapley Values (Marzouk et al., AISTATS 2025)

[2] Expressive Power of Tensor-Network Factorizations for Probabilistic Modeling (Glasser et al., NeurIPS 2019)

[3] Feature Synergy, Redundancy, and Independence in Global Model Explanations using SHAP Vector Decomposition (Ittner et al., arXiv 2021)

[4] Multicollinearity Correction and Combined Feature Effect in Shapley Values (Basu et al., arXiv 2020)

[5] Explaining Individual Predictions When Features Are Dependent: More Accurate Approximations to Shapley Values (Aas et al., arXiv 2021)

[6] Explaining predictive models with mixed features using Shapley values and conditional inference trees (Redelmeier et al., arXiv 2020)

[7] GPUTreeShap: Massively Parallel ExactCalculation of SHAP Scores for Tree Ensembles (Mitchell et al., arXiv 2020)

[8] Tensor Networks for Probabilistic Sequence Modeling (Miller et al., AISTATS 2021)

[9] Width is Less Important than Depth in ReLU Neural Networks (Vardi et al., COLT 2022)

[10] Efficient Exact Verification of Binarized Neural Networks. (Jia et al., Neurips 2020)

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.

While 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.

These 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.

We thank the reviewer once again for this valuable input.