acceptodds
Under review as a conference paper at ICLR 2027

QuadraSHAP: -Exact Shapley Values for Product Games in Logarithmic Parallel Time

Abstract

We introduce QuadraSHAP, a method for -exact Shapley computation in product games, cooperative games whose coalition values factorize multiplicatively across players. Given a tolerance , our method determines a sufficient computational budget before evaluation, guaranteeing an absolute attribution error of at most for every feature in exact arithmetic. By extending to weighted sums of product games, the framework supports baseline and empirical interventional attribution across a broad class of models, including log-link regression models, Cox proportional-hazards models, odds-scale classifiers, product-kernel machines, and tree-based models. For a -player product game, we replace the exponentially large coalition sum by a one-dimensional integral of a polynomial of degree at most . Gauss–Legendre quadrature with nodes therefore recovers exact Shapley values when . For given positive tolerances, we derive a computable, factor-dependent error bound that decays geometrically in and yields a sufficient node budget for the prescribed tolerance. Efficient evaluation at scale is enabled by sharing computations across features and evaluating products in log-space with sign tracking, mitigating intermediate overflow and underflow. Given the quadrature rule, computing all attributions requires work per product game, compared with for direct coalition summation, and admits parallel time with sufficient processors. On a survival analysis problem with features, the exact quadrature configuration computes all feature attributions in approximately five minutes of GPU evaluation per explanation, at a scale where exhaustive coalition enumeration is infeasible. Explicit error control enables a further reduction: setting selects a smaller, theoretically certified quadrature budget and reduces the mean evaluation time to seconds per explanation. These results demonstrate scalable attribution with explicit error control and motivate application of low-latency explanations for real-time safety-critical decision support. Code is available at https://anonymous.4open.science/r/quadrashap-28D7.

Primary area:
interpretability and explainable AI
Keywords:
shapley value, explainability, quadrature

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_hzegOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the computation of Shapley values on so-called product games, which are games where the coalition value is expressed as a product over fixed individual player contributions (Def 1). The paper establishes an integral representation using the Owen's multilinear representation of the Shapley value, which then involves an integral over a d−1d-1-order polynomial (Prop 1). This integral can be solved via Gauss-Legendre quadrature via d/2d/2 evaluations, and approximately with less, for which an error bound is given (Prop 2). Using the error bound, the authors establish a certificate for an ϵ\epsilon-close approximation (Prop 3), and establish a sequential and parallel computation schemes (Prop 4). The authors then proceed to identify product games in multiplicative models (Def 2), and demonstrate that baseline and interventional value functions in these models are defining weighted sum of product games (Prop 5), which can be solved the same way through linearity of Shapley values (Prop 6). The multiplicative models includes a diverse range of models (Table 1). Finally, the method is evaluated on product-kernel methods and other applications against exact numeration, and the benefits of ϵ\epsilon-approximated solutions are highlighted, which further increase the runtime. Lastly, the scalability is illustrated on a high-dimensional Cox model.

Critical strengths
  1. Scope: The paper is written very general using the broad class of product games, which extends exact Shapley value computation to a diverse range of (multiplicative) models, including product-kernel methods, trees, and Cox models, which enables new applications such as survival analysis. Moreover, the value functions are clearly linked to the model predictions and abstractly viewed as instances of product games or weighted product games. This is often overlooked in related literature e.g. on TreeSHAP, and beneficial for future research in this domain.
  2. Approximation guarantee: In contrast to concurrent/previous methods, the authors provide a guaranteed ϵ\epsilon-approximation of the Shapley values using fewer evaluation points of the integral representation
Critical weaknesses
  1. Limited technical depth and novelty: The tools used were mostly known and there is limited novelty in each separate contribution. TreeGrad and Quadrature SHAP have proposed similar methods via Gauss-Legendre integration. Its exact computation and approximation guarantee (Prop 2) follows directly from previous results. The bound appears to be novel (Prop 3) and most significant novel contribution. The results on multiplicative models and representation of value functions as weighted product games (Prop 5, Prop 6) are also modest. The overall novelty of the approach is to combine these results to solve the computation of Shapley values for new types of models. I think, though, that the authors have presented their approach in a transparent way, which is sufficiently linking to prior discoveries.
  2. Limited discussion on optimal complexity and distinction between product games and special case of tree-based product games: The product game formulation is universal and includes the most-relevant practical application, namely tree-based models and TreeSHAP. However, the underlying structure of a tree-based model is richer in its presentation, since several paths (products) are shared between leaves. It seems that this underlying structure is crucial in the computation of the trees. I think it would be beneficial to spend additional time on the special case of tree-based games (as a special case of product games), and outline the algorithmic details that are required to solve this computation more efficiently than simply treating it as weighted sum of isolated product games. Related to this is a discussion on a lower bound of the complexity for such game structures, separately for tree-based games and product games (see questions below). For future research, it would be beneficial to know if lower complexities can be achieved. While the current quadrature approach is known to be optimal for solving the integral, it remains unclear if there could be faster ways for computing Shapley values in these types of structures. A separate discussion on computational complexities and possible lower bounds would be helpful for future research, and are currently missing. This extended discussion would also strengthen the theoretical contribution mentioned in W1.
Questions for authors
  1. considering W1, an extension of the theoretical contribution would be to additionally provide the Möbius and Fourier spectrum of the given product game value functions, can you state these, and contrast tree-based product games with other product games?
  2. considering W1, could the newly established computations of Shapley value be used to enrich benchmarks of Shapley value approximators? Do these model types exhibit different structure than existing benchmarks, which are often tree based?
  3. considering W2 above, where does the implemented QuadraSHAP approach for tree-based models exploit the tree structure explicitly? What are the implications for its computation on trees? Is it really just an average over several weighted product games as described in the theoretical result?
  4. considering W2, does there exist a lower complexity-bound that is achievable for general product games, which is lower than QuadraSHAP's O(d2)\mathcal O(d^2)? If not, why not? If yes, why is it less preferable or stable than QuadraSHAP's approach? Is there any sort of "optimal" complexity for these types of games?
3 comments

We thank the reviewer for the careful assessment and for recognizing the scope of the product-game framework and its approximation guarantees. Our responses to the concerns are provided below.

W1. Technical contribution. Proposition 2 uses the standard Gauss–Legendre error bound. Proposition 3 turns this bound into a sufficient node budget computed directly from the factors of the product game. Specifically, the Bernstein-ellipse bound in Proposition 2 depends on the maximum of a polynomial of degree d−1d-1 over an ellipse, a quantity that is not readily available. Lemma 1 in Appendix C.1 bounds this maximum using two quantities computed from the factor table in O(d)O(d) time: the absolute scale ∣ui−1∣Πi|u_i-1|\Pi_i and the total relative variation Λi\Lambda_i. The bound holds for every admissible ellipse parameter, which we optimize by solving a scalar equation. This yields a node budget for a prescribed accuracy before quadrature evaluation. Appendix C presents the full procedure, including its extension to weighted sums of product games. This factor-based budget for general product games distinguishes our contribution from the cited tree quadrature methods, with a significant impact in practice: we can compute ϵ\epsilon-exact Shapley values for problems with tens of thousands of features in a fraction of a second. Identifying product structure in different value functions of several well-known models also extends the practical applicability of QuadraSHAP.

W2 and Q3. Tree structure. We agree that tree structure enables more efficient computation by reusing work along paths shared by multiple leaves. We derive this tree-specific computation in Appendix F. Since it is closely related to the computations in TreeGrad-Shap and Quadrature-TreeSHAP, we present the derivation in the appendix and keep the main text focused on the general framework. We have added an explicit reference to Appendix F in Section 4.

In Appendix G.5, we compare QuadraSHAP with existing tree explainers on CPU and GPU. On the GPU benchmarks, QuadraSHAP is faster than Quadrature-TreeSHAP in 17 of 18 settings. Both use GL quadrature with the same asymptotic tree complexity, so the timing differences reflect implementation choices, including GPU kernel development.

Q1. Möbius and Fourier spectra. We agree that the Möbius and Fourier spectra provide important ways to characterize interactions among features. In Appendix D, we derive closed-form expressions for both spectra of product games and explain how they extend to weighted sums by linearity. We also show how the Möbius coefficients recover our integral representation of the Shapley values. Section 2 now refers to these results.

In a tree leaf game, every off-path factor equals one. Consequently, a subset can contribute to either spectrum of the tree only if all its features occur together on at least one root-to-leaf path. A general product component can involve all input features, so its coefficients can be nonzero at every interaction order. We have added these formulas and the comparison to Appendix D.

Q2. Benchmarks for Shapley approximators. Product-kernel, log-link, and survival models can complement small-game and tree-based benchmarks with high-dimensional games that exhibit interactions across many features and orders. Full-degree quadrature provides reference attributions in exact arithmetic. We added a discussion about this benchmark application in the Conclusion, including the need to document the background set and numerical precision.

Q4. Complexity lower bound. In a sequential model where each attribution occupies one memory word, explicitly returning all dd Shapley values requires Ω(d)\Omega(d) work. Given the quadrature rule, our evaluation requires O(d mq)O(d\,m_q) work. It is therefore optimal up to the node budget and matches the linear output lower bound in regimes where the certified node count mqm_q remains bounded as dd grows. For general product games, we do not establish a stronger lower bound or claim that the O(d2)O(d^2) work of the full-degree regime is optimal.

Dear Reviewer hzeg,

Thank you again for your review and your positive assessment of the paper. As the discussion period closes on November 18, we would like to ask whether our response has addressed your concerns. We would be glad to clarify any remaining points.

I thank the authors for their effort to address my concerns. While I still believe that the technical depth is not too strong, I believe that this paper should be accepted and will increase my score accordingly.

Reviewer_ai1jOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

QuadraSHAP computes Shapley values for product-form coalition games and weighted sums of them. The classical multilinear/Beta-integral identity reduces each attribution to a one-dimensional polynomial integral. Gauss–Legendre quadrature is exact at ceil(d/2) nodes in exact arithmetic; a factor-dependent Bernstein-ellipse bound selects a sufficient smaller budget for positive absolute tolerances. Shared log-space products, sign/zero handling, and parallel reductions evaluate all coordinates efficiently. The framework covers several multiplicative output scales and finite-background interventional games. Experiments include certified-versus-observed budgets, product-kernel benchmarks, very high-dimensional Cox models, sampling comparisons, and tree implementations.

Critical strengths
  1. The strongest contribution is the computable a priori certificate, not merely the integral identity. Proposition 3 and Appendix C eliminate an unknown complex-ellipse maximum using factor scales and total relative variation, optimize a scalar parameter, and extend the bound to signed weighted sums by absolute error accumulation. The exact-degree fallback ensures a sufficient budget exists.
  2. The model/value-function mapping is useful and explicit. The paper distinguishes baseline, empirical interventional, and neutral-factor games, preserves dependence among absent features by averaging whole background rows, and states that logistic/NB outputs are explained on the odds scale rather than probabilities.
  3. Numerical range is addressed constructively. The log-space evaluator avoids forming long raw products, and the prefix/suffix variant handles zero and signed factors without division. The paper explicitly distinguishes quadrature error from floating-point rounding and background approximation.
  4. The practical evidence is substantial. Certified budgets are far below full degree in the tested families, with controlled signal/reference studies and an analytically solvable product game. The Cox example has 396,065 features, selecting 41–53 nodes at tolerance 1e-6 instead of 198,033 full-degree nodes, with reported warm evaluation time .36 seconds versus 311.10 seconds.
  5. The relation to concurrent tree quadrature methods is treated unusually carefully in Appendix A/F: the same tree integrand/node representation is acknowledged, and GPU differences are attributed to implementation/call organization rather than a new asymptotic tree algorithm. The appendix supplies relevant sampling and tree comparisons rather than only an exhaustive-enumeration baseline.
Critical weaknesses
  1. The mathematical certificate does not certify the returned floating-point vector (Secs. 2–3, Appendix G). This is explicitly disclosed and does not invalidate the exact-arithmetic theorem. However, “epsilon-exact” can still be read as a software accuracy guarantee. In Appendix G.4, float32 runs requested at 1e-10 have observed errors around 1e-8–1e-7, illustrating the distinction. In the largest Cox example, the same 1.75e-7 discrepancy across requested tolerances suggests a rounding/reference floor rather than measured quadrature error. State precision and observed resolution beside headline tolerances, and distinguish the bound, finite-precision evaluation, and finite-precision bound computation/root finding. A validated numerical error enclosure would be stronger future work; it is not required to make the current mathematical result valid.

  2. The high-dimensional “exact” reference and some numerical checks are not independent (Sec. 5.3, Appendix G.5). Full-degree quadrature uses the same evaluator, so agreement can share rounding or implementation errors. Efficiency residuals in deep-tree tests are useful necessary checks, but errors can cancel across coordinates and preserve efficiency. The analytic product control and independent TreeGrad agreement on a separate suite are strengths; they do not automatically validate every deep-tree/high-dimensional coordinate. Please identify existing independent/high-precision checks or narrow claims from demonstrated coordinate correctness to consistency with the stated reference.

  3. Headline timings concern a specific warm evaluation scope (Sec. 5.3). Cox timings include automatic node selection but exclude quadrature-rule construction and warmup, with five patients and one full-degree call per patient. This is reported, yet the abstract's low-latency/safety-critical motivation could be read as end-to-end deployment evidence. Summarize setup amortization, peak memory, rule caching, device transfer, and patient/model variability. The full-degree QuadraSHAP baseline demonstrates a useful accuracy-budget trade-off; it does not establish that 311 seconds is the fastest possible exact Cox attribution implementation.

  4. Novelty and generality need to remain centered on the actual advance. Owen's identity, Gauss–Legendre polynomial exactness, scan/reduction parallelism, and the basic tree quadrature computation are established. The paper generally acknowledges this; lead consistently with the factor-derived budget certificate and broad model formulation. O(log d) is parallel span with a growing processor budget and a supplied quadrature rule, not logarithmic sequential work or unconditional GPU latency. Weighted sums introduce p and background-count factors, and a very large sum-of-products representation can limit practicality.

  5. Absolute-error usefulness is output-scale dependent (Proposition 3, Table 1). The product scale and cancellations strongly affect the certificate; small absolute tolerance need not preserve rankings or relative error of near-zero attributions. Conversely, background choice can change the attribution target independently of quadrature accuracy. Provide a practical tolerance-selection example and report output/attribution scale. The fixed finite-background game is itself a valid estimand; there is no demonstrated need to estimate a population expectation for every application.

  6. A few comparative statements need tighter numerical presentation. Put a concise sampling/tree comparison summary in the main text, retain CPU/GPU and precision qualifications, and avoid treating an efficiency check alone as full correctness validation. Appendix G.5.2 calls 1.544 ms versus 1.631 ms a 1.37-fold advantage; the displayed values imply about 1.06-fold, so please correct or explain the aggregation. These editorial/comparison issues do not drive the main recommendation.

Questions for authors
  1. What floating-point precision is used in each headline benchmark and in the certificate computation? Are there existing independent/high-precision or compensated-summation checks for the largest Cox case, beyond agreement with the same full-degree evaluator?
  2. Can the software report requested quadrature tolerance separately from an observed/estimated rounding floor, especially for float32 tolerances below that floor? Please clarify the certificate's numerical evaluation safeguards.
  3. What setup/rule-construction costs and peak memory are excluded from the .36-second Cox figure, and how are they amortized? Is an independent exact recurrence comparison already available at a tractable dimension?
  4. What existing coordinate-level checks accompany the deep-tree efficiency residuals, and can the erroneous 1.37-fold ratio be reconciled with the displayed times?
  5. How should a practitioner choose an absolute tolerance on odds/relative-hazard output scales? Is a normalized known-scale error option already supported, without implying a relative guarantee for potentially zero attributions?
4 comments

We thank the reviewer for the detailed comments, which helped us improve the paper. Our responses to the concerns are provided below.

W1, Q1 and Q2. Floating-point error. Thank you for the careful reading of the paper. Section 2 of the submitted paper distinguished the quadrature guarantee in exact arithmetic from floating-point rounding, and Appendix G specified float64 arithmetic unless stated otherwise. We now also state the precision at the start of Section 5. In G.4, the float32 attribution vectors differ from a separate float64 calculation by a few 10−810^{-8} across the tested tolerances, including requests of 10−1010^{-10} and below. We had already mentioned this in the experiment, but have now highlighted it further. The remaining experiments use float64.

The Python implementation computes the node budget in float64 and selects the ellipse parameter by bisection. The analytic bound holds for every ρ>1\rho>1, so an approximate minimizer can loosen the bound while preserving its validity in exact arithmetic. We clarify in Appendix C that evaluating the bound in floating point introduces a separate source of error. The budget report gives the requested tolerance, selected node count, and computed quadrature bound. G.4 reports observed discrepancies separately. The software currently provides no automatic estimate of the rounding floor, but the repository will be updated to include this functionality. A validated enclosure for the complete finite-precision calculation remains future work.

W2, Q1 (second part), Q3 (last part), and Q4 (first part). We agree that agreement with a full-degree run of the same evaluator is a consistency check rather than an independent one, and the paper treats it as such: Section 5.3 reports Δ\Delta as the discrepancy from the full-degree computation, and G.5.1 now describes the efficiency residual as a numerical consistency check, with coordinate-level agreement assessed separately in G.5.2. Independent checks exist for each experiment family, and the revision reports them as follows:

  • Budget study (Appendix G.3). Besides the analytically solvable product game, all 21 cases flagged at 10−610^{-6} were recomputed with complete 50-decimal-digit reference vectors, including high-precision nodes and weights. Additionally, 24 selected coordinates were compared with independently computed high-precision Bernstein integrals. No observed count at the main tolerance changed. G.3 now states this.

  • Product kernels (Section 5.2). PKeX-Shapley is an exact recursion that shares no code with our evaluator. Where both methods run, their attributions agree to 2.7×10−152.7\times10^{-15}, 1.3×10−151.3\times10^{-15}, and 7.8×10−167.8\times10^{-16} at d=50d=50, 500500, and 1,0001{,}000, respectively, measured as the largest coordinate difference over 50 inputs. This is the independent exact comparison at tractable dimensions requested in Q3, and Section 5.2 now reports it.

  • Cox models (Section 5.3). Two checks are independent of the GPU evaluator. The test suite of our Python repository compares the Cox explainer with exhaustive coalition enumeration through the model’s hazard function on an empirical-background game, using absolute and relative comparison tolerances of 2×10−122\times10^{-12}. For the two cohorts of Section 5.3, with the same fitted models, background rows, and patients, a separate double-precision implementation that shares no code with the evaluator (log1p/expm1 on factor differences, no shared products) computed a 64-node reference, cross-checked at 96 nodes. The attributions at the certified budgets agree with it to 1.2×10−111.2\times10^{-11} for GSE24080 and 1.6×10−101.6\times10^{-10} for TCGA LGG across all 30 patient–tolerance cases. Appendix G.2.4 now reports this check. Δ\Delta in Table 3 is defined as the discrepancy from the full-degree output and, as Section 5.3 notes, reflects the rounding level of that reference rather than the quadrature error.

  • Trees (Appendix G.5). Coordinate-level agreement is reported in G.5.2: 8.9×10−158.9\times10^{-15} against TreeGrad-Shap and 7.3×10−67.3\times10^{-6} against GPUTreeSHAP, an exact algorithm unrelated to quadrature, on the six GPU model shapes. On imdb (depth 20), where the CPU competitors remain stable, all methods agree. For the deeper text forests of G.5.1, no external exact reference is available because the tested competitors break down there. G.5.1 now states that these results support numerical stability rather than demonstrated coordinate correctness.

W3. Reported time. We thank the reviewer for highlighting the setup cost, which led us to adopt a faster and more accurate method for constructing large quadrature rules.

First, we clarify the timing protocol. Following Appendix G.1 and the Shapley-value benchmarks used for comparison, the reported time per explanation excludes model fitting and explainer construction. For exact computation, constructing the Gauss–Legendre rule is part of explainer construction. The rule depends only on the number of nodes, so it is constructed once and reused across inputs to be explained.

That said, we now construct all rules with FastGL (Bogaert, 2014), an iteration-free method that computes each node–weight pair independently in O(1)O(1) work, and we have rerun the Cox experiments with it. Construction now takes 0.650.65 ms and 10.6910.69 ms for the full-degree rules with 27,33827{,}338 and 198,033198{,}033 nodes, respectively, and under 0.40.4 ms for the certified rules with 37–57 nodes. Table 3 now reports these construction times separately, and the reported times include all per-explanation work: rule construction, automatic node selection, host–device transfers, and accumulation on the host.

The new rules are also more accurate. The previous construction used SciPy for large rules, whose weights lose accuracy as the number of nodes grows, with relative errors of approximately 10−510^{-5} near the endpoints already at 20,00020{,}000 nodes. This limited the accuracy of the full-degree reference. With FastGL, the discrepancy between the certified and full-degree results falls from 1.75×10−71.75\times10^{-7} to at most 3.84×10−113.84\times10^{-11} for TCGA LGG, and from approximately 4.5×10−104.5\times10^{-10} to at most 9.01x×10−129.01x\times10^{-12} for GSE24080 (Table 3).

These discrepancies are far below the requested tolerances, even at ϵ=10−1\epsilon=10^{-1}. For GSE24080, tightening the tolerance from 10−110^{-1} to 10−610^{-6} increases the certified budget from 44–53 to 48–57 nodes, while the discrepancies remain around 10−1210^{-12}–10−1110^{-11}. The absence of a systematic decrease is consistent with floating-point effects dominating the measured differences from the full-degree outputs.

W4. Novelty and generality. We build on the established integral identity, Gauss–Legendre quadrature, and parallel reductions. Our contribution is the factor-derived certificate that selects a sufficient node budget before evaluation, together with a formulation covering multiple model families and value functions.

For a single product game, evaluation requires O(d mq)O(d\,m_q) work and has O(log⁡d)O(\log d) parallel span when mq=O(d)m_q=O(d), the quadrature rule is supplied, and sufficient processors are available. For empirical interventional games with pp product components and nbn_b background rows, the work is O(p nb d mq)O(p\,n_b\,d\,m_q). We note in the conclusion that large sum-of-products representations can therefore remain expensive.

W5 and Q5. Choosing the tolerance. The output scale provides context for ϵ\epsilon, but the accuracy needed depends on the explanation. In particular, two features may have nearly equal Shapley values at any output scale. Distinguishing them requires a tighter tolerance, which may increase the node count. The domain expert chooses the accuracy appropriate for the intended use.

In addition, a practitioner can choose a positive reference scale AA on the odds or relative-hazard scale and set ϵ=Aη\epsilon=A\eta using the existing absolute-tolerance input. In exact arithmetic, the quadrature error of each attribution, divided by AA, is then at most η\eta:

∣ϕ^i−ϕi∣A≤η.\frac{|\widehat{\phi}_i-\phi_i|}{A}\leq\eta.

This remains meaningful when an individual Shapley value is zero or close to zero.

When the aim is to preserve a ranking, the relevant gaps are unknown before the Shapley values are computed. We therefore check the ranking after evaluation. An estimated gap greater than 2ϵ2\epsilon certifies the order of a pair under a common error bound ϵ\epsilon. We tighten ϵ\epsilon and recompute when a comparison remains unresolved. Appendix C.4 gives the sharper test using per-feature bounds and the refinement procedure, which we now reference in Section 3.2.

W6 and Q4 (second part). The 1.37×1.37\times advantage was an error: with the displayed values, 1.6311.631 ms against 1.5441.544 ms, the advantage is approximately 1.06×1.06\times, and G.5.2 now states this.

The opening of Section 5 now summarizes the appendix comparisons with their qualifications: against KernelSHAP and SamplingSHAP at 1,000 samples, QuadraSHAP’s error is approximately 10−710^{-7}, whereas theirs is 10–84% of the largest attribution (float32 GPU, Appendix G.4). On tree ensembles, it matches Linear TreeSHAP’s CPU speed while remaining stable at depth 100, where the tested competitors fail (Appendix G.5). The precision of the experiments is stated at the start of Section 5, and the hardware is specified with each table. The efficiency residual in G.5.1 is now presented as a consistency check, with coordinate-level agreement reported in G.5.2, as discussed under W2.

We hope these clarifications and additional results address the reviewer’s concerns and help inform their reassessment of the paper.

Dear Reviewer ai1j,

Thank you again for your thorough review and constructive feedback. As the discussion period closes soon, we wonder if we have sufficiently addressed the comments. We would be happy to clarify any remaining points.

Reviewer_AqVnOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The main contribution of this work is to give an ϵ\epsilon-exact computational procedure for the Shapley value on product games (based on the Gauss-Legendre quadrature that is used in the exact form before in Li et al., ICLR'26), of which decision trees and several other ML models are a special case. Numerical issues and parallelization are discussed. Experiments across a variety of datasets and models confirm the significant practical advantage of the proposed implementation.

Critical strengths
  • mostly very well written and easy to follow

  • a practical way to (significantly) speed up the Shapley value computation on product games, especially when the required accuracy is not too low

Critical weaknesses
  • If I had to pick, the one weakness I see is the main result, essentially Proposition 3, is not too difficult to obtain. The rest of the pieces are nicely put together by the authors, although without much significant novelty in their own right. Having said that, I am convinced by the practical usefulness and consider this work a valuable contribution to the community.
Questions for authors

My main comment is how useful it is to obtain fairly accurate numbers of the Shapley value? For most applications that one may care about, is it really important what the Shapley numbers are or is it sufficient to obtain some kind of ranking of the features? Of course, as a computational procedure, the proposed implementation has value in its own right. I guess what I am really asking is how much time can one (additionally) save if we are only interested in obtaining a ranking (say by successively increasing epsilon until the ranking changes significantly)? In this setting, is it possible for some Monte Carlo based approximation to win?

Some minor comments:

  • in line 075, the authors mentioned Li et al. and Wettenstein et al. as concurrent work. I note that Li et al. already appeared in ICLR'26. Should it still be counted as concurrent or maybe this is a resubmission? It also appears to me that this work and Wettenstein et al. seem to complement each other.

  • line 298-303, some subscripts seem to be mis-typeset.

2 comments

We thank the reviewer for the positive assessment and for raising the question of feature rankings. Our responses to the concerns are provided below.

1. Contribution. Proposition 2 uses the standard Gauss–Legendre error bound. Proposition 3 turns this bound into a sufficient node budget computed directly from the factors of the product game. Specifically, the Bernstein-ellipse bound in Proposition 2 depends on the maximum of a polynomial of degree d−1d-1 over an ellipse, a quantity that is not readily available. Using Lemma 1, Appendix C.1 bounds this maximum through two quantities computed from the factor table in O(d)O(d) time: the absolute scale ∣ui−1∣Πi|u_i-1|\Pi_i and the total relative variation Λi\Lambda_i. The bound holds for every admissible ellipse parameter, which we optimize by solving a scalar equation. This yields a node budget for a prescribed accuracy before quadrature evaluation. Appendix C presents the full procedure, including its extension to weighted sums of product games. This factor-based budget for general product games distinguishes our contribution from the cited tree quadrature methods and has a significant practical impact: we can compute ϵ\epsilon-exact Shapley values for problems with tens of thousands of features in a fraction of a second. Identifying product structure in different value functions of several well-known models also extends the applicability of QuadraSHAP to several models in practice.

2. Ranking and Monte Carlo. We agree that a ranking suffices for many applications. In exact arithmetic, each Shapley estimate computed with a certified tolerance ϵ\epsilon differs from its exact value by at most ϵ\epsilon. An estimated gap greater than 2ϵ2\epsilon therefore certifies the order of two features. For a full ranking, we sort the estimates and check adjacent gaps. For top-kk membership, we check the gap at the cutoff. The same test applies to rankings by absolute attribution magnitude.

We start with a small number of quadrature nodes and double the node count whenever a relevant estimated gap is at most twice the current common certified error bound. We stop when the relevant comparisons are certified, the exactness threshold ⌈d/2⌉\lceil d/2\rceil is reached, or a prescribed positive tolerance floor is reached.

This adaptive refinement preserves the asymptotic quadrature complexity. Starting with m0m_0 nodes, the cumulative cost over ss iterations is

O\left(d\,m_0\sum_{r=0}^{s-1}2^r\right) &= O\left(d\,m_0(2^s-1)\right) \\\ &= O(d\,m_{\mathrm{final}}), \end{aligned}$$ where $m_{\mathrm{final}}$ is the number of quadrature nodes in the final iteration. Thus, the cumulative quadrature cost is bounded by a constant multiple of the cost of a single evaluation with $m_{\mathrm{final}}$ nodes. This bound also holds when the final node count is capped at the exactness threshold. Moreover, since exactness is guaranteed at $\lceil d/2\rceil$ nodes, at most $O(\log d)$ refinement iterations are required for a fixed initial node count, yielding a worst-case quadrature complexity of $O(d^2)$. Thus, this iterative procedure preserves the asymptotic quadrature complexity. We discuss the procedure in Section 3.2 and have added its full description and complexity analysis in Appendix C.4. Sampling methods, including Monte Carlo methods, can efficiently identify leading features or estimate rankings. However, they can also be time-consuming at large scale. In our product-kernel experiments, QuadraSHAP was faster than the tested configurations of KernelSHAP and SamplingSHAP at 1,000 samples, while producing more accurate attributions (Appendix G.4). Thus, for these models, computing all Shapley values to a certified quadrature tolerance is already fast, even when the application ultimately uses only a ranking. **3. Related work.** We will reserve *concurrent* for Quadrature-TreeSHAP, which appeared at the same time as our work, and cite TreeGrad-Shap as related work that appeared during our independent development of QuadraSHAP. See the Introduction section. **4. Typesetting.** We thank the reviewer for the careful reading. We corrected the subscript formatting in lines 298–303. We hope our responses and the revisions to the manuscript resolve the reviewer’s concerns and support their reassessment of the paper.

Dear Reviewer AqVn,

Thank you again for your review. As the discussion period closes on November 18, we wanted to kindly check whether our response has addressed your concerns. We would be happy to clarify any remaining points.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.