skip to content

In Tree of Thoughts, how do branching factor, depth and beam width set the LLM call count?

level: middleimportance: must knowfreq 62%

answer

  1. is the frontier capped or not
  2. constant work per level with a beam
  3. exponential in depth without one
  4. calls linear, tokens grow with prefix
  5. latency is depth round-trips, not total calls

basics

~20 s

With a fixed beam, each level generates width x branching candidates, so generation calls total width x branching x depth — linear in depth. Without a beam the tree grows as branching^depth, which is why unpruned breadth-first search is unaffordable past a few levels.

solid answer

~60 s

Do the arithmetic level by level. A beam search holds w states, expands each into b candidates, and keeps the best w — so each level produces w x b candidate states and the whole run produces w x b x d of them, where d is the depth. Each candidate costs at least one generation and at least one evaluation, so the call count is roughly 2 x w x b x d, adjusted for whether you get b proposals from one call or from b calls, and for whether evaluation is batched. The point of the beam is what it removes. Unpruned, level d holds b^d nodes and the whole tree below the root holds b + b^2 + ... + b^d. With b = 3 and d = 4 that is 120 nodes; at d = 8 it is nearly 10,000. Capping the width converts exponential growth in depth into linear growth. When an interviewer hands you a configuration, quote both figures: the beamed cost and the unpruned cost it avoided.

code

python · 10 lines
python
def beamed(width, branching, depth, evals_per_candidate=1):
    candidates = width * branching * depth
    return candidates, candidates * evals_per_candidate

def unpruned_nodes(branching, depth):
    return sum(branching ** d for d in range(1, depth + 1))

print(beamed(width=4, branching=3, depth=4))   # (48, 48) -> 96 calls total
print(unpruned_nodes(branching=3, depth=4))    # 120 nodes if nothing is pruned
print(unpruned_nodes(branching=3, depth=8))    # 9840

go deeper

for a junior

Be able to multiply: width times branching gives the candidates per level, and multiplying by depth gives the run total. Know that without a beam the tree grows exponentially with depth.

for a middle

Separate candidates from calls. Say whether generation is one call per state or one per candidate, add the evaluation calls, and note that the prompt prefix grows with depth so tokens outrun calls.

for a senior

Turn the formula into a budget: pick width, branching and depth from a per-query cost and latency ceiling, and name the production leaks — retries, duplicate expansion, repeated scoring — that make the real bill exceed the estimate.

for a principal

Own the trade between cost, latency and accuracy across a whole workload: which request classes justify branching at all, whether the parallelism of a level-synchronous search is worth its extra total spend, and where a cheaper strategy buys the same outcome.

## The two regimes Everything about Tree of Thoughts cost follows from one question: is the frontier capped? **Uncapped (true breadth-first or exhaustive depth-first).** Every node at level d-1 is expanded, so the level sizes are b, b^2, b^3, ... and the total node count below the root is the geometric sum b + b^2 + ... + b^d. This is exponential in depth. With b = 3, depth 4 gives 120 nodes; depth 6 gives 1,092; depth 8 gives 9,840. Nothing about LLM calls being expensive changes the shape — it only moves the depth at which you run out of money from 'deep' to 'shallow'. **Capped (beam search, or depth-first with a cap on retries per node).** Only w states survive each level, so the level size is constant at w x b candidates and the total is w x b x d. Linear in depth. With w = 4, b = 3, d = 4 that is 48 candidate states, versus 120 unpruned — and the gap widens fast with depth. ## From candidates to calls Candidate states are not the same as model calls, and interviewers listen for whether you know the difference. - **Generation.** You can ask for b candidates in a single call (one prompt, b listed continuations) or make b separate sampled calls. The first is cheaper and lower latency; the second gives more independent, more diverse candidates. So per level you pay either w calls or w x b calls for generation. - **Evaluation.** Every generated candidate normally needs a score before ranking, which is at least one more call each, unless several candidates are scored in one prompt or a cheap non-model check filters obvious failures first. - **Bookkeeping.** Summarising a state, or re-emitting the accumulated prefix, adds tokens rather than calls, but token cost grows with depth because the prefix grows with depth. A run whose call count is linear in depth can still have a token bill that is quadratic in depth, since level d re-sends d thoughts of context. That distinction catches people out. A defensible back-of-envelope for a beamed run: calls is about w x b x d x (1 + e) where e is evaluation calls per candidate, and tokens is about that times the average prefix length, which itself scales with depth. ## Latency is a different sum Cost is a total; latency is a critical path. In a beam search the w x b expansions of a level are independent, so they can be issued concurrently and the wall clock is roughly d sequential rounds — depth round-trips, not w x b x d. This is the strongest practical argument for the level-synchronous shape: you buy parallelism. A depth-first search has no such structure; its calls are inherently sequential along the path, so its latency tracks the number of nodes it happens to visit. ## Where the estimate goes wrong in production Three things make real bills exceed the formula: 1. **Retries and refusals.** Malformed candidates that fail to parse get regenerated, so the effective b is higher than the configured one. 2. **Duplicate expansion.** Two branches reaching the same partial state, expanded twice, silently doubles a subtree's cost. 3. **Evaluation creep.** Scoring a candidate several times and averaging multiplies e, which is usually the largest term because it applies to every generated candidate rather than every surviving one. ## How to answer the arithmetic question When asked 'how many calls does this configuration imply', state the formula, plug the numbers, name the assumption you made about generation batching and evaluation, and then give the counterfactual. 'Forty-eight candidates, ninety-six calls if each candidate is generated and scored separately, four sequential rounds of latency; unpruned this would have been a hundred and twenty nodes and would keep tripling per extra level.' That answer shows the model of the cost, not just a number.

  • Your call count is linear in depth but the token bill is growing faster. Why?
    Because each state carries its accumulated thought prefix. At level d the prompt contains roughly d thoughts of context, so token cost per call rises with depth while the number of calls stays flat — the total lands closer to quadratic. Fixes are to summarise or truncate the prefix when passing a state down, or to pass a compact state description rather than the full transcript of how it was reached.
  • How does the cost picture change if you generate all b candidates in one call rather than b calls?
    Generation calls drop from w x b to w per level, and latency drops with them, so the total is dominated by evaluation instead. The trade is diversity: candidates written in one completion tend to be correlated, because the model sees its own earlier suggestions, so the effective branching factor is lower than b even though you paid for b. If the beam keeps filling with near-duplicates, that is the cause.
  • Where does concurrency help and where does it not?
    A level-synchronous beam search parallelises perfectly within a level: all w x b expansions are independent, so wall clock is about d rounds regardless of width. Depth-first search cannot do this along a single path, since each thought depends on the previous one; it can only parallelise across independent restarts. That asymmetry often decides the strategy for interactive latency budgets.

saying these in an interview costs you the question

  • Quoting branching^depth for a beam-capped search
  • Ignoring evaluation calls in the total
  • Assuming token cost scales exactly with call count
  • Confusing total cost with wall-clock latency
  • Forgetting retries inflate the effective branching factor

context

resolving links…