{"id":"a01a05f2-7840-400c-9cbf-9d5b729b3e44","arxiv_id":"2510.22138","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"TN-SHAP extracts exact Shapley values and k-way interactions of a multilinear tensor-network surrogate from O(n) probe evaluations, replacing O(2^n) coalition enumeration.","lead":"TN-SHAP computes Shapley values and Shapley-style interaction scores from a tensor-network surrogate using a small number of structured evaluations instead of enumerating all 2^n feature coalitions. The method is exact on the surrogate and, when local model behavior is nearly multilinear, can explain predictions orders of magnitude faster than sampling-based SHAP estimators.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"TN-SHAP's zero-imputation game is not shown to match the v_obs/v_int coalition values of Sec. 2.1, so Theorem 4.1's epsilon premise is not connected to the target.","rationale":"The reader's CONDITIONAL verdict is appropriate. The surrogate-scoped algorithm is algebraically coherent: for an exactly multilinear g, the selector-probe plus Vandermonde interpolation recovers size-aggregated marginals exactly, and the signed-toggle identity in Sec. 10.3 is a correct application of multilinearity. The rank ablations are valuable and suggest that modest TN ranks can recover interaction structure on multilinear teachers. However, the central public-facing claim—replacing O(2^n) coalition enumeration behind Shapley values—depends on the surrogate's coalition values being the same objects as the v_obs/v_int values defined at the outset. The paper never establishes this. Zero-imputation is not distributional conditioning, and for correlated standardized features the two games differ. Theorem 4.1 is an honest bound, but its premise is about an epsilon that is neither defined for the surrogate's actual probe game nor measured. The proposed concrete test settles whether the concern lands: if TN-SHAP matches the zero-imputation game but not v_obs/v_int, then the paper's contribution should be reframed as computing zero-baseline Shapley values of a TN surrogate, with the fidelity-to-target question left as an empirical (and so far unquantified) matter. This is an addressable issue rather than a fatal flaw, so the verdict remains CONDITIONAL.","tokens_in":26611,"tokens_out":7240,"duration_ms":70443,"concrete_test":"On Diabetes (n=10), for 20 test points: (A) compute exact v_obs/v_int Shapley values of the MLP teacher by enumerating all 2^10 coalitions, estimating each expectation with 200 background samples; (B) compute exact zero-imputation Shapley values of the same teacher by setting excluded features to 0; (C) run TN-SHAP. Check whether C matches B and whether A≈B. If A and B differ materially (e.g., cosine similarity < 0.95), TN-SHAP is not computing the Sec. 2.1 Shapley values, confirming the concern. This requires only 20×1024≈20k teacher calls, which is negligible.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.1 defines coalition values as conditional/marginal expectations over D (Eqs. 2.1–2.2). The algorithm, however, probes the surrogate with selectors S_i(t)=Diag(t,1), so S_i(0)x̃_i=[0,1]^T (Eq. 3.3). Thus a feature outside the coalition is replaced by the constant bias channel, not by its conditional mean or a sample from D. The size-aggregated marginals recovered in Eq. 3.5 are therefore Shapley marginals of a 'zero-baseline' game v_g(C)=g({x_i}_{i∈C},{0}_{i∉C}), not of v_obs or v_int. For this to coincide with the target, one would need f (or g) to be multilinear in the original features and the features to be independent with mean zero. The paper standardizes features but does not enforce or verify independence; UCI datasets are correlated. Consequently the surrogate's game differs from the target, and Theorem 4.1's assumption sup_C |v_g(C)-v_f(C)|≤ε is comparing v_g to the wrong v_f unless v_f is also defined by zero-imputation. The paper never states this, and the experiments do not distinguish the two games. A related symptom is that the ε in Theorem 4.1 is never measured; but the semantic mismatch is the more fundamental issue: the exponential enumeration is replaced for a different quantity.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"TN-SHAP proposes to compute Shapley values and order-k Shapley interaction indices by fitting a tensor-network (TN) surrogate that is multilinear in lifted feature vectors [phi_i(x_i),1]^T, then probing it with diagonal selectors S_i(t)=Diag(t,1). The core algebraic claim is that for a multilinear surrogate the size-aggregated marginal contributions are the coefficients of a degree-(n-1) polynomial, recoverable from n evaluations and one Vandermonde solve, reducing the exponential coalition enumeration to O(n*poly(chi)+n^2) per index. The paper provides a theoretical approximation bound (Theorem 4.1), a tractability theorem (Theorem 4.2), and experiments on synthetic and UCI regression tasks showing large wall-clock speedups over KernelSHAP-IQ. The central derivation on the surrogate is sound, but the paper does not establish that the zero-baseline game induced by S_i(0) matches the coalition-value definitions in Section 2.1, and the key approximation error epsilon is never measured.","tokens_in":26977,"tokens_out":10676,"duration_ms":98424,"significance":"The main algebraic insight is correct and useful: for a multilinear game v(C)=sum_{T subseteq C} c_T, Shapley values depend only on size-aggregated marginals, and those marginals can be recovered from O(n) diagonal probes. This is a clean, parameter-free identity that makes the exact computation on the surrogate genuinely tractable. The TN contraction machinery is a novel computational vehicle for this old observation and has the potential to be useful for low-rank or locally multilinear models. The paper also ships an implementation, which aids reproducibility. However, the significance for explaining the original model is contingent on two unverified premises: (i) that zero-imputation coalition values agree with the declared target v_obs/v_int, and (ii) that the surrogate achieves small uniform coalition-value error, epsilon. Theorem 4.1 is a mathematically valid conditional bound, but as a guarantee about the original model it is not connected to the experiments.","major_comments":[{"comment":"The target game is not the game being computed. Section 2.1 defines v_obs and v_int as expectations over the data distribution D (Eqs. 2.1-2.2), but the selectors S_i(t)=Diag(t,1) replace an excluded feature by [0,1]^T (Eq. 3.3), giving the zero-baseline game v_g(C)=g({x_i}_{i in C},{0}_{i notin C}). No argument is given that these coincide for standardized but correlated UCI features. Theorem 4.1's assumption sup_C |v_g-v_f|<=epsilon therefore compares v_g with the wrong v_f unless v_f is also defined by zero-imputation. The paper should explicitly adopt zero-imputation as the intended Explainability semantics and discuss its implications, or change the probe to implement the declared baseline.","section":"Sec. 2.1 vs. Sec. 3.2, Eq. (3.3)"},{"comment":"The uniform coalition-value error epsilon is never measured. The experiments report cosine similarity and MSE against exact teacher SII values, but not sup_C |v_g(C)-v_f(C)|. Thus the theoretical guarantee is not empirically validated, and the phrase 'comparable accuracy' is not tied to the theorem's hypothesis. Please report the uniform error (e.g., over a representative subset of coalitions) or explicitly state that the experiments validate only the surrogate-fidelity heuristic, not Theorem 4.1.","section":"Sec. 4, Theorem 4.1; Sec. 5"},{"comment":"The stated interaction error '2k epsilon' is incorrect for k>=3. For order-k SII, each inclusion-exclusion marginal Delta_C v(T) is a signed sum of 2^k coalition values, each with error at most epsilon, so the marginal error is at most 2^k epsilon; with SII weights summing to 1, the index error is at most 2^k epsilon. The k=3 entry should be 8 epsilon, not 6 epsilon. The proof sketch of Theorem 4.1 covers only single-feature indices and does not support the interaction entries. Please correct the bound and provide the derivation.","section":"Table 1, Sec. 4"},{"comment":"The TN surrogate fitting procedure is underspecified. The text describes a 'binary tensor-tree surrogate (rank chi=16)', an MLP feature map, a Gaussian neighborhood, and '2n^2 selector-weighted interpolation configurations', but never defines the loss function or the tensor-tree parameterization being optimized. Without the exact training objective (e.g., least-squares over teacher outputs at these configurations, with any regularization), the empirical results cannot be reproduced and it is unclear whether the selector probes are part of the training data or only of the inference. Please provide the full training protocol.","section":"Sec. 5.2 and Appendix 11.1"}],"minor_comments":[{"comment":"The complexity statement is per index or per pair, not total for all interactions. The paper should state explicitly that computing all n Shapley values costs O(n^2*poly(chi)+n^3), and computing all pairs costs O(n^3*poly(chi)+n^4) under the per-pair algorithm, to avoid the impression that all order-2 interactions are obtained in O(n^2) total.","section":"Abstract and Table 1"},{"comment":"The initial exposition says 'setting x_j=1 for j in C and x_j=0 otherwise yields f(x)=sum_{T subseteq C} c_T' (Sec. 2.1, Eq. 2.3). This holds for binary inputs, but the method later uses actual values x_i and a separate bias channel. The text should clarify that this is a simplified motivation and that the actual probe uses the lifted features with x_i values retained.","section":"Sec. 2.1 and Sec. 3.1"},{"comment":"The synthetic multilinear validation reports only runtime, not recovery error. Since this is the only setting where exactness on the surrogate is analytically clear, please report the actual Shapley/interaction recovery error against enumeration on the surrogate, not just wall-clock times.","section":"Sec. 5.1"},{"comment":"Several references are duplicated (Grabisch and Roubens 1999a/b, Muschalik et al. 2024a/b, Tsai et al. 2023a/b). Consolidate to avoid confusion.","section":"References"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: TN-SHAP does something useful. It gives a clean way to compute Shapley values and order-k Shapley interactions on a multilinear tensor-network surrogate with O(n·poly(χ)+n²) cost per index, replacing exponential coalition enumeration with diagonal probes and a Vandermonde solve. The algebraic core is Owen's multilinear-extension observation, but the packaging — selectors as trainable feature maps, TN contraction, local cohort amortization — is genuinely new and practically motivated. The central derivation in Section 3.2 checks out: a multilinear map evaluated at t-scaled inputs produces size-aggregated coefficients, and the Shapley weights recover the index. Theorem 4.1 is a correct triangle-inequality bound, and the experiments include rank ablations and a code link, which is more than many papers in this area ship.\n\nThe soft spot matters. Section 2.1 defines coalition values as conditional/marginal expectations over the data distribution, v_obs and v_int. The algorithm, however, probes the surrogate with selectors S_i(t)=Diag(t,1); at t=0 the feature channel is zeroed and the bias channel is set to 1. So excluded features are replaced by zero, not by a conditional mean or a draw from D. The paper never proves these two games coincide, and for standardized but correlated UCI features they generally do not. The stress-test note has this right: TN-SHAP computes Shapley values of the zero-baseline game v_g(C)=g({x_i}_{i∈C},{0}_{i∉C}), not necessarily of v_obs or v_int. Theorem 4.1's epsilon is then an assumption about the wrong comparison — or at best an unmeasured one. The experiments report accuracy against \"exact\" SII but don't say which game the exhaustive enumeration used. If it used zero-imputation on the teacher, the strong cosine numbers validate the surrogate fit, not the Section 2.1 quantity.\n\nA smaller inconsistency: Table 1 and Algorithm 3 list 2^k forwards per probe for k-way interactions, while Section 10.3's signed-toggle identity claims one forward per probe. These can't both be the implemented complexity. The paper should say which is real and how Table 1 relates to it.\n\nThese are fixable. The right response is not rejection but a substantive revision: state the zero-baseline game explicitly, prove or disprove equivalence under concrete conditions (independence plus zero-mean standardization would do), and measure epsilon on held-out coalitions. I'd send it to a serious referee. The method is worth engaging with, and the flaw is in the framing, not in the core algebra.\n\nFor peer review: accept. This deserves referee time, with the semantic mismatch and the complexity inconsistency as the main review asks.","headline":"TN-SHAP is a real algorithmic contribution — polynomial-time Shapley and SII reads off a tensor-network surrogate — but it silently swaps the distributional coalition game for a zero-baseline game and never measures the epsilon its main theorem needs.","tokens_in":27433,"tokens_out":2606,"would_cite":true,"duration_ms":29123,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact Shapley values can be computed in polynomial time for any model well approximated by a multilinear tensor-network surrogate, replacing the exponential coalition enumeration with a handful of structured evaluations.","keywords":["Shapley values","Shapley interaction indices","tensor networks","multilinear extension","polynomial interpolation","model explanations","coalitional games","low-rank approximation"],"falsifier":"On a dataset with n ≤ 12, fit the surrogate exactly as described, then exhaustively enumerate all 2^n coalitions and compute the worst-case coalition-value error between surrogate and true model under both the observed and interventional coalition definitions. If that supremum is not small compared with the output scale, Theorem 4.1's 2ε bound is vacuous and the reported accuracy is attributable to the surrogate's local fit rather than to the lemma.","tokens_in":26485,"feed_emoji":"🧮","tokens_out":7910,"duration_ms":69951,"temperature":0.7,"pith_summary":"This paper claims that the exponential cost of Shapley values and Shapley interaction indices — normally O(2^n) coalition queries — can be replaced by a few structured evaluations. The device is a multilinear tensor-network surrogate: when each feature is lifted to [φ_i(x_i),1] and multiplied by a diagonal selector Diag(t,1), every coalition of size s contributes a term proportional to t^s, so the whole sweep over coalitions collapses into interpolation of a single polynomial. An n×n solve recovers the size-aggregated marginal contributions, and Shapley weights turn them into attributions; the surrogate makes each evaluation cheap. The paper proves exactness on the surrogate plus a 2ε error bound to the true model if coalition values are uniformly ε-accurate, and reports millisecond attributions that are orders of magnitude faster than sampling baselines at comparable accuracy.","feed_headline":"Exact Shapley values in polynomial time via tensor networks","feed_subtitle":"A handful of structured evaluations replaces the exponential coalition sweep, with a proven 2ε error bound.","key_machinery":"The engine is the diagonal selector S_r(t)=Diag(t,1) applied to lifted feature vectors x̃_r=[φ_r(x_r),1]: it scales the data channel by t for included features and keeps a constant bias channel, so setting t=1 includes a feature, t=0 excludes it by zeroing its data channel. Contracting all selectors at once makes the output a univariate polynomial in t whose coefficients are the size-aggregated marginal contributions; a single Vandermonde solve extracts them. The multiplier is the tensor network itself: with bond dimension χ, each probe evaluation costs O(poly(χ)), cutting total cost from O(2^n) to O(n·poly(χ)+n^2).","core_discovery":"TN-SHAP's central claim is that coalitional quantities — Shapley values and order-k Shapley interaction indices — are linear probes of the coefficient tensor of a multilinear map, so they can be extracted without visiting 2^n coalitions. For the probe G_i(t;x) that difference-includes feature i while scaling every other feature by t, multilinearity forces G_i to be a degree-(n−1) polynomial whose t^s coefficient aggregates all marginal contributions over coalitions of size s; evaluating at n distinct points and solving a Vandermonde system recovers these exactly, and the Shapley value is their size-weighted sum. The same construction, with inclusion–exclusion over a size-k subset and a signe","pith_inferences":["The same probe-and-interpolate structure applies to any size-weighted coalitional index, not just Shapley and SII, so the method opens a route to exact semivalues of cooperative games of large n.","The decisive quantity for the guarantee — sup_C |v_g(C)−v_f(C)| — is never measured in the experiments; enumerating all coalitions for a small dataset would test how often the 2ε bound actually binds.","Since one surrogate is fitted per local cohort and reused for every point in it, the amortized training cost is modest, making the method attractive for explaining whole test sets rather than single instances."],"forward_implications":["All n single-feature Shapley values require only 2n² tensor-network forwards plus an n² linear solve, so attribution for models with hundreds of locally multilinear features becomes routine.","Pairwise interactions cost 4(n−1) forwards and order-k interactions cost 2^k(n−k+1) forwards (or one per probe via the signed-toggle identity), with the error bound scaling as 2^k ε.","Any surrogate whose coalition values are uniformly within ε of the true model yields Shapley values within 2ε, independent of the number of features.","Feature maps that are nonlinear per feature (polynomial, Fourier, or learned embeddings) can be inserted without breaking multilinearity, so surrogate fidelity and tractability are independently tunable."],"fun_headline_variants":["Polynomial-time Shapley and interaction indices via tensor networks","No more 2^n: Shapley via tensor networks","Exact Shapley without the exponential coalition sweep","TN-SHAP: A few evaluations for exact Shapley values","From exponential to polynomial: Shapley with tensor networks"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that a low-rank multilinear surrogate reproduces the true model's coalition values uniformly within a small ε — with switching a feature off implemented by zeroing its data channel while keeping a constant bias — so that the Shapley values computed on the surrogate are those of a game close to the original.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time Shapley and interaction indices via tensor networks","No more 2^n: Shapley via tensor networks","Exact Shapley without the exponential coalition sweep","TN-SHAP: A few evaluations for exact Shapley values","From exponential to polynomial: Shapley with tensor networks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000768,"raw_usage":{"total_tokens":3231,"prompt_tokens":726,"completion_tokens":2505,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":470,"completion_tokens_details":{"reasoning_tokens":2420}},"tokens_in":470,"tokens_out":2505,"duration_ms":17199,"temperature":1.0,"reasoning_tokens":2420,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T08:10:06.151491+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a dataset with n ≤ 12, fit the surrogate exactly as described, then exhaustively enumerate all 2^n coalitions and compute the worst-case coalition-value error between surrogate and true model under both the observed and interventional coalition definitions. If that supremum is not small compared with the output scale, Theorem 4.1's 2ε bound is vacuous and the reported accuracy is attributable to the surrogate's local fit rather than to the lemma.","supporting_citations":[],"review_version":1}