Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks
Summary
Proposes a verification-based algorithm to compute provable bounds on exact SHAP values for neural networks, scaling to much larger search spaces than prior exact methods.
View Cached Full Text
Cached at: 05/26/26, 09:00 AM
# Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks Source: [https://arxiv.org/abs/2605.24084](https://arxiv.org/abs/2605.24084) [View PDF](https://arxiv.org/pdf/2605.24084) > 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\. ## Submission history From: David Boetius \[[view email](https://arxiv.org/show-email/41213bfe/2605.24084)\] **\[v1\]**Fri, 22 May 2026 18:00:01 UTC \(2,560 KB\)
Similar Articles
Quantitative Sobolev Approximation Bounds for Neural Operators with Empirical Validation on Burgers Equation
This paper establishes quantitative Sobolev approximation bounds for neural operators, proving that operators can be uniformly approximated with explicit complexity-error relations. It validates these theoretical bounds using Fourier Neural Operators on the Burgers' equation, demonstrating that Sobolev-space approximation theory accurately predicts scaling behavior.
Precise Verification of Transformers through ReLU-Catalyzed Abstraction Refinement
This paper proposes a novel transformer verification approach that uses ReLU to represent precise but non-linear bounds for dot products, enabling precise and efficient verification. The method outperforms state-of-the-art baselines on sentiment analysis models.
From LLM-Generated Conjectures to Lean Formalizations: Automated Polynomial Inequality Proving via Sum-of-Squares Certificates
This paper presents NSPI, a neuro-symbolic framework that combines LLMs and symbolic computation to prove polynomial inequalities. It uses LLM-generated sum-of-squares conjectures, refines them symbolically, and formally verifies the proofs in Lean, demonstrating scalability on polynomials with up to 10 variables.
Vertex-Softmax: Tight Transformer Verification via Exact Softmax Optimization
This paper introduces Vertex-Softmax, a method for tight Transformer verification by proving that exact softmax optimization over interval constraints occurs at vertices of the constraint box. It improves certified accuracy and efficiency in CROWN-style verifiers for attention models on standard datasets.
Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization
This paper studies the exact certification problem for neural networks, showing that even minimal overparametrization can make certification exponentially hard for threshold circuits of depth≥2 and log-precision Transformers. It also characterizes approximate certification, revealing that allowing polynomially many mistakes still requires exponentially large certificates.