title: Stream of Search (SoS): Learning to Search in Language
summary: 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.
paper_authors._id: 6613588b188ff298b0521791
paper_authors.name: Kanishk Gandhi
paper_authors.status: extracted_confirmed
paper_authors.statusLastChangedAt: 2024-09-19T01:34:54.793Z
paper_authors._id: 63e6a880f2e9a8f22c5a1630
paper_authors.avatarUrl: /avatars/53b57690fe052ce6882bbfc87b11567c.svg
paper_authors.fullname: Kanishk Gandhi
paper_authors.type: user
paper_authors.user: obiwan96
paper_authors._id: 6613588b188ff298b0521792
paper_authors.name: Denise Lee
paper_authors._id: 6613588b188ff298b0521793
paper_authors.name: Gabriel Grand
paper_authors._id: 6613588b188ff298b0521794
paper_authors.name: Muxin Liu
paper_authors._id: 6613588b188ff298b0521795
paper_authors.name: Winson Cheng
paper_authors._id: 6613588b188ff298b0521796
paper_authors.name: Archit Sharma
paper_authors._id: 6613588b188ff298b0521797
paper_authors.name: Noah D. Goodman
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-11-15T09:47:53.860Z
paper_authors._id: 67321274c1f20c742bcf7a8d
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/no-auth/ltcQhre6eDRVzn6Vbbyhu.png
paper_authors.fullname: Noah D. Goodman
paper_authors.type: user
paper_authors.user: ngoodman
paper_title: Stream of Search (SoS): Learning to Search in Language
paper_summary: 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.
paper_ai_keywords: transformer-based language model stream of search (SoS) symbolic search strategies Advantage-Induced Policy Alignment (APA) Self-Taught Reasoner (STaR) heuristic solvers