Abstract
As autonomous systems increasingly rely on machine learning, formal safety verification becomes a critical challenge. While methods exist for stateless Feed-Forward Neural Networks (FFNNs), real-world agents often use stateful Recurrent Neural Networks (RNNs) to maintain memory of past interactions. This paper introduces a framework for verifying RNN-based agents by "unrolling" them into equivalent FFNNs over bounded time horizons. By encoding the agent, environment, and safety properties into Mixed Integer Linear Programming (MILP) problems, the authors provide a sound and complete verification procedure. Experimental results on a pendulum control task show that a novel "Input on Demand" unrolling technique significantly improves scalability and performance.
Introduction
The transition from human-coded logic to machine-learning models in autonomous systems, such as self-driving cars or underwater drones, complicates traditional safety certification. While verification of Feed-Forward Neural Networks (FFNNs) has seen significant progress, these models are stateless. In contrast, Recurrent Neural Networks (RNNs) are stateful; their behavior depends on the entire history of inputs, making the verification of closed-loop systems—where agent actions influence future environmental states—exceptionally difficult. This research addresses the lack of formal tools for checking safety properties in RNN-based agent-environment systems (RNN-AES) over sequential interactions.
Methodology: RNN Unrolling and MILP Encoding
The proposed verification approach, implemented in the tool RNSVERIFY, relies on three pillars: system modeling, network unrolling, and MILP translation.
System Modeling
The authors define an RNN-AES where a stateful environment with linear transitions interacts with a ReLU-based RNN agent. Safety properties are expressed using a bounded version of Linear Temporal Logic (LTL).
RNN Unrolling Techniques
To handle recurrence, the authors prove that an RNN executing for $n$ steps can be mathematically represented as a larger FFNN. They propose two unrolling techniques:
- Input on Start (IOS): All inputs are scaled by weights at the beginning of the process.
- Input on Demand (IOD): Inputs are passed to hidden units only as needed at each specific time step.
MILP Encoding
The unrolled network, environment dynamics, and safety properties are translated into a Mixed Integer Linear Programming (MILP) problem. A solver then searches for a "counter-example"—a sequence of events leading to a safety violation. If no such sequence exists, the system is formally proven safe for the given time horizon.
Experimental Evaluation
The framework was evaluated using the OpenAI Gym "Pendulum-v0" benchmark. A ReLU-RNN with 16 hidden units was trained via Q-learning to maintain a pendulum's vertical position. The environment's physics were linearly approximated to fit the MILP framework. The verification task checked whether the pendulum would remain within a specific angle ($\epsilon$) from the vertical over $n$ steps.
Key Insights and Results
The core theoretical contribution is the proof of behavioral equivalence between the unrolled FFNNs and the original RNN for bounded traces. This allows the application of existing high-performance FFNN verification tools to the RNN domain.
Scalability and Efficiency
A major finding is the superiority of the Input on Demand (IOD) method. By passing inputs only when necessary, IOD generates significantly fewer variables and constraints than IOS, leading to massive speedups as the time horizon increases.
As shown in the experimental results, for an 8-step horizon, the IOD method solved the verification problem in approximately 0.7 seconds, whereas the IOS method required over 240 seconds. This efficiency gain is critical for practical applications where longer time horizons or larger networks are involved.
Conclusion and Future Work
While the current method provides a sound and complete procedure for bounded executions, it faces limitations regarding environment linearity and state-space explosion in very large networks. Future research may explore Satisfiability Modulo Theories (SMT) solvers to handle more complex, non-linear environment models and further improve computational performance. Despite these challenges, RNSVERIFY offers a practical path toward certifying short-term maneuvers in autonomous, learning-based systems.
Summary updated