LTL Verification of Memoryful Neural Agents
Mehran Hosseini, Alessio Lomuscio, Nicola Paoletti · 2025
Read LTL Verification of Memoryful Neural Agents by Mehran Hosseini, Alessio Lomuscio, Nicola Paoletti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-02512.txt.
Introduction
Mehran Hosseini, Alessio Lomuscio, and Nicola Paoletti check memory-holding neural agent teams against timed rules, in a paper from two thousand twenty-five. The agents act in foggy, chance worlds, from plain nets to state-space builds. Past tools could not touch open-ended timed rules.
Bounded search tricks, loop hunting and fixed-point building, turn checks into constraint sums. Fast solvers use bound spread, integer math, and smart splits. On gym and zoo worlds, open rules were checked for the first time. Bounded checks ran about ten times faster than the best past tools. Readers get proof tools that keep pace with learning agents.
Catalog record
| CREATOR | Mehran Hosseini, Alessio Lomuscio, Nicola Paoletti |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-02512
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
LTL Verification of Memoryful Neural Agents Mehran Hosseini, Alessio Lomuscio, Nicola Paoletti Abstract . We present a framework for verifying Memoryful Neural Multi-Agent Systems (MN-MAS) against full Linear Temporal Logic (LTL) specifications. In MN-MAS, agents interact with a non-deterministic, partially observable environment. Examples of MN-MAS include multi-agent systems based on feed-forward and recurrent neural networks or state-space models. Different from previous approaches, we support the verification of both bounded and unbounded LTL specifications. We leverage well-established bounded model checking techniques, including lasso search and invariant synthesis, to reduce the verification problem to that of constraint solving. To solve these constraints, we develop efficient methods based on bound propagation, mixed-integer linear programming, and adaptive splitting. We evaluate the effectiveness of our algorithms in single and multi-agent environments from the Gymnasium and PettingZoo libraries, verifying unbounded specifications for the first time and improving the verification time for bounded specifications by an order of magnitude compared to the SoA. Y. Vorobeychik, S. Das, A. Nowé (eds.) Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA <<977>> 1. Introduction With the rise of machine learning, we are increasingly witnessing applications of neural networks (NNs) to autonomous systems. While neural agents may solve significantly more complex tasks than traditionally programmed counterparts ( Silver et al., 2017 ; Vinyals et al., 2019 ) , NNs suffer from fragilities ( Szegedy et al., 2014 ) , which is a concern in safety-critical applications. Thus, they require rigorous guarantees, as those offered by formal verification. In this paper, we develop the methodology for verifying systems comprising multiple memoryful neural agents that interact with an uncertain environment over time in a closed loop. We refer to such systems as Memoryful Neural Multi-Agent System ( MN-MAS ). The verification of MN-MAS is more challenging than the verification of individual predictions made by NNs, due to the presence of multiple networks, multiple time steps, and temporal dependencies between predictions. Several methods for the verification of systems with NNs “in the loop” have been recently proposed ( Hosseini and Lomuscio, 2023 ; Fan et al., 2020 ) . Nevertheless, these are limited by at least two of the following: they only consider single-agent systems; are limited to the analysis of (time-)bounded reachability; do not account for uncertainty in the environment; or the agents are implemented by feedforward models, thus are stateless/memoryless. We propose a verification approach for MN-MAS that addresses all the above limitations. The approach presented here supports verification of MN-MAS against full linear temporal logic ( Pnueli, 1977 ) . Thus, the method presented here goes beyond simple bounded reachability analysis and, unlike existing methods, can verify both bounded and unbounded specification, as well as nested properties. These include (unbounded) safety (e.g., will an agent always remain in a safe state region? ) or stability (e.g., will an agent reach its target and remain there long enough thereafter? ). Although we show that the verification of unbounded specifications is undecidable in general, we develop sound or complete procedures based on Bounded Model Checking (BMC) ( Biere et al., 2009 ) , which allows us to verify unbounded properties of the MN-MAS using finite paths. In particular, we develop three BMC procedures, based on, respectively, simple path unrolling, lasso search, and inductive invariants. Thus, when the presented method establishes that an MN-MAS S satisfies an LTL specification \phi , written S\models\phi , then \phi must hold for all the paths of the system induced by the uncertain (non-deterministic) environment dynamics and initial states. With BMC, we reduce the verification problem to solving a set of logical constraints over the MN-MAS states. In particular, we target linearly definable systems, i.e., systems that can be formulated by a finite set of piecewise-linear (PWL) constraints. This class of systems remains quite expressive, as it includes, among others, neural agents with ReLU-based activations. We introduce two efficient algorithms to solve the resulting PWL constraints. The first is Bound Propagation through Time (BPT) , an extension of interval and linear bound propagation ( Gowal et al., 2018 ; Wang et al., 2018 ) to support memoryful models, such as those based on Recurrent Neural Networks ( RNNs ). BPT is highly efficient but results in an over-approximation of the model’s outputs, meaning that it cannot be used in all verification instances (see Section 3.2 ). The second is a Mixed-Integer Linear Programming ( MILP )-based algorithm, called Recursive MILP ( RMILP ), which allows encoding the constraints and variables during multiple time steps in MILP. Unlike BPT, the latter is precise (i.e., does not overapproximate) and is more efficient than past MILP approaches for recurrent models ( Hosseini and Lomuscio, 2023 ; Akintunde et al., 2019 ) (see Section 5.3 ). We also employ adaptive splitting ( Kouvaros and Lomuscio, 2021 ) , which exploits the information about the reachable sets computed by BPT to resolve a priori some of the discrete variables of the MILP instances, thereby considerably simplifying the MILP encoding. In summary, we make the following contributions: (1) we introduce the first framework for verifying memoryful, neural multi-agent systems against full LTL specifications under uncertainty; (2) we characterize the decidability of the verification problem; (3) we develop efficient solutions based on bounded model checking, bound propagation, and constraint solving; and (4) we evaluate the approach on deep Reinforcement Learning (RL) benchmarks with single and multiple agents, demonstrating its efficiency compared to the SoA (being strictly faster in all instances, up to one order of magnitude) and its versatility in verifying, for the first time, both time-bounded and unbounded specifications. Related Work. Following several seminal works exposing the vulnerability of machine learning models to adversarial perturbations ( Szegedy et al., 2014 ; Biggio and Roli, 2018 ) , significant attention has been paid to the verification of neural networks against input-output relations. A special class of these consists of the verification of local robustness including output reachability. Most solution techniques are based on (a combination of) bound propagation ( Gowal et al., 2018 ; Wang et al., 2018 ) and constraint solving ( Ehlers, 2017 ; Lomuscio and Maganti, 2017 ; Tjeng et al., 2019 ; Katz et al., 2019 ; Botoeva et al., 2020 ) . While this line of research focuses on open-loop systems, we here consider closed-loop systems with NN components, i.e., sequential processes characterised by multiple interdependent NN predictions over time. In recent years, several methods have been proposed to verify this kind of systems ( Hosseini and Lomuscio, 2023 ; Akintunde et al., 2020a ; Akintunde et al., 2020b ; Tran et al., 2020 ; Sidrane et al., 2022 ; Fan et al., 2020 ; Bacci and Parker, 2020 ; Ivanov et al., 2021 ; Wicker et al., 2021 ; Wicker et al., 2024 ; Giacomarra et al., 2025 ) . Among the above, the work of Akintunde et al. (2020b) focuses on temporal logic verification of multi-agent systems but considers a bounded fragment of the logic and agents implemented via feedforward NNs (FFNN), i.e., memoryless models. Closer to this contribution is the method of Akintunde et al. (2019) , which supports RNN-based agents but