learn.ifs.name

Tree of Thoughts: Deliberate Problem Solving with Large Language Models

Yao et al., 2023, Tree of Thoughts (Advances in Neural Information Processing Systems 36 (NeurIPS 2023))

Subscriber deck — free during early access

6 cards in “3 Tree of Thoughts: Deliberate Problem Solving with LM” · whole deck

3 Tree of Thoughts: Deliberate Problem Solving with LM

  1. What is a “thought” in Tree of Thoughts, and how big should it be?
    A coherent language sequence that is an intermediate step toward a solution: a few words (crosswords), one equation (Game of 24), or a paragraph-long plan (creative writing). It should be small enough to generate diverse, promising candidates, but big enough for the model to judge its promise.
    • Yao et al., 2023, Tree of Thoughts (Advances in Neural Information Processing Systems 36 (NeurIPS 2023)), §3
  2. What four questions define an instance of Tree of Thoughts?
    How to decompose the process into thought steps; how to generate candidate thoughts from a state; how to evaluate states heuristically; and which search algorithm to use. A state \(s = [x, z_{1 \ldots i}]\) is the input plus the thoughts so far.
    1 5 6 99 − 5 = 4left: 1 4 6sure6 + 9 = 15left: 1 5 15impossible5 × 6 = 30left: 1 9 30impossible4 × 6 = 2424 × 1 = 24pruned: not expanded
    The model proposes next steps and judges each state; the search expands only promising ones (invented Game of 24 example)
    • Yao et al., 2023, Tree of Thoughts (Advances in Neural Information Processing Systems 36 (NeurIPS 2023)), §3
  3. What two ways of generating thoughts does Tree of Thoughts use, and when does each fit?
    Sampling i.i.d. thoughts from a CoT prompt, good when the thought space is rich (e.g. paragraphs) so samples differ; or proposing several thoughts at once with a “propose prompt”, good when the space is constrained (a word or an equation) so independent samples would duplicate.
    • Yao et al., 2023, Tree of Thoughts (Advances in Neural Information Processing Systems 36 (NeurIPS 2023)), §3
  4. How does Tree of Thoughts evaluate states, and why is this new?
    The language model itself reasons about states, either valuing each (e.g. a score, or sure/maybe/impossible, via quick lookahead and commonsense such as “1 2 3 are too small to reach 24”) or voting for the most promising among several. Earlier search heuristics were either programmed (Deep Blue) or learned (AlphaGo).
    • Yao et al., 2023, Tree of Thoughts (Advances in Neural Information Processing Systems 36 (NeurIPS 2023)), §3
  5. Which search algorithms does Tree of Thoughts use?
    Breadth-first search keeping the \(b\) best states per step (shallow trees: Game of 24, creative writing), and depth-first search exploring the most promising state first, pruning subtrees judged impossible and backtracking (crosswords). A* and MCTS are left for future work.
    • Yao et al., 2023, Tree of Thoughts (Advances in Neural Information Processing Systems 36 (NeurIPS 2023)), §3
  6. Why do Yao et al. say Tree of Thoughts generalizes earlier prompting methods?
    IO, CoT, CoT-SC and self-refinement are special cases: trees of limited depth and breadth. The model, decomposition, generation, evaluation and search can each be varied independently, and no training is needed.
    • Yao et al., 2023, Tree of Thoughts (Advances in Neural Information Processing Systems 36 (NeurIPS 2023)), §3

Source