Structure-Induced Information for Rerooting Levin Tree Search

Jake Tuero, Michael Buro, Laurent Orseau, Levi H. S. Lelis

TL;DR

Policy-guided tree search often relies on explicit subgoal generation to solve complex planning problems, which introduces heavy computational overhead and modeling brittleness. This paper introduces automated "rerooter" designs for the $\sqrt{\text{LTS}}$ algorithm that implicitly decompose problems into soft subtasks using global clustering and local heuristics. The resulting hybrid approach achieves state-of-the-art online training efficiency and scales robustly to complex environments where explicit subgoal methods fail.

What Problem Does This Paper Address?

Planning in complex discrete environments requires balancing exploration and exploitation. Algorithms like Levin Tree Search (LTS) use learned policies to guide search but struggle without structural guidance in vast state spaces.

A common way to scale these methods is to decompose the problem into easier subtasks by explicitly generating intermediate subgoals (e.g., predicting future states). However, this introduces massive computational overhead (such as running neural network subgoal generators) and makes the search brittle: if the subgoal generator fails or gets distracted by task-irrelevant details in the environment, the entire planning pipeline collapses. This paper addresses the challenge of exploiting state-space structure implicitly, capturing the benefits of subtask decomposition without the heavy baggage of explicit subgoal reconstruction.

Methods

The authors build on $\sqrt{\text{LTS}}$ (root-LTS), an algorithm that implicitly starts a new search at every node in the tree, distributing computational effort based on a "rerooter" weight ($w_t$). They propose three automated ways to compute these weights from structure already present in the search tree:

  1. Global Structure ($\sqrt{\text{LTS}}\text{-L}$): This variant dynamically builds a graph of the state space during search and applies the Leiden clustering algorithm. Nodes in smaller or newly discovered clusters get higher weights to encourage exploration across broader regions.
  2. Local Structure ($\sqrt{\text{LTS}}\text{-H}$): This variant uses a learned heuristic function to scale weights exponentially based on estimated proximity to the goal relative to the root.
  3. Hybrid ($\sqrt{\text{LTS}}\text{-LH}$): This approach additively combines both global clustering and local heuristic signals, providing a coarse-to-fine search control mechanism.
Figure 1. √

The authors also provide a new theoretical bound proving that $\sqrt{\text{LTS}}$ can effectively leverage the synergies of multiple additive rerooters without one dominating and degrading the search.

Datasets

The methods are evaluated using online bootstrap training across four challenging discrete planning domains:

  • BoulderDash: A game where the agent collects diamonds and keys. The authors vary the percentage of task-irrelevant "dirt" tiles (from 10% to 50%) to test complexity scaling.
  • CraftWorld: A recipe-crafting environment with strict deadlock conditions.
  • Sokoban: The classic box-pushing puzzle, utilizing problems from the Boxoban dataset.
  • TSP (GridWorld): A modified Traveling Salesman Problem where revisiting a city causes an immediate deadlock.

Key Insights and Ideas

  • Implicit Beats Explicit: You don't need to reconstruct what a subgoal looks like to benefit from subtask decomposition. Shifting the root of the search tree based on structural cues provides the same benefits with a fraction of the compute.
  • The Vulnerability of Visual Subgoals: Subgoal-generating models (like VQ-VAEs) are easily distracted by task-irrelevant visual clutter (like dirt in BoulderDash). As clutter increases, subgoal generation degrades rapidly, causing explicit methods to fail.
  • Synergy of Local & Global: Heuristics provide excellent goal-directed drive but can be noisy or miscalibrated in deadlocks. Clustering provides stable, coarse structural boundaries but lacks goal awareness. Combining them additively allows the search to fall back on whichever signal is more informative in that region of the tree.

Key Results

  • Training Efficiency: The hybrid method ($\sqrt{\text{LTS}}\text{-LH}$) consistently outperformed standard LTS and subgoal-based baselines (SGPS) in bootstrap training efficiency across all domains, often by orders of magnitude in wall-clock time.
Figure 2. Average online training loss with respect to expansions (top) and time (bottom), in log-scale. Shaded regions show the minimum and maximum. Time measures the sum an algorithm spends on each problem across all threads used during training.
  • Robustness to Complexity: In the BoulderDash scaling experiment, the subgoal baseline ($\text{PHS}^*(\pi^{\text{SG}})$) completely timed out and failed when task-irrelevant dirt reached 30% or more. In contrast, $\sqrt{\text{LTS}}\text{-LH}$ and $\sqrt{\text{LTS}}\text{-H}$ remained highly robust, successfully completing training even at 50% dirt.
  • Test Performance: Despite training much faster, the rerooting methods achieved comparable or superior solution lengths and success rates on held-out test sets, proving that efficiency gains do not come at the expense of policy quality.
Table 1. Test results averaged over all seeds. Time measures the sum an algorithm spends on each problem across all threads used during training, in seconds.

Limitations and Future Work

  • Dependence on Clustering Quality: The clustering-based rerooter ($\sqrt{\text{LTS}}\text{-L}$) performs poorly in environments with weak or poorly separated state-space clustering structures (like TSP or Sokoban), where the number of edges crossing cluster boundaries is high.
  • Heuristic Temperature Sensitivity: The local heuristic rerooter relies on an inverse-temperature hyperparameter ($\alpha$). If $\alpha$ is too large, the search can overcommit to deadlocked subtrees that superficially look like progress.
  • Future Directions: The authors suggest exploring alternative ways to derive side information for defining rerooters, and extending the framework to non-deterministic or continuous domains.

Summary updated

Abstract

Subgoal-based policy tree search, which uses a policy to guide search, is effective for complex single-agent deterministic problems but often relies on explicit subgoal generation that can incur substantial overhead and hinders scalability. In this paper, we overcome these limitations by using a learned ``rerooter'' through the recently-introduced $\sqrt{\text{LTS}}$ algorithm. A rerooter implicitly decomposes the problem into soft subtasks. While previous work focused on the formal guarantees for given or handcrafted rerooters, in this work we propose three rerooter designs: (i) a clustering-based rerooter that exploits global state-space structure, (ii) a heuristic-based rerooter that leverages learned cost-to-go estimates, and (iii) a hybrid that combines both signals. Our framework avoids having to explicitly reconstruct and reason over generated subgoals, thereby enabling scalable allocation of search effort with significantly lower computational overhead. Empirically, our rerooting-based methods scale to complex environments where subgoal-based policy tree search fails, and achieve state-of-the-art online training efficiency on the domains tested.
BibTeX
@inproceedings{tuero2026structure,
  author = {Jake Tuero and Michael Buro and Laurent Orseau and Levi H. S. Lelis},
  title = {{Structure-Induced Information for Rerooting Levin Tree Search}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=195EfI9ae5},
}
Figure