pith. sign in

arxiv: 2605.05870 · v2 · pith:53IQTEZNnew · submitted 2026-05-07 · 💻 cs.LG

QuadraSHAP: Stable and Scalable Shapley Values for Product Games via Gauss-Legendre Quadrature

Majid Mohammadi , Grigory Reznikov , Pavel Sinitcyn , Krikamol Muandet , Siu Lun Chau This is my paper

Pith reviewed 2026-05-20 22:39 UTC · model grok-4.3

classification 💻 cs.LG
keywords Shapley valuesproduct gamesGauss-Legendre quadratureexplainable AIcooperative game theorynumerical integrationkernel methodstree models
0
0 comments X

The pith

Shapley values for product games reduce exactly to the integral of a degree-(d-1) polynomial over [0,1].

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that when a cooperative game's value function factors as a product of individual player contributions, the usual exponential sum over all possible coalitions simplifies to a single one-dimensional integral. A sympathetic reader would care because this removes the main computational barrier that makes exact Shapley explanations infeasible for models with thousands of features. The resulting quadrature rule is provably exact once the number of nodes reaches roughly half the feature count and otherwise converges geometrically fast. The method also supplies a numerically stable log-space implementation and an associative-scan parallel algorithm that runs in linear work and logarithmic depth. Experiments confirm the approach is faster than prior stable methods across kernel and tree models while retaining high accuracy.

Core claim

The Shapley value of each player in a product game admits an exact one-dimensional integral representation: the weighted sum over exponentially many feature coalitions collapses to the integral of a degree-(d-1) polynomial over [0,1], where d is the total number of features. This yields a Gauss-Legendre quadrature scheme that is provably exact whenever the number of nodes satisfies m_q ≥ ⌈d/2⌉, and otherwise provides a near-exact approximation with error provably decaying geometrically in m_q. In practice, a few hundred nodes can achieve highly precise estimates even with thousands of features. Building on this formulation, the authors derive a numerically stable implementation via log-space

What carries the argument

The one-dimensional integral representation that converts the exponential coalition sum into Gauss-Legendre quadrature of a polynomial of degree d-1 over the unit interval.

If this is right

  • The exponential 2^d enumeration is replaced by O(d m_q) arithmetic operations.
  • Log-space evaluation keeps the procedure numerically stable for large d.
  • Associative-scan primitives yield O(log d) parallel depth on modern hardware.
  • A few hundred quadrature nodes suffice for high accuracy even when d reaches thousands.
  • The same scheme applies directly to product kernels and tree-based models used in practice.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The geometric convergence rate could make quadrature preferable to Monte-Carlo sampling even when the game is only approximately multiplicative.
  • The integral view might be combined with gradient-based methods to obtain Shapley values for differentiable models without explicit product structure.
  • Because the polynomial degree depends only on d, the same quadrature grid can be reused across many queries once d is fixed.

Load-bearing premise

The value function must factorize exactly as a product of per-player terms.

What would settle it

Compute the exact Shapley values by full enumeration on a small product game with known closed form, then check whether the quadrature formula with m_q = ⌈d/2⌉ nodes reproduces those values to machine precision.

Figures

Figures reproduced from arXiv: 2605.05870 by Grigory Reznikov, Krikamol Muandet, Majid Mohammadi, Pavel Sinitcyn, Siu Lun Chau.

Figure 1
Figure 1. Figure 1: Scope of QuadraSHAP. Left: two settings, tree-based models and product kernels, where Shapley values reduce to weighted sums of product games. Right: qualitative comparison of the methods on complexity and stability. product per feature, we compute the full product once and divide out the corresponding factor for each i. This sharing reduces the total work from O(d 2mq) to O(d mq). To avoid overflow and un… view at source ↗
Figure 2
Figure 2. Figure 2: Mean ℓ2 error of QuadraSHAP against the exact Shapley vector versus quadrature budget mq (KRR with RBF kernel; bands: ±1σ over ten test points; dashed line: exactness threshold). Error decays geometrically, reaching near-machine precision within a few hundred nodes at all scales. with the empty product equal to 1. The contribution of leaf ℓ under coalition S is then νℓ Y e∈Eℓ pe Y j∈S qj,ℓ(x)  , giving v… view at source ↗
read the original abstract

We study the efficient computation of Shapley values for \emph{product games} -- cooperative games in which the coalition value factorizes as a product of per-player terms. Such games arise in machine learning explainability whenever the value function inherits a multiplicative structure from the underlying model, as in kernel methods with product kernels and tree-based models. Our key result is that the Shapley value of each player in a product game admits an exact one-dimensional integral representation: the weighted sum over exponentially many feature coalitions collapses to the integral of a degree-$(d-1)$ polynomial over $[0,1]$, where $d$ is the total number of features. This yields a Gauss--Legendre quadrature scheme that is \emph{provably exact} whenever the number of nodes satisfies $m_q \geq \lceil d/2 \rceil$, and otherwise provides a \emph{near-exact} approximation with error provably decaying geometrically in $m_q$. In practice, a few hundred nodes can achieve highly precise estimates even with thousands of features. Building on this formulation, we derive a numerically stable implementation via log-space evaluation, together with an efficient parallel implementation based on associative scan primitives that achieves $O(d\,m_q)$ total work and $O(\log d)$ parallel time. Experiments show that \textsc{QuadraSHAP} is the fastest numerically stable method across all tested configurations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces QuadraSHAP for efficient computation of Shapley values in product games, where the coalition value factorizes as a product of per-player terms. It derives that each player's Shapley value reduces exactly to a one-dimensional integral over [0,1] of a degree-(d-1) polynomial, enabling a Gauss-Legendre quadrature scheme that is provably exact for m_q >= ceil(d/2) nodes and otherwise yields near-exact approximations with geometric error decay. The work includes a numerically stable log-space implementation and an associative-scan parallelization achieving O(d m_q) work and O(log d) parallel time, with experiments claiming superior speed and stability for kernel and tree models.

Significance. If the central reduction holds, this provides a meaningful advance for scalable, stable SHAP explanations in models with exact multiplicative structure. The explicit use of the beta-integral representation to recover combinatorial weights, combined with classical exactness guarantees from quadrature theory for polynomials, is a clear strength; the parallel scan implementation further supports practical deployment in high-d regimes.

minor comments (3)
  1. Abstract: the statement that 'a few hundred nodes can achieve highly precise estimates even with thousands of features' would benefit from a supporting table or explicit scaling relation between m_q and d to make the claim quantitative.
  2. Implementation section: the description of the associative scan for O(log d) parallel time is promising but lacks pseudocode or a small worked example; adding either would improve reproducibility.
  3. Notation: ensure that the symbol d (total features) is introduced once and used consistently; occasional shifts to n or other variables appear in the provided abstract and should be unified.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work on QuadraSHAP, as well as the recommendation for minor revision. We appreciate the recognition of the integral reduction, quadrature guarantees, and parallel implementation as strengths.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The central claim reduces the Shapley sum for product games to a one-dimensional integral of a degree-(d-1) polynomial via the beta integral representation of binomial coefficients and the exact factorization v(S) = prod a_j * prod b_j. This is a direct algebraic identity followed by the classical Gauss-Legendre quadrature rule for polynomials, both of which are external to the paper and require no fitted parameters, self-citations, or renaming of results. The paper's implementation details (log-space evaluation, parallel scan) are algorithmic consequences rather than load-bearing premises. No step in the provided derivation chain collapses to a self-definition or fitted input called a prediction.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The approach rests on standard properties of Shapley values and Gauss-Legendre quadrature; no new entities are postulated and the only tunable quantity is the number of quadrature nodes chosen for desired accuracy.

free parameters (1)
  • number of quadrature nodes m_q
    Selected to achieve exactness or target error; not fitted to data but determined by the polynomial degree d.
axioms (2)
  • standard math Shapley values are defined by the standard four axioms of cooperative games
    Invoked to establish that the values being computed satisfy the usual fairness properties.
  • standard math Gauss-Legendre quadrature integrates polynomials of degree less than 2m exactly
    Directly supports the claim of exactness when m_q >= ceil(d/2).

pith-pipeline@v0.9.0 · 5809 in / 1421 out tokens · 38489 ms · 2026-05-20T22:39:47.325177+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    , booktitle =

    Shapley, Lloyd S. , booktitle =. A Value for n-Person Games , year =

    work page

  2. [2]

    and Lee, Su-In , booktitle =

    Lundberg, Scott M. and Lee, Su-In , booktitle =. A Unified Approach to Interpreting Model Predictions , year =

    work page

  3. [3]

    and Erion, Gabriel and Chen, Hugh and DeGrave, Alex and Prutkin, Jordan M

    Lundberg, Scott M. and Erion, Gabriel and Chen, Hugh and DeGrave, Alex and Prutkin, Jordan M. and Nair, Bala and Katz, Ronit and Himmelfarb, Jonathan and Bansal, Nisha and Lee, Su-In , journal =. From Local Explanations to Global Understanding with Explainable AI for Trees , year =

    work page

  4. [4]

    Linear TreeSHAP , year =

    Yu, Peng and Xu, Chao and Bifet, Albert and Read, Jesse , booktitle =. Linear TreeSHAP , year =

    work page

  5. [5]

    Fast Calculation of Feature Contributions in Boosting Trees , year =

    Jiang, Zhongli and Zhang, Min and Zhang, Dabao , booktitle =. Fast Calculation of Feature Contributions in Boosting Trees , year =

    work page

  6. [6]

    , institution =

    Blelloch, Guy E. , institution =. Prefix Sums and Their Applications , year =

    work page

  7. [7]

    Cooperative product games , volume =

    Dehez, Pierre , journal =. Cooperative product games , volume =

    work page

  8. [8]

    The Explanation Game: Explaining Machine Learning Models Using Shapley Values , year =

    Merrick, Luke and Taly, Ankur , journal =. The Explanation Game: Explaining Machine Learning Models Using Shapley Values , year =

    work page

  9. [9]

    Exact shapley attributions in quadratic-time for fanova gaussian processes , volume =

    Mohammadi, Majid and Muandet, Krikamol and Tiddi, Ilaria and Ten Teije, Annette and Chau, Siu Lun , booktitle =. Exact shapley attributions in quadratic-time for fanova gaussian processes , volume =

    work page

  10. [10]

    Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics , title =

    Janzing, Dominik and Minorics, Lenon and Bl. Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics , title =

    work page

  11. [11]

    Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models , volume =

    Heskes, Tom and Sijben, Enzo and Bucur, Ioana and Claassen, Tom , journal =. Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models , volume =

    work page

  12. [12]

    and Erion, Gabriel G

    Chen, Hugh and Lundberg, Scott M. and Erion, Gabriel G. and Lee, Su-In , journal =. True to the Model or True to the Data? , year =

    work page

  13. [13]

    The Many Shapley Values for Model Explanation , year =

    Sundararajan, Mukund and Najmi, Amir , journal =. The Many Shapley Values for Model Explanation , year =

    work page

  14. [14]

    Interpretable Machine Learning , url =

    Molnar, Christoph , publisher =. Interpretable Machine Learning , url =. 2022 , bdsk-url-1 =

    work page 2022

  15. [15]

    Kernel Mean Embedding of Distributions: A Review and Beyond , year =

    Muandet, Krikamol and Fukumizu, Kenji and Sriperumbudur, Bharath and Sch. Kernel Mean Embedding of Distributions: A Review and Beyond , year =

    work page

  16. [16]

    Why Should I Trust You?: Explaining the Predictions of Any Classifier , year =

    Ribeiro, Marco Tulio and Singh, Sameer and Guestrin, Carlos , booktitle =. Why Should I Trust You?: Explaining the Predictions of Any Classifier , year =

    work page

  17. [17]

    shapiq: Shapley interactions for machine learning , volume =

    Muschalik, Maximilian and Baniecki, Hubert and Fumagalli, Fabian and Kolpaczki, Patrick and Hammer, Barbara and H. shapiq: Shapley interactions for machine learning , volume =. Advances in Neural Information Processing Systems , pages =

    work page

  18. [18]

    PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression , year =

    Fumagalli, Fabian and Witter, R Teal and Musco, Christopher , journal =. PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression , year =

    work page

  19. [19]

    Explaining the uncertain: Stochastic shapley values for gaussian process models , volume =

    Chau, Siu Lun and Muandet, Krikamol and Sejdinovic, Dino , journal =. Explaining the uncertain: Stochastic shapley values for gaussian process models , volume =

    work page

  20. [20]

    RKHS-SHAP: Shapley values for kernel methods , volume =

    Chau, Siu Lun and Hu, Robert and Gonzalez, Javier and Sejdinovic, Dino , journal =. RKHS-SHAP: Shapley values for kernel methods , volume =

    work page

  21. [21]

    Computing exact shapley values in polynomial time for product-kernel methods , year =

    Mohammadi, Majid and Chau, Siu Lun and Muandet, Krikamol , journal =. Computing exact shapley values in polynomial time for product-kernel methods , year =

    work page

  22. [22]

    Fast TreeSHAP: Accelerating SHAP Value Computation for Trees , year =

    Yang, Jilei , journal =. Fast TreeSHAP: Accelerating SHAP Value Computation for Trees , year =

    work page

  23. [23]

    Linear TreeSHAP: reference implementation , year =

    Yu, Peng and Xu, Chao and Bifet, Albert and Read, Jesse , howpublished =. Linear TreeSHAP: reference implementation , year =

    work page

  24. [24]

    Multilinear extensions of games , volume =

    Owen, Guillermo , journal =. Multilinear extensions of games , volume =

    work page

  25. [25]

    and Welsch, John H

    Golub, Gene H. and Welsch, John H. , journal =. Calculation of

    work page

  26. [26]

    , journal =

    Trefethen, Lloyd N. , journal =. Is

    work page

  27. [27]

    and Rabinowitz, Philip , edition =

    Davis, Philip J. and Rabinowitz, Philip , edition =. Methods of Numerical Integration , year =

    work page

  28. [28]

    , journal =

    Weber, Robert J. , journal =. Probabilistic values for games , year =

    work page

  29. [29]

    Unifying attribution-based explanations using functional decomposition , year =

    Gevaert, Arne and Saeys, Yvan , journal =. Unifying attribution-based explanations using functional decomposition , year =

    work page

  30. [30]

    , journal =

    Brent, Richard P. , journal =. The Parallel Evaluation of General Arithmetic Expressions , volume =

    work page

  31. [31]

    , publisher =

    Trefethen, Lloyd N. , publisher =. Approximation Theory and Approximation Practice , year =

    work page

  32. [32]

    PeerJ Computer Science , volume=

    GPUTreeShap: massively parallel exact calculation of SHAP scores for tree ensembles , author=. PeerJ Computer Science , volume=. 2022 , publisher=

    work page 2022

  33. [33]

    doi: 10.18653/v1/D18-1404

    Saravia, Elvis and Liu, Hsien-Chi Toby and Huang, Yen-Hao and Wu, Junlin and Chen, Yi-Shin. CARER : Contextualized Affect Representations for Emotion Recognition. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing. 2018. doi:10.18653/v1/D18-1404

    work page doi:10.18653/v1/d18-1404 2018

  34. [34]

    and Daly, Raymond E

    Maas, Andrew L. and Daly, Raymond E. and Pham, Peter T. and Huang, Dan and Ng, Andrew Y. and Potts, Christopher , title =. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies , month =. 2011 , address =

    work page 2011

  35. [35]

    Proceedings of the 11th ACM symposium on Document engineering , pages=

    Contributions to the study of SMS spam filtering: new collection and results , author=. Proceedings of the 11th ACM symposium on Document engineering , pages=

    work page

  36. [36]

    Wang, Alex and Singh, Amanpreet and Michael, Julian and Hill, Felix and Levy, Omer and Bowman, Samuel R. , note=

    work page

  37. [37]

    Bo Pang and Lillian Lee , title =

    work page

  38. [38]

    Li, Weida and Yu, Yaoliang and Low, Bryan Kian Hsiang , booktitle =

    work page