Memory Bounded Best First Search via Recursive Thresholding

18 concepts11 papers1 proposal

When solving complex optimization or inference problems, graph search algorithms typically fall into one of two extremes. On one side is Best-First Search (BFS), exemplified by algorithms like A*. BFS is highly node-efficient because it always expands the most promising path first based on a heuristic function. However, to guarantee this optimality, it must maintain an explicit search frontier (the OPEN list) containing every discovered but unvisited node. In large search spaces, this frontier grows exponentially, causing the algorithm to quickly exhaust all available RAM and crash.

On the other side are Depth-First Search (DFS) and Iterative Deepening A (IDA). These algorithms operate within strict, linear memory constraints because they only need to store the current path from the root to the active node. The penalty they pay is in time: because they discard the search graph as they go, they suffer from massive amounts of redundant node re-expansions, repeatedly traversing the same subtrees.

As noted by Kaindl et al., traditional search frameworks fail to adapt to the actual, finite memory capacities of modern hardware—they are hardcoded to use either minimal memory or unbounded memory. The research direction detailed here bridges this gap, creating a family of memory-adaptive algorithms that utilize every available byte of RAM to maximize search speed while strictly bounding memory consumption.

The Core Mechanism: Recursive Thresholding

How can an algorithm mimic the behavior of a global best-first search without maintaining a massive global priority queue? The solution is recursive thresholding.

Instead of a global OPEN list, the search is executed recursively down a single path, mimicking a depth-first traversal. However, the recursion is governed by a local cost threshold passed down the call stack. The algorithm explores a chosen branch as long as the estimated cost of that branch remains below the threshold.

      [Parent] (Heuristic updated to 15)
       /      \
  [Child A]  [Child B] (Cost: 15 -> Exceeds threshold of 12!)
  (Cost: 10)

When a child branch's cost exceeds the threshold, the recursion backtracks. Crucially, as the stack unwinds, the algorithm backs up the best alternative cost discovered among the children and updates the parent node's heuristic value. The parent node now remembers exactly how promising its best subtree actually is, allowing the algorithm to safely discard the explicit child nodes from memory. The next time the parent node is selected from a higher level, the search knows precisely when to switch to an alternative sibling branch.

An early realization of this hybrid approach was the MREC algorithm, introduced in Fast and further developed by Sen et al.. MREC allocates a fixed amount of memory to store a partial search graph. When memory is abundant, it caches nodes to completely avoid re-expansions (behaving like A); when memory is scarce, it performs virtual expansions and relies on recursive thresholding (behaving like IDA). Similarly, in game tree search, Bhattacharya et al. demonstrated that making the size of the priority queue a configurable parameter allows an algorithm to scale smoothly between the memory efficiency of Alpha-Beta and the node efficiency of SSS*.

Managing Memory via Pruning and Re-Expansion

When an algorithm runs out of its allocated memory allocation mid-search, it must gracefully degrade rather than crash. It achieves this through a strategy of selective pruning and re-expansion.

When a strict memory threshold is reached, the algorithm identifies low-priority nodes currently stored in memory and purges them. Because the backed-up heuristic values remain preserved in the ancestor nodes higher up the tree, the algorithm does not lose the global context of where the optimal solution lies. If alternative paths turn out to be worse than expected, the search will naturally return to the pruned ancestor, triggering a re-expansion of the discarded subtree.

Lou et al. utilized this mechanism to create an "anytime, anyspace" framework. By dynamically pruning low-priority nodes when memory limits are reached and re-expanding them only if they become relevant later, the algorithm provides increasingly tight bounds over time while operating reliably within any arbitrary hardware constraint.

Scaling to Complex Graphical Models

The power of recursive best-first search is vividly demonstrated in solving Marginal Maximum a Posteriori (Marginal MAP or MMAP) problems within graphical models. MMAP tasks are notoriously difficult because they require alternating between maximization (finding the most likely assignment) and summation (marginalizing out nuisance variables). This structure creates massive, high-induced-width search spaces where standard best-first solvers immediately run out of memory.

To solve this, researchers adapted recursive thresholding to AND/OR search spaces, where AND nodes represent independent subproblems and OR nodes represent variable choices. Marinescu et al. introduced recursive best-first search variants that use local threshold control to manage memory consumption, achieving the efficiency of best-first exploration within stable, linear space constraints.

Building on this, Lee et al. introduced weighted recursive best-first search (WRBFAOO), which applies heuristic weights to provide rapid, high-quality anytime solutions with guaranteed suboptimality bounds. As synthesized by Marinescu 0002 et al. and refined in the RBFAOO+ algorithm by Marinescu et al., these recursive thresholding strategies allow solvers to reliably prove optimality on complex graphical models that would otherwise cause traditional solvers to stall or crash.

Parallelism and Dynamic Scheduling

The philosophy of memory-adaptive search also extends to parallel and distributed computing, where memory bottlenecks are frequently exacerbated by concurrent execution and explosive intermediate data generation.

In multi-core environments, Kishimoto et al. designed a parallel recursive best-first search (SPRBFAOO). It coordinates multiple threads using a concept called "virtual q-values" to guide threshold-based exploration concurrently. This allows the system to leverage the processing power of multi-core CPUs while maintaining the low memory footprint inherent to recursive thresholding.

At the massive scale of distributed systems, such as during subgraph enumeration in giant graphs, the challenge shifts from managing a search tree to managing intermediate results. Yang et al. addressed this by designing an adaptive scheduler that dynamically switches between breadth-first and depth-first scheduling. The system defaults to breadth-first search to maximize parallelism and CPU utilization. However, the moment intermediate results threaten to exhaust system memory, the scheduler dynamically switches to depth-first execution. This shifts the system's priority from generating new tasks to consuming existing ones, effectively bounding the memory footprint during explosive search phases.

Key Foundational Work

Fast Recursive Formulations for Best-First Search That Allow Controlled Use of Memory (1989) — contributed 3 concept elements to this direction.
Making Best Use of Available Memory When Searching Game Trees (1986) — contributed 2 concept elements to this direction.
Fast Recursive Formulations for Best-First Search That Allow Controlled Use of Memory (1989) — 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_recursive_best_first_search_a4436659,
  title = {recursive best-first search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-best-first-search/rdr_a4436659520a4afaadcf72275ef42d92},
  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_recursive_best_first_search_a4436659_v1,
  title = {recursive best-first search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/recursive-best-first-search/rdr_a4436659520a4afaadcf72275ef42d92/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