SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism

ArXi:2510.21599v2 Announce Type: replace 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 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 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.