- Rating
- 4(+2)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
The authors introduce a verification-based algorithm for discovering additive structures within neural networks. This tool gives upper and lower bounds on a broad family of game-theoretic explanations, including Shapley and Fourier explanations. They claim to bring for the first time certified game-theoretic interactions to transformers.
They mentioned that recent work shows that neural network verification offers a way out with affine bound propagation. However, this work by Boetius et al limits to first-order Shapley values, and it scales only to small models and search spaces. This work develops a general framework, extending beyond first-order. They name this VeriDAP which leverages this idea of affine functions and refines this decomposition until the exact values are recovered.
The authors also discuss the scalability of the problem and show that the problem remains hard for models with as few as two ReLU neurons, or a single attention layer. Then, they propose to obtain tractability by shaping the input-space geometry of the trained neural network and for that they introduce a certified-training approach based on robust optimisation that directly reshapes the neural network’s input geometry.
Critical strengths
-
The problem the paper addresses is very relevant. As said by the authors, Transformers power today’s most capable deep learning models, but remain challenging to deploy in sensitive applications. Their propose method seems to be useful in this setting to provide exact, certified game-theoretic explanation, as well as for other types of networks.
-
Their idea of obtaining tractability by shaping the input-space geometry of the trained neural network seem very interesting and a potential beneficial approach.
Critical weaknesses
My main points in terms of limitations comes from the experimental results:
-
Figure 5 is not discussed in the main text
-
It is not fully clear why there are some datasets in Figure 1 for this for all the networks the half-widths are significantly higher than the 0.1% while for others it is not, what is the causing this? from Table 1 it does not seem to the be the |B^d|.
-
Similarly to the point before, I do not see a good discussion on why we also see in Table 1 for some |B^d| in MNIST that there crux for two networks and for IBP, it is below 0.1% with a tick. I think this is a limitation.
-
I do not see a clear comparison of performance to other methods to estimate Shapley values. I think this is important. While Figure 5 aims to do this, it is not clear which of all of them is the proposed method in the paper, why those other methods are chosen, and how it is done an apples-to-apples comparison. I would like to see clear evidence that this method improves upon state-of-the-art.
-
This claim in page 8 is not supported "As visualised in Figure 1, VERIDAP computes the exact order-2 SII of a certifiably trained vision transformer (ViT) (Dosovitskiy et al., 2021; Brix et al., 2023) over a search space of 2 23 coalitions within 1 440 s. ". I do not see that in Figure 1.
Questions for authors
-
what do you mean with this sentence in page 2 "We use the resulting ground-truth interactions as a benchmark for evaluating Shapley estimators on neural networks, which has so far been infeasible.'? to me the Shapely estimations are infeasible to estimate exactly in general but one can make good approximations.
-
To what extend is this idea of decomposing neural cooperative games into additive pieces similar to making a decision tree from the neural network? I wonder how different or similar can be a decision tree (or an ensemble of trees) trained on the same data be to this decomposition.
-
why did you select those methods to estimate the Shapley values that you compare to in Figure 5? There are some many estimators that I wonder that is the best performing one and what is an apples-to-apples comparison. I do not follow which of them is the method you propose and which is the baseline.
7 comments
Rebuttal Part II
W4 & Q3: I do not see a clear comparison of performance to other methods to estimate Shapley values. While Figure 5 aims to do this, it is not clear which of all of them is the proposed method in the paper, why those other methods are chosen, and how it is done an apples-to-apples comparison.
Thank you for raising this important and subtle point. We have revised the caption of Figure 5 to clarify its purpose and would be grateful for further feedback on its presentation. Figure 5 does not compare our approach to Shapley estimators, since VeriDAP is not a Shapley estimator, but an exact method. Instead, the figure shows the results of benchmarking different standard (KernelSHAPIQ) and state-of-the-art (ProxySHAP, ProxySpex) SII estimators using the guaranteed ground-truth SII results computed by VeriDAP.
In Figure 5, VeriDAP corresponds to the dashed line. Overall, Figure 5 shows that VeriDAP can compute more precise bounds on the true SII than the estimates. However, this comparison is not quite apples-to-apples to VeriDAP’s disadvantage, since VeriDAP computes guaranteed bounds on the true SII, while the estimators do not provide guarantees. In fact, this comparison is only possible because VeriDAP provides guaranteed bounds on the true value.
Table 2 provides an apples-to-apples comparison of VeriDAP with the state-of-the-art exact baseline from shapiq.
Q2: To what extent is this idea of decomposing neural cooperative games into additive pieces similar to making a decision tree from the neural network?
Thank you for this interesting question. Indeed, both our decomposition and a decision tree partition the input space. However, our decomposition is quite different from a decision tree. Unlike a decision tree, it is neither learned from data nor can it be used to make predictions. Instead, we construct our decomposition from the internal structure of the neural network. Furthermore, while the progress of VeriDAP can be visualised using a branch-and-bound search tree (Figure 3), VeriDAP never stores this tree, but only maintains a frontier of leaves.
Nonetheless, it is an interesting question how our partitioning compares to the partitioning of a decision tree for computing Shapley interactions. We experimentally compare the following tree-based approaches:
- the classic CART [Breiman et al., 1984] and the state-of-the-art STreeD [van der Linden et al., 2023] algorithms for learning decision trees. We trained the decision trees on the same data used to train the neural network;
- the classic random forest [Breiman, 2001] and XGBoost [Chen and Guestrin, 2016], trained on the same data; and
- The RENTT algorithm [Monke et al., 2025] that makes a decision tree from a neural network by enumerating the activation patterns occurring for the training data.
The following table shows the normalised half-widths of the SII bounds obtained from the partitions of the decision trees and forests above, compared to the partition computed by VeriDAP. The half-widths are normalised as in Table 1. All half-widths are orders of magnitude looser than the VeriDAP bounds. In most cases, the bounds are entirely vacuous. Overall, partitions from trees made from the neural network are not competitive with VeriDAP.
| Dataset (features) | VeriDAP | STreeD | CART | Random forest | XGBoost | RENTT |
|---|---|---|---|---|---|---|
| obesity | 0.01% | 2978% | 2221% | 40% | 28% | 4929% |
| german | 0.02% | 4172% | 3342% | 202% | 213% | 5217% |
| mushroom | 0.06% | 9281% | 10483% | 2179% | 9882% | 13621% |
| default | 0.02% | 6073% | 4056% | 222% | 78% | 7318% |
| automobile | 0.01% | 1884% | 2701% | 148% | 282% | 3544% |
We hope that this discussion addresses your concerns regarding soundness. If there are additional experiments that would alleviate your soundness concerns, we would be happy to use the remaining rebuttal time frame to provide those.
—
[Breiman et al., 1984]: Breiman, Leo; Friedman, J. H.; Olshen, R. A.; Stone, C. J. (1984). Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software.
[van der Linden et al., 2023]: Jacobus G. M. van der Linden, Mathijs de Weerdt, Emir Demirovic: Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming. NeurIPS 2023
[Breiman, 2001]: Breiman L (2001). "Random Forests". Machine Learning. 45 (1): 5–32.
[Chen and Guestrin, 2016]: Tianqi Chen, Carlos Guestrin: XGBoost: A Scalable Tree Boosting System. KDD 2016: 785-794
[Monke et al., 2025]: Helena Monke, Benjamin Frész, Marco Bernreuther, Yilin Chen, Marco F. Huber: Efficiently Transforming Neural Networks into Decision Trees: A Path to Ground Truth Explanations with RENTT. CoRR abs/2511.09299 (2025)
Thank you for your responses and for updating the manuscript. Now I think the paper is much stronger. Some remaining points:
W2: In your response you claim " Furthermore, VeriDAP significantly improves scalability compared to previous exact approaches, also without certified training." Where is in the paper the evidence to support this claim?
In Fig 5 the VeriDAP results are showed with the horizontal --- black line, right? why for the right most panel this line is not there?
Q1: Thank you for explaining, and I agree that your method enabled the first ground-truth interaction benchmarks on high-dimensional networks. While this is a major step forward over tree-only benchmarks, I would like to highlight that the networks in their benchmark are exclusively certifiably trained models. I would like to see this clearly in the text so readers do not over-generalize the estimator rankings to standard deep neural networks.
Rebuttal Part I
Thank you for your thorough evaluation of our paper. Your comments were very helpful in improving the discussion of our experiments. We hope that our responses below and the changes we made in our revised version (highlighted in blue in the PDF) can address your soundness concerns.
We agree that we discussed Figure 5 too briefly. Our revised paper now contains a more detailed discussion at the end of Section 6.2. The most relevant insight is that the ProxySHAP estimator is state-of-the-art for neural networks. Previous work could only benchmark using already-explainable tree-based models, since no ground truth explanations were available for neural networks. VeriDAP provides these ground-truth explanations for the first time.
Thank you for catching this. We have revised this misleading sentence in our updated submission, clarifying that Figure 1 only visualises the final exact SIIs. The runtime claims are supported by our experiment log now available in the supplementary material.
These loose bounds (> 100% for the crosses) indeed reflect the computational hardness limitation discussed in Sections 4, 5, and 8. Since SIIs and other interaction indices are #P-hard to compute exactly, our method – like all other exact methods – is unable to compute exact values for some networks. The tight bounds for the triangle network in Table 1 show that our certified-training approach addresses this limitation and enables computing exact SIIs for significantly larger search spaces. Furthermore, VeriDAP significantly improves scalability compared to previous exact approaches, also without certified training.
Beyond the search space size ∣Bd∣, the main driver of scalability is whether a network was trained with certified training. While the first network (red star symbol) was created without certified training, the second (orange square) and third (blue triangle) were created with certified training. Furthermore, VeriDAP scales furthest for the third network (blue triangle), since this network was selected from the certified-training Pareto curve (Figure 4) to achieve tight bounds.
Overall, the results in Table 1 demonstrate the success of our certified-training approach in mitigating the inherent scalability limitation of computing exact interaction indices for neural networks.
We have clarified this sentence. VeriDAP computes exact ground-truth Shapley interaction values for neural networks, specifically for larger feature spaces, where previously no exact computation was feasible (see Table 2). A natural question is then how existing stochastic approximation methods for Shapley interactions, such as KernelSHAP-IQ, ProxySHAP or ProxySPEX, perform on such realistic neural network architectures (see Figure 5). Prior to our work, such benchmarks on larger feature spaces were only feasible with tree-based models on tabular data.