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

Abstract

We introduce QuadraSHAP, a method for $\epsilon$-exact Shapley computation in product games, cooperative games whose coalition values factorize across players. Given a tolerance $\epsilon\ge0$, the method determines a computational budget before evaluation, guaranteeing an absolute attribution error of at most $\epsilon$ 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 $d$-player product game, we replace the exponentially large coalition sum by a one-dimensional integral of a polynomial of degree at most $d-1$. Gauss--Legendre quadrature with $m_q=\lceil d/2\rceil$ nodes therefore recovers exact Shapley values when $\epsilon=0$. For positive tolerances, a computable error bound derived from the game factors decays geometrically with the node count and can certify substantially smaller budgets. To support efficient evaluation at scale, we share computations across features and evaluate products in log-space with sign tracking, mitigating intermediate overflow and underflow. Given the quadrature rule, computing all $d$ attributions requires $O(d\,m_q)$ work per product game, and admits $O(\log d)$ parallel time with sufficient processors. On a survival analysis problem with $396{,}065$ 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 $\epsilon=10^{-6}$ selects a smaller, theoretically certified quadrature budget and reduces the mean evaluation time to $0.36$ seconds per explanation.