CS Paper Radar

Data-Driven Compositional Safety Verification of Interconnected Monotone Systems

Amirreza Alavi, Majid Zamani, Saber Jafarpour

eess.SY ·submitted 2026-09-16 20:26 UTC · v1

Abstract

This paper introduces a sample-efficient compositional method for formal safety verification of interconnected monotone systems without requiring explicit models of the local subsystems. Existing data-driven approaches either lack formal safety guarantees or rely on dense Lipschitz-based discretizations of the state space to provide such guarantees, which leads to significant computational overhead and limits scalability. In contrast, we leverage the monotonicity of local subsystems to construct tractable local interval-barrier certificates using only boundary evaluations of each subsystem in a decentralized manner, together with a global condition that guarantees the safety of the overall interconnected system. At the local level, our framework learns interval-barrier certificates using monotone neural networks from boundary samples induced by partitions of the local state and internal-input spaces. At the global level, it composes these local neural interval-barrier certificates using the interconnection structure to certify the safety of the overall system. Furthermore, under appropriate structural assumptions, we reformulate the global safety condition into a scalable form that can be directly incorporated into the neural network loss. This enables the enforcement of overall system safety during local training. The experimental results demonstrate the effectiveness and scalability of the proposed method.

Closest papers

Nearest neighbours by meaning across the whole index.

Scalable Neural Safety Certification via Monotonicity

eess.SY cs.LGmath.OC ·2026-11-08 ·Amirreza Alavi, Majid Zamani, Saber Jafarpour
similarity 0.82
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.

0.13

Training Mixed-Monotone Neural Networks for Verification Without Set Propagation

cs.LG ·2026-10-22 ·Jonas Fingerhut, Lukas Koller, Matthias Althoff
theory similarity 0.66
Abstract · 20 pages, 3 figures, 9 tables

Most formal verification approaches for neural networks conservatively enclose the output set of the neural network. However, computing a tight output enclosure is in general computationally hard. We sidestep this challenge with a novel neural network architecture that realizes mixed-monotone functions as the difference of monotone subnetworks. By utilizing the theory on mixed-monotone systems, this reduces the computation of a tight output enclosure from complicated set propagation to two simple forward passes of opposite corners of an input interval. Moreover, because the size of the resulting enclosure is a closed-form function of the weights of the neural network, we can directly minimize it during training. We prove a lower bound on the size of any such enclosure, given by the total variation of the represented function generalized to several inputs, which makes it possible to compare the tightness of the enclosure against the optimum. Our evaluation on regression and dynamical-system benchmarks demonstrates that our training reduces the enclosure size to within 0.5% of the lower bound without sacrificing prediction accuracy. Computing our enclosure is orders of magnitude faster than CROWN and $α$-CROWN and on deep networks it is also tighter than zonotope propagation and CROWN, while its size exceeds that of $α$-CROWN by only 5.1%.

0.18

Input-to-State Safety and Small-Gain Theorems for Large-Scale Nonlinear Systems

eess.SY ·2026-11-10 ·Jianqiang Wang, Tengfei Liu, Zhong-Ping Jiang
theory similarity 0.65
Abstract · 16 pages, 7 figures

This paper studies the safety verification problem for a general class of large-scale systems characterized by multiple safety indicator functions. Each safety indicator function satisfies a trajectory-based input-to-state safety (ISSf) estimate that provides a lower bound on its value along system trajectories in terms of the initial state, external inputs, and the other safety indicator functions, whose influence is quantified by continuous and nondecreasing gain functions. Within this framework, we establish a safety-oriented small-gain theorem and its corresponding corollaries that enable compositional and scalable safety verification of the interconnected system, provided that the interconnection gain functions satisfy a small-gain condition on the negative real axis. This condition concerns only the neighborhood of the safety boundary, thereby facilitating the application of our results to safety verification of multi-agent systems under distributed control. Our proof combines small-gain techniques with the lower-bound structure of ISSf estimates and develops an inductive comparison argument that establishes the ISSf property for the overall system throughout the maximal interval of existence. As an application, we establish robust safety for the natural distributed "half-spring" controller, theoretically supporting the computationally efficient and inspiring approach to safety-critical control of multi-agent systems in the presence of obstacles and external disturbances.

0.18

Fast and Sample Efficient Safety Verification via Extreme Learning Machine

eess.SY ·2026-09-30 ·Ahan Basu, Mahathi Anand, Pushpak Jagtap
similarity 0.65
Abstract

Deep learning methods like neural networks have greatly simplified the computation of safety certificates for complex nonlinear systems with unknown dynamics. However, due to the data-driven nature of these certificates and the complex architecture of neural networks, computation time as well as robustness guarantees across unseen data remain a challenge. This work aims to formally verify safety properties of discrete-time unknown systems by synthesizing extreme learning machine (ELM)-based barrier certificates. Compared to neural network counterparts, this approach greatly improves convergence guarantees and computational time due to its architectural simplicity and the convex nature of the underlying optimization problem. By minimizing the Lipschitz constant of the candidate barrier, we present a grid-based sampling technique to formally verify its validity using the minimum number of samples required. We demonstrate through numerical examples the effectiveness of our approach, and compare with traditional deep-learning based certificate synthesis to highlight its benefits.

0.18

Enumeration-Guided Training of Neural Hamilton-Jacobi Safety Certificates

cs.RO cs.LG ·2026-10-20 ·Mihaela-Larisa Clement, Tosca Pierro, Ezio Bartocci, Luca Marzari
similarity 0.62
Abstract

Hamilton-Jacobi (HJ) reachability analysis offers formal safety guarantees for control systems, but training accurate neural certificates remains difficult, particularly when unsafe regions are hard to characterize. We propose a verification-guided training framework that addresses this by using probabilistic enumeration of safety constraints to detect forward-invariance violations, i.e., states where the learned certificate incorrectly classifies unsafe behavior. This produces a compact, targeted set of counterexamples that more precisely captures the failure boundary than inputs generated by standard adversarial attack methods. Crucially, using this representation to fine-tune a pretrained HJ value function yields larger certified regions and reduces certification time across all tested benchmarks. We further introduce a shielding mechanism based on the refined certificates to enforce safety constraints at deployment time. We evaluate the proposed safety filter in a realistic, physics-based Isaac Sim environment and through real-world autonomous racing experiments, achieving zero safety constraint violations compared to a nominal controller and a backup policy based on Linear Quadratic Regulation (LQR). These results demonstrate the effectiveness of the proposed shielding mechanism in ensuring safe operation under high-speed, safety-critical conditions.

0.13

Unified Overview of Safety Certificate Functions: Techniques from Hamilton--Jacobi Reachability and Control Barrier Functions

cs.RO eess.SY ·2026-11-05 ·Hao Wang, Max Cohen, Zeyuan Feng, Donggeon David Oh, Oswin So +7 more
surveybenchmark similarity 0.61
Abstract

Safety is a central concern in modern autonomous systems. Safety certificates---functions whose existence guarantees that a system meets its safety specification---have long been used as a principled tool for rigorously reasoning about safety. Methods for synthesizing such certificates are scattered across research areas, with little guidance on when to use a particular approach. This tutorial provides a holistic treatment of safety certificate synthesis centered on two widely used families: Hamilton--Jacobi (HJ) reachability analysis and control barrier functions (CBFs). For each family of methods, we first introduce its general formulation, along with classical and learning-based tools for certificate synthesis. Next, we introduce two benchmark problems consisting of vehicle systems of differing complexity to assess the certificate quality of different synthesis methods and their effectiveness in safety-critical control. We use these benchmarks to compare various methods and provide practical guidance for selecting an approach.

0.24

Time-Invariant Control Barrier Functions for Bounded STL Safety

eess.SY ·2026-08-28 ·Avinash Malik
theory similarity 0.60
Abstract · 6 pages, 3 figures

Enforcing finite-time persistence specifications in Signal Temporal Logic typically requires formulating Control Barrier Functions within an extended state-time space. This introduces strict mathematical assumptions on global clock synchronization, rendering multi-agent execution brittle under asynchronous network delays, clock skew, and non-monotonic jitter. In this paper, we prove that for bounded-time safety tasks, explicit time dependency can be mathematically eliminated for general continuous-time nonlinear systems. By leveraging the reciprocal integral of worst-case system dissipation, we systematically compile temporal specifications into static, lower-dimensional spatial invariants. We formally prove that this time-invariant realization is strictly sound, removes the need for heuristic time-varying envelope tuning, and guarantees robust forward invariance even under severe network desynchronization.

0.18

Neural Barriers: An Online Certifiable Learning-enhanced Adaptive High Order Safety Critical Control

cs.RO ·2026-10-04 ·Lishuo Pan, Mattia Catellani, An Cao, Lorenzo Sabattini, Nora Ayanian
similarity 0.59
Abstract · 14 pages, 11 figures, 3 tables

Control barrier functions are an effective model-based tool to formally certify the safety of a system. However, transferring their theoretical guarantees to real-world robotics systems requires high model fidelity. For example, payloads or wind disturbances can cause significant model perturbations to an aerial vehicle, leading to safety compromises. In this work, we propose a certifiable online learning-enhanced robust adaptive control barrier function, which adapts to disturbances using a Neural ODE and quantifies its adaptation uncertainty with conformal prediction. Our approach guarantees safety at all time under unknown time-varying model disturbances. It adopts a conservative strategy when the adaptation uncertainty is high; and efficiently adapts to reduce controller conservativeness as it receives more data. Our approach provides a provable safety guarantee with a probability bound under suitable Lipschitz smoothness assumptions on the underlying model and trajectory. These results demonstrate the potential of our method as a practical safety controller for robotics system operating under model perturbations.

0.23