⚡ electrical engineering

Scalable Verification of Neural Control Barrier Functions Using Linear Bound Propagation

This paper presents a scalable framework for verifying neural control barrier functions by extending linear bound propagation to compute gradient bounds and combining them with McCormick relaxation to derive linear approximations of CBF conditions, thereby enabling the verification of larger networks through an adaptive, parallelizable refinement strategy.

Original authors: Nikolaus Vertovec, Frederik Baymler Mathiesen, Thom Badings, Luca Laurenti, Alessandro Abate

Published 2026-04-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nikolaus Vertovec, Frederik Baymler Mathiesen, Thom Badings, Luca Laurenti, Alessandro Abate

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 building a self-driving car. You've trained a super-smart AI (a neural network) to drive it, teaching it to stay in its lane and avoid crashing into trees. This AI is like a brilliant but unpredictable apprentice. It knows how to drive, but how do you prove to the police (or the safety regulators) that it will never crash, no matter what weird situation it encounters?

In the world of robotics, this "proof" is called a Control Barrier Function (CBF). Think of a CBF as an invisible, magical forcefield surrounding the car. As long as the car stays inside this forcefield, it is safe. If the AI can prove that its driving decisions will always keep the car inside this forcefield, the car is certified as safe.

The Problem: The "Math Wall"

The problem is that modern AI is complex. It's not a simple rulebook; it's a massive web of calculations. To prove the AI is safe, you have to check every single possible road condition, speed, and turn.

Traditionally, mathematicians used a method called SMT Solving (think of it as a super-literal, extremely slow detective) to check these rules.

The Detective's Flaw: This detective is incredibly thorough but painfully slow. If you give it a small, simple car, it can solve the case in minutes. But if you give it a complex, high-performance racing car with a massive AI brain, the detective gets overwhelmed. It might take years to check just one scenario. This limits us to using only small, simple AI models, which aren't very good drivers.

The Solution: The "Map and Compass" Approach

The authors of this paper propose a new, faster way to verify safety. Instead of asking the detective to check every single detail of the road, they use a technique called Linear Bound Propagation (LBP) combined with McCormick Relaxation.

Here is the analogy:

1. The "Box" Strategy (Linear Bounds)
Imagine you need to know if a wiggly, squiggly snake (the AI's complex behavior) will ever touch a wall.

The Old Way: You try to trace the exact path of every single scale of the snake. It takes forever.
The New Way: You put the snake inside a series of cardboard boxes. You know for a fact that if the box doesn't hit the wall, the snake inside it definitely won't hit the wall either.
- The authors developed a way to draw these "boxes" around the AI's decisions very quickly. They don't trace the exact curve; they just calculate the highest and lowest points the AI could possibly reach in a specific area.

2. The "Slicing" Strategy (Refinement)
Sometimes, a big box is too loose. The box might be huge, and even though the box doesn't hit the wall, the snake inside might wiggle close enough to be dangerous. The box is too "conservative."

The Fix: The authors use a Simiplicial Mesh. Imagine cutting a pizza into triangular slices. If a big slice of the pizza is too vague, you just cut that specific slice in half.
They do this automatically. If the "box" isn't tight enough to prove safety, they slice that area into smaller pieces and check those again. They do this in parallel (like a team of people checking different slices at the same time), making it incredibly fast.

3. The "Gradient" Trick
To make these boxes accurate, the authors had to invent a new way to track not just where the AI is, but how fast it's changing direction (the gradient).

Think of it like driving. Knowing you are at a specific GPS coordinate isn't enough; you need to know if you are accelerating, braking, or turning sharply.
The authors extended their "box" method to wrap around these changes in direction too, ensuring the safety forcefield holds up even when the car is swerving.

Why This Matters

Speed: Their method is like switching from a slow detective to a high-speed drone swarm. They can check much larger, smarter AI models in minutes that used to take days or years.
Flexibility: It works with all kinds of AI "brains," not just the simple ones. This means we can use more powerful AI for complex tasks (like flying drones in a storm or driving on icy roads) without losing safety.
Real-World Impact: This paves the way for safer, more capable autonomous vehicles and robots. It allows engineers to build bigger, smarter safety nets without hitting a "math wall."

In a Nutshell

The paper is about building a fast, adaptive safety net for AI robots. Instead of trying to calculate every single detail of the robot's future (which is impossible), they create tight, adjustable boxes around the robot's possible actions. If the boxes are safe, the robot is safe. By cutting these boxes into smaller pieces only where necessary, they verify safety quickly and reliably, allowing us to trust much smarter robots in the real world.

1. Problem Statement

The paper addresses the critical challenge of safety verification for autonomous control systems modeled as nonlinear dynamical systems. Specifically, it focuses on verifying Neural Control Barrier Functions (NCBFs).

Context: Control Barrier Functions (CBFs) are mathematical tools used to ensure a system remains within a "safe set" (forward invariance). While Neural Networks (NNs) offer a flexible way to learn complex CBFs for high-dimensional and non-polynomial systems, verifying that a trained NN actually satisfies the rigorous mathematical conditions of a CBF is computationally expensive.
The Bottleneck: Existing verification methods rely on Satisfiability Modulo Theories (SMT) solvers or Mixed-Integer Programming (MIP). These approaches struggle with scalability, often failing to verify networks larger than a few layers or systems with high state dimensions. Furthermore, many existing scalable methods are restricted to ReLU activation functions, limiting the expressiveness of the learned barrier functions.
Goal: The authors aim to develop a verification framework that is scalable (handling larger networks), general (supporting arbitrary nonlinear activation functions like tanh), and efficient (avoiding the computational overhead of SMT solvers).

2. Methodology

The proposed framework replaces exact nonlinear reasoning with linear over- and under-approximations of the CBF conditions. The core methodology consists of three main components:

A. Linear Bound Propagation (LBP) for Gradients

Standard LBP (Zhang et al., 2018) computes linear bounds on the output of a neural network ( $B_\theta(x)$ ). The authors extend this to compute linear bounds on the gradients (Jacobian) of the network ( $\nabla B_\theta(x)$ ), which are required for the Lie derivative condition in CBFs.

Challenge: The gradient involves the product of Jacobians across layers, creating bilinear terms that standard LBP cannot handle directly.
Solution: The authors derive recursive linear bounds on the Jacobian product by:
1. Expressing the gradient via the chain rule.
2. Applying McCormick relaxations to the bilinear terms arising from the product of layer Jacobians.
3. Using the pre-activation bounds from the forward pass to tighten these relaxations.
Result: This yields linear upper and lower bounds of the form $\Pi x + \pi \leq \nabla B_\theta(x) \leq \Pi x + \pi$ , computable efficiently via batched GPU operations.

B. Certified Dynamics Approximation

To verify the CBF condition $\nabla B_\theta(x) f(x) + \sup_{u} [\nabla B_\theta(x) g(x) u] + \alpha(B_\theta(x)) \geq 0$ , the system dynamics $f(x)$ and $g(x)$ must also be bounded.

The authors use first-order Taylor expansions with certified remainder bounds (Lagrange error bounds) over convex domains.
This converts the nonlinear dynamics into linear bounds ( $A_f x + b_f \pm r_f$ ), allowing the entire CBF inequality to be expressed as a linear function of the state $x$ .

C. Linear Surrogate and Refinement Strategy

The authors construct a linear surrogate formula ( $\phi_{linear}$ ) that approximates the original nonlinear CBF verification condition.

Surrogate Logic: If the linear surrogate is satisfied, the original nonlinear condition is guaranteed to be satisfied.
Handling Conservatism: Linear bounds are often too loose over large domains. To address this, the authors introduce a parallelizable refinement strategy:
- Instead of splitting the state space into hyperrectangles (which can be inefficient for coupled nonlinear constraints), they partition the domain into a simplicial mesh (simplexes).
- They recursively split the simplex along its longest edge if the verification is inconclusive.
- This adaptive refinement reduces conservatism while maintaining computational efficiency through GPU batching.

3. Key Contributions

Novel Verification Framework: Introduction of a method to verify neural CBFs using Linear Bound Propagation (LBP) combined with McCormick relaxation, eliminating the need for SMT solvers.
Gradient Bounding Extension: A significant theoretical extension of LBP to compute certified linear bounds on the gradients of neural networks with arbitrary nonlinear activation functions (e.g., tanh, sigmoid), not just ReLU.
Adaptive Simplicial Refinement: Development of a parallelizable refinement strategy using simplicial meshes to reduce the conservatism of linear bounds, specifically tailored for the coupled nature of CBF invariance conditions.
Scalability: Demonstration that the approach can verify significantly larger neural networks and higher-dimensional systems than state-of-the-art SMT-based tools.

4. Experimental Results

The authors evaluated their method on standard benchmarks (Darboux, Barrier 2-4) and new benchmarks involving control inputs (2D-Control, Cart-Pole).

Performance: The proposed method achieved 100% certification on all tested benchmarks.
Scalability:
- It successfully verified networks with up to 3 million regions (in the Cart-Pole benchmark) and large architectures (e.g., [128, 256, 128]).
- In contrast, the SMT-based solver dReal timed out on several benchmarks (e.g., Barrier 4, Darboux) or required significantly longer computation times (e.g., 1820s vs. 5.83s for Barrier 3).
Efficiency: The use of GPU batching allowed for the simultaneous processing of multiple simplices, making the verification of large networks feasible within minutes rather than hours or days.
Activation Functions: The method successfully handled tanh activations, which are preferred for maximizing control invariant sets but are difficult for ReLU-specific verification tools.

5. Significance

This work represents a major step forward in the formal safety certification of learning-based control systems.

Bridging the Gap: It bridges the gap between the expressiveness of deep neural networks and the rigorous requirements of safety-critical control.
Practical Deployment: By enabling the verification of larger, more expressive networks, it allows engineers to deploy neural CBFs in complex, real-world scenarios (like robotics and autonomous vehicles) where polynomial or small-network approximations fail.
General Applicability: The framework is agnostic to the training method and supports arbitrary activation functions and control-affine systems, making it a versatile tool for the broader community of safety-critical AI.

In summary, the paper provides a computationally efficient, scalable, and mathematically rigorous alternative to SMT-based verification, unlocking the potential of neural networks for safety-critical control applications.