VeRecycle: Reclaiming Guarantees from Probabilistic Certificates for Stochastic Dynamical Systems after Change

Sterre Lutz, Matthijs T. J. Spaan, Anna Lukina

Abstract

Ensuring the safety of autonomous systems in stochastic environments typically requires expensive formal verification. However, these guarantees are often invalidated by localized environmental changes, necessitating costly re-certification. We present VeRecycle, a framework that "recycles" existing probabilistic safety proofs by mathematically adjusting them in response to changes. VeRecycle achieves a three-order-of-magnitude speedup over traditional methods while maintaining competitive safety thresholds.

Introduction

Autonomous systems operating in real-world environments, such as warehouse robots or self-driving vehicles, must navigate stochastic dynamics while maintaining rigorous safety guarantees. Researchers often employ "probabilistic neural Lyapunov certificates" to prove that a system will reach a goal state while avoiding unsafe regions with a specific probability. Unfortunately, these formal proofs are brittle; a minor environmental change, such as a new obstacle or a change in surface friction, renders the original certificate invalid. Traditional re-certification is computationally intensive, often requiring hours of retraining and formal solving. VeRecycle addresses this gap by providing a lightweight method to update safety guarantees on the fly.

Methodology

VeRecycle leverages the mathematical properties of Lyapunov functions to adjust safety thresholds without re-running full verification.

The framework assumes that while the specific nature of a change might be unknown, its location within the state space ($\mathcal{X}_?$) is identified. The core theoretical insight is that the maximum reclaimable safety threshold is linked to the infimum (minimum value) of the existing Lyapunov certificate within the affected area. If the Lyapunov function maintains high values in the "corrupted" region, the system is statistically unlikely to enter that area, allowing much of the original safety guarantee to be preserved.

Sound Approximation and Compositional Re-routing

To ensure safety, VeRecycle uses Interval Bound Propagation (IBP) to find a sound lower bound on the certificate's value. For complex, multi-stage tasks, the framework employs a graph-based compositional approach. By updating safety scores for individual path segments (modules), VeRecycle can use shortest-path algorithms to identify the safest global route in the modified environment.

Graph-based navigation in the Nine Rooms benchmark showing safety thresholds and re-routing.

Experimental Evaluation

The framework was evaluated using the "Stochastic Nine Rooms" benchmark, where a robot navigates a 3x3 grid of rooms with slippery floors. The researchers introduced seven types of localized changes across 63 unique reach-avoid specifications to test the robustness and efficiency of the recycling process.

Results

VeRecycle demonstrates significant improvements in computational efficiency. As shown in the results table, the framework computes new safety thresholds in approximately 0.33 seconds, compared to over 918 seconds for baseline re-certification—a speedup exceeding 2,700x.

Comparison of VeRecycle against baseline methods in terms of computation time and reclaimed threshold quality.

Crucially, this speed does not come at the cost of safety. The reclaimed probability thresholds remain highly competitive with, and often identical to, those produced by exhaustive verification methods. In practical scenarios, VeRecycle successfully re-routes systems away from degraded paths to maintain high overall success probabilities.

Conclusion

VeRecycle represents a significant step toward resilient autonomous systems. By shifting the paradigm from "re-verify" to "re-calculate," it enables real-time adaptation to environmental changes. Future work will focus on extending the framework to continuous-time systems and integrating targeted re-learning loops to further refine conservative bounds.

Summary updated

Abstract

Autonomous systems operating in the real world encounter a range of uncertainties. Probabilistic neural Lyapunov certification is a powerful approach to proving safety of nonlinear stochastic dynamical systems. When faced with changes beyond the modeled uncertainties, e.g., unidentified obstacles, probabilistic certificates must be transferred to the new system dynamics. However, even when the changes are localized in a known part of the state space, state-of-the-art requires complete re-certification, which is particularly costly for neural certificates. We introduce VeRecycle, the first framework to formally reclaim guarantees for discrete-time stochastic dynamical systems. VeRecycle efficiently reuses probabilistic certificates when the system dynamics deviate only in a given subset of states. We present a general theoretical justification and algorithmic implementation. Our experimental evaluation shows scenarios where VeRecycle both saves significant computational effort and achieves competitive probabilistic guarantees in compositional neural control. Code — https://github.com/SUMI-lab/VeRecycle Extended version — https://doi.org/10.48550/arXiv.2505.14001
BibTeX
@inproceedings{lutz2025verecycle,
  author = {Sterre Lutz and Matthijs T. J. Spaan and Anna Lukina},
  title = {{VeRecycle: Reclaiming Guarantees from Probabilistic Certificates for Stochastic Dynamical Systems after Change}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/52},
}
Figure