Sample, Mix, or Verify? Allocating Test-Time Compute under Imperfect Verifiers

Srinivasan Iyengar

cs.LGOct 16, 2026

Sample, Mix, or Verify? Allocating Test-Time Compute under Imperfect Verifiers

Authors: Srinivasan Iyengar

Organizations: Microsoft Research India

Abstract

A common way to make language models and agents more accurate is to spend more compute at inference time: generate many candidate solutions and submit the one a verifier prefers. Success then requires that some candidate is correct and that the verifier picks it. The first grows predictably with the number of samples; the second does not, because real verifiers (unit tests, majority votes, LLM judges, reward models) accept wrong answers, reject right ones, and make correlated mistakes. With a fixed budget, a practitioner must decide how many samples to draw, which models to draw them from, and how much to spend on verification, and today these choices are made by rules of thumb. We introduce SPLIT, which makes them from a small labelled pilot. It rests on an exact formula for the probability of submitting a correct answer under accept/reject and top-score selection that accounts for varying task difficulty, blind spots shared across models, and correlated repeated verifier calls. SPLIT fits the formula by empirical Bayes and uses it to plan budgets on unseen tasks. Across seven benchmarks spanning math, science QA, code and software-engineering agents, 26 models, 175 agent systems and six kinds of real verifiers, all from public releases, SPLIT lands within 0.02-0.8 percentage points of the best allocation in hindsight, while every fixed rule we test loses at least 2.5 points in some setting. Regret depends only on how well SPLIT ranks configurations, and it stays near-optimal under compute, price and latency costs and online. The formula also explains when asking more LLM judges lowers precision. As a forecaster far beyond the pilot, SPLIT beats power-law fitting when the verifier caps success, and we report where it loses.

Figures & tables

Figure 1: Generation is not selection. Coverage (black) keeps rising with the number of samples

N

, but verified success flattens at a ceiling set by the verifier’s precision (dotted). Coloured lines are the exact success formula ( Proposition 1 ); markers are simulations of the verifier on the real correctness labels of the Large Language Monkeys release ( Brown et al., 2024 ) . A real majority vote (grey dashed) stalls near 43% on MATH while coverage reaches 98%.

Benchmark	Tasks	Samples per task	Generators	Verifier(s)
MATH	128	10,000	5 (Llama-3 8B/70B, Gemma 2B/7B)	simulated (TPR, FPR, $\kappa$ controlled); real majority vote
CodeContests	140	10,000	3 (Llama-3 8B/70B-Inst., Gemma-7B)	simulated; public tests (80,403 programs executed)
HumanEval	164	50–1,000	17 (CodeGen-6B to GPT-4o)	base tests ; truth: HumanEval+
MBPP	399	20–50	10	base tests ; truth: MBPP+
MATH-500, GPQA	500, 646	100	Llama-3.1-70B-Inst. (+8B)	8 LLM judges (random judge per call, majority of $k$ ); 19 reward models; Weaver score
SWE-Bench Verified (R2E-Gym rollouts)	492	22	R2E-Gym 32B agent	LLM patch verifier $P(\text{yes})$ : thresholds or argmax

Table 1: Data. All samples and verdicts come from public releases; we generate nothing new. Benchmarks: MATH ( Hendrycks et al., 2021 ) , CodeContests ( Li et al., 2022 ) , HumanEval ( Chen et al., 2021 ) with HumanEval+ ( Liu et al., 2023 ) , MBPP ( Austin et al., 2021 ) , MATH-500, GPQA ( Rein et al., 2023 ) and SWE-Bench Verified ( Jimenez et al., 2024 ) . Releases are cited in the text.

	Simulated verifier		Sim., compute-matched		CodeContests, real tests
Method	MATH	CodeContests	MATH	CodeContests	param. cost	compute-matched
SPLIT (ours)	0.54	0.82	0.47	0.65	0.62	0.46
SPLIT, independent errors	1.69	1.01	1.36	0.82	1.46	1.34
Singhi et al. (2025) rule	11.95	0.78	11.94	0.73	—	—
Strongest model	12.35	0.99	12.72	1.02	0.94	0.94
Uniform ensemble	16.73	3.62	16.74	3.82	2.33	2.53

Table 2: Allocation regret on unseen tasks: samples and generators (percentage points below the hindsight-optimal configuration; mean over budgets and splits; lower is better). “Compute-matched” prices samples by parameters

\times

measured output tokens instead of parameters alone. SPLIT with independent errors is our ablation; the others are fixed rules.

LLM judges (Weaver release)			SWE-Bench Verified agents
Method	MATH-500	GPQA	Method	Regret
SPLIT, empirical task population	0.06	0.02	SPLIT, task-varying verifier	0.33
SPLIT, fitted judge correlation	0.06	0.11	SPLIT, auto-selected verifier model	0.56
SPLIT, judge-level IRT	0.04	0.05	SPLIT, pooled verifier	2.36
SPLIT, independent judge calls	0.23	0.53	Fixed threshold 0.5	2.62
Singhi et al. (2025) rule	0.05	1.20	No verifier (random rollout)	3.58

Table 3: Allocation regret on unseen tasks: how much to verify (percentage points; mean over budgets/

N

and 10 splits). Left: solve-vs-verify with real LLM judges (each judge call costs one generation). Right: choosing the acceptance threshold of an LLM patch verifier for each number of agent rollouts on SWE-Bench Verified.

Figure 2: Allocation with a real verifier (CodeContests public tests, planner calibrated on 50% of tasks with 32-sample pilots, 10 splits). (a) Success on held-out tasks of the configuration chosen by each method against the per-task budget. (b) Regret relative to the oracle at each budget. SPLIT (ours) stays within about 1.2 points of the oracle at every budget; each fixed rule is good only in part of the range.

Figure 3: Cost models and online re-planning (CodeContests, public tests as the verifier, 10 splits). (a) Regret of each allocation rule when a sample costs

(\text{parameters})^{\gamma}\times

output tokens; “params” prices by parameters only. Zero bars are labelled. (b) Success of online policies minus the static plan (mean

\pm

s.e. over splits). Budgets are pooled across the evaluation tasks.

	$B=4$		$B=16$		$B=64$		$B=256$
Policy	success	spent	success	spent	success	spent	success	spent
Static plan (SPLIT)	2.90	1.00	7.14	1.00	11.04	1.00	15.31	1.00
Static oracle (hindsight)	3.22	1.00	7.32	1.00	11.85	1.00	16.47	1.00
Early stop, static mix, per task	2.82	0.95	6.90	0.93	10.91	0.85	15.21	0.75
Re-planning, per task	2.79	0.95	7.42	0.93	11.09	0.86	15.13	0.75
Early stop, static mix, pooled	2.98	1.00	7.16	1.00	11.68	1.00	16.03	1.00

Table 4: Online re-planning on unseen CodeContests tasks (success in %, mean over 10 splits; 16 Monte Carlo replays per split). “Spent” is the fraction of the budget used. Policies with a per-task budget stop a task at its first accepted candidate. Policies with a pooled budget give the savings to unresolved tasks.

	$N=4$	$N=16$	$N=64$
Real	$+1.2$	$+3.3$	$+4.8$
SPLIT, empirical task population	$\mathbf{+1.2}$	$\mathbf{+3.3}$	$\mathbf{+4.6}$
SPLIT, pooled judge rates	$+3.7$	$+7.3$	$+10.0$
SPLIT, judge-level IRT	$+3.4$	$+6.6$	$+9.6$

Table 5: Gain from 9 judge calls instead of 1 on GPQA (percentage points of verified success), real versus predicted from a 32-sample pilot on calibration tasks.

Figure 4: Stochastic LLM-judge verification (Weaver release, Llama-3.1-70B-Instruct candidates). (a) Many wrong MATH-500 answers are accepted by most of the eight judges. (b, c) Verified success against the number of judge calls

k

for

N=4,16,64

: real (solid), SPLIT with the empirical task population (dashed), and SPLIT with pooled judge rates (dotted). Extra calls are useless on MATH-500 and help on GPQA. (d–f) Solve-vs-verify allocation on unseen tasks and planner regret.

Figure 5: Capability and verifier false positives. (a) For fixed test suites, the FPR rises with generator pass@1 on HumanEval+, MBPP+ and CodeContests (replicating Stroebl et al., 2024 ). (b, c) For 19 reward models, the stronger generator’s wrong answers pass a fixed threshold more often (b), but not once the threshold is re-tuned to equal TPR (c).

Setting	Target	Horizon	Ours	Power law	Plug-in	$p$
MATH + CodeContests, sim. verifier (pilot 32)	selection	8,192	1.9	7.6	—	$<10^{-3}$
MATH + CodeContests (pilot 32)	coverage	8,192	3.3	2.6	—	—
CodeContests, public tests	selection	8,192	2.13	2.77	5.54	0.002
HumanEval, base tests (17 models)	selection	$\approx$ 128	1.69	2.13	4.55	$<10^{-3}$
SWE-bench, LLM verifier thresholds	selection	16	2.74	6.70	4.07	$<10^{-3}$
SWE-bench, argmax of verifier score	selection	16	3.28	1.58	2.11	0.006

Table 6: Extrapolation error (MAE in percentage points over all

N

beyond the pilot; mean over pilot sizes and seeds unless stated). “Ours” is the best-justified variant per row: pooled verifier for a simulated verifier and CodeContests; task-varying verifier for HumanEval and SWE-bench thresholds; issue-level score shift for argmax; NPMLE prior for the agent pool. Paired

p

-values compare ours with the power law.

Figure 6: Agentic setting: SWE-Bench Verified rollouts with an execution-free LLM verifier (R2E-Gym release). (a) Resolved rate of the selected patch at threshold 0.5: truth, SPLIT (pooled and task-varying verifier) and baselines, from a 6-rollout pilot. (b) Extrapolation error by threshold. (c) Choosing the threshold for each number of rollouts on unseen issues. Argmax of the verifier score (pink) matches the best threshold at

N=1

and exceeds every threshold for

N\geq 2

Figure 7: A pool of 175 SWE-Bench Verified submissions as attempts (coverage only; no shared verifier). (a) Random pilot of 16 systems; (b) pilot of the 16 oldest systems (capability drift); (c) extrapolation error over 10 random splits for three pools; (d) share of systems that resolve each issue. Issues no system resolves cap coverage.

Figure 8: CodeContests public tests as a real verifier. (a) Per-task FPR is zero for most tasks but heavy-tailed. (b) Truth (all tests) versus predictions from a 32-sample pilot. (c) Extrapolation error to

N=8{,}192

against pilot size for three generators and 10 pilots.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Pooled verifier	Task-varying	Automatic	Picks task-varying
CodeContests (3 models)	2.13	2.64	2.40	43%
HumanEval (17 models)	1.85	1.69	1.73	56%
SWE-Bench Verified (3 thresholds)	5.35	2.74	3.45	59%

Appendix

Table 7: Choosing the verifier model automatically (extrapolation MAE in points, mean over pilot sizes). Paired tests: the automatic choice is significantly better than the worse fixed model on every dataset (

p\leq 0.03

), ties the better one on HumanEval (

p=0.52

), and is behind it on CodeContests and SWE-bench (0.28 and 0.71 points,

p<0.01

Pool, pilot	Horizon	Beta prior	NPMLE prior	Power law	Plug-in	Independence
All 175 systems, 16	159	3.23	2.58	1.71	4.93	8.40
All 175 systems, 32	143	2.84	1.27	1.58	2.56	7.51
90 single-attempt systems, 32	58	2.39	1.14	0.73	2.66	7.87
41 mini-SWE-agent runs, 16	25	3.39	1.65	1.48	2.68	10.95

Appendix

Table 8: Agent pool: extrapolation MAE (points; random splits, 10 seeds). Horizon = all held-out systems.

Method	MAE (points)	Error at $N=16$
Power law	1.6	$+2.3$
Plug-in per task	2.1	$-2.9$
Ours, issue-level score shift	3.3	$+2.4$
Ours, pooled score distributions	4.5	$+5.3$
Ours, issue shift with Gaussian tails (ablation)	3.8	$-7.4$
Ours, joint Dirichlet over bins (ablation)	20.3	$+22.6$

Appendix

Table 9: Argmax selection on SWE-Bench Verified (6-rollout pilot, 10 draws).

Figure 9: Shared blind spots. (a, b) Pilot-estimated copula correlations between generator pairs on MATH and CodeContests. (c) Predicted versus real gain from the best two-model mix: the SPLIT with the copula (ours) against the independence assumption. (d, e) Mixing curves. (f) The independence over-promise grows with correlation.

Figure 10: Which lever to pull (theory). (a) Best use of a fixed budget as a function of verifier FPR and cross-generator correlation: sample more, diversify, verify more, or both. (b) The optimal number of verifier calls stays at one when repeated calls are highly correlated.

Figure 11: Allocation with a simulated verifier (MATH and CodeContests, 5 splits). Success of the chosen configuration on unseen tasks by budget, and regret relative to the oracle.

Figure 12: Pilot extrapolation with a simulated verifier (FPR 0.1). Top: predicted curves from a 32-sample pilot. Bottom: error against pilot size for coverage and selection.

Figure 13: HumanEval base tests as a real verifier, HumanEval+ as ground truth, 17 generators. (a) FPR, pooled over tasks, against pass@1 (Spearman 0.98; 0.97 with per-task FPRs as in Section 6.3 ). (b) Coverage and verified success for three generators. (c) Predicted versus true success at the held-out horizon. (d) Error against pilot size. (e) Error per generator.

Figure 14: Argmax (best-of-

N

) selection on SWE-Bench Verified. (a) Truth and predictions; the best fixed accept/reject threshold (grey; 0.3, 0.5 or 0.7, scored as a failure when no rollout is accepted) is below argmax at every

N

, by 1.8 points at

N=1

and 4.4 at

N=16

. (b) Extrapolation error.

Setting	$\|\mathcal{C}\|$	$T_{\mathrm{cal}}$	Regret	Pairwise error	$\max\|e\|$	Model spread	Task gap	Hoeffding
MATH, simulated verifier	140	64	0.54	0.96	11.12	7.20	10.40	73.4
CodeContests, simulated verifier	48	70	0.82	2.81	7.59	3.69	5.79	65.7
CodeContests, real tests	13	70	0.62	1.48	6.03	2.63	5.50	59.8

Appendix

Table 10: Planner-regret diagnostics ( Proposition 4 ; percentage points, mean over budgets and splits). Pairwise error is

e(\hat{c})-e(c^{\star})

, which bounds regret. Model spread is

\operatorname{osc}(b)

, the variation across configurations of SPLIT’s error on the calibration tasks. Task gap is

\max_{c}|S_{\mathrm{cal}}(c)-S(c)|

. Hoeffding is the finite-sample term of Proposition 4 (c) at

\delta=0.05

Comparison	Mean diff. [95% CI]	$p$
Selection MAE, sim. verifier: SPLIT vs power law	$-5.71$ [ $-6.17$ , $-5.22$ ]	$<10^{-3}$
CodeContests MAE: SPLIT vs power law	$-0.65$ [ $-1.00$ , $-0.32$ ]	0.002
HumanEval MAE: SPLIT, task-varying vs power law	$-0.44$ [ $-0.55$ , $-0.33$ ]	$<10^{-3}$
SWE-bench MAE: SPLIT, task-varying vs power law	$-3.97$ [ $-4.34$ , $-3.59$ ]	$<10^{-3}$
SWE-bench argmax MAE: SPLIT, issue shift vs power law	$+1.71$ [ $+1.00$ , $+2.35$ ]	0.006
Agent-pool coverage MAE: SPLIT, NPMLE vs power law	$+0.30$ [ $-0.11$ , $+0.72$ ]	0.57

Appendix

Table 11: Paired tests for headline comparisons. Mean difference (ours minus comparator; negative favours ours) with bootstrap 95% interval and Wilcoxon signed-rank

p

-value. Units are shared (model, pilot, seed) for MAE and (dataset, seed, budget) for regret.

Inference-Time Compute Allocation

Inference-time compute allocation decides where, when, and how much computation models spend during prediction to improve quality under resource limits.

See all 76 papers

What If We Allocate Test-Time Compute Adaptively?
Feb 1, 2026Ahsan Bilal, Ahmed Mohsin, Muhammad Umer +4Inference-Time Search Test-Time Scaling
University of Oklahoma, OK, USA · Stanford University, CA, USA · Universitat Pompeu Fabra, Barcelona, Spain +2
How Much Can Language Models Gain from Test-Time Computation?
Oct 1, 2026Bangji Yang, Jingyuan Li, Jiajun Fan +8LLM Evaluation Test-Time Scaling
University of Illinois at Urbana-Champaign · University of Washington · Tsinghua University
Thinking Hard, Not Smart: Reasoning Models Fail to Ration Test-Time Compute Across Questions
Aug 8, 2026Chenrui Fan, Yize Cheng, Ming Li +3LLM Evaluation Inference-Time Compute Allocation
University of Maryland, College Park · MBZUAI, UAE

Feb 1, 2026J/K move · Enter open · S save

What If We Allocate Test-Time Compute Adaptively?

Ahsan Bilal, Ahmed Mohsin, Muhammad Umer, Ali Subhan+3

University of Oklahoma, OK, USA · Stanford University, CA, USA · Universitat Pompeu Fabra, Barcelona, Spain+2

Inference-Time Search Test-Time Scaling Inference-Time Compute Allocation Inference-Time Guidance

Open paper AskPDF arXiv

Test-time compute scaling allocates inference computation uniformly, uses fixed sampling strategies, and applies verification only for reranking. In contrast, we propose a verifier-guided adaptive framework treating reasoning as iterative trajectory generation and selection. For each problem, the agent runs multiple inference iterations. In each iteration, it optionally produces a high-level plan, selects a set of reasoning tools and a compute strategy together with an exploration parameter, and then generates a candidate reasoning trajectory. A process reward model (PRM) serves as a unified control signal: within each iteration, step-level PRM scores are aggregated to guide pruning and expansion during generation, and across iterations, aggregated trajectory rewards are used to select the final response. Across datasets, our dynamic, PRM-guided approach consistently outperforms direct test-time scaling, yielding large gains on MATH-500 and several-fold improvements on harder benchmarks such as AIME24 and AMO-Bench. We characterize efficiency using theoretical FLOPs and a compute intensity metric penalizing wasted generation and tool overhead, demonstrating that verification-guided allocation concentrates computation on high-utility reasoning paths.

Abstract

Inference-Time Compute Allocation

Explore similar work

What If We Allocate Test-Time Compute Adaptively?

How Much Can Language Models Gain from Test-Time Computation?

Thinking Hard, Not Smart: Reasoning Models Fail to Ration Test-Time Compute Across Questions