Skip to content

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

May 2026 · 0 citations
Computer Science

TL;DR

QuadraSHAP is introduced, a method for $\epsilon$-exact Shapley computation in product games, cooperative games whose coalition values factorize across players, and extends to weighted sums of product games, supporting baseline and empirical interventional attribution across a broad class of models.

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.

View source

Similar papers

#artificial intelligence Preprint Jul 2024

The Llama 3 Herd of Models

It is found that Llama 3 delivers comparable quality to leading language models such as GPT-4 on a plethora of tasks, and performs competitively with the state-of-the-art on image, video, and speech recognition tasks.

Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri et al. · 21,082 citations · ⚡3,832
#artificial intelligence Conference Open access Jun 2018

Gibson Env: Real-World Perception for Embodied Agents

This paper investigates developing real-world perception for active agents, proposes Gibson Environment for this purpose, and showcases a set of perceptual tasks learned therein.

F. Xia, Amir Zamir, Zhi-Yang He et al. · 1,069 citations · ⚡112
#machine learning Review Open access Oct 2014

Software development in startup companies: A systematic mapping study

The results indicate that software engineering work practices are chosen opportunistically, adapted and configured to provide value under the constrains imposed by the startup context.

Nicolò Paternoster, Carmine Giardino, M. Unterkalmsteiner et al. · 394 citations · ⚡54

Diffusion models as plug-and-play priors

The possibility of inferring high-dimensional data inference in a model that consists of a prior and an auxiliary differentiable constraint given some additional information is considered, thereby allowing a range of potential applications in adapting models to new domains and tasks.

Alexandros Graikos, Esmeralda S. Whitammer, N. Jojic et al. · 316 citations · ⚡15

Trajectory Balance: Improved Credit Assignment in GFlowNets

It is proved that any global minimizer of the trajectory balance objective can define a policy that samples exactly from the target distribution, and empirically demonstrate the benefits of the trajectories balance objective for GFlowNet convergence, diversity of generated samples, and robustness to long action sequenc...

Esmeralda S. Whitammer, Moksh Jain, Emmanuel Bengio et al. · 302 citations · ⚡60

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.