🤖 machine learning

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

This paper introduces a novel algorithm that leverages neural network verification techniques to compute provable, arbitrarily tight bounds on exact Shapley values, enabling scalable and precise SHAP computation for neural networks with significantly larger search spaces than existing exact methods.

Original authors: David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David Boetius, Shahaf Bassan, Guy Katz, Stefan Leue, Tobias Sutter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very complex, black-box machine (a neural network) that makes decisions, like diagnosing a disease or approving a loan. You want to know exactly which input features (like age, income, or blood pressure) caused the machine to make that specific decision.

The standard way to answer this is called SHAP. Think of SHAP as a game where you try to figure out how much each player (feature) contributed to the team's final score. To get the perfectly accurate answer, you would theoretically need to test every single possible combination of players.

The Problem:
For a simple machine, testing every combination is easy. But for a complex neural network with hundreds of features, the number of combinations is so huge it's like trying to count every grain of sand on every beach on Earth. It takes so long that it's practically impossible. Because of this, most tools today just guess the answer using shortcuts. These guesses are usually fast, but they can be wrong, and we have no way to know how wrong they are because we can't calculate the "real" answer to compare them against.

The Solution: Verified SHAP (VERISHAP)
The authors of this paper built a new tool called VERISHAP. They didn't try to count every grain of sand. Instead, they used a clever trick borrowed from a field called "Neural Network Verification" (which is usually used to prove that AI systems are safe and secure).

Here is how VERISHAP works, using a simple analogy:

The "Room Search" Analogy

Imagine you are looking for a specific treasure hidden in a giant, dark warehouse filled with millions of boxes (the search space).

Old Methods (Guessing): You throw a dart at the map and say, "The treasure is probably in this general area." It's fast, but you might be off by a mile.
Old Exact Methods (Counting): You try to open every single box one by one. This guarantees you find the treasure, but you will die of old age before you finish.
VERISHAP (The Smart Search):
1. Divide and Conquer: Instead of opening boxes one by one, you divide the warehouse into large rooms.
2. The "Fence" Trick: You use a special mathematical fence (called bound propagation) to check a whole room at once. This fence tells you: "The treasure in this room is definitely between $10 and $20."
3. Zooming In: If the range ($10 to $20) is too wide, you split that room into smaller rooms and check again. The fence gets tighter: "Now we know it's between $14 and $16."
4. The Result: You keep splitting rooms until the fence is so tight that the range is effectively zero. You have found the exact treasure location.

Why This is a Big Deal

The paper claims three main victories:

It Scales Up: Previous methods that tried to find the exact answer would crash or run out of memory if the problem got too big. VERISHAP can handle search spaces that are orders of magnitude larger (think billions or trillions of times bigger) than what was possible before.
It Gives You "Good Enough" Answers Fast: You don't always have to wait until the search is 100% finished. If the "fence" gets tight enough (e.g., "The answer is between 14.9 and 15.1"), you can stop early and say, "We are 99.9% sure the answer is 15." This gives you trustworthy insights much faster than waiting for the perfect answer.
It Creates a "Gold Standard" for Testing: Because VERISHAP can calculate the real answer for larger problems, it acts as a "truth machine." Researchers can now use it to test those guessing tools (like KERNELSHAP) to see how accurate they really are on complex, real-world neural networks. Before this, we could only test guessing tools on tiny, toy examples that didn't reflect reality.

What the Paper Actually Says (and What It Doesn't)

It DOES say: They successfully computed exact SHAP values and tight bounds for neural networks on tabular data (like spreadsheets) and image data (like MNIST digits). They showed it works on different types of network architectures (like ResNets) and different activation functions (like ReLU, Tanh).
It DOES say: It is currently slower than the "guessing" methods, but it is the only way to get a mathematically proven, exact answer for large networks.
It DOES NOT say: The paper does not claim this tool is ready for immediate clinical use in hospitals or that it solves all AI bias issues. It focuses strictly on the mathematical ability to compute these values and verify them. It acknowledges that while it is a huge step forward, the underlying math is still very hard, and for some very specific, complex networks, it might still take a long time.

In Summary:
VERISHAP is like upgrading from a compass that points "roughly North" to a GPS that can tell you your exact location, even in a massive, unmapped forest. It proves that we can get the exact truth for complex AI decisions, and it gives us a ruler to measure how good our other, faster tools really are.

Technical Summary: Verified SHAP (VERISHAP)

Problem Statement

Shapley Additive Explanations (SHAP) are a standard post-hoc explainability method for attributing machine learning model predictions to input features. However, computing exact SHAP values for neural networks is widely considered computationally intractable due to the exponential search space over feature subsets ( $2^n$ ). While exact computation is feasible for tree-based and additive models, it is #P-hard for general neural networks. Consequently, the literature relies on statistical estimators (e.g., KERNELSHAP, FASTSHAP, LEVERAGESHAP). These estimators face two fundamental limitations:

Inaccuracy: They provide approximations that can be unreliable in highly non-linear models or scenarios with strong feature interactions.
Lack of Ground Truth: Because exact SHAP values are prohibitively expensive to compute for neural networks, estimators are typically evaluated on toy-sized models where exact computation is possible. These settings often fail to generalize to real-world, high-dimensional neural networks.

Methodology: Verified SHAP (VERISHAP)

The paper introduces VERISHAP, the first algorithm to leverage recent advances in neural network verification to compute exact SHAP values and provable bounds for neural networks. The approach adapts branch-and-bound verification techniques to the discrete, probabilistic, and summation-heavy nature of SHAP.

Core Algorithm

VERISHAP employs an incremental branch-and-bound strategy to recursively partition the feature space (the set of all coalitions $S_i$ for a feature $i$ ).

Partitioning: The algorithm defines branches $B$ based on sets of included ( $I$ ) and excluded ( $E$ ) features. A branch represents a subset of coalitions where features in $I$ are present and features in $E$ are absent.
Bounding via Propagation: For each branch, the algorithm computes lower and upper bounds on the marginal contribution $\Delta_i(S) = v(S \cup \{i\}) - v(S)$ $Δ_{i} (S) = v (S \cup {i}) - v (S)$ .
- To apply continuous bound propagation (e.g., CROWN, IBP) to discrete sets, the algorithm relaxes Boolean feature masks $m \in \{0, 1\}^n$ to the continuous domain $[0, 1]^n$ .
- It uses Linear Bound Propagation (LBP) (specifically CROWN-IBP) to derive tight bounds on the value function $v(S)$ over the relaxed domain.
Aggregation: The total SHAP value bounds are computed by summing the weighted bounds of all branches:
$\phi_i^{(t)} = \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B \leq \phi_i \leq \sum_{B \in \mathcal{B}^{(t)}} \Lambda_B \Delta_i^B = \bar{\phi}_i^{(t)}$
where $\Lambda_B$ is the closed-form sum of Shapley weights for the coalitions in branch $B$ , derived combinatorially.
Refinement: The algorithm iteratively selects branches to split (using strategies like MAXDIAM) and features to split on (using strategies like SMEARS), refining the bounds until they converge to the exact value or a desired precision.

Key Theoretical Properties

Termination: The algorithm is guaranteed to terminate with exact SHAP values after a finite number of iterations (at most $2^{n-1}$ ), as the partition eventually isolates single coalitions.
Early Termination for Linear Models: For linear models, the algorithm terminates in the first iteration because the marginal contribution is constant, and LBP introduces no approximation error for linear compositions.
Piecewise-Linearity: For ReLU-activated networks, the algorithm can terminate early if the partition restricts the search to regions where the network behaves linearly.

Key Contributions

First Exact SHAP for Neural Networks: VERISHAP is the first algorithm to compute exact SHAP values for general neural networks, scaling to search spaces orders of magnitude larger than previous exact methods.
Provable Bounds: The method provides arbitrarily tight lower and upper bounds on SHAP values, enabling trustworthy explanatory insights even before full convergence.
Ground-Truth Baseline: It establishes a principled framework for evaluating statistical SHAP estimators on larger, more realistic search spaces where ground truth was previously unattainable.
Efficiency via Verification: By exploiting the decomposition of neural networks into near-linear regions, the algorithm avoids enumerating all $2^n$ coalitions in many practical cases.

Experimental Results

The authors evaluated VERISHAP on tabular (UCI datasets) and vision (MNIST, FashionMNIST, CIFAR10, GTSRB) benchmarks.

Scalability vs. ExactSHAP: VERISHAP significantly outperforms the state-of-the-art exact method (EXACTSHAP). While EXACTSHAP exhausts GPU memory for search spaces larger than $2^{20}$ , VERISHAP computes exact values for instances up to $2^{25}$ ( $\approx 3 \times 10^7$ coalitions) and provides tight bounds for spaces up to $2^{60}$ ( $\approx 10^{18}$ coalitions).
Comparison to Estimators: When compared to statistical estimators (KERNELSHAP, TREEMSR, LEVERAGESHAP), VERISHAP demonstrates that estimators often fail to achieve the same accuracy within memory constraints. Furthermore, VERISHAP reveals that estimator performance varies significantly across datasets (e.g., TREEMSR shows volatile performance on neural networks compared to tree-based models).
Architecture Versatility: The algorithm successfully computes exact SHAP values for various architectures, including fully connected networks with ReLU, tanh, and Swish activations, as well as ResNets.
Convergence: In experiments (e.g., MNIST), the bounds become informative (revealing attribution patterns) long before the exact value is computed, often within seconds, while exact computation may take tens of seconds.

Significance and Claims

The paper positions VERISHAP as a first step toward scaling exact SHAP computation for neural networks. Its significance lies in three areas:

Scalability: It bridges the gap between the theoretical intractability of exact SHAP and practical application by leveraging neural network verification.
Trustworthiness: It offers a method to obtain "ground-truth" explanations with provable guarantees, addressing the uncertainty inherent in statistical approximations.
Evaluation Framework: It provides a rigorous benchmark for evaluating and improving SHAP estimators on larger search spaces, moving beyond toy models.

The authors acknowledge that computing exact SHAP remains #P-hard and that VERISHAP may still be slow for certain complex networks. However, they argue that the ability to compute provable bounds and the potential for continued improvements in neural network verification make this a foundational advancement for trustworthy AI explainability.