Can Leverage SHAP estimate Shapley values with provable accuracy?

Kernel SHAP had no non-asymptotic guarantee

Shapley values assign each input feature a share of a model prediction. Computing them exactly is expensive: for a general model with n features, the paper states that O(2^n) model evaluations are necessary, because the value function must be queried on essentially every subset of features. Kernel SHAP avoids that cost by treating Shapley values as the solution to a weighted least-squares regression over subsets, then solving an approximation built from a sample of subsets.

The paper's stated motivation is a gap in that approximation. At the time of the original submission, no strong non-asymptotic complexity guarantees were known for Kernel SHAP when it uses fewer than 2^n − 2 sampled rows. A non-asymptotic guarantee is a bound that holds at a fixed, finite sample size rather than only as the sample grows without limit — exactly the regime practitioners work in. Leverage SHAP is presented as a fix that keeps Kernel SHAP's model-agnostic structure.

Leverage scores replace weight-based sampling

Kernel SHAP samples subsets with probability proportional to a weight function w(|S|) = C(n,|S|)^-1 · (|S|(n−|S|))^-1, on the intuition that larger terms in the regression sum should be sampled more often. The paper argues that a more principled way to subsample a least-squares problem is to sample rows in proportion to their statistical leverage scores, which measure how important or unique a row of the design matrix is.

Applying that idea directly is not possible, because the design matrix has 2^n − 2 rows and writing down all leverage scores would cost at least O(2^n) time. The paper's key technical step is proving that, after reformulating the constrained Shapley regression as an unconstrained one via a projection matrix, the leverage score of the row for any subset S is proportional to C(n,|S|)^-1. Because all subsets of the same size share the same score, sampling becomes cheap: draw a size s uniformly from {1, …, n−1}, then draw a subset of that size uniformly at random. This is a similar but meaningfully different distribution from Kernel SHAP's.

The guarantee bounds objective error, not each value

Theorem 1.1 states that for any ε > 0 and constant δ > 0, Leverage SHAP uses m = O(n log(n/δ) + n·(1/(εδ))) evaluations of the value function in expectation, plus O(mn²) additional runtime, and returns estimates φ̃ that satisfy the efficiency constraint ⟨φ̃,1⟩ = v([n]) − v(∅) and, with probability 1 − δ, achieve ∥Zφ̃ − y∥²₂ ≤ (1+ε)∥Zφ − y∥²₂.

That is a bound on the regression objective value, not directly on the per-feature error readers usually care about. The paper closes part of the gap with Corollary 4.1: if the estimate satisfies the efficiency constraint and the objective bound, and ∥Aφ∥² > 0, then ∥φ − φ̃∥²₂ ≤ εγ∥φ∥²₂, where γ = ∥Aφ − b∥²₂ / ∥Aφ∥²₂ measures how well the optimal coefficients reach the target vector. The authors report in Appendix F that performance erodes as γ increases for all regression-based algorithms, which they read as evidence that γ is not an artifact of their analysis. The paper also notes in Appendix C why estimating Shapley values with multiplicative error is NP-hard, which is why the guarantee is framed this way.

Paired sampling and no-replacement sampling carry over

The optimized Kernel SHAP in the SHAP library includes two practical refinements: paired sampling, where sampling a set S also samples its complement, so each feature appears in the same number of samples; and sampling without replacement, which matters when n is small and sampling with replacement can stay inaccurate even as m approaches or exceeds 2^n. The paper shows leverage score sampling can be combined with paired sampling without losing the theoretical guarantee, and that a without-replacement version improves accuracy when m is large.

Ablations quantify the pieces. Bernoulli (without-replacement) sampling has little effect for large n but reduces Leverage SHAP's error for small n by a factor between 1.1 and 10, about 2 in the typical setting, growing as m approaches 2^n. Paired sampling reduces error by a factor of roughly four or more in every setting of the sample-size experiment.

About half the error of optimized Kernel SHAP

Experiments use eight datasets from the SHAP library, with n ranging from 4 (IRIS) to 101 (Communities). Ground-truth Shapley values come from Tree SHAP on tree-based models, trained with XGBoost using 100 estimators and maximum depth 4. The primary metric is relative squared ℓ2 error, ∥φ − φ̃∥²₂ / ∥φ∥²₂, and results are reported as medians and quartiles over 100 runs because the mean minus standard deviation is negative for the small error values.

At m = 10n, Leverage SHAP has the lowest mean error on every dataset except ties: for example 0.000249 versus 0.00301 for optimized Kernel SHAP on California (n = 8), and 0.0139 versus 0.0231 on Communities (n = 101). Across the study the authors report an approximately 50% reduction in error on average relative to the optimized Kernel SHAP implementation. In the sample-size sweep (m = 5n, 10n, 20n, …, 160n), Leverage SHAP reliably beats optimized Kernel SHAP outside the regime where exact recovery is possible: on Correlated and Independent (both n = 60) the third quartile of Leverage SHAP error is roughly the median of optimized Kernel SHAP, on NHANES and Communities it is at most about 1.5 times that median, and on the small-n datasets it is below the median. Both methods reach essentially machine precision as m approaches 2^n because both sample without replacement.

The advantage grows when n is large relative to m

The paper states that Leverage SHAP's improvement over Kernel SHAP is especially substantial when n is large compared with m, and when only noisy estimates of the value function are available. The noisy setting is common in explainable AI, where v(S) is an expectation over functions involving random baselines and is itself estimated from a finite sample. In the noise experiments reported in Appendix D, Leverage SHAP meets or exceeds the other estimators at low and moderate noise.

Scope matters here. Like Kernel SHAP, Leverage SHAP assumes black-box access to a single value function v; the paper explicitly says this setting is incomparable to work that reuses information across many input vectors, each inducing its own set function. The experiments use tree models so exact Shapley values are computable, and the reported error reductions are on those eight datasets and sample budgets, not a claim about every model class or every attribution task.

When the sampling distribution is the thing to change

The paper's practical priority is narrow and specific: if you are already using Kernel SHAP and your sample budget m is small relative to n, the change worth making is the sampling distribution, not the regression solver. Leverage SHAP keeps the same regression formulation and adds paired sampling and without-replacement sampling, so the reported gains come from which subsets get evaluated. The guarantee is a near-optimal objective value with high probability at near-linear sample cost, and the empirical payoff is roughly half the relative squared error of the optimized library implementation on average.

The boundary is equally specific. When m approaches 2^n, both optimized Kernel SHAP and Leverage SHAP reach essentially machine precision, so there is little left to gain. And because the theorem bounds the regression objective while Corollary 4.1 converts that into per-feature error only through the problem-dependent factor γ, the strength of the per-feature promise depends on how well the optimal coefficients reach the target — a quantity the authors show empirically degrades performance for all regression-based methods as it grows.

Sources used in this answer