mlsanityData to 14 Oct 2026

Subgoal Search For Complex Reasoning Tasks

arXiv 2108.11204 ↗First posted 25 Aug 2021cs.AI cs.LGcited by 21

Not on the map. Why?

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.

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

32 of 78 references.

References · 32

  1. 2017Attention Is All You Needcited by 60,361
  2. 2019HuggingFace's Transformers: State-of-the-art Natural Language Processingcited by 2,218
  3. 2017Hindsight Experience Replaycited by 1,136
  4. 2020Multilingual Denoising Pre-training for Neural Machine Translationcited by 1,035
  5. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  6. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  7. 2020Generative Language Modeling for Automated Theorem Provingcited by 388
  8. 2017FeUdal Networks for Hierarchical Reinforcement Learningcited by 337
  9. 2017Automatic Goal Generation for Reinforcement Learning Agentscited by 259
  10. 2018Semi-parametric Topological Memory for Navigationcited by 209
  11. 2019Planning with Goal-Conditioned Policiescited by 149
  12. 2017Imagination-Augmented Agents for Deep Reinforcement Learningcited by 140
20 more
  1. 2021Goal-Conditioned Reinforcement Learning with Imagined Subgoalscited by 134
  2. 2020Maximum Entropy Gain Exploration for Long Horizon Multi-goal Reinforcement Learningcited by 102
  3. 2019Hierarchical Foresight: Self-Supervised Learning of Long-Horizon Tasks via Visual Subgoal Generationcited by 83
  4. 2020World Model as a Graph: Learning Latent Landmarks for Planningcited by 69
  5. 2019An investigation of model-free planningcited by 66
  6. 2020Long-Horizon Visual Planning with Goal-Conditioned Hierarchical Predictorscited by 62
  7. 2017Classical Planning in Deep Latent Space: Bridging the Subsymbolic-Symbolic Boundarycited by 58
  8. 2018Learning Plannable Representations with Causal InfoGANcited by 57
  9. 2020On the role of planning in model-based deep reinforcement learningcited by 57
  10. 2020INT: An Inequality Benchmark for Evaluating Generalization in Theorem Provingcited by 44
  11. 2019Variational Temporal Abstractioncited by 38
  12. 2018Time-Agnostic Prediction: Predicting Predictable Video Framescited by 37
  13. 2019Learning from Trajectories via Subgoal Discoverycited by 28
  14. 2021Discovery of Options via Meta-Learned Subgoalscited by 27
  15. 2020Hallucinative Topological Memory for Zero-Shot Visual Planningcited by 25
  16. 2019Dynamics Learning with Cascaded Variational Inference for Multi-Step Manipulationcited by 24
  17. 2017Intention-Net: Integrating Planning and Deep Learning for Goal-Directed Autonomous Navigationcited by 20
  18. 2019Keyframing the Future: Keyframe Discovery for Visual Prediction and Planningcited by 20
  19. 2020Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planningcited by 19
  20. 2019Uncertainty-sensitive Learning and Planning with Ensemblescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 6; 2023: 4; 2024: 4; 2025: 5; 2026: 1.

21 papers.

Sort:

By area:

  1. 2022Formal Mathematics Statement Curriculum Learningcited by 142
  2. 2021Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learningcited by 47
  3. 2024Proving Theorems Recursivelycited by 26
  4. 2023Hierarchical Imitation Learning with Vector Quantized Modelscited by 15
  5. 2022Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Searchcited by 12
  6. 2025Flattening Hierarchies with Policy Bootstrappingcited by 11
  7. 2022Subgoal-Based Explanations for Unreliable Intelligent Decision Support Systemscited by 6
  8. 2023Hybrid Search for Efficient Planning with Completeness Guaranteescited by 6
  9. 2025Contrastive Representations for Temporal Reasoningcited by 6
  10. 2023Unifying Structure Reasoning and Language Model Pre-training for Complex Reasoningcited by 4
  11. 2023Consciousness-Inspired Spatio-Temporal Abstractions for Better Generalization in Reinforcement Learningcited by 4
  12. 2025OptionZero: Planning with Learned Optionscited by 2
9 more
  1. 2022Generalizing to New Tasks via One-Shot Compositional Subgoalscited by 1
  2. 2024tsGT: Stochastic Time Series Modeling With Transformercited by 1
  3. 2024What Matters in Hierarchical Search for Combinatorial Reasoning Problems?cited by 1
  4. 2025Solving Sokoban using Hierarchical Reinforcement Learning with Landmarkscited by 1
  5. 2022Graph Value Iterationcited by 0
  6. 2022Multi-Task Option Learning and Discovery for Stochastic Path Planningcited by 0
  7. 2024Bidirectional-Reachable Hierarchical Reinforcement Learning with Mutually Responsive Policiescited by 0
  8. 2025DHP: Discrete Hierarchical Planning for Hierarchical Reinforcement Learning Agentscited by 0
  9. 2026Structure-Induced Information for Rerooting Levin Tree Searchcited by 0