Successive Halving

Successive halving spends an evaluation budget unevenly: it tests all candidates cheaply, discards the worse half, and gives the survivors a larger share, repeating until one remains. Jamieson and Talwalkar analyze the idea for best-arm identification and hyperparameter search. It is useful when evaluating each candidate fully is expensive, such as running many prompt or model configurations on a test set graded by a costly judge.

Procedure

Start with \(n\) candidates and a per-candidate budget \(b_0\) (for example a number of test cases or training steps). In each round:

1. Evaluate every surviving candidate with the current budget.
2. Keep the top half by score.
3. Double the per-candidate budget.

Stop when one candidate remains. With \(n = 2^r\) there are \(r+1\) rounds.

Budget arithmetic

With 16 candidates and 10 cases for each at the start, treat each round’s budget as a cumulative case count. In this example each survivor is evaluated again on that many cases, including cases from earlier rounds; earlier outputs are not reused. The table counts all evaluations, including those repeated:

round	candidates	cases each	cases spent
0	16	10	160
1	8	20	160
2	4	40	160
3	2	80	160
4	1	160	160

Each round costs the same because the candidate count halves while the cumulative budget doubles, so the total is the number of rounds times \(n b_0\), here 5 × 160 = 800 case evaluations. Evaluating all 16 candidates on 160 cases each would cost 2,560. The winner has 160 distinct cases of evidence, although some cases were evaluated repeatedly; most candidates are rejected after 10 to 20. Selection itself is complete after round 3, which costs 640 in total; round 4 only gives the winner more evidence. If prior outputs are reused and only newly added cases are evaluated, the same cumulative budgets instead cost 160+80+80+80+80=480 evaluations. If each round uses an entirely fresh batch of the displayed size, the cost stays 800 but the winner sees 10+20+40+80+160=310 distinct cases.

Does it pick the best candidate?

In a simulation, 16 candidates have true success rates drawn from a normal distribution (mean 0.70, standard deviation 0.05) and are measured with binomial noise, over 4,000 repetitions. Both plans spend 640 cases, the cost of rounds 0 to 3. Evaluating every candidate on 40 cases and picking the top scorer found the truly best one 28.9 percent of the time, with an average shortfall of 0.038 in true success rate. Halving from 10 cases found it 35.4 percent of the time with a shortfall of 0.027. At equal spend, halving does better, because it stops spending cases on candidates that are clearly behind. Neither is reliable at this budget: when candidates differ by about as much as the noise, a small test cannot separate them.

Pitfalls

• Early scores mislead. A candidate that is weak on 10 cases but strong on 160 is dropped. This is more serious when candidates improve at different speeds, as in training runs, where a slow starter can overtake a fast starter.
• Noise at small budgets. With few cases, scores are noisy and the cut at the median is nearly random among close candidates. Early rounds should use cases that separate candidates, not arbitrary subsets.
• Winner's curse. The final winner's score is biased upward, since it was selected partly for being lucky. The winner should be confirmed on fresh cases not used for selection.
• Reused cases. Evaluating on the same subset throughout can overfit to that subset.
• Choice of starting budget. The method needs a choice of \(n\) versus \(b_0\): many candidates with tiny budgets, or fewer with larger ones. Hyperband (Li et al.) addresses this by running successive halving several times with different trade-offs.

Neighbors

Equal allocation (grid or random search with a fixed budget per candidate) is simpler and gives unbiased comparisons but wastes budget on weak candidates. Successive halving is a bandit-style method of adaptive allocation. It does not choose which candidates to try, only how to spend evaluation on those already chosen.

References

• Li et al., Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization