🤖 machine learning

$S^3$ : A Smooth Simulation Surrogate for Optimizing Discrete Abstractions of Dynamical Systems

This paper introduces $S^3$ , a differentiable smooth simulation surrogate that enables gradient-based optimization of discrete abstractions for dynamical systems, effectively reducing conservatism while preserving soundness through Taylor model-based reachability.

Original authors: Jordan Peper, James Mathias Gast, Vignesh Nanduri, Tanmayee Maram, Ethan Howes, Ivan Ruchkin

Published 2026-08-18

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Jordan Peper, James Mathias Gast, Vignesh Nanduri, Tanmayee Maram, Ethan Howes, Ivan Ruchkin

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

Modern machines are increasingly making their own decisions in the real world, from self-driving cars navigating busy streets to drones delivering packages. These systems often rely on complex computer programs, including artificial intelligence, that act as "black boxes." We know they work, but we cannot always see exactly how they think or predict every possible move they might make. To ensure these machines are safe, engineers use a technique called abstraction. They replace the complicated, continuous reality of a moving object with a simpler, step-by-step model made of distinct blocks. This allows them to check if the machine will crash or fail before it ever leaves the lab. However, there is a catch. To be safe, these simplified models must be conservative; they must assume the worst-case scenario for every move. If they are too conservative, they become cluttered with impossible, imaginary dangers that never actually happen. This "false alarm" problem makes the models so large and messy that computers cannot analyze them in time, leaving engineers unable to certify the safety of the very systems they built.

A team of researchers at the University of Florida has developed a new method to solve this balancing act. They created a tool called S3, which acts as a smooth guide for refining these simplified models. Instead of guessing how to arrange the blocks of the model, the researchers built a mathematical objective that can be tweaked and improved using standard optimization techniques. This tool allows them to automatically adjust the size and shape of the model's blocks to remove unnecessary imaginary dangers while keeping the model safe. By testing this approach on three different scenarios—a spiraling system, a unicycle-like robot, and a simulated car climbing a hill—they found that their method produces models that are far more accurate and much faster to compute than previous techniques. The result is a way to verify that complex, intelligent machines are safe without getting bogged down by excessive, unrealistic warnings.

The core challenge in verifying these machines lies in the tension between safety and practicality. When engineers build a simplified model of a moving system, they must ensure that every possible real-world movement is covered by the model. If the model misses a real path, it is unsafe. To guarantee this, the model often includes extra paths that the real machine could never take. These extra paths are the "spurious" behaviors mentioned earlier. They are like drawing a map that includes every possible road, including ones that are blocked by walls or lead off a cliff, just to be sure you haven't missed a valid route. While this ensures you won't miss a real danger, it creates a map so crowded with dead ends that it becomes useless for planning a trip. The researchers needed a way to prune these dead ends without cutting off any real roads.

To achieve this, the team focused on a specific type of mathematical relationship called a simulation. In this context, a simulation is a way of checking if the simplified model can mimic the real system's behavior. If the model is "sound," it means the real system can never do something the model doesn't allow. The researchers wanted to minimize the "reverse simulation" error, which measures how much the model overestimates the system's possibilities. A high error means the model is too conservative, filled with too many fake paths. The problem was that the standard way to measure this error was too slow and too jagged to be improved automatically. It was like trying to smooth out a crumpled piece of paper by hand, one tiny fold at a time, without a tool to guide your fingers.

The researchers' breakthrough was to create a "surrogate," a smooth, easy-to-calculate stand-in for the difficult error measurement. They derived a new objective function that approximates the worst-case error but behaves smoothly, allowing computers to use gradient-based optimization. Think of this as replacing a jagged, rocky mountain path with a smooth, rolling hill that leads to the same destination. By following the slope of this smooth hill, the computer can quickly find the best arrangement of the model's blocks. This process involves adjusting the gaps between the blocks, making them wider or narrower depending on where the system moves most unpredictably. The method guarantees that the resulting model remains safe by construction, meaning it never misses a real path, but it aggressively cuts out the fake ones.

The team tested this approach on three distinct systems to see if it worked in practice. The first was a simple two-dimensional system that spiraled toward a target. The second was a three-dimensional unicycle robot that had to navigate around an obstacle to reach a goal. The third was a simulation of a car trying to climb a steep hill, a classic challenge in robotics where the car must build up momentum to reach the top. In each case, they compared their new method against two established strategies: one that refines the model only when it finds a specific error, and another that tries to optimize the grid size using a fixed shape. The results showed that the new method was significantly faster. For the unicycle robot, the new approach took about 140 seconds to build and verify the model, while the older refinement method took over 1,900 seconds. For the car climbing the hill, the new method took roughly 12 seconds compared to nearly 100 seconds for the older method.

Beyond speed, the quality of the models improved. The researchers measured how well the new models predicted the system's behavior and found that they were much less conservative. In the unicycle test, the new method reduced the average error by a significant margin, meaning the model contained far fewer impossible paths. For the car on the hill, the new method allowed the model to verify a larger portion of the starting positions that would actually lead to success. This is crucial because a model that is too conservative might tell an engineer that a car cannot climb the hill from a certain spot, even though it actually can. By reducing this false conservatism, the new method gives engineers more confidence that their systems will work as intended.

The study also revealed how the new tool behaves under different settings. The researchers found that they could tune the tool to focus on either the worst-case scenario or the average behavior of the system. If the goal is to ensure absolute safety against the most extreme possibilities, the tool can be set to prioritize the worst-case error. If the goal is to get a better overall picture of how the system usually behaves, the tool can be adjusted to focus on the average. This flexibility allows engineers to choose the right balance for their specific needs. The team also observed that the tool naturally learned to make the blocks of the model smaller in areas where the system moved quickly or changed direction sharply, and larger where the movement was steady. This adaptive granularity is exactly what is needed to create efficient models without wasting computational power on areas that are easy to predict.

The implications of this work extend beyond just these three examples. The method provides a general framework for making the verification of complex, intelligent systems more practical. As machines become more autonomous and are deployed in safety-critical environments, the ability to quickly and accurately verify their safety is paramount. The new tool does not require the engineers to know the exact controller the machine is using; it works with the known dynamics of the system and the controller's behavior. This makes it applicable to a wide range of scenarios, from industrial robots to autonomous vehicles. The researchers have made their code available to the public, inviting others to build upon this foundation.

In the end, the work demonstrates that it is possible to have both safety and efficiency in the verification of complex systems. By replacing a difficult, jagged measurement with a smooth, optimizable guide, the researchers have opened a new path for engineers to design and certify the next generation of intelligent machines. The method does not promise to solve every problem in artificial intelligence, but it offers a concrete, reliable way to ensure that the systems we rely on are not only smart but also safe. The ability to strip away the noise of false alarms and focus on the real risks is a significant step forward in the field of trustworthy engineering.

Technical Summary: S3 - A Smooth Simulation Surrogate for Optimizing Discrete Abstractions

Problem Statement

Intelligent systems, particularly those employing black-box controllers like neural networks, are increasingly deployed in safety-critical environments. Abstraction-based methods offer a way to analyze these complex dynamical systems by replacing them with simpler, finite-state models. However, constructing these abstractions involves a fundamental trade-off: ensuring soundness (the abstract model over-approximates the concrete system's behavior) often leads to excessive conservatism. Overly conservative abstractions introduce spurious transitions and nondeterminism that do not exist in the real system, potentially causing valid system properties to fail verification.

While bi-simulation theory provides metrics to quantify the relationship between a concrete system and its abstraction, these metrics are ill-suited for optimization. Specifically, the reverse simulation metric (which quantifies conservatism) is computationally expensive to evaluate, non-differentiable with respect to quantization parameters, and characterizes only worst-case discrepancies. Consequently, existing methods typically rely on uniform partitioning or heuristic refinements (like CEGAR) rather than directly optimizing the distribution of abstract states to minimize conservatism under a fixed computational budget.

Methodology

The authors propose S3 (Smooth Simulation Surrogate), a differentiable objective function designed to approximate the reverse simulation metric, enabling gradient-based optimization of abstraction parameters while preserving soundness by construction.

1. Soundness by Construction

To guarantee that the abstract model $\hat{s}_\theta$ exactly simulates the concrete system $s$ (i.e., $\sigma_\rightarrow(s, \hat{s}_\theta) = 0$ ), the paper employs a specific construction pipeline:

Rectilinear Quantization: The continuous state space is partitioned into variable-width cells using a parameterized quantization function $\psi_\theta$ . The boundaries are derived from unconstrained gap weights $\omega$ mapped via a Softplus activation to ensure positive widths.
Taylor Model Reachability: To determine transitions between abstract states, the method uses first-order Taylor models with bounded remainders to over-approximate the reachable sets of the concrete dynamics.
Transition Synthesis: An abstract transition exists if the over-approximated reachable set of a concrete cell intersects with the concretization of an abstract successor. This construction guarantees soundness for any choice of parameters $\theta$ .

2. The Smooth Simulation Surrogate (S3)

To optimize the quantization parameters $\theta$ to reduce conservatism, the authors derive a differentiable proxy for the reverse simulation metric $\sigma_\leftarrow$ .

Finite-Horizon Approximation: Instead of evaluating the infinite-horizon simulation function, the method uses a finite-horizon analogue $V_H$ , which measures the maximum discrepancy over a time window $H$ .
Abstract Value Function: A strict upper bound on the simulation metric is constructed using an abstract value function $\hat{W}_H(\hat{x})$ . This function aggregates the radius of the reachable set and the distance between the trajectory of the concrete system's centroid and the abstract state's centroid.
Differentiable Surrogate: To make the upper bound differentiable, the non-smooth operations (supremums over time steps and abstract states) are replaced with temperature-scaled log-sum-exp (LSE) aggregations. Additionally, the discrete logic of set intersections is replaced with smooth over-approximations of reachable sets using a fixed inflation vector $\tilde{e}$ .
Optimization: The resulting objective, $\tilde{\sigma}_\leftarrow^H(s, \theta)$ , is minimized using stochastic gradient descent (SGD) to find the optimal grid spacing that minimizes conservatism.

Key Contributions

The paper makes three primary contributions:

Differentiable Proxy: A computationally efficient, smooth surrogate (S3) that approximates the reverse simulation metric, serving as a proxy for abstraction conservatism.
Optimization Pipeline: A gradient-based framework that optimizes state quantization parameters to minimize conservatism while strictly adhering to soundness constraints via Taylor model-based reachability.
Empirical Validation: Case studies demonstrating that S3 is strongly correlated with the true simulation metric and effectively reduces conservatism compared to baseline strategies.

Experimental Results

The method was evaluated on three case studies: a 2D spiral system, a 3D unicycle (Dubins) system, and the Mountain Car benchmark.

Correlation and Efficiency: S3 exhibits strong positive correlation (Pearson and Spearman coefficients often > 0.7) with the finite-horizon reverse simulation metric $\sigma_\leftarrow^H$ . Crucially, evaluating S3 is orders of magnitude faster (0.01–0.02 seconds) than computing the ground-truth metric (seconds to minutes), making it viable for iterative optimization.
Performance vs. Baselines:
- CEGAR (Counterexample-Guided Abstraction Refinement): S3 achieves comparable or better verification recall and simulation metrics but requires significantly less total computation time. For example, on the Unicycle system, S3 completed optimization in ~140 seconds versus ~1924 seconds for CEGAR.
- Grid Resolution Optimization (Weber et al.): While Weber's method optimizes aspect ratios, S3 optimizes individual gap widths. S3 often achieves lower mean and median discrepancies and higher verification recall, even when the worst-case metric is slightly higher than Weber's in some configurations.
Hyperparameter Sensitivity: The paper notes a trade-off controlled by the LSE temperature parameters. Lower temperatures prioritize worst-case metrics, while higher temperatures improve correlation with mean/median discrepancies, allowing users to tune the objective based on specific verification needs.

Significance and Claims

The paper claims to be the first to derive a differentiable proxy for an upper bound on the reverse simulation metric for discrete abstractions of dynamical systems. By bridging the gap between formal verification (soundness) and optimization (minimizing conservatism), S3 enables the automatic synthesis of "minimally conservative" abstractions.

The authors emphasize that their approach does not require learning a controller or assuming specific system structures beyond differentiability. Instead, it leverages known dynamics and controllers to directly optimize the abstraction's geometry. The results suggest that S3 provides a practical, scalable alternative to traditional refinement loops, offering a principled way to balance computational cost with the fidelity of the abstract model.

The work concludes that while S3 is a significant step forward, future extensions could include jointly optimizing the infimum selection in the metric definition, exploring neural parameterizations for non-grid partitions, and extending the framework to probabilistic transition systems.