Reducing Conservatism in Reachability Over Approximation

46 concepts46 papers1 proposal

When verifying the safety of a complex system—whether it is an autonomous vehicle navigating an intersection, a neural network controlling a robotic arm, or a power grid balancing renewable energy inputs—we face a fundamental mathematical barrier. Computing the exact set of future states that a non-linear or neural-network-driven system can reach is often computationally intractable or completely undecidable.

To bypass this barrier, formal verification relies on over-approximation. Instead of calculating the exact, jagged trajectory of a system's possible futures, we draw a simplified geometric boundary (like a box, ellipsoid, or polytope) that is guaranteed to enclose every single valid state. If this enclosing boundary does not intersect with any unsafe regions, we have a ironclad mathematical proof that the system is safe. This strategy dates back to foundational static analysis concepts, such as those explored by Moreno Falaschi et al. in Compositional Analysis for Concurrent Constraint Programming, which traded perfect classical correctness for correct, superset approximations to make complex dataflow analysis feasible.

The catch is conservatism. If our over-approximation is too loose, the boundary will spill over into safe zones and falsely report a collision or failure. This "over-approximation gap" introduces severe practical penalties:

To make formal verification practical, a major research direction focuses on reducing the over-approximation gap. By understanding why conservatism happens, researchers have developed mechanisms to tighten these boundaries without losing their mathematical guarantees.


The Root of Conservatism: The Wrapping Effect and Dependency Loss

To understand why over-approximations bloat, consider a simple system where a state variable $x$ is multiplied by a matrix at each timestep. If our initial uncertainty is represented by a axis-aligned box, and the system rotates the state space by 45 degrees, the true reachable set becomes a tilted diamond.

If our verification tool can only represent axis-aligned boxes, it must draw a new, larger box that encloses the tilted diamond. This introduction of unachievable states is known as the wrapping effect. As this process repeats over multiple timesteps, the unachievable states compound exponentially, causing the calculated boundary to explode in size.

Furthermore, standard interval arithmetic suffers from dependency loss: it treats different occurrences of the same variable as independent. If $x \in [-1, 1]$, evaluating $x - x$ using naive interval arithmetic yields $[-1, 1] - [-1, 1] = [-2, 2]$, completely missing the fact that the two variables are perfectly correlated and their difference is exactly $0$. This issue frequently causes symbolic analysis tools to fail when certifying model robustness against data perturbations, as observed by Anna P. Meyer et al. in Certifying Robustness to Programmable Data Bias in Decision Trees.

To combat this, researchers have designed more sophisticated geometric data structures that preserve dependencies across time and variables.

Constrained Polynomial Zonotopes

A standard zonotope is a center vector plus a linear combination of generator vectors scaled by factors between $-1$ and $1$. While computationally efficient, standard zonotopes cannot capture non-linear dependencies or complex intersections.

To solve this, Matthias Althoff et al. introduced Constrained Polynomial Zonotopes (CPZs) in Constrained polynomial zonotopes. CPZs allow the factors to be raised to polynomial powers and introduce explicit equality constraints between them. This mathematical framework allows the representation to "remember" non-linear correlations between variables across timesteps, drastically reducing the wrapping effect while maintaining computational tractability.

Tracking Initial-State Dependencies

Another way to prevent boundary bloat is to explicitly track how each point in the current reachable set relates back to its origin. In Utilizing dependencies to obtain subsets of reachable sets, Niklas Kochdumper et al. demonstrated that by using polynomial zonotopes to maintain a functional link between initial conditions and future states, they could instantly extract tight, precise reachable sets for specific subsets of starting conditions. This eliminates the need to re-run expensive global simulations from scratch, mitigating the conservatism that arises when averaging over a wide range of initial states.


Eliminating Geometric Shapes via Exact Convex Hulls

Even with advanced shapes like CPZs, fitting a predefined geometric template (like a box or ellipsoid) around an arbitrary, non-linear reachable set inherently introduces a gap. What if we could bypass these templates entirely?

In Exact Characterization of the Convex Hulls of Reachable Sets, Thomas Lew et al. proved a remarkable theoretical result: the exact convex hull of a non-linear system's reachable set can be characterized by a finite-dimensional ordinary differential equation (ODE).

Instead of trying to wrap the reachable set in an arbitrary ellipsoid, their method samples initial directions on a unit sphere and integrates an augmented ODE forward in time. This maps out the absolute tightest possible convex boundary for the system. Because it avoids coarse geometric templates, it eliminates the false safety violations that plague traditional reachability tools.

Traditional Over-Approximation          Exact Convex Hull (Lew et al.)
      +-----------------+                       .  .  ...  .
      |     /\          |                     .  /\         .
      |    /  \  True   |                    .  /  \  True   .
      |   /____\ Set    |                   .  /____\ Set     .
      |                 |                    .               .
      +-----------------+                      . . . . . . .
 (Coarse box introduces gap)             (Tightest convex boundary)

For online, real-time control where computing this continuous boundary might still be too demanding, sampling-based alternatives provide a bridge. In Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling, Thomas Lew et al. leveraged Random Set Theory to guarantee asymptotic convergence to the true reachable set's convex hull. To prevent the opposite problem—where a finite number of samples creates an under-approximation that dangerously underestimates risk—the authors introduced an adversarial sampling technique called robUP!. This technique actively hunts for edge-case parameters to ensure the sample boundaries expand rapidly and safely toward the true outer limit.


Contextual and Maneuver-Based Decomposition

Often, conservatism does not stem from bad geometry, but from a lack of context. Traditional reachability analysis assumes an agent might execute any physically possible action at any moment. For an autonomous vehicle, this means drawing a safety zone that accounts for the car suddenly swerving violently left, slamming on the brakes, or accelerating to its maximum speed simultaneously.

In Refining Obstacle Perception Safety Zones via Maneuver-Based Decomposition, Sever Topan et al. showed that if you decompose the reachability analysis based on the agent's intended maneuver (such as maintaining a lane or executing a specific turn), you can prune away vast swaths of impossible trajectories. By applying a temporal convolution operation tailored to the chosen maneuver, the authors reduced the volume of perception safety zones by up to 76% without missing any genuine threats. This demonstrates that incorporating high-level intent is a powerful mechanism for shrinking the over-approximation gap.


Trading Determinism for Tight Probabilistic Bounds

In high-dimensional systems—such as Semantic Segmentation Networks (SSNs) processing millions of pixels—deterministic over-approximation becomes a victim of the curse of dimensionality. Attempting to find an absolute deterministic bound for every pixel output results in a boundary so massive that it renders the certification meaningless, a challenge documented by Navid Hashemi et al. in Scaling Data-Driven Probabilistic Robustness Analysis for Semantic Segmentation Neural Networks.

When absolute determinism forces uselessly conservative bounds, the solution is to pivot to a Probably Approximately Correct (PAC) or probabilistic framework.

In Data-Driven Reachability with Scenario Optimization and the Holdout Method, Elizabeth Dietrich et al. proved that traditional "wait-and-judge" scenario optimization techniques often yield highly conservative safety boundaries because they are forced to accommodate every single boundary data point. The authors demonstrated that the classic holdout method (splitting data into training and validation sets) provides significantly tighter and more computationally efficient probabilistic safety guarantees.

Crucially, they provided mathematical proof that converting these probabilistic bounds into absolute deterministic ones requires a sample size that grows exponentially with the system's dimension. Accepting a tiny, bounded probability of violation allows us to collapse the over-approximation gap and obtain highly practical, tight safety boundaries for high-dimensional systems.


Embedded Over-Approximation: Designing for Verifiability

Most verification workflows treat the system as a fixed "black box" and attempt to wrap an over-approximation around it post-hoc. If the system's internal dynamics are highly non-linear, this post-hoc wrapping is doomed to be highly conservative.

A recent paradigm shift embeds the over-approximator directly into the system's architecture during training. The framework known as SMLE (Safe Machine Learning via Embedded Overapproximation) achieves this by training a neural network alongside an internal, parallel "overapproximator" layer.

Instead of trying to solve an NP-hard verification problem after training, the network is forced during training to optimize its weights such that its worst-case behavior remains easily and tightly boundable by a polynomial-time verification check. This creates a controlled trade-off: while it slightly restricts the unconstrained parameter space of the model, it ensures that the resulting safety guarantees are incredibly tight and can be verified almost instantly during inference.


Summary of Core Mechanisms

The research direction of mitigating over-approximation conservatism can be understood through a handful of distinct mechanisms, each tackling a different source of boundary bloat:

Mechanism Source of Conservatism Addressed Key Reference
Advanced Geometric Representations The wrapping effect and dependency loss in interval arithmetic. Althoff et al., Kochdumper et al.
Exact Convex Hull Tracking Inherent gaps introduced by fitting arbitrary templates (boxes/ellipsoids). Lew et al.
Maneuver-Based Decomposition Assuming the agent will take any physically possible action without context. Topan et al.
Probabilistic (PAC) Frameworks The exponential growth of deterministic bounds in high dimensions. Dietrich et al., Hashemi et al.
Embedded Over-Approximation The difficulty of wrapping tight bounds around unconstrained, highly non-linear models post-hoc. SMLE

Key Foundational Work

Applications of polytopic approximations of reachable sets to linear dynamic games and a class of nonlinear systems (2003) — contributed 2 concept elements to this direction.
Compositional Analysis for Concurrent Constraint Programming (1993) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_conservative_over_approximation_7c72aa02,
  title = {conservative over-approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conservative-over-approximation/rdr_7c72aa02fe95410c99b7ed96a4d905a6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_conservative_over_approximation_7c72aa02_v1,
  title = {conservative over-approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conservative-over-approximation/rdr_7c72aa02fe95410c99b7ed96a4d905a6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake