In the classic A* search algorithm, expanding a node is an "all-or-nothing" operation. When the algorithm visits a state, it generates every single one of its children and places them into the priority queue (the Open list). While this ensures completeness, it creates a massive memory bottleneck in problems with high branching factors—where a single state might have thousands or even millions of successors.
A growing body of research suggests a more surgical approach: Partial Expansion. Instead of materializing the entire frontier at once, these algorithms generate successors lazily, storing only the most promising nodes and deferring the rest until they are actually needed.
The Memory Wall of Successor Generation
The primary motivation for partial expansion is the "branching factor explosion." In domains like Multiple Sequence Alignment or multi-agent planning, the number of successors for a single node can be astronomically large. As Matthew Hatem and Wheeler Ruml demonstrate in External Memory Best-First Search for Multiple Sequence Alignment, standard A* quickly exhausts RAM because it stores "surplus" nodes—children that have such high heuristic costs they will likely never be expanded.
To solve this, Hatem and others developed Partial Expansion A (PEA). The intuition is simple: when expanding a node, only generate the children whose total estimated cost ($f$-value) is equal to the parent's $f$-value. The "surplus" children are discarded for now, but the parent is re-inserted into the Open list with a new priority based on its best unexpanded child. This keeps the search frontier lean, allowing the algorithm to explore deeper into the state space before hitting memory limits.
Just-in-Time Expansion
While PEA uses cost thresholds to filter children, other researchers have moved toward Incremental Expansion*, where children are generated one by one.
In Scaling Up Optimal Heuristic Search in Dec-POMDPs via Incremental Expansion, Matthijs T. J. Spaan, Christopher Amato, and Frans A. Oliehoek introduce GMAA*-ICE. Instead of expanding all children, they use "placeholders" in the search queue. Only the single most promising child is materialized; the rest remain as a single abstract entry in the priority queue. This "just-in-time" approach allows the search to handle the doubly exponential growth of multi-agent decision trees by focusing computational effort only on the most relevant branches.
A similar logic applies to pathfinding in continuous or dense spaces. Keisuke Okumura introduces LaCAS* in Pathfinding with Lazy Successor Generation, which uses a k-d tree to retrieve only the nearest unchecked neighbors as needed. By batching successor generation, the algorithm finds initial solutions rapidly and refines them over time, avoiding the overhead of validating thousands of edges that the optimal path will never use.
Lazy Trees and Monadic Abstractions
The idea of "only computing what you need" is naturally expressed through lazy evaluation. Peter J. Stuckey, Tom Schrijvers, and Philip Wadler formalize this in Monadic constraint programming. By representing a search space as a lazy monadic tree, the search engine only instantiates the portions of the tree that the search strategy actually visits. This decouples the definition of the search space from the execution of the search, ensuring that memory is only consumed for explored states.
This lazy philosophy extends to complex linguistic structures as well. Philipp Koehn, Alon Lavie, and Kenneth Heafield applied this to machine translation hypergraphs in Grouping Language Model Boundary Words to Speed K-Best Extraction from Hypergraphs. By grouping hypotheses and expanding them lazily, they avoid building exhaustive representations of translation spaces that are never visited by the extraction algorithm.
Balancing Memory and Re-computation
The trade-off for saving memory is often an increase in computation. If an algorithm discards a child node and later needs it, it must "re-expand" the parent.
Meir Goldenberg, Nathan R. Sturtevant, and colleagues addressed this in Optimal-Generation Variants of EPEA. They introduced OGA (Optimal Generation A), proving that it is possible to be optimal not just in the number of nodes expanded, but also in the number of nodes generated. By carefully managing how parents are re-inserted into the priority queue, OGA* ensures that no "surplus" node is ever created, effectively minimizing the computational overhead of the partial expansion strategy.
This lineage of work—from early hybrids like ITS by Subrata Ghosh and Ambuj Mahanti (ITS: An Efficient Limited-Memory Heuristic Tree Search Algorithm) to modern hybrid algorithms like PEA+IDA (André Grahl Pereira and Frederico Messa, PEA+IDA: An Improved Hybrid Memory-Restricted Algorithm)—demonstrates that the key to scaling search isn't just faster hardware, but a more disciplined approach to what we choose to remember.