eess.SYNov 8, 2026

Scalable Neural Safety Certification via Monotonicity

Authors: Amirreza Alavi, Majid Zamani, Saber Jafarpour

Organizations: University of Colorado Boulder, Boulder, CO, USA

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)O(n) simulator queries. Across high-dimensional benchmarks, including oscillator networks with up to 13,65913{,}659 states and traffic networks with 1,0001{,}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.

Figures & tables

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Set-Based Training of Neural Barrier Certificates for Safety Verification of Dynamical Systems

    May 4, 2026Miriam Kranzlmüller, Lukas Koller, Tobias Ladner +1Neural Network VerificationSafety-Critical Control

  2. Training Mixed-Monotone Neural Networks for Verification Without Set Propagation

    Oct 22, 2026Jonas Fingerhut, Lukas Koller, Matthias AlthoffNeural Network VerificationNeural Network Optimization

  3. k-Inductive Neural Barrier Certificates for Unknown Nonlinear Dynamics

    May 19, 2026Ben Wooding, Hongchao Zhang, Taylor T. Johnson +1Control Barrier FunctionsFormal Verification