# Provably Accurate Shapley Value Estimation via Leverage Score Sampling

arXiv: https://arxiv.org/abs/2410.01917 · HTML: https://mlsanity.com/paper/2410.01917/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 46 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 27 of 27)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Consistent Individualized Feature Attribution for Tree Ensembles](https://mlsanity.com/paper/1802.03888/) (2018)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Feature relevance quantification in explainable AI: A causal problem](https://mlsanity.com/paper/1910.13413/) (2019)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data](https://mlsanity.com/paper/1808.02610/) (2018)
- [CXPlain: Causal Explanations for Model Interpretation under Uncertainty](https://mlsanity.com/paper/1910.12336/) (2019)
- [Shapley values for feature selection: The good, the bad, and the axioms](https://mlsanity.com/paper/2102.10936/) (2021)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (2017)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Query Complexity of Least Absolute Deviation Regression via Robust Uniform Convergence](https://mlsanity.com/paper/2102.02322/) (2021)
- [Fourier Sparse Leverage Scores and Approximate Kernel Learning](https://mlsanity.com/paper/2006.07340/) (2020)
- [Estimation of the Shapley value by ergodic sampling](https://mlsanity.com/paper/1906.05224/) (2019)
- [A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms](https://mlsanity.com/paper/1812.08723/) (2018)
- [Active Learning for Single Neuron Models with Lipschitz Non-Linearities](https://mlsanity.com/paper/2210.13601/) (2022)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [Accurate Shapley Values for explaining tree-based models](https://mlsanity.com/paper/2106.03820/) (2021)
- [Leverage Score Sampling for Faster Accelerated Regression and ERM](https://mlsanity.com/paper/1711.08426/) (2017)
- [Improved Active Learning via Dependent Leverage Score Sampling](https://mlsanity.com/paper/2310.04966/) (2023)
- [Exact Shapley Values for Local and Model-True Explanations of Decision Tree Ensembles](https://mlsanity.com/paper/2112.10592/) (2021)
- [A Note on Random Sampling for Matrix Multiplication](https://mlsanity.com/paper/1811.11237/) (2018)

## Built on by (most cited first, 23 of 23)

- [Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values](https://mlsanity.com/paper/2506.11849/) (2025)
- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently](https://mlsanity.com/paper/2410.23808/) (2024)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression](https://mlsanity.com/paper/2601.18608/) (2026)
- [Explaining Similarity in Vision-Language Encoders with Weighted Banzhaf Interactions](https://mlsanity.com/paper/2508.05430/) (2025)
- [Explanation Multiplicity in SHAP: Characterization and Assessment](https://mlsanity.com/paper/2601.12654/) (2026)
- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values](https://mlsanity.com/paper/2506.05216/) (2025)
- [Exactly Computing do-Shapley Values](https://mlsanity.com/paper/2602.07203/) (2026)
- [Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values](https://mlsanity.com/paper/2410.08336/) (2024)
- [Faithful Group Shapley Value](https://mlsanity.com/paper/2505.19013/) (2025)
- [All Leaks Count, Some Count More: Interpretable Temporal Contamination Detection and Mitigation in LLM Backtesting](https://mlsanity.com/paper/2602.17234/) (2026)
- [Creator Incentives in Recommender Systems: A Cooperative Game-Theoretic Approach for Stable and Fair Collaboration in Multi-Agent Bandits](https://mlsanity.com/paper/2604.08643/) (2026)
- [SIM-Shapley: A Stable and Computationally Efficient Approach to Shapley Value Approximation](https://mlsanity.com/paper/2505.08198/) (2025)
- [Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond](https://mlsanity.com/paper/2604.08438/) (2026)
- [CUBE: Contrastive Understanding by Balanced Experiments](https://mlsanity.com/paper/2509.10825/) (2025)
- [Geometric Data Valuation via Leverage Scores](https://mlsanity.com/paper/2511.02100/) (2025)
- [ConfoundingSHAP: Quantifying confounding strength in causal inference](https://mlsanity.com/paper/2605.10533/) (2026)
- [Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks](https://mlsanity.com/paper/2605.24084/) (2026)
- [ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation](https://mlsanity.com/paper/2606.02247/) (2026)
- [OperatorSHAP: Fast and Accurate Shapley Value Estimation for Neural Operators](https://mlsanity.com/paper/2606.28065/) (2026)
- [RelShap: Relationally Consistent Shapley Explanations](https://mlsanity.com/paper/2608.11508/) (2026)

## Abstract (arXiv)

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(2n) 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) 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].