cs.LGApr 9, 2026

Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond

Authors: Weida Li, Yaoliang Yu, Bryan Kian Hsiang Low

Organizations: Department of Computer Science, National University of Singapore, Republic of Singapore · School of Computer Science, University of Waterloo, Canada · Vector Institute, Canada

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

The Shapley value, and its broader family of semi-values, has received much attention in various attribution problems. A fundamental and long-standing challenge is their efficient approximation, since exact computation generally requires an exponential number of utility queries in the number of players nn. To meet the challenges of large-scale applications, we explore the limits of efficiently approximating semi-values under a Θ(n)Θ(n) space constraint. Building upon a vector concentration inequality, we establish a theoretical framework that enables sharper query complexities for existing unbiased randomized algorithms. Within this framework, we systematically develop a linear-space algorithm that requires O(nε2log⁡1δ)O(\frac{n}{ε^{2}}\log\frac{1}δ) utility queries to ensure P(∥φ^−φ∥2≥ε)≤δP(\|\hat{\boldsymbolφ}-\boldsymbolφ\|_{2}\geqε)\leq δ for all commonly used semi-values. In particular, our framework naturally bridges OFA, unbiased kernelSHAP, SHAP-IQ and the regression-adjusted approach, and definitively characterizes when paired sampling is beneficial. Moreover, our algorithm allows explicit minimization of the mean squared error E[∥φ^−φ∥22]\mathbb{E}[\|\hat{\boldsymbolφ}-\boldsymbolφ\|_{2}^{2}] for each specific utility function. Accordingly, we introduce the first adaptive, linear-time, linear-space randomized algorithm, Adalina, that theoretically achieves improved mean squared error. All of our theoretical findings are experimentally validated. Our code is available at https://github.com/watml/adalina.

Figures & tables

Figure 1: The relative approximation error of unbiased kernelSHAP in approximating the Shapley value with different sampling distributions. Here, λ=u[n]−u∅n\lambda=\frac{u_{[n]}-u_{\emptyset}}{n} . The dashed lines correspond to those with paired sampling, whereas the solid lines are without paired sampling. For the first row, the utility function there is positive, whereas for the second row, U(S)U(S) can be either positive or negative.
Figure 2: The relative approximation error of ϕ^γ\hat{\boldsymbol{\phi}}^{\gamma} in approximating the Shapley value as γ\gamma varies.
Figure 3: The relative approximation error of SHAP-IQ, ϕ^γ\hat{\boldsymbol{\phi}}^{\gamma} and its adaptive variant. The adaptive method corresponds to Adalina, presented in Algorithm 1 , which adaptively estimates the optimal γ\gamma . Weighted Banzhaf values are parameterized by w∈(0,1)w\in(0,1) , whereas Beta Shapley values are parameterized by (α,β)(\alpha,\beta) , with (1,1)(1,1) corresponding to the Shapley value.
Figure 4: The relative approximation error of different randomized algorithms. Weighted Banzhaf values are parameterized by w∈(0,1)w\in(0,1) , whereas Beta Shapley values are parameterized by (α,β)(\alpha,\beta) , with (1,1)(1,1) corresponding to the Shapley value.
Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset#Instances#FeaturesSourceTask#ClassesDepth
FOTP6,1186,1185151https://openml.org/d/1475classification662020
GPSP9,8739,8733232https://openml.org/d/4538classification551010
MinibooNE130,064130,0645050https://openml.org/d/41150classification222020
philippine5,8325,832308308https://openml.org/d/41145classification221515
spambase4,6014,6015757https://openml.org/d/44classification221515
jannis83,73383,7335454https://openml.org/d/41168classification44040
Appendix
Table 1: Summary of the datasets used.
Figure 5: The relative approximation error of different randomized algorithms. Weighted Banzhaf values are parameterized by w∈(0,1)w\in(0,1) , whereas Beta Shapley values are parameterized by (α,β)(\alpha,\beta) , with (1,1)(1,1) corresponding to the Shapley value.
Figure 6: The relative approximation error of different randomized algorithms. Weighted Banzhaf values are parameterized by w∈(0,1)w\in(0,1) , whereas Beta Shapley values are parameterized by (α,β)(\alpha,\beta) , with (1,1)(1,1) corresponding to the Shapley value.
Figure 7: The relative approximation error of different randomized algorithms. Weighted Banzhaf values are parameterized by w∈(0,1)w\in(0,1) , whereas Beta Shapley values are parameterized by (α,β)(\alpha,\beta) , with (1,1)(1,1) corresponding to the Shapley value.
More in this topic

Shapley Value Attribution

Shapley value attribution fairly assigns a prediction or outcome among contributing features, data points, agents, or modalities.

See all 102 papers

Explore similar work

CardsList
Oct 2, 2024

Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Originally introduced in game theory, Shapley values have emerged as a central tool in explainable machine learning, where they are used to attribute model predictions to specific input features. However, computing Shapley values exactly is expensive: for a general model with nn features, O(2n)O(2^n) model evaluations are necessary. To address this issue, approximation algorithms are widely used. One of the most popular is the Kernel SHAP algorithm, which is model agnostic and remarkably effective in practice. At the time of our original submission, no strong non-asymptotic complexity guarantees were known for Kernel SHAP. We address this issue by introducing Leverage SHAP, a lightweight modification of Kernel SHAP that provides provably accurate Shapley value estimates with just O(nlog⁡n)O(n\log n) model evaluations. Our approach takes advantage of a connection between Shapley value estimation and agnostic active learning by employing leverage score sampling, a powerful regression tool. Beyond theoretical guarantees, we find that Leverage SHAP achieves an approximately 50%50\% reduction in error compared to the highly optimized implementation of Kernel SHAP in the widely used SHAP library [Lundberg & Lee, 2017].

Christopher Musco, R. Teal Witter

New York University

SHAP Feature AttributionShapley Value Attribution
AskPDF
Jun 1, 2026

ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation

Shapley values are a principled attribution measure widely used in interpretable machine learning, but their exact computation scales exponentially with the number of players, motivating a wide range of approximation methods based on value function evaluations of sampled coalitions. This raises the question of whether approximation accuracy can be improved by adaptively selecting coalitions for evaluation based on previous evaluations. This is particularly relevant in settings where the value function is costly and the number of evaluations is severely limited, such as retraining-based feature importance, data valuation, and hyperparameter importance. For this purpose, we propose ShaplEIG, a Bayesian experimental design approach that approximates the expensive value function using a Gaussian process surrogate and adaptively selects coalitions based on their expected information gain about the Shapley values. By the linearity of the Shapley values in the value function, we show that the expected information gain is available in closed form. Furthermore, we propose an efficient computation scheme that reduces the complexity from exponential to polynomial in the number of players via elementary symmetric polynomials. In extensive experiments across diverse costly applications, our method consistently improves sample efficiency in the low-budget regime over state-of-the-art baselines.

David Rundel, Fabian Fumagalli, Maximilian Muschalik +2

Department of Statistics, LMU Munich, Munich, Germany · Munich Center for Machine Learning, Munich, Germany · Institute for Informatics, LMU Munich, Munich, Germany +2

Shapley Value AttributionAdaptive SamplingBayesian Experimental Design
AskPDF
Jun 13, 2025

Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values

With origins in game theory, probabilistic values like Shapley values, Banzhaf values, and semi-values have emerged as a central tool in explainable AI. They are used for feature attribution, data attribution, data valuation, and more. Since exact computation can require exponential time, research has focused on efficient approximation methods using two techniques: Monte Carlo sampling and linear regression formulations. In this work, we present a new way of combining both of these techniques. Our approach is more flexible than prior algorithms, allowing for linear regression to be replaced with any function family whose probabilistic values can be computed efficiently. This allows us to harness the accuracy of tree-based models like XGBoost; with cross-fitting, the method also produces unbiased estimates. From experiments across eight datasets, we find that our methods give state-of-the-art performance for estimating probabilistic values. For Shapley values, the error of our methods can be 11×11\times lower than Permutation SHAP (the most popular Monte Carlo method), 6.5×6.5\times lower than Kernel SHAP (the most popular linear regression method), and 3.4×3.4\times lower than Leverage SHAP (the prior state-of-the-art Shapley value estimator). For more general probabilistic values, we can obtain error 390×390\times lower than the best estimator from prior work.

R. Teal Witter, Yurong Liu, Christopher Musco

Claremont McKenna College · New York University

Shapley Value AttributionValue Function Estimation
AskPDF