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