Wiki
Advanced12 min read

Search over thoughts

Instead of one chain, grow a tree of candidate thoughts, score them, and search. Tree of Thoughts, best-of-N, and MCTS-style deliberation — and their cost.

A single chain-of-thought commits to one path and walks it to the end, even when an early step was a dead end. Search over thoughts instead grows several candidate next-steps, scores them, expands the promising ones, and can backtrack — turning deliberation into the same explore-and-exploit problem that made game-playing systems strong.

Start here

One chain is a single sample. A tree is a search: generate several candidate thoughts, ask which look promising, keep the good branches, and drop the rest. Backtracking is the payoff — the ability to abandon a wrong turn instead of reasoning further down it.

One hard problem, one model — only the thinking budget changes

thinking tokens spent →accuracy50%

Problem: "A farmer has 24 apples in three baskets. The second basket has twice the first; the third equals the first. How many in each?"

sets up equations

a + b + c = 24, b = a + c, and 'twice' means b = 2a → c = a, so 4a = 24 → a = 6, b = 12, c = 6… but let me check the 'twice' reading before committing — could also mean b = 2a only, with c free…

The characteristic shape: steep early gains as the budget buys actual setup and self-checking, then a plateau — extra thinking rarely rescues a model past its ceiling. Curve and samples are illustrative; on easy problems the curve is flat from token zero, and the cost is paid in latency whether or not accuracy moves.

The underlying lever is the same: more test-time compute, spent better. Search is what "spend it better" looks like when a single chain plateaus.

Tree of Thoughts

  • Generate — from a state, produce several candidate next thoughts.
  • Evaluate — score each candidate, either by the model or a value function. This step is the weak link: a bad evaluator searches badly.
  • Select and expand — keep the best, discard the rest, recurse.
  • Backtrack — if a branch stalls, return to an earlier node and try another. This is what a single chain cannot do.

Search strategies

  • Best-of-N — sample N complete answers, pick the best. Parallel, simple, no backtracking.
  • BFS / DFS over thoughts — breadth or depth-first exploration of the candidate tree, guided by the evaluator.
  • MCTS-style (LATS) — simulate, score, and back-propagate values to balance exploring new branches against exploiting good ones, unifying reasoning, acting, and planning in one tree.

Careful

Search multiplies cost — N branches means roughly N× the tokens — and it is only as good as its evaluator. If the model cannot tell a good partial thought from a bad one, a bigger tree just explores more of the wrong space. On many tasks a single long chain beats an elaborate search; reach for the tree when the task genuinely branches and the branches are scoreable.

Check yourself

Eduspheria wiki · Agentic AI, Planning & reasoning

0 / 5 answered

  1. 1A single chain uses about 2,000 tokens and a best-of-N search samples 5 branches. Roughly how many tokens does the search spend?
    Numeric answer
  2. 2What can a tree of thoughts do that a single chain cannot?
    Multiple choice
  3. 3A bigger search tree always improves the result, even with a weak evaluator.
    True / false
  4. 4Which strategy samples N complete answers in parallel and picks the best, with no backtracking?
    Short answer
  5. 5In Tree of Thoughts, which step does the lesson call the weak link?
    Multiple choice

Next: what to do when the plan itself is wrong.