TLDR: The research paper introduces BaB-prob, a novel Branch-and-Bound framework with preactivation splitting for probabilistic verification of neural networks. It iteratively divides problems into subproblems, using linear bounds to calculate probabilities. BaB-prob is proven sound and complete for feedforward-ReLU networks and features two splitting strategies based on ‘uncertainty level’. Experimental results show it significantly outperforms state-of-the-art methods on medium to high-dimensional input problems, enhancing the reliability assessment of neural networks.
Neural networks are at the heart of many advanced technologies, from self-driving cars to medical diagnostics. Ensuring their reliability and safety is paramount, especially when dealing with uncertain or random inputs. This is where the field of probabilistic verification comes into play: it asks whether a neural network will behave as expected with a high degree of probability under a given input distribution.
Traditional methods for verifying neural networks often fall into two categories: sampling-based and analytical. Sampling-based approaches are versatile but require a vast number of samples to achieve high confidence, which can be computationally expensive. Analytical methods, while deterministic, often struggle with scalability for deep and wide networks or make simplifying assumptions that limit their completeness.
A new research paper introduces a novel framework called BaB-prob, which stands for Branch-and-Bound with Preactivation Splitting for Probabilistic Verification of Neural Networks. This approach extends the highly effective branch-and-bound technique, previously used for deterministic verification, into the probabilistic domain. The core idea is to systematically break down a complex verification problem into smaller, more manageable subproblems. This is achieved by ‘splitting’ preactivations – the values before a non-linear activation function like ReLU – into negative and non-negative cases.
By dividing the problem in this way, BaB-prob can leverage linear bound propagation to calculate tighter probability bounds for each subproblem. This iterative process continues until the original problem can be definitively certified as true or false. A significant achievement of BaB-prob is its proven soundness and completeness for feedforward-ReLU neural networks, meaning it will correctly identify when a property holds and will always find it if it does.
The researchers also introduce the concept of an ‘uncertainty level’ for unstable preactivations, which helps quantify how much a split might improve the probability bounds. Based on this, they designed two efficient splitting strategies: BaB-prob-ordered and BaB+BaBSR-prob. BaB-prob-ordered follows a more naive, layer-by-layer approach, often splitting on preactivations with zero uncertainty. BaB+BaBSR-prob, on the other hand, combines this uncertainty level with heuristics from deterministic verification to make more informed splitting decisions, particularly beneficial for complex CNN models.
Extensive experiments were conducted on various neural network models, including untrained MLPs and CNNs, as well as models trained on MNIST and CIFAR-10 datasets, and benchmarks from VNN-COMP 2025. The results consistently demonstrate that BaB-prob, in both its ordered and BaBSR-enhanced versions, significantly outperforms existing state-of-the-art probabilistic verification approaches, especially for problems with medium to high-dimensional inputs. For instance, BaB-prob-ordered showed better scalability on MLP models, while BaB+BaBSR-prob excelled with CNN architectures, often requiring significantly fewer splits to reach a conclusion.
Also Read:
- Bridging Neural Networks and Logic: A Formal Correspondence in Fibring Architectures
- ImitSAT: Accelerating SAT Solvers with Imitation Learning and Expert Traces
This work represents a substantial step forward in the reliable and efficient probabilistic verification of neural networks, offering a robust framework that can handle the complexities of modern deep learning models. For those interested in the full technical details, the research paper can be found here.
