# A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 31 references that are in the map.
- First posted on arXiv 5 Jun 2025.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Consistent Individualized Feature Attribution for Tree Ensembles](https://mlsanity.com/paper/1802.03888/) (2018)
- [Explaining individual predictions when features are dependent: More accurate approximations to Shapley values](https://mlsanity.com/paper/1903.10464/) (2019)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [L-Shapley and C-Shapley: Efficient Model Interpretation for Structured Data](https://mlsanity.com/paper/1808.02610/) (2018)
- [Shapley explainability on the data manifold](https://mlsanity.com/paper/2006.01272/) (2020)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Efficient nonparametric statistical inference on population feature importance using Shapley values](https://mlsanity.com/paper/2006.09481/) (2020)
- [Determinantal Point Processes in Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2005.03185/) (2020)
- [WeightedSHAP: analyzing and improving Shapley based feature attributions](https://mlsanity.com/paper/2209.13429/) (2022)
- [A Multilinear Sampling Algorithm to Estimate Shapley Values](https://mlsanity.com/paper/2010.12082/) (2020)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [KernelSHAP-IQ: Weighted Least-Square Optimization for Shapley Interactions](https://mlsanity.com/paper/2405.10852/) (2024)
- [SHAP@k:Efficient and Probably Approximately Correct (PAC) Identification of Top-k Features](https://mlsanity.com/paper/2307.04850/) (2023)
- [Fast Shapley Value Estimation: A Unified Approach](https://mlsanity.com/paper/2311.01010/) (2023)

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

- [Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values](https://mlsanity.com/paper/2506.11849/) (2025)
- [Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond](https://mlsanity.com/paper/2604.08438/) (2026)
- [Do covariates explain why these groups differ? The choice of reference group can reverse conclusions in the Oaxaca-Blinder decomposition](https://mlsanity.com/paper/2603.29972/) (2026)
- [α-TCAV: A Unified Framework for Testing with Concept Activation Vectors](https://mlsanity.com/paper/2605.15688/) (2026)

## Abstract (arXiv)

Shapley values have emerged as a critical tool for explaining which features impact the decisions made by machine learning models. However, computing exact Shapley values is difficult, generally requiring an exponential (in the feature dimension) number of model evaluations. To address this, many model-agnostic randomized estimators have been developed, the most influential and widely used being the KernelSHAP method (Lundberg & Lee, 2017). While related estimators such as unbiased KernelSHAP (Covert & Lee, 2021) and LeverageSHAP (Musco & Witter, 2025) are known to satisfy theoretical guarantees, bounds for KernelSHAP have remained elusive. We describe a broad and unified framework that encompasses KernelSHAP and related estimators constructed using both with and without replacement sampling strategies. We then prove strong non-asymptotic theoretical guarantees that apply to all estimators from our framework. This provides, to the best of our knowledge, the first theoretical guarantees for KernelSHAP and sheds further light on tradeoffs between existing estimators. Through comprehensive benchmarking on small and medium dimensional datasets for Decision-Tree models, we validate our approach against exact Shapley values, consistently achieving low mean squared error with modest sample sizes. Furthermore, we make specific implementation improvements to enable scalability of our methods to high-dimensional datasets. Our methods, tested on datasets such MNIST and CIFAR10, provide consistently better results compared to the KernelSHAP library.