skip to content

How do you bound depth in a Tree of Thoughts run that must answer within a fixed latency budget?

level: seniorimportance: should knowfreq 42%

answer

  1. depth, wall clock and budget together
  2. always hold a best-so-far state
  3. unknown depth means deepen iteratively
  4. repetition is not free under a fixed beam
  5. say which cap actually fired

basics

~20 s

Set a hard depth cap plus a wall-clock and token cap, and keep a best-so-far state at all times so any cap that fires still returns an answer. When the needed depth is unknown, deepen iteratively — search to depth 1, then 2, then 3 — so every bound completed leaves a usable result.

solid answer

~50 s

Three bounds, and one property. The bounds are a depth cap derived from the task's expected solution length, a wall-clock deadline, and a token or call budget; whichever fires first stops the search. The property is **anytime behaviour**: the run must always hold a best-so-far state so that stopping is a degradation, not a failure. When you cannot predict the depth — a multi-hop research question that might resolve in two hops or four — iterative deepening is the honest answer. Search to depth 1, return the best; then to depth 2, and so on until the deadline. Every completed bound is a shippable answer and you never over-commit to a depth the budget cannot reach. Be candid about the cost: with a fixed beam the per-level cost is roughly constant, so deepening to depth D costs about (D+1)/2 times a single depth-D run — real overhead, bought in exchange for never returning nothing.

code

python · 7 lines
python
per_level = 12  # beam width 4 x branching factor 3
max_depth = 5

direct = per_level * max_depth
deepening = sum(per_level * d for d in range(1, max_depth + 1))

print(direct, deepening, deepening / direct)  # 60 180 3.0

go deeper

for a junior

Know that a thought search needs an explicit depth limit because nothing stops the model proposing another step, and that the run should keep its best answer so far.

for a middle

Explain the three caps that run together — depth, wall clock, token or call budget — and what iterative deepening is: repeated searches with a rising bound so every pass leaves a usable answer.

for a senior

Show how you derive the cap from observed solution depths and from budget inversion, make the run anytime, and report which cap fired so a truncated answer is never mistaken for a complete one.

for a principal

Own the judgement of whether the deepening multiplier is worth paying for a given workload, and the conclusion that a task whose affordable depth is below its needed depth should not use branching search at all.

## Why depth needs an explicit bound A thought tree has no natural floor. The model will happily propose a next step from any state, including states that have already wandered off the problem, so without a cap the search terminates only when a goal test passes — which may be never. Depth is therefore the primary safety bound, and it is a design input, not an afterthought. Where the number comes from: - **Known task structure.** If the task decomposes into a fixed number of stages, the depth is that number, possibly plus one for a final consolidation step. - **Observed solution length.** Run the task set once with a generous cap, record the depth at which correct answers were actually found, and set the cap somewhere above the high percentile of that distribution. - **Budget inversion.** If the per-level cost is w x b calls and the budget allows N calls, the affordable depth is N divided by that. When the affordable depth is below the observed solution length, the honest conclusion is that this task is not affordable with branching search — not that you should shave the beam until it technically fits. ## Depth is not the only cap Depth alone does not bound latency, because level cost varies: retries, slow evaluations, and oversized prefixes all stretch a level. Production runs carry three caps together — depth, wall clock, and total calls or tokens — and stop on the first. State clearly which one fired, because that is the difference between 'the search finished and this is its answer' and 'the search was cut off and this is the best it had'. Downstream consumers should treat those differently, and a run that cannot report which happened is under-instrumented. ## Anytime behaviour An anytime algorithm always has an answer available and improves it given more time. Making a thought search anytime costs little: keep the highest-ranked complete state seen so far, and if none is complete, keep the highest-ranked partial one along with the fact that it is partial. Then any cap firing yields a degraded result rather than an exception. This matters most in interactive settings. A research assistant answering a multi-hop question inside a few seconds should return a two-hop answer with its supporting evidence rather than time out because four hops did not fit. The user-visible contract becomes 'an answer, with a confidence and a note about the depth reached', which is far more useful than an error. ## Iterative deepening When the required depth is unknown, repeatedly search with an increasing bound: depth 1, then depth 2, and so on until the deadline or a goal test passes. Properties: - **Every bound completed is a shippable answer.** This is what makes it a natural fit for anytime behaviour. - **No commitment to a guess.** You never gamble the whole budget on a depth the task may not need or the budget may not reach. - **It repeats work.** The classic argument that repetition is nearly free relies on the deepest level dominating an exponentially growing tree. That argument does not hold under a fixed beam, where each level costs about the same w x b. Deepening to depth D costs the sum 1 + 2 + ... + D levels rather than D levels, so roughly (D+1)/2 times as much. At D = 5 that is three times the cost of a single depth-5 run. Whether that overhead is acceptable is a judgement call and interviewers are looking for you to make it explicitly. If the depth distribution is tight, guess the depth and cap it. If it is wide, and if returning something is much better than returning nothing, deepening earns its multiplier. A middle path is to start at a bound near the observed median rather than at 1, which skips the cheapest and least useful passes. ## Failure modes to name - **A cap with no anytime state** turns every timeout into a total loss. - **A depth cap set from the happy path** silently truncates the hard cases, and the metric that suffers is accuracy on exactly the queries that needed the search. - **Deepening without a deadline** removes the very bound it was meant to provide; the loop still needs a wall-clock stop. - **Reporting a truncated result as final** hides the degradation from whatever consumes the answer.

  • Why is iterative deepening more costly, relatively, in a beamed thought search than in classic exhaustive tree search?
    Classic iterative deepening is cheap because the tree grows exponentially, so the deepest level dwarfs everything above it and re-walking the shallow levels adds a small constant fraction. A fixed beam removes that growth: every level costs about width times branching, so the levels are equal in cost and repeating them is a linear multiplier. Deepening to depth D costs roughly (D+1)/2 times a direct depth-D run.
  • How do you choose the depth cap when you have no prior runs to learn from?
    Invert the budget: divide the affordable call count by the per-level cost and take the depth that fits, then sanity-check it against how many steps a human would need for the task. Run a small pilot with a generous cap purely to observe where correct answers actually appear, and reset the cap from that distribution. If the affordable depth sits below the observed one, the correct conclusion is that branching search does not fit this budget.
  • What should a run return when the wall-clock cap fires mid-level?
    The best-so-far state, explicitly labelled as truncated, together with the depth reached and which cap fired. Discard the half-finished level rather than ranking it against complete states, since its candidates are unscored and not comparable. Downstream logic can then decide whether a depth-2 answer is acceptable for this request or whether it should be retried with a larger budget.

saying these in an interview costs you the question

  • Relying on depth alone to bound latency
  • Returning nothing when the deadline fires
  • Claiming iterative deepening is essentially free
  • Setting the depth cap from happy-path runs only
  • Presenting a truncated result as a completed search

context

resolving links…