Does Test-Time Search Still Pay Off When the Benchmark Is New?

Language models can be made more accurate at deployment by spending more computation per question. They can sample many candidate solutions and keep the best one, or run a beam search, which keeps the top few partial solutions at each step and extends them. They can also run a short "look-ahead" before committing to each next step. These test-time compute methods are mostly validated on public benchmarks such as GSM8K and MATH, which have very likely leaked into training data. They are also mostly validated by checking only the final answer. Both habits can inflate the apparent value of search. If the model has seen a problem before, the scorer that ranks candidates finds it easy to tell right from wrong, so a wider search looks helpful. And if only the final answer is graded, a search that finds lucky trajectories looks the same as one that actually planned.

This proposal measures how much of the reported benefit of test-time search survives when both inflations are removed, and turns that measurement into a practical rule. The rule is to choose the search width from the scorer's reliability measured on freshly generated, structure-matched problems, not on the public benchmark. Procedurally generated tasks give exact ground truth for every intermediate step, not just the answer. We can therefore also count how often wider search selects answers that are "right for the wrong reasons," and how often it walks into the specific short-sighted traps that look-ahead is supposed to prevent.

Core Claim

More Test-Time Compute Can Hurt models beam search with extreme value theory, the statistics of the maximum of many noisy draws. It shows that a noisy scorer gives incorrect paths a "lucky maximum" bonus that grows with the candidate pool. As a result, the largest useful beam width scales as

$$\hat{k} \propto \exp\!\left((\Delta/\sigma)^2\right),$$

where $\Delta$ is the average score gap between correct and incorrect candidates and $\sigma$ is the scorer's noise. In that paper, perplexity scoring sits at $\hat{k}=1$ and a process reward model sits at $\hat{k}\ge 4$, on the static MR-BEN benchmark. A process reward model is a scorer trained to grade each reasoning step rather than only the final answer.

Our hypothesis is that familiarity inflates $\Delta/\sigma$. On memorized items both the generator and the scorer are confident and well separated. On items that share the structure but not the surface form, the separation shrinks, and because the dependence is exponential, $\hat{k}$ shrinks sharply. If this holds, three predictions follow.

First, the slope of accuracy against compute should flatten in a fixed order: largest on public items, smaller on perturbed versions of the same items, smallest on matched procedurally generated ones.

Second, the scorer-reliability estimate measured on a cheap procedural "twin" should predict the empirically best search width on genuinely new tasks. The same estimate measured on the public benchmark should not.

Third, under outcome-only selection, widening the search on fresh tasks should increase the share of correct answers whose intermediate trajectory is wrong. It should also leave the short-sighted trap rate largely unchanged.

The idea treats test-time compute as the mechanism under study, contamination as the variable we control, outcome-only grading as the measurement flaw we remove, and short-sightedness as the specific failure that look-ahead claims to fix.

Research Program

The core artifact is a three-arm evaluation built so that each pair of arms isolates one effect.

Arm A (public items). These are original items from GSM8K and from the logic sets used by Logical Reasoning with Outcome Reward Models for Test-Time Scaling.

Arm B (perturbed items). These keep each public item's reasoning graph but change the numbers, names and wording. This preserves structure and semantic priors while breaking verbatim recall.

Arm C (procedural items). These are new problems generated with DyVal's graph-based generator, which composes problems as directed acyclic graphs of intermediate quantities, matched to the Arm B items in depth and node count.

The pairwise contrasts then read as follows. The difference between Arms A and B estimates the memorization effect. The difference between Arms B and C estimates the effect of natural-language semantic priors. We report the two separately because they are different things.

For agentic tool use we build the same three-way split on FuncBenchGen, which generates function-calling tasks as dependency graphs. One arm renders each graph with natural API names and types resembling public tool benchmarks. The other uses FuncBenchGen's randomized identifiers. FuncBenchGen matters here because it defines a precise short-sighted failure: the "connected irrelevant node," a type-compatible function that looks callable but leads nowhere. Its graph tells us exactly which calls were correct.

Because every intermediate value in DyVal and every call in FuncBenchGen is determined by the generator, we compute process correctness exactly, with no model acting as judge. This addresses the open problem, noted for outcome-bias research, of getting step-level ground truth without subjective grading. On each trajectory we record four things: whether the final answer is correct, the first incorrect intermediate state, whether a correct answer was reached despite an incorrect intermediate (right for the wrong reasons), and the number of irrelevant-node calls.

We sweep four selection methods across compute budgets matched in generated tokens: best-of-N with an outcome reward model, beam search with perplexity, beam search with a process reward model, and Predictive-Decoding. For every scorer and arm we estimate $\Delta/\sigma$ directly from the candidate pools. Using the extreme-value relation, we then predict $\hat{k}$ and compare it with the empirically best width.

The practical output is a calibration rule. Before deploying search on a domain, generate a few hundred procedural twins at roughly $0.016 per item, the cost reported for code-verified generation by A²RBench. Measure the scorer's separation on those twins and set the width from it.

Baselines

Greedy decoding with zero-shot chain-of-thought. This is the naive reference point: a single sample, no search. It is run on every arm, with the same prompt across arms. Every compute curve is reported relative to it. A method that does not beat greedy decoding on Arm C at matched tokens has shown no transferable benefit.

Predictive-Decoding. This comes from Non-myopic Generation of Language Models for Reasoning and Planning. Before committing to each step, it samples several look-ahead rollouts and reweights the current step by how well those futures score. It is the strongest competitor because it is explicitly designed to fix short-sighted decoding, and it is the only method in the file reported as both cheaper and better than tree search. It reports a 7.2% accuracy gain for Llama-3-8B on GSM8K, beating Monte Carlo tree search by 2.4% with 50% of the FLOPs. It also reports a 25.3% success-rate gain over ReAct on AlfWorld. We run it with its own released settings, the same Llama-3-8B backbone, and the same token budgets as the other methods, tuning its rollout count on Arm A only. Beating it means our calibrated-width search matches or exceeds its Arm C accuracy at equal tokens. Independently of accuracy, we test whether its own gain on Arm C retains less than half of its Arm A gain, which would confirm the inflation hypothesis.

Process-reward-model beam search. This is the strongest scorer-based baseline in the file. More Test-Time Compute Can Hurt reports that Mistral improved by 8.9 percentage points at $k=4$ on MR-BEN with process reward model scoring. With perplexity scoring, Llama-3.1-8B lost 5.4 percentage points at $k=4$ relative to $k=1$. We reproduce both on Arm A and then run them unchanged on Arms B and C.

Outcome reward model best-of-N. Logical Reasoning with Outcome Reward Models for Test-Time Scaling trains a scorer on final answers only and reports that it improves Gemma-1B accuracy by nearly 30%. This baseline is where right-for-wrong-reasons selection should be most visible.

FuncBenchGen variable-state reminder. This is the simplest non-search baseline. The environment restates the variables known so far, which raised GPT-5 from 62.5% to 81.3% on specific tasks. GPT-5 still falls from about 90% at depth 1 to below 30% at depth 4. We give reminders to every method in a separate condition.

Width ablation. The key ingredient is the width chosen from procedural-twin calibration. Its ablation is identical search with the width tuned on Arm A. The difference between the two on held-out procedural items isolates the value of calibrating on fresh structure.

Why not just…?

Why not just run best-of-N on DyVal and report accuracy? That is half of this study. On its own it cannot separate structural difficulty from lost familiarity, because DyVal items differ from GSM8K in both respects at once. Its outcome-only grading would also hide whether the extra accuracy came from lucky final answers. The perturbed middle arm and the exact step-level labels are what make the result interpretable. If the A-to-B gap turns out negligible, we will report that contamination does not inflate search gains on these models. That would be a useful negative result.

Why not just add state reminders instead of searching? This is a real threat on shallow tool tasks, given the gain from 62.5% to 81.3%. FuncBenchGen's own results show reminders do not fix depth or irrelevant-node traps: success remains at 15% on 20-call tasks. Our reminder-plus-search condition settles where each helps. If reminders alone match search at every depth on the randomized-identifier arm, we will conclude that the bottleneck is memory and not short-sightedness, and that look-ahead is not worth its cost there.

Why not just use an LLM analyst to grade reasoning, as A²RBench does? A²RBench classifies chains of thought into categories such as "Surface Fitting" using another model. That reintroduces a noisy judge, which is exactly the object whose noise we are measuring. Generator-derived labels are exact. We will report how often the analyst-style judge agrees with them, as a side result.

Why not just remap symbols to detect contamination? The 17.7% drop on remapped symbols in A²RBench already shows that models rely on memorized tokens. It says nothing about whether test-time compute gains shrink, or whether the scorer's reliability, and therefore the useful search width, changes. Our question is about the scaling curve, not the accuracy level.

Decisive Checks

We use Llama-3-8B, Llama-3.1-8B and Mistral as the generating models, matching the cited baselines. Scorers are perplexity, a process reward model, and the outcome reward model. Budgets range from 1 to 64 candidates or beams, matched in generated tokens. Each arm contains 500 items per task family, the per-dataset size DyVal uses. FuncBenchGen depths run from 1 to 6.

The hypothesis is supported if four things hold. The compute-accuracy slope must decrease from Arm A to B to C, with non-overlapping bootstrap intervals. The $\Delta/\sigma$ measured on the twins must predict the best width on held-out procedural items within one doubling, while $\Delta/\sigma$ measured on Arm A overestimates it. The right-for-wrong-reasons rate under outcome reward model selection must rise with N on Arm C. Predictive-Decoding's irrelevant-node rate must fall less than its accuracy gain suggests.

The hypothesis is refuted if Arms A and C show equal slopes and equal scorer separation. In that case contamination is not what makes search look good, and the existing extreme-value account suffices without it.