tree of thoughts (ToT)

Tree of thoughts treats problem solving as deliberate search over partial solutions rather than a single left-to-right ramble. The model proposes several next reasoning steps from the current state, scores how promising each looks, expands the good ones, and can back up to abandon a dead end. It is the difference between writing the first solution that comes to mind and sketching a few openings, evaluating them, and committing to the strongest.

Concretely, a thought is an intermediate step; states are sequences of thoughts forming nodes of a tree. A generator G(s) samples k candidate next thoughts, an evaluator V(s) gives each a heuristic value — by direct prompting (rate this state 1–10) or by voting across samples — and a search strategy such as breadth-first or depth-first with pruning explores the frontier. The language model thus plays all three roles: proposing moves, judging them, and being driven by the search controller.

ToT measurably helps on puzzles with branching choices and verifiable subgoals, like Game of 24 or crosswords, where lookahead and backtracking pay off. The cost is many more model calls per problem, and the evaluator can be miscalibrated, so the search may confidently expand a wrong branch; gains shrink on tasks where a single coherent chain already suffices.