Branch and Bound Verification

Branch and Bound Verification is the core algorithmic paradigm for exact neural network verification — systematically partitioning the input space (branching) and computing bounds on each subregion (bounding) to either prove or disprove a property.

How Branch and Bound Works

• Bounding: Use relaxation methods (LP, IBP, CROWN) to compute output bounds for a given input region.
• Decision: If bounds prove the property → verified. If bounds show a violation → counterexample found.
• Branching: If bounds are inconclusive, split the input region (or split a ReLU activation state) into sub-problems.
• Pruning: Sub-problems that are provably safe (from bounding) are pruned — no further branching needed.

Why It Matters

• Complete: Branch and bound is complete — given enough time, it will always find the answer.
• Efficient Pruning: Smart branching heuristics and tight bounds dramatically reduce the search space.
• α,β-CROWN: State-of-the-art tools (winners of VNN-COMP) combine GPU-accelerated bound propagation with branch-and-bound.

Branch and Bound is divide and conquer for verification — recursively splitting the problem until every subregion is proven safe or a counterexample is found.