skip to content

In a Tree of Thoughts search, what does beam width control, and what breaks at width 1?

level: juniorimportance: should knowfreq 55%

answer

  1. how many states survive a level
  2. not the same as branching factor
  3. width times branching equals candidates
  4. width 1 is greedy hill climbing
  5. no sibling left to fall back to

basics

~20 s

Beam width is how many partial reasoning states survive at each level of the tree before the next round of expansion. At width 1 only one path survives, so a bad early step can never be recovered.

solid answer

~50 s

Each level of a Tree of Thoughts run takes the states currently held, expands each into several candidate next thoughts, ranks the candidates, and keeps the top **w**. That **w** is the beam width. It decides how much of the tree you actually look at, and because every kept state is expanded next round it also multiplies the per-level cost: width is exploration you are paying for directly. At width 1 the search degenerates into greedy hill climbing. Whatever ranks first at level one is the only state that exists at level two, so if that ranking was wrong there is no sibling left to fall back to and nothing to backtrack into — the branching that justified the whole method is gone. A warehouse pick-path planner that keeps the best three route prefixes at each depth can still recover when the shortest-looking prefix strands the picker in the wrong aisle; at width 1 it cannot.

code

python · 11 lines
python
def beam_search(root, expand, score, width, depth):
    beam = [root]
    for _ in range(depth):
        candidates = [child for state in beam for child in expand(state)]
        beam = sorted(candidates, key=score, reverse=True)[:width]
    return beam[0]

expand = lambda s: [s + d for d in "159"]
score = lambda s: sum(int(c) for c in s)

print(beam_search("", expand, score, width=2, depth=3))  # 999

go deeper

for a junior

Be able to say plainly that beam width is how many partial states are carried to the next level, and that width 1 leaves a single path with no way back.

for a middle

Explain the arithmetic: width times branching is the candidates generated per level, and memory is proportional to width, not to depth. Distinguish width from branching factor without hesitating.

for a senior

Show how you would pick a width from measurement rather than taste — diversity of the survivors, whether the eventual winner was ever ranked first, and accuracy against width 1 on a held-out set.

for a principal

Own the framing that width is a purchased insurance policy against premature commitment, and that its value depends on how early the evaluation signal becomes discriminating. Argue when that insurance is not worth the token bill at all.

## What a beam is Tree of Thoughts treats reasoning as search over a tree of partial solutions. A node is a *state*: the sequence of thought steps taken so far, which is enough to say where the reasoning has got to. *Expanding* a node means asking the model for candidate next thoughts, producing that node's children. If every node has b children, level d holds b^d nodes, which becomes unaffordable within a handful of levels. A beam is the standard cap on that growth. After generating all candidates for a level, you rank them and keep only the best w. The next level expands those w states and nobody else. So the shape of the search is: constant width, growing depth. Total work per level is roughly w x b generations plus one evaluation per candidate, and total work is that figure times the depth — linear in depth rather than exponential. ## Width is not branching factor The two numbers are routinely confused in interviews. Branching factor b is how many candidate continuations you ask for *per state*; beam width w is how many states *survive* the level. With w = 3 and b = 5 you generate 15 candidates per level and throw 12 of them away. Widening the beam keeps more diverse lines of attack alive; widening the branching factor gives each surviving line more options to choose between. They cost the same in generation calls but buy different things: width buys insurance against a wrong commitment, branching buys a better local choice. ## Why width 1 is a different algorithm Set w = 1 and every level commits irrevocably to whichever candidate happened to rank highest. This is greedy search: no frontier, no siblings retained, no path back. It inherits the classic greedy failure — a locally attractive step that leads into a region with no good continuations. The search cannot notice, because by the time the dead end is visible, the alternatives at the fork have been discarded and nothing in the orchestrator remembers them. That matters most when the evaluation signal is weak early. In a route planner, prefixes of length two say very little about the total distance of a length-twelve route; scores only become discriminating deeper down. Keeping three prefixes alive lets the deeper evidence arbitrate; keeping one forces the decision while the evidence is still noise. ## Choosing a width There is no universal number, and interviewers do not expect one. The reasoning they want is: start narrow, measure, widen only where you can show it changes the answer. Widths in the low single digits are typical, because cost is linear in width and each extra slot has diminishing returns once the retained states stop being genuinely different from each other. Two practical checks: - **Diversity.** If the w survivors are near-paraphrases of one another, the extra width is buying nothing; the fix lives in how candidates are proposed, not in a bigger beam. - **Rank churn.** If the eventual winner was rarely ranked first at level one, width is doing real work and cutting it will cost accuracy. If the winner was almost always the level-one leader, the run is greedy in all but name and the beam is overhead. ## Anytime behaviour A beam also gives you something to return when the clock runs out. Because the beam holds a ranked set of live states at all times, a run cancelled mid-level still yields the best-so-far state rather than nothing. Width 1 gives you that too, but with no alternative to compare it against, so you cannot tell a confident answer from an unlucky one. ## Memory Width is also the memory profile. A beam search holds exactly w states (plus the candidate batch being ranked), independent of depth — much smaller than a full breadth-first frontier, which would hold b^d. This is why beam search is the usual breadth-first variant in practice: it makes the level-by-level structure affordable without keeping the whole level.

  • If you can only afford to double one number, would you double the beam width or the branching factor?
    It depends on where the failure is. If runs fail because the right line of attack was discarded early, widen the beam — that keeps more distinct lines alive. If runs fail because every candidate at a fork was mediocre, raise the branching factor so each surviving state has better options. Diagnose first by checking whether the eventual winner was ever in the beam at level one; if it was never generated at all, branching is the constraint.
  • How would you tell whether your beam is wider than it needs to be?
    Compare the run at width w against the same run at width w-1 and at width 1 on a held-out task set. If accuracy is flat from width 2 upward, the extra slots are paying for nothing. Also inspect the survivors: if they are paraphrases of each other, the beam is holding duplicates rather than alternatives, and the money would be better spent on more diverse proposals or on depth.

saying these in an interview costs you the question

  • Calling beam width the number of children per node
  • Assuming a wider beam makes the tree deeper
  • Thinking width 1 still backtracks on a dead end
  • Claiming beam search keeps the entire level in memory
  • Treating a bigger beam as always more accurate

context

resolving links…