POLAR-Express: Efficient and Precise Formal Reachability Analysis of Neural-Network Controlled Systems

Yixuan Wang, Weichao Zhou, Jiameng Fan, Zhilu Wang, Jiajun Li, Xin Chen, Chao Huang, Wenchao Li, Qi Zhu

TL;DR

POLAR-Express is a state-of-the-art formal verification tool designed to guarantee the safety of systems controlled by neural networks. By combining Taylor model arithmetic with a novel Bernstein polynomial approach for ReLU activations and symbolic remainder tracking, it achieves significantly tighter reachability bounds and faster execution times than existing tools across a wide range of benchmarks.

What Problem Does This Paper Address?

Neural networks (NNs) are increasingly used as controllers in autonomous vehicles, robotics, and aerospace. However, their non-linear, "black-box" nature makes it difficult to prove they will always behave safely.

Reachability analysis is the formal method used to solve this. It asks: "Given a set of possible starting positions, can the system ever enter an 'unsafe' state (like a collision) within a certain timeframe?" The challenge is that both the neural network and the physical system (the "plant") are non-linear. When you loop them together, errors in approximating their behavior tend to grow exponentially (the "wrapping effect"), leading to "loose" results that are too vague to prove safety. Existing tools often struggle with either precision (the bounds are too wide) or scalability (they are too slow for complex systems).

Methods

POLAR-Express builds on the earlier POLAR prototype but introduces several key technical innovations:

  • Taylor Model (TM) Propagation: It represents sets of states as Taylor models—a combination of a polynomial and an error interval. It propagates these models through the neural network layer-by-layer.
  • Bernstein Over-approximation for ReLU: Standard Taylor models struggle with ReLUs because they are non-differentiable at zero. The authors exploit the fact that ReLUs are convex. They use Bernstein polynomials to create a tighter "sandwich" around the ReLU function, significantly reducing approximation error compared to standard methods.
  • Symbolic Remainders (SR): To combat the wrapping effect, the tool keeps track of linear transformations symbolically as long as possible. Instead of immediately collapsing errors into a simple interval at each layer, it maintains the dependency information, only performing the final interval evaluation at the end of the process.
  • Parallel Computation: The tool implements multi-threading for the layer-by-layer propagation, allowing it to scale much better to large neural networks and high-dimensional systems.

Datasets

The authors evaluated POLAR-Express against six other state-of-the-art tools (including NNV, Verisig 2.0, and CORA) using a diverse suite of benchmarks:

  • Standard Benchmarks (1-6): Common NNCS verification tasks with various activation functions (tanh, sigmoid, ReLU).
  • Discrete Mountain Car: A classic 2D control problem.
  • Adaptive Cruise Control (ACC): Modeling vehicle-following behavior.
  • 2D Spacecraft Docking: A 5-variable system requiring precise speed limits.
  • Attitude Control & Quadrotor-MPC: Complex drone dynamics.
  • QUAD20: A high-dimensional (12-state) system that serves as a stress test for scalability.

Key Insights and Ideas

  • The "Accuracy Preservation" Problem: The authors highlight that a smaller approximation error at one layer doesn't always lead to a smaller error after the next layer. This insight led them to develop a selection method that chooses between Taylor and Bernstein approximations based on which preserves accuracy better through the entire composition.
  • ReLU Convexity is a Cheat Code: By treating ReLU as a convex optimization problem rather than just a non-linear function, they can move the approximating polynomial "down" by a calculated distance to create a perfectly tight lower bound, effectively "halving" the error interval.
  • Efficiency vs. Threads: While multi-threading is essential for high-dimensional systems (like the 12-D QUAD20), the authors noted that for very simple, low-dimensional systems, the overhead of managing threads can actually make the tool slower than a single-threaded version.

Key Results

  • Superior Tightness: In almost all benchmarks, POLAR-Express produced the tightest "flowpipes" (the set of reachable states), often succeeding where other tools produced bounds so large they were useless (marked as "Unknown").
  • Speedups: On the ReLU-based Benchmark 5, POLAR-Express was ~4x faster than the original POLAR tool while providing tighter bounds.
  • Scalability: POLAR-Express was the only tool able to efficiently verify the 12-dimensional QUAD20 system. Other tools either timed out, crashed, or failed due to "soundness issues" (where the tool's estimated safe set didn't actually cover the real simulation traces).

Limitations and Future Work

  • High-Dimensional Complexity: While it handles 12 dimensions well, the authors admit that as state dimensions increase further, the polynomial expressions in the Taylor Models become "tedious" and computationally expensive.
  • Control Step Sensitivity: Large control time-steps or very long time horizons still pose a challenge for tracking state dependencies accurately.
  • Future Directions: The authors plan to focus on further improving scalability for even higher-dimensional systems and exploring more efficient ways to handle the "tedious" polynomial expansions.

Summary updated

Abstract

Neural networks (NNs) playing the role of controllers have demonstrated impressive empirical performance on challenging control problems. However, the potential adoption of NN controllers in real-life applications has been significantly impeded by the growing concerns over the safety of these NN-controlled systems (NNCSs). In this work, we present POLAR-Express, an efficient and precise formal reachability analysis tool for verifying the safety of NNCSs. POLAR-Express uses Taylor model (TM) arithmetic to propagate TMs layer-by-layer across an NN to compute an overapproximation of the NN. It can be applied to analyze any feedforward NNs with continuous activation functions, such as ReLU, Sigmoid, and Tanh activation functions that cover the common benchmarks for NNCS reachability analysis. Compared with its earlier prototype POLAR, we develop a novel approach in POLAR-Express to propagate TMs more efficiently and precisely across ReLU activation functions, and provide parallel computation support for TM propagation, thus significantly improving the efficiency and scalability. Across the comparison with six other state-of-the-art tools on a diverse set of common benchmarks, POLAR-Express achieves the best verification efficiency and tightness in the reachable set analysis. POLAR-Express is publicly available at https://github.com/ChaoHuang2018/POLAR_Tool .
BibTeX
@article{wang2024polar,
  author = {Yixuan Wang and Weichao Zhou and Jiameng Fan and Zhilu Wang and Jiajun Li and Xin Chen and Chao Huang and Wenchao Li and Qi Zhu},
  title = {{POLAR-Express: Efficient and Precise Formal Reachability Analysis of Neural-Network Controlled Systems}},
  journal = {IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.},
  year = {2024},
  url = {https://openreview.net/forum?id=a6iwonvUKd},
}

Loading related content...

Figure