mlsanityData to 14 Oct 2026

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

arXiv 2605.24084 ↗First posted 22 May 2026cs.LG cs.AI cs.LOcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 62 of its 99 references that are in the map. First posted on arXiv 22 May 2026.

Builds on

62 of 99 references.

References · 62

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2017A Unified Approach to Interpreting Model Predictionscited by 6,555
  3. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,349
  4. 2016Gaussian Error Linear Units (GELUs)cited by 3,502
  5. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
  6. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 445
  7. 2019Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methodscited by 443
  8. 2019The many Shapley values for model explanationcited by 344
  9. 2021Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verificationcited by 228
  10. 2019Towards Stable and Efficient Training of Verifiably Robust Neural Networkscited by 205
  11. 2020Problems with Shapley-value-based explanations as feature importance measurescited by 200
  12. 2020Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifierscited by 187
38 more
  1. 2018Formal Security Analysis of Neural Networks using Symbolic Intervalscited by 185
  2. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  3. 2018Abduction-Based Explanations for Machine Learning Modelscited by 160
  4. 2020Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regressioncited by 154
  5. 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
  6. 2019Explaining Deep Neural Networks with a Polynomial Time Algorithm for Shapley Values Approximationcited by 115
  7. 2021Sampling Permutations for Shapley Value Estimationcited by 102
  8. 2020On The Reasons Behind Decisionscited by 100
  9. 2020On the Tractability of SHAP Explanationscited by 92
  10. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  11. 2022From Shapley Values to Generalized Additive Models and backcited by 60
  12. 2021Shapley values for feature selection: The good, the bad, and the axiomscited by 54
  13. 2021On Guaranteed Optimal Robust Explanations for NLP Modelscited by 54
  14. 2023SHAP-IQ: Unified Approximation of any-order Shapley Interactionscited by 51
  15. 2020Scaling Polyhedral Neural Network Verification on GPUscited by 43
  16. 2024The Fifth International Verification of Neural Networks Competition (VNN-COMP 2024): Summary and Resultscited by 43
  17. 2022Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networkscited by 42
  18. 2023Explaining Predictive Uncertainty with Information Theoretic Shapley Valuescited by 36
  19. 2024Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planescited by 33
  20. 2021On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Resultscited by 32
  21. 2021Trading Complexity for Sparsity in Random Forest Explanationscited by 32
  22. 2021RKHS-SHAP: Shapley Values for Kernel Methodscited by 30
  23. 2019Explaining Models by Propagating Shapley Values of Local Componentscited by 29
  24. 2021Fast TreeSHAP: Accelerating SHAP Value Computation for Treescited by 29
  25. 2023Provably Bounding Neural Network Preimagescited by 29
  26. 2021On Locality of Local Explanation Modelscited by 25
  27. 2024Provably Accurate Shapley Value Estimation via Leverage Score Samplingcited by 23
  28. 2024KernelSHAP-IQ: Weighted Least-Square Optimization for Shapley Interactionscited by 22
  29. 2024Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementationcited by 21
  30. 2023Explaining the Uncertain: Stochastic Shapley Values for Gaussian Process Modelscited by 19
  31. 2025Regression-adjusted Monte Carlo Estimators for Shapley Values and Probabilistic Valuescited by 19
  32. 2023HarsanyiNet: Computing Accurate Shapley Values in a Single Forward Propagationcited by 17
  33. 2024SVARM-IQ: Efficient Approximation of Any-order Shapley Interactions through Stratificationcited by 16
  34. 2020GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensemblescited by 14
  35. 2022Linear TreeShapcited by 13
  36. 2025Exact Computation of Any-Order Shapley Interactions for Graph Neural Networkscited by 13
  37. 2025Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanationscited by 13
  38. 2025On the Computational Tractability of the (Many) Shapley Valuescited by 12

50 most cited of 62 All 62 (JSON)

Built on by

Not cited yet.