Verifier Noise Is a Temperature: Testing Tilt Predictions in Finite-Budget LLM-Guided Search

Xiaomeng Li

cs.LGNov 6, 2026

Verifier Noise Is a Temperature: Testing Tilt Predictions in Finite-Budget LLM-Guided Search

Authors: Xiaomeng Li

Organizations: Link Heart Limited, Houston, TX, USA

Abstract

LLM-guided search loops propose a modified candidate, score it, and keep it if it scores better. When both candidates are re-scored at every comparison, as in the minibatch acceptance gates of prompt optimizers, keep-if-better is a reversible Markov chain if the score difference is logistic and the mutation operator is reversible, and its stationary law is the mutation equilibrium tilted by exp(beta f). For any continuous symmetric noise difference the same tilt is the stationary law of a small-step diffusion limit, with beta = 4F'(0); for a minibatch gate beta grows with the square root of the minibatch size. Caching the incumbent's score instead inflates the recorded score. We test the tilt as a prediction for LLM-guided program search, committing each prediction from calibration data before the search runs. The level after 150 steps rises with the minibatch size in six of seven settings, but its predicted value fails: on bin packing, search attains 62-88% of the predicted gain when the proposer edits the parent and 109-119% when it writes new heuristics. The attained fraction falls with the parent-child quality correlation of unselected mutation; a registered test on two new settings confirmed the direction, but not the quantitative agreement after a correction. Further registered tests found that runs started from a good program kept losing quality over 300 steps, more so from starts that search had selected, by a margin that passed its registered rule narrowly. Runs from different starts had not reached a common level, so whether the tilt describes the stationary law of LLM editing remains open. A registered test in prompt optimisation on frozen task-model scores failed: search exceeded the tilt, and the bin-packing relation did not transfer.

Figures & tables

$d$	$\rho=0.5$	$0.9$	$0.99$	$0.998$
0.5	1.148	1.135	1.124	1.123
1	1.188	1.142	1.127	1.127
3	1.332 †	1.215	1.143	1.132

Table 1: Mean quality of regime R divided by SNR

d

, Gaussian noise: average over the second half of runs of

60/(1-\rho)+500

steps. Theorem 1 :

1.128

\rho\to 1

. † Grid stationary mean by power iteration; this chain mixes slowly, and a run of

620

steps gives only

1.23

(Section 3.4).

Figure 1: True quality returned at matched evaluations (autoregressive model,

\rho=0.9

, Gaussian noise). Re-evaluated search (R) flattens at its plateau; at

d=1

the dotted small-step value

2d/\sqrt{\pi}

is close, at

d=3

the finite-step plateau (

3.65

) is above it. Cached search (C) keeps rising. IID grows like

\sqrt{2\log E}

$d$	$E$	IID	C (cached)	R (re-evaluated)
1	32	1.45	0.74	0.61
1	512	2.16	2.03	1.17
1	8192	2.69	3.52	1.14
1	32768	2.92	4.26	1.13
3	32	1.96	2.06	1.39
3	512	2.88	6.01	3.63

Table 2: True quality of the returned candidate at matched evaluations

E

(

\rho=0.9

\delta=0

, 2,000 runs).

setting	$m$	$\beta$	pre-reg. pred.	ESS	observed	$z$	from above	lift	IID at $E$
BP, Haiku, neutral	1	281	$0.9509\pm 0.0001$	480	$0.9500\pm 0.0005$	$-1.7$	$0.9519\pm 0.0005$	88%	0.9491
	4	566	$0.9525\pm 0.0002$	188	$0.9512\pm 0.0007$	$-1.9$	$0.9525\pm 0.0006$	86%	0.9496
	16	1168	$0.9541\pm 0.0002$	48	$0.9533\pm 0.0010$	$-0.9$	$0.9543\pm 0.0002$	92%	0.9512
	64	2716	$0.9551\pm 0.0001$	10	$0.9541\pm 0.0006$	$-1.5$	–	(91%)	0.9529
BP, Haiku, small edit	1	424	$0.9512\pm 0.0006$	397	$0.9499\pm 0.0010$	$-1.1$	$0.9503\pm 0.0007$	76%	–
	4	855	$0.9531\pm 0.0007$	82	$0.9510\pm 0.0005$	$-2.4$	$0.9508\pm 0.0007$	71%	–

Table 3: Test 1. “Pre-reg. pred.”: tilt prediction from calibration only (

\pm

bootstrap error over walks); ESS: effective sample size of the reweighting. “Observed”: mean true quality of the incumbent over steps 100–150,

\pm

s.e. over 6 seeds;

z

: (observed

-

prediction)/combined s.e. “From above”: same, started at quality

0.9559

. “Lift”: (observed

-

walk mean)/(prediction

-

walk mean), in parentheses where ESS

<30

, since the prediction there is not informative. IID for the small-edit settings is omitted: 599 (Haiku) and 600 (Sonnet) of the 600 fresh children have identical quality.

Figure 2: True quality of the incumbent in regime R (mean

\pm

s.e. over 6 seeds) for each setting and minibatch size. Dotted: pre-registered prediction. Dashed: runs started from above. ESS of the reweighting in each panel; where it is in single digits the prediction is close to the largest walk sample and does not test the shape of

\pi_{0}

Test	Hypothesis	Rule	Result	Verdict
1	plateau level = tilt	none (report $z$ )	editing: 16/16 cells below, $z\in[-2.9,-0.9]$ ; rewrite: 7/8 above	level fails
1	ordering by $m$	none	six of seven settings	sanity check
2	H1a (rewrite)	fail if $L+2\,\mathrm{se}<0.95$	$L=1.19\pm 0.06$	pass
2	H1b (small edit)	fail if $L-2\,\mathrm{se}>0.85$	$L=0.62\pm 0.08$	pass
2	H1q (both)	$\|L-\hat{L}(\rho)\|\leq 2\sqrt{0.020^{2}+\mathrm{se}^{2}}$	$0.04$ (tol. $0.12$ ); $0.15$ (tol. $0.17$ ). Seed-blocked se: tol. $0.15$ , $0.10$ . Approx. propagation: 95% CI $[-0.11,0.21]$ , $[-0.36,0.07]$	pass, pass. Seed-blocked: pass, fail
2	H2 (both)	search vs. walk P(better)	$0.02$ vs. $0.04$ ; $0.17$ vs. $0.28$ . First proposals only: $0.02$ vs. $0.04$ ; $0.22$ vs. $0.26$	pass, pass. First proposals: pass, fail ( $0.046<0.05$ )

Table 4: Every registered hypothesis, its decision rule and its verdict. Test 1 registered predictions without a numerical pass/fail rule; tests 2–5 registered rules before calibration (tests 2 and 5), before any step beyond 150 (test 3 and H6-300/H10) or before any step of the new runs (test 4). Test 5 is the prompt-optimisation domain (Section 5.3 ); its

L

rests on the one cell with ESS

\geq 30

(

m=4

) and its se is over 6 seeds.

L

: attained fraction of the predicted lift;

\rho

: parent–child quality correlation of the calibration walks; se: standard error over 6 seeds (test 4: across starts, 6 per group).

D

: mean drop of walk-visited minus search-selected starts. Robustness checks (post-hoc, Section 5.2 ) correct two features of the registered analyses: cells that share proposals within a seed (H1q) and pooled proposals that over-weight hard-to-improve search parents (H2). Test 5 scores are frozen single evaluations of each prompt.

Figure 3: Test 3: incumbent true quality over 300 steps (mean

\pm

s.e. over 6 seeds, 10-step moving average). Solid: from the start program; dashed: from the single high-quality start program (small-edit settings only); dotted: pre-registered prediction. Shaded: windows

W_{150}

and

W_{300}

. Haiku with the small-edit instruction has no

m=16

run from below continued to 300 steps.

Figure 4: Test 4: incumbent true quality in regime R at

m=4

from start programs of matched quality (10-step moving average). Thin lines: single starts (mean of two seeds); thick: group mean

\pm

s.e. over starts (Sonnet: 6 per group; Haiku: 2). Grey: runs from the root (mean of 6 seeds). Dotted: pre-registered prediction. Shaded: the primary (steps 1–50), secondary (100–150) and continuation (250–300) windows. Steps beyond 150 are the registered continuation, rerun after the evaluation fault of Appendix C .

$m$	$\beta(m)$	tilt pred.	ESS	kernel	R observed	C observed
1	260	$0.9502\pm.0004$	129	0.9497	$0.9505\pm.0011$	$0.9503\pm.0008$
4	519	$0.9515\pm.0004$	58	0.9514	$0.9509\pm.0009$	$0.9508\pm.0008$
16	1038	$0.9533\pm.0006$	10	0.9540	$0.9535\pm.0008$	$0.9521\pm.0008$
64	2076	$0.9545\pm.0006$	2.6	0.9563	$0.9551\pm.0002$	$0.9544\pm.0002$

Table 5: Exploratory run (not pre-registered): predicted vs. observed level, regimes R and C. Values are true quality of the incumbent, averaged over the last third of the run (100 steps for

m\leq 4

, 200 for

m\geq 16

\pm

: standard error over 6 seeds, or bootstrap error over walks for the tilt prediction. ESS: effective sample size of the reweighting.

Figure 5: Exploratory run, mean

\pm

s.e. over 6 seeds. Solid lines and bands: observed true quality of the incumbent. Dotted: tilt prediction from

\pi_{0}

and

\tau

alone. Dashed: projected-kernel transient.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

setting	pooled	parent-weighted	first proposal	first, by run	$n$ first
Haiku neutral	$0.53$ $[0.33,0.85]$	$1.45$ $[0.91,2.30]$	$1.05$ $[0.63,1.75]$	$[0.63,1.75]$	471/164 (12/24)
Haiku small edit	$0.23$ $[0.13,0.38]$	$0.80$ $[0.49,1.29]$	$0.51$ $[0.28,0.92]$	$[0.16,1.59]$	121/152 (6/13)
Sonnet neutral	$0.37$ $[0.26,0.53]$	$0.97$ $[0.73,1.29]$	$0.74$ $[0.54,1.01]$	$[0.53,1.02]$	413/443 (6/23)
Sonnet small edit	$0.34$ $[0.22,0.51]$	$0.99$ $[0.71,1.37]$	$0.80$ $[0.54,1.19]$	$[0.51,1.26]$	227/413 (6/16)
Haiku rewrite	$1.02$ $[0.66,1.60]$	$1.81$ $[1.11,2.94]$	$1.26$ $[0.63,2.52]$	$[0.60,2.62]$	197/254 (6/24)
Sonnet rewrite	$1.02$ $[0.42,2.51]$	$2.15$ $[0.79,5.84]$	$0.69$ $[0.13,3.67]$	$[0.12,3.78]$	108/155 (6/24)

Appendix

Table 6: Selection effect at matched quality, parents in

[0.952,0.957)

, chains from above excluded: odds ratio of a better child for search vs. walk parents, adjusted for parent quality (95% intervals). Pooled: all proposals, interval clustered by parent. Parent-weighted: each proposal weighted by

1/

(proposals of its parent). First: first proposal per parent and run, interval clustered by parent (in this band every parent contributes one first proposal, so this is close to unclustered) and, in the next column, by run (search seed or calibration walk; normal approximation with few clusters).

n

: parents (first), search/walk, with the number of runs in parentheses.

Large Language Model-Guided Optimization

Large Language Model-Guided Optimization uses language models to propose, steer, and refine solutions to hard search and design problems.

See all 628 papers

Apr 21, 2026

What Makes an LLM a Good Optimizer? A Trajectory Analysis of LLM-Guided Evolutionary Search

Recent work has demonstrated the promise of orchestrating large language models (LLMs) within evolutionary and agentic optimization systems. However, the mechanisms driving these optimization gains remain poorly understood. In this work, we present a large-scale study of LLM-guided evolutionary search, collecting optimization trajectories for 15 LLMs across 8 tasks. Although zero-shot problem-solving ability correlates with final optimization outcomes, it explains only part of the variance: models with similar initial capability often induce dramatically different search trajectories and outcomes. By analyzing these trajectories, we find that strong LLM optimizers behave as local refiners, producing frequent incremental improvements while progressively localizing the search in semantic space. Conversely, weaker optimizers exhibit large semantic drift, with sporadic breakthroughs followed by stagnation. Notably, various measures of solution novelty do not predict final performance; novelty is beneficial only when the search remains sufficiently localized around high-performing regions of the solution space. Our results highlight the importance of trajectory analysis for understanding and improving LLM-based optimization systems and provide actionable insights for their design and training.

Xinhao Zhang, Xi Chen, François Portet +1

Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG, 38000 Grenoble, France

Evolutionary Optimization Large Language Model-Guided Optimization LLMs for Evolutionary Optimization

Ask PDF

Mar 16, 2026

More Test-Time Compute Can Hurt: Overestimation Bias in LLM Beam Search

Wider beam search should improve LLM reasoning, but when should you stop widening? Prior work on beam width selection has focused on inference efficiency \citep{qin2025dsbd, freitag2017beam}, without analyzing whether wider search can hurt output quality. We present an analysis, grounded in Extreme Value Theory, that answers this question. Beam selection over noisy scorer outputs introduces a systematic overestimation bias that grows with the candidate pool size, and we derive a maximum useful beam width

\hat{k}

beyond which search degrades performance. This critical width depends on the signal-to-noise ratio of the scorer:

\hat{k}

grows exponentially with

(Δ/σ)^2

, where

Δ> 0

is the quality advantage of correct paths over incorrect ones and

σ

is the scorer noise. We validate this theory by comparing perplexity-guided and PRM-guided beam search across three 7B-parameter models and ten domains on MR-BEN (5,975 questions). Perplexity scoring, with its high noise, yields

\hat{k} = 1

: search provides no benefit at any width tested. PRM scoring, with lower noise, yields

\hat{k} \geq 4

, with gains of up to 8.9 percentage points. The same model, the same algorithm, but different scorers place

\hat{k}

at opposite ends of the beam width range. Our analysis identifies the scorer's signal-to-noise ratio as the key quantity governing beam width selection, and we propose diagnostic indicators for choosing the beam width in practice.

Gal Dalal, Assaf Hallak, Gal Chechik +1

NVIDIA Research · Bar-Ilan University · University of Groningen

Inference-Time Search

Ask PDF

Sep 17, 2026

Evolution or Illusion? Rethinking Evaluation in LLM Evolutionary Search

LLM-driven evolutionary search finds programs by launching seeds and iterating each one. Papers report a single budget setting, usually one seed run for a fixed number of iterations, and rank methods from that one point. We show this is not enough. We evaluate three evolutionary search strategies on five optimization tasks, commonly used by papers in the genre to report results. We run the analysis over a full grid of seeds and iterations. Our findings suggest that the best way to split a fixed budget between more seeds (width) and more iterations (depth) changes with the strategy, the task, and the total budget. Furthermore, we observe that the ranking of strategies also changes with the budget. On one task the strategy that looks worst at one seed is best at forty seeds. On another the best number of iterations is well below the value common in practice, so extra depth wastes budget that more seeds would turn into score. We provide a measurement protocol that reports the seeds-by-iterations frontier and practical guidance for using it.

Tal Oved, Roi Pony, Oshri Naparstek +1

IBM Research

Evolutionary Optimization Large Language Model-Guided Optimization

Ask PDF

Abstract

Large Language Model-Guided Optimization

Explore similar work

What Makes an LLM a Good Optimizer? A Trajectory Analysis of LLM-Guided Evolutionary Search

More Test-Time Compute Can Hurt: Overestimation Bias in LLM Beam Search

Evolution or Illusion? Rethinking Evaluation in LLM Evolutionary Search