A researcher is applying a language model to a puzzle-like task, such as the Game of 24, where an early move can turn out to be a dead end many steps later, and simply extending a single left-to-right chain of thought performs poorly. According to Yao et al. (2023), "Tree of Thoughts: Deliberate Problem Solving with Large Language Models," what does the Tree of Thoughts framework add on top of chain-of-thought prompting to address this?
- Producing one single, linear sequence of reasoning steps from the problem to the final answer, exactly as in standard chain-of-thought prompting
- Sampling many complete, independent chain-of-thought reasoning paths for the whole problem and picking the final answer that the largest number of them agree on
- Framing problem solving as a search over a tree whose nodes are intermediate "thoughts": the model generates and self-evaluates multiple candidate next thoughts at each step, and the search can look ahead or backtrack using strategies such as breadth-first or depth-first search, at substantially higher inference-time compute cost than a single reasoning chain
- Training a separate value function offline to score candidate solutions, then using that fixed value function alone to pick a solution without the language model exploring or backtracking at inference time
Why C? And why not the others?
Correct answer: C. Framing problem solving as a search over a tree whose nodes are intermediate "thoughts": the model generates and self-evaluates multiple candidate next thoughts at each step, and the search can look ahead or backtrack using strategies such as breadth-first or depth-first search, at substantially higher inference-time compute cost than a single reasoning chain
Yao et al. (2023) introduce Tree of Thoughts to handle tasks like Game of 24 where an early step can turn out to be a dead end many steps later and a single left-to-right chain of thought performs poorly: the model frames problem solving as search over a tree of intermediate "thoughts," generating and self-evaluating multiple candidate next thoughts at each step and using search strategies such as breadth-first or depth-first search to look ahead or backtrack, which the paper reports raised Game of 24 success far above plain chain-of-thought, at the cost of far more inference-time compute than a single chain. The option describing one linear chain describes the baseline Tree of Thoughts is built to outperform on exactly this kind of task. The option describing sampling many independent full chains and majority-voting describes self-consistency, which does not let the model evaluate or backtrack partway through a path the way Tree of Thoughts does. The option describing an offline-trained value function used alone describes a different architecture that removes the model's own step-by-step exploration and self-evaluation at inference time.
Source: Yao et al., "Tree of Thoughts: Deliberate Problem Solving with Large Language Models" (2023), arXiv:2305.10601