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

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

## Key facts

- Cited by 90 papers in the map (data through 14 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.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [DINOv2: Learning Robust Visual Features without Supervision](https://mlsanity.com/paper/2304.07193/) (2023)
- [Emerging Properties in Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.14294/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Make-A-Video: Text-to-Video Generation without Text-Video Data](https://mlsanity.com/paper/2209.14792/) (2022)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Self-Supervised Learning from Images with a Joint-Embedding Predictive Architecture](https://mlsanity.com/paper/2301.08243/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Extending Context Window of Large Language Models via Positional Interpolation](https://mlsanity.com/paper/2306.15595/) (2023)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Offline Reinforcement Learning as One Big Sequence Modeling Problem](https://mlsanity.com/paper/2106.02039/) (2021)
- [YaRN: Efficient Context Window Extension of Large Language Models](https://mlsanity.com/paper/2309.00071/) (2023)
- [A Survey of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2312.14925/) (2023)
- [Emu Video: Factorizing Text-to-Video Generation by Explicit Image Conditioning](https://mlsanity.com/paper/2311.10709/) (2023)
- [BlenderBot 3: a deployed conversational agent that continually learns to responsibly engage](https://mlsanity.com/paper/2208.03188/) (2022)
- [In-context Reinforcement Learning with Algorithm Distillation](https://mlsanity.com/paper/2210.14215/) (2022)
- [Deep Hierarchical Planning from Pixels](https://mlsanity.com/paper/2206.04114/) (2022)
- [Lipschitz Continuity in Model-based Reinforcement Learning](https://mlsanity.com/paper/1804.07193/) (2018)
- [On the Planning Abilities of Large Language Models (A Critical Investigation with a Proposed Benchmark)](https://mlsanity.com/paper/2302.06706/) (2023)
- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [Bayesian Relational Memory for Semantic Visual Navigation](https://mlsanity.com/paper/1909.04306/) (2019)
- [Making Neural Programming Architectures Generalize via Recursion](https://mlsanity.com/paper/1704.06611/) (2017)
- [Learning to Search with MCTSnets](https://mlsanity.com/paper/1802.04697/) (2018)
- [Chain of Thought Imitation with Procedure Cloning](https://mlsanity.com/paper/2205.10816/) (2022)

## Built on by (most cited first, 30 of 90)

- [Training Large Language Models to Reason in a Continuous Latent Space](https://mlsanity.com/paper/2412.06769/) (2024)
- [Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRs](https://mlsanity.com/paper/2503.01307/) (2025)
- [From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Step](https://mlsanity.com/paper/2405.14838/) (2024)
- [Train for the Worst, Plan for the Best: Understanding Token Ordering in Masked Diffusions](https://mlsanity.com/paper/2502.06768/) (2025)
- [Agent Q: Advanced Reasoning and Learning for Autonomous AI Agents](https://mlsanity.com/paper/2408.07199/) (2024)
- [Hierarchical Reasoning Model](https://mlsanity.com/paper/2506.21734/) (2025)
- [Recursive Introspection: Teaching Language Model Agents How to Self-Improve](https://mlsanity.com/paper/2407.18219/) (2024)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Stop Regressing: Training Value Functions via Classification for Scalable Deep RL](https://mlsanity.com/paper/2403.03950/) (2024)
- [From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models](https://mlsanity.com/paper/2406.16838/) (2024)
- [Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning](https://mlsanity.com/paper/2410.14157/) (2024)
- [Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuning](https://mlsanity.com/paper/2503.07572/) (2025)
- [Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought](https://mlsanity.com/paper/2501.04682/) (2025)
- [Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning](https://mlsanity.com/paper/2502.03275/) (2025)
- [Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Models](https://mlsanity.com/paper/2412.15287/) (2024)
- [Scaling Test-Time Compute Without Verification or RL is Suboptimal](https://mlsanity.com/paper/2502.12118/) (2025)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [Learning to Plan & Reason for Evaluation with Thinking-LLM-as-a-Judge](https://mlsanity.com/paper/2501.18099/) (2025)
- [A Survey on Large Language Models for Mathematical Reasoning](https://mlsanity.com/paper/2506.08446/) (2025)
- [Scaling of Search and Learning: A Roadmap to Reproduce o1 from Reinforcement Learning Perspective](https://mlsanity.com/paper/2412.14135/) (2024)
- [Thinking LLMs: General Instruction Following with Thought Generation](https://mlsanity.com/paper/2410.10630/) (2024)
- [Less is More: Recursive Reasoning with Tiny Networks](https://mlsanity.com/paper/2510.04871/) (2025)
- [Dualformer: Controllable Fast and Slow Thinking by Learning with Randomized Reasoning Traces](https://mlsanity.com/paper/2410.09918/) (2024)
- [Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokens](https://mlsanity.com/paper/2505.13775/) (2025)
- [Large Language Models for Planning: A Comprehensive and Systematic Survey](https://mlsanity.com/paper/2505.19683/) (2025)
- [Causal Language Modeling Can Elicit Search and Reasoning Capabilities on Logic Puzzles](https://mlsanity.com/paper/2409.10502/) (2024)
- [Position: Stop Anthropomorphizing Intermediate Tokens as Reasoning/Thinking Traces!](https://mlsanity.com/paper/2504.09762/) (2025)
- [System-1.x: Learning to Balance Fast and Slow Planning with Language Models](https://mlsanity.com/paper/2407.14414/) (2024)
- [Intelligent Go-Explore: Standing on the Shoulders of Giant Foundation Models](https://mlsanity.com/paper/2405.15143/) (2024)
- [Robotouille: An Asynchronous Planning Benchmark for LLM Agents](https://mlsanity.com/paper/2502.05227/) (2025)

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