acceptodds
Under review as a conference paper at ICLR 2027

Towards Tractable, Provably Exact Shapley Interactions and Beyond in Neural Networks

Abstract

Shapley interactions and the broader family of game-theoretic explanations are widely used to characterise how features contribute to neural network predictions. Yet exact computation requires reasoning over exponentially many feature subsets, and these quantities are therefore typically estimated, without provable guarantees. We introduce a verification-based algorithm for discovering additive structures within neural networks, enabling the computation of *provable upper and lower bounds on the exact values* of a broad family of game-theoretic explanations, including Shapley interactions of any order and sparse Fourier explanations. We then analyse the computational limits of this problem, proving that computing Shapley interactions remains #P-hard even for networks with as few as two ReLU neurons or a single attention layer. To address this, we introduce a robustness-based training scheme that encourages additive structure in the learned model, substantially improving the scalability of our algorithm. Experimentally, our approach handles substantially larger models and search spaces and brings exact certified game-theoretic interactions to transformer architectures for the first time. Overall, our results provide game-theoretic attributions and interactions with provable guarantees where estimation would otherwise be required, while also providing a principled basis for evaluating such estimators.

Primary area:
interpretability and explainable AI
Keywords:
Shapley Values, SHAP, Shapley Interactions

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_ghynOpenReview ↗
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
  1. 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.

  2. 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:

  1. Figure 5 is not discussed in the main text

  2. 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|.

  3. 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.

  4. 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.

  5. 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
  1. 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.

  2. 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.

  3. 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
AuthorsOpenReview ↗

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.

W1: Figure 5 is not discussed in the main text

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.

W5: 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. ".

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.

W2: It is not fully clear why there are some datasets in Figure 1 with half-widths significantly larger than 0.1%, while for others it is not.
W3: Missing discussion of why there are crosses for some |B^d| in MNIST in Table 1 while others have a tick. I think this is a limitation.

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∣|\mathbb{B}^d|, 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.

Q1: What do you mean by this sentence on 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.”?

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.

AuthorsOpenReview ↗

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)VeriDAPSTreeDCARTRandom forestXGBoostRENTT
obesity0.01%2978%2221%40%28%4929%
german0.02%4172%3342%202%213%5217%
mushroom0.06%9281%10483%2179%9882%13621%
default0.02%6073%4056%222%78%7318%
automobile0.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.

Reviewer_2RbeOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies neural network verification for Shapley interaction indices, an important problem at the intersection of explainable AI and formal verification. The proposed direction is promising, as it aims to extend verification techniques beyond individual feature attributions to interactions between features. Such interactions can provide richer insights into how neural networks represent and combine information, making their verification particularly valuable for understanding model behavior.

Critical strengths

Although I am only familiar with the SII literature and not the neural network verification literature, I believe the following are the critical strengths of the paper that support acceptance.

  • Important and timely problem. Extending neural network verification to Shapley interaction indices is a compelling and highly impactful research direction. While feature attribution provides insight into the contribution of individual features, interaction indices can reveal the higher-order relationships that are otherwise difficult to characterize.

  • Potential for more expressive explanations. Verifying interaction indices could provide stronger guarantees about how a model combines features, rather than merely explaining their individual contributions. This is particularly valuable for understanding complex neural networks and assessing the reliability of model explanations.

  • Promising research direction. The idea is both interesting and needed. Bringing formal verification to Shapley-based interaction explanations could help establish more rigorous guarantees for explainability methods. This could enable new applications in trustworthy machine learning, probably.

Critical weaknesses
  • Restriction to linear bounds. One aspect of the current approach that is somewhat surprising is its reliance on linear bounds. It would be interesting to understand whether the proposed framework could be extended to multilinear bounds, which may offer a more natural or expressive treatment of higher-order feature interactions. The paper would benefit from a clearer discussion of this design choice and the potential trade-offs involved.

  • Reliance on the baseline Shapley formulation. Another limitation is the use of the baseline Shapley value formulation. The authors should discuss how this choice affects the applicability and interpretation of the proposed method, as well as whether the framework could be extended to alternative formulations of Shapley interaction indices.

Questions for authors
  • Restriction to linear bounds. Could the linear bounds used throughout the paper be taken to the natural extension of multilinear bounds? A priori, it seems this would take much fewer regions than VeriDAP using only "DAPs". This is because any nonlinear interaction would need to be broken into all of its pieces before an SII or SFE could be applied. Are there any obvious difficulties in such an approach?

  • Reliance on the baseline Shapley formulation. Is there any possibility of extending from the baseline value function to the marginal or conditional value function? The definitions and results from the appendix seem to imply that marginal is possible but much more computationally intensive. Is there any hope of computing the conditional value or would that need to be done outside of the current framework?

5 comments

Thank you for your thorough review and the interesting questions. We have updated our submission to address your comments. All changes are highlighted in blue in the PDF.

W1/Q1: Restriction to linear bounds.

Multi-linear bounds are a very interesting direction for VeriDAP, as multi-linear bounds could significantly accelerate computing interactions. Our decision to use linear bounds is primarily informed by the limited scalability of quadratic bounds in neural network verification (e.g., [Fazlyab et al., 2022; Dathathri et al., 2020]; discussion in [Wang et al., 2021; Chiu et al., 2025]).

Beyond this, propagating multi-linear bounds requires at least quadratic memory in the hidden layer size. Assuming we only track interactions between pairs of variables, multi-linear bounds already require memory quadratic in the number of neurons on a layer when forward or backwards propagating a multi-linear bound. Forward-propagating linear bounds, which requires n×kn \times k memory for input of size nn and kk hidden-layer neurons, already exceeds the available memory on our GPU for our MNIST networks (we instead backwards-propagate linear bounds, which requires k×mk \times m memory, where m≪nm \ll n is the output dimension). For this reason, propagating multi-linear bounds that require at least k×kk \times k memory is also infeasible, since kk is much larger than nn for typical architectures.

These memory issues can be partially circumvented by only tracking a selection of higher-order terms in the bounds. We think this is an interesting approach that, however, requires further investigation. We have added it to our discussion of future work.

W2/Q2: Reliance on the baseline Shapley formulation.

As you already acknowledge in your question, our current approach already covers the marginal value function. We focus on the baseline value function for ease of presentation in the main body, but discuss the marginal value function in Appendix A.2 and present experimental results on the marginal value function in Appendix G.2. Comparing Tables 6 and 7 to Tables 1 and 2 shows that our results for the marginal value function and the baseline value function are comparable. Because modern hardware is parallel, the additional data points in the marginal value functions have limited effect on VeriDAP's runtime.

Thank you for also asking about the conditional value function that we did not consider so far. Whether we can apply bound propagation to the conditional value function depends on how the conditional expectation inside this value function is represented.

  • If the conditional expectation is an empirical distribution, we can propagate bounds through the value function in a similar way as for the marginal value function. Concretely, we can propagate bounds through v(s)=Ey∈D[f(y)∣ys=xs]=1/∣D∣∑y∈D1[ys=xs]f(y)v(\mathbf{s}) = \mathbb{E}_{\mathbf{y} \in \mathcal{D}}[f(\mathbf{y}) | \mathbf{y}_{\mathbf{s}} = \mathbf{x}_{\mathbf{s}}] = 1/|\mathcal{D}|\sum_{\mathbf{y} \in \mathcal{D}} \mathbb{1}[\mathbf{y}_{\mathbf{s}} = \mathbf{x}_{\mathbf{s}}] f(\mathbf{y}) by propagating bounds through the indicator function 1[ys=xs]\mathbb{1}[\mathbf{y}_{\mathbf{s}} = \mathbf{x}_{\mathbf{s}}]. However, empirical distributions are ill-suited for conditional distributions, due to the exact matching problem. More practical choices are discussed below.
  • If the conditional distribution is represented by a generative model, we would need to perform bound propagation over the chain of the generative model and the neural network to explain. As for the marginal distribution, this bound propagation would have to be repeated several times for each sample. If the generative model is a neural network, our bound propagation approach is directly applicable.
  • Approaches that train models with masked inputs to directly enable conditional expectations via the input, such as Covert et al. (2023), reduce the conditional value function to the baseline value function using masks. VeriDAP is directly applicable to such models.

Our main body focuses on the baseline value function, as it is the practical choice currently in wide use for explaining neural networks.

We hope these clarifications could answer your questions. If you have further suggestions for improving our paper, we would be happy to continue the discussion during the rebuttal period.

AuthorsOpenReview ↗

Rebuttal References

[Fazlyab et al., 2022] Mahyar Fazlyab, Manfred Morari, George J. Pappas:
Safety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming. IEEE Trans. Autom. Control. 67(1): 1-15 (2022)

[Dathathri et al., 2020] Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, Ian J. Goodfellow, Percy Liang, Pushmeet Kohli: Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming. NeurIPS 2020

[Wang et al., 2021] Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, J. Zico Kolter: Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification. NeurIPS 2021: 29909-29921
[Chiu et al., 2025] Hong-Ming Chiu, Hao Chen, Huan Zhang, Richard Y. Zhang: SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programming. ICML 2025

[Covert et al., 2023] Ian Connick Covert, Chanwoo Kim, Su-In Lee: Learning to Estimate Shapley Values with Vision Transformers. ICLR 2023

W1/Q1: Restriction to linear bounds.

The references provided [Fazlyab et al., 2022; Dathathri et al., 2020] seem to focus on a quadratic constraint semidefinite program approach to safety verification, rather than the bound propagation method employed herein, as used with quadratic constraints in [Zhang et al., 2018]. Further, recent work in [Chiu et al., 2025] seems to imply they have found a best-of-both-worlds result which achieves the "good" SDP results in the same time as the "fast" BP methods. Although I understand the discussion on how naive application would cost O(k^2) memory in practice, and agree that interaction sparsification might require a more serious research contribution, could the authors provide a little more detail on how this discussion connects to that in [Chiu et al., 2025] mixing SDP and BP?

W2/Q2: Reliance on the baseline Shapley formulation.

Comparing the results in Tables 1 and 6 does not give the impression that baseline SII and marginal SII are equally easy to explain. The usage of the "empirical conditional" is not convincing and should never be used for continuous variables which you consider. Verified propogation of the "baseline" through the surrogate method of [Covert et al., 2023] is convincing. This discussion reminds me, however, that the "verified marginal SII" which is computed by this work is then an exact verified result of what is itself an approximation, a somewhat unintuitive result. The marginal and conditional versions of SHAP/SII should likely be mentioned in the main body of the paper, or perhaps the authors could provide some further research papers supporting the idea that baseline removal is the practical and widely-used for explaining neural networks. Bound propagation through a separate neural generative model is an interesting line of future exploration.

Reviewer_w4U3OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

Computing exact Shapley interactions in neural networks is challenging because it requires aggregating model predictions over exponentially many feature subsets. This paper introduces VERIDAP, which combines affine bound propagation with branch-and-bound refinement to derive lower and upper bounds on game-theoretic interactions. The framework supports a broad family of interaction indices and certifies the faithfulness of sparse Fourier explanations. The paper also establishes computational hardness results for simple neural architectures and uses certified training to improve the practical scalability of explanation computation.

Critical strengths

S1: The framework provides a meaningful extension beyond first-order Shapley attribution. A shared decomposition supports multiple interaction targets and different interaction indices, while also enabling the certification of sparse Fourier explanations. This unifies several explanation tasks within a consistent mathematical framework.

S2: The method provides useful bounds before exact termination, making it valuable even when complete refinement is computationally infeasible. Its ability to both confirm and reject a proposed explanation’s faithfulness is particularly useful.

Critical weaknesses

W1: The strongest scalability improvements depend on certified training, which changes the model being explained. Similar predictive accuracy does not necessarily imply similar interaction structure.

W2: The empirical support for broad applicability is limited. The Transformer demonstration involves two images that manually segmented into 23 superpixels, using a relatively small certified-trained ViT. Most other evaluations report medians over five inputs per network and dataset. Additionally, the estimator benchmark includes only instances for which VERIDAP obtains sufficiently tight bounds, so conclusions about estimator performance may not generalize to harder, uncertified instances.

Questions for authors

Q1: Can the authors consistently distinguish tolerance-based termination from mathematical exactness and provide an implementation with floating-point sound guarantees? Would the reported faithfulness certifications remain valid after accounting for numerical errors? As Table 1 labels results with normalized half-widths below 0.1% as “exact,” while Appendix F adopts a visually indistinguishable tolerance. Although these conventions are disclosed, they do not establish equality of the bounds.

Q2: How much of the speedup from certified training comes from tighter bound propagation, and how much comes from changes in the model’s actual interaction structure? Can this be investigated with matched-accuracy comparisons, together with the training and hyperparameter-search costs?

Q3: Can the authors expand experiments to larger and commonly used datasets and more complex model backbones?

3 comments
AuthorsOpenReview ↗

Rebuttal Part I

Thank you for your thorough review. We have conducted additional experiments and updated our paper to address your concerns, as described below. All changes in the PDF are highlighted in blue.

W1 & Q2: How much of the speedup from certified training comes from tighter bound propagation, and how much comes from changes in the model’s actual interaction structure?

We have investigated this interesting question by (i) computing the complete interaction structure for networks where this is feasible and (ii) comparing the results for networks with matching accuracy from standard and certified training. We also provide training times at the end of this comment.

Interaction Structure. To investigate differences in interaction structure, we computed the full 2ⁿ Fourier transform on the Obesity, German, and Mushroom datasets. The table below contains the cosine similarity between the standard training network, the square networks (CT-Square), and the triangle networks (CT-Triangle) from Table 1.

DatasetCT-SquareCT-Triangle
obesity0.990.77
german0.620.70
mushroom0.65(no such network)

This table shows a large overlap between the interaction structure of the standard network and the certified training networks, but otherwise reveals no consistent trend. To investigate this further, we also counted how many interactions are required for an R² > 0.95 faithful Fourier representation of the different networks.

DatasetStandardCT-SquareCT-Triangle
Obesity223
German2431826
Mushroom114–

This shows that certified training does not necessarily reduce the number of relevant interactions compared with standard training, suggesting that bound tightness plays a larger role in Table 1 than the interaction structure.

Matched-Accuracy Comparison. We have selected those pairs of standard and CT-Square networks in Table 1 whose accuracy differs by at most 0.1 percentage points (see Table 5). The table below compares the VeriDAP results for these pairs of networks. The percentages in the table are normalised half-ranges as in Table 1, while runtimes indicate that VeriDAP reached a tightness below 0.1% within the indicated runtime.

NetworkMushroomBreastCMNIST 2²⁵MNIST 2³⁶MNIST 2⁴⁹MNIST 2⁶⁴
Standard104s6.4%21%31%45%49%
CT-Square102s4.4%0.1%0.2%0.2%0.3%

This comparison reveals that, at matching accuracy, VeriDAP requires a similar runtime (respectively, exceeds 600s of runtime) for both networks, while computing significantly tighter bounds for CT-Square. This indicates that VeriDAP needs to explore a similarly complex interaction structure, while bound propagation provides significantly tighter bounds, strengthening our previous observation that VeriDAP likely profits more from tighter bounds than from a simplified interaction structure from certified training.

W2: Number of samples for our transformer demonstration.

We have repeated our transformer demonstration on three additional images, so that this experiment is now also based on five inputs. We obtained comparable results on these additional inputs, as for the two inputs in our initial submission. The new results are available in Appendix G of our revised submission.

W2 & Q3: Strengthening the empirical support for broad applicability.

We have performed experiments on additional standard datasets and additional network architectures to strengthen the empirical support for the broad applicability of our algorithm. Furthermore, we have added results for three additional interaction indices and order-3 interactions. All results are available in Appendix G of our revised submission. Overall, they confirm the insights from our initial submission. In total, we have added seven new settings, clearly demonstrating the broad applicability of VeriDAP.

Our image datasets and networks are state-of-the-art in neural network verification [Brix et al., 2023; Brix et al., 2024; Kaulen et al., 2025]. Neural network verification continues to advance rapidly [Zhou et al., 2024; Zhou et al., 2025; Chiu et al., 2025]. Improved scalability and bound tightness will also expand the reach of VERIDAP.

AuthorsOpenReview ↗

Rebuttal Part II

W2: Estimator benchmark includes only instances for which VERIDAP obtains sufficiently tight bounds.

We agree that the set of included networks may not be representative of all practically relevant neural networks. We have added a discussion of this to our limitations section. However, the estimators show consistent behaviour across datasets, model size, and training regime (standard vs certified). Because of this and because estimators follow a fundamentally different approach than VeriDAP, we believe the risk to validity from using our benchmark is small. Furthermore, our benchmark allows for evaluating estimators on neural networks for the first time. Evaluating on neural networks at all, rather than using already interpretable models such as decision trees, is a significant step forward.

Q1: Can the authors consistently distinguish tolerance-based termination from mathematical exactness and provide an implementation with floating-point sound guarantees? Would the reported faithfulness certifications remain valid after accounting for numerical errors? As Table 1 labels results with normalized half-widths below 0.1% as “exact,” while Appendix F adopts a visually indistinguishable tolerance. Although these conventions are disclosed, they do not establish equality of the bounds.

Thank you for catching this ambiguity in our initial submission. We have now clarified which result tables report bounds that are exact up to a practically indiscernible tolerance and which report exact bounds up to numerical precision for a fair comparison with ExactSHAP. We have also clarified our discussion in Appendix F.

We were able to add floating-point soundness guarantees to our implementation using the approach of Müller et al. (2021). Our results under floating-point guarantees are provided in Appendix G, mirroring the results in our main body. To the best of our knowledge, we are the first to compute exact Shapley explanations under floating-point soundness guarantees. Neither ExactSHAP nor TreeSHAP or LinearSHAP bound the floating-point error of their solutions.

Q2: Training and Hyperparameter-Search Cost.

We recorded the GPU-time required for tuning on the FashionMNIST dataset. Certified training hyperparameter search took 1823s for 100 trials, while standard hyperparameter search required 232s for 25 trials. Regarding individual training time, standard training takes 24s, while training CT-Square takes 29s and training CT-Triangle takes 66s.

Overall, your comments helped us improve our paper by adding important clarifications and additional experiments to support the broad applicability of our approach. If you have additional questions, we would be happy to continue the discussion during the rebuttal timeframe.

—

[Kaulen et al., 2025]: Konstantin Kaulen, Tobias Ladner, Stanley Bak, Christopher Brix, Hai Duong, Thomas Flinkow, Taylor T. Johnson, Lukas Koller, Edoardo Manino, ThanhVu H. Nguyen, Haoze Wu: The 6th International Verification of Neural Networks Competition (VNN-COMP 2025): Summary and Results. CoRR abs/2512.19007 (2025)

[Brix et al., 2024]: Christopher Brix, Stanley Bak, Taylor T. Johnson, and Haoze Wu. The fifth international verification of neural networks competition (VNN-COMP 2024): Summary and results. CoRR, abs/2412.19985, 2024. doi: 10.48550/arXiv.2412.19985

[Brix et al., 2023]: Christopher Brix, Stanley Bak, Changliu Liu, and Taylor T. Johnson. The fourth international verification of neural networks competition (VNN-COMP 2023): Summary and results. CoRR, abs/2312.16760, 2023. doi: 10.48550/arXiv.2312.16760.
[Zhou et al., 2024]: Duo Zhou, Christopher Brix, Grani A. Hanasusanto, and Huan Zhang. Scalable neural network verification with branch-and-bound inferred cutting planes. In NeurIPS, pp. 29324–29353, 2024

[Zhou et al., 2025]: Duo Zhou, Jorge Chavez, Hesun Chen, Grani A. Hanasusanto, and Huan Zhang. Clip-and-Verify: Linear constraint-driven domain clipping for accelerating neural network verification. In NeurIPS, 2025

[Chiu et al., 2025]: Hong-Ming Chiu, Hao Chen, Huan Zhang, and Richard Y. Zhang. SDP-CROWN: Efficient bound propagation for neural network verification with tightness of semidefinite programming. In ICML, 2025

[Müller et al., 2021]: Christoph Müller, François Serre, Gagandeep Singh, Markus Püschel, Martin T. Vechev: Scaling Polyhedral Neural Network Verification on GPUs. MLSys 2021

AuthorsOpenReview ↗

Update for Second Revision

W2: Estimator benchmark includes only instances for which VERIDAP obtains sufficiently tight bounds.

Following the discussion with reviewer ghyn, we have added a figure to our appendix (Figure 9 of our second revision) comparing the estimator results for standard training networks and certified training networks on inputs where VeriDAP provides ground-truth information for both the standard training network and the certified training networks. The figure visualises that all estimators follow the same trends for both standard training and certified training networks.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.