# PolySHAP: Extending KernelSHAP with Interaction-Informed Polynomial Regression

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 60 references that are in the map.
- First posted on arXiv 26 Jan 2026.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [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)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Consistent Individualized Feature Attribution for Tree Ensembles](https://mlsanity.com/paper/1802.03888/) (2018)
- [Explaining by Removing: A Unified Framework for Model Explanation](https://mlsanity.com/paper/2011.14878/) (2020)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [The Shapley Taylor Interaction Index](https://mlsanity.com/paper/1902.05622/) (2019)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [Sampling Permutations for Shapley Value Estimation](https://mlsanity.com/paper/2104.12199/) (2021)
- [How does this interaction affect me? Interpretable attribution for feature interactions](https://mlsanity.com/paper/2006.10965/) (2020)
- [Faith-Shap: The Faithful Shapley Interaction Index](https://mlsanity.com/paper/2203.00870/) (2022)
- [OpenML-Python: an extensible Python API for OpenML](https://mlsanity.com/paper/1911.02490/) (2019)
- [From Shapley Values to Generalized Additive Models and back](https://mlsanity.com/paper/2209.04012/) (2022)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [shapiq: Shapley Interactions for Machine Learning](https://mlsanity.com/paper/2410.01649/) (2024)
- [WeightedSHAP: analyzing and improving Shapley based feature attributions](https://mlsanity.com/paper/2209.13429/) (2022)
- [Approximating the Shapley Value without Marginal Contributions](https://mlsanity.com/paper/2302.00736/) (2023)
- [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)
- [ProxySPEX: Inference-Efficient Interpretability via Sparse Feature Interactions in LLMs](https://mlsanity.com/paper/2505.17495/) (2025)
- [A Comparative Study of Methods for Estimating Conditional Shapley Values and When to Use Them](https://mlsanity.com/paper/2305.09536/) (2023)
- [Learning to Understand: Identifying Interactions via the M"obius Transform](https://mlsanity.com/paper/2402.02631/) (2024)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [Unifying Feature-Based Explanations with Functional ANOVA and Cooperative Game Theory](https://mlsanity.com/paper/2412.17152/) (2024)
- [A k-additive Choquet integral-based approach to approximate the SHAP values for local interpretability in machine learning](https://mlsanity.com/paper/2211.02166/) (2022)
- [Shaping Up SHAP: Enhancing Stability through Layer-Wise Neighbor Selection](https://mlsanity.com/paper/2312.12115/) (2023)

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

- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [Priority-Aware Shapley Value](https://mlsanity.com/paper/2602.09326/) (2026)
- [QuadraSHAP: ε-Exact Shapley Values for Product Games in Logarithmic Parallel Time](https://mlsanity.com/paper/2605.05870/) (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)
- [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)

## Abstract (arXiv)

Shapley values have emerged as a central game-theoretic tool in explainable AI (XAI). However, computing Shapley values exactly requires 2d game evaluations for a model with d features. Lundberg and Lee's KernelSHAP algorithm has emerged as a leading method for avoiding this exponential cost. KernelSHAP approximates Shapley values by approximating the game as a linear function, which is fit using a small number of game evaluations for random feature subsets. In this work, we extend KernelSHAP by approximating the game via higher degree polynomials, which capture non-linear interactions between features. Our resulting PolySHAP method yields empirically better Shapley value estimates for various benchmark datasets, and we prove that these estimates are consistent. Moreover, we connect our approach to paired sampling (antithetic sampling), a ubiquitous modification to KernelSHAP that improves empirical accuracy. We prove that paired sampling outputs exactly the same Shapley value approximations as second-order PolySHAP, without ever fitting a degree 2 polynomial. To the best of our knowledge, this finding provides the first strong theoretical justification for the excellent practical performance of the paired sampling heuristic.