Abstract
Neural Network Certification (NNC) is essential for safety-critical AI, yet standard Interval Bound Propagation (IBP) suffers from the "wrapping effect," where axis-aligned bounding boxes lead to exponentially loose bounds. This paper adapts Affine Arithmetic (AA) and Doubleton Arithmetic (DA) from validated numerics to provide tighter, certifiable robustness guarantees by accounting for linear dependencies between neurons.
Introduction
To deploy deep learning in safety-critical areas like autonomous driving or medical diagnosis, we need Neural Network Certification (NNC)—a way to prove that a small change in input (like a few pixels of noise) won't flip a model's prediction.
The most common tool for this is Interval Bound Propagation (IBP). IBP is popular because it’s fast: you take an input range (an "interval") and push it through the network layer by layer. However, IBP has a fatal flaw known as the wrapping effect. Because IBP represents sets of values as simple axis-aligned hyper-cubes (boxes), it cannot account for rotations or correlations between neurons.
The Wrapping Effect
In a simple linear layer, a rotated set must be "wrapped" in a new, larger axis-aligned box. As these boxes pass through dozens of layers, the overestimation grows exponentially, eventually leading to bounds so loose they become useless for certification. One of the most striking theoretical contributions of this work proves that IBP leads to exponential bound growth even for orthogonal linear layers. You don't even need complex non-linearities for IBP to fail; the geometry of the "box" itself is the problem.
Methods
The authors propose replacing standard interval arithmetic with two more sophisticated frameworks borrowed from the field of strict numerical computation:
- Doubleton Arithmetic (DA): Originally used for rigorous integration of Differential Equations, DA represents sets using a combination of a center point, a linear transformation of an interval, and an error term. It is highly accurate but computationally heavy.
- Affine Arithmetic (AA): AA represents quantities as affine combinations of "noise symbols." This allows the framework to keep track of linear dependencies between variables. When two neurons are correlated, AA knows it, preventing the "box" from expanding unnecessarily during linear transformations.
Crucially, the authors implemented these methods in C++ using the CAPD library. Unlike standard Python-based deep learning, this approach provides full control over floating-point rounding errors (IEEE 754), making the resulting bounds "completely certifiable."
Experimental Evaluation
The methods were evaluated on several standard benchmarks to test scalability and tightness of bounds, including MNIST, CIFAR-10, SVHN, and a smaller Digits dataset ($8 \times 8$ gray-scale images).
Key Results
- Superior Tightness: In all tests, AA and DA produced average maximal diameters of output intervals that were significantly lower than IBP.
- Efficiency: While Doubleton Arithmetic is mathematically powerful, the authors found that Affine Arithmetic is the practical winner. It produces bounds nearly as tight as DA but is orders of magnitude faster, making it viable for larger CNNs. AA's complexity remains manageable for modern architectures compared to DA's $O(n^3)$.
- Resistance to Large Perturbations: In experiments, as the input perturbation ($\epsilon$) increases, IBP bounds quickly explode to a diameter of 1.0 (meaning the model is 100% uncertain). AA and DA maintain much smaller diameters, providing meaningful guarantees where IBP offers none.
- Robustness to Masking: The authors tested "partially masked data" (where 50% of pixels are zeroed out). Even in this high-uncertainty scenario, AA and DA bounds remained close to the theoretical lower bound, while IBP bounds were several orders of magnitude wider.
Discussion and Limitations
While IBP is a great regularizer during training to make a network robust, it is a poor tool for certifying a network that has already been trained. AA provides a middle ground: it is more expensive than IBP but significantly more accurate.
However, challenges remain. Although AA is faster than DA, both are still more expensive than standard IBP. AA's cost is non-constant and depends on the input arguments. Furthermore, applying these techniques to massive Transformers or LLMs remains a challenge due to the memory overhead of tracking affine dependencies. Finally, while AA handles linear layers perfectly, non-linear functions like ReLU and Softmax still require approximations. Further refining how these functions are "wrapped" to minimize error is a key area for future work.
Summary updated