# An Odd Estimator for Shapley Values

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 53 references that are in the map.
- First posted on arXiv 1 Feb 2026.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [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)
- [Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models](https://mlsanity.com/paper/2011.01625/) (2020)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [The Shapley Value in Machine Learning](https://mlsanity.com/paper/2202.05594/) (2022)
- [Shapley explainability on the data manifold](https://mlsanity.com/paper/2006.01272/) (2020)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles](https://mlsanity.com/paper/2401.12069/) (2024)
- [Provably Accurate Shapley Value Estimation via Leverage Score Sampling](https://mlsanity.com/paper/2410.01917/) (2024)
- [Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Values](https://mlsanity.com/paper/2506.11849/) (2025)
- [Efficient Data Shapley for Weighted Nearest Neighbor Algorithms](https://mlsanity.com/paper/2401.11103/) (2024)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [SPEX: Scaling Feature Interaction Explanations for LLMs](https://mlsanity.com/paper/2502.13870/) (2025)
- [SHAP values via sparse Fourier representation](https://mlsanity.com/paper/2410.06300/) (2024)
- [PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression](https://mlsanity.com/paper/2601.18608/) (2026)
- [Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes](https://mlsanity.com/paper/2508.14499/) (2025)
- [Improving the Weighting Strategy in KernelSHAP](https://mlsanity.com/paper/2410.04883/) (2024)
- [Shapley Values: Paired-Sampling Approximations](https://mlsanity.com/paper/2508.12947/) (2025)

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

- [Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond](https://mlsanity.com/paper/2604.08438/) (2026)
- [ConfoundingSHAP: Quantifying confounding strength in causal inference](https://mlsanity.com/paper/2605.10533/) (2026)
- [Generalized Priority-Aware Shapley Value](https://mlsanity.com/paper/2605.15018/) (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)

The Shapley value is a ubiquitous framework for attribution in machine learning, encompassing feature importance, data valuation, and causal inference. However, its exact computation is generally intractable, necessitating efficient approximation methods. While the most effective and popular estimators leverage the paired sampling heuristic to reduce estimation error, the theoretical mechanism driving this improvement has remained opaque. In this work, we provide an elegant and fundamental justification for paired sampling: we prove that the Shapley value depends exclusively on the odd component of the set function, and that paired sampling orthogonalizes the regression objective to filter out the irrelevant even component. Leveraging this insight, we propose OddSHAP, a novel consistent estimator that performs polynomial regression solely on the odd subspace. By utilizing the Fourier basis to isolate this subspace and employing a proxy model to identify high-impact interactions, OddSHAP overcomes the combinatorial explosion of higher-order approximations. Through an extensive benchmark, we find that OddSHAP achieves state-of-the-art estimation accuracy at larger sampling budgets.