Introduction
Deep neural networks are notoriously vulnerable to adversarial attacks—small, imperceptible perturbations that can cause a model to misclassify inputs. To guarantee safety, researchers employ formal verification to mathematically prove a model's robustness. However, this process is computationally intensive, often taking hours per image. When selecting the most robust model from a large pool of candidates, such as in Neural Architecture Search (NAS), the total verification time can reach thousands of GPU hours. This paper introduces a "racing" framework that significantly accelerates this selection process by disqualifying underperforming models early and prioritizing the most informative test instances.
The Racing Framework
The core idea behind the proposed approach is to treat model selection as a competition. Instead of exhaustively verifying every model on every image in a test set, the authors propose two main racing algorithms:
- Naive Racing: This aggressive strategy verifies models on one image at a time. If a model's robust accuracy falls below that of its competitors, it is immediately discarded.
- F-Race: A more conservative approach that uses statistical tests (Cochran’s Q and McNemar’s test) to ensure a model is statistically inferior before elimination, mitigating the risk of premature disqualification due to the random order of test images.
Δ-Sorting: A Smart Selection Mechanism
Standard racing algorithms typically select test images at random. This paper introduces Δ-sorting to make the racing process more efficient. The Δ-value is defined as the difference between a model's highest and second-highest output scores (logits). A small Δ indicates that the model is "unsure," suggesting the input is near a decision boundary and thus more likely to be vulnerable to adversarial attacks.
As shown in Figure 2, there is a clear statistical correlation: non-robust (unsat) instances consistently exhibit lower Δ-values than robust (sat) ones. By sorting the test set and evaluating these "hard" images first, the racing algorithm can expose model weaknesses much earlier, leading to faster disqualifications.
Experimental Evaluation
The authors evaluated their framework on MNIST (31 models) and CIFAR-10 (27 models) using state-of-the-art verifiers like VeriNet and β-CROWN.
Efficiency Gains
The racing method achieved dramatic speedups compared to exhaustive evaluation:
- MNIST: Up to 108x faster.
- CIFAR-10: Up to 42x faster.
For CIFAR-10, where exhaustive verification required 558 GPU hours, the racing approach identified the optimal model in a fraction of the time.
Model Pruning Dynamics
The effectiveness of the sorting mechanism is most evident when observing how quickly the pool of candidate models shrinks.
As illustrated in Figure 6, the "Naive racing with sorting mechanism" (red dotted line) prunes the search space almost instantly. Surprisingly, despite its aggressiveness, Naive Racing consistently reached zero "regret"—meaning it successfully identified the absolute best model—after processing only a tiny fraction of the test data.
Conclusion and Future Work
The racing framework, combined with Δ-sorting, offers a powerful solution to the bottleneck of robust model selection. By focusing computational resources on the most vulnerable instances and the most promising models, it achieves order-of-magnitude speedups without sacrificing the quality of the final selection.
Future research could explore the applicability of Δ-sorting to other perturbation types, such as rotations or brightness changes, and investigate whether these efficiency gains scale to even larger, more complex neural architectures.
Summary updated