🤖 machine learning

Branch and Bound for Relational Verification of Neural Networks

This paper introduces SaBRe, a branch-and-bound framework for relational neural network verification that improves efficiency and scalability by splitting relational neurons based on a dual-formulation selection strategy, outperforming existing baselines across multiple benchmarks.

Original authors: Kota Fukuda, Zhenya Zhang, Guanqin Zhang, Jianjun Zhao

Published 2026-08-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kota Fukuda, Zhenya Zhang, Guanqin Zhang, Jianjun Zhao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the safety inspector for a fleet of self-driving cars. These cars are powered by "neural networks," which are basically super-smart computer brains that learn to recognize things like stop signs or pedestrians by looking at millions of examples. But here's the catch: these brains can be a little too sensitive. If a stop sign has a tiny sticker on it, or if the lighting changes just a little bit, the car might suddenly think it's a speed limit sign and zoom right through. To keep everyone safe, we need to prove that the car's brain won't get confused by small changes. This is called "verification."

For a long time, safety inspectors only checked if the car could handle one specific change at a time, like "Will this car still see the stop sign if I add a tiny dot to the image?" But in the real world, we need to check something much bigger: "Will the car behave consistently no matter what the weather is like, or if the road is slightly wet?" This is called "relational verification." It's like asking, "If I drive the car in two slightly different scenarios, will it make the same safe decision in both?" The problem is that checking two scenarios at once is mathematically much harder than checking just one. It's like trying to balance two spinning plates at once instead of just one; the old tools often get confused and start screaming "Danger!" when there actually isn't any, or they miss real dangers entirely.

This paper introduces a new tool called SABRE (Splitting Approximated Bounds for RElational verification) to solve this tricky balancing act. Think of the old way of checking these cars as trying to fix a messy room by picking up one sock at a time. If the room is huge and the socks are everywhere, you might spend forever picking up socks and still miss the big pile of laundry in the corner. The authors realized that in the world of "relational" problems (checking two scenarios at once), the real mess isn't the individual socks (the single data points); it's the difference between the two piles of laundry.

So, SABRE changes the strategy. Instead of picking up one sock at a time, it grabs the difference between the two piles and splits that apart. Imagine you have two nearly identical maps of a city. The old method would check every single street on both maps separately. SABRE, however, looks at the tiny differences between the two maps and splits the problem based on those differences. If the maps disagree about a specific turn, SABRE zooms in on that disagreement immediately.

The researchers tested this new method on 817 different safety problems using standard datasets like ACAS Xu (for air traffic control), MNIST, CIFAR, and GTSRB (for image recognition). They found that SABRE was much better at solving these problems than the previous best methods. In fact, it solved significantly more problems and did so faster. For example, on the ACAS Xu dataset, SABRE solved 67 problems where the old method only solved 42. On the GTSRB dataset, it solved 33 problems compared to the old method's 9.

Crucially, the paper argues that the old way of splitting problems—focusing on individual parts of the network—is often the wrong move for these "two-at-a-time" checks. By focusing on the relationship between the two scenarios, SABRE cuts through the confusion much more efficiently. The authors also designed a smart "selector" that helps SABRE decide which difference to split next, kind of like a detective who knows exactly which clue to follow to solve a mystery the fastest. When they tested this smart selector against a random guesser, the smart selector solved way more problems, proving that knowing what to split is just as important as splitting it.

In short, the paper suggests that by changing how we break down the problem—focusing on the relationship between two scenarios rather than the scenarios themselves—we can make self-driving cars and other AI systems much safer and easier to verify. It doesn't solve every single problem in the world yet, but it shows a clear path forward that is significantly better than what we had before.

Technical Summary: Branch and Bound for Relational Verification of Neural Networks (SABRE)

Problem Statement
The paper addresses the challenge of verifying neural networks against relational specifications, specifically global robustness. Unlike local robustness, which ensures a network's output remains stable under small perturbations to a single input, global robustness requires reasoning about the relationship between multiple network inferences. Formally, a network is globally robust if, for any two inputs within a bounded distance $\epsilon$ , the difference in their outputs is bounded by $\delta$ .

Existing approaches for relational verification primarily rely on sound over-approximation techniques (e.g., RaVeN) using convex domains to bound the differences between network outputs. While efficient, these methods are inherently incomplete and prone to generating false alarms (spurious counterexamples) due to the looseness of the approximations. Although Branch and Bound (BaB) is a standard technique for refining approximations in local robustness verification by splitting individual neurons, its application to relational verification has been limited. Previous attempts (e.g., RABBit) applied BaB to relational problems by splitting individual neurons, which the authors argue fails to exploit the specific structure of relational constraints and may yield suboptimal refinement.

Methodology: The SABRE Framework
The authors propose SABRE (Splitting Approximated Bounds for RElational verification), a Branch and Bound framework designed specifically for relational verification. The core innovation lies in shifting the splitting strategy from individual neurons to relational neurons.

Relational Neurons and Problem Splitting:
- The framework models the difference between two network inferences using relational neurons ( $\Delta y^{(i)}_j = y^{(i)}_j - \hat{y}^{(i)}_j$ ), which represent the difference between corresponding neurons in two parallel network copies.
- Instead of splitting based on the activation state of an individual neuron (e.g., $x > 0$ vs. $x < 0$ ), SABRE splits based on the sign of the relational neuron's input ( $\Delta x^{(i)}_j \geq 0$ vs. $\Delta x^{(i)}_j \leq 0$ ).
- This approach directly targets the uncertainty in the difference between outputs, aiming to tighten the bounds of the relational difference more effectively than splitting individual components.
Dual-Based Neuron Selection Strategy:
- A critical factor in BaB efficiency is selecting which neuron to split at each step. To avoid the computational cost of solving sub-problems to estimate impact, SABRE employs a Lagrangian dual formulation of the verification problem.
- The authors derive a dual problem where the objective function is a summation of neuron-wise terms. These terms capture the contribution of specific neurons to the final output bound under linear relaxation.
- By analyzing how splitting a specific relational neuron affects the coefficients in the dual objective function, SABRE can efficiently estimate the potential refinement (tightening of bounds) without solving the sub-problems. The algorithm selects the relational neuron that maximizes this estimated improvement.
Workflow:
- The process begins with an approximation verifier (e.g., RaVeN) to check the global robustness property.
- If a false alarm is detected, the algorithm selects a relational neuron using the dual-based strategy.
- The problem is split into two sub-problems by adding constraints on the selected relational neuron's input.
- This recursive process continues until all sub-problems are verified or a real counterexample is found.

Key Contributions

Novel Splitting Strategy: The paper introduces a BaB framework that prioritizes splitting relational neurons rather than individual neurons, arguing that this directly addresses the source of approximation error in relational specifications.
Dual-Based Selection Heuristic: The authors extend the dual formulation approach (previously used for local robustness) to the relational setting, enabling efficient, data-driven selection of the most impactful relational neuron to split.
SABRE Implementation: A complete verification framework integrating these strategies, capable of handling global robustness properties across various network architectures.

Experimental Results
The authors evaluated SABRE on 817 verification instances across five datasets: ACAS Xu, MNIST-F, MNIST-C, CIFAR, and GTSRB. The evaluation compared SABRE against:

RaVeN: A state-of-the-art approximation verifier without refinement.
ClasIS & DualIS: Variants of BaB that split individual neurons (ClasIS uses standard selection; DualIS uses the proposed dual formulation but applied to individual neurons).
RandRS: A variant of SABRE using random neuron selection.

Key Findings:

Performance vs. RaVeN: SABRE significantly outperformed RaVeN, solving a substantially higher number of instances by effectively refining approximations that RaVeN could not verify.
Relational vs. Individual Splitting: On most benchmarks (ACAS Xu, MNIST-F, MNIST-C, GTSRB), SABRE (relational splitting) solved more instances, explored fewer sub-problems, and required less time than individual splitting methods (ClasIS, DualIS).
- Note on CIFAR: On the CIFAR dataset with small perturbation radii ( $\epsilon$ ), individual splitting methods initially outperformed SABRE. The authors attribute this to the high number of unstable ReLUs in CIFAR models, which dilutes the local impact of relational splits. However, as $\epsilon$ increased, relational splitting became more effective.
Selection Strategy: The dual-based selection strategy (SABRE) significantly outperformed random selection (RandRS) across all datasets, reducing the number of sub-problems and verification time by approximately 50% in many cases.
Maximum Verifiable Perturbation: SABRE consistently certified larger perturbation regions ( $\epsilon^*$ ) than baseline methods, particularly on ACAS Xu and MNIST-F, where it often succeeded in finding non-trivial bounds while other methods failed to certify any.

Significance and Claims
The paper claims that SABRE represents a significant step forward in relational verification by demonstrating that splitting relational neurons is a more effective strategy for refining approximations in global robustness verification than splitting individual neurons. The authors emphasize that their dual-based selection strategy provides reliable guidance for prioritizing splits, leading to improved verification efficiency and scalability.

The work highlights that while the approach remains incomplete (due to the nature of approximation), the proposed techniques maximize the degree of refinement per split, making formal verification of relational properties more practical for safety-critical cyber-physical systems. The authors modestly note that future work could explore hybrid strategies that dynamically switch between individual and relational splitting, but they assert that their current exclusive focus on relational neurons already yields superior performance on the majority of tested benchmarks.

More like this