A neural network verifier asks whether every input in a small box around an image, or in a region of flight-sensor readings, produces the same safe decision. The cheapest verifier, interval bound propagation (IBP), pushes a lower and upper value for each neuron through the network. It is loose because of the interval dependency problem. Interval arithmetic treats every appearance of an uncertain quantity as independent, so $x - x$ over $[1,2]$ comes out as $[-1,1]$ rather than $0$. Across many layers this error compounds exponentially. Methods that track dependencies are much tighter but cost more. Examples are affine arithmetic, which writes each neuron as a center plus a weighted sum of shared noise terms, and symbolic intervals, which write each bound as a linear function of the input. The field has judged that extra cost by counting operations. The systems literature has shown repeatedly that operation counts are a poor guide to real speed on GPUs, where moving data and launching small kernels often dominate.
This note proposes to apply that systems lesson to bound propagation itself. IBP is made almost entirely of element-wise min, max, add and ReLU operations, which are limited by memory bandwidth. Dependency tracking with a fixed number $k$ of noise terms per neuron turns each layer into a dense matrix multiply, the operation GPUs run fastest. Our hypothesis is that wall-clock latency stays nearly flat as $k$ grows, up to a threshold set by the hardware, even though FLOPs grow linearly in $k$. If that holds, much of the tightness of dependency tracking is available at close to IBP's latency. The right amount of tracking per layer should then be chosen from measured latency, not FLOPs. We will build a fixed-budget, GPU-native affine arithmetic, measure its tightness-versus-latency frontier, and allocate the budget per layer against a measured cost model.
Core Claim
Existing verifiers choose the level of dependency tracking uniformly, and they reason about cost in operation counts or in CPU runtime. Make Interval Bound Propagation great again provides the motivating evidence on tightness. It proves that IBP's box-shaped enclosures grow exponentially with depth even for orthogonal linear layers, and it shows that affine arithmetic is nearly as tight as the far costlier doubleton arithmetic. Its implementation, however, runs in C++ on CPUs through the CAPD library. The authors report that affine arithmetic has a non-constant, input-dependent cost and a memory overhead that blocks large models. Formal Security Analysis of Neural Networks using Symbolic Intervals tracks linear input dependencies and parallelizes input bisection on multicore CPUs, but it never profiles accelerators.
On the systems side, ShuffleNet V2 shows that element-wise operations have negligible FLOPs but high memory access cost. TResNet and Searching for Fast Model Families on Datacenter Accelerators show that higher-FLOP dense designs can run faster because they keep the matrix units busy. Neither line of work has been turned on the verifier.
Our claim is specific. For a fixed network and hardware, define the tightness of a bound method as the ratio of the true output range to the computed one, following the propagation-tightness idea of Understanding Certified Training with Interval Bound Propagation. The claim is that the frontier of tightness against measured GPU latency differs sharply from the frontier of tightness against FLOPs. Per-layer allocations chosen on the latency frontier should verify more properties within a fixed wall-clock budget than allocations chosen by FLOPs or chosen uniformly.
Research Program
The first component is a static-shape affine arithmetic. Each neuron in layer $l$ is represented as $\hat z = z_0 + \sum_{i=1}^{k_l} z_i \epsilon_i + [-r, r]$. Here $z_0$ is the center, the $z_i$ are coefficients on shared noise terms $\epsilon_i \in [-1,1]$, $k_l$ is a fixed per-layer budget, and $r$ is a per-neuron interval remainder. Standard affine arithmetic adds a new noise term at every unstable ReLU, which is what makes its cost input-dependent. We instead condense after each nonlinearity. We keep the $k_l$ noise terms with the largest total coefficient mass and fold the rest into $r$. This is sound because folding a term only widens the box.
Condensation keeps tensor shapes fixed. Layers can then be compiled and fused into a small number of kernels, which addresses the launch-overhead failure mode documented in Polyline Path Masked Attention for Vision Transformer. We will fuse the remainder and ReLU relaxation steps with a Triton-style kernel, in the spirit of the custom kernels in LiteASR. Soundness is a first-class constraint. VNN-COMP 2021 reports that GPU tools produced mismatched verdicts because of floating-point rounding. We will therefore add a per-layer rounding term to $r$, derived from a worst-case bound on accumulated matrix-multiply error. We will also cross-check every verdict against the outward-rounded CPU implementation of Krukowski et al.
The second component is a measured cost model and an allocation rule. For each layer shape and candidate $k$ on each GPU, we time the fused layer to obtain a latency $t_l(k)$. We choose budgets by solving
$$\max_{k_1,\dots,k_L} \; \tau(k_1,\dots,k_L) \quad \text{subject to} \quad \sum_{l=1}^{L} t_l(k_l) \le T,$$
where $\tau$ is output tightness estimated on held-out input boxes and $T$ is a latency budget. We solve this greedily by marginal tightness gained per marginal millisecond. The FLOP-based version of this rule replaces $t_l(k)$ with the FLOP count of the layer and serves as the key ablation.
The third component is the analysis that tests the core hypothesis. We will plot latency against $k$ per layer and identify the knee at which the matrix multiply stops being dominated by memory traffic. We will check whether that knee moves across GPUs and with batch size, meaning the number of input boxes processed together. Batch size matters because branch-and-bound verifiers process thousands of subdomains at once, as in Beta-CROWN, which changes the arithmetic intensity.
A secondary study connects to certified training. Understanding Certified Training with Interval Bound Propagation finds that tightness decays exponentially with depth but only polynomially with width, and recommends wide, shallow networks without bottlenecks. It evaluates cost in parameters, not latency. We will time those recommended architectures, in both inference and IBP training, against deeper networks matched on certified accuracy. We will also test the claim in On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models that IBP training costs "only 2-3x more" than natural training, measuring wall-clock time rather than operation counts. Mao et al. also report that training with tighter bounds underperforms IBP training. That finding constrains us, so we do not propose training with our bounds. We use it only to show whether the wide-shallow advice survives a latency accounting.
Baselines
The naive reference point is plain IBP run as fused element-wise GPU kernels on the same networks. It defines the fastest achievable latency and the loosest bounds. We will run it with the same batching and compilation as our method, so that any gain we show comes from dependency tracking rather than better engineering. We count ourselves as beating it only if we verify strictly more properties within IBP's own latency plus a small, stated margin.
The strongest existing method is the α,β-CROWN verifier from Beta-CROWN. It propagates linear bounds backward through the network on GPUs and optimizes relaxation and split multipliers by gradient ascent. It is the right competitor because it already runs as dense GPU tensor algebra and it won VNN-COMP 2021 with 779.7 points, ahead of VeriNet at 705.0 and ERAN at 643.4. Those are competition scores computed on the organizers' AWS hardware against other tools, so we cannot reproduce them directly. We will rerun α,β-CROWN ourselves on the same GPU, benchmarks and per-instance timeouts, with its default configuration plus a matched hyperparameter search. Our method will enter the same branch-and-bound loop as a drop-in incomplete bounding step.
Beating α,β-CROWN means one of two outcomes at equal wall-clock budget. The first is more verified instances on at least some benchmark families. The second is equal verified counts at lower median time per instance. We expect any win to come from the inner loop, where many cheap bounds are needed, not from the final tightest bound.
The CPU affine and doubleton implementations of Krukowski et al. provide a tightness ceiling and a soundness reference. They also isolate how much of our gain comes from moving to GPUs as opposed to fixing the budget.
The key ablation isolates the core idea. It keeps everything identical, including kernels, condensation and hardware, but chooses $k_l$ by FLOPs, or uniformly, instead of by measured latency. If latency-chosen and FLOP-chosen allocations perform the same, the FLOPs-latency discrepancy does not matter for verifiers and the central claim fails.
Why not just…?
Why not just use α,β-CROWN, since it is already GPU-native linear bounding? This is the real threat. Backward linear bounding is at least as tight as affine forms for a given relaxation. Its cost, however, grows with the number of intermediate neurons whose bounds must be refined, and it must run a backward pass from each refined layer. A forward affine form yields bounds for all intermediate layers in a single forward pass with a cost fixed in advance. We will not argue the point in the abstract. The head-to-head at equal wall-clock budget on ACAS Xu, MNIST, CIFAR-10 and the VNN-COMP 2021 families settles it. If α,β-CROWN dominates everywhere, the contribution shrinks to the latency characterization and the training-architecture study. We would then report that outcome plainly.
Why not just spend the time on more IBP splits, as ReluVal-style bisection does? IBP is so cheap that splitting the input domain more finely could beat tighter bounds per split. Formal Security Analysis of Neural Networks using Symbolic Intervals already shows that symbolic tracking cuts overestimation by over 85% relative to naive intervals. It also shows that tracking plus bisection achieves a 200x average speedup over Reluplex on ACAS Xu. That evidence suggests tracking pays off, but it was measured on CPUs. Our equal-time comparison of IBP-with-splits against budgeted affine arithmetic with splits, on GPU, tests this directly. Its result is informative in both directions.
Why not just pick the budget by FLOPs, which is simpler and hardware-independent? If latency were proportional to FLOPs for these kernels, a FLOP-based rule would be equivalent and easier to transfer across machines. The ablation above answers this. We will also report the correlation between FLOPs and measured latency per layer across two GPUs and several batch sizes. A high correlation would mean the systems literature's warning does not carry over to verification, and we would adopt the FLOP rule.
Proposed Experiments
We will use four benchmark settings. The first is ACAS Xu, the 45 collision-avoidance networks used by ReluVal and VNN-COMP. The second is the MNIST and CIFAR-10 networks and the Digits and SVHN settings from Krukowski et al. The third is the VNN-COMP 2021 categories, including Cifar10_resnet and Cifar2020. The fourth is the IBP-trained CIFAR-10 and TinyImageNet networks in the style of Mao et al.
We will report four kinds of result. The first is tightness, measured as maximal interval diameter and the τ ratio, against measured median and tail latency, alongside FLOPs. The second is verified instance counts under fixed per-instance time limits. The third is GPU memory use. The fourth is the number of soundness mismatches against the CPU outward-rounded reference, which must be zero for any reported result.
For context on the certified-training study, the file reports a verified CIFAR-10 error of 67.96% at $\epsilon = 8/255$ for Gowal et al.. Mao et al. report τ rising from $10^{-9}$ to 0.98 under IBP training. We found no reported wall-clock latency on Lacuna for the wide-shallow architectures of Mao et al. Our timing study fills exactly that gap.
Three checks are decisive. The first is whether per-layer latency is nearly flat in $k$ up to a hardware knee while FLOPs rise linearly. The second is whether latency-chosen budgets verify more instances than FLOP-chosen and uniform budgets at equal wall-clock time. The third is whether budgeted affine arithmetic, used inside branch-and-bound, matches or beats α,β-CROWN's bounding step on some benchmark family at equal time. If the first check fails, the project ends as a negative systems result. If the first holds but the second fails, the FLOP rule is adequate. Only if all three hold does the proposal deliver a better verifier.
References
- Make Interval Bound Propagation great again
- Formal Security Analysis of Neural Networks using Symbolic Intervals
- ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design
- TResNet: High Performance GPU-Dedicated Architecture
- Searching for Fast Model Families on Datacenter Accelerators
- Understanding Certified Training with Interval Bound Propagation
- Polyline Path Masked Attention for Vision Transformer
- LiteASR: Efficient Automatic Speech Recognition with Low-Rank Approximation
- The Second International Verification of Neural Networks Competition (VNN-COMP 2021): Summary and Results
- Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Neural Network Robustness Verification
- On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models