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

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

## Key facts

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

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 23 of 23)

- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [STaR: Bootstrapping Reasoning With Reasoning](https://mlsanity.com/paper/2203.14465/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Sequence Level Training with Recurrent Neural Networks](https://mlsanity.com/paper/1511.06732/) (2015)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [The pitfalls of next-token prediction](https://mlsanity.com/paper/2403.06963/) (2024)
- [On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Tasks](https://mlsanity.com/paper/2402.08115/) (2024)
- [Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generation](https://mlsanity.com/paper/2204.01171/) (2022)
- [Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models](https://mlsanity.com/paper/2308.10379/) (2023)
- [Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping](https://mlsanity.com/paper/2402.14083/) (2024)
- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [Strategic Reasoning with Language Models](https://mlsanity.com/paper/2305.19165/) (2023)
- [Fine-Tuning Language Models with Advantage-Induced Policy Alignment](https://mlsanity.com/paper/2306.02231/) (2023)
- [Understanding the Capabilities of Large Language Models for Automated Planning](https://mlsanity.com/paper/2305.16151/) (2023)
- [Chain of Thought Imitation with Procedure Cloning](https://mlsanity.com/paper/2205.10816/) (2022)

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

- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [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 System 1 to System 2: A Survey of Reasoning Large Language Models](https://mlsanity.com/paper/2502.17419/) (2025)
- [Scaling Diffusion Language Models via Adaptation from Autoregressive Models](https://mlsanity.com/paper/2410.17891/) (2024)
- [HuatuoGPT-o1, Towards Medical Complex Reasoning with LLMs](https://mlsanity.com/paper/2412.18925/) (2024)
- [Training Language Models to Reason Efficiently](https://mlsanity.com/paper/2502.04463/) (2025)
- [Inference-Time Scaling for Diffusion Models beyond Scaling Denoising Steps](https://mlsanity.com/paper/2501.09732/) (2025)
- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [Recursive Introspection: Teaching Language Model Agents How to Self-Improve](https://mlsanity.com/paper/2407.18219/) (2024)
- [Crossing the Reward Bridge: Expanding RL with Verifiable Rewards Across Diverse Domains](https://mlsanity.com/paper/2503.23829/) (2025)
- [Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning](https://mlsanity.com/paper/2410.14157/) (2024)
- [LLM Post-Training: A Deep Dive into Reasoning Large Language Models](https://mlsanity.com/paper/2502.21321/) (2025)
- [Optimizing Test-Time Compute via Meta Reinforcement Fine-Tuning](https://mlsanity.com/paper/2503.07572/) (2025)
- [Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning](https://mlsanity.com/paper/2502.18080/) (2025)
- [Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought](https://mlsanity.com/paper/2501.04682/) (2025)
- [Agentic Large Language Models, a survey](https://mlsanity.com/paper/2503.23037/) (2025)
- [Curriculum Reinforcement Learning from Easy to Hard Tasks Improves LLM Reasoning](https://mlsanity.com/paper/2506.06632/) (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)
- [Efficient Reasoning with Hidden Thinking](https://mlsanity.com/paper/2501.19201/) (2025)
- [One Token to Fool LLM-as-a-Judge](https://mlsanity.com/paper/2507.08794/) (2025)
- [e3: Learning to Explore Enables Extrapolation of Test-Time Compute for LLMs](https://mlsanity.com/paper/2506.09026/) (2025)
- [Learning Adaptive Parallel Reasoning with Language Models](https://mlsanity.com/paper/2504.15466/) (2025)
- [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026)
- [Dualformer: Controllable Fast and Slow Thinking by Learning with Randomized Reasoning Traces](https://mlsanity.com/paper/2410.09918/) (2024)
- [SoftCoT++: Test-Time Scaling with Soft Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.11484/) (2025)
- [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)

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