acceptodds
Under review as a conference paper at ICLR 2027

SL-SDP: A Scalable Layer-by-Layer SDP Approach for Robustness Analysis of Deep Neural Networks

Abstract

Ensuring the robustness of neural networks against small input perturbations is essential for their safe deployment in safety-sensitive applications. While semidefinite programming (SDP) provides a principled route to certified robustness, monolithic end-to-end formulations scale poorly due to the global coupling of decision variables across all layers. To overcome this computational bottleneck, this paper develops a scalable layer-by-layer SDP (SL-SDP) scheme that decomposes the monolithic verification problem into a sequence of smaller, tractable SDPs linked through propagated quadratic constraints. Crucially, our recursive approach leverages Schur complement to derive tight, adaptive intermediate bounds with an explicit ellipsoidal interpretation, which in turn yield inexpensive neuron-wise pre-activation intervals and enable more precise abstraction of activation functions. We show how such bounds can be effectively used to tighten the relaxations of ReLU layers. Empirical results demonstrate that SL-SDP significantly improves scalability over end-to-end SDP approaches while preserving accuracy.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Robustness Analysis of Neural Networks, Semidefinite Programming

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_ARNcOpenReview ↗
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 α\alpha-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 α\alpha-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 β\beta-CROWN which I find surprising. Some important baselines are also missing from the comparison, e.g. for l2l_2 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 β\beta-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 β\beta-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
AuthorsOpenReview ↗

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)H_i(\rho_i) before propagating the resulting QC GiG_i 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)P_{in}(\omega_0) (ℓ∞\ell_\infty or ℓ2\ell_2 balls) are identical across all evaluated methods.

W2: Comparison with β\beta-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:

  • Comparison with β\beta-CROWN: When the input perturbation set is small, linear relaxations remain relatively tight and many neurons are stable, allowing the branch-and-bound refinement in β\beta-CROWN to perform very well. However, when the perturbation radius is larger (especially under ℓ2\ell_2-norm perturbations), linear relaxations become overly loose and β\beta-CROWN collapses, verifying only 11 to 22 samples before timing out, whereas SL-SDP and SL-SDP-2L certify a substantial number of samples. We have also doubled our evaluation in Table 1 from 25 to 50 test samples (and will double it again to 100 in the final version). The new results confirm that all relative performance trends hold consistently.
  • Comparison with SDP-CROWN [1]: In response to the reviewer’s request, we evaluated the official implementation of SDP-CROWN [1] across all ℓ2\ell_2-norm settings in Table 1 (the setting for which it is specifically designed). Across all tested configurations on both networks, SDP-CROWN verified zero samples (0/500/50) and produced robustness margins substantially looser than α\alpha-CROWN. This is unsurprising, as the experiments in [1] (Section 6 and Appendix A) are conducted exclusively on networks trained via a specialized routine enforcing 1-Lipschitz layers, implying its dependence on a very specific training routine. We have added this result to Section 4.
  • Comparison with BM-Full [2]: Method [2] (BM-Full) solves the same monolithic end-to-end SDP relaxation as DeepSDP (already evaluated in Table 1), using a nonconvex Burer-Monteiro factorization initialized with neuron-wise LP-All bounds (requiring MATLAB and the commercial Artelys Knitro solver). Since DeepSDP already represents the exact monolithic SDP relaxation in our benchmarks, including a separate evaluation was not feasible within the limited rebuttal period; however, we have now discussed [2] in the revised manuscript and would be happy to include a dedicated empirical comparison in the final version.
  • Scaling of SDP methods in [3]: The chordal SDP approaches evaluated in [3] rely critically on pruning stably inactive neurons under very small ℓ∞\ell_\infty perturbations (ϵ∈{0.015,0.026}\epsilon \in \{0.015, 0.026\}) and were executed on significantly more powerful hardware. In fact, in [3, Table 1], the runtime on their 9-layer 9×100 network is nearly half that of their 6-layer network because a larger fraction of neurons were stably inactive and pruned away. Thus, their reported scaling stems from testing small perturbations with high neuron stability rather than overcoming the SDP dimensionality bottleneck when most neurons are unstable (as in our larger ℓ2\ell_2 and ℓ∞\ell_\infty settings). Furthermore, those implementations and their clique-merging heuristics are closed-source; therefore, we focused on DeepSDP to evaluate our method against monolithic SDPs.
AuthorsOpenReview ↗

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 ℓ2\ell_2-PGD attacks with perturbation radii of ϵ=1.0\epsilon = 1.0 and ϵ=0.6\epsilon = 0.6. We have added these training details to Section 4 of the revised manuscript.

Q3: β\beta-CROWN Version and Cutting-Plane Configuration

Response: We used standard β\beta-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 ℓ∞\ell_\infty-box MILP encodings rather than ℓ2\ell_2-norm perturbations (which comprise four of our six settings). Also, on ℓ∞\ell _ \infty configurations, β\beta-CROWN already establishes a good performance and we have acknowledged its good performance. To maintain a consistent baseline across all configurations, we used standard β\beta-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 LL, 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 nin_i 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 4,8004{,}800 seconds (8080 minutes), which was inadvertently stated as 1.51.5 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 [1;xi−3;xi−2;xi−1;xi][1; x_{i-3}; x_{i-2}; x_{i-1}; x_i]), 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).

AuthorsOpenReview ↗

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 β\beta-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.

Reviewer_KqdWOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper is motivated by the gap that current SDP relaxation is expensive and causes large conservatism. Authors propose a sequential local SDP relaxation through a generalized Schur complement based constraint layer by layer. They build the theory for the soundness of propagation and the local tightening. Experimental results validate the proposed method on synthetic and MNIST datasets. SL-SDP is substantially faster than DeepSDP in several settings, while SL-SDP-2L generally improves certification over SL-SDP at additional cost. Performance depends strongly on the network and perturbation regime. The main limitations lie in the lost of dependencies, incomplete verification, and lacking generalization in extensive architectures like recurrent, and attention architectures.

Critical strengths

The strongest points are:

  1. Decomposing the expensive verification problem into small and cheap sequential subproblems is useful to improve scalability. This directly addresses the computational bottleneck of monolithic SDP and gives the method a clear practical purpose.
  2. The mathematical derivation in Theory 1 provides the conditions of soundness.
  3. The propagated constraint is an appealing way to take advantage of geometric information and provides analytical pre-activation intervals. Obtaining these intervals without separate optimization problems is a useful feature, especially because they subsequently improve the activation relaxations.
  4. The reuse of the intermediate computation saves much computation expense.
Critical weaknesses

The weak points are:

  1. On page 1, the “preserving accuracy” is overstated based the empirical findings. On the smaller network at ℓ2,ϵ=1.0\ell_2,\epsilon=1.0, certification drops from DeepSDP’s 20/25 to 6/25 for SL-SDP and 11/25 for SL-SDP-2L. At ℓ∞,ϵ=0.05\ell_\infty,\epsilon=0.05, β-CROWN certifies 23/25, compared with 13/25 and 17/25. These are substantial losses despite runtime benefits.
  2. On page 8-9 and 19, the evaluation is too narrow to claim the broad scalability. The trained-network experiments use one dataset, two MLPs, and only 25 examples. There are no systematic width sweeps, memory measurements, or reported variation across seeds. The results support improved scalability relative to the tested SDP baselines on these architectures.
  3. On page 7-10, additional validation experiments are needed. First, SDP-CROWN is cited but not evaluated. Second, The authors attribute some improved tightness to better intermediate intervals, but sufficient ablation experiments are lacking to demonstrate how much improvement comes form the interval information.
  4. On page 6, Proposition 1 establishes non-strict containment, so equality is possible. The phrase “strictly enclosed” is therefore too strong. The paper also provides no quantitative wrapping-error bound or theorem guaranteeing that two-layer propagation always improves the final certificate.
  5. For Figure 2, plain SL-SDP produces larger regions than the monolithic baselines in the displayed examples. The stronger tightness results chiefly concern SL-SDP-2L. Also, Monte Carlo samples are an inner sample of the reachable set, not an exact reachable-set reference.
Questions for authors

On page8-10: Can you compare with SDP-CROWN and evaluate more samples, larger widths and depths, and additional architectures?

5 comments
AuthorsOpenReview ↗

Response to Reviewer KqdW (Part 1/2)

We thank the reviewer for their careful reading of our paper and for providing constructive feedback and insightful questions. Please also see our General Response above for a summary of all updates to the manuscript (highlighted in blue in the revised PDF). Below, we address the comments in detail.

W1: Framing of Accuracy vs. Scalability

Response: We have revised the abstract and main text to avoid overstating uniform accuracy preservation. 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:

  • Comparison with β\beta-CROWN: When the input perturbation set is small (such as ℓ∞,ϵ=0.05\ell_\infty, \epsilon=0.05 on MLP 4×100), many neurons remain stable and linear relaxations combined with branch-and-bound (β\beta-CROWN) are highly effective, while our single-pass methods still achieve competitive verification at lower runtime. Conversely, when the input perturbation set is larger (e.g., ℓ2,ϵ=1.0\ell_2, \epsilon=1.0 on MLP 4×100 or ℓ2,ϵ=0.5\ell_2, \epsilon=0.5 on MLP 9×150), linear relaxations become overly loose and β\beta-CROWN almost fails to verify any samples (11 vs. 1414 and 2727 on MLP 4×100, and 22 vs. 1111 and 1515 on MLP 9×150 for SL-SDP and SL-SDP-2L) before timing out, whereas SL-SDP and SL-SDP-2L successfully certify a significant number of instances.
  • Comparison with DeepSDP: When DeepSDP is computationally tractable (MLP 4×100), its monolithic formulation retains all cross-layer couplings and achieves higher certified accuracy at the cost of much higher runtime. On deeper networks (MLP 9×150), DeepSDP times out completely across all settings, while SL-SDP and SL-SDP-2L remain scalable and verify up to 46 samples (exceeding β\beta-CROWN).

W2, W3 & Q: Additional Experiments (SDP-CROWN, Ablation, and Expanded Evaluation)

Response: In response to the reviewer’s request, we have conducted additional experiments and expanded our evaluation in the revised manuscript:

  • Comparison with SDP-CROWN: We evaluated the official implementation of SDP-CROWN (Chiu et al., 2025) across all ℓ2\ell_2-norm settings in Table 1 (the setting for which it is specifically developed). Across all tested configurations on both MLP 4×100 and MLP 9×150, SDP-CROWN verified zero samples (0/500/50), yielding certified margins substantially looser than the α\alpha-CROWN baseline. This is unsurprising, as the experiments conducted by Chiu et al. (2025, Section 6 and Appendix A) exclusively consider networks trained using a specialized spectral-norm routine that enforces 1-Lipschitz layers. On standard or PGD-trained networks, its inter-layer scaling factor blows up with depth, causing the bounds to collapse. We have added this result to Section 4.
  • Ablation on intermediate pre-activation intervals: While sequential decomposition incurs some relaxation loss compared to a monolithic SDP, our method compensates through two mechanisms: (i) our refined ReLU QC (Lemma 1) and (ii) dynamic intermediate bound tightening (Proposition 3). To visualize the impact of bound tightening, we added w/o BT ablation curves (keeping the initial α\alpha-CROWN bounds fixed throughout) to Figures 2 and 3, showing that while baseline bounds suffice for shallower networks or smaller radii, dynamic interval refinement is critical for enabling SL-SDP-2L to achieve tighter bounds than DeepSDP at larger depths and perturbation radii.
  • Expanded sample size and scalability scope: We have doubled the number of evaluated test samples in Table 1 from 25 to 50 (and will expand to 100 samples in the final version). We observed that the verification rates and runtime trends remain consistent across the larger sample set and we expect this to remain the same for the next doubling in the number of samples. In addition, Figure 2 (right) and Appendix B.7 evaluate depths from L=5L=5 to L=9L=9 on synthetic networks, demonstrating near-linear runtime growth with depth compared to the steep growth of monolithic SDPs. Finally, we have clarified the text to avoid overclaiming improved scalability relative to existing SDP baselines.
AuthorsOpenReview ↗

Response to Reviewer KqdW (Part 2/2)

W4: Theoretical Clarifications on Proposition 1 and Wrapping Error

Response: We thank the reviewer for catching this. Since Proposition 1 proves Hi(ρi⋆)−Gi⪰0H_i(\rho _ i^\star) - G _ i \succeq 0 (X~i⊆X~iH\tilde{\mathcal{X}} _ i \subseteq \tilde{\mathcal{X}} _ i^H), equality is mathematically possible; we have changed "strictly enclosed" to "enclosed" in the proof sketch of Proposition 1. Furthermore, because each layer-wise SDP optimizes a localized surrogate objective through nonlinear ReLU relaxations, deriving either a closed-form quantitative bound on the cumulative wrapping error or a universal guarantee that two-layer propagation strictly improves the final certificate for all weight matrices is analytically intractable. However, at any given step, SL-SDP-2L retains the cross-layer quadratic couplings between xi−1x _ {i-1} and xix _ i that single-layer SL-SDP projects out, which consistently yields tighter bounds in practice.

W5: Figure 2 Discussion and Monte Carlo Approximation

Response: We agree with the reviewer and have clarified in Section 4 and Appendix B.7 that single-layer SL-SDP prioritizes runtime speed (producing slightly looser regions than DeepSDP in Figure 2), whereas the two-layer variant SL-SDP-2L achieves tighter over-approximations than DeepSDP as the perturbation radius and network depth increase. We have also updated the captions of Figures 2 and 3 to state accurately that the Monte Carlo point cloud represents an inner empirical approximation of the reachable set rather than the exact reachable set.

We appreciate the reviewer's time and helpful feedback, which have helped us improve our manuscript.

AuthorsOpenReview ↗

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. In particular, following your suggestions, we (1) added an empirical comparison with SDP-CROWN (Section 4), (2) added ablation experiments (w/o BT) in Figures 2 and 3 isolating the gain from dynamic intermediate intervals, (3) doubled the MNIST sample size in Table 1, and (4) refined our accuracy framing and the wording in Proposition 1.

Please let us know if we can provide any further clarification before the discussion period closes. If our responses and revisions satisfactorily addressed the points raised regarding the paper’s soundness and evaluation, we would be grateful if you would consider updating your assessment accordingly. Thank you again for your time and constructive feedback.

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

This paper proposes SL-SDP, a layer-wise SDP framework for DNN robustness certification. Existing SDP methods encode inputs, activations, and the safety property as quadratic constraints (QCs) and couple all layers into one monolithic LMI of size (1+N)×(1+N)(1+N)\times(1+N), which is prohibitive for deep networks. The paper replaces this with a sequential scheme. Each layer solves a small SDP, then applies the Schur complement to eliminate the previous layer's variables, yielding an adaptive ellipsoidal QC GiG_i that is propagated forward. Proposition 1 shows GiG_i is strictly tighter than naively propagating the fixed target constraint Hi(ρi⋆)H_i(\rho_i^\star), since it preserves cross-neuron dependencies and dampens the wrapping effect. Experiments on synthetic reachable-set visualization and MNIST MLPs show certification at depths where monolithic DeepSDP times out.

Critical strengths

1. A clean, provable decomposition mechanism. The Schur complement eliminates xi−1x_{i-1} to produce a propagated QC GiG_i that lives only on xix_i. Proposition 1 formally shows that {Gi}⊆{Hi(ρi⋆)}\{G_i\}\subseteq\{H_i(\rho_i^\star)\}, so the tightness gain over naive layer-wise propagation is guaranteed, not merely observed.

2. Scalability demonstrated where monolithic SDP provably fails. On MLP 9×150, DeepSDP returns timeouts across all three perturbation settings, while SL-SDP certifies 6, 22, and 5 samples. The runtime plot shows flat growth with depth versus steep growth for end-to-end methods, which is the paper's central claim and it is directly supported.

3. Faithful reporting of the tightness–scalability trade-off. The paper concedes that any sequential decomposition incurs wrapping error, reports SL-SDP as strictly weaker than DeepSDP in tightness on 4-layer networks, and does not overclaim optimality.

Critical weaknesses

1. The empirical evidence is too thin for the claim's strength. Experiments cover MNIST MLPs only, with 25 test samples, no CNN, ResNet, transformer, or nonlinear activation. Yet the framework is presented as a general replacement for monolithic SDP. At n=25n=25, the gap between SL-SDP-2L (11) and DeepSDP (20) verified samples is within noise of a small-sample regime.

2. The method is consistently dominated in tightness, and no bound on that loss is given. On MLP 4×100 ℓ2(ϵ=1.0)\ell_2(\epsilon=1.0): DeepSDP certifies 20, SL-SDP only 6. The paper proves Gi⪯HiG_i \preceq H_i (better than naive propagation) but never relates GiG_i to the monolithic optimum, which Proposition-wise is exactly the relevant benchmark. The central promise "competitive tightness" is therefore unverified theoretically and unmet empirically.

3. Novelty is narrower than framed, and a key baseline is dropped. The approach is explicitly inspired by existing similar approaches, transferring recursive QC propagation from Lipschitz estimation to verification. Separately, the observation that DeepSDP and LayerSDP yield identical geometric bounds is used to drop LayerSDP from all large experiments; this is a convenient elimination of the closest competing decomposition method rather than a comparison against it. In this sense, the contribution of the work is merely incremental.

**4. Algorithm 1 shall be included in the main text because of its central contribution of the paper. You can save several space and put it in although the space is limited.

Questions for authors

Q1. Can you bound the gap between GiG_i and the monolithic relaxation, either theoretically or via a measured proxy (e.g., reachable-set volume) on networks where DeepSDP still runs? Proposition 1 only establishes improvement over naive propagation.

Q2. On MLP 4×100 with ℓ2(ϵ=1.0)\ell_2(\epsilon=1.0), SL-SDP certifies 6 samples against DeepSDP's 20, at 6× lower runtime. What is the tightness-per-second trade-off curve across the timeout budget? If SL-SDP-2L were given 2151 s, would it reach 20? This distinguishes a fundamental limitation from a budget artifact.

Q3. All SDP baselines share α-CROWN intermediate bounds. Are the intermediate bounds re-derived by your propagation for later layers, or fixed from α-CROWN throughout? The text states both (computing "more accurate intermediate bounds than α-CROWN" vs. "all methods use α-CROWN as baseline"), and this determines whether improvements are attributable to propagation or to baseline choice.

Q4. Why do the propagation direction and layer count favor the 9-layer network so strongly (SL-SDP: 22 verified at ℓ2(ϵ=0.3)\ell_2(\epsilon=0.3) vs. β-CROWN's 21, DeepSDP timeout) yet underperform on 4 layers? Is there a depth threshold below which the monolithic formulation is strictly preferable, and if so, how should practitioners choose?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Kko1 (Part 1/2)

We sincerely thank the reviewer for their time, thoughtful evaluation, and constructive feedback. Please also see our General Response above for a summary of all updates to the revised manuscript (highlighted in blue in the revised PDF). Below, we address the weaknesses and questions in detail.

W1: Empirical Scope, Sample Size, and Architectures

Response: We would like to clarify that our work, similar to existing SDP baselines including DeepSDP and LayerSDP, does not support ResNets or Transformers and computationally does not scale to CNNs. Furthermore, although our framework, similar to DeepSDP, supports other nonlinear activation functions representable via QCs (including tanh and Leaky-ReLU), we focused on standard ReLU networks because most competing baselines are developed exclusively for ReLU networks, which remain the established benchmark in the literature. Regarding the sample size, due to computational limits, we evaluated all methods on 25 samples in the initial submission. In response to the reviewer’s request, we have doubled this to 50 samples in the revised version and will double it again to 100 samples in the final version. The new results confirm that all relative performance trends hold consistently and we expect that this will not change by doubling the number of samples again.

W2 & Q1: Tightness Gap Relative to the Monolithic SDP

Response: We agree with the reviewer that, for shallower networks where the monolithic SDP remains tractable (e.g., MLP 4×100), DeepSDP achieves higher certified accuracy. Because our layer-by-layer framework optimizes intermediate surrogate objectives Hi(ρi)H_i(\rho_i) and eliminates prior layer variables via the Schur complement at each step, deriving a closed-form analytical bound on the tightness gap relative to the global monolithic optimum is non-trivial across multiple nonlinear layers. Instead, our framework is designed to offer a favorable tradeoff between scalability and tightness: as shown in Figure 2 and Table 1 (MLP 9×150), when network depth increases, the monolithic SDP becomes computationally intractable (timing out completely), whereas SL-SDP and SL-SDP-2L remain fast and certify safety where end-to-end SDP methods fail. We have revised the abstract and main text to state this tradeoff explicitly.

W3: Novelty over Recursive Lipschitz Estimation and Why LayerSDP Was Excluded from Table 1

Response:

  • Novelty over Lipschitz estimation (Xu & Sivaranjani, 2024): Although both are motivated by sequential Schur-complement elimination, global Lipschitz estimation and local robustness verification are fundamentally different problems. Lipschitz estimation operates on zero-centered homogeneous differences (Δxi=xi−yi\Delta x_i = x_i - y_i) using global sector bounds, with no nominal input point, no constant offset term, and no intermediate pre-activation bounds (applying global sector bounds to local verification yields vacuous certificates). To make sequential SDP propagation effective for local verification, our work: (i) operates on inhomogeneous lifted QCs over [1;xi][1; x_i] and proves that the Schur complement GiG_i forms a bounded ellipsoid E(xˉi,Ei)\mathcal{E}(\bar{x} _ i, E _ i) around an adaptively shifted center (Propositions 1 and 2); (ii) derives closed-form analytical pre-activation intervals v^±a^\hat{v} \pm \hat{a} from this ellipsoid at zero extra solver cost (Proposition 3) to iteratively tighten subsequent ReLU QCs (Lemma 1); and (iii) introduces an overlapping two-layer formulation (SL-SDP-2L, Section 3.3) that propagates joint cross-layer constraints Gi,i−1G_{i,i-1} to tighten bounds for both layers ii and i+1i+1.
  • Why LayerSDP was excluded from Table 1: We did not exclude LayerSDP to evade comparison. In fact, by Proposition 3 of Batten et al. (2021), LayerSDP is an exact chordal reformulation of the monolithic SDP that couples all layers simultaneously via equality constraints; it is not a sequential decomposition method like ours that breaks a global problem into smaller subproblems, but rather reformulates the same underlying SDP as DeepSDP (differing only by an optional linear cut constraint that proved redundant in our first experiment). Thus, the DeepSDP row in Table 1 already reports the certified accuracy achievable by LayerSDP. Regarding runtime, the official LayerSDP codebase is closed-source. We implemented LayerSDP in CVXPY and also tested a direct low-level MOSEK implementation (bypassing the modeling parser, as noted in Batten et al., 2021), which did not improve scalability. Because LayerSDP introduces dense equality constraints to stitch overlapping layer cliques, it is severely bottlenecked when most neurons are unstable and consistently ran out of memory across all six configurations in Table 1. We have clarified this in Section 4.
AuthorsOpenReview ↗

Response to Reviewer Kko1 (Part 2/2)

W4: Moving Algorithm 1 to the Main Text

Response: We thank the reviewer for this helpful suggestion and have moved Algorithm 1 into Section 3.2 of the main text.

Q2: Tightness-per-Second Tradeoff and Timeout Budget

Response: We would like to clarify a key algorithmic distinction: unlike branch-and-bound methods (such as β\beta-CROWN) that iteratively refine bounds until a timeout budget is exhausted, SL-SDP and SL-SDP-2L are single-pass sequential algorithms. They solve one convex SDP per layer (or per two-layer window) to optimality in a single forward sweep and then terminate. On MLP 4×100 (ℓ2,ϵ=1.0\ell_2, \epsilon=1.0), SL-SDP-2L finishes its complete forward pass in 426.85s on average; giving it 2,118s does not change its verified count because the optimization has already terminated at its layer-wise optimum. In our framework, trading additional runtime for tighter bounds is achieved structurally by increasing the overlapping window size, e.g., moving from 1-layer SL-SDP (14 verified, 356s) to 2-layer SL-SDP-2L (27 verified, 427s).

Q3: Role of Dynamic Intermediate Bound Tightening

Response: All SDP methods initialize with inexpensive baseline bounds {libase,uibase}\{l_i^{\text{base}}, u_i^{\text{base}}\} computed once by α\alpha-CROWN, which are also provided to our method as an initial rough estimate (Algorithm 1). While DeepSDP must use these static bounds across all layers, SL-SDP and SL-SDP-2L dynamically re-derive and tighten the intermediate pre-activation bounds layer by layer: after solving layer ii's SDP, we analytically project the ellipsoid GiG_i via Proposition 3 to obtain v^±a^\hat{v} \pm \hat{a} and intersect it with {li+1base,ui+1base}\{l_{i+1}^{\text{base}}, u_{i+1}^{\text{base}}\} (Algorithm 1, Line 19) before constructing the ReLU QCs for layer i+1i+1. Overall, while decomposing the monolithic SDP introduces some relaxation loss due to surrogate layer objectives Hi(⋅)H_i(\cdot), our framework compensates through two sources of improvement over standard DeepSDP: (i) a more expressive ReLU QC formulation (Lemma 1) and (ii) dynamic intermediate bound tightening (Proposition 3). We have clarified this in Section 4 and added w/o BT ablation curves (without dynamic bound tightening) to Figures 2 and 3, which show that while baseline bounds suffice in shallower settings, dynamic bound tightening is essential for enabling SL-SDP-2L to outperform DeepSDP at larger depths and perturbation radii.

Q4: Why 9-Layer Networks Favor SL-SDP(-2L) and How Practitioners Should Choose

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:

  • Comparison with β\beta-CROWN: Linear relaxation methods (α/β\alpha/\beta-CROWN) perform well when the input perturbation is small (especially small ℓ∞\ell_\infty boxes) so that many neurons are stable. Under larger perturbations or ℓ2\ell_2 balls, and as depth increases from 4 to 9 layers, linear relaxations accumulate severe wrapping errors, causing β\beta-CROWN to verify only 1 sample on MLP 4×100 (ℓ2,ϵ=1.0\ell_2, \epsilon=1.0) and 2 samples on MLP 9×150 (ℓ2,ϵ=0.5\ell_2, \epsilon=0.5) before timing out. Therefore, whenever the perturbation set is large enough that many hidden neurons become unstable, SDP-based relaxations provide a substantial advantage over linear branch-and-bound methods.
  • Comparison with DeepSDP and practitioner guidance: When a network is shallow enough that the (1+N)×(1+N)(1+N)\times(1+N) monolithic LMI fits comfortably in solver time and memory (e.g., 4 layers), DeepSDP is preferable if maximum tightness is prioritized over runtime. However, on deeper networks (e.g., 9 layers), DeepSDP becomes computationally intractable (TO), and its static α\alpha-CROWN intermediate bounds become overly loose in deeper layers (as also seen in Figure 2). Thus, practitioners should use SL-SDP(-2L) whenever (i) fast verification is required or (ii) network depth renders the monolithic SDP intractable.

We thank the reviewer once again for their valuable comments and suggestions, which helped us significantly improve the manuscript.

Thanks for the thorough reply and for the revisions. Algorithm 1 provides much details of the proposed approach. How about the complexity of the algorithm? It looks to me the approach shall be scalable as its main computation depends on the lay-to-layer propagation. I agree that dynamic intermediate lighting is very helpful to reduce the over-approximation. The novelty of the approach is fair to me and I prefer to maintain my score.

AuthorsOpenReview ↗

Follow-up Response to Reviewer Kko1

Thank you for recognizing the novelty of our approach and the benefits of dynamic intermediate bound tightening. Regarding complexity, the cost of Algorithm 1 is dominated by LL layer-wise SDPs (Line 15). At layer ii, the SDP operates only on the consecutive layer variables [1;xi−1;xi][1; x_{i-1}; x_i], resulting in an LMI of dimension 1+ni−1+ni=O(n)1 + n_{i-1} + n_i = \mathcal{O}(n) and 2+ni−1+3ni=O(n)2 + n_{i-1} + 3n_i = \mathcal{O}(n) scalar decision variables (and similarly O(n)\mathcal{O}(n) for SL-SDP-2L over [1;xi−2;xi−1;xi][1; x_{i-2}; x_{i-1}; x_i]). Furthermore, the intermediate propagation steps between layers, computing the Schur complement GiG_i (Line 17) and tightening the pre-activation bounds via Proposition 3 (Lines 18–19), require only closed-form matrix inversions and multiplications of size n×nn \times n, incurring negligible overhead relative to the SDP solve. Because the size of each layer-wise subproblem is independent of LL, the total runtime of Algorithm 1 scales linearly with network depth LL, whereas the monolithic DeepSDP formulation couples all neurons of the network into a single LMI. With a generic interior-point solver, factorizing this matrix alone costs O(L3)\mathcal{O}(L^3) per iteration, so its runtime and memory grow rapidly with depth. We will add this complexity discussion to Section 3.2 in the final manuscript.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response and Summary of Manuscript Revisions

We sincerely thank all three reviewers for their time, constructive feedback, and insightful questions. In response to the reviewers' feedback, we have uploaded a revised manuscript (with all changes highlighted in blue) and the updated code. Below is a summary of the main updates:

  1. Expanded MNIST Evaluation (Table 1, Section 4): We doubled the number of evaluated test samples in Table 1 from 25 to 50 samples (and will expand to 100 samples in the final version). All relative verification and runtime trends remain consistent.
  2. New Baseline Comparison with SDP-CROWN (Section 4): We evaluated the official implementation of SDP-CROWN (Chiu et al., 2025) across all ℓ2\ell_2-norm settings in Table 1. It verified 0/50 samples across all configurations, as its inter-layer scaling factor relies on a specialized 1-Lipschitz training routine and collapses on general PGD-trained networks.
  3. Ablation Study on Dynamic Intermediate Bound Tightening (Figures 2 & 3, Section 4, Appendix B.7): We added ablation results (SL-SDP (w/o BT) and SL-SDP-2L (w/o BT)) without dynamic intermediate bound updates to Figures 2 and 3, and clarified the two sources of tightness improvement in our framework: our refined ReLU QC (Lemma 1) and dynamic ellipsoidal pre-activation bound tightening (Proposition 3).
  4. Moved Algorithm 1 to the Main Text (Section 3.2): Following Reviewer Kko1's suggestion, we moved the core SL-SDP pseudocode (Algorithm 1) from the Appendix into Section 3.2 of the main text.
  5. Additional Experimental & Text Clarifications (Abstract, Sections 3 & 4): We refined the abstract and main text to accurately frame the tradeoff between tightness and scalability, added adversarial training details, documented that LayerSDP ran out of memory on all configurations in Experiment 2, and fixed minor wording and caption typos (Proposition 1 proof sketch, Figures 2 and 3 captions, and the 80-minute timeout in Table 1).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.