Dynamic Algorithm Termination for Branch-and-Bound-based Neural Network Verification

Konstantin Kaulen, Matthias König, Holger H. HoosAAAI 2025 · OpenReview

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.

Classification performance (Accuracy, TPR, FPR) of the early termination model across different verifiers and benchmarks.

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.

Comparison of running time and number of solved instances between the baseline and the proposed dynamic termination method. Percentages in parentheses indicate the portion of original time consumed.

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

Abstract

With the rising use of neural networks across various application domains, it becomes increasingly important to ensure that they do not exhibit dangerous or undesired behaviour. In light of this, several neural network robustness verification algorithms have been developed, among which methods based on Branch and Bound (BaB) constitute the current state of the art. However, these algorithms still require immense computational resources. In this work, we seek to reduce this cost by leveraging running time prediction techniques, thereby allowing for more efficient resource allocation and use. Towards this end, we present a novel method that dynamically predicts whether a verification instance can be solved in the remaining time budget available to the verification algorithm. We introduce features describing BaB-based verification instances and use these to construct running time, and more specifically, timeout prediction models. We leverage these models to terminate runs on instances early in the verification process that would otherwise result in a timeout. Overall, using our method, we were able to reduce the total running time by 64% on average compared to the standard verification procedure, while certifying a comparable number of instances.
BibTeX
@inproceedings{kaulen2025dynamic,
  author = {Konstantin Kaulen and Matthias König and Holger H. Hoos},
  title = {{Dynamic Algorithm Termination for Branch-and-Bound-based Neural Network Verification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=sfHgFfKDGJ},
}
Figure