# Exact Shapley Attributions in Quadratic-time for FANOVA Gaussian Processes

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 20 Aug 2025.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [Model Agnostic Supervised Local Explanations](https://mlsanity.com/paper/1807.02910/) (2018)
- [A Review of Feature Selection Methods Based on Mutual Information](https://mlsanity.com/paper/1509.07577/) (2015)
- [RKHS-SHAP: Shapley Values for Kernel Methods](https://mlsanity.com/paper/2110.09167/) (2021)
- [Looping in the Human Collaborative and Explainable Bayesian Optimization](https://mlsanity.com/paper/2310.17273/) (2023)
- [Deconditional Downscaling with Gaussian Processes](https://mlsanity.com/paper/2105.12909/) (2021)
- [BayesIMP: Uncertainty Quantification for Causal Data Fusion](https://mlsanity.com/paper/2106.03477/) (2021)
- [Explaining the Uncertain: Stochastic Shapley Values for Gaussian Process Models](https://mlsanity.com/paper/2305.15167/) (2023)
- [Explanations of Black-Box Models based on Directional Feature Interactions](https://mlsanity.com/paper/2304.07670/) (2023)
- [Unifying Feature-Based Explanations with Functional ANOVA and Cooperative Game Theory](https://mlsanity.com/paper/2412.17152/) (2024)
- [Amortized Linear-time Exact Shapley Value for Product-Kernel Methods](https://mlsanity.com/paper/2505.16516/) (2025)

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

- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [Beyond Prediction-Set Size: Quantifying Conformal Uncertainty through Credal Geometry](https://mlsanity.com/paper/2602.01667/) (2026)
- [Exactly Computing do-Shapley Values](https://mlsanity.com/paper/2602.07203/) (2026)
- [Tractable Shapley Values and Interactions via Tensor Networks](https://mlsanity.com/paper/2510.22138/) (2025)
- [When Do Credal Sets Stabilize? Fixed-Point Theorems for Credal Set Updates](https://mlsanity.com/paper/2510.04769/) (2025)
- [ShaplEIG: Bayesian Experimental Design for Shapley Value Estimation](https://mlsanity.com/paper/2606.02247/) (2026)

## Abstract (arXiv)

Shapley values are widely recognized as a principled method for attributing importance to input features in machine learning. However, the exact computation of Shapley values scales exponentially with the number of features, severely limiting the practical application of this powerful approach. The challenge is further compounded when the predictive model is probabilistic - as in Gaussian processes (GPs) - where the outputs are random variables rather than point estimates, necessitating additional computational effort in modeling higher-order moments. In this work, we demonstrate that for an important class of GPs known as FANOVA GP, which explicitly models all main effects and interactions, *exact* Shapley attributions for both local and global explanations can be computed in *quadratic time*. For local, instance-wise explanations, we define a stochastic cooperative game over function components and compute the exact stochastic Shapley value in quadratic time only, capturing both the expected contribution and uncertainty. For global explanations, we introduce a deterministic, variance-based value function and compute exact Shapley values that quantify each feature's contribution to the model's overall sensitivity. Our methods leverage a closed-form (stochastic) M"obius representation of the FANOVA decomposition and introduce recursive algorithms, inspired by Newton's identities, to efficiently compute the mean and variance of Shapley values. Our work enhances the utility of explainable AI, as demonstrated by empirical studies, by providing more scalable, axiomatically sound, and uncertainty-aware explanations for predictions generated by structured probabilistic models.