Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Christopher Musco; R. Teal Witter

cs.LGOct 2, 2024

Provably Accurate Shapley Value Estimation via Leverage Score Sampling

Authors: Christopher Musco, R. Teal Witter

Organizations: New York University

Abstract

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 $n$ features, $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(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\%$ reduction in error compared to the highly optimized implementation of Kernel SHAP in the widely used SHAP library [Lundberg & Lee, 2017].

Figures & tables

Figure 1: Predicted versus true Shapley values for all features in 8 datasets (we use

m=5n

samples for this experiment). Points near the identity line indicate that the estimated Shapley value is close to its true value. The plots suggest that our Leverage SHAP method is more accurate than the baseline Kernel SHAP algorithm, as well as the optimized Kernel SHAP implementation available in the SHAP library. We corroborate these findings with more experiments in Section 5 .

Figure 2: Let

S

be a subset sampled with the Kernel SHAP or Leverage SHAP probabilities. The plots show the distribution of the set size

|S|

for different

n

. As in in the definition of Shapley values, the leverage score distribution places equal total weight on each subset size, contrasting with Kernel SHAP which over-weights small and large subsets.

\tilde{\bm{\phi}}^{\perp}\leftarrow\argmin_{\mathbf{x}}\|\mathbf{W}^{\frac{1}{2}}\mathbf{Z^{\prime}}\mathbf{Px}-\mathbf{W}^{\frac{1}{2}}\mathbf{b^{\prime}}\|_{2}^{2}

Algorithm 1 Leverage SHAP

Figure 3: The relative squared

\ell_{2}

error between the estimated Shapley values and ground truth Shapley values as a function of sample size. The lines report the median error while the shaded regions encompass the first to third quartile over 100 runs. Besides the setting where the exact Shapley values can be recovered, Leverage SHAP reliably outperforms even Optimized Kernel SHAP: on Correlated and Independent, the third quartile of the Leverage SHAP error is roughly the median error of Optimized Kernel SHAP; on NHANES and Communities it is at most about

1.5

times the median; and on the small-

n

datasets it is below the median.

	IRIS	California	Diabetes	Adult	Correlated	Independent	NHANES	Communities
Kernel SHAP
Mean	0.0326	0.03	0.0592	0.0596	0.0471	0.0269	0.0542	0.118
1st Quartile	1.03e-05	0.00689	0.0123	0.0196	0.0264	0.0142	0.0175	0.0578
2nd Quartile	0.000259	0.0177	0.0237	0.0412	0.0405	0.0207	0.038	0.0876
3rd Quartile	0.034	0.0417	0.0545	0.0844	0.0556	0.0315	0.0789	0.139
Optimized Kernel SHAP

Table 1: Summary statistics of the relative squared

\ell_{2}

error for every dataset. We adopt the Olympic medal convention: gold , silver and bronze cells signify first, second and third best performance, respectively. Except for ties, Leverage SHAP gives the best performance across all settings.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: The relative squared

\ell_{2}

error between the estimated and ground truth Shapley values as a function of noise in the set function. Leverage SHAP gives the best performance at low and moderate noise (

\sigma\leq 0.1

) on every dataset, and at every noise level on Diabetes, Correlated, Independent, and Communities. At the highest noise levels (

\sigma\geq 0.5

), where the noise dominates the error, Leverage SHAP and Optimized Kernel SHAP are close, and Optimized Kernel SHAP pulls slightly ahead in some settings on California, Adult, and NHANES. On IRIS, where

m\geq 2^{n}

, the noise alone determines the error.

Dataset	$5n$	$10n$	$20n$	$40n$	$80n$	$160n$
IRIS	1.00	1.00	1.00	1.00	1.00	1.00
California	0.0894	0.0824	0.0471	1.00	1.00	1.00
Diabetes	0.184	0.287	0.261	0.181	0.151	1.00
Adult	0.527	0.400	0.328	0.439	0.345	0.211
Correlated	0.588	0.568	0.660	0.657	0.727	0.674
Independent	0.492	0.507	0.625	0.654	0.618	0.651

Appendix

Table 2: The table reports the average error ratio over 100 random runs between Leverage SHAP and Optimized Kernel SHAP. For example, on the Independent dataset with

m=5n

samples, Leverage SHAP achieved estimates with

49\%

of the error of Optimized Kernel SHAP. A ratio of

1

indicates that

m\geq 2^{n}

, and both algorithms recovered estimates accurate to machine precision. On average (excluding entries where the ratio is

1

), Leverage SHAP estimates have

50.0\%

of the error of Optimized Kernel SHAP. In other words, Leverage SHAP achieves roughly a

50\%

reduction in error compared to Optimized Kernel SHAP.

Dataset	$n$	1st Quartile	2nd Quartile	3rd Quartile
IRIS	4	0.000234	0.142	0.991
California	8	0.161	0.297	0.44
Diabetes	10	0.182	0.321	0.528
Adult	12	0.171	0.4	0.729

Appendix

Table 3: Summary statistic of

\gamma

over 100 runs.

Figure 5: The relative squared

\ell_{2}

error as a function of

\gamma

, the problem-specific parameter in Corollary 4.1 . The lines indicate the median and the shaded regions encompass the first and third quartile over 100 runs. All three of the main algorithms we consider have higher relative squared

\ell_{2}

error as

\gamma

grows, suggesting that

\gamma

is not an artifact of our analysis. Leverage SHAP has lower median error at

n=10

and

n=14

, while Leverage SHAP and Optimized Kernel SHAP are closer at

n=12

and

n=16

Figure 6: The relative squared

\ell_{2}

error as a function of

\gamma

, the problem-specific parameter in Corollary 4.1 . The lines indicate the mean over 100 runs. All algorithms we consider have higher relative squared

\ell_{2}

error as

\gamma

grows, suggesting that

\gamma

is not an artifact of our analysis.

Figure 7: The linear objective error as a function of

\gamma

, the problem-specific parameter in Corollary 4.1 . The lines indicate the mean over 100 runs. The error of every algorithm we consider stays flat as

\gamma

grows, suggesting that

\gamma

is not a relevant parameter for the linear objective error. This finding aligns with Theorem 1.1 , which has no dependence on

\gamma

	IRIS	California	Diabetes	Adult	Correlated	Independent	NHANES	Communities
Kernel SHAP
Mean	0.0326	0.03	0.0592	0.0596	0.0471	0.0269	0.0542	0.118
1st Quartile	1.03e-05	0.00689	0.0123	0.0196	0.0264	0.0142	0.0175	0.0578
2nd Quartile	0.000259	0.0177	0.0237	0.0412	0.0405	0.0207	0.038	0.0876
3rd Quartile	0.034	0.0417	0.0545	0.0844	0.0556	0.0315	0.0789	0.139
Kernel SHAP Paired

Appendix

Table 4: Relative squared

\ell_{2}

error by dataset and estimator, reported in summary statistics from 100 random runs. The Binomial entry uses the corrected sampler and fresh runs described in this appendix.

Figure 8: The relative squared

\ell_{2}

error between the estimated Shapley values and ground truth Shapley values as a function of sample size. The lines report the mean error over 100 runs. Leverage SHAP and its Binomial variant give the best performance in nearly every setting with

m<2^{n}

. Leverage SHAP without Bernoulli sampling is within

10\%

of them for large

n

once

m\geq 10n

(at

m=5n

the gap is only slightly larger,

4

–

12\%

), but between

1.1

and

15.2

times as bad for small

n

, with the gap growing as

m

approaches

2^{n}

and sampling without replacement matters more. Kernel SHAP Paired and Optimized Kernel SHAP typically come next, followed by Permutation SHAP and then Leverage SHAP (Unpaired), although Permutation SHAP beats Optimized Kernel SHAP on California and on most of NHANES; Kernel SHAP is worst in every setting.

Figure 9: The relative squared

\ell_{2}

error between the estimated and ground truth Shapley values as a function of noise in the set function. For

\sigma\leq 0.1

, Leverage SHAP, its Binomial variant, and (on the large-

n

datasets) Leverage SHAP without Bernoulli sampling trade places from setting to setting and give the best performance in every setting with

m<2^{n}

except California at

\sigma=0.1

, where Kernel SHAP Paired is best. At the highest noise levels (

\sigma\geq 0.5

), Optimized Kernel SHAP is best on Correlated and Independent, and on NHANES at

\sigma=1

; the Binomial variant is best on NHANES at

\sigma=0.5

. Kernel SHAP Paired is best on California at

\sigma=1

. On IRIS, the methods that enumerate all

2^{n}

coalitions have error dominated by noise.

Figure 10: Linear objective error by sample size. The lines indicate the mean error over 100 runs. Leverage SHAP and its Binomial variant quickly achieve the lowest error in nearly all settings. (For small

n

, numerical instability can lead to error below 1.)

Figure 11: Linear objective error by standard deviation of noise. The noise grows large as

\sigma

approaches one for all algorithms. The plots indicate no clear winner across all four datasets.

SHAP Feature Attribution

SHAP (SHapley Additive exPlanations) feature attribution assigns model predictions to input features using Shapley values from cooperative game theory.

See all 36 papers

Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values
Jun 13, 2025R. Teal Witter, Yurong Liu, Christopher MuscoShapley Value Attribution Value Function Estimation
Claremont McKenna College · New York University
Beyond Shapley: Efficient Computation of Asymmetric Shapley Values
Jun 23, 2026Ezequiel Companeetz, Santiago Cifuentes, Sergio AbriolaCooperative Game Theory Feature Attribution
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, UBA · Instituto de Ciencias de la Computación (ICC), CONICET
ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation
Jun 1, 2026David Rundel, Fabian Fumagalli, Maximilian Muschalik +2Shapley Value Attribution Adaptive Sampling
Department of Statistics, LMU Munich, Munich, Germany · Munich Center for Machine Learning, Munich, Germany · Institute for Informatics, LMU Munich, Munich, Germany +2

Jun 13, 2025J/K move · Enter open · S save

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

R. Teal Witter, Yurong Liu, Christopher Musco

Claremont McKenna College · New York University

Shapley Value Attribution Value Function Estimation

Open paper AskPDF arXiv

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\times

lower than Permutation SHAP (the most popular Monte Carlo method),

6.5\times

lower than Kernel SHAP (the most popular linear regression method), and

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\times

lower than the best estimator from prior work.

Abstract

SHAP Feature Attribution

Explore similar work

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

Beyond Shapley: Efficient Computation of Asymmetric Shapley Values

ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation