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

arXiv:2605.05870v2 Announce Type: replace Abstract: We study the efficient computation of Shapley values for 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 provably exact whenever the number of nodes satisfies m_q geq lceil d/2 rceil, 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, 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 extsc{QuadraSHAP} is the fastest numerically stable method across all tested configurations.

Source: arXiv cs.LG | 2026-05-19