acceptodds
Under review as a conference paper at ICLR 2027

Verification of Sigmoid-Like Neural Networks via Symbolic Relaxation

Abstract

Formal robustness verification is essential for providing rigorous guarantees that a neural network's predictions remain unchanged with perturbations. For networks with sigmoid-like activations, a central challenge is to construct relaxations that faithfully capture their transcendental relations while remaining amenable to efficient verification. We propose a symbolically derived family of rational function relaxations, parametric in a relaxation order . The relaxations are sound and convergent, and they yield a -complete verification procedure, meaning that robust instances with a strictly positive margin can be certified with a finite relaxation order. Building on this family, we develop a scalable robustness verification method. Experiments on image classification benchmarks show that our method often outperforms the representative linear-relaxation baselines with tighter certified bounds on the robustness margin and improves certified robustness accuracy. Together, these results highlight the potential of rational relaxations beyond conventional linear bounds and suggest a new direction for certified robustness.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Neural Network Verification, Robustness, Symbolic Relaxation

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_gMQKOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper addresses the problem of DNN verification with transcendental, sigmoid-like activations (specifically logistic sigmoid and hyperbolic tangent). Because these functions are smooth and are not piecewise linear, existing verifiers typically either suffer from significant over-approximation errors (using linear relaxations) or incur prohibitive computational costs (using infinite branching in branch-and-bound).

To address this challenge, the authors introduce Syrt, a new abstraction domain based on a parameterized family of symbolic relaxations over the rational function field R(x)\mathbb{R}(x). Key elements of the paper include:

  1. Rational Function Sandwiching: Deriving sound, monotonic upper and lower rational bounding functions (σl(x,k)\sigma_l(x, k) and σu(x,k)\sigma_u(x, k)) via a customized Taylor expansions that guarantee lower and upper bounds.
  2. kk-Completeness: Proving that the relaxation parameter kk controls approximation tightness, and that the procedure is kk-complete, hence, guaranteeing that any strictly robust property can be certified at a finite relaxation order kk without infinite branching.
  3. Hybrid Verification: Combining fast linear relaxations (e.g., CROWN) to make Syrt more scalable.
  4. Empirical Validation: Evaluating on six small feedforward architectures (MNIST, Fashion-MNIST, CIFAR-10) with sigmoid and tanh activations, under 150k parameters, comparing against linear relaxation (NeWise) and branch-and-bound (GenBaB).
Critical strengths
  1. As the DNN verification community expands beyond standard computer vision networks toward transformers, vision-language models, and architectures featuring smooth activations (e.g., tanh, GELU, SiLU), tighter relaxation techniques for non-piecewise-linear functions are needed. This is an important topic but has remained largely underexplored, making the paper's focus both timely and consequential.

  2. The idea of constructing bounding relaxations within the rational function field to sandwich transcendental an activation function is mathematically elegant. Specifically, designing modified Taylor expansions that provide sound one-sided bounds (Eqs. 4 and 5) is non-trivial and neat.

  3. While prior nonlinear relaxation DNN verification techniques attempt to fit activation curves, they often struggle with scalability and lack a direct mechanism to trade off precision against computational complexity. Syrt addresses this by introducing the relaxation order kk as an explicit tuning parameter. Furthermore, the kk-completeness guarantee (Definition 5.1) thus ensuring that any strictly robust property is verifiable with finite computational resources is a valuable theoretical contribution.

  4. The paper is generally well-structured, clearly written, and easy to follow.

Critical weaknesses
  1. The empirical evaluation is limited to small-scale, fully-connected networks where every hidden neuron employs either uniformly sigmoid or tanh activations. This setup is uncommon in supervised learning as recent DNNs rarely use sigmoid or tanh uniformly throughout all layers. Real-world computer vision architectures are almost always heterogeneous, featuring piecewise-linear activations throughout the backbone and having sigmoid/tanh to specific layers (e.g., gating mechanisms or output heads).

  2. Moreover, the paper do not explain why it does not use standard benchmarks adopted by DNN verification community. For example, VNN-COMP includes NN4Sys (ReLU + Sigmoid, 33k–37M parameters), ml4acopf (ReLU + Sigmoid), and Dist Shift (FC + ReLU + Sigmoid, 342k–855k parameters). Also, demonstration on verifying small YOLO models (most activation are ReLU, with Sigmoid at last layer) is needed. The chosen benchmark only consist of DNN with less than 150k parameters. Verification benchmarks in ARCHCOMP, another competition on verifying neural network control systems, also have some small NN with tanh or sigmoid activations.

  3. Although the authors present certified robustness accuracy across varying relaxation orders and showing increase kpk_p also improve certified robustness, they provide no report on solving time. Reporting runtime is essential to fulfill the claim regarding scalability and practical efficiency.

  4. The mathematical intuition behind Equations 4 and 5 in Section 4 is not adequately explained in the main text. It is difficult to see how the authors arrived at these specific bounding rational forms and why they guarantee soundness, so the main text is not self contained.

Questions for authors

Most of my addressable concern are on the finishing quality of the experimental evaluation of this paper:

  1. Could you clearly clarify the different between this paper and [a] as [a] also use Taylor over-approximation for S-shape activation functions.

  2. Can the design method of the symbolic bound be systematically generalized to other activations (e.g., GELU, SiLU, ELU, Softmax)?

  3. What are the absolute solving times of Syrt compared to the baselines (NeWise and GenBaB) across the benchmark instances in Tab. 1?

  4. In my viewpoint, Syrt is a new abstraction domain with two modified Taylor expansions as symbolic lower and upper, but its concretization algorithm (e.g., SolveLowerBound(O, C)) is implemented in MILP solver like Gurobi, which are known to DNN verification community to be trivial and not scalable. Is there any closed-form solution or fast iterative procedure to solve the concretization for Syrt. If possible, could the authors include a few empirical evidences to the revised version of the experimental result?

  5. Can Syrt's non-linear relaxation be seamlessly composed with standard linear relaxations (e.g., DeepPoly / CROWN back-substitution) in mixed networks where some layers are ReLU and others use sigmoid-like activations? How are intermediate bounds propagated across heterogeneous layers during back-substitution? Same as previous question, could the authors include a few empirical evidence to the revised version of the experimental result?

  6. This is a independent question from Q4, Q5. Could the authors provide a cactus plot for the revised version or table for the rebuttal comparing the runtime distributions of certified robust instances across the original version of Syrt, NeWise, and GenBaB on existing experimental result? Additionally, could the authors also include a cactus plot/table showing the runtime of Syrt on different kp∈{0,1,2}k_p \in \{0, 1, 2\} to illustrate the scalability and precision-cost trade-off?

Reference

[a] Radoslav Ivanov. et. al. "Verisig 2.0: Verification of neural network controllers using taylor model preconditioning", CAV'21

If the authors resolve all of my questions, I'd be happy to increase my score.

8 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/2]

We thank the reviewer for their careful review and constructive feedback, and for recognizing the importance of this underexplored problem and the value of our contributions.

The intuition behind our relaxations comes from symbolic computation. Essentially, inspired from the Taylor expansion, we designed the relaxations such that they give good results for moderate values of kk (see also the illustrations in Figure 1). Due to space constraints, we did not present proof ideas in the main text. In the revised version, we added concise proofs and keep detailed proofs in the appendix. We also appreciate insightful suggestions outlined in the questions. In response, we provide a new example illustrating the potential for integrating different approaches and opening up further research opportunities. We address the reviewer's questions below. Revisions to the manuscript are highlighted in blue in PDF document.

Q1: Clarification of the differences between Syrt and Verisig 2.0.

Verisig 2.0 addresses the more general reachability problem for continuous-time neural-network control systems (i.e., the network is a controller for a continuous plant). It employs Taylor models, which approximate a nonlinear function as a Taylor polynomial plus an interval remainder. These Taylor models are propagated through the network layer by layer, which leads to accumulation of approximation errors. The main contributions of that approach are to apply tricks like preconditioning and shrink wrapping to mitigate that error accumulation. In contrast, we only target network output bounds, and our relaxations are not based on Taylor models. We construct parameterized symbolic lower and upper bounds inspired from Taylor expansions, where parameter kk provides a mechanism for controlling the approximation accuracy. We obtain bounds by solving an optimization problem.

Q2: Generalization to other activation functions.

Although the current formulation of Syrt is specifically designed for sigmoid-like activation functions, we believe that the underlying principle of constructing parameterized symbolic nonlinear bounds can be extended to other activation functions with certain features. However, we do not know of a general algorithmic procedure. While the general symbolic-bound construction principle is extensible, the current theoretical guarantees and implementation of Syrt are limited to the activation functions studied in this work. Establishing rigorous approximation guarantees and formally verifying these extensions remain important directions for future work.

Q3: Comparison of running times across benchmark instances in Table 1.

We now report the running time and memory consumption in Table 3 and Table 4 (Appendix B.2).

Table 3. CPU time and wall time comparison (in seconds), reported as mean ±\pm std dev over 100 samples (population std dev, ddof=0\mathrm{ddof}=0).

InstancesSyrt CPUSyrt WallNeWise CPUNeWise WallGenBaB CPUGenBaB Wall
sigmoidMNIST\mathrm{sigmoid}^{\text{MNIST}}37.37±23.4337.37 \pm 23.437.53±3.997.53 \pm 3.990.07±0.420.07 \pm 0.420.07±0.430.07 \pm 0.4311.97±3.3511.97 \pm 3.359.43±2.489.43 \pm 2.48
tanhMNIST\mathrm{tanh}^{\text{MNIST}}3.09±0.673.09 \pm 0.671.28±0.691.28 \pm 0.690.13±0.130.13 \pm 0.130.05±0.130.05 \pm 0.1316.42±0.7116.42 \pm 0.7110.57±0.2810.57 \pm 0.28
sigmoidFMNIST\mathrm{sigmoid}^{\text{FMNIST}}22.34±24.2022.34 \pm 24.204.72±4.614.72 \pm 4.610.03±0.000.03 \pm 0.000.03±0.010.03 \pm 0.0113.10±2.2213.10 \pm 2.229.99±1.649.99 \pm 1.64
tanhFMNIST\mathrm{tanh}^{\text{FMNIST}}25.13±24.4625.13 \pm 24.465.31±4.655.31 \pm 4.650.03±0.010.03 \pm 0.010.03±0.010.03 \pm 0.0114.01±4.9514.01 \pm 4.959.09±3.009.09 \pm 3.00
sigmoidCIFAR\mathrm{sigmoid}^{\text{CIFAR}}22.28±11.8822.28 \pm 11.888.30±4.018.30 \pm 4.010.04±0.000.04 \pm 0.000.04±0.010.04 \pm 0.0119.72±0.4419.72 \pm 0.4410.31±0.1810.31 \pm 0.18
tanhCIFAR\mathrm{tanh}^{\text{CIFAR}}46.87±22.3646.87 \pm 22.367.49±3.557.49 \pm 3.550.04±0.000.04 \pm 0.000.04±0.010.04 \pm 0.0115.91±7.4015.91 \pm 7.408.62±3.738.62 \pm 3.73

Table 4. Peak memory usage (resident set size, RSS) in MiB.

InstancesSyrtNeWiseGenBaB
sigmoidMNIST\mathrm{sigmoid}^{\text{MNIST}}1381.66803.28844.89
tanhMNIST\mathrm{tanh}^{\text{MNIST}}1216.08824.421372.25
sigmoidFMNIST\mathrm{sigmoid}^{\text{FMNIST}}1085.91803.61781.89
tanhFMNIST\mathrm{tanh}^{\text{FMNIST}}1555.98824.481293.83
sigmoidCIFAR\mathrm{sigmoid}^{\text{CIFAR}}1554.28813.341463.94
tanhCIFAR\mathrm{tanh}^{\text{CIFAR}}2113.20828.692156.86
AuthorsOpenReview ↗

Official Comment by Authors [2/2]

Q4: Scalability and efficiency of Syrt.

Regarding the closed-form solution, we provided information about Cylindrical Algebraic Decomposition (CAD) in the appendix. CAD provides a complete decision procedure for the relaxed verification problem. However, its computational cost grows rapidly with the number of variables and polynomial degrees, making it impractical for neural networks. In our implementation, we therefore use Gurobi as the optimization backend and certify the property using the solver-reported global objective bound, which returns a sound lower bound.

Nonlinear optimization problems are generally difficult to scale, as is the original verification problem for neural networks we address. One approach to managing this complexity is to sacrifice completeness in favor of efficient relaxations, such as the linear relaxations. Alternatively, our approach seeks to balance computational complexity and completeness, providing a tunable trade-off between the two.

Q5: Compatibility with linear relaxations in mixed-activation networks.

Our hybrid algorithm Syrt already employs linear relaxations partially for neurons deemed non-critical (Line 9 of the pseudocode) to improve scalability. Indeed, Syrt can be combined with existing relaxation methods. To demonstrate this compatibility, we present an example that integrates Syrt's nonlinear relaxations with NeWise's linear relaxations for a network containing both ReLU and sigmoid activation functions. We have added a benchmark from the dist_shift category of VNN-COMP (see the new Appendix B.3 and Table 5). We can verify robustness for all 20 samples we looked at (GenBaB also verifies these samples).

Syrt achieves scalability primarily by adjusting kk, without incorporating back-substitution. Integrating Syrt with back-substitution methods is a promising direction for future work, particularly as preserving formal guarantees requires further theoretical investigation.

Table 5. Experimental results for a heterogeneous ReLU/sigmoid network (dist_shift) from VNN-COMP with 20 input samples.

ApproachVerifiedCPU Time (s)Wall Time (s)Memory (MiB)
Syrt+NeWise2041.54±6.6541.54 \pm 6.6510.73±0.0810.73 \pm 0.081576.16
GenBaB2024.71±5.5024.71 \pm 5.5010.76±1.6610.76 \pm 1.665696.69

Time is reported as mean ±\pm standard deviation.

Q6: Additional cactus plots

We have added cactus plots in Figure 4 (Appendix B.2). (Please note that, since we retained the experimental setup from Table 1, where we selected the instances that NeWise could not verify, the NeWise curves always show a 0% success rate, by construction.)

Thanks for the revision on Q1, Q2, Q5. I really appreciate your effort.

  • My biggest concern on the scalability (Q3, Q4) is not yet resolved. There is no scalable method to solve this abstraction domain. Using Gurobi is trivial, limiting Syrt's contribution. Can you come up with an iterative approximated algorithms to find near optimal and sound symbolic bound for your abstraction domain? It'll be really unfortunate if I have to keep my score because of this.
  • The cactus plot should be transposed, horizontal is number of verified instances, vertical is time.
Reviewer_76HXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses an important verification problem and proposes an interesting rational-relaxation approach -Syrt, with encouraging empirical results. However, the stated activation-bound conditions admit a counterexample, and the network-level completeness claim is not justified by the displayed formulation. These issues directly concern the paper’s central contribution. The selected evaluation subset and ambiguity about multiclass certification further limit confidence in the reported performance claims.

Critical strengths

-- The paper studies robustness verification for neural networks with sigmoid and hyperbolic-tangent activations. It proposes rational lower and upper bounds derived from truncated exponential expansions. Increasing the relaxation order is intended to tighten these bounds and yield a verification framework that is complete for robust instances with strictly positive margins.

-- The evaluation covers six feedforward networks on MNIST, Fashion-MNIST, and CIFAR-10. On the selected test instances, Syrt reports higher certification rates than GenBaB in five of six settings. An ablation investigates the effect of increasing the relaxation order.

Critical weaknesses

-- In Theorem 4.3, there is an incorrect denominator-positivity condition as written, but the condition defining k0k_0 omits the factor e2ce^{2c}

-- Equations (6)–(8) initialize lower and upper inputs using the box endpoints. Taken literally, this propagates interval bounds and loses input dependencies, even when activation relaxations become exact.

-- Algorithm 1 checks every opponent class, but Section 6 selects one opponent using NeWise for reporting margins. This is acceptable for a pairwise-margin comparison, but a positive margin against one selected class does not, by itself, certify multiclass robustness.

-- The shared 10-second timeout is useful, but the paper does not report actual end-to-end runtimes, timeout frequencies, memory consumption, or scaling with network size. It is also unclear whether the budget applies per opponent class or per image and whether preprocessing is included

-- Table 2 needs clearer reporting. Its caption says it uses the same benchmark instances as Table 1, although Appendix B changes both the perturbation radius and sample-selection rule. The sigmoid Fashion-MNIST architecture also changes from 3×503\times50 to 2×2002\times200.

Questions for authors

see above

2 comments
AuthorsOpenReview ↗

Official Comment by Authors

We thank the reviewer for their careful review and feedback, which helped us identify oversights and provided concrete suggestions for improving the presentation. Accordingly, we have revised the manuscript to improve its clarity, which are highlighted in blue in the document.

Q1: Missing factor in Theorem 4.3.

The missing factor has been included in the revised manuscript.

Q2: Clarification of input dependency preservation in Eqs. (6)–(8).

We would like to clarify that only the bounds in the first layer are concrete values derived from the L∞L_{\infty} perturbation region, whereas in hidden layers, Eqs. (6)–(8) describe symbolic expressions. Specifically, xlx_l, xux_u, etc., are symbolic variables (not concrete bounds). We do not propagate concrete bounds for these variables. Instead, we pass the resulting symbolic expression directly to the solver, thus preserving input dependencies.

Q3: Clarification of pairwise-margin comparison versus multiclass robustness certification.

We use pairwise-margin comparison to simplify the experimental setup, a practice also found in prior studies [1, 2]. Since we apply the same simplification for all approaches, our comparison is fair. In practice, the largest classes often account for the majority of the total output weight across all inputs, in which case it is actually sound to only validate these classes.

[1] Zhang et al. "Efficient neural network robustness certification with general activation functions" (NeurIPS 2018).

[2] Weng et al. "Towards fast computation of certified robustness for ReLU networks" (ICML 2018).

Q4: Clarification of runtime budgets and additional efficiency metrics.

We now added Table 3 and Table 4 to the appendix that report the running times and memory consumption. As can be seen, Syrt is competitive with GenBaB, finishing faster (wall time) on average across all instances. The timeout only applies to the solver, not the preprocessing and construction of the solver input (which however is negligible). Since the experiment only considers one opponent class (see the previous question), \emph{per-opponent-class} and \emph{per-image} are equivalent.

Table 3. CPU time and wall time comparison (in seconds), reported as mean ±\pm std dev over 100 samples (population std dev, ddof=0\mathrm{ddof}=0).

InstancesSyrt CPUSyrt WallNeWise CPUNeWise WallGenBaB CPUGenBaB Wall
sigmoidMNIST\mathrm{sigmoid}^{\text{MNIST}}37.37±23.4337.37 \pm 23.437.53±3.997.53 \pm 3.990.07±0.420.07 \pm 0.420.07±0.430.07 \pm 0.4311.97±3.3511.97 \pm 3.359.43±2.489.43 \pm 2.48
tanhMNIST\mathrm{tanh}^{\text{MNIST}}3.09±0.673.09 \pm 0.671.28±0.691.28 \pm 0.690.13±0.130.13 \pm 0.130.05±0.130.05 \pm 0.1316.42±0.7116.42 \pm 0.7110.57±0.2810.57 \pm 0.28
sigmoidFMNIST\mathrm{sigmoid}^{\text{FMNIST}}22.34±24.2022.34 \pm 24.204.72±4.614.72 \pm 4.610.03±0.000.03 \pm 0.000.03±0.010.03 \pm 0.0113.10±2.2213.10 \pm 2.229.99±1.649.99 \pm 1.64
tanhFMNIST\mathrm{tanh}^{\text{FMNIST}}25.13±24.4625.13 \pm 24.465.31±4.655.31 \pm 4.650.03±0.010.03 \pm 0.010.03±0.010.03 \pm 0.0114.01±4.9514.01 \pm 4.959.09±3.009.09 \pm 3.00
sigmoidCIFAR\mathrm{sigmoid}^{\text{CIFAR}}22.28±11.8822.28 \pm 11.888.30±4.018.30 \pm 4.010.04±0.000.04 \pm 0.000.04±0.010.04 \pm 0.0119.72±0.4419.72 \pm 0.4410.31±0.1810.31 \pm 0.18
tanhCIFAR\mathrm{tanh}^{\text{CIFAR}}46.87±22.3646.87 \pm 22.367.49±3.557.49 \pm 3.550.04±0.000.04 \pm 0.000.04±0.010.04 \pm 0.0115.91±7.4015.91 \pm 7.408.62±3.738.62 \pm 3.73

Table 4. Peak memory usage (resident set size, RSS) in MiB.

InstancesSyrtNeWiseGenBaB
sigmoidMNIST\mathrm{sigmoid}^{\text{MNIST}}1381.66803.28844.89
tanhMNIST\mathrm{tanh}^{\text{MNIST}}1216.08824.421372.25
sigmoidFMNIST\mathrm{sigmoid}^{\text{FMNIST}}1085.91803.61781.89
tanhFMNIST\mathrm{tanh}^{\text{FMNIST}}1555.98824.481293.83
sigmoidCIFAR\mathrm{sigmoid}^{\text{CIFAR}}1554.28813.341463.94
tanhCIFAR\mathrm{tanh}^{\text{CIFAR}}2113.20828.692156.86

Q5: Clarification of Table 2.

By instance we refer to the network/dataset combinations in the first column. Indeed, the perturbation radius and sample-selection rule differ between the experiments. We have corrected the architecture of sigmoid-FMNIST to align with Table 1 and updated the experimental results accordingly. The description has been revised to improve clarity.

Dear reviewer,

Thank you for your review and feedback. As the discussion period will close within 24 hours, we would like to ask whether our response has satisfyingly addressed your questions and whether any open concerns remain.

Thanks again for your time and feedback which helped us improving the paper.

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

This paper presents a verification framework for neural networks with sigmoid-like activations (logistic sigmoid, tanh). These networks are hard to verify: their transcendental activation relations are not known to be decidable, and state-of-the-art tools fall back on linear relaxations, which discard nonlinear structure and yield loose certified bounds. The authors instead derive a parametric family of rational-function relaxations that bound the activation from below and above over a given interval. The relaxation order k controls tightness; the bounds converge monotonically to the true activation and, unlike truncated Taylor series, are provably one-sided and valid everywhere in the interval.

The main contributions are threefold. First, explicit sound, convergent, monotone k-relaxations for sigmoid and tanh over the rational function field. Second, a verification framework that substitutes these relaxations layer-wise while keeping affine transformations exact, recasting robustness as a feasibility problem over rational functions; the framework is proven sound and "k-complete," meaning any instance with a strictly positive margin is certified at some finite k — presented as the first complete relaxation method for sigmoid-like activations without exhaustive branch-and-bound refinement. Third, a practical hybrid implementation, Syrt, that applies cheap linear relaxation where the activation is nearly flat (|pre-activation| ≥ 5) and the rational relaxation elsewhere, using Gurobi as the optimization backend.

The experiments cover six pretrained MLPs (sigmoid or tanh, two to three hidden layers) on MNIST, Fashion-MNIST, and CIFAR-10, under ℓ∞ perturbations with ε = 5/255, 10 seconds per instance on CPU, single run. Baselines are NeWise (linear relaxation) and GenBaB (α-CROWN-style branch-and-bound); metrics are certified robustness accuracy and the certified robustness margin. Instances are deliberately hard: the first 100 correctly classified test samples that NeWise fails to certify. Syrt performs better on five of six instances, including 64% certified versus 0% for GenBaB on tanh-MNIST-3×100, and loses on tanh-CIFAR-3×50, where 76% of neurons degenerate to the linear case. An ablation over the precision parameter kp yields modest further gains, with one regression caused by solver timeouts.

Critical strengths
  1. A genuinely new relaxation paradigm. Rather than refining linear bounds, the paper constructs rational-function relaxations that track the sigmoid's nonlinear shape directly. This is consequential because it opens a design axis beyond linear relaxation, and it is what makes completeness achievable at all for transcendental activations.

  2. Soundness plus k-completeness, with proofs. Tightness is not only demonstrated empirically but guaranteed: monotone convergence of the relaxations yields a finite order certifying any instance with positive margin. This distinguishes the work from heuristics and grounds the empirical gains in theory.

  3. Honest, non-cherry-picked evaluation. Benchmark instances are chosen precisely where the linear baseline fails, the losing case is reported and explained mechanistically, and the hybrid's cost and limitations are acknowledged. This raises confidence that reported gains are real rather than setup artifacts.

Critical weaknesses
  1. Scalability is untested at realistic scale. Networks have at most three hidden layers of 200 neurons, no CNNs, 10-second timeouts, and a 100-sample subset chosen for failure. Since k-completeness needs higher orders for hard instances, symbolic expressions likely explode quickly. Without a scaling study, the practical reach of the method stays unclear.

  2. k-completeness is weaker than it appears. The guarantee needs a finite but unbounded order, relies on an external solver terminating, and depends on pre-activation bounds from the linear baseline being tight. The hybrid deliberately abandons completeness, and higher kp even degraded one instance under timeout. So the theoretical property is not demonstrated end-to-end.

Questions for authors
  1. How do symbolic expression size and solving time grow with layer width, depth, and k? Could you report expression size, constraint count, and wall-clock per instance against network size, and the certificate rate under a realistic budget (say 600 s)?

  2. Is the 10-second Gurobi gap guaranteed to be a valid global lower bound at termination, and how often do results rely on Gurobi heuristics rather than proven bounds?

  3. The paper lists missing GPU engineering as a limitation, but does not say what a GPU could actually accelerate here. Could you clarify whether the bottleneck is symbolic expression construction and bound propagation, or the non-convex global optimization? Since certificates rely on Gurobi's global ObjBound, a GPU path likely means batched symbolic bound propagation and per-sample parallelism rather than replacing the solver. Roughly how much of the runtime sits in each phase, and could a PyTorch/JAX implementation reuse the α-CROWN GPU infrastructure?

2 comments
AuthorsOpenReview ↗

Official Comment by Authors

We thank the reviewer for recognizing the value of our novel rational relaxation paradigm as well as our experimental evaluation. As the reviewer highlights, this paradigm opens a new design direction beyond linear relaxations, offering promising opportunities for further advances that could benefit the broader neural network verification community. Building on established algebraic theory, our method is complete and theoretically feasible. However, the high dimensionality of neural networks necessitates practical engineering techniques to improve computational efficiency in terms of both running time and memory usage. To this end, we leverage Gurobi as an optimization solver in our implementation. We address the reviewer's questions below. Revisions to the manuscript are highlighted in blue in PDF document.

Q1: Scalability with network size and k, and verification performance under a fixed time budget.

The expression size grows linearly in width, depth, and kk. We now report the running time and memory consumption in Table 3 and Table 4 (Appendix B.2). Since we used a time limit of 10 s per sample, we used a total budget of 1000 s per instance. Additionally, the newly added cactus plots (Figure 5) show the number of certified samples over wall-clock time.

Table 3. CPU time and wall time comparison (in seconds), reported as mean ±\pm std dev over 100 samples (population std dev, ddof=0\mathrm{ddof}=0).

InstancesSyrt CPUSyrt WallNeWise CPUNeWise WallGenBaB CPUGenBaB Wall
sigmoidMNIST\mathrm{sigmoid}^{\text{MNIST}}37.37±23.4337.37 \pm 23.437.53±3.997.53 \pm 3.990.07±0.420.07 \pm 0.420.07±0.430.07 \pm 0.4311.97±3.3511.97 \pm 3.359.43±2.489.43 \pm 2.48
tanhMNIST\mathrm{tanh}^{\text{MNIST}}3.09±0.673.09 \pm 0.671.28±0.691.28 \pm 0.690.13±0.130.13 \pm 0.130.05±0.130.05 \pm 0.1316.42±0.7116.42 \pm 0.7110.57±0.2810.57 \pm 0.28
sigmoidFMNIST\mathrm{sigmoid}^{\text{FMNIST}}22.34±24.2022.34 \pm 24.204.72±4.614.72 \pm 4.610.03±0.000.03 \pm 0.000.03±0.010.03 \pm 0.0113.10±2.2213.10 \pm 2.229.99±1.649.99 \pm 1.64
tanhFMNIST\mathrm{tanh}^{\text{FMNIST}}25.13±24.4625.13 \pm 24.465.31±4.655.31 \pm 4.650.03±0.010.03 \pm 0.010.03±0.010.03 \pm 0.0114.01±4.9514.01 \pm 4.959.09±3.009.09 \pm 3.00
sigmoidCIFAR\mathrm{sigmoid}^{\text{CIFAR}}22.28±11.8822.28 \pm 11.888.30±4.018.30 \pm 4.010.04±0.000.04 \pm 0.000.04±0.010.04 \pm 0.0119.72±0.4419.72 \pm 0.4410.31±0.1810.31 \pm 0.18
tanhCIFAR\mathrm{tanh}^{\text{CIFAR}}46.87±22.3646.87 \pm 22.367.49±3.557.49 \pm 3.550.04±0.000.04 \pm 0.000.04±0.010.04 \pm 0.0115.91±7.4015.91 \pm 7.408.62±3.738.62 \pm 3.73

Table 4. Peak memory usage (resident set size, RSS) in MiB.

InstancesSyrtNeWiseGenBaB
sigmoidMNIST\mathrm{sigmoid}^{\text{MNIST}}1381.66803.28844.89
tanhMNIST\mathrm{tanh}^{\text{MNIST}}1216.08824.421372.25
sigmoidFMNIST\mathrm{sigmoid}^{\text{FMNIST}}1085.91803.61781.89
tanhFMNIST\mathrm{tanh}^{\text{FMNIST}}1555.98824.481293.83
sigmoidCIFAR\mathrm{sigmoid}^{\text{CIFAR}}1554.28813.341463.94
tanhCIFAR\mathrm{tanh}^{\text{CIFAR}}2113.20828.692156.86

Q2: Validity of Gurobi bounds under time limits and reliance on heuristics.

For minimization problems, Gurobi maintains guaranteed (up to floating-point precision and solver tolerances) lower and upper bounds on the objective value (please see the link in footnote 2 in the appendix for details). These bounds are valid for any time limit, and they improve if the solver is given more time. Since we want to prove that the objective value is positive, using the lower bound is sound (up to standard numerical precision).

Q3: Clarification of computational bottlenecks and GPU acceleration opportunities.

The baselines benefit from GPU acceleration, whereas our current implementation of Syrt does not. Syrt consists of two main computational stages: symbolic relaxation construction and nonconvex global optimization. While the former offers opportunities for GPU acceleration through batched computation but is generally fast, the latter relies on Gurobi to obtain formally valid global bounds and is the bottleneck in practice.

I quickly browsed other reviewer's comments and the authors response. As gMQK stated, the scalability issue is essential. Formal verification is still struggling on this problem due to inherent high computational complexity. But it still to see some new non-linear approximation approach after a lot of linear-based approximation approaches proposed. The theoretical aspect shall be valued. I will maintain my score as it is.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Responses

We thank the reviewers for their careful review and constructive feedback, and for acknowledging the significance of our contributions. We have addressed the concerns raised by the reviewers. All revisions are indicated in blue text in the revised manuscript. We will also revise the final manuscript based on the discussions. We categorize the concerns as follows:

  1. Theoretical soundness and guarantees (gMQK q2; 76HX w1–w3; zZW6 w2, q2)

The missing factor in Theorem 4.3 was fixed, and symbolic vs.\ concrete bounds and the validity of Gurobi's global lower bounds were clarified.

  1. Clarity and presentation (gMQK w4, q1)

The differences from Verisig 2.0 were clarified. Intuitive explanations and proofs for Theorems 4.2–4.4 and Lemma 4.5 were added to the main text.

  1. Scalability and algorithmic efficiency (gMQK q4; zZW6 w1, q1, q3)

The precision–cost trade-off through iterative refinement of kk, computational characteristics, and opportunities for GPU acceleration were discussed.

  1. Experimental evaluation (gMQK w1–w3, q3, q5, q6; 76HX w4, w5)

Time and memory comparisons (Tables 3–4), cactus plots (Figure 5), and a mixed ReLU/sigmoid benchmark from VNN-COMP (Appendix B.3) were added. The network architecture was corrected.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.