mlsanityData to 7 Oct 2026

Stream of Search (SoS): Learning to Search in Language

arXiv 2404.03683 ↗First posted 1 Apr 2024cs.LG cs.AI cs.CLcited by 141

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

Language models are rarely shown fruitful mistakes while training. They then struggle to look beyond the next token, suffering from a snowballing of errors and struggling to predict the consequence of their actions several steps ahead. In this paper, we show how language models can be taught to search by representing the process of search in language, as a flattened string -- a stream of search (SoS). We propose a unified language for search that captures an array of different symbolic search strategies. We demonstrate our approach using the simple yet difficult game of Countdown, where the goal is to combine input numbers with arithmetic operations to reach a target number. We pretrain a transformer-based language model from scratch on a dataset of streams of search generated by heuristic solvers. We find that SoS pretraining increases search accuracy by 25% over models trained to predict only the optimal search trajectory. We further finetune this model with two policy improvement methods: Advantage-Induced Policy Alignment (APA) and Self-Taught Reasoner (STaR). The finetuned SoS models solve 36% of previously unsolved problems, including problems that cannot be solved by any of the heuristic solvers. Our results indicate that language models can learn to solve problems via search, self-improve to flexibly use different search strategies, and potentially discover new ones.

Key facts. Cited by 141 papers in the map (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 23 of its 31 references that are in the map. First posted on arXiv 1 Apr 2024.

Builds on

23 of 31 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks12 Feb
  2. 2023Large Language Models Cannot Self-Correct Reasoning Yet3 Oct
  3. 2023Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models20 Aug
  4. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Models17 May
  5. 2022STaR: Bootstrapping Reasoning With Reasoning28 Mar

Other references · 18

  1. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,064
  2. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  3. 2023Let's Verify Step by Stepcited by 3,598
  4. 2020The Pile: An 800GB Dataset of Diverse Text for Language Modelingcited by 2,346
  5. 2022Do As I Can, Not As I Say: Grounding Language in Robotic Affordancescited by 2,302
  6. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  7. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 873
  8. 2015Sequence Level Training with Recurrent Neural Networkscited by 568
  9. 2023Reinforced Self-Training (ReST) for Language Modelingcited by 486
  10. 2023On the Planning Abilities of Large Language Models : A Critical Investigationcited by 308
  11. 2024The pitfalls of next-token predictioncited by 156
  12. 2022Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generationcited by 106
6 more
  1. 2024Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrappingcited by 89
  2. 2023Evaluating Cognitive Maps and Planning in Large Language Models with CogEvalcited by 77
  3. 2023Strategic Reasoning with Language Modelscited by 64
  4. 2023Fine-Tuning Language Models with Advantage-Induced Policy Alignmentcited by 48
  5. 2023Understanding the Capabilities of Large Language Models for Automated Planningcited by 34
  6. 2022Chain of Thought Imitation with Procedure Cloningcited by 30

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 18; 2025: 85; 2026: 38.

141 papers.

Sort:

By area:

  1. 2025s1: Simple test-time scalingcited by 1,311
  2. 2024Training Large Language Models to Reason in a Continuous Latent Spacecited by 763
  3. 2025Cognitive Behaviors that Enable Self-Improving Reasoners, or, Four Habits of Highly Effective STaRscited by 373
  4. 2025From System 1 to System 2: A Survey of Reasoning Large Language Modelscited by 319
  5. 2024Scaling Diffusion Language Models via Adaptation from Autoregressive Modelscited by 268
  6. 2024HuatuoGPT-o1, Towards Medical Complex Reasoning with LLMscited by 257
  7. 2025Training Language Models to Reason Efficientlycited by 242
  8. 2025Inference-Time Scaling for Diffusion Models beyond Scaling Denoising Stepscited by 225
  9. 2025A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?cited by 215
  10. 2024Recursive Introspection: Teaching Language Model Agents How to Self-Improvecited by 162
  11. 2025Crossing the Reward Bridge: Expanding RL with Verifiable Rewards Across Diverse Domainscited by 150
  12. 2024Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planningcited by 135
38 more
  1. 2025LLM Post-Training: A Deep Dive into Reasoning Large Language Modelscited by 129
  2. 2025Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuningcited by 121
  3. 2025Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoningcited by 118
  4. 2025Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thoughtcited by 108
  5. 2025Agentic Large Language Models, a surveycited by 105
  6. 2025Curriculum Reinforcement Learning from Easy to Hard Tasks Improves LLM Reasoningcited by 89
  7. 2025Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoningcited by 87
  8. 2024Inference-Aware Fine-Tuning for Best-of-N Sampling in Large Language Modelscited by 86
  9. 2025Scaling Test-Time Compute Without Verification or RL is Suboptimalcited by 82
  10. 2025Efficient Reasoning with Hidden Thinkingcited by 72
  11. 2025Learning Adaptive Parallel Reasoning with Language Modelscited by 58
  12. 2025e3: Learning to Explore Enables Extrapolation of Test-Time Compute for LLMscited by 56
  13. 2025One Token to Fool LLM-as-a-Judgecited by 56
  14. 2026A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agentscited by 47
  15. 2025Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokenscited by 41
  16. 2024Dualformer: Controllable Fast and Slow Thinking by Learning with Randomized Reasoning Tracescited by 40
  17. 2025SoftCoT++: Test-Time Scaling with Soft Chain-of-Thought Reasoningcited by 38
  18. 2025Large Language Models for Planning: A Comprehensive and Systematic Surveycited by 38
  19. 2024System-1.x: Learning to Balance Fast and Slow Planning with Language Modelscited by 35
  20. 2024EVOLvE: Evaluating and Optimizing LLMs For In-Context Explorationcited by 33
  21. 2025Meta-Reasoner: Dynamic Guidance for Optimized Inference-time Reasoning in Large Language Modelscited by 33
  22. 2025Navigate the Unknown: Enhancing LLM Reasoning with Intrinsic Motivation Guided Explorationcited by 33
  23. 2024Thought of Search: Planning with Language Models Through The Lens of Efficiencycited by 32
  24. 2025Generative to Agentic AI: Survey, Conceptualization, and Challengescited by 32
  25. 2024Surveying the Effects of Quality, Diversity, and Complexity in Synthetic Data From Large Language Modelscited by 31
  26. 2025Next-Latent Prediction Transformers Learn Compact World Modelscited by 29
  27. 2024On Expressive Power of Looped Transformers: Theoretical Analysis and Enhancement via Timestep Encodingcited by 28
  28. 2025LongProc: Benchmarking Long-Context Language Models on Long Procedural Generationcited by 28
  29. 2025Adversarial Reasoning at Jailbreaking Timecited by 27
  30. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillationcited by 25
  31. 2025LaDiR: Latent Diffusion Enhances LLMs for Text Reasoningcited by 25
  32. 2025To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoningcited by 24
  33. 2026Purified OPSD: On-Policy Self-Distillation Without Losing How to Thinkcited by 23
  34. 2025Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Samplingcited by 20
  35. 2024Transformers Struggle to Learn to Searchcited by 19
  36. 2025On the Effect of Sampling Diversity in Scaling LLM Inferencecited by 18
  37. 2025Stepwise Guided Policy Optimization: Coloring your Incorrect Reasoning in GRPOcited by 18
  38. 2025Meta-RL Induces Exploration in Language Agentscited by 17

50 most cited of 141 All 141 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2024Navigating the Labyrinth: Evaluating LLMs' Ability to Reason About Search Problems
  2. 2025SEM: Reinforcement Learning for Search-Efficient Large Language Models
  3. 2026LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories
  4. 2025Rethinking the Unsolvable: When In-Context Search Meets Test-Time Scaling
  5. 2026Search, Do not Guess: Teaching Small Language Models to Be Effective Search Agents
  6. 2026When Should LLMs Search? Counterfactual Supervision for Search Routing
  7. 2025Unifying Tree Search Algorithm and Reward Design for LLM Reasoning: A Survey
  8. 2025ReSearch: Learning to Reason with Search for LLMs via Reinforcement Learning