mlsanityData to 7 Oct 2026

Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping

arXiv 2402.14083 ↗First posted 21 Feb 2024cs.AIcited by 89

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

While Transformers have enabled tremendous progress in various application settings, such architectures still trail behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks. This is accomplished by training an encoder-decoder Transformer model to predict the search dynamics of the A^* search algorithm. We fine tune this model to obtain a Searchformer, a Transformer model that optimally solves previously unseen Sokoban puzzles 93.7% of the time, while using up to 26.8% fewer search steps than the A^* implementation that was used for training initially. In our training method, A^*'s search dynamics are expressed as a token sequence outlining when task states are added and removed into the search tree during symbolic planning. Searchformer significantly outperforms baselines that predict the optimal plan directly with a 5-10× smaller model size and a 10× smaller training dataset. Lastly, we demonstrate how Searchformer scales to larger and more complex decision making tasks with improved percentage of solved tasks and shortened search dynamics.

Key facts. Cited by 89 papers in the map (data through 7 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 32 of its 52 references that are in the map. First posted on arXiv 21 Feb 2024.

Builds on

32 of 52 references.

Closest ancestors · 1

Same direction, newest first

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 31

  1. 2017Attention Is All You Needcited by 59,932
  2. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,456
  3. 2022Training language models to follow instructions with human feedbackcited by 15,712
  4. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  5. 2023DINOv2: Learning Robust Visual Features without Supervisioncited by 7,764
  6. 2021Emerging Properties in Self-Supervised Vision Transformerscited by 6,893
  7. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  8. 2023Code Llama: Open Foundation Models for Codecited by 2,105
  9. 2022Make-A-Video: Text-to-Video Generation without Text-Video Datacited by 1,725
  10. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
  11. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  12. 2023Self-Supervised Learning from Images with a Joint-Embedding Predictive Architecturecited by 982
19 more
  1. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  2. 2023Extending Context Window of Large Language Models via Positional Interpolationcited by 721
  3. 2021Offline Reinforcement Learning as One Big Sequence Modeling Problemcited by 636
  4. 2014Neural Turing Machinescited by 630
  5. 2023YaRN: Efficient Context Window Extension of Large Language Modelscited by 584
  6. 2023A Survey of Reinforcement Learning from Human Feedbackcited by 259
  7. 2023Emu Video: Factorizing Text-to-Video Generation by Explicit Image Conditioningcited by 254
  8. 2022BlenderBot 3: a deployed conversational agent that continually learns to responsibly engagecited by 197
  9. 2022In-context Reinforcement Learning with Algorithm Distillationcited by 186
  10. 2022Deep Hierarchical Planning from Pixelscited by 96
  11. 2018Lipschitz Continuity in Model-based Reinforcement Learningcited by 90
  12. 2023On the Planning Abilities of Large Language Models (A Critical Investigation with a Proposed Benchmark)cited by 85
  13. 2023Evaluating Cognitive Maps and Planning in Large Language Models with CogEvalcited by 77
  14. 2019Bayesian Relational Memory for Semantic Visual Navigationcited by 48
  15. 2017Making Neural Programming Architectures Generalize via Recursioncited by 35
  16. 2018Learning to Search with MCTSnetscited by 32
  17. 2022Chain of Thought Imitation with Procedure Cloningcited by 30
  18. 2022Reward-Respecting Subtasks for Model-Based Reinforcement Learningcited by 15
  19. 2020Addressing Some Limitations of Transformers with Feedback Memorycited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 27; 2025: 43; 2026: 19.

89 papers.

Sort:

By area:

  1. 2024Training Large Language Models to Reason in a Continuous Latent Spacecited by 763
  2. 2025Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRscited by 373
  3. 2024From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Stepcited by 225
  4. 2025Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusionscited by 208
  5. 2024Agent Q: Advanced Reasoning and Learning for Autonomous AI Agentscited by 201
  6. 2025Hierarchical Reasoning Modelcited by 167
  7. 2024Recursive Introspection: Teaching Language Model Agents How to Self-Improvecited by 162
  8. 2024Stream of Search (SoS): Learning to Search in Languagecited by 141
  9. 2024Stop Regressing: Training Value Functions via Classification for Scalable Deep RLcited by 136
  10. 2024From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Modelscited by 136
  11. 2024Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planningcited by 135
  12. 2025Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuningcited by 121
38 more
  1. 2025Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thoughtcited by 108
  2. 2025Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoningcited by 87
  3. 2024Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Modelscited by 86
  4. 2025PlanGenLLMs: A Modern Survey of LLM Planning Capabilitiescited by 82
  5. 2025Scaling Test-Time Compute Without Verification or RL is Suboptimalcited by 82
  6. 2025Learning to Plan & Reason for Evaluation with Thinking-LLM-as-a-Judgecited by 75
  7. 2025A Survey on Large Language Models for Mathematical Reasoningcited by 52
  8. 2024Scaling of Search and Learning: A Roadmap to Reproduce o1 from Reinforcement Learning Perspectivecited by 49
  9. 2024Thinking LLMs: General Instruction Following with Thought Generationcited by 45
  10. 2025Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokenscited by 41
  11. 2024Dualformer: Controllable Fast and Slow Thinking by Learning with Randomized Reasoning Tracescited by 40
  12. 2025Large Language Models for Planning: A Comprehensive and Systematic Surveycited by 38
  13. 2025Less is More: Recursive Reasoning with Tiny Networkscited by 38
  14. 2025Position: Stop Anthropomorphizing Intermediate Tokens as Reasoning/Thinking Traces!cited by 36
  15. 2024System-1.x: Learning to Balance Fast and Slow Planning with Language Modelscited by 35
  16. 2024Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzlescited by 35
  17. 2024Intelligent Go-Explore: Standing on the Shoulders of Giant Foundation Modelscited by 32
  18. 2025Robotouille: An Asynchronous Planning Benchmark for LLM Agentscited by 31
  19. 2024Exploring and Benchmarking the Planning Capabilities of Large Language Modelscited by 19
  20. 2025Stepwise Guided Policy Optimization: Coloring your Incorrect Reasoning in GRPOcited by 18
  21. 2026Vision-aligned Latent Reasoning for Multi-modal Large Language Modelcited by 16
  22. 2025BoxingGym: Benchmarking Progress in Automated Experimental Design and Model Discoverycited by 15
  23. 2025Generative AI Act II: Test Time Scaling Drives Cognition Engineeringcited by 14
  24. 2025LongPerceptualThoughts: Distilling System-2 Reasoning for System-1 Perceptioncited by 14
  25. 2025Self-Steering Language Modelscited by 13
  26. 2025GaLore 2: Large-Scale LLM Pre-Training by Gradient Low-Rank Projectioncited by 13
  27. 2025How Much Backtracking is Enough? Exploring the Interplay of SFT and RL in Enhancing LLM Reasoningcited by 13
  28. 2024UniZero: Generalized and Efficient Planning with Scalable Latent World Modelscited by 12
  29. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 12
  30. 2026Equilibrium Reasoners: Learning Attractors Enables Scalable Reasoningcited by 12
  31. 2024Transformers Can Navigate Mazes With Multi-Step Predictioncited by 11
  32. 2025A Survey of Large Language Model-Powered Spatial Intelligence Across Scales: Advances in Embodied Agents, Smart Cities, and Earth Sciencecited by 11
  33. 2025ASTRO: Teaching Language Models to Reason by Reflecting and Backtracking In-Contextcited by 10
  34. 2024LASP: Surveying the State-of-the-Art in Large Language Model-Assisted AI Planningcited by 9
  35. 2025GraphThought: Graph Combinatorial Optimization with Thought Generationcited by 9
  36. 2025Performative Thinking? The Brittle Correlation Between CoT Length and Problem Complexitycited by 9
  37. 2025Should You Use Your Large Language Model to Explore or Exploit?cited by 8
  38. 2025Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoningcited by 8

50 most cited of 89 All 89 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2025From Next Token Prediction to (STRIPS) World Models
  2. 2026Planning with Transformers: Chain of Computation and Structured Context Windows
  3. 2026On Sample-Efficient Generalized Planning via Learned Transition Models
  4. 2024Transformers Struggle to Learn to Search
  5. 2026Can Transformers Learn to Verify During Backtracking Search?
  6. 2026Agentic Transformers Provably Learn to Search via Reinforcement Learning
  7. 2024Amortized Planning with Large-Scale Transformers: A Case Study on Chess
  8. 2025SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search