⚡ electrical engineering

Bridging Control with Neural Network Verifier alpha-beta-CROWN: A Tutorial

This tutorial introduces a unified framework that bridges control theory with the state-of-the-art neural network verifier $\alpha,\!\beta$ -CROWN to enable scalable, formal verification of safety and stability properties in learning-based controllers for safety-critical systems.

Original authors: Haoyu Li, Xiangru Zhong, Hao Cheng, Bin Hu, Huan Zhang

Published 2026-05-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Haoyu Li, Xiangru Zhong, Hao Cheng, Bin Hu, Huan Zhang

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 or a robot that learns to walk by watching videos and practicing, rather than being programmed with strict rules. This is a "learning-based" controller. It's incredibly smart and flexible, but it has a scary flaw: we don't know for sure if it will ever make a fatal mistake. We can test it a million times, but if it fails once in a billionth of a second, the result could be catastrophic.

This paper introduces a "safety inspector" for these AI brains called α,β-CROWN. Think of it not as a test driver, but as a mathematical guarantee that says, "I have checked every single possible path this robot could take, and I promise it will never crash."

Here is how the paper explains this technology using simple analogies:

1. The Problem: The "Black Box" and the "Infinite Maze"

Learning-based controllers are like black boxes. You put a situation in (e.g., "a pedestrian is crossing"), and a complex neural network (a digital brain) spits out an action (e.g., "brake").

The Challenge: To prove this brain is safe, you have to check every possible situation it might face. Since the world is continuous and the brain is complex, there are effectively infinite situations. Traditional math tools are too slow to check them all, or they only work for very simple, rigid systems.

2. The Solution: The "Smart Flashlight" (α,β-CROWN)

The authors present α,β-CROWN as a powerful tool that acts like a smart flashlight in a dark, infinite maze.

How it works: Instead of trying to walk every single path in the maze (which takes forever), the flashlight shines a beam that covers a whole section of the maze at once.
The "Bounding" Trick: It doesn't need to know the exact path the robot will take. Instead, it calculates a safe box (a boundary) that is guaranteed to contain all possible paths the robot could take in that section.
- If the "safe box" is entirely inside the "safe zone," the robot is safe in that section.
- If the "safe box" touches the "danger zone," the flashlight gets smarter. It splits that section into two smaller pieces and shines the light on them again.
The Speed: This tool is supercharged by GPUs (the same chips used for video games). It can check thousands of these "sections" simultaneously, making it fast enough to handle complex, real-world robots.

3. The Three Main Jobs of the Inspector

The paper shows that this tool can do three specific jobs for control engineers:

Job A: The "Reachability" Map (Where can we go?)
Imagine you drop a ball in a box. Where can it roll in the next second? The tool draws a tight, safe outline around all the places the ball could possibly end up. This helps engineers know if the robot might accidentally wander into a wall.
Job B: The "Stability" Check (Will it fall over?)
Think of a ball rolling in a bowl. If you push it, it wobbles but eventually settles at the bottom. This is "stability." The tool mathematically proves that no matter how hard you push the robot (within reason), it will always settle back down and never spin out of control. It does this by checking a "Lyapunov function," which is like a digital energy meter that must always go down.
Job C: The "Optimizer" (What is the best move?)
Sometimes you want the robot to find the best path, not just a safe one. The tool acts like a super-smart GPS that doesn't just guess the best route; it mathematically proves that the route it found is the absolute best one possible, without missing any hidden shortcuts.

4. How It's Built: The "Lego" Approach

The paper explains that the tool treats the robot's brain (the neural network) and the physics of the world as a giant computation graph.

Imagine the robot's decision-making process as a chain of Lego blocks. Some blocks are simple math (addition), some are "switches" (if the light is red, stop), and some are complex curves (sine waves).
α,β-CROWN knows how to put a "safety wrapper" around every single Lego block. It then connects these wrappers together to see the safety of the whole chain. If a block is too complex to wrap perfectly, it breaks that block into smaller pieces and wraps those instead.

5. Teaching the Robot to be "Verifiable"

Finally, the paper discusses how to train these robots so they are easier to inspect.

Old Way (CEGIS): You train the robot, check if it's safe, find a mistake, and tell it to try again. This is like a student guessing answers until they get them right.
New Way (Certified Training): The tool gives the robot a "hint" during training. It tells the robot, "If you move your brain weights this way, the safety wrapper gets tighter." The robot learns to shape its own brain so that the safety inspector can easily prove it's safe. The paper claims this makes the final robot 5 times faster to verify than the old way.

Summary

In short, this paper introduces a universal safety inspector for AI-controlled machines. It uses a clever method of drawing "safe boxes" around complex math problems and splitting them up until they are small enough to prove. By using powerful computer chips (GPUs), it can do this fast enough to be useful for real-world applications like self-driving cars and power grids, ensuring that these smart machines are not just empirically good, but mathematically safe.

Technical Summary: Bridging Control with Neural Network Verifier $\alpha,\beta$ -CROWN

Problem Statement

Learning-based neural network (NN) controllers have demonstrated high expressiveness and strong empirical performance in safety-critical domains such as autonomous driving, robotics, and power systems. However, empirical performance alone is insufficient for deployment in these settings. There is a critical need for formal verification of closed-loop properties, including stability (e.g., Lyapunov stability), safety (e.g., barrier functions), and reachability.

Existing verification approaches face significant limitations:

Scalability: Traditional methods like SMT solvers (e.g., dReal, Z3), Mixed-Integer Linear Programming (MILP), and convex optimization (SDP, SOS) often scale poorly, particularly for high-dimensional systems or deep networks, due to limited ability to exploit GPU acceleration and parallelism.
Structural Rigidity: Many methods are tied to specific structural assumptions, such as shallow piecewise-linear networks with ReLU activations or polynomial systems, making them difficult to transfer across different control settings or certificate classes.
Certificate Specificity: Recent control-oriented verification methods often exploit certificate-specific structures (e.g., symbolic bound propagation), which limits their direct applicability to different classes of certificates.

Methodology

The paper introduces a unified framework that bridges control theory with the state-of-the-art neural network verifier $\alpha,\beta$ -CROWN. The core methodology relies on treating control problems as verification or optimization tasks over computation graphs.

1. The $\alpha,\beta$ -CROWN Verifier

$\alpha,\beta$ -CROWN is a general-purpose bounding engine for nonlinear functions represented as computation graphs. Its operation involves:

Computation Graphs: The framework models system dynamics $f$ , controllers $\pi$ , and certificates (e.g., Lyapunov functions $V$ ) as directed acyclic graphs (DAGs) composed of elementary operations (affine maps, nonlinearities like ReLU, sin, multiplication, etc.).
Automatic Linear Relaxation (auto LiRPA): The verifier propagates sound linear over-approximations (bounds) backward through the computation graph. For any input domain $B$ , it computes an affine lower bound $F(x) \geq a^\top x + b$ . This process is fully differentiable and highly vectorized, allowing for efficient execution on GPUs.
Branch-and-Bound (BaB): To handle cases where linear bounds are inconclusive, the framework employs input domain branch-and-bound. It recursively partitions the input domain into subdomains. As domains shrink, local linear relaxations tighten, and the over-approximation error decreases.
Jacobian Handling: For continuous-time systems requiring gradient bounds (e.g., $\nabla V \cdot f$ ), the framework extends the computation graph to explicitly encode gradient computation via the chain rule, treating Jacobian computation as another operator.

2. Reformulating Control Problems

The tutorial demonstrates how to reformulate classical control-theoretic problems into $\alpha,\beta$ -CROWN-friendly satisfiability or optimization problems over box domains:

Reachability Analysis: Computing sound over-approximations of reachable sets by bounding the output of the closed-loop map $g(x)$ over an input box.
Stability Verification (Lyapunov): Converting the requirement that a Lyapunov function decreases along trajectories into a satisfiability problem. For discrete-time systems, this involves verifying conditions like $(V(g(x)) - (1-\kappa)V(x) \leq 0)$ over a sublevel set, reformulated as logical implications over a surrounding box. Similar reformulations are provided for continuous-time systems, including handling forward invariance at box boundaries.
Safety Verification (Barrier Functions): Verifying that a safe set is forward invariant by checking conditions on the derivative of a barrier function. For control-affine systems, the supremum over control inputs is converted to a maximum over polytope vertices.
Contraction Analysis: Reformulating matrix-based contraction conditions into scalar satisfiability problems involving Riemannian metrics.
Optimization (MPC): Using the verifier as a global optimizer for Model Predictive Control (MPC) by minimizing cost functions subject to nonlinear dynamics and constraints, guided by certified lower bounds.

3. Training and Synthesis

The paper discusses frameworks for co-synthesizing controllers and certificates:

Counterexample-Guided Inductive Synthesis (CEGIS): An iterative approach where counterexamples found during verification are used as training data.
Certified Training: A paradigm that incorporates the differentiable lower bounds generated by $\alpha,\beta$ -CROWN directly into the training loss function. This allows for gradient-based optimization to maximize the certified lower bound of a specification, yielding models that are inherently "verification-friendly."

Key Contributions

Unified Framework: The paper presents a unified approach to apply $\alpha,\beta$ -CROWN to diverse control tasks, including reachability, stability, safety, and optimization.
Scalability via GPU Parallelization: By leveraging the efficient, parallelizable nature of bound propagation and branch-and-bound on GPUs, the framework achieves superior scalability compared to traditional SMT or MILP-based approaches, particularly for high-dimensional and complex nonlinear systems.
General-Purpose Applicability: Unlike methods restricted to specific network architectures or certificate types, $\alpha,\beta$ -CROWN handles general nonlinear functions represented as computation graphs, supporting a wide range of operators (trigonometric, piecewise-linear, etc.).
Differentiability: The linear bound propagation is fully differentiable, enabling the integration of verification constraints directly into the training loop (certified training).
Practical Implementation: The tutorial provides a detailed programming interface (API) and code examples demonstrating how to define computation graphs, formulate constraints using a Domain-Specific Language (DSL), and execute verification, bound computation, and optimization tasks. It also offers a drop-in compatibility layer for the dReal API.

Results and Claims

The paper claims that the proposed pipeline demonstrates superior scalability on verification and optimization problems that are challenging for traditional approaches.

Efficiency: The ability to process tens of thousands of subdomains simultaneously on a GPU allows for rapid pruning of large regions and certification with coarse bounds on tiny domains.
Versatility: The framework successfully handles various control specifications, including Lyapunov stability, barrier function safety, and contraction metrics, by reformulating them as satisfiability problems over box domains.
Training Benefits: The paper notes that in a 2D quadrotor environment, models trained with the certified training approach were 5 times faster to verify compared to those trained using CEGIS, suggesting that the training objective directly improves verifiability.

Significance

The significance of this work lies in its attempt to bridge the gap between control theory and scalable neural network verification. By providing a unified, efficient, and general-purpose framework, the authors aim to make formal certification a more practical and integral component of learning-based control design. The tutorial serves to lower the barrier to entry for applying rigorous verification techniques to complex, learned control policies, moving beyond empirical testing to provide formal guarantees for safety-critical systems.