Adaptive Branch-and-Bound Tree Exploration for Neural Network Verification

Kota Fukuda, Guanqin Zhang, Zhenya Zhang, Yulei Sui, Jianjun Zhao

Abstract

Formal verification is a rigorous approach that can provably ensure the quality of neural networks. To date, Branch-and-Bound (BaB) is the state-of-the-art framework for verification, performing its task by splitting the problem into sub-problems and applying off-the-shelf verifiers. However, existing BaB implementations often suffer from inefficiencies due to naive exploration strategies that ignore the relative importance of different sub-problems. To bridge this gap, we introduce ABONN (Adaptive BaB with Order for Neural Network verification), a novel approach that explores the sub-problem space adaptively using a Monte-Carlo Tree Search (MCTS) style strategy. By prioritizing sub-problems more likely to contain counterexamples, ABONN achieves significant speedups—up to 15.2× on MNIST and 24.7× on CIFAR-10—compared to traditional verifiers.

Introduction

Ensuring that deep neural networks (DNNs) are safe and robust is a major challenge in modern AI. Formal verification aims to provide mathematical proof that a network will not misbehave under specific conditions, such as misclassifying a slightly perturbed image.

The current state-of-the-art approach, Branch-and-Bound (BaB), works by taking a difficult verification problem and recursively splitting it into smaller, more manageable sub-problems (branching). However, most BaB tools explore these sub-problems naively, typically using breadth-first or first-come, first-served heuristics. This "blind" search is inefficient because it treats every branch as equally important, often wasting computational resources on "safe" regions of the search space while a counterexample remains hidden in an unvisited branch.

The ABONN Framework

ABONN replaces the standard search mechanisms of BaB with an adaptive, "smart" search guided by Monte-Carlo Tree Search (MCTS) principles. The core innovation lies in how the algorithm prioritizes which part of the search tree to explore next.

1. Defining Counterexample Potentiality

The authors introduce a metric for "importance" that reflects the likelihood of a sub-problem containing a counterexample. This is calculated based on two primary factors:

  • Node Depth: Deeper nodes in the BaB tree involve fewer approximations, making them more likely to reveal a real violation of the property being verified.
  • Verifier Output ($p$): Approximated verifiers return a value indicating how close a property is to being violated. Larger negative values suggest a higher potential for a real counterexample.

2. MCTS-Style Exploration

Instead of a standard queue, ABONN utilizes the UCB1 (Upper Confidence Bound) algorithm to navigate the search tree. This allows the tool to balance two critical needs:

  • Exploitation: Focusing on branches that appear highly promising based on current data.
  • Exploration: Occasionally checking less promising branches to ensure the search does not become trapped in a local dead end.

3. Early Termination

By prioritizing branches with high counterexample potentiality, ABONN can terminate the entire process as soon as a single real violation is found. This saves the significant time that traditional methods would spend verifying the remainder of the tree.

Experimental Evaluation

The approach was evaluated on 552 verification problems drawn from the VNN-COMP (International Verification of Neural Networks Competition) suite, focusing on $L_\infty$-based local robustness. The benchmarks included:

  • MNIST: Two fully connected network architectures (MNIST_L2 and MNIST_L4).
  • CIFAR-10: Three convolutional network architectures (Base, Wide, and Deep).

Key Results

ABONN demonstrated significant performance gains over both a standard BaB baseline and the high-performance $\alpha\beta$-Crown verifier:

  • Massive Speedups: On CIFAR-10, ABONN was up to 24.7× faster than the BaB baseline. On MNIST, it achieved up to 15.2× speedup.
  • Higher Success Rate: In the CIFAR-10 Base model, ABONN solved 106 instances within the time limit, compared to only 27 for the BaB baseline and 32 for $\alpha\beta$-Crown.
  • Scalability: The advantages of ABONN became increasingly pronounced as the models grew in size and complexity, particularly in the "Deep" and "Wide" CIFAR-10 models.

Discussion and Insights

Search Order as a First-Class Citizen

A core insight of this research is that the order in which sub-problems are visited is just as critical as the strategy used to split them. By treating verification as a search for a "reward" (a counterexample), reinforcement learning techniques like MCTS can be effectively applied to formal methods.

Strategic Imbalance

While traditional BaB often seeks to maintain a balanced search tree, ABONN intentionally creates an "imbalanced" tree. It dives deep into suspicious branches while ignoring demonstrably safe ones, leading to faster falsification of properties.

Synergy with Heuristics

Interestingly, the adaptive search also benefits "certified" cases where no violation exists. The authors found that their search strategy helps existing ReLU selection heuristics perform better by leading them toward more effective splits earlier in the process.

Limitations and Future Work

Despite its success, ABONN's performance remains tied to the quality of the underlying approximated verifier and the ReLU selection method. Furthermore, the algorithm requires tuning of hyperparameters, such as the weight of depth versus verifier output ($\lambda$) and the exploration constant ($c$). While the authors identified stable defaults ($\lambda=0.5, c=0.2$), these may vary across different property types.

Future research will investigate tighter integration between MCTS and advanced branching heuristics, such as DeepSplit, to further accelerate the verification of large-scale, industrial-grade neural networks.

Summary updated

Abstract

Formal verification is a rigorous approach that can provably ensure the quality of neural networks, and to date, Branch and Bound (BaB) is the state-of-the-art that performs verification by splitting the problem as needed and applying off-the-shelf verifiers to sub-problems for improved performance. However, existing BaB may not be efficient, due to its naive way of exploring the space of sub-problems that ignores the \emph{importance} of different sub-problems. To bridge this gap, we first introduce a notion of ``importance'' that reflects how likely a counterexample can be found with a sub-problem, and then we devise a novel verification approach, called ABONN, that explores the sub-problem space of BaB adaptively, in a Monte-Carlo tree search (MCTS) style. The exploration is guided by the ``importance'' of different sub-problems, so it favors the sub-problems that are more likely to find counterexamples. As soon as it finds a counterexample, it can immediately terminate; even though it cannot find, after visiting all the sub-problems, it can still manage to verify the problem. We evaluate ABONN with 552 verification problems from commonly-used datasets and neural network models, and compare it with the state-of-the-art verifiers as baseline approaches. Experimental evaluation shows that ABONN demonstrates speedups of up to $15.2\times$ on MNIST and $24.7\times$ on CIFAR-10. We further study the influences of hyperparameters to the performance of ABONN, and the effectiveness of our adaptive tree exploration.
BibTeX
@inproceedings{fukuda2025adaptive,
  author = {Kota Fukuda and Guanqin Zhang and Zhenya Zhang and Yulei Sui and Jianjun Zhao},
  title = {{Adaptive Branch-and-Bound Tree Exploration for Neural Network Verification}},
  booktitle = {DATE},
  year = {2025},
  url = {https://openreview.net/forum?id=cxEUDUlpMV},
}
Figure