How do you cap token spend in a Tree of Thought run without losing the answer?
answer
- Cost is a product, not a sum
- Project the next level, not the last
- Cap output tokens per role
- Shared prefix served from cache
- Always return best-so-far
basics
~20 sTrack tokens per call against an explicit run budget, and gate each expansion on its projected cost rather than on spend already incurred. When the budget is exhausted, return the best-scoring node found so far instead of failing.
solid answer
~50 sMake the budget a first-class run parameter and enforce it at the expansion boundary. The trap is checking spend after the fact: one expansion of a twelve-node frontier at three children each is thirty-six proposer calls plus thirty-six evaluations, so a run sitting comfortably at 120k tokens can blow past 150k in a single step. The guard should therefore project the next expansion's cost — frontier width times branching factor times (prompt tokens plus capped output tokens) — and refuse to start it if that would overshoot, optionally narrowing the frontier instead of stopping outright. Two levers cut the cost itself: keep the shared task-and-rules prefix identical across sibling calls so it is served from prompt cache, and cap max output tokens per call, since an unbounded proposer response is the usual source of surprise spend. Because the loop always holds a best-so-far node, budget exhaustion degrades quality rather than producing nothing — which is what makes an aggressive cap safe to set.
code
python · 18 linesBUDGET_TOKENS = 150_000
def projected_cost(frontier, children_per_node, prompt_tokens, max_output):
calls = len(frontier) * children_per_node
propose = calls * (prompt_tokens + max_output)
evaluate = calls * (prompt_tokens + 8)
return propose + evaluate
def plan_expansion(spent, frontier, children_per_node, prompt_tokens, max_output):
while frontier:
cost = projected_cost(frontier, children_per_node, prompt_tokens, max_output)
if spent + cost <= BUDGET_TOKENS:
return frontier
frontier = frontier[:-1]
return []
frontier = [f"node-{i}" for i in range(12)]
print(len(plan_expansion(120_000, frontier, 3, 800, 200)))go deeper
Know that a tree run makes many calls, so it needs an explicit token budget and a cap on how long each response may be.
Explain why cost is a product of depth, width, branching and per-call tokens, and why the prompt grows with depth as each node resends its path.
Show the guard projecting the next expansion's cost, narrowing the frontier when it will not fit, returning the best node so far on exhaustion, and using prefix caching plus output caps to cut per-call spend.
Own the limits as policy: layered token, wall-clock and node caps with per-tenant aggregates, spend attributed by depth and role, and a defined contract for what a truncated result means to the caller.
## Why cost surprises are structural here A linear reasoning call has a cost you can bound by looking at one prompt. A tree run's cost is a product: depth times frontier width times branching factor times per-call tokens, and every one of those terms is a knob someone may turn without thinking about the other three. Worse, the per-call prompt grows with depth, because each node re-sends its path. The result is that ToT implementations routinely cost several times their estimate on the first real workload, and 'we added a token cap' is the single most common lesson learned. ## Count, do not estimate after the fact Every call — proposer, evaluator, retry — returns usage. Attribute it to the node that caused it and accumulate at the run level. Two accounting rules matter. Retries are charged to the same budget as first attempts, or a run 'stays under budget' while quietly spending double. And evaluation is charged separately from proposal, because the ratio between the two is a diagnostic: a run spending 70% of its tokens on scoring is telling you either that the frontier is too wide or that the evaluator prompt is carrying too much state. ## Project before you spend A guard that fires after the budget is crossed is a guard that fires late. The check belongs *before* an expansion, on a projection: projected = frontier_width × children_per_node × (prompt_tokens + max_output_tokens) The prompt-token term should use the actual rendered length for the nodes about to be expanded, not an average, since deep nodes carry longer paths. If spent plus projected exceeds the budget, you have three graceful options and one bad one. Narrow the frontier to the top-k nodes that fit; reduce the branching factor for this level; or stop and return the best node found. The bad option is starting the expansion and aborting mid-flight, which pays for calls whose results you discard. ## Making each call cheaper **Cache the shared prefix.** The task statement and the rules are identical across every call in an expansion — often dozens. Providers discount a repeated prompt prefix substantially, so putting the constant block first and keeping it byte-identical converts most of the input cost of a wide level into cache reads. This is the highest-leverage single change in most implementations. **Cap output tokens.** A proposer asked for one step should not be allowed to write five paragraphs. A hard output cap per role bounds the most variable term in the product and, as a side effect, keeps the state serialization compact for every descendant. **Keep state lean.** Because a node's path is resent on every child and every evaluation, a verbose state representation is multiplied by the whole subtree beneath it. Trimming the rendered path is worth more than it looks. **Prune before you score.** If a cheap check can reject a child, reject it before spending an evaluator call on it. **Split the roles by model.** Scoring is often a much easier task than proposing, and routing the two roles to different models is a standard cost lever — though how you choose and cascade models is a general serving concern rather than a ToT-specific one. ## The anytime property is the safety net The reason a hard budget is acceptable at all is that a search always has an incumbent: the highest-scoring node seen so far, complete or partial. When the guard trips, return that node with a flag saying the search was truncated, plus the spend and the depth reached. Callers can then decide whether to accept it, re-run with a larger budget, or fall back to a simpler path. A run that throws on budget exhaustion has converted a graceful degradation into an outage, and it is the most common implementation bug in this area. ## Layered limits A single token number is rarely enough in production. Useful layers: a per-run token budget; a wall-clock deadline, because latency and cost fail independently; a maximum node count as a cheap structural bound; and a per-tenant or per-day aggregate so that one pathological request cannot consume a shared allowance. Each layer should record which one tripped, because 'we hit the deadline' and 'we hit the token cap' call for different fixes. ## Attribution and regression detection Log spend per node and per depth. That is what lets you say 'depth four cost 60% of the run' and act on it, and it is what turns a cost regression after a prompt change into a diff rather than an investigation. A run summary with total tokens, tokens by role, cache-hit share, depth reached and which limit stopped the run is a small artefact that pays for itself the first week. ## What interviewers listen for The projection-not-retrospection point, the anytime return, prefix caching, output caps, and layered limits with attribution. Saying 'we set max_tokens' alone signals someone who has not yet watched one expansion of a wide frontier double a run's cost.
- Why is a check on tokens already spent insufficient for a tree run?Because spend moves in large discrete jumps. One expansion of a twelve-node frontier at three children fires seventy-two calls before any post-hoc check runs, so a run at 120k tokens can land at 180k in a single step. Gating on the projected cost of the next expansion catches the overshoot before you pay for it, and lets you narrow the frontier instead of stopping.
- What do you return when the budget trips mid-search, and what does the caller need to know?The best-scoring node found so far and the path to it, flagged as truncated. The caller should also see the depth reached, tokens spent, and which limit tripped — token cap, deadline or node cap — because those imply different remedies. Throwing on exhaustion turns a graceful degradation into an outage and is the most common bug in this area.
- Your run spends 70% of its tokens on evaluator calls. What does that suggest?Either the frontier is too wide for the value the scores add, or the evaluator prompt is carrying more state than it needs — often the full path where a summary of it would do. Both are fixable without touching the search: narrow the level, trim the state you render for scoring, or pre-filter children with a cheap check so fewer of them reach the evaluator at all.
saying these in an interview costs you the question
- Checks the budget only after an expansion completes
- Throws an error instead of returning the best node found
- Leaves proposer output tokens uncapped
- Reorders the prompt so the constant block is no longer first
- Counts first attempts but not retries against the budget