REVIEW 30 cited by
Stream of Search (SoS): Learning to Search in Language
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
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.
Forward citations
Cited by 30 Pith papers
-
Bridging Compute- and Data-Optimal Pretraining
Pretraining loss obeys a single law in which repeated or paraphrased tokens count as η(N, data-per-parameter, expansion-ratio) fresh tokens, with total effective data saturating as derived tokens grow.
-
Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion
In clue-rich Sudoku, LDT-style lattice reasoners are one-shot amortized predictors: the first pass fixes the grid, all failures are first-pass poisonings, and search changes efficiency but not accuracy.
-
Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation
In a metastable Markov model of reasoning, search and RL improve hitting times by boosting rare hard edges, and distilling clusters into a meta-chain preserves escape dynamics.
-
Planning with Transformers: Chain of Computation and Structured Context Windows
Small transformers, trained from scratch on curated instruction traces and run inside a pointer-memory loop, solve BlocksWorld/Pancake at >99.89% and Tower of Hanoi to 20 disks.
-
GradAlign: Gradient-Aligned Data Selection for LLM Reinforcement Learning
GradAlign selects RL training problems whose policy gradients align with validation-set gradients, claiming more stable and better-performing LLM post-training.
-
Performative Thinking? The Brittle Correlation Between CoT Length and Problem Complexity
A transformer trained to imitate A* produces traces whose length reflects similarity to training data, not true problem complexity, so long chain-of-thought should not be read as more 'thinking'.
-
It's Not That Simple. An Analysis of Simple Test-Time Scaling
The apparent scaling behavior of the s1 model is mostly an artifact of truncating long outputs, while appending 'Wait' does not reliably improve answers.
-
One Token to Fool LLM-as-a-Judge
LLM reward models falsely accept empty 'master key' responses such as ':' or 'Thought process:' across many models, and a fine-tuning defense reduces these false positives to near zero.
-
AALC: Large Language Model Efficient Reasoning via Adaptive Accuracy-Length Control
AALC, an accuracy-aware length reward, reduces reasoning-model response length by over 50% on math benchmarks while preserving or improving accuracy.
-
e3: Learning to Explore Enables Extrapolation of Test-Time Compute for LLMs
e3 couples asymmetric skill chaining, negative-gradient RL, and a difficulty/budget curriculum so a 1.7B model extrapolates test-time compute to 2x its training budget and sets reported <2B state-of-the-art on AIME/HMMT 2025.
-
LLM-First Search: Self-Guided Exploration of the Solution Space
LLM-First Search, where the model itself decides whether to continue or backtrack during reasoning, outperforms MCTS, BestFS, and ToT-BFS on harder Countdown and Sudoku tasks while using fewer tokens.
-
How Much Backtracking is Enough? Exploring the Interplay of SFT and RL in Enhancing LLM Reasoning
On three controlled tasks, the optimal number of backtracks in SFT warm-up data grows with task difficulty, while trajectory correctness has little effect on final RL performance.
-
Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokens
Intermediate reasoning tokens help transformer performance not by their semantic content but by their presence and consistency; models trained on problem-irrelevant A* traces match or beat models trained on correct traces.
-
The Geometry of Self-Verification in a Task-Specific Reasoning Model
In a CountDown reasoning model, three attention heads drive a verification subspace that, when disabled, makes the model mark correct solutions as incorrect.
-
Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning
Partially replacing chain-of-thought tokens with discrete latent tokens during fine-tuning improves LLM reasoning accuracy and reduces generated token count.
-
Adversarial Reasoning at Jailbreaking Time
A loss-guided 'reason, verify, search' loop with three LLM modules surpasses prior semantic jailbreak methods on several defended models.
-
Constrained Path Reasoning: Measuring When Committed Stages Earn Their Cost
Committed LLM stages earn their cost when gains exceed propagated error and execution cost; in a convexification case study, formalization plus solver reached 90% usable yield versus 41% direct, and residual triage re...
-
Search, Fail, Recover: A Training Framework for Correction-Aware Reasoning
Pyligent trains LLMs to search, detect failures via task validators, and backtrack to recoverable prefixes, improving solve rates by 13–73 points over gold-only SFT on hidden graphs, Sudoku, and Blocksworld.
-
Position: We Need An Algorithmic Understanding of Generative AI
The paper argues for a systematic algorithmic understanding of LLMs and presents a case study suggesting that Llama models do not implement BFS or DFS on graph navigation tasks.
-
ASTRO: Teaching Language Models to Reason by Reflecting and Backtracking In-Context
ASTRO converts MCTS search trees into chain-of-thoughts with explicit self-reflection and backtracking, trains Llama-3.1-70B on them with SFT, then improves with RL, reaching 81.8% on MATH-500, 64.4% on AMC 2023, and ...
-
Make Planning Research Rigorous Again!
A position paper calling for LLM-based planning research to reuse the rigor, benchmarks, and tools of the classical automated planning community.
-
SoftCoT++: Test-Time Scaling with Soft Chain-of-Thought Reasoning
SoftCoT++ generates multiple diverse latent thoughts through distinct initial tokens and a contrastive loss, improving reasoning accuracy beyond soft-thought and self-consistency baselines.
-
Agent-Centric Projection of Prompting Techniques and Implications for Synthetic Training Data for Large Language Models
The paper defines linear and non-linear interaction contexts for LLMs and conjectures that prompting techniques and multi-agent systems are equivalent projections of the same patterns.
-
First Finish Search: Efficient Test-Time Scaling in Large Language Models
First Finish Search launches n parallel reasoning traces and returns the shortest one, improving accuracy on AIME benchmarks while cutting token use.
-
Generative to Agentic AI: Survey, Conceptualization, and Challenges
Agentic AI is characterized over Generative AI by iterative reasoning, environment interaction, memory, and tool use, with autonomy as the defining difference.
-
Surveying the Effects of Quality, Diversity, and Complexity in Synthetic Data From Large Language Models
This survey organizes LLM synthetic data research around quality, diversity, and complexity, claiming quality mainly helps in-distribution generalization, diversity mainly helps out-of-distribution generalization, and...
-
Large Language Models for Planning: A Comprehensive and Systematic Survey
A structured survey of LLM planning methods, benchmarks, and interpretability work, organized around a three-way taxonomy.
-
Generative AI Act II: Test Time Scaling Drives Cognition Engineering
Test-time scaling techniques such as long chain-of-thought, tree search, and self-correction define the paper's 'cognition engineering' paradigm, which it surveys, taxonomizes, and tutorials.
-
Reinforcement learning fine-tuning of language model for instruction following and math reasoning
RLOO with a DeBERTa reward model reaches a 0.695 win rate on instruction following, while best-of-N with an exact-match verifier lifts Countdown accuracy from 0.37 to 0.811.
- Transformers Struggle to Learn to Search
Discussion (0). Continue with ORCID to comment.