---
title: "Stream of Search (SoS): Learning to Search in Language (2024)"
description: "They propose Stream of Search (SoS), a unified textual vocabulary that turns an entire search… 28 references, cited by 47 papers here."
authors: ["Kanishk Gandhi", "Denise Lee", "Gabriel Grand", "Muxin Liu", "Winson Cheng", "Archit Sharma", "Noah D. Goodman"]
year: 2024
venue: "arXiv:2404.03683"
source: "https://arxiv.org/abs/2404.03683"
doi: "10.48550/arxiv.2404.03683"
arxiv: "2404.03683"
licence: "CC BY 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/gandhi-2024-stream-search-sos-learning-search/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/gandhi-2024-stream-search-sos-learning-search/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2024](https://md.research.elamur.ai/free/en/papers/2024/page/8/) / Stream of Search (SoS): Learning to Search in Language

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

**Authors:** [Kanishk Gandhi](https://md.research.elamur.ai/free/en/authors/kanishk-gandhi/), Denise Lee, [Gabriel Grand](https://md.research.elamur.ai/free/en/authors/gabriel-grand/), Muxin Liu, Winson Cheng, [Archit Sharma](https://md.research.elamur.ai/free/en/authors/archit-sharma/) and [Noah D. Goodman](https://md.research.elamur.ai/free/en/authors/noah-d-goodman/) · **Year:** 2024 · **Venue:** arXiv:2404.03683 · **Licence:** [CC BY 4.0 (arXiv)](http://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2404.03683) · [PDF](https://arxiv.org/pdf/2404.03683) · [DOI 10.48550/arxiv.2404.03683](https://doi.org/10.48550/arxiv.2404.03683) · [arXiv 2404.03683](https://arxiv.org/abs/2404.03683) · [OpenAlex](https://openalex.org/W4394591144)

**Citations:** 2 citations (OpenAlex, 2026-10-14) · [47](https://md.research.elamur.ai/free/en/papers/gandhi-2024-stream-search-sos-learning-search/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Autoregressive language models are usually trained only on finished, correct answers, so they never see a solver hit dead ends and recover. The authors link this to two known weaknesses: mistakes that accumulate during generation, and poor anticipation of outcomes several moves ahead. They propose Stream of Search (SoS), a unified textual vocabulary that turns an entire search process into one flat string, covering state expansion, goal checks, backtracking and implicit pruning. They use Countdown, where given numbers must be combined arithmetically to hit a target. Several symbolic solvers guided by simple heuristics produce the training trajectories, and a transformer is pretrained from scratch on them. This model is about 25% more accurate than one trained only on optimal solution paths. Further finetuning for correctness with APA and STaR lets it solve problems its heuristic teachers could not, and it appears to move toward its own search strategies. The work suggests search can be learned inside a plain sequence model rather than added externally at inference time.

## Key points
- Countdown is the testbed. It is a generalization of the game of 24, with a high branching factor and a combinatorial search space.
- Pretraining on SoS data (exploration plus backtracking) raised search accuracy by about 25% over a baseline trained only on optimal trajectories.
- Policy improvement used Advantage-Induced Policy Alignment (APA) and STaR-style expert iteration.
  - Finetuned models solved roughly 36% of 10,000 training problems the symbolic solvers had left unsolved.
  - They also solved about 4% of 10,000 problems that no symbolic strategy could solve.
- The SoS+APA and SoS+STaR models made fewer arithmetic errors per trajectory and visited fewer states before finding correct solutions. This points to a better internal model of the environment.
- Limitations:
  - Experiments cover Countdown only.
  - Building the initial dataset requires symbolic solvers.
- Code: github.com/kanishkg/stream-of-search

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Stanford University](https://md.research.elamur.ai/free/en/universities/stanford-university/) — University, Stanford, United States · 567 works · 335,190 citations
- [Massachusetts Institute of Technology](https://md.research.elamur.ai/free/en/universities/massachusetts-institute-of-technology/) — University, Cambridge, United States · 274 works · 82,013 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 19,503 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 18,805 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,959 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,789 works

## Cite

Cite as: Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma and Noah D. Goodman. 2024. Stream of Search (SoS): Learning to Search in Language. arXiv:2404.03683.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{gandhi2024stream,
  title = {{Stream of Search (SoS): Learning to Search in Language}},
  author = {Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma and Noah D. Goodman},
  year = {2024},
  doi = {10.48550/arxiv.2404.03683},
  eprint = {2404.03683},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2404.03683}
}
```

- [← previous LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning](https://md.research.elamur.ai/free/en/papers/zhang-2024-llama-berry-pairwise-optimization-o1/)
- [next → The Effectiveness of LLMs as Annotators: A Comparative Overview and Empirical Analysis of Direct Representation](https://md.research.elamur.ai/free/en/papers/pavlovic-2024-effectiveness-llms-annotators-comparative-overview/)
- [↑ back to papers of 2024](https://md.research.elamur.ai/free/en/papers/2024/page/8/)

## References

28 references, 12 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, et al. [Do as i can, not as i say: Grounding language in robotic affordances](https://md.research.elamur.ai/free/en/papers/ahn-2022-i-i-say-grounding-language/). arXiv preprint arXiv:2204.01691, 2022.
2. Kushal Arora, Layla El Asri, Hareesh Bahuleyan, and Jackie Chi Kit Cheung. [Why exposure bias matters: An imitation learning perspective of error accumulation in language generation](https://md.research.elamur.ai/free/en/papers/arora-2022-why-exposure-bias-matters-imitation/). arXiv preprint arXiv:2204.01171, 2022.
3. Gregor Bachmann and Vaishnavh Nagarajan. [The pitfalls of next-token prediction](https://md.research.elamur.ai/free/en/papers/bachmann-2024-pitfalls-next-token-prediction/). arXiv preprint arXiv:2403.06963, 2024.
4. Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. arXiv preprint arXiv:2308.09687, 2023. [find](https://scholar.google.com/scholar?q=Maciej+Besta%2C+Nils+Blach%2C+Ales+Kubicek%2C+Robert+Gerstenberger%2C+Lukas+Gianinazzi%2C+Joanna+Gajda%2C+Tomasz+Lehmann%2C+Michal+Podstawski%2C+Hubert+Niewiadomski%2C+Piotr+Nyczyk%2C+et+al%2E+Graph+of+thoughts%3A+Solving+el)
5. Countdown. Countdown (game show). [https://en.wikipedia.org/wiki/Countdown_](https://en.wikipedia.org/wiki/Countdown_) (game_show), 2024. [Online; accessed 29-March-2024]. [↗](https://en.wikipedia.org/wiki/Countdown_)
6. Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344–16359, 2022. [find](https://scholar.google.com/scholar?q=Tri+Dao%2C+Dan+Fu%2C+Stefano+Ermon%2C+Atri+Rudra%2C+and+Christopher+R%C3%A9%2E+Flashattention%3A+Fast+and+memory%2Defficient+exact+attention+with+io%2Dawareness%2E+Advances+in+Neural+Information+Processing+Systems%2C+35%3A16344)
7. Richard E Fikes and Nils J Nilsson. [Strips: A new approach to the application of theorem proving to problem solving](https://md.research.elamur.ai/free/en/papers/fikes-1971-strips-new-approach-application-theorem/). Artificial intelligence, 2(3-4):189–208, 1971.
8. Kanishk Gandhi, Dorsa Sadigh, and Noah D Goodman. [Strategic reasoning with language models](https://md.research.elamur.ai/free/en/papers/gandhi-2023-strategic-reasoning-language-models/). arXiv preprint arXiv:2305.19165, 2023.
9. Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.00027, 2020. [find](https://scholar.google.com/scholar?q=Leo+Gao%2C+Stella+Biderman%2C+Sid+Black%2C+Laurence+Golding%2C+Travis+Hoppe%2C+Charles+Foster%2C+Jason+Phang%2C+Horace+He%2C+Anish+Thite%2C+Noa+Nabeshima%2C+et+al%2E+The+pile%3A+An+800gb+dataset+of+diverse+text+for+language+)
10. Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjie Gu, et al. [Reinforced self-training (rest) for language modeling](https://md.research.elamur.ai/free/en/papers/gulcehre-2023-reinforced-self-training-rest-language/). arXiv preprint arXiv:2308.08998, 2023.
11. Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. [Large language models cannot self-correct reasoning yet](https://md.research.elamur.ai/free/en/papers/huang-2023-large-language-models-cannot-self/). arXiv preprint arXiv:2310.01798, 2023.
12. Y LeCun. Do large language models need sensory grounding for meaning and understanding. In Workshop on Philosophy of Deep Learning, NYU Center for Mind, Brain, and Consciousness and the Columbia Center for Science and Society, 2023. [find](https://scholar.google.com/scholar?q=Y+LeCun%2E+Do+large+language+models+need+sensory+grounding+for+meaning+and+understanding%2E+In+Workshop+on+Philosophy+of+Deep+Learning%2C+NYU+Center+for+Mind%2C+Brain%2C+and+Consciousness+and+the+Columbia+Cente)
13. Lucas Lehnert, Sainbayar Sukhbaatar, Paul Mcvay, Michael Rabbat, and Yuandong Tian. Beyond a*: Better planning with transformers via search dynamics bootstrapping. arXiv preprint arXiv:2402.14083, 2024. [find](https://scholar.google.com/scholar?q=Lucas+Lehnert%2C+Sainbayar+Sukhbaatar%2C+Paul+Mcvay%2C+Michael+Rabbat%2C+and+Yuandong+Tian%2E+Beyond+a%2A%3A+Better+planning+with+transformers+via+search+dynamics+bootstrapping%2E+arXiv+preprint+arXiv%3A2402%2E14083%2C+202)
14. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. arXiv preprint arXiv:2305.[20050, 2023](https://md.research.elamur.ai/free/en/papers/lightman-2023-let-s-verify-step-step/).
15. Ida Momennejad, Hosein Hasanbeig, Felipe Vieira Frujeri, Hiteshi Sharma, Nebojsa Jojic, Hamid Palangi, Robert Ness, and Jonathan Larson. Evaluating cognitive maps and planning in large language models with cogeval. Advances in Neural Information Processing Systems, 36, 2024. [find](https://scholar.google.com/scholar?q=Ida+Momennejad%2C+Hosein+Hasanbeig%2C+Felipe+Vieira+Frujeri%2C+Hiteshi+Sharma%2C+Nebojsa+Jojic%2C+Hamid+Palangi%2C+Robert+Ness%2C+and+Jonathan+Larson%2E+Evaluating+cognitive+maps+and+planning+in+large+language+models)
16. Vishal Pallagani, Bharath Muppasani, Keerthiram Murugesan, Francesca Rossi, Biplav Srivastava, Lior Horesh, Francesco Fabiano, and Andrea Loreggia. Understanding the capabilities of large language models for automated planning. arXiv preprint arXiv:2305.16151, 2023. — [arXiv:2305.16151](https://arxiv.org/abs/2305.16151) [find](https://scholar.google.com/scholar?q=Vishal+Pallagani%2C+Bharath+Muppasani%2C+Keerthiram+Murugesan%2C+Francesca+Rossi%2C+Biplav+Srivastava%2C+Lior+Horesh%2C+Francesco+Fabiano%2C+and+Andrea+Loreggia%2E+Understanding+the+capabilities+of+large+language+mod)
17. Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 627–635. JMLR Workshop and Conference Proceedings, 2011… [find](https://scholar.google.com/scholar?q=St%C3%A9phane+Ross%2C+Geoffrey+Gordon%2C+and+Drew+Bagnell%2E+A+reduction+of+imitation+learning+and+structured+prediction+to+no%2Dregret+online+learning%2E+In+Proceedings+of+the+fourteenth+international+conference+on)
18. Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839): 604–609, 2020. [find](https://scholar.google.com/scholar?q=Julian+Schrittwieser%2C+Ioannis+Antonoglou%2C+Thomas+Hubert%2C+Karen+Simonyan%2C+Laurent+Sifre%2C+Simon+Schmitt%2C+Arthur+Guez%2C+Edward+Lockhart%2C+Demis+Hassabis%2C+Thore+Graepel%2C+et+al%2E+Mastering+atari%2C+go%2C+chess+an)
19. Bilgehan Sel, Ahmad Al-Tawaha, Vanshaj Khattar, Lu Wang, Ruoxi Jia, and Ming Jin. Algorithm of thoughts: Enhancing exploration of ideas in large language models. arXiv preprint arXiv:2308.10379, 2023. [find](https://scholar.google.com/scholar?q=Bilgehan+Sel%2C+Ahmad+Al%2DTawaha%2C+Vanshaj+Khattar%2C+Lu+Wang%2C+Ruoxi+Jia%2C+and+Ming+Jin%2E+Algorithm+of+thoughts%3A+Enhancing+exploration+of+ideas+in+large+language+models%2E+arXiv+preprint+arXiv%3A2308%2E10379%2C+2023%2E)
20. Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. [Reflexion: Language agents with verbal reinforcement learning](https://md.research.elamur.ai/free/en/papers/shinn-2023-reflexion-language-agents-verbal-reinforcement/). Advances in Neural Information Processing Systems, 36, 2024.
21. David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–1144, 2018. [find](https://scholar.google.com/scholar?q=David+Silver%2C+Thomas+Hubert%2C+Julian+Schrittwieser%2C+Ioannis+Antonoglou%2C+Matthew+Lai%2C+Arthur+Guez%2C+Marc+Lanctot%2C+Laurent+Sifre%2C+Dharshan+Kumaran%2C+Thore+Graepel%2C+et+al%2E+A+general+reinforcement+learning+a)
22. Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. [On the self-verification limitations of large language models on reasoning and planning tasks](https://md.research.elamur.ai/free/en/papers/stechly-2024-self-verification-limitations-large-language/). arXiv preprint arXiv:2402.08115, 2024.
23. Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. [find](https://scholar.google.com/scholar?q=Richard+S+Sutton+and+Andrew+G+Barto%2E+Reinforcement+learning%3A+An+introduction%2E+MIT+press%2C+2018%2E)
24. Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati. On the planning abilities of large language models-a critical investigation. Advances in Neural Information Processing Systems, 36, 2024. — [On the Planning Abilities of Large Language Models : A Critical Investigation](https://md.research.elamur.ai/free/en/papers/valmeekam-2023-planning-abilities-large-language-models/)
25. Mengjiao Sherry Yang, Dale Schuurmans, Pieter Abbeel, and Ofir Nachum. Chain of thought imitation with procedure cloning. Advances in Neural Information Processing Systems, 35: 36366–36381, 2022. [find](https://scholar.google.com/scholar?q=Mengjiao+Sherry+Yang%2C+Dale+Schuurmans%2C+Pieter+Abbeel%2C+and+Ofir+Nachum%2E+Chain+of+thought+imitation+with+procedure+cloning%2E+Advances+in+Neural+Information+Processing+Systems%2C+35%3A+36366%E2%80%9336381%2C+2022%2E)
26. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024. [find](https://scholar.google.com/scholar?q=Shunyu+Yao%2C+Dian+Yu%2C+Jeffrey+Zhao%2C+Izhak+Shafran%2C+Tom+Griffiths%2C+Yuan+Cao%2C+and+Karthik+Narasimhan%2E+Tree+of+thoughts%3A+Deliberate+problem+solving+with+large+language+models%2E+Advances+in+Neural+Informati)
27. Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. [Star: Bootstrapping reasoning with reasoning](https://md.research.elamur.ai/free/en/papers/zelikman-2022-star-bootstrapping-reasoning-reasoning/). Advances in Neural Information Processing Systems, 35:15476–15488, 2022.
28. Banghua Zhu, Hiteshi Sharma, Felipe Vieira Frujeri, Shi Dong, Chenguang Zhu, Michael I Jordan, and Jiantao Jiao. Fine-tuning language models with advantage-induced policy alignment. arXiv preprint arXiv:2306.02231, 2023. — [arXiv:2306.02231](https://arxiv.org/abs/2306.02231) [find](https://scholar.google.com/scholar?q=Banghua+Zhu%2C+Hiteshi+Sharma%2C+Felipe+Vieira+Frujeri%2C+Shi+Dong%2C+Chenguang+Zhu%2C+Michael+I+Jordan%2C+and+Jiantao+Jiao%2E+Fine%2Dtuning+language+models+with+advantage%2Dinduced+policy+alignment%2E+arXiv+preprint+arX)

*Updated 3 November 2026*