# Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 57 references that are in the map.
- First posted on arXiv 1 Jun 2022.

## Builds on (most cited first, 30 of 33)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning](https://mlsanity.com/paper/1910.10897/) (2019)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Multilingual Denoising Pre-training for Neural Machine Translation](https://mlsanity.com/paper/2001.08210/) (2020)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [RL2: Fast Reinforcement Learning via Slow Reinforcement Learning](https://mlsanity.com/paper/1611.02779/) (2016)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [Learning to reinforcement learn](https://mlsanity.com/paper/1611.05763/) (2016)
- [Semi-parametric Topological Memory for Navigation](https://mlsanity.com/paper/1803.00653/) (2018)
- [What Matters In On-Policy Reinforcement Learning? A Large-Scale Empirical Study](https://mlsanity.com/paper/2006.05990/) (2020)
- [Multi-task Deep Reinforcement Learning with PopArt](https://mlsanity.com/paper/1809.04474/) (2018)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [Hierarchical Foresight: Self-Supervised Learning of Long-Horizon Tasks via Visual Subgoal Generation](https://mlsanity.com/paper/1909.05829/) (2019)
- [World Model as a Graph: Learning Latent Landmarks for Planning](https://mlsanity.com/paper/2011.12491/) (2020)
- [An investigation of model-free planning](https://mlsanity.com/paper/1901.03559/) (2019)
- [Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictors](https://mlsanity.com/paper/2006.13205/) (2020)
- [Learning Plannable Representations with Causal InfoGAN](https://mlsanity.com/paper/1807.09341/) (2018)
- [INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving](https://mlsanity.com/paper/2007.02924/) (2020)
- [Variational Temporal Abstraction](https://mlsanity.com/paper/1910.00775/) (2019)
- [Time-Agnostic Prediction: Predicting Predictable Video Frames](https://mlsanity.com/paper/1808.07784/) (2018)
- [Sub-Goal Trees -- a Framework for Goal-Based Reinforcement Learning](https://mlsanity.com/paper/2002.12361/) (2020)
- [MuZero with Self-competition for Rate Control in VP9 Video Compression](https://mlsanity.com/paper/2202.06626/) (2022)
- [Hallucinative Topological Memory for Zero-Shot Visual Planning](https://mlsanity.com/paper/2002.12336/) (2020)
- [Dynamics Learning with Cascaded Variational Inference for Multi-Step Manipulation](https://mlsanity.com/paper/1910.13395/) (2019)
- [Subgoal Search For Complex Reasoning Tasks](https://mlsanity.com/paper/2108.11204/) (2021)
- [Intention-Net: Integrating Planning and Deep Learning for Goal-Directed Autonomous Navigation](https://mlsanity.com/paper/1710.05627/) (2017)
- [Keyframing the Future: Keyframe Discovery for Visual Prediction and Planning](https://mlsanity.com/paper/1904.05869/) (2019)

## Built on by (most cited first, 12 of 12)

- [Thought Cloning: Learning to Think while Acting by Imitating Human Thinking](https://mlsanity.com/paper/2306.00323/) (2023)
- [Double-Ended Synthesis Planning with Goal-Constrained Bidirectional Search](https://mlsanity.com/paper/2407.06334/) (2024)
- [PDE-Controller: LLMs for Autoformalization and Reasoning of PDEs](https://mlsanity.com/paper/2502.00963/) (2025)
- [Hierarchical Imitation Learning with Vector Quantized Models](https://mlsanity.com/paper/2301.12962/) (2023)
- [Flattening Hierarchies with Policy Bootstrapping](https://mlsanity.com/paper/2505.14975/) (2025)
- [Hybrid Search for Efficient Planning with Completeness Guarantees](https://mlsanity.com/paper/2310.12819/) (2023)
- [On the Theory of Risk-Aware Agents: Bridging Actor-Critic and Economics](https://mlsanity.com/paper/2310.19527/) (2023)
- [Contrastive Representations for Temporal Reasoning](https://mlsanity.com/paper/2508.13113/) (2025)
- [tsGT: Stochastic Time Series Modeling With Transformer](https://mlsanity.com/paper/2403.05713/) (2024)
- [What Matters in Hierarchical Search for Combinatorial Reasoning Problems?](https://mlsanity.com/paper/2406.03361/) (2024)
- [Subgoal-Guided Policy Heuristic Search with Learned Subgoals](https://mlsanity.com/paper/2506.07255/) (2025)
- [Structure-Induced Information for Rerooting Levin Tree Search](https://mlsanity.com/paper/2605.30664/) (2026)

## Abstract (arXiv)

Complex reasoning problems contain states that vary in the computational cost required to determine a good action plan. Taking advantage of this property, we propose Adaptive Subgoal Search (AdaSubS), a search method that adaptively adjusts the planning horizon. To this end, AdaSubS generates diverse sets of subgoals at different distances. A verification mechanism is employed to filter out unreachable subgoals swiftly, allowing to focus on feasible further subgoals. In this way, AdaSubS benefits from the efficiency of planning with longer subgoals and the fine control with the shorter ones, and thus scales well to difficult planning problems. We show that AdaSubS significantly surpasses hierarchical planning algorithms on three complex reasoning tasks: Sokoban, the Rubik's Cube, and inequality proving benchmark INT.