🤖 machine learning

Verification of Unknown Dynamical Systems via Autoencoder Latent Space

This paper proposes a formal verification framework that combines convex autoencoders and kernel-based dynamics learning to reduce high-dimensional dynamical systems into a lower-dimensional latent space, constructing a finite abstraction that guarantees the containment of true system behaviors to enable scalable and correct verification.

Original authors: Robert Reed, Luca Laurenti, Morteza Lahijanian

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Robert Reed, Luca Laurenti, Morteza Lahijanian

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to prove that a very complex, high-dimensional robot (like a self-driving car with hundreds of sensors) will never crash and will always reach its destination. This is called "formal verification."

The problem is that the robot's "brain" is so complicated and has so many moving parts (dimensions) that checking every possible scenario is like trying to count every grain of sand on a beach. It takes too long and requires too much computer power.

This paper proposes a clever solution: Shrink the problem down, solve it there, and prove the solution works for the big version.

Here is how they do it, using simple analogies:

1. The "Magic Map" (The Autoencoder)

Imagine the robot's world is a giant, 3D maze. Trying to navigate and prove safety in 3D is hard. The authors use a special tool called an Autoencoder to create a "Magic Map."

The Encoder: This is like a translator that takes the complex 3D maze and compresses it into a simple 2D drawing.
The Decoder: This is the reverse translator that can turn the 2D drawing back into the 3D maze.
The Catch: Usually, when you squish a 3D object into 2D, you lose information. Two different places in the 3D maze might look like the same spot on the 2D map. This creates "folding" or confusion.

The Innovation: The authors built a very specific type of encoder (called a Convex Autoencoder) that acts like a strict, orderly librarian. It ensures that if you have a solid, connected shape in the 3D world, it stays a solid, connected shape on the 2D map. It doesn't tear or fold the map in a way that breaks the logic.

2. The "Foggy Crystal Ball" (Inclusion Dynamics)

In the real world, the robot's movement is deterministic (if you push it, it goes a specific way). But on the 2D map, because we squished the world, the robot's movement becomes "fuzzy."

If the robot is at point A on the map, it might actually be at any of several different spots in the real 3D world.
Therefore, on the map, the robot doesn't just go to one next spot; it could go to a whole cloud of possible next spots.

The authors call this "Inclusion Dynamics." Instead of predicting a single point, they predict a "cloud" or a "ball" of possibilities. They use a statistical tool called a Gaussian Process (think of it as a very smart crystal ball) to learn how these clouds move. They don't just guess the center of the cloud; they calculate the worst-case boundaries of the cloud to ensure they never miss a possibility.

3. The "Safety Net" (Verification)

Once they have this 2D map with fuzzy clouds of movement, they build a "Safety Net" (a Finite Abstraction).

They divide the 2D map into small tiles.
They check: "If the robot starts in this tile, can it ever get stuck in a 'danger zone' (like a cliff or a wall)?"
Because they used the "worst-case" clouds, if the Safety Net says "Yes, it's safe," they know for a fact that the robot is safe in the real 3D world, too. Even if the map is fuzzy, the safety net is built to be extra cautious.

4. The "Proof of Return"

The most important part is that they proved you can take the answer from the 2D map and map it back to the real 3D world without losing the guarantee.

If the 2D map says "This area is safe," they can mathematically prove that the corresponding area in the real 3D world is also safe.
They tested this on a 26-dimensional system (a robot using LiDAR sensors). Traditional methods would have taken forever or failed completely because the number of possibilities explodes. Their method shrank it down to 2 dimensions, solved it quickly, and proved it worked.

Summary

Think of it like this:
You have a massive, chaotic library (the high-dimensional system). You want to prove no books will ever fall off the shelves.

Compress: You take a photo of the library and shrink it down to a tiny, manageable sketch (the latent space).
Blur: Because the sketch is small, the shelves look a bit blurry. You don't know exactly where every book is, so you draw a "fuzzy box" around where a book could be (Inclusion Dynamics).
Check: You check the sketch. If the fuzzy boxes never touch the "danger zone" on the sketch, you know for a fact the real books won't fall.
Translate: You prove that your sketch is drawn so carefully that if it's safe, the real library is definitely safe.

The paper claims this method allows us to verify complex, AI-controlled systems that were previously too big to check, without sacrificing safety guarantees.

Technical Summary: Verification of Unknown Dynamical Systems via Autoencoder Latent Space

Problem Formulation
Formal verification of continuous-space dynamical systems is essential for guaranteeing that autonomous systems satisfy safety and liveness specifications, often expressed in Linear Temporal Logic (LTL). Standard approaches involve constructing finite-state abstractions to enable model checking. However, these techniques face severe scalability challenges in high-dimensional settings, as the size of the abstraction grows exponentially with the state space dimension. This issue is exacerbated in AI-enabled systems (e.g., those controlled by neural networks processing LiDAR or camera data) where dynamics are complex, partially unknown, or black-box. While data-driven dimensionality reduction techniques like autoencoders offer a potential solution for scalability, they typically lack formal correctness guarantees. Specifically, mapping high-dimensional specifications to a learned latent space and ensuring that the learned latent dynamics faithfully represent the original system's behavior (including non-determinism) remains an open challenge. Existing methods often trade correctness for flexibility or rely on strong assumptions about system dynamics that do not hold for learned representations.

Methodology
The proposed framework addresses these challenges by combining dimensionality reduction with abstraction-based verification to provide formal guarantees for high-dimensional systems with unknown dynamics. The approach consists of four main stages:

Convex Autoencoder Architecture: To ensure the latent space is interpretable and supports sound reasoning, the authors employ a Convex Autoencoder. The encoder is restricted to be an Input Convex Neural Network (ICNN) with specific structural constraints: strictly monotonic activation functions (to act as homeomorphisms), injective first and skip layers, and full-rank weight matrices. This architecture, termed a "Connected Input-Connected Output" (CICO) network, guarantees that the pre-image of any connected set in the latent space is a connected set in the original state space. This property is crucial for handling the non-injectivity of the mapping when the latent dimension is lower than the minimal realization of the system.
Learning Latent Inclusion Dynamics: Because the dimensionality reduction may result in a loss of information, the evolution in the latent space is modeled as inclusion dynamics (set-valued) rather than deterministic difference equations. The authors introduce "Inclusion Gaussian Processes" (Inclusion GPs), a novel formulation of Gaussian Process Regression (GPR) for set-valued dynamics. This method lifts the dynamics to a higher-dimensional space where they follow difference equations involving an unobserved parameter $c$ . By learning a deep kernel that incorporates this unobserved coordinate, the method predicts the evolution of the system as a set (specifically, a ball in the latent space) and provides rigorous error bounds based on Reproducing Kernel Hilbert Space (RKHS) analysis.
Sound Finite Abstraction Construction: Using the learned Inclusion GP, the authors construct a Nondeterministic Transition System (NTS) in the latent space.
- Region Mapping: High-dimensional regions of interest (safe, unsafe, and goal sets) are mapped to the latent space. The convexity of the encoder allows for efficient sampling-based under-approximation and probabilistic over-approximation (using $\epsilon$ -RandUp) of these sets.
- Transition Relation: Transitions between abstract states are computed by propagating regions through the Inclusion GP model, accounting for regression errors and the unobserved parameter $c$ . This ensures that the abstraction conservatively captures all possible behaviors of the original system.
- Correctness Guarantees: The framework proves that if a state in the latent NTS satisfies a reach-avoid specification, then all corresponding trajectories in the original high-dimensional system satisfy the specification with a high confidence level ( $1-\delta$ ).
Verification and Decoding: Standard model-checking tools are applied to the latent NTS to identify states guaranteed to satisfy the specification ( $Q_{yes}$ ), states that cannot satisfy it ( $Q_{no}$ ), and uncertain states ( $Q_?$ ). Because the encoder is convex, satisfying latent states can be efficiently decoded back to the original high-dimensional space using convex optimization to identify the set of initial states in the original system that are guaranteed to be safe.

Key Contributions
The paper makes four primary contributions:

Provably Correct Mapping: A method for mapping high-level specifications into a latent space using a CICO encoder, enabling efficient reasoning over compressed representations while preserving formal guarantees.
Inclusion GPs: A novel formulation of Gaussian Process regression for inclusion-valued (set-valued) dynamics, enabling the learning of latent dynamics governed by difference inclusions without requiring explicit knowledge of the underlying unobserved parameters.
Sound Abstraction Framework: A complete framework for generating sound finite abstractions in the latent space based on Inclusion GPs, including procedures for mapping satisfaction guarantees back to the original system with proofs of correctness.
Empirical Validation: Demonstration of the approach on multiple systems, including a 26-dimensional system controlled by a neural network (using LiDAR inputs), showing significant scalability improvements over traditional abstraction methods.

Results
The approach was evaluated on three case studies:

3D to 2D: A minimal realization system where the method successfully verified the entire latent space, whereas traditional data-driven abstraction in the original 3D space failed to verify reachability due to uncertainty in slow-moving dimensions.
6D to 2D: An over-parameterized system with nonlinear observations. The method verified 100% of the latent space for the obstacle-free case and 59.78% for the case with an obstacle. In contrast, attempting abstraction in the original 6D space resulted in state explosion, failing to verify any regions beyond the goal itself within the time limit.
26D to 2D: A robot navigation task with LiDAR inputs and a neural network controller. The method successfully learned a 2D latent space that captured the system's dynamics with minimal non-determinism, verifying 50.0001% of the latent space. This demonstrated the ability to handle high-dimensional observation spaces where traditional methods are infeasible.

Significance
The paper claims to bridge a critical gap between dimensionality reduction and formal verification. By providing soundness guarantees for both the mapping of specifications and the learned latent dynamics, the work eliminates false positives in verification results, a common issue in learning-based control. The authors emphasize that their approach enables scalable verification for high-dimensional systems with unknown dynamics, a capability previously unattainable with existing formal methods. While the framework is sound, the authors modestly note limitations, including the restriction to convex encoders (which limits expressivity) and open questions regarding noise incorporation and control synthesis, which are identified as directions for future work.

1. The "Magic Map" (The Autoencoder)

2. The "Foggy Crystal Ball" (Inclusion Dynamics)

3. The "Safety Net" (Verification)

4. The "Proof of Return"

Summary

More like this