In Tree of Thought, how do you parallelize and retry branch calls safely?

## The parallelism is free and you should take it A tree run makes many more calls than a linear one, and almost all of them are independent. Every proposer call for the nodes on the current frontier can go out at once; every evaluator call for the children just produced can go out at once. If you write the loop with a naive for-comprehension over nodes, wall-clock time scales with the number of calls, and a run that could have taken twenty seconds takes six minutes. Concurrent fan-out per level is the single biggest latency win in a ToT implementation, and it is why the pattern is tolerable interactively at all. The constraint is that the *levels* are sequential — you cannot expand a child before it exists — so the achievable speedup is bounded by depth. Describe the shape as 'parallel within a level, serial across levels' and you have said the useful thing. ## Bounded, not unbounded Fire-and-forget concurrency across a wide frontier will hit provider limits immediately and turn a search into a retry storm. Run the fan-out through a bounded worker pool sized to your rate allowance, with the ordinary client-side protections you would apply to any high-volume LLM workload. What is specific to a tree is that the pool is shared between two roles with different urgency: if evaluator calls queue behind a flood of proposer calls, the frontier cannot be pruned and the next level will be even wider. Separate queues, or a simple rule that evaluation for the current level is drained before the next level's proposals begin, avoids that self-amplifying widening. ## Expansion as a barrier Ranking is a comparison, so it needs the full set. If you rank as results trickle in, you are comparing whoever returned first, and a slow-but-excellent candidate can be pruned because it arrived after the cut. Make the expansion an explicit barrier: gather all sibling results (or their terminal failures), then score, then prune. The cost is that the level takes as long as its slowest call, which is why per-call timeouts matter more here than in a single-shot pipeline — one hung call should not stall a level. A timeout that converts a straggler into a recorded failure is better than a level that waits indefinitely for it. ## Two failure kinds, two policies This is where most implementations are subtly wrong. **A failed proposer call** removes a candidate that never existed. The search degrades gracefully: you expand the node with three children instead of four. Retry once if it is cheap, then continue. Record the gap so you can see later whether a whole level was thin. **A failed evaluator call** leaves an existing node without a score, and the tempting shortcuts are all wrong. Scoring it zero prunes it — you have invented evidence against a candidate you never examined. Scoring it maximum promotes it — you have invented evidence for it. Copying a sibling's score is worse still. The correct options are to retry the evaluation, or to mark the node `unknown` and either exclude it from this round's ranking while keeping it in the store, or carry it forward at a defined default that your logs make visible. Whatever you pick, it must be a deliberate, recorded policy rather than an accidental `score or 0`. ## Determinism under concurrency Concurrency introduces nondeterministic completion order, and completion order must never influence the search. Two habits fix this. First, assign each child a deterministic id at creation — parent id plus an index derived from the request order, not from the response order. Second, sort by that id before ranking, so ties break identically on every run. Without this, two runs with identical prompts, identical seeds and identical scores can explore different subtrees, and you will spend an afternoon chasing a 'flaky' search that is really a flaky sort. ## Retries and budget accounting Every retry costs tokens, and the budget must see them. A retry counter that increments the node's spend, and a rule that retries draw from the same run budget as first attempts, prevents the failure mode where a run 'stayed under budget' while quietly spending double on retries. Retries should also be idempotent in the sense that matters here: re-render the same prompt from the same stored state rather than rebuilding it from mutated state, so the retried call is genuinely the same call. ## What good answers include Parallel within a level, bounded pool, explicit barrier before ranking, per-call timeouts, distinct policies for proposer versus evaluator failure, deterministic child ordering, and retries charged to the budget. Candidates who mention only 'use async' have not yet been bitten by a level that pruned the right answer because it arrived third.