When solving complex planning, pathfinding, or formal verification problems, algorithms inevitably collide with a fundamental bottleneck: the memory wall. Whether navigating a robot, optimizing a game strategy, or verifying a hardware circuit, the state space of the problem scales exponentially with the number of variables involved.
To avoid redundant work and infinite loops, standard search algorithms like A* or Value Iteration must remember where they have been. However, storing every visited state or precomputing perfect look-up tables quickly exhausts physical RAM, causing systems to crash or stall.
To scale search algorithms to real-world problems, researchers have developed techniques that trade a small amount of computational time or heuristic precision for massive reductions in memory usage. This article explores the core insights behind these memory-constrained search strategies.
Localizing Duplicate Detection for External Storage
The most direct cause of memory exhaustion in graph search is duplicate detection. To prevent an algorithm from re-exploring the same state via different paths (transpositions), it typically maintains a "Closed List" of all visited states in RAM. When the state space exceeds available RAM, the search must rely on secondary storage (like hard drives), which introduces devastating latency penalties for random lookups.
The core intuition for bypassing this bottleneck is localization: if we can predict or structure the order in which states are visited, we can check for duplicates in batches or restrict our active RAM usage to a tiny fraction of the graph.
Delayed Duplicate Detection
Instead of checking every newly generated state against a massive hash table in real time, Korf introduced Delayed Duplicate Detection (DDD). The algorithm allows the search to generate duplicate states blindly, writing them sequentially to disk. Periodically, the algorithm performs a large-scale sequential sort on the disk file, which naturally groups identical states together, allowing duplicates to be purged in a single, highly efficient pass. This shifts the bottleneck from random-access RAM latency to sequential disk I/O bandwidth.
Structured Duplicate Detection
Taking localization a step further, Zhou et al. proposed Structured Duplicate Detection (SDD). By using a high-level state-space abstraction to partition the search graph into localized blocks, the algorithm maps out which abstract states are adjacent to one another.
[ Abstract State A ] <---> [ Abstract State B ]
| |
(Local Block A) (Local Block B)
[In RAM: Active] [On Disk: Cached]
When searching within Local Block A, the algorithm knows it can only transition to states within Block A or its immediate neighbor, Block B. Therefore, only the visited states belonging to these active blocks need to reside in RAM; the rest of the closed list can be safely cached on disk without risking undetected duplicates.
Compressing and Abstracting Heuristic Guidance
Another major consumer of memory is the guidance system itself. High-quality search heuristics often rely on Pattern Databases (PDBs)—precomputed lookup tables that store the exact distances to a goal for simplified subproblems. As Zhou et al. observe, large or highly detailed subproblems create tables so massive that they cannot fit into a single system's memory.
The key insight here is that imperfect guidance in RAM is vastly superior to perfect guidance on disk. If a planner must fetch a heuristic value from disk, the latency penalty outweighs the benefit of the more accurate estimate.
To resolve this, Felner et al. demonstrated that PDBs can be aggressively compressed by merging adjacent, highly correlated entries. While this lossy compression introduces small errors into the heuristic estimates, keeping the entire database within RAM yields search speedups of up to three orders of magnitude by completely avoiding disk swapping.
When explicit abstractions become too memory-intensive to construct, planners must find alternative representations. As Katz et al. note, traditional planning heuristics often hit a dimensionality bottleneck where only a small number of variables can be explicitly mapped. This has driven the development of implicit or algebraic representations—such as using arithmetic circuits or binary decision diagrams—to compress state spaces symbolically rather than enumerating them explicitly.
Bounded Caching and Partial Representations
In domains like probabilistic planning or classical planning with massive numbers of objects, even representing the initial problem structure or caching every subproblem can cause immediate memory failure.
Bounded Caching over Full Memoization
When solving probabilistic planning problems, algorithms often use full memoization to avoid re-solving identical subproblems across long planning horizons. However, this quickly hits a memory wall. Littman et al. proved that replacing full memoization with bounded caching—such as using a Least Recently Used (LRU) eviction policy or difficulty-based heuristics—allows solvers to extend their planning horizons significantly. By capping the maximum memory allocation, the solver focuses its resources on the most relevant or frequent subproblems without risking a system crash.
Partial Grounding
In classical planning, a major bottleneck occurs during the preprocessing phase, where abstract operators are translated into concrete actions (grounding). In complex environments, the fully grounded representation is simply too large for RAM.
To combat this, Gnad et al. introduced partial grounding. Instead of instantiating every possible interaction upfront, the authors leverage machine learning to predict which actions are highly likely to belong to an optimal plan. The planner then grounds only that vital subset, allowing it to successfully initiate and complete searches on massive problem instances that would otherwise fail before the search even began.
Collapsing Trees into Graphs
Memory inefficiencies also stem from how algorithms represent the history of a search. In tree-based search frameworks (such as standard Monte-Carlo Tree Search or open-loop planning), identical states reached via different sequences of actions are treated as entirely distinct nodes.
Tree Search (Duplicate Data):
(Root) -> (Action A) -> [State X: Stores Policy/Value]
-> (Action B) -> [State X: Stores Duplicate Policy/Value]
Graph Search (Shared Data):
(Root) -> (Action A) --\
-> (Action B) ----> [State X: Stores Single Policy/Value]
When nodes store high-dimensional data—such as policy distributions or value vectors—this duplication causes rapid memory exhaustion. As highlighted by recent advancements in graph-based search architectures, transitioning from a tree representation to a directed acyclic graph (DAG) naturally collapses these transpositions. By forcing paths that arrive at the same physical state to point to a single shared node, the algorithm eliminates redundant data structures, allowing deeper and more comprehensive exploration within the same hardware memory constraints.