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

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

TL;DR

ABONN (Adaptive BaB with Order for Neural Network verification) supercharges the standard Branch-and-Bound verification process by using Monte-Carlo Tree Search (MCTS). By prioritizing sub-problems most likely to contain counterexamples, it achieves speedups of up to 24.7× on complex models compared to traditional "blind" search methods.

What Problem Does This Paper Address?

Ensuring that deep neural networks (DNNs) are safe and robust is a major challenge. Formal verification aims to prove that a network won't misbehave (e.g., misclassify a slightly perturbed image).

The current state-of-the-art approach is Branch-and-Bound (BaB). BaB works by taking a hard verification problem and splitting it into smaller, easier sub-problems (branching). However, most BaB tools explore these sub-problems naively—usually in a "breadth-first" or "first-come, first-served" manner. This is inefficient because it treats every branch as equally important, wasting massive amounts of computation on "boring" parts of the search tree while the actual counterexample might be hidden in a branch that hasn't been checked yet.

Methods

The authors introduce ABONN, which replaces the "dumb" search of BaB with an adaptive, "smart" search guided by Monte-Carlo Tree Search (MCTS).

  1. Counterexample Potentiality: The authors define a new metric for "importance." A sub-problem is considered promising if it has a high likelihood of containing a counterexample. This is calculated based on:
  2. Node Depth: Deeper nodes have fewer approximations, making them more likely to reveal a real violation.
  3. 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.
  4. MCTS-Style Exploration: Instead of a standard queue, ABONN uses the UCB1 (Upper Confidence Bound) algorithm to navigate the search tree. This allows the tool to balance:
  5. Exploitation: Focusing on branches that look highly "promising" based on current data.
  6. Exploration: Occasionally checking less promising branches to ensure the search doesn't get stuck in a local dead end.
  7. Early Termination: As soon as a real counterexample is found in any branch, the entire process terminates immediately, saving the time that would have been spent verifying the rest of the tree.

Datasets

The approach was evaluated on 552 verification problems across two major benchmarks:

  • MNIST: Using two fully connected network architectures (MNIST_L2 and MNIST_L4).
  • CIFAR-10: Using three convolutional network architectures (Base, Wide, and Deep). These problems were drawn from the VNN-COMP (International Verification of Neural Networks Competition) suite, focusing on $L_\infty$-based local robustness.

Key Insights and Ideas

  • Search Order Matters: The core "aha moment" is that the order in which we visit sub-problems is just as important as how we split them. By treating verification as a search for a "reward" (a counterexample), we can use reinforcement learning techniques like MCTS.
  • Imbalanced Trees are Good: Traditional BaB tries to keep the search tree somewhat balanced. ABONN intentionally creates an "imbalanced" tree, diving deep into suspicious branches while ignoring safe ones.
  • Synergy with Heuristics: Interestingly, the adaptive search doesn't just help find counterexamples; it also helps in "certified" cases (where no violation exists). The authors found that their search strategy actually helps existing ReLU selection heuristics perform better by leading them to more effective splits.

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.
  • Efficiency in Complexity: The advantages of ABONN became more pronounced as the models became larger and more complex (e.g., the "Deep" and "Wide" CIFAR models).

Limitations and Future Work

  • Heuristic Dependence: While ABONN is "orthogonal" to branching heuristics (meaning it can work with any of them), its performance is still tied to the quality of the underlying approximated verifier and the ReLU selection method used.
  • Hyperparameter Sensitivity: The performance relies on tuning $\lambda$ (weighting depth vs. verifier output) and $c$ (the exploration constant in UCB1). While the authors found stable defaults ($\lambda=0.5, c=0.2$), these might vary for different types of properties.
  • Future Direction: The authors plan to investigate how to more tightly integrate MCTS with advanced branching heuristics like DeepSplit to further accelerate the verification of very large-scale 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 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 commonlyused 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× on MNIST and 24.7× 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},
}

Loading related content...

Figure