Monotonicity enables scalable neural safety checks for complex systems

Scalable Neural Safety Certification via Monotonicity

Machine Learning

Summary

Verifying safety of complex systems can be very hard, especially when the system's exact rules are unknown. The authors show that when a system behaves in a way called "monotonicity," safety checks become much simpler and faster. They build a special kind of neural network to find safety certificates using fewer simulations. Their method works well even on very large systems, like traffic or oscillator networks, where older methods struggle or fail.

What this means in practice

Authors

Amirreza Alavi, Majid Zamani, Saber Jafarpour

Abstract

Learning-based safety certification offers a promising route for verifying complex dynamical systems when explicit models are unavailable, but existing data-driven methods often scale poorly: they treat the system as a black box, rely on dense discretizations or Lipschitz bounds, and consequently suffer from sample complexity that grows exponentially with dimension. This paper shows that a common structural property of dynamical systems--monotonicity--can be used to break this curse of dimensionality. We develop a data-driven framework for robust safety verification and safe controller synthesis for unknown monotone systems using only simulator queries. Our main theoretical result proves that, for monotone systems with upper-closed unsafe sets, safety is completely characterized by the existence of monotone inductive barrier certificates. This structure reduces certificate verification over continuous state spaces to localized boundary checks over finitely many cells. To learn such certificates, we introduce Max-Monotone Networks, a monotone neural architecture with universal approximation guarantees for monotone functions. We then propose a training and refinement algorithm that, upon successful termination, returns formally valid neural barrier certificates and, under mild partition assumptions, requires only $O(n)$ simulator queries. Across high-dimensional benchmarks, including oscillator networks with up to $13{,}659$ states and traffic networks with $1{,}000$ states, our method certifies safety in regimes where prior approaches either do not converge or exceed memory limits. These results demonstrate that exploiting order structure can make neural safety certification both scalable and formally sound.