# Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound

Source: [Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound](<https://www.sota2.com/research/paper/68fa6c7a1e209131cea342fe>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T00:11:46.889Z

Authors: Claudio Ferrari, Mark Niklas Muller, Nikola Jovanovic, Martin Vechev

Published: 2022-04-30T13:12:33.000Z

## Abstract

State-of-the-art neural network verifiers are fundamentally based on one of two paradigms: either encoding the whole verification problem via tight multi-neuron convex relaxations or applying a Branch-and-Bound (BaB) procedure leveraging imprecise but fast bounding methods on a large number of easier subproblems. The former can capture complex multi-neuron dependencies but sacrifices completeness due to the inherent limitations of convex relaxations. The latter enables complete verification but becomes increasingly ineffective on larger and more challenging networks. In this work, we present a novel complete verifier which combines the strengths of both paradigms: it leverages multi-neuron relaxations to drastically reduce the number of subproblems generated during the BaB process and an efficient GPU-based dual optimizer to solve the remaining ones. An extensive evaluation demonstrates that our verifier achieves a new state-of-the-art on both established benchmarks as well as networks with significantly higher accuracy than previously considered. The latter result (up to 28% certification gains) indicates meaningful progress towards creating verifiers that can handle practically relevant networks.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Neural Network Verification on oval VNN-COMP 2022](<https://www.sota2.com/research/sota/neural-network-verification-on-oval-vnn-comp-2022.md>): Neural Network Verification; oval VNN-COMP 2022; Verification Time (s): 137.13.

- [Neural Network Verification on cifar100-tinyimagenet VNN-COMP 2022](<https://www.sota2.com/research/sota/neural-network-verification-on-cifar100-tinyimagenet-vnn-comp-2022.md>): Neural Network Verification; cifar100-tinyimagenet VNN-COMP 2022; Verification Time (s): 40.27.

- [Robustness Verification on CIFAR (test)](<https://www.sota2.com/research/sota/robustness-verification-on-cifar-test.md>): Robustness Verification; CIFAR (test); Verification Rate: 42.5.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2205.00263>)

[PDF](<https://arxiv.org/pdf/2205.00263.pdf>)