Abstract
Formal verification of neural networks is a computationally intensive task, often hindered by "hard" instances that consume significant resources before eventually timing out. This paper presents a dynamic termination strategy that utilizes machine learning to predict, during execution, whether a verification attempt will succeed within its allocated time budget. By monitoring the internal state of Branch-and-Bound (BaB) solvers, the proposed framework reduces total computation time by an average of 64% across diverse benchmarks while maintaining nearly the same number of certified instances.
Introduction
Ensuring the robustness of neural networks—such as verifying that a small perturbation to an input image does not change its classification—is an NP-complete problem. State-of-the-art "complete" verifiers typically employ a Branch-and-Bound (BaB) approach, which recursively partitions the input space into smaller sub-problems. However, these algorithms are often "all or nothing": a verifier may spend substantial GPU or CPU time on a single instance only to reach a timeout without a conclusive result. In large-scale evaluation suites, this "sunk cost" on unsolvable instances represents a major bottleneck. This research addresses the lack of standard mechanisms for identifying these "lost causes" early in the verification process.
Methodology: Dynamic Algorithm Termination
The authors propose a Dynamic Algorithm Termination framework that monitors a verifier's progress at regular intervals, known as checkpoints. Instead of relying solely on initial problem characteristics, the system evaluates the evolving state of the search tree.
Feature Extraction
The framework utilizes two categories of cheaply computable features:
- Static Features: Properties available before the search begins, such as the initial prediction margin and the count of unstable neurons.
- Dynamic Features: Snapshots of the BaB process, including current search tree depth, the number of solved branches, and the tightening of global lower and upper bounds.
Checkpoint Classifiers
At fixed intervals (e.g., every 10 seconds), a Random Forest classifier analyzes these features to predict the probability that the instance will be solved before the final cutoff (typically 600 seconds). To prioritize the preservation of solvable instances, a high confidence threshold ($\theta = 0.99$) is employed. The search is only terminated early if the model is extremely certain that the instance will fail to be verified within the budget.
Experimental Evaluation
The method was integrated into three prominent verification tools: $\alpha\beta$-CROWN, VeriNet, and Oval. Evaluation was conducted on a wide range of benchmarks from the International Verification of Neural Networks competition (VNN-COMP), including MNIST, CIFAR-10, Vision Transformers (ViT), and Tiny ImageNet. A 5-fold cross-validation protocol was used to ensure the generalizability of the trained classifiers.
Results and Discussion
The experimental results demonstrate that the internal state of a BaB tree provides a highly reliable signal for predicting search outcomes. Dynamic features effectively capture the "discovered difficulty" of a problem that static features alone cannot anticipate.
Efficiency and Accuracy
On average, the proposed method achieved a 64% reduction in total running time. The classifiers were highly effective, correctly identifying approximately 84% of timeouts while incorrectly terminating only 5% of solvable instances. In extreme cases, such as the Marabou benchmark using $\alpha\beta$-CROWN, the system achieved a 95% reduction in total computation time.
Impact on Certification
Crucially, the massive speedup did not come at the cost of verification power. The number of successfully certified instances remained nearly identical to the standard, full-budget verification procedure. This suggests that the framework successfully identifies instances that are truly beyond the reach of the current solver's budget.
Conclusion and Future Work
Dynamic Algorithm Termination offers a practical path toward scaling neural network verification to larger and more complex models by eliminating wasted computation. While the current approach requires training data specific to the verifier and benchmark, future work could explore more universal features or "Algorithm Selection" strategies—using these predictive signals to choose the most suitable verifier for a specific instance before the search even begins.
Summary updated