Make Interval Bound Propagation great again

Patryk Krukowski, Daniel Wilczak, Jacek Tabor, Anna Bielawska, Przemyslaw Spurek

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.

Comparison of IBP and AA propagation showing the wrapping effect.

Methods

The authors propose replacing standard interval arithmetic with two more sophisticated frameworks borrowed from the field of strict numerical computation:

  1. 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.
  2. 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

Abstract

In various scenarios motivated by real life, such as medical data analysis, autonomous driving, and adversarial training, we are interested in robust deep networks. A network is robust when a relatively small perturbation of the input cannot lead to drastic changes in output (like change of class, etc.). This falls under the broader scope field of Neural Network Certification (NNC). Two crucial problems in NNC are of profound interest to the scientific community: how to calculate the robustness of a given pre-trained network and how to construct robust networks. The common approach to constructing robust networks is Interval Bound Propagation (IBP). This paper demonstrates that IBP is sub-optimal in the first case due to its susceptibility to the wrapping effect. Even for linear activation, IBP gives strongly sub-optimal bounds. Consequently, one should use strategies immune to the wrapping effect to obtain bounds close to optimal ones. We adapt two classical approaches dedicated to strict computations -- Dubleton Arithmetic and Affine Arithmetic -- to mitigate the wrapping effect in neural networks. These techniques yield precise results for networks with linear activation functions, thus resisting the wrapping effect. As a result, we achieve bounds significantly closer to the optimal level than IBPs.
BibTeX
@misc{krukowski2024make,
  author = {Patryk Krukowski and Daniel Wilczak and Jacek Tabor and Anna Bielawska and Przemyslaw Spurek},
  title = {{Make Interval Bound Propagation great again}},
  year = {2024},
  eprint = {2410.03373},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.03373},
}
Figure