- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
While neural network verification usually relies on linear relaxations of nonlinear network components, the excessive relaxations errors introduced by such approaches can be problematic for larger networks and make successful verification infeasible. Semidefinite Programming-based relaxations can instead be used to more accurately model the behaviour of the network, albeit at a higher computational cost. This paper proposes SL-SDP, an improved SDP encoding for ReLU neural networks which scales better with the number of neurons in the network and therefore enables the verification of larger models. The verification problem is split into multiple smaller problems for each layer, and an SDP is used to find the smallest ball that contains the preactivations of the next layer. A Schur complement is then used to eliminate the variables of the previous layer and to obtain a tighter, quadratic constraint that is propagated forward. The method can be tightened by using bounds from the linear -CROWN verifier, and even tighter relaxations can be obtained by considering more layers at each step of the propagation which comes at an increased computational cost. The method is evaluated on various randomly initialised networks as well as some neural networks trained on the MNIST dataset where the authors show that it produces tighter relaxations than competing approaches.
Critical strengths
- The idea of propagating quadratic constraints rather than linear constraints or concrete bounds as has previously been proposed in the literature seems novel. It allows the method to maintain a more accurate representation of the network's behaviour, and the experimental evaluation shows that this enables the verification of properties which the standard SDP encoding cannot solve.
- Since the authors propagate ellipsoids through the network, they are able to obtain tighter intermediate bounds (which have previously been identified as a weakness in SDP verifiers and which other approaches can only tackle by inserting bounds from bound propagation-based verifiers into the problem).
Critical weaknesses
- The authors do not clearly identify where the method's gains stem from. It seems to me that SL-SDP can never produce a tighter final bound than DeepSDP if they are both provided with the same activation constraints. SL-SDP's main advantage therefore seems to be that it can use tighter intermediate bounds rather than having to only rely on bounds from -CROWN like DeepSDP, which is inconsistent with some statements in the paper such as "maintaining tighter over-approximations than monolithic SDPs". the actual SL-SDP method also seems to be looser than DeepSDP in every plot and only the more expensive SL-SDP-2L is able to provide tighter bounds than DeepSDP. In order to clearly identify where the approach's advantage comes from, DeepSDP should be run with intermediate bounds computed by SL-SDP and SL-SDP-2L.
- On trained networks, SL-SDP seems to verify fewer or as many cases as -CROWN which I find surprising. Some important baselines are also missing from the comparison, e.g. for perturbations the method should be compared to [1] and [2]. The paper also excludes DeepSDP from the experiments for larger networks, but [3] shows that existing SDP approaches do scale to MNIST networks with 9 layers (100 neurons each) or 6 layers (200 neurons each). According to the paper's argumentation, these approaches should compute the same bounds as DeepSDP and seem to scale better, hence, a comparison should be run. The experiments are also restricted to rather small networks with at most 9 layers and 150 neurons per layer, so it remains unclear to me whether the proposed approach would actually scale to larger networks such as the ones from the verification of neural networks competition (VNN-COMP).
[1] Chiu, H. M., Chen, H., Zhang, H., & Zhang, R. Y. (2025). Sdp-crown: Efficient bound propagation for neural network verification with tightness of semidefinite programming. arXiv preprint arXiv:2506.06665.
[2] Chiu, H. M., & Zhang, R. Y. (2023, July). Tight certification of adversarially trained neural networks via nonconvex low-rank semidefinite relaxations. In International Conference on Machine Learning (pp. 5631-5660). PMLR.
[3] Lan, J., Brückner, B., & Lomuscio, A. (2023, June). A semidefinite relaxation based branch-and-bound method for tight neural network verification. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 37, No. 12, pp. 14946-14954).
Questions for authors
- Could the comparison suggested above with the tighter intermediate bounds supplied to DeepSDP be run? Are the input constraints that are used for DeepSDP and SL-SDP identical?
- Where do the authors obtain the MLPs trained on MNIST, how are they trained and what is their accuracy on the dataset? The Chiu and Zhang paper from above [2] argues that SDPs are mainly beneficial for adversarially trained neural networks.
- What version of -CROWN is used? Are cutting planes used, if so, are they generated using a MILP solver (GCP-CROWN) or using the more recently introduced branch-and-bound-inferred cutting planes?
- How does the runtime scale with the network size? Do the authors expect the proposed method to scale to larger neural networks?
- Why is the average runtime for -CROWN for 9x150 4800 seconds? The text states that the timeout here is 1.5 hours, i.e. 5400 seconds and since no sample was verified according to the table, no query should have terminated early and the average runtime should be 5400 seconds?
- Does using more than two overlapping layers (SL-SDP-3L) yield any benefits? Do the authors observe a gain similar to the one when switching from SL-SDP to SL-SDP-2L?
3 comments
Response to Reviewer ARNc (Part 2/2)
Q2: Training Details of the MNIST MLPs
Response: Both networks (MLP 4×100 and MLP 9×150) were adversarially trained on MNIST using -PGD attacks with perturbation radii of and . We have added these training details to Section 4 of the revised manuscript.
Q3: -CROWN Version and Cutting-Plane Configuration
Response: We used standard -CROWN (Wang et al., 2021) via the official alpha-beta-CROWN complete verifier (complete_verifier/abcrown.py). Cutting planes (MILP-based GCP-CROWN or BaB-inferred BICCOS) were not enabled, because the cutting-plane generators in alpha-beta-CROWN are formulated for -box MILP encodings rather than -norm perturbations (which comprise four of our six settings). Also, on configurations, -CROWN already establishes a good performance and we have acknowledged its good performance. To maintain a consistent baseline across all configurations, we used standard -CROWN (Wang et al., 2021) throughout.
Q4: Runtime Scaling with Network Size
Response: For a fixed layer width, the runtime of our method scales linearly with network depth , since the same fixed-size layer-wise SDP subproblem is solved sequentially for each additional layer (as demonstrated in Figure 2, right). This is a major improvement over DeepSDP, where the dimension of the monolithic LMI grows with the total number of layers. However, as the layer width increases, the dimension of each layer-wise SDP subproblem increases accordingly, so scaling to very wide networks remains an important direction for future work.
Q5: Timeout Budget for MLP 9×150 (4,800s vs. 1.5 Hours)
Response: We thank the reviewer for catching this typo in our initial manuscript. All methods on MLP 9×150 were given a timeout budget of seconds ( minutes), which was inadvertently stated as hours in the table caption. We have fixed this in the revised manuscript.
Q6: Extending Overlap Beyond Two Layers (SL-SDP-3L)
Response: In SL-SDP-3L, the overlap increases substantially because every hidden layer appears in three consecutive subproblems (spanning four layer states ), making each SDP significantly larger. Because interior-point solver time does not grow efficiently with LMI dimension, we found that extending the overlap beyond two layers is not computationally efficient relative to the marginal tightness gain over SL-SDP-2L.
We thank the reviewer once again for their constructive feedback and valuable time, which helped us significantly improve the manuscript.
References:
[1] Chiu, H. M., Chen, H., Zhang, H., & Zhang, R. Y. (2025). SDP-CROWN: Efficient bound propagation for neural network verification with tightness of semidefinite programming. arXiv:2506.06665.
[2] Chiu, H. M., & Zhang, R. Y. (2023). Tight certification of adversarially trained neural networks via nonconvex low-rank semidefinite relaxations. In ICML (pp. 5631-5660).
[3] Lan, J., Brückner, B., & Lomuscio, A. (2023). A semidefinite relaxation based branch-and-bound method for tight neural network verification. In AAAI (Vol. 37, No. 12, pp. 14946-14954).
Follow-up as the discussion period concludes
Dear Reviewer,
As the discussion period concludes in less than 24 hours, we wanted to kindly follow up and ensure that you had an opportunity to review our responses and revised manuscript. Following your feedback, we (1) added ablation experiments (w/o BT) in Figures 2 and 3 to isolate the impact of dynamic intermediate bound tightening, (2) evaluated the official implementation of SDP-CROWN [1] and discussed [2, 3] in Section 4, (3) doubled the evaluated test samples from 25 to 50 (and will double to 100 in the final version) in Table 1, and (4) added MNIST PGD-training details and -CROWN configurations.
We would be happy to provide any further clarification before the discussion period closes. If our responses and revisions have satisfactorily addressed the points raised in your review, we would greatly appreciate your consideration of updating your evaluation accordingly. Thank you again for your time and constructive feedback.
Response to Reviewer ARNc (Part 1/2)
We sincerely thank the reviewer for their insightful technical questions and helpful pointers to related literature. Please also see our General Response above for a summary of all updates to the manuscript (highlighted in blue in the revised PDF).
W1 & Q1: Source of Tightness Gains, Intermediate Bound Ablation, and Input Constraints
Response: As the reviewer rightly points out, SL-SDP decomposes the monolithic SDP and solves sequential layer-wise SDPs using surrogate intermediate objectives Hi(ρi) before propagating the resulting QC Gi to the next layer. While decomposing the monolithic SDP and using surrogate objectives inherently introduces some relaxation loss, our framework compensates through two sources of improvement over standard DeepSDP: (i) a more expressive ReLU QC formulation that bounds both positive and negative splits (Lemma 1), and (ii) dynamic intermediate pre-activation bound tightening via ellipsoidal projection (Proposition 3), whereas DeepSDP must rely on static baseline intermediate bounds computed upfront (which loosen rapidly with depth and perturbation size).
To illustrate the impact of dynamic bound tightening directly, we added w/o BT ablation curves (without updating intermediate bounds along the layers) to the reachability plots in Figures 2 and 3. The results show that while baseline bounds suffice in shallower settings, disabling dynamic bound tightening eliminates almost all of SL-SDP-2L's tightness advantage over DeepSDP at larger depths and perturbation radii. We have revised Section 4 to state these two sources of improvement explicitly. Finally, we confirm that the input constraints Pin(ω0) (ℓ∞ or ℓ2 balls) are identical across all evaluated methods.
W2: Comparison with β-CROWN and SDP Baselines [1, 2, 3]
Response: Given the different aspects of neural network verification, no single method dominates across all regimes, and our goal is to provide a practical trade-off across perturbation scales and network depths: