On the Fly State Space Exploration

76 concepts59 papers1 proposal

Imagine trying to verify whether a complex computer program or a robotic controller will always remain safe. The traditional approach to formal verification requires building a complete, highly detailed mathematical map of every possible state the system could ever enter before checking if any of those states are hazardous.

In practice, this "offline" or "pre-computed" approach frequently hits a wall known as the state-space explosion problem. As systems grow linearly in complexity, their potential state combinations grow exponentially. As Joseph Halpern et al. observed in Finite Models for Deterministic Propositional Dynamic Logic, standard top-down algorithms that construct the entire state space upfront quickly become computationally intractable.

The core intuition behind on-the-fly and lazy state-space exploration is simple: build the map as you walk it, not before you leave. By interleaving the construction of the system's state space with the verification search itself, we can bypass the need to ever compute or store the vast majority of unreachable or irrelevant states.


Why does shifting from offline pre-computation to online, step-by-step exploration yield such massive efficiency gains?

In Validating Generalized Plans in the Presence of Incomplete Information, Marianne Winslett contrasted "Prove-Ahead" (pre-calculating safety requirements) with "Prove-As-You-Go" verification. The author demonstrated that step-by-step verification is fundamentally more efficient because it focuses exclusively on states that are actually reached during execution. Pre-computing a state space forces an algorithm to spend massive computational resources analyzing potential violations in states that the system can never actually encounter.

Offline Verification:
[System Description] ──> [Exhaustive State Graph] ──> [Property Checker] ──> Result
                             (Explodes in Memory)

On-the-Fly Verification:
[System Description] ──┐
                       ├──> [Incremental Search Loop] ──> Result (Stops Early)
[Property Query]     ──┘       (Generates states on-demand)

This insight transformed real-time systems verification. Foundational model-checking tools like UPPAAL adopted this paradigm to handle complex, time-sensitive protocols. As explained by Kim Guldstrand Larsen et al. in Model-Checking for Real-Time Systems and Johan Bengtsson et al. in UPPAAL in 1995, on-the-fly verification constructs the system's transition graph incrementally during the search process.

Instead of pre-generating a massive global graph, the engine evaluates the system's rules locally to generate only the immediate successor states of the current path. Paul Pettersson et al. showed in Compositional and Symbolic Model-Checking of Real-Time Systems that this localized approach makes complex multi-process systems verifiable by focusing computational resources strictly on reachable and relevant execution paths.


Lazy Determinization and Abstraction

The power of the on-the-fly paradigm extends beyond skipping unreachable states; it fundamentally redefines how we handle complex mathematical transformations like determinization and abstraction.

Bypassing the Automata Bottleneck

When synthesizing software from logical specifications (such as Linear Temporal Logic), traditional methods suffer from a "doubly exponential" bottleneck. They must convert a non-deterministic specification into a massive, deterministic finite automaton upfront.

To break this bottleneck, Alberto Camacho et al. in Finite LTL Synthesis as Planning and Shengping Xiao et al. in On-the-fly Synthesis for LTL over Finite Traces introduced lazy determinization. Instead of building the complete deterministic state space upfront, the system offloads non-determinism to targeted search algorithms, generating successor states only as needed to find a winning strategy.

Similarly, Jun Sun et al. applied this to timed automata in Are Timed Automata Bad for a Specification Language? Language Inclusion Checking for Timed Automata, constructing the deterministic equivalent incrementally during the exploration of the implementation's state space.

On-Demand Discretization

When verifying continuous or hybrid physical systems (like autonomous vehicles or wind turbines), the continuous physical world must be discretized into abstract symbolic blocks. Exhaustive pre-discretization is computationally prohibitive.

In Lazy Abstraction-Based Control for Safety Specifications, Kyle Hsu et al. demonstrated that computing abstract state transitions on-the-fly during controller synthesis avoids the waste of calculating transitions for states that are inherently unsafe or never visited.

For large-scale stochastic systems, Mark Kattenbelt et al. in Game-Based Probabilistic Predicate Abstraction in PRISM, Alessandro Abate et al. in ARCH-COMP21 Category Report: Stochastic Models, and Abolfazl Lavaei et al. in AMYTISS: Parallelized Automated Controller Synthesis for Large-Scale Stochastic Systems proved that calculating transition probabilities dynamically on-demand drastically conserves memory, making high-dimensional verification possible without pre-computing the entire state space.


Why It Works: Early Termination and Local Verification

The primary mathematical reason lazy evaluation provides such a massive speedup is its capacity for early termination.

Global or offline verification algorithms typically rely on fixed-point computations that must analyze the entire model before returning a definitive answer. As Nisarg Shah et al. noted in Symbolic Algorithms for Qualitative Analysis of Markov Decision Processes with Büchi Objectives, this lack of incremental discovery is highly inefficient when a user only needs to verify a specific property or subset of states.

By contrast, on-the-fly explicit-state exploration, as advocated by Rajeev Alur et al. in On-the-Fly Reachability and Cycle Detection for Recursive State Machines, prioritizes discovering program paths incrementally from the initial state. This design is incredibly effective for finding bugs:

  1. Immediate Halting: The moment the search encounters a state that violates a safety property, the algorithm terminates. It does not matter if there are billions of unexplored states remaining; the counterexample has been found.
  2. Localized Proofs: In Hector: An Equivalence Checker for a Higher-Order Fragment of ML, David Hopkins showed that generating counterexamples on-the-fly allows tools to detect program mismatches in milliseconds.
  3. Coalition Early-Outs: For multi-agent systems, Falke B. Ø. Carlsen et al. demonstrated in CGAAL: Distributed On-The-Fly ATL Model Checker with Heuristics that local graph exploration can confirm a winning strategy for a coalition based on a partial search, avoiding global fixed-point calculations entirely.

On-Demand Composition and Live-State Initialization

Lazy state exploration also redefines how we compose complex systems and refine abstract models.

When a system is built from multiple interacting components, the total state space is the cross-product of all individual component states. Pre-computing this composition causes an immediate combinatorial explosion. Nikolaos Kekatos et al. demonstrated in Modeling the Wind Turbine Benchmark with PWA Hybrid Automata that on-the-fly composition allows verification tools to handle massive industrial benchmarks by evaluating component interactions dynamically, exploring only the joint locations that are actually reachable.

Furthermore, if an abstract model is found to be too coarse during verification, it must be refined. Instead of refining the entire model globally, "lazy abstraction" frameworks—such as the Wolverine tool developed by Daniel Kroening et al. in Wolverine: Battling Bugs with Interpolants - (Competition Contribution)—limit model refinement strictly to the local regions encountered during the search for error states.

Global Refinement (Expensive):
[Coarse Abstract Model] ──> [Refine Entire Model] ──> [Re-verify Everything]

Lazy Abstraction (Targeted):
[Explore Path] ──> [Hit Error Region?] ──> [Refine ONLY This Local Region]

Finally, this paradigm enables live-state verification. Rather than starting an exhaustive search from a hypothetical initial system state, Maysam Yabandeh et al. demonstrated in CrystalBall: Predicting and Preventing Inconsistencies in Deployed Distributed Systems that model checking can be initialized directly from live, running system snapshots.

By executing a localized, goal-directed search—a concept pioneered by Kim Guldstrand Larsen in Efficient Local Correctness Checking—from the system's current operational context, modern verifiers bypass the state-space explosion of early-state histories entirely. They focus all computational power on predicting and preventing bugs in the states the system is actually experiencing in real-time.

Key Foundational Work

Validating Generalized Plans in the Presence of Incomplete Information (1987) — contributed 1 concept elements to this direction.
Finite Models for Deterministic Propositional Dynamic Logic (1981) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 55 papers
  2. Version 1 · 2026-10-04 · 38 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_lazy_state_space_exploration_e343ca24,
  title = {lazy state-space exploration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lazy-state-space-exploration/rdr_e343ca24858c40688b421ac6de1134c5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_lazy_state_space_exploration_e343ca24_v2,
  title = {lazy state-space exploration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lazy-state-space-exploration/rdr_e343ca24858c40688b421ac6de1134c5/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake