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

We introduce QuadraSHAP, a method for $ϵ$-exact Shapley computation in product games, cooperative games whose coalition values factorize multiplicatively across players. Given a tolerance $ϵ\ge 0$, 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 $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 $ϵ=0$. For given positive tolerances, we derive a computable, factor-dependent error bound that decays geometrically in $m_q$ 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 $d$ attributions requires $O(d{m}_q)$ work per product game, compared with $O(2^d)$ for direct coalition summation, 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 $ϵ=10^{-6}$ selects a smaller, theoretically certified quadrature budget and reduces the mean evaluation time to $0.36$ 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.