Tree Search for Language Models

Summary & Methodology Analysis

Standard language model inference relies on token-level, left-to-right decision-making processes, which restricts performance on tasks requiring exploration, strategic lookahead, or pivotal initial decisions. To address this limitation, the authors introduce the Tree of Thoughts framework. This approach frames problem-solving as a search over a tree where each node represents a partial solution state. The intermediate process is decomposed into thought steps depending on the properties of the problem. Potential thoughts are generated from each state using either independent and identically distributed sampling from a chain-of-thought prompt or sequential generation using a propose prompt. States are then heuristically evaluated by valuing each state independently using a value prompt or by voting across states using a vote prompt. Finally, the tree of thoughts is explored using search algorithms such as breadth-first search or depth-first search with lookahead and backtracking.

The framework was evaluated across several models and tasks, including GPT, PaLM, DeepBlue, AlphaGo, the Game of 24, Creative Writing, Mini Crosswords, GSM8K, StrategyQA, and GPT-3.5-turbo. In the Game of 24 task, GPT-4 with chain-of-thought prompting solved 4 percent of tasks, whereas Tree of Thoughts achieved a success rate of 74 percent. In Creative Writing, Tree of Thoughts generated more coherent passages, yielding an average GPT-4 score of 7.56 compared to 6.19 for input-output prompting and 6.93 for chain-of-thought prompting. The paper also evaluated standard techniques for comparison or as baselines, including input-output prompting, chain-of-thought prompting, self-consistency with chain-of-thought, and iterative-refine.

Despite the performance gains, the paper notes specific limitations. Deliberate search such as Tree of Thoughts might not be necessary for many existing tasks that GPT-4 already excels at. Additionally, search methods like Tree of Thoughts require more resources and higher API costs than sampling methods in order to improve task performances. The paper does not specify exact dollar costs or hardware memory footprints beyond noting the higher resource and API cost requirements.