# Structure-Induced Information for Rerooting Levin Tree Search

arXiv: https://arxiv.org/abs/2605.30664 · HTML: https://mlsanity.com/paper/2605.30664/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 38 references that are in the map.
- First posted on arXiv 28 May 2026.

## Builds on (most cited first, 21 of 21)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [An investigation of model-free planning](https://mlsanity.com/paper/1901.03559/) (2019)
- [Successor Options: An Option Discovery Framework for Reinforcement Learning](https://mlsanity.com/paper/1905.05731/) (2019)
- [Single-Agent Policy Tree Search With Guarantees](https://mlsanity.com/paper/1811.10928/) (2018)
- [Subgoal Search For Complex Reasoning Tasks](https://mlsanity.com/paper/2108.11204/) (2021)
- [Policy-Guided Heuristic Search with Guarantees](https://mlsanity.com/paper/2103.11505/) (2021)
- [Humans decompose tasks by trading off utility and computational cost](https://mlsanity.com/paper/2211.03890/) (2022)
- [Hierarchical Imitation Learning with Vector Quantized Models](https://mlsanity.com/paper/2301.12962/) (2023)
- [Hierarchical State Abstraction Based on Structural Information Principles](https://mlsanity.com/paper/2304.12000/) (2023)
- [Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search](https://mlsanity.com/paper/2206.00702/) (2022)
- [Hybrid Search for Efficient Planning with Completeness Guarantees](https://mlsanity.com/paper/2310.12819/) (2023)
- [Creating Multi-Level Skill Hierarchies in Reinforcement Learning](https://mlsanity.com/paper/2306.09980/) (2023)
- [Hierarchical Decision Making Based on Structural Information Principles](https://mlsanity.com/paper/2404.09760/) (2024)
- [GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting](https://mlsanity.com/paper/2312.13936/) (2023)
- [Memory-Efficient Episodic Control Reinforcement Learning with Dynamic Online k-means](https://mlsanity.com/paper/1911.09560/) (2019)
- [Exponential Speedups by Rerooting Levin Tree Search](https://mlsanity.com/paper/2412.05196/) (2024)
- [Subgoal-Guided Policy Heuristic Search with Learned Subgoals](https://mlsanity.com/paper/2506.07255/) (2025)

## Abstract (arXiv)

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 √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.