- 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 . Key elements of the paper include:
- Rational Function Sandwiching: Deriving sound, monotonic upper and lower rational bounding functions ( and ) via a customized Taylor expansions that guarantee lower and upper bounds.
- -Completeness: Proving that the relaxation parameter controls approximation tightness, and that the procedure is -complete, hence, guaranteeing that any strictly robust property can be certified at a finite relaxation order without infinite branching.
- Hybrid Verification: Combining fast linear relaxations (e.g.,
CROWN) to makeSyrtmore scalable. - 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
-
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.
-
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.
-
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.
Syrtaddresses this by introducing the relaxation order as an explicit tuning parameter. Furthermore, the -completeness guarantee (Definition 5.1) thus ensuring that any strictly robust property is verifiable with finite computational resources is a valuable theoretical contribution. -
The paper is generally well-structured, clearly written, and easy to follow.
Critical weaknesses
-
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).
-
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 than150k parameters. Verification benchmarks in ARCHCOMP, another competition on verifying neural network control systems, also have some small NN with tanh or sigmoid activations. -
Although the authors present certified robustness accuracy across varying relaxation orders and showing increase also improve certified robustness, they provide no report on solving time. Reporting runtime is essential to fulfill the claim regarding scalability and practical efficiency.
-
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:
-
Could you clearly clarify the different between this paper and [a] as [a] also use Taylor over-approximation for S-shape activation functions.
-
Can the design method of the symbolic bound be systematically generalized to other activations (e.g., GELU, SiLU, ELU, Softmax)?
-
What are the absolute solving times of Syrt compared to the baselines (NeWise and GenBaB) across the benchmark instances in Tab. 1?
-
In my viewpoint,
Syrtis 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 forSyrt. If possible, could the authors include a few empirical evidences to the revised version of the experimental result? -
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? -
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, andGenBaBon existing experimental result? Additionally, could the authors also include a cactus plot/table showing the runtime ofSyrton different 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
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 , 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.
| Approach | Verified | CPU Time (s) | Wall Time (s) | Memory (MiB) |
|---|---|---|---|---|
| Syrt+NeWise | 20 | 1576.16 | ||
| GenBaB | 20 | 5696.69 |
Time is reported as mean 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.
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 k (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 k 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 ± std dev over 100 samples (population std dev, ddof=0).
Table 4. Peak memory usage (resident set size, RSS) in MiB.