On Demand State Space Exploration

This direction is merged into another direction: lazy state-space exploration. Its last version stays readable and citable here.

Version 1 of 114 papers23 conceptsfrozen 2026-10-04

In fields ranging from natural language processing to formal verification, researchers often model problems as massive graphs of states and transitions. Whether it is a parse table for a complex grammar, a state machine for speech recognition, or a transition system for a robot's logic, these graphs share a common enemy: state explosion.

The traditional approach is "eager": you compile the entire state space upfront before you begin your search. However, as systems grow in complexity, this pre-computation becomes a bottleneck, often requiring gigabytes of memory and hours of CPU time to generate states that may never even be visited.

A powerful alternative has emerged across these disciplines: On-demand (or lazy) computation. Instead of building the whole map before the journey, these systems generate only the specific "tiles" of the state space required by the traversal algorithm in real-time.

The Need to Know Principle

The core intuition behind on-demand computation is that for any specific task—parsing a single sentence or finding one counterexample in a program—only a tiny fraction of the total possible state space is relevant.

In Incremental Parser Generation for Tree Adjoining Grammars, Anoop Sarkar demonstrated that pre-compiling exhaustive tables for complex grammars is often unnecessary. By constructing states and transitions based on the specific input being processed, the system avoids the "startup tax" of full compilation, significantly reducing initial memory overhead.

Similarly, Stephan Kanthak and Hermann Ney applied this to weighted finite-state automata in their FSA toolkit. By calculating transitions and weights only when required by the traversal, they reduced memory usage in large-scale translation tasks from gigabytes to megabytes.

Lazy Determinization and Synthesis

One of the most computationally expensive operations in automata theory is determinization—turning a non-deterministic system (where one action can lead to multiple states) into a deterministic one. This process is notorious for exponential growth.

In the context of software synthesis, Alberto Camacho and colleagues developed SynKit, which treats LTL synthesis as a planning task. Rather than building a complete deterministic state space upfront, they employ lazy determinization. The solver explores only the reachable states necessary to find a winning strategy. This "just-in-time" exploration bypasses the traditional double-exponential bottleneck, allowing the tool to handle specifications that were previously unsolvable.

This iterative discovery is also central to SIMSAT, a tool by Azadeh Farzan and Zachary Kincaid. Instead of performing global quantifier elimination—which maps out the entire state space—they iteratively discover only the portions of the space needed to prove or disprove a formula.

Computing Transitions on the Fly

Even when the states themselves are manageable, the number of transitions (the edges between states) can explode. In classical planning, Cartesian abstractions are used to simplify problems, but the number of abstract transitions can become a memory bottleneck.

Jendrik Seipp addressed this in Efficiently Computing Transitions in Cartesian Abstractions by replacing explicit storage with on-demand computation. By using successor generators to compute edges only when needed, the solver can explore significantly larger and more complex domains without exhausting memory.

A similar optimization appears in Petri net model checking. Zhijun Ding and Cong He introduced lazy transition calculation in their tool EnPAC. While explicit-state checkers usually calculate all possible transitions for a state at once, EnPAC computes them one at a time. If a counterexample is found early in the search, the CPU cycles that would have been spent calculating the remaining transitions are saved.

Scaling to Stochastic and Noisy Data

The benefits of on-demand exploration extend into probabilistic realms. In the ARCH-COMP21 report, Alessandro Abate and co-authors highlight on-the-fly abstraction for stochastic hybrid systems. By calculating transition probabilities for Markov Decision Processes only when required during controller synthesis, researchers can verify high-dimensional systems that would be impossible to pre-compute.

Even in machine learning, Corinna Cortes and Mehryar Mohri utilized lazy automata evaluation to compute complex kernels for noisy sequence data. This ensures that only the necessary portions of a large transducer are materialized during the kernel evaluation process, making higher-order statistics computationally feasible.

Summary

The shift from eager to on-demand computation represents a fundamental change in how we handle complexity. By treating the state space as a dynamic frontier to be explored rather than a static object to be built, these researchers have turned the "curse of dimensionality" into a manageable search problem. The common thread is clear: when the map is too big to draw, only draw the parts where you are currently standing.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_on_demand_state_space_exploration_d44d543f,
  title = {On Demand State Space Exploration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/on-demand-state-space-exploration/rdr_d44d543f10914c5f86b1534a2373fa2b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_on_demand_state_space_exploration_d44d543f_v1,
  title = {On Demand State Space Exploration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/on-demand-state-space-exploration/rdr_d44d543f10914c5f86b1534a2373fa2b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}