Quantized neural networks achieve computational efficiency by reducing precision, but bounding their quantization error remains a challenge due to discrete rounding and clamping operations. We present a zonotope-based abstract interpretation framework for quantized ReLU feed-forward network verification, introducing a unified round-clamp abstract transformer that jointly handles both operations. We extend this framework to constrained zonotopes, which add linear constraints to tighten bounds, and derive sound quantization error representations. We establish soundness and affine-strip optimality of the round-clamp abstract transformer, as well as convex-hull optimality of its complete constrained formulation. On the ACAS Xu benchmarks, our constrained zonotope method reduces average error-bound widths by approximately 70-85% and runtimes by 65-80% compared to QEBVerif's symbolic DRA propagation at the two smallest tested perturbation radii (r=3 and r=6). These improvements are not uniform across bitwidths, and symbolic DRA achieves tighter bounds at larger radii. Our plain zonotope method delivers competitive sound bounds nearly 300 times faster on average.
Figures & tables
Figure 1: Abstract ReLU for the unstable case. The affine abstraction y∈[λx,λx+2μ] (central affine line with upper and lower error bounds, shown in red and blue) soundly over-approximates the ReLU graph (solid black), with the grey regions eliminated by the two added constraints to tighten the over-approximation.
Figure 2: Abstract round-clamp for Case 4: input range [l,u] spans both rounding and clamping thresholds. The affine abstraction y∈[λx+μ−e,λx+μ+e] (central affine line with upper and lower error bounds) soundly over-approximates the stepped function (solid black), with the grey regions eliminated by the two box constraints y≥0 and y≤C . The complete formulation (Appendix A ) adds a third, oblique constraint.
Method
Avg. ODiff
Avg. Time (s)
Original Zonotope
361.1
0.002
Constrained Zonotope
230.0
0.382
DRA-Sym
145.3
0.564
Table 1: Average performance across all 150 ACAS Xu experiments. Bold marks the better of Constrained Zonotope and DRA-Sym; the Original Zonotope is the fastest method.
Zonotope
Constrained
DRA-Sym
r
ODiff
Time
ODiff
Time
ODiff
Time
3
2.3
1 ms
1.4
94 ms
8.5
422 ms
6
7.7
1 ms
4.7
170 ms
14.9
485 ms
13
175.0
3 ms
111.9
413 ms
74.0
611 ms
19
512.2
1 ms
326.5
541 ms
194.4
641 ms
26
1108.4
3 ms
705.6
691 ms
435.0
660 ms
Table 2: Per-radius breakdown. Bold marks the better of Constrained and DRA-Sym for each metric; the unconstrained Zonotope is the fastest at every radius. Constrained zonotopes are tighter and faster at r≤6 ; DRA-Sym is tighter from r=13 and also faster at r=26 .
Figure 3: Precision vs speed trade-off (log-log scale). Each point is one experiment. At small radii, constrained zonotopes are both faster and more precise than DRA-Sym: runtimes converge only at the largest radius ( r=26 ).
Figure 4: Average ODiff vs. attack radius for Q=6 and Q=10 . Constrained zonotopes are tightest at small radii; DRA-Sym recovers at large radii.
Full
Main
r
ODiff
Time
ODiff
Time
3
1.40
191 ms
1.41
104 ms
6
4.65
318 ms
4.66
180 ms
13
111.9
647 ms
111.9
411 ms
19
326.5
897 ms
326.5
567 ms
26
705.6
1098 ms
705.6
714 ms
Table 3: Comparison of the full and main constrained formulations across different perturbation radii.
We investigate the computational complexity of neural network verification in quantised settings. We distinguish three classes of Feedforward Neural Networks (FNNs): rational FNNs with exact rational weights, quantised FNNs whose weights come from a finite-width arithmetic, and dynamically quantised FNNs in which rational networks are evaluated with respect to a given finite-width arithmetic. We consider two types of specifications used in the literature. Linear programming (LP) specifications are conjunctions of linear constraints, while bit-vector (BV) specifications allow reasoning at the bit level and can express non-linear constraints. Our results give a complexity landscape of these verification problems. For quantised FNNs with fixed arithmetic precision, we show that verification under both LP and BV specifications remains NP-complete, matching the complexity of the rational case. For dynamically quantised FNNs with BV specifications, we establish upper bounds, complementing a previously known PSPACE-hardness result.
Eric Alsmann, Martin Lange, Marco Sälzer
University of Kassel · RPTU University Kaiserslautern-Landau
The parameterized CROWN analysis, a.k.a., alpha-CROWN has emerged as a practically successful abstract interpretation method for neural network verification. However, existing implementations of alpha-CROWN are limited to Python, which complicates integration into existing DNN verifiers and long-term production-level systems. We introduce Luna, a new abstract-interpretation-based bound propagator implemented in C++. Luna supports Interval Bound Propagation, the DeepPoly/CROWN analysis, and the alpha-CROWN analysis over a general computational graph. We describe the architecture of Luna and show that it outperforms the state-of-the-art alpha-CROWN implementation in terms of both bound tightness and computational efficiency on supported benchmarks from VNN-COMP 2025. Luna is publicly available at https://github.com/ai-ar-research/luna.
Most formal verification approaches for neural networks conservatively enclose the output set of the neural network. However, computing a tight output enclosure is in general computationally hard. We sidestep this challenge with a novel neural network architecture that realizes mixed-monotone functions as the difference of monotone subnetworks. By utilizing the theory on mixed-monotone systems, this reduces the computation of a tight output enclosure from complicated set propagation to two simple forward passes of opposite corners of an input interval. Moreover, because the size of the resulting enclosure is a closed-form function of the weights of the neural network, we can directly minimize it during training. We prove a lower bound on the size of any such enclosure, given by the total variation of the represented function generalized to several inputs, which makes it possible to compare the tightness of the enclosure against the optimum. Our evaluation on regression and dynamical-system benchmarks demonstrates that our training reduces the enclosure size to within 0.5% of the lower bound without sacrificing prediction accuracy. Computing our enclosure is orders of magnitude faster than CROWN and α-CROWN and on deep networks it is also tighter than zonotope propagation and CROWN, while its size exceeds that of α-CROWN by only 5.1%.