Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks

David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:8760-8793, 2026.

Abstract

Shapley additive explanations (SHAP) are widely recognised as computationally intractable for neural networks, since they induce an exponential search space over the input features. In this work, we take a first step towards scaling exact SHAP computation to larger search spaces by introducing an algorithm that leverages recent advances in neural network verification to compute arbitrarily tight exact lower and upper bounds on SHAP values for neural networks, ultimately recovering the exact SHAP values. We demonstrate that our approach scales to orders of magnitude larger search spaces than state-of-the-art exact methods. This provides an important first step towards exact SHAP computation and establishes a principled cornerstone for evaluating statistical approximation methods on larger search spaces.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-boetius26a, title = {Verified {SHAP}: Provable Bounds for Exact Shapley Values of Neural Networks}, author = {Boetius, David and Bassan, Shahaf and Katz, Guy and Leue, Stefan and Sutter, Tobias}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {8760--8793}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/boetius26a/boetius26a.pdf}, url = {https://proceedings.mlr.press/v306/boetius26a.html}, abstract = {Shapley additive explanations (SHAP) are widely recognised as computationally intractable for neural networks, since they induce an exponential search space over the input features. In this work, we take a first step towards scaling exact SHAP computation to larger search spaces by introducing an algorithm that leverages recent advances in neural network verification to compute arbitrarily tight exact lower and upper bounds on SHAP values for neural networks, ultimately recovering the exact SHAP values. We demonstrate that our approach scales to orders of magnitude larger search spaces than state-of-the-art exact methods. This provides an important first step towards exact SHAP computation and establishes a principled cornerstone for evaluating statistical approximation methods on larger search spaces.} }
Endnote
%0 Conference Paper %T Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks %A David Boetius %A Shahaf Bassan %A Guy Katz %A Stefan Leue %A Tobias Sutter %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-boetius26a %I PMLR %P 8760--8793 %U https://proceedings.mlr.press/v306/boetius26a.html %V 306 %X Shapley additive explanations (SHAP) are widely recognised as computationally intractable for neural networks, since they induce an exponential search space over the input features. In this work, we take a first step towards scaling exact SHAP computation to larger search spaces by introducing an algorithm that leverages recent advances in neural network verification to compute arbitrarily tight exact lower and upper bounds on SHAP values for neural networks, ultimately recovering the exact SHAP values. We demonstrate that our approach scales to orders of magnitude larger search spaces than state-of-the-art exact methods. This provides an important first step towards exact SHAP computation and establishes a principled cornerstone for evaluating statistical approximation methods on larger search spaces.
APA
Boetius, D., Bassan, S., Katz, G., Leue, S. & Sutter, T.. (2026). Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:8760-8793 Available from https://proceedings.mlr.press/v306/boetius26a.html.

Related Material