Replanning, Branching, and Search Budgets

Adding calls to a compound system improves the answer, and then makes it worse. The curve goes up and comes back down. Chen and colleagues measured the turn in 2024. They ran majority-vote (Vote) and filter-then-vote (Filter-Vote) systems on MMLU Physics, TruthfulQA, GPQA and AVERITEC. Their introduction states it plainly: “Specifically, although one might expect their performance to monotonically increase as more LM calls are invoked, we have identified a surprising phenomenon, across multiple language tasks, exhibited by these systems: growing the number of LM calls initially improves performance but then degrades it, as shown in Figure 1.”

The mechanism is simple. Extra calls help easy queries and hurt hard ones, so the aggregate curve turns over. The direction is not even uniform across systems on the same benchmark. On MMLU Physics, Vote first increases then decreases; Filter-Vote first decreases then increases. A run that produces thirty candidates and evaluates none of them rigorously is not buying a probability of correctness. It is buying a position on a curve nobody in the room has plotted.

Branches are proposed. A cheap filter removes most of them, an evaluator ranks what survives, a budget policy says when to stop, and a selection rule decides what leaves the building. AlphaCode ran exactly that pipeline with a number on every box. DeepMind published it in Science in 2022.

The sampler produced up to one million programs per problem. The problem's own example tests were the cheap filter: “Filtering removes approximately 99% of model samples, although the exact amount depends on the problem and model, and filtering can still leave tens of thousands of candidate samples for many problems.” The survivors were clustered by behaviour, and at most 10 were submitted. The actual average was 2.4 submissions per problem solved. That bought a top 54.3% placing across 10 Codeforces contests.

The budget policy is where the honesty lives. On the validation set the 41B-plus-clustering system went from 21.0% at 10@1k to 34.2% at 10@1M. A 1000x sample budget bought about 13 points. Two separate decisions hide in that sentence: how much to spend, and what to hand over. They should not share an owner or a test.

Planning search creates multiple candidate actions or plans, evaluates them, and chooses or expands promising branches. It can help when errors are detectable and alternatives differ meaningfully. The multiplication of model calls, tools, context, and merge complexity is charged the moment you fan out. Without strong evaluators, search may select the most persuasive candidate rather than the most correct one.

There is a ceiling on the fan-out, and the compute budget is not what sets it. Stroebl and colleagues showed that an imperfect verifier's false-positive rate caps what resampling can deliver, whatever you spend. Once false positives carry a cost, the optimal number of attempts collapses: “Empirical results show that optimal sampling attempts are often fewer than 10, as the negative utility of false positives outweighs benefits, bending inference scaling curves downward.” At a cost-benefit ratio of 4, the optimal number of samples was K ≤ 5. That held for all four models they tested, drawn from the Llama-3.1 and Code Llama families on HumanEval/HumanEval+. If the ratio is high enough, the optimal K is zero. Sometimes the correct amount of search is none.

Give a branching experiment a fixed budget and run the single-branch baseline at the same cost. Two of the five steps below have published settings you can copy rather than invent: choosing evaluators, and allocating compute.

Choose evaluators. Hold the search constant, change only the scorer, and watch where the points actually come from. Lightman and colleagues ran best-of-N over 1,860 sampled solutions per problem, on 500 held-out MATH problems. Then they swapped the evaluator. The process-supervised reward model solved 78.2%, the outcome-supervised reward model 72.4%, and majority voting 69.6%. Their comment on the figure: “While the ORM performs slightly better than the majority voting baseline, the PRM strongly outperforms both.” With the amount of search fixed, the evaluator moved the result by 8.6 points. The better scorer has a price, and it is stated in labels. The training set behind it, PRM800K, contains 800K step-level labels across 75K solutions to 12K problems.

Allocate compute. A budget policy can be a mechanism rather than an instruction. The s1 paper, published in 2025, implements one it calls “budget forcing”. It terminates or extends the model's thinking by appending the word “Wait”. The model was finetuned on just 1,000 curated questions (s1K). The abstract reports: “Further, scaling s1-32B with budget forcing allows extrapolating beyond its performance without test-time intervention: from 50% to 57% on AIME24.” A budget is a knob someone can turn and measure, not a paragraph in a design document.

With diversity defined, hard filters in place, an evaluator chosen, and compute allocated, the final comparison should expose “Search amplifies evaluator weaknesses” and preserve evidence for “Additional branches increase verified task success at a known cost”.

Search should be an ablated mechanism. If it does not beat a simpler run under equal budget, remove it.

That ablation has been run the honest way. Snell and colleagues allocated test-time compute adaptively per prompt and priced it against a fixed baseline: “Using this compute-optimal strategy, we can improve the efficiency of test-time compute scaling by more than 4x compared to a best-of-N baseline.” The comparison that carried the claim was FLOPs-matched. On problems where a smaller base model already attains somewhat non-trivial success rates, test-time compute can be used to outperform a model 14x larger. Not more search. Better-allocated search, priced against an equal budget and against the alternative of simply buying a bigger model.

The person who turns search on owns “Search amplifies evaluator weaknesses”. The evidence that keeps bounded plan search in the system is “Additional branches increase verified task success at a known cost”.