# Subgoal Search For Complex Reasoning Tasks

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 78 references that are in the map.
- First posted on arXiv 25 Aug 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (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)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Generative Language Modeling for Automated Theorem Proving](https://mlsanity.com/paper/2009.03393/) (2020)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [Automatic Goal Generation for Reinforcement Learning Agents](https://mlsanity.com/paper/1705.06366/) (2017)
- [Semi-parametric Topological Memory for Navigation](https://mlsanity.com/paper/1803.00653/) (2018)
- [Planning with Goal-Conditioned Policies](https://mlsanity.com/paper/1911.08453/) (2019)
- [Imagination-Augmented Agents for Deep Reinforcement Learning](https://mlsanity.com/paper/1707.06203/) (2017)
- [Goal-Conditioned Reinforcement Learning with Imagined Subgoals](https://mlsanity.com/paper/2107.00541/) (2021)
- [Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learning](https://mlsanity.com/paper/2007.02832/) (2020)
- [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)
- [Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundary](https://mlsanity.com/paper/1705.00154/) (2017)
- [Learning Plannable Representations with Causal InfoGAN](https://mlsanity.com/paper/1807.09341/) (2018)
- [On the role of planning in model-based deep reinforcement learning](https://mlsanity.com/paper/2011.04021/) (2020)
- [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)
- [Learning from Trajectories via Subgoal Discovery](https://mlsanity.com/paper/1911.07224/) (2019)
- [Discovery of Options via Meta-Learned Subgoals](https://mlsanity.com/paper/2102.06741/) (2021)
- [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)
- [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, 21 of 21)

- [Formal Mathematics Statement Curriculum Learning](https://mlsanity.com/paper/2202.01344/) (2022)
- [Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2110.13625/) (2021)
- [Proving Theorems Recursively](https://mlsanity.com/paper/2405.14414/) (2024)
- [Hierarchical Imitation Learning with Vector Quantized Models](https://mlsanity.com/paper/2301.12962/) (2023)
- [Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search](https://mlsanity.com/paper/2206.00702/) (2022)
- [Flattening Hierarchies with Policy Bootstrapping](https://mlsanity.com/paper/2505.14975/) (2025)
- [Subgoal-Based Explanations for Unreliable Intelligent Decision Support Systems](https://mlsanity.com/paper/2201.04204/) (2022)
- [Hybrid Search for Efficient Planning with Completeness Guarantees](https://mlsanity.com/paper/2310.12819/) (2023)
- [Contrastive Representations for Temporal Reasoning](https://mlsanity.com/paper/2508.13113/) (2025)
- [Unifying Structure Reasoning and Language Model Pre-training for Complex Reasoning](https://mlsanity.com/paper/2301.08913/) (2023)
- [Consciousness-Inspired Spatio-Temporal Abstractions for Better Generalization in Reinforcement Learning](https://mlsanity.com/paper/2310.00229/) (2023)
- [OptionZero: Planning with Learned Options](https://mlsanity.com/paper/2502.16634/) (2025)
- [Generalizing to New Tasks via One-Shot Compositional Subgoals](https://mlsanity.com/paper/2205.07716/) (2022)
- [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)
- [Solving Sokoban using Hierarchical Reinforcement Learning with Landmarks](https://mlsanity.com/paper/2504.04366/) (2025)
- [Graph Value Iteration](https://mlsanity.com/paper/2209.09608/) (2022)
- [Multi-Task Option Learning and Discovery for Stochastic Path Planning](https://mlsanity.com/paper/2210.00068/) (2022)
- [Bidirectional-Reachable Hierarchical Reinforcement Learning with Mutually Responsive Policies](https://mlsanity.com/paper/2406.18053/) (2024)
- [DHP: Discrete Hierarchical Planning for Hierarchical Reinforcement Learning Agents](https://mlsanity.com/paper/2502.01956/) (2025)
- [Structure-Induced Information for Rerooting Levin Tree Search](https://mlsanity.com/paper/2605.30664/) (2026)

## Abstract (arXiv)

Humans excel in solving complex reasoning tasks through a mental process of moving from one idea to a related one. Inspired by this, we propose Subgoal Search (kSubS) method. Its key component is a learned subgoal generator that produces a diversity of subgoals that are both achievable and closer to the solution. Using subgoals reduces the search space and induces a high-level search graph suitable for efficient planning. In this paper, we implement kSubS using a transformer-based subgoal module coupled with the classical best-first search framework. We show that a simple approach of generating k-th step ahead subgoals is surprisingly efficient on three challenging domains: two popular puzzle games, Sokoban and the Rubik's Cube, and an inequality proving benchmark INT. kSubS achieves strong results including state-of-the-art on INT within a modest computational budget.