skip to content

How do you spend a fixed evaluation budget across candidates in a prompt search?

level: principalimportance: should knowfreq 40%

answer

  1. most evaluations go to already-lost candidates
  2. cheap screen first, deep evaluation last
  3. successive halving doubles items for survivors
  4. same items for everyone, paired comparison
  5. budget in tokens and money, not items

basics

~20 s

Spend unevenly. Score every candidate cheaply on a small shared subset, eliminate the clearly weak ones, and reallocate the saved evaluations to survivors — successive halving. Budget in model calls and tokens, not candidate counts, and reserve capacity to confirm finalists.

solid answer

~60 s

Uniform allocation is the wasteful default: beam width four, ten generations, four proposals each, 200 items per candidate is already tens of thousands of calls, and most of them go to candidates that were obviously weak after twenty items. Adaptive allocation fixes that. **Successive halving** scores all candidates on a small shared subset, drops the bottom half, and doubles the per-candidate item count for survivors, so evaluation depth grows only for candidates still in contention. **Racing** stops evaluating a candidate as soon as it is confidently worse than the incumbent. Both need care: rankings on twenty items are extremely noisy, so use the *same* items for every candidate (paired comparison), stratify the subset so it is not accidentally all easy cases, and never eliminate on a margin smaller than the noise at that sample size. Finally, budget in money and tokens rather than item counts — a long chain-of-thought candidate can cost several times a terse one per item — and hold back budget for a clean confirmation run on untouched data.

code

python · 6 lines
python
def successive_halving(candidates, score_on, item_subsets):
    survivors = list(candidates)
    for items in item_subsets:
        ranked = sorted(survivors, key=lambda c: score_on(c, items), reverse=True)
        survivors = ranked[: max(1, len(ranked) // 2)]
    return survivors[0]

go deeper

for a junior

Know that each candidate evaluation costs real model calls, so a search has a budget, and that cheap early screening avoids paying full price for obviously weak prompts.

for a middle

Explain successive halving concretely — small shared subset, drop the weakest, more items for survivors — and why every candidate in a round should be scored on identical items.

for a senior

Balance efficiency against the risk of cutting a good candidate early: stratified subsets, elimination margins above the noise, and a reserved budget for deep re-scoring of finalists.

for a principal

Own the economics: define the objective as quality subject to serving cost and latency, set the spend cap and the schedule for the whole team, and instrument whether allocation is too uniform or too aggressive.

## The budget is the design In a gradient-free prompt search the dominant cost is evaluation. Multiply it out for a routine configuration: beam width 4, ten generations, four proposals per incumbent, 200 evaluation items per candidate. That is 16 candidates scored per generation, 3,200 item-evaluations per generation, 32,000 model calls for the run — before any judge calls, and before retries. Under that arithmetic, the interesting question is not which search algorithm is theoretically best but how to convert a fixed number of calls into the most improvement. Allocation is where most of the leverage sits, because the naive policy — score everything on everything — spends the majority of the budget resolving comparisons that were already decided. ## Uniform versus adaptive allocation Uniform allocation gives every candidate the same number of evaluation items. It is simple, gives every candidate the same measurement precision, and makes the aggregate numbers easy to compare. It is also obviously wasteful: a candidate that is wrong on fifteen of its first twenty items does not need the other 180 to be ruled out. Adaptive allocation makes precision a function of how much a candidate still matters. - **Successive halving.** Evaluate all N candidates on a small shared subset. Rank, keep the top half, double the per-candidate item count, repeat. Total spend stays roughly constant per round while the survivors get progressively more reliable measurement. By the final round only two or three candidates are being scored, and they are being scored deeply enough that the choice between them means something. - **Racing / bandit-style allocation.** Treat each candidate as an arm and pull the promising ones more. Evaluate incrementally, maintain a confidence interval on each candidate's score, and eliminate a candidate the moment its interval is entirely below the leader's. This spends effort exactly where the ranking is still ambiguous. - **Best-of-N with a cheap prefilter.** Screen candidates on a very cheap signal first — well-formedness, schema conformance, an obviously-broken-output check — before spending any evaluation items on them. A surprising share of automatically generated candidates fail this and cost nothing to discard. ## The hazard: eliminating a good candidate early Aggressive allocation trades budget efficiency for the risk of discarding a strong candidate on a noisy twenty-item read. Three practices keep that risk manageable. **Use common items.** Every candidate in a round should be scored on the *same* items, so comparisons are paired and item difficulty cancels out of the difference. This is the single cheapest variance reduction available, and it makes small subsets far more informative than their raw size suggests. **Stratify the subset.** A random twenty items may contain no hard cases, no rare classes, and none of the edge conditions you actually care about. Stratify by class and difficulty so early rounds test the same skills the final metric rewards; otherwise successive halving optimizes for whatever the easy subset happens to reward. **Eliminate on a margin, not on a rank.** Drop a candidate only when it is behind by more than the sampling noise at the current sample size, and prefer to promote ties rather than break them arbitrarily. A tie at twenty items is not information. ## Wide-and-shallow versus narrow-and-deep A fixed budget forces a choice between exploring many candidates with imprecise measurement and refining a few with precise measurement. When the landscape is rugged and you have not yet found a good region, wide-and-shallow pays: you are looking for a large signal, and large signals survive noisy measurement. Once candidates are close together, the remaining differences are small, and only deep evaluation can resolve them — so late rounds should be narrow and deep. Successive halving is essentially an automatic schedule for that transition, which is why it is the default worth reaching for. ## Budget in the right unit Item counts are a poor currency. Candidates differ in prompt length, in whether they induce long reasoning, and in output length; one candidate can cost several times another per item. Track spend in tokens and money, cap per-candidate cost, and make the cap visible to whatever generates candidates, so the search does not silently drift toward expensive prompts that win on quality while destroying the production latency and cost budget. In many real settings quality-per-token is the objective you actually want, and a prompt that gains one point while tripling cost should lose. ## Operational levers Evaluation across candidates is embarrassingly parallel, so throughput is usually bounded by provider rate limits rather than by compute. Structuring rounds so a whole generation can be scored concurrently is worth more than a cleverer search rule. Deterministic scoring settings reduce variance and therefore reduce the items needed per comparison. And a fixed reserve of budget — commonly ten to twenty percent — should be held back to re-score the finalists on data the search never selected on, because the search's own argmax is not a trustworthy final answer. ## Knowing when the budget is misallocated Two diagnostics matter. If most spend goes to candidates eliminated in the first round, allocation is too uniform. If final rankings reorder substantially when finalists are re-scored deeply, allocation was too aggressive and the search has been selecting on noise. Instrument both; they are the feedback loop that tunes the schedule.

  • How would you pick the size of the first-round evaluation subset?
    Work from the effect size you need to detect in that round. Round one only needs to separate clearly-broken candidates from plausible ones, which is a large gap, so a small stratified subset suffices. Later rounds must resolve small differences and need far more items. Sanity-check the choice by re-scoring a few first-round eliminations deeply once: if strong candidates were being cut, the subset is too small or not stratified.
  • When would you deliberately choose uniform allocation instead?
    When candidate count is small and you need every measurement to be comparable — for example a final comparison of three finalists that will be reported, or a regression check across releases where consistent methodology matters more than efficiency. Uniform allocation is also safer when candidates differ wildly in behaviour on rare classes, since adaptive schedules can eliminate a candidate that is excellent exactly where the small subset is thin.
  • How do latency and cost of the candidate prompt itself enter the objective?
    They belong in the objective, not just the budget. A prompt that adds long reasoning may gain a point of accuracy while multiplying per-request cost and latency, which can be a net loss in production. Score candidates on quality subject to a cost or latency cap, or optimize an explicit quality-per-token objective, so the search cannot win by spending resources you would refuse to spend at serving time.

saying these in an interview costs you the question

  • Scores every candidate on the full evaluation set every round
  • Eliminates candidates on rank differences smaller than the noise
  • Uses a different random sample of items for each candidate
  • Counts budget in candidates rather than tokens or dollars
  • Leaves no budget to re-confirm finalists on untouched data

context

resolving links…