WorksComputer Science
Sample, Mix, or Verify? Allocating Test-Time Compute under Imperfect Verifiers
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.
Introduction
Spending more compute at inference time, by sampling many candidate solutions and keeping one, is now a standard way to raise the accuracy of language models and agents [5, 27, 2, 24]. Coverage, the probability that at least one of attempts is correct, grows smoothly with , often as a power law over several orders of magnitude [2, 22]. But a system is graded on the one answer it submits. That answer is chosen by a verifier: unit tests, a majority vote, an LLM judge or a reward model. Real verifiers accept some wrong answers and reject some right ones, and their mistakes are not independent. The same plausible wrong answer tends to fool every judge, and different generators tend to fail on the same hard problems. As a result, verified success can stall far below coverage. On MATH, majority voting over Llama-3-8B-Instruct samples stays near 43% while coverage reaches 98% (Figure 1), and Stroebel et al. (2024) show that imperfect unit tests cap what resampling can achieve.
Figure 1. Generation is not selection. Coverage (black) keeps rising with the number of samples , 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 ([2]). A real majority vote (grey dashed) stalls near 43% on MATH while coverage reaches 98%.
Practitioners therefore face an allocation problem rather than a scaling problem. With a fixed budget, should they draw more samples, mix in a second model, spend calls on verification, or change how strictly the verifier accepts? Fixed rules of thumb answer these questions differently: “use the strongest model”, “scale solutions faster than verifications” [23], “ask more judges”. We show that each of them is badly wrong in some realistic setting. We argue that the decision should be made from a small labelled pilot using a model of selection, not only of generation.
Three obstacles. Fixed rules fail for three reasons, and our method addresses each. (1) The verifier caps what is handed in. When a verifier sometimes accepts wrong answers, verified success saturates at the verifier’s precision however many samples are drawn (§ 3), so the verifier’s true- and false-accept rates must be modelled, not only how often the generator is right. (2) Tries are correlated. Llama-3-8B-Instruct solves an average MATH problem 27% of the time, which would give 96% coverage at 10 tries if every problem were equally hard; its measured per-problem solve rates give 61%, because 44 of the 128 problems are almost never solved. A second model gets stuck on the same problems (per-problem solve rates of Llama-3-8B-Instruct and Gemma-7B correlate at 0.80), and a third of wrong MATH-500 answers fool at least six of eight LLM judges, so asking again repeats the mistake. (3) No fixed split works everywhere. The best configuration changes with the budget, the models and the verifier (§ 6.1), so it has to be chosen per setting.
Approach. We write success as and model the second factor explicitly. § 3 derives an exact success formula for two selectors used in practice, uniform choice among accepted candidates and choice of the top-scoring candidate. The formula models the verifier’s error rates (obstacle 1) and the three sources of correlation (obstacle 2): heterogeneous task difficulty, shared blind spots across generators (a Gaussian copula), and correlated repeated verifier calls (a candidate-level acceptance propensity). § 4 estimates the formula’s ingredients from a pilot by empirical Bayes, including variants for verifiers whose accuracy depends on the task. A planner then chooses the configuration that maximises predicted success under a cost budget (obstacle 3), and is evaluated on tasks not used for calibration. We call the whole method SPLIT, because it chooses how to split a fixed budget across generators, samples and verification.
Contributions.
SPLIT, a pilot-calibrated allocator of test-time compute. One planner chooses generators, sample counts, verifier calls or verifier thresholds under a budget. Across five allocation problems with real or simulated verifiers, plus an agentic threshold-selection problem, it lands within 0.02–0.8 points of the hindsight-optimal allocation on unseen tasks. Every fixed rule we compare against, including our adaptation of the compute-optimal exponents of Singhi et al. [23], loses at least 2.5 points somewhere (§ 6.1). Its regret is bounded by differential rather than absolute forecast error (Proposition 4), it stays within 0.62 points under five ways of pricing a sample, and an online variant that re-plans per task matches the best static configuration in hindsight (§ 6.2).
An exact success formula with heterogeneous difficulty, cross-generator correlation and correlated verifier calls, for both accept/reject and argmax selection, with proofs (§ 3, Section A).
Three mechanisms, measured on real verifiers (§ 6.3). (i) We give the exact condition under which majority-of- re-verification lowers attainable precision, and show that real LLM judges meet it on MATH-500 but not on GPQA. (ii) Pooling verifier accuracy across tasks biases forecasts because judge accuracy is coupled to task difficulty; modelling this coupling recovers the measured gain from extra judge calls. (iii) We replicate the rise of verifier false-positive rates with generator capability ([25]) on HumanEval+, MBPP+ and CodeContests, and show that for scored verifiers it is a threshold-calibration effect.
A candid comparison with curve fitting (§ 6.4). Using SPLIT as a point forecaster beats power-law extrapolation clearly under a simulated verifier and on agentic SWE-Bench Verified, modestly but significantly on code with real tests, and not at all for pure coverage or for argmax selection. This includes a long-horizon test on a pool of 175 SWE-bench agent systems.
All experiments use publicly released samples and verdicts. We spend no API budget, re-execute 80,403 CodeContests programs locally, and report paired significance tests for every headline comparison (Section D). The code, which reproduces every number and figure, will be released publicly.
Related work
Repeated sampling and coverage laws. Brown et al. [2] show that coverage grows roughly as a power law in the number of samples across math, code and formal proofs, and document that majority voting and reward-model selection plateau well below coverage. Schaeffer et al. [22] explain the power law through a heavy-tailed distribution of per-problem success rates. Both works model coverage. We add a predictive, mechanistic model for the selection factor, a treatment of correlated errors, and pilot-calibrated allocation; our coverage component uses the same beta-binomial view of difficulty. Chen et al. [3] show that voting accuracy can be non-monotone in the number of calls, depending on the mix of easy and hard queries. We obtain a related non-monotonicity for verification calls, with an exact condition (Proposition 2).
Imperfect verifiers. Stroebl et al. [25] show that false positives of unit tests bound the accuracy of resampling, that a model’s single-sample accuracy is strongly correlated with its false-positive rate on HumanEval and MBPP, and that the best number of attempts is often small. We build on their observations. We replicate the accuracy–FPR correlation on HumanEval+, MBPP+ and CodeContests and refine it for scored verifiers (§ 6.3). We also turn the bound into a predictive model with correlated errors, estimated from a pilot, and use it for allocation. Verifier design is a large literature: outcome and process reward models ([5, 16]), generative verifiers ([30]), and weak-verifier ensembles such as Weaver ([21]). That work builds better verifiers. We take a verifier as given, measure its errors, and decide how much to rely on it.
Compute-optimal test-time scaling. Snell et al. [24] allocate test-time compute adaptively between search and revision based on estimated question difficulty. Singhi et al. [23] fit compute-optimal power laws for the split between solutions and generative verifications (, ). We use their rule as a baseline. Our approach differs in three ways. It is mechanistic rather than a curve fit, so it transfers to new verifiers and budgets. It models cross-generator correlation and the correlation of repeated verifier calls. And it chooses jointly over generators, samples, verifier calls and thresholds.
Agents and best-of- for software engineering. SWE-bench [10], SWE-bench Verified [19] and agent scaffolds such as SWE-agent [28] made repository-level evaluation standard. R2E-Gym [9] and CodeMonkeys [7] scale the number of rollouts and select among them with execution-free verifiers or generated tests. Holistic agent evaluation [11] and studies of multi-agent scaling [13, 29] show that outcomes depend on the scaffold and on the diversity of agents, not only on their number. We use the public rollouts of R2E-Gym and the per-instance results of 175 SWE-bench submissions [26] to test SPLIT on agents.
Statistical tools. The estimators are standard empirical Bayes [6], with beta-binomial and non-parametric maximum-likelihood [12] priors for difficulty. The diversity result uses the supermodular order of Gaussian copulas [18], and the re-verification result is a version of the Condorcet jury theorem with correlated votes [14].
The success formula for verified best-of-
Setting. A task is attempted by generators ; a sample from is correct with probability . A verifier accepts a correct candidate with probability (true positive rate, TPR) and a wrong one with probability (false positive rate, FPR). Both may depend on the task. Write and for the per-sample probabilities of “accepted and correct” and “accepted”. The uniform-among-accepted selector submits a uniformly random accepted candidate and abstains (counted as failure) if none is accepted. Coverage is . Expectations are over the task distribution. Throughout we assume:
Assumption 1 (Conditional independence). Given the task, candidates are independent: candidate from generator has a (correct, accepted) pair with and , independently across candidates. Sample counts are non-negative integers; with no samples, or with , the selector abstains.
All dependence across tasks (difficulty, cross-generator correlation, task-dependent verifier rates) enters through the joint distribution of over tasks. Dependence within a candidate across repeated verifier calls enters through a candidate-level propensity (Proposition 2).
Proposition 1 (Exact success formula). Under Assumption 1, with samples from generator , the probability that the selected candidate is correct is
For a single generator with , , which is non-decreasing in and converges to the precision ceiling .
The single-generator form factorises success as (probability that something is accepted) (precision of acceptance). The proof (Section A) represents “uniform among accepted” as “first accepted under independent uniform arrival times”. Averaging Equation (1) over the task distribution gives the expected success of a configuration. Two regimes follow (Proposition 5, Section A). If the FPR is bounded below by on every task, verified success saturates exponentially, . If instead the FPR has mass near zero, , the saturation gap is bounded only by . Coverage itself decays polynomially, , when the density of behaves like near zero. Finally, verified success equals TPR-thinned coverage up to : , so small budgets behave as if the verifier were perfect and large budgets hit the ceiling.
Shared blind spots. With two generators and a budget split and , the coverage of the mixture is concave in . Mixing in B strictly helps iff with , i.e. iff B is better than A on the tasks A still fails. If follow a Gaussian copula with correlation and fixed marginals, the gain from an even mix is non-increasing in (Proposition 6, Section A). The planner therefore needs one number per generator pair, , estimated from the pilot.
Correlated re-verification. Repeated verifier calls on the same candidate are not independent. A judge that is fooled by an answer once tends to be fooled again, and so do other judges. We model each candidate by a propensity : given , calls are i.i.d. Bernoulli(), with for correct and for wrong candidates. The majority of (odd) calls accepts with probability for correct and for wrong candidates, where . In experiments we take to be Beta distributions with means and a concentration (: independent calls; : every call repeats the first).
Proposition 2 (When re-verification helps or hurts). (a) As over odd integers, , and likewise . (b) If every , then and for all . (c) Fix a task with and positive rates, and take . For any odd , the precision ceiling with calls is strictly above the ceiling with calls iff . In particular, calls lower the ceiling relative to one call iff
that is, iff majority voting inflates false acceptances by a larger factor than true acceptances. The same holds for with the limits of part (a). A larger FPR () alone is not sufficient.
Majority voting amplifies whatever most calls believe. If most wrong answers fool most judges ( has mass above ), grows with . Whether this hurts depends on how much the same amplification helps correct answers. The condition concerns the large- precision ceiling; at finite , extra calls also change how often nothing is accepted. Section A gives an example where the ceiling falls and a counterexample with where it rises.
Argmax selection. Many systems instead submit the candidate with the highest verifier score. Let correct and wrong candidates have score distributions and , and .
Proposition 3 (Verified success under argmax selection). For i.i.d. candidates, (a) if is atomless and has density , . (b) With scores binned into ordered bins, let and be the joint probabilities that a candidate is correct and in bin , or wrong and in bin (so , , and . With ties broken uniformly, , where empty bins contribute zero. (c) converges to the precision of the top occupied bin. In the continuous case it converges to whenever the local precision has a limit at the upper end of the score support.
So argmax selection replaces the average precision among accepted candidates with the local precision at the top of the score distribution. Which one is larger is an empirical question. It depends on the upper tails of and .
From a pilot to a plan
The success formula needs the joint distribution of difficulty and verifier behaviour over tasks. We estimate it from a labelled pilot: samples per task (typically 8–64) on a set of calibration tasks, with correctness labels and verifier verdicts or scores. All estimators are empirical Bayes; full details are in Section B.
Difficulty. For each generator, pilot success counts give a beta prior on by maximum likelihood, optionally zero-inflated for tasks no sample ever solves. For long horizons we also use the non-parametric maximum-likelihood estimator (NPMLE) of the difficulty distribution [12], which can put point masses at . Per-task posteriors combine the prior with the task’s own pilot counts.
Cross-generator correlation. For each pair of generators we fit the Gaussian-copula correlation by maximising the bivariate likelihood of the pair’s pilot counts, integrating the latent normals by Gauss–Hermite quadrature. We then project the correlation matrix onto the nearest valid correlation matrix and draw correlated by Monte Carlo.
Verifier. The pooled estimator uses a single TPR and an empirical-Bayes beta prior over per-task FPRs. For repeated stochastic verification (LLM judges) we fit the propensity concentration separately for correct and wrong candidates from the spread of acceptance counts across repeated calls. Three refinements address verifiers whose accuracy depends on the task:
Task-varying verifier. Each task has its own , with beta marginals coupled by a three-dimensional Gaussian copula fitted on the pilot. This captures, for example, LLM patch verifiers that are lenient on easy issues.
Automatic model choice. Neither the pooled nor the task-varying verifier model is best everywhere. We fit both on half of each task’s pilot samples, predict verified success at the full pilot size, and keep the model whose prediction is closer to the model-free success on the full pilot. In-sample BIC chose the wrong model on all three datasets where we tried it, so we do not use it.
Empirical task population (for judges). Instead of a parametric difficulty prior combined with pooled judge rates, SPLIT averages over the calibration tasks’ own pilot candidates and their measured judge propensities. This keeps the coupling between task difficulty and judge accuracy, which pooling destroys (§ 6.3). A judge-level item response model (each judge’s leniency, each candidate’s deceptiveness, each task’s effect) is reported as an alternative.
Argmax selection. We bin verifier scores and estimate the class-conditional score distributions from the pilot, then evaluate Proposition 3(b). Pooling scores across tasks overstates how well the verifier separates good from bad candidates within a task: on SWE-Bench Verified a task’s mean score correlates with its solve rate (), and within-task AUC is against pooled. We therefore fit a per-task random intercept on logit scores by EM and keep the empirical residual tails.
Planner. A configuration specifies generators with mixing weights , the number of verifier calls (or an acceptance threshold), and implicitly the sample counts for a per-task budget , generation costs and verifier cost . The planner evaluates Equation (1) (or Proposition 3) under the fitted posterior for every configuration in a grid and returns the one with the highest predicted success. Costs are either a parameter-count proxy (an 8B-parameter sample costs 1) or compute-matched: parameters measured mean output tokens for the model on that dataset, normalised to Llama-3-8B-Instruct. To cover money and time as well as compute, we also price a sample as (parameters) output tokens: is compute, mimics per-token prices that grow sublinearly with model size, mimics decode latency when larger models are served on more accelerators, and is a flat per-token price. Judge calls cost one generation, test execution costs nothing, and a simulated verifier call costs 0.25.
What accuracy the planner needs
The planner only has to rank configurations, so an error shared by all configurations is harmless. Let be the configurations at a budget, the true success on the evaluation tasks, the prediction, , , , and .
Proposition 4 (Planner regret). Reg .
If , then .
Let be the true success on the calibration tasks and the model’s error there. If calibration and the evaluation tasks are i.i.d. draws from one population, then with probability at least ,
Part (a) explains why regret can be far below forecasting error, and part (c) why it grows only logarithmically with the size of the search space. The constant in (c) is loose for our task counts (see § 6.2).
| Benchmark | Tasks | Samples per task | Generators | Verifier(s) |
| MATH | 128 | 10,000 | 5 (Llama-3 8B/70B, Gemma 2B/7B) | simulated (TPR, FPR, 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 ); 19 reward models; Weaver score |
| SWE-Bench Verified (R2E-Gym rollouts) | 492 | 22 | R2E-Gym 32B agent | LLM patch verifier : thresholds or argmax |
| SWE-Bench Verified (agent pool) | 500 | 1 per system | 175 submitted systems | none (coverage only) |
Table 1. Data. All samples and verdicts come from public releases; we generate nothing new. Benchmarks: MATH (Hendrycks et al. [8]), CodeContests (Li et al. [15]), HumanEval (Chen et al. [4]) with HumanEval+ (Liu et al. [17]), MBPP (Austin et al. [1]), MATH-500, GPQA (Rein et al. [20]) and SWE-Bench Verified (Jimenez et al. [10]). Releases are cited in the text.
Experimental setup
Data. Table 1 lists the benchmarks. MATH and CodeContests samples come from the Large Language Monkeys release (Brown et al. [2]). For CodeContests we executed every unique program against the public tests (the verifier) and against all tests (the ground truth) in isolated subprocesses. HumanEval and MBPP samples and verdicts come from the release of Stroebl et al. [25]; the original tests are the verifier and the extended EvalPlus tests the ground truth. MATH-500 and GPQA candidates with verdicts from eight LLM judges and 19 reward-model scores come from the Weaver release (Saad-Falcon et al. [21]). Calling “a random judge” gives a stochastic verifier whose per-candidate propensity is the fraction of judges that accept. SWE-Bench Verified rollouts with an execution-free verifier probability come from R2E-Gym (Jain et al. [9]). We keep the 492 issues with at least 22 rollouts and draw 22 at random per issue. The agent pool uses official per-instance resolved labels of the 175 systems in the SWE-bench experiments repository (SWE-bench team [26]).
Protocols
Allocation on unseen tasks. Calibrate on a random 50% of tasks from an -sample pilot (32 unless stated), plan for each budget, and score the chosen configuration on the other 50% against ground truth. The oracle is the best configuration in hindsight on the evaluation tasks; regret is oracle success minus achieved success, in percentage points. We use 5 splits (simulated verifier) or 10 (real verifiers) and budgets of 4–256 (sampling) or 16–1,024 (judges) cost units per task. The search space covers single generators and pairs with mixing weights , verifier calls, and, for SWE-bench, thresholds for .
Pilot extrapolation. Draw pilot samples per task ({2,4,6} rollouts on SWE-bench; 4–32 systems for the agent pool) and predict success for all up to the held-out horizon: 8,192 for MATH and CodeContests, about 128 for HumanEval, 16 for SWE-bench rollouts and up to 167 for the agent pool. Truth is computed on held-out samples (exact hypergeometric pass@N for coverage). The metric is the mean absolute error (MAE) over beyond the pilot, over 6–10 random pilots.
Statistics. Headline comparisons use paired Wilcoxon signed-rank tests and bootstrap 95% intervals over shared (model, pilot, seed) or (seed, budget) units (Section D).
Baselines. For allocation: strongest model, most accurate per cost, uniform ensemble, a heuristic adaptation of the compute-optimal exponents of Singhi et al. [23] (, , anchored at at the smallest budget, with the best pilot generator; their study concerns the solve-versus-verify split for one generator with generative verification, so conclusions about this baseline concern transfer to our settings, not their original claim), generation only (), maximum verification (), a fixed threshold of 0.5, no verifier, and SPLIT with errors assumed independent (, ) as an ablation. For forecasting: the power law of Brown et al. [2] fitted to the pilot’s selection curve, the same power law fitted to coverage (implicitly assuming a perfect verifier), per-task plug-in estimates without shrinkage, and the independence formula .
Results
The pilot-calibrated planner allocates near-optimally
Table 2 and Table 3 summarise the main result (see also Figure 2, and Figure 10 and Figure 11 in the appendix). In every setting, a variant of SPLIT is within 0.8 points of the hindsight-optimal configuration on tasks it never saw, and the best variant is within 0.02–0.65 points. Every fixed rule fails somewhere, for an identifiable reason:
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 measured output tokens instead of parameters alone. SPLIT with independent errors is our ablation; the others are fixed rules.
| Method | Simulated verifier MATH | Simulated verifier CodeContests | Sim., compute-matched MATH | Sim., compute-matched CodeContests | CodeContests, real tests param. cost | CodeContests, real tests 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. [23] 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 |
| Most accurate per cost | 19.81 | 5.31 | 20.67 | 4.58 | 3.74 | 3.35 |
Table 2.
Table 3: Allocation regret on unseen tasks: how much to verify (percentage points; mean over budgets/ 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.
| 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. [23] rule | 0.05 | 1.20 | No verifier (random rollout) | 3.58 |
| Generation only () | 0.10 | 2.58 | ||
| Maximum verification () | 1.69 | 3.84 |
Table 3.
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 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.
“Strongest model” and the Singhi et al. rule are near-optimal at large budgets but lose about 12 points on MATH. At small budgets a single Llama-3-70B sample (cost 7.8–8.75) is unaffordable, so they submit nothing. The planner instead draws three Llama-3-8B samples and reaches 36% at a budget of 4. The Singhi rule is slightly better than the planner on CodeContests with parameter-count costs (0.78
vs 0.82) and on MATH-500 (0.05 vs 0.06), but loses under compute-matched costs (0.73 vs 0.65) and on GPQA (1.20 vs 0.02).
“Generation only” is right for MATH-500, where extra judge calls are useless, and loses 2.6 points on GPQA, where they help. “Maximum verification” is never best.
A fixed verifier threshold is wrong at both ends of the budget range on SWE-bench (Figure 6c). With one rollout, filtering through the verifier at threshold 0.5 lowers the resolve rate from 32.5% to 25.1%, because it rejects correct patches with no second attempt to fall back on. The planner uses no verifier at , a lenient threshold at and a stricter one from .
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 and exceeds every threshold for .
Modelling correlation matters for decisions. Assuming independent errors raises regret 1.2–4.8 times (e.g. 0.54 to 1.69 on MATH, 0.11 to 0.53 on GPQA; paired on MATH, CodeContests and real tests). Modelling task-dependent verifier accuracy matters on agents: the pooled-verifier variant mis-picks the strictest threshold at and has regret 2.36, against 0.33 with the task-varying model (). The automatic choice between the two verifier models gives 0.56, a safe default when the right model is unknown (Table 7). Results are unchanged in kind under compute-matched costs, where a Llama-3-70B sample costs 7.8 (MATH) or 10.7 (CodeContests) Llama-3-8B samples. Two comparisons are not significant: the planner against “strongest model” with real CodeContests tests (−0.32 points, ), and against the Singhi rule averaged over the two simulated datasets ( and 0.09 under compute-matched costs), where a large win on MATH is paired with a near tie on CodeContests.
| 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% |
Table 7.
Why regret is small, other costs, and online re-planning
Regret tracks differential, not absolute, error. Proposition 4(a) bounds regret by the difference between the prediction errors of the chosen and the optimal configuration. On CodeContests with real tests, the largest absolute prediction error over the 13 configurations averages 3.2–8.5 points across budgets, but this pairwise error averages only 0.6–2.8 points and the regret 0.2–1.2 (Table 10). On MATH with a simulated verifier the gap is wider still: the largest absolute error averages 11.1 points, the regret 0.54. Most of the absolute error is shared by all configurations and comes from the task sample: the calibration and evaluation halves differ by up to 3–8 points in true success, while SPLIT’s own error on the calibration tasks varies by only 0.6–4.9 points across configurations. The finite-sample term of Proposition 4(c) is vacuous here (60 points at , , ), so the guarantee explains consistency and the dependence, not the size of the observed regret.
| Setting | Regret | Pairwise error | 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 |
Table 10. Planner-regret diagnostics (Proposition 4; percentage points, mean over budgets and splits). Pairwise error is , which bounds regret. Model spread is , the variation across configurations of SPLIT’s error on the calibration tasks. Task gap is . Hoeffding is the finite-sample term of Proposition 4(c) at .
Other prices. Which fixed rule is right depends on how a sample is priced (Figure 3a). On CodeContests with real tests, “strongest model” is optimal when per-token prices are flat or grow with the square root of model size (), and loses 0.9 points otherwise. “Most accurate per cost” is optimal under flat prices and loses 3.3–4.7 points under every other price. The planner’s regret stays between 0.45 and 0.62 points under all five cost models. It is never worse than 0.62, but under flat or latency-like prices, where one model dominates, a fixed rule that happens to pick that model beats it by about half a point (0.45–0.50, ). With the simulated verifier under prices, the planner’s regret is 0.16 points on MATH and 0.79 on CodeContests, against 10.44 and 1.06 for “strongest model” and 9.69 and 0.68 for the Singhi rule. This repeats the pattern of Table 2: a large win on MATH and a near tie on CodeContests.
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 (parameters) × output tokens; “params” prices by parameters only. Zero bars are labelled. (b) Success of online policies minus the static plan (mean ± s.e. over splits). Budgets are pooled across the evaluation tasks.
Online re-planning. The planner fixes a configuration before seeing any task. Under uniform-among-accepted selection, once one candidate of a task is accepted, its success equals the precision and further samples cannot raise it. So a policy can stop a task at its first acceptance and spend the remainder elsewhere. We evaluate two online policies on the E7 splits, simulating samples from each evaluation task’s measured correctness and verifier rates, the same rates that score the static plan (Table 4 and Figure 3b). Early stopping keeps the static plan’s generator mix. Re-planning keeps a per-task posterior over the generators’ rates (importance weights on the copula prior draws, updated by each rejection) and draws the generator, and with a pooled budget the task, with the highest posterior probability of a correct acceptance per unit cost. With a per-task budget, stopping at the first acceptance reaches the static plan’s success while spending 5–25% less. Pooling the savings raises success above the static plan by 0.56 points on average (95% bootstrap interval 0.30–0.80; Wilcoxon ; better in 33 of 40 split–budget pairs). This is statistically indistinguishable from the best static configuration in hindsight (−0.06 points, ), which re-planning beats at . Most of the gain comes from early stopping with a pooled budget. Per-task generator switching adds to it only at small budgets (0.66 points at ); averaged over budgets, re-planning and early stopping with the static mix differ by 0.19 points, which is not significant (). The gains are modest in absolute terms because most CodeContests tasks are never solved by any generator and the public tests rarely accept wrong programs, which leaves little to re-allocate.
| 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 |
| Re-planning, pooled | 3.16 | 1.00 | 7.82 | 1.00 | 11.61 | 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.
Mechanisms
Re-verification lowers the precision ceiling exactly when Equation (2) holds. We treat a call to a random judge among the eight LLM judges in the Weaver release as a stochastic verifier and take the majority of calls. Pooled over MATH-500 candidates, going from to multiplies the acceptance of wrong answers by 1.052 (0.507 → 0.534) but the acceptance of correct answers by only 1.026 (0.931 → 0.955). Because pooled ratios mix heterogeneous tasks, we also evaluate the condition task by task, using each task’s own candidates and judge propensities. Nine calls lower the precision ceiling on 61% of MATH-500 tasks, and the mean per-task ceiling is flat (0.717 vs 0.718). Measured verified success changes by only −0.3 to +0.1 points across (Figure 4b). Many wrong MATH answers fool most judges (Figure 4a): a third of the 11,015 wrong answers are accepted by at least six of the eight judges. Majority voting therefore amplifies the error. On GPQA, pooled wrong-answer acceptance falls (×0.75) while correct-answer acceptance rises (×1.07). Nine calls raise the ceiling on 86% of tasks (mean 0.569 to 0.638) and add +1.2, +3.3 and +4.8 points of verified success at , 16 and 64 (Figure 4c).
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 for : 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.
Pooling verifier accuracy across tasks biases forecasts. SPLIT with pooled judge rates gets the direction of these effects right but overstates the GPQA gain about twofold (Table 5). The cause is not the difficulty prior: a non-parametric prior does no better, and with each task’s true rates SPLIT matches the simulation to 0.2 points. The cause is that judge accuracy is coupled to task difficulty. On GPQA, the per-task TPR and FPR of the judge pool have Spearman correlations of 0.54 and 0.65 with task difficulty, and a pooled rate erases this. Averaging the formula over the calibration tasks’ own candidates and judge propensities (the empirical task population) removes the bias. It predicts the gain at every to within 0.2 points (Table 5) and gives the lowest allocation regret on GPQA (0.02 points). A judge-level IRT model improves decisions but not the size of the effect. The same coupling appears on agents. An LLM patch verifier is more lenient on easy issues, and modelling per-issue verifier rates halves the forecast error on SWE-bench (5.35 to 2.74 points; Table 6).
| Real | +1.2 | +3.3 | +4.8 |
| SPLIT, empirical task population | +1.2 | +3.3 | +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.
Table 6: Extrapolation error. (MAE in percentage points over all 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 -values compare ours with the power law.
| Setting | Target | Horizon | Ours | Power law | Plug-in | |
| MATH + CodeContests, sim. verifier (pilot 32) | selection | 8,192 | 1.9 | 7.6 | — | |
| 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 | ≈128 | 1.69 | 2.13 | 4.55 | |
| SWE-bench, LLM verifier thresholds | selection | 16 | 2.74 | 6.70 | 4.07 | |
| SWE-bench, argmax of verifier score | selection | 16 | 3.28 | 1.58 | 2.11 | 0.006 |
| SWE-bench agent pool (175 systems) | coverage | 25–167 | 2.23 | 1.94 | 4.75 | 0.57 |
Table 6.
A strong scorer is not a universal selector. Submitting the candidate with the highest Weaver aggregated score ([21]) reaches 86–93% on MATH-500 ( to 64), well above judge-based selection (≈81%). On GPQA it reaches only ≈43%, below a single judge call (46–49%). Which selector to use is itself a decision that a pilot can make.
Stronger generators fool fixed tests more; for scored verifiers this is calibration. Stroebl et al. [25] reported that a model’s single-sample accuracy is strongly correlated with its false-positive rate on HumanEval and MBPP. We replicate this with per-task FPRs on the HumanEval+ ground truth: Spearman across 17 models (), from 1.5% for Vicuna-7B to 31% for GPT-4o. We also replicate it on MBPP+ ( across 10 models, ), and find the same ordering for CodeContests public tests (Figure 5a). For scored verifiers the picture differs. Across 19 reward models on MATH-500, the wrong answers of Llama-3.1-70B-Instruct pass a fixed threshold more often than those of Llama-3.1-8B-Instruct for 16 of 19 reward models (sign test ). When the threshold is re-tuned so that each generator’s correct answers pass at the same 90% rate, the effect disappears (9 of 19, ). The capability effect for reward models is a shift of the whole score distribution, which per-generator calibration removes; pass/fail tests offer no such knob. For allocation, this means the verifier must be re-measured whenever the generator changes, which the pilot does.
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 [25]). (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).
Shared blind spots set the value of mixing models. Generators mostly fail on the same problems. On MATH, the per-problem solve rates of Llama-3-8B-Instruct and Gemma-7B correlate at 0.80, and 38 of the 128 problems are solved less than 5% of the time by both. Pilot-estimated copula correlations between model pairs are 0.67–0.96 on MATH and CodeContests (Figure 9, Section C). Assuming independent failures overstates the gain from mixing two models by up to about 7 points, with a mean error of 2.81 points, whereas SPLIT (with the copula) predicts the gain with a mean error of 0.43 points. For Llama-3-8B-Instruct and Gemma-7B on MATH (), independence promises +5 points; the real gain is +1.6 and the SPLIT predicts +2.4. The same structure appears among agents: of 500 SWE-Bench Verified issues, 26 are resolved by none of 175 submitted systems and 67 by fewer than 5% of them (Figure 7d).
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 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.
Forecasting success far beyond the pilot
The allocation results need SPLIT to rank configurations correctly, not to forecast exact success rates. Table 6 reports how well it does as a forecaster. The picture is mixed, and we report it in full.
Where SPLIT helps. With a verifier that has a non-zero FPR, success plateaus. A power law fitted to the pilot keeps predicting growth and misses by 7.6 points at 8,192 samples; SPLIT misses by 1.9 (simulated verifier; Figure 12). The power law fitted to coverage, which implicitly assumes a perfect verifier, is off by 6–24 points with real verifiers. With real tests the margin over the power law is small but significant: 0.6 points on CodeContests (80,403 executed programs, Figure 8) and 0.4 points on HumanEval across 17 generators (Figure 13). On agentic SWE-bench the task-varying verifier model is 4 points better than the power law.
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 against pilot size for three generators and 10 pilots.
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 § 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.
Where it does not. For pure coverage, the power law is slightly better than the beta-binomial prior in SPLIT (2.6 vs 3.3 points), consistent with the heavy-tailed explanation of Schaeffer et al. [22]. For argmax selection on SWE-bench, our estimator improves from 4.5 to 3.3 points with the per-issue score shift, and its error at (+2.4) matches the power law’s (+2.3). Averaged over , the power law is still better (1.6 points, ; Table 9, Figure 14). The estimator is sensitive to the upper tail of the score distribution, as Proposition 3 predicts: replacing the empirical residual tails with Gaussian tails turns a 5-point over-prediction into a 7-point under-prediction.
| Method | MAE (points) | Error at |
| 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 |
Table 9. Argmax selection on SWE-Bench Verified (6-rollout pilot, 10 draws).

Figure 14. Argmax (best-of-) 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 , by 1.8 points at and 4.4 at . (b) Extrapolation error.
A long horizon with real agents. No public release we found has more than about 25 labelled rollouts of one agent per SWE-bench issue. As a long-horizon test of the coverage component (the difficulty prior), we treat an “attempt” as a system drawn at random from the 175 SWE-bench Verified submissions. Random splitting makes systems exchangeable, so for each issue the held-out systems behave as draws with a common success rate and the coverage term of the formula applies. There is no shared verifier, so this does not test selection, and the attempts come from different policies rather than repeated runs of one agent. We calibrate on a random pilot of 4–32 systems and predict coverage out to every held-out system, up to about 20 times the pilot for the smallest pilots (Figure 7, Table 8). The power law and SPLIT with an NPMLE prior are statistically tied (1.9 vs 2.2 points, ). The beta prior is worse (3.8 points) because it puts too little mass on unsolvable issues. With the NPMLE prior, SPLIT is nearly unbiased at the largest : its mean signed error is −2.3 to +0.1 points, while the power law over-predicts in every configuration (+0.5 to +3.6). It is noisier from pilot to pilot, however, so its mean absolute end-point error is larger (2.9 vs 2.0, ). When the pilot consists of the oldest systems, every method under-predicts badly for small pilots, because later systems are much stronger. A pilot must represent the generators that will actually be deployed.
| 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 |
Table 8. Agent pool: extrapolation MAE (points; random splits, 10 seeds). Horizon = all held-out systems.
Limitations and conclusion
Limitations.
Point forecasts. SPLIT’s advantage over power-law extrapolation is large only under a simulated verifier and on SWE-bench thresholds. It is small (0.4–0.6 points) with real tests, absent for pure coverage, and negative for argmax selection (Table 6). Our claims rest on decisions and mechanisms, not on forecasting accuracy.
Same-policy agent horizons. The longest same-agent horizon we can test is 16 held-out rollouts per issue, because no public release we found has more. The 175-system pool tests long horizons for coverage only, with no shared verifier. Testing selection at long horizons with one agent needs new rollouts. We release a pipeline that collects, scores and analyses them (Section E), but have not run it: at 64 rollouts per issue it needs about 32,000 agent runs.
Representative pilots. All estimators assume the pilot is exchangeable with deployment. Under capability drift (pilot of older systems), every method fails for small pilots (§ 6.4). Some refinements also need labelled calibration tasks with repeated judge verdicts.
Costs. Prices and latency enter through a one-parameter family, (parameters) measured tokens, not through quoted provider prices. Latency is modelled as additive cost, which ignores parallel sampling. Judge calls are priced as one generation.
Model choice. Neither the pooled nor the task-varying verifier model is best on every dataset. Our out-of-sample selection rule is never the worse of the two but is significantly behind the better one on two of three datasets (Section C).
Theory. The propositions are exact under conditional independence of candidates given the task (Assumption 1). Dependence among candidates within a task, such as duplicated or near-duplicated answers, is not modelled and may bias SPLIT, especially at large . The verifier propensity models repeated calls on one candidate, not correlated candidates. The planner’s finite-sample regret guarantee (Proposition 4) is vacuous at our task counts; it explains consistency, not the size of the observed regret.
Online policy. The re-planning policy is a greedy index, not an optimal sequential policy. It ignores the risk that a false acceptance ends a task, and is evaluated only on CodeContests, by simulation from measured per-task rates.
Agent pool. The 175-system experiment treats different systems as exchangeable attempts. This tests the difficulty prior at long horizons but is not a test of one agent’s repeated sampling or of selection.
Conclusion. Test-time compute is limited by selection as much as by generation. A small labelled pilot, interpreted through an exact success formula that accounts for difficulty, shared blind spots and correlated verifier errors, is enough to decide how many samples to draw, which generators to mix, and how much to verify. Across math, science QA, code and agents this decision is within a fraction of a point of the best possible, where fixed rules can lose 2.5 to 20 points. The planner needs only to rank configurations, so its regret is bounded by differential, not absolute, forecast error, and it stays near-optimal when samples are priced by compute, by sublinear per-token prices or by latency. The same model explains when re-verification backfires and why pooled verifier statistics mislead. Re-planning online, by stopping a task at its first accepted candidate and moving the savings to unresolved tasks, recovers the gap to the best static configuration in hindsight. The most useful next step is to test selection on long same-agent rollouts, for which we release a ready-to-run pipeline.
Broader Impact Statement
This work helps practitioners spend inference compute more efficiently, which can reduce the cost and energy use of deployed language-model systems. It also documents failure modes that matter for oversight. Stronger generators produce wrong outputs that pass fixed checks more often, and asking more LLM judges can make acceptance of wrong answers more likely when judges share blind spots. Systems that rely on automated verification for safety-relevant decisions should re-measure verifier error rates whenever the generator changes, and should not assume that majority votes of judges converge to the truth. Our planner optimises measured success on a benchmark-defined notion of correctness; when that notion is itself flawed (e.g. weak tests), the planner will optimise the flawed target. All data are public releases; we collected no human data.
Proofs
Throughout, Assumption 1 holds, abstention counts as failure, when , and . Numerical checks of every statement below, of the corrected conditions and of the edge cases (26 checks) are included in the code release.
Proposition 1 (exact success formula)
Proof. Give each candidate an independent arrival time , independent of all . Choosing uniformly among accepted candidates has the same distribution as choosing the accepted candidate with the smallest , because the arrival order is a uniformly random permutation independent of acceptance. Candidate is selected and correct iff it is accepted and correct and every with is rejected. Conditioning on and using independence across candidates,
since . Integrating over and summing over , grouping the exchangeable candidates of generator , gives (1). For one generator, for , which is non-decreasing in with limit . If then and .
The implementation uses the closed form for one generator and evaluates the mixed-generator integral by 480-node log-spaced trapezoidal quadrature; it agrees with Monte Carlo to within .
Convergence regimes
Proposition 5 (Regimes). Let on , , one generator, and .
(a) If for all tasks, then .
(b) If has a density with as for some , then .
(c) If for , with , then . This is an upper bound only.
(d) For any FPRs and any , .
Proof. (a) , and is a convex combination of and , so ; then use . (b) Fix with on . The integral over is at most . On , substitute : . The integrand converges to and is dominated by , so dominated convergence gives (cf. [cf. 22]). (c) As in (a), and , so . Writing the expectation through the CDF, . The true gap can decay faster (for instance if tasks with small also have small ). (d) Couple the verifier with FPR to one with FPR 0: same labels, same acceptance of correct candidates, same arrival times, and wrong candidates accepted only by the first verifier. If no wrong candidate is accepted, both selectors make the same choice. The FPR-0 selector succeeds iff some correct candidate is accepted, with probability . The other can only do worse, and only on the event that a wrong candidate is accepted, which has probability at most by a union bound.
Shared blind spots
Proposition 6 (Diversity). Let two generators have per-task rates with a.s., conditionally independent labels given , a perfect verifier, a budget split as and ( continuous), and . Assume the weighted log-moments below are finite.
(a) is concave.
(b) for some iff with . An interior strictly better than both endpoints exists iff and .
(c) If and have the same marginal law, , with equality iff a.s.
(d) If , with standard bivariate normal with correlation , then is non-increasing in .
Proof. (a) With and , is an expectation of the exponential of an affine function of , hence convex. (b) , and by concavity exceeds somewhere iff . If and , a maximiser of the concave cannot be at an endpoint and is strictly better than both endpoints. Conversely, if at an interior , concavity gives , and symmetrically . (c) With and , Cauchy–Schwarz gives . Equality iff a.s., i.e. , i.e. since is injective for . (d) with is a product of two non-negative functions monotone in the same direction, hence supermodular. Gaussian copulas increase in in the supermodular order [18], so is non-decreasing in while does not depend on .
With identical marginals the gain decreases to zero as ; with unequal marginals it is only non-increasing. We make no analytic claim for imperfect verifiers; the planner evaluates (1) numerically over mixing weights.
Proposition 2 (re-verification)
Proof. (a) For , by the law of large numbers; for odd , exactly by symmetry. Bounded convergence gives the limits. (b) and for all . (c) Given the propensities, majority verdicts satisfy Assumption 1 with and , so Proposition 1 gives the ceiling , strictly decreasing in for . Hence the ceiling with calls exceeds the ceiling with calls iff ; with this is the negation of (2). Since by (a), the same comparison holds for . At the ceiling is 0 or 1 for every . For a joint limit in which and grow together while , one additionally needs so that abstention vanishes.
Example and counterexample. Let , so 60% of wrong answers fool most calls: and . If , then and the ceiling at falls from 0.561 to 0.500. If instead , then and , so , and the ceiling rises from 0.460 to 0.526 even though .
Proposition 3 (argmax selection)
Proof. (a) The maximum score is a.s. unique because is atomless. By exchangeability it belongs to candidate 1 with probability , so . (b) The top occupied bin is with probability (). Conditional on lying in bin , a candidate is correct with probability , independently of the others. Given that is the top occupied bin, exchangeability and the multi-break give success probability . Empty bins contribute zero. (c) Binned: for and for , so and only the term survives. Continuous: let . Conditional on , the maximiser is correct with probability , so . Since for below the upper endpoint , , so in probability. As converges to at , bounded convergence gives . Without the existence of this limit no ceiling of this form follows.
Proposition 4 (planner regret)
Proof. (a) Since maximises , . Hence , which is at most . (b) If , then , contradicting (a). (c) Write with . Oscillation is subadditive, so . For a fixed , is a difference of two independent means of per-task success values in with equal expectations, so Hoeffding’s inequality gives . A union bound over and (a) complete the proof. The bound holds for any estimator: may depend on the pilot arbitrarily, because does not involve the estimator.
Estimation details
Difficulty. Beta-binomial (optionally zero-inflated) hyper-parameters are fitted by maximum likelihood on the pilot counts of the calibration tasks. Per-task posteriors are , or the corresponding mixture when zero-inflated. The NPMLE uses EM on a fixed grid of 200 support points that is dense near 0 and 1 and includes the endpoints.
Copula. Pairwise correlations are fitted by maximising the bivariate beta-binomial likelihood under a Gaussian copula, using Gauss–Hermite quadrature. This is accurate for pilot-scale (up to a few hundred). The matrix is projected to the nearest correlation matrix, and – Monte Carlo draws of represent the prior.
Verifier. The pooled model estimates the TPR from the accepted fraction of correct pilot samples, and a beta prior over per-task FPRs by beta-binomial maximum likelihood on the accepted counts of wrong pilot samples. The task-varying model fits beta-binomial marginals for , TPR and FPR and a Gaussian-copula correlation from per-task pilot counts. Each task’s TPR is observed through its correct samples and its FPR through its wrong ones. For LLM judges, a candidate’s propensity is the fraction of the eight judges that accept it. The concentrations and are fitted by beta-binomial likelihood on these acceptance counts (typical values: , on MATH-500; , – on GPQA). The simulated verifier of Table 2 uses , per-task with mean 0.1 and concentration 2, and .
Automatic verifier-model choice. Both verifier models are fitted on the first half of each calibration task’s pilot samples. Each predicts verified success at the full pilot size. We keep the model whose prediction is closer to the model-free success of uniform-among-accepted selection on the full pilot.
Argmax. Verifier probabilities are binned into 20 equal-width bins on . The issue-level model is on logit scores, with a random intercept fitted by EM. Class-conditional residual distributions are kept empirical. Predictions combine the posterior of with the shifted class-conditional bin probabilities.
Additional results
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 (), ties the better one on HumanEval (), and is behind it on CodeContests and SWE-bench (0.28 and 0.71 points, ).
Significance tests
Table 11: Paired tests for headline comparisons. Mean difference (ours minus comparator; negative favours ours) with bootstrap 95% interval and Wilcoxon signed-rank -value. Units are shared (model, pilot, seed) for MAE and (dataset, seed, budget) for regret.
| Comparison | Mean diff. [95% CI] | |
| Selection MAE, sim. verifier: SPLIT vs power law | −5.71 [−6.17, −5.22] | |
| 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] | |
| SWE-bench MAE: SPLIT, task-varying vs power law | −3.97 [−4.34, −3.59] | |
| 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 |
| Agent-pool at max : SPLIT, NPMLE vs power law | +0.99 [+0.46, +1.56] | 0.004 |
| Regret, sim.: SPLIT vs independent errors | −0.67 [−1.10, −0.30] | 0.003 |
| Regret, sim.: SPLIT vs strongest model | −5.99 [−10.03, −2.47] | 0.009 |
| Regret, sim.: SPLIT vs Singhi et al. [23] | −5.69 [−9.87, −2.08] | 0.13 |
| Regret, sim., compute-matched: SPLIT vs Singhi et al. [23] | −5.78 [−9.98, −2.16] | 0.09 |
| Regret, real tests: SPLIT vs independent errors | −0.84 [−1.22, −0.50] | |
| Regret, real tests: SPLIT vs strongest model | −0.32 [−0.92, +0.23] | 0.43 |
| Regret, judges: empirical task population vs Singhi et al. [23] | −0.58 [−0.76, −0.42] | |
| Regret, judges: empirical task population vs judge-level IRT | −0.00 [−0.03, +0.02] | 0.93 |
| Regret, SWE-bench: SPLIT, task-varying vs fixed threshold 0.5 | −2.29 [−3.12, −1.52] | |
| Regret, SWE-bench: SPLIT, task-varying vs pooled verifier | −2.03 [−3.37, −0.88] | 0.005 |
| Regret, real tests, : SPLIT vs strongest model | −0.32 [−0.90, +0.21] | 0.55 |
| Regret, real tests, : SPLIT vs most accurate per cost | −4.13 [−5.28, −2.92] | |
| Regret, real tests, : SPLIT vs strongest model | +0.45 [+0.22, +0.72] | |
| Regret, real tests, : SPLIT vs strongest model | +0.50 [+0.26, +0.80] | 0.001 |
| Regret, sim., : SPLIT vs Singhi et al. [23] | −4.71 [−9.01, −1.02] | 0.59 |
| Regret, online: re-planning (pooled) vs static plan | −0.56 [−0.81, −0.31] | |
| Regret, online: re-planning (pooled) vs static oracle | +0.06 [−0.34, +0.49] | 0.48 |
| Regret, online: re-planning vs early stopping (both pooled) | −0.19 [−0.54, +0.15] | 0.28 |
Table 11.
Data, compute and reproducibility
Data sources. MATH and CodeContests samples: Large Language Monkeys release (Brown et al., [2]). HumanEval and MBPP samples with EvalPlus verdicts: release accompanying Stroebel et al. (2024). MATH-500 and GPQA candidates with LLM-judge verdicts, reward-model scores and Weaver scores: Weaver release [21]. SWE-Bench Verified rollouts with verifier probabilities: R2E-Gym release [9]. Per-instance results of 175 systems: SWE-bench experiments repository [26]. We use these releases under their respective licenses. We do not redistribute model outputs. The code release includes only derived per-sample correctness labels and verifier verdicts, so that the main experiments run without the multi-gigabyte downloads.
Compute. All experiments run on a single 8-core laptop CPU. Executing the CodeContests programs takes about 1.5 hours; the remaining experiments take roughly 5–8 hours in total. No GPU or model API is used.
Reproducibility. The code will be released publicly. It contains the estimators, the planner, the online policies, scripts that regenerate every number and figure in this paper from the public releases, 35 unit tests, and 26 numerical checks of the propositions. Random seeds are fixed. Token counts for compute-matched and price costs are measured from the released samples.
Long same-agent rollouts. The code release also contains a pipeline for the experiment that public data cannot support: collect rollouts of one fixed agent per SWE-Bench Verified issue with a standard open-source scaffold, score them with the official evaluation harness and an execution-free LLM verifier ( from the first-token log-probabilities), and re-run the threshold and argmax analyses with pilots of 4–16 rollouts and horizons up to . At this is 32,000 agent runs. A self-test runs the analysis path on resampled public rollouts.
References
- [1]Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021.arxiv.org/abs/2108.07732
- [2]Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024.arxiv.org/abs/2407.21787
- [3]Lingjiao Chen, Jared Quincy Davis, Boris Hanin, Peter Bailis, Ion Stoica, Matei Zaharia, and James Zou. Are more LLM calls all you need? towards scaling laws of compound inference systems. arXiv preprint arXiv:2403.02419, 2024.arxiv.org/abs/2403.02419
- [4]Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021.arxiv.org/abs/2107.03374
- [5]Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021.arxiv.org/abs/2110.14168
- [6]Bradley Efron. Large-Scale Inference: Empirical Bayes Methods for Estimation, Testing, and Prediction. Cambridge University Press, 2010.
- [7]Ryan Ehrlich, Bradley Brown, Jordan Juravsky, Ronald Clark, Christopher Ré, and Azalia Mirhoseini. CodeMonkeys: Scaling test-time compute for software engineering. arXiv preprint arXiv:2501.14723, 2025.arxiv.org/abs/2501.14723
- [8]Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Advances in Neural Information Processing Systems, Datasets and Benchmarks Track, 2021.
- [9]Naman Jain, Jaskirat Singh, Manish Shetty, Liang Zheng, Koushik Sen, and Ion Stoica. R2E-Gym: Procedural environments and hybrid verifiers for scaling open-weights SWE agents. arXiv preprint arXiv:2504.07164, 2025.arxiv.org/abs/2504.07164
- [10]Carlos E. Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. SWE-bench: Can language models resolve real-world GitHub issues? In International Conference on Learning Representations, 2024.arxiv.org/abs/2310.06770
- [11]Sayash Kapoor, Benedikt Stroebl, Peter Kirgis, Nitya Nadgir, Zachary S. Siegel, Boyi Wei, Tianci Xue, Ziru Chen, et al. Holistic agent leaderboard: The missing infrastructure for AI agent evaluation. arXiv preprint arXiv:2510.11977, 2025.arxiv.org/abs/2510.11977
- [12]J. Kiefer and J. Wolfowitz. Consistency of the maximum likelihood estimator in the presence of infinitely many incidental parameters. The Annals of Mathematical Statistics, 27(4):887–906, 1956.
- [13]Yubin Kim, Ken Gu, Chanwoo Park, Chunjong Park, Samuel Schmidgall, A. Ali Heydari, Yao Yan, Zhihan Zhang, et al. Towards a science of scaling agent systems. arXiv preprint arXiv:2512.08296, 2025.arxiv.org/abs/2512.08296
- [14]Krishna K. Ladha. The Condorcet jury theorem, free speech, and correlated votes. American Journal of Political Science, 36(3):617–634, 1992.DOI
- [15]Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, et al. Competition-level code generation with AlphaCode. Science, 378(6624):1092–1097, 2022.DOI
- [16]Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, et al. Let’s verify step by step. arXiv preprint arXiv:2305.20050, 2023.arxiv.org/abs/2305.20050
- [17]Jiawei Liu, Chunqiu Steven Xia, Yuyan Wang, and Lingming Zhang. Is your code generated by ChatGPT really correct? rigorous evaluation of large language models for code generation. In Advances in Neural Information Processing Systems, 2023.
- [18]Alfred Müller and Marco Scarsini. Some remarks on the supermodular order. Journal of Multivariate Analysis, 73(1):107–119, 2000.DOI
- [19]OpenAI. Introducing SWE-bench verified. https://openai.com/index/introducing-swe-bench-verified/, 2024.
- [20]David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R. Bowman. GPQA: A graduate-level Google-proof Q&A benchmark. arXiv preprint arXiv:2311.12022, 2023.arxiv.org/abs/2311.12022
- [21]Jon Saad-Falcon, E. Kelly Buchanan, Mayee F. Chen, Tzu-Heng Huang, Brendan McLaughlin, Tanvir Bhathal, Shang Zhu, Ben Athiwaratkun, et al. Shrinking the generation-verification gap with weak verifiers. arXiv preprint arXiv:2506.18203, 2025.
- [22]Rylan Schaeffer, Joshua Kazdan, John Hughes, Jordan Juravsky, Sara Price, Aengus Lynch, Erik Jones, Robert Kirk, et al. How do large language monkeys get their power (laws)? arXiv preprint arXiv:2502.17578, 2025.arxiv.org/abs/2502.17578
- [23]Nishad Singhi, Hritik Bansal, Arian Hosseini, Aditya Grover, Kai-Wei Chang, Marcus Rohrbach, and Anna Rohrbach. When to solve, when to verify: Compute-optimal problem solving and generative verification for LLM reasoning. arXiv preprint arXiv:2504.01005, 2025.arxiv.org/abs/2504.01005
- [24]Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.arxiv.org/abs/2408.03314
- [25]Benedikt Stroebl, Sayash Kapoor, and Arvind Narayanan. The limits of inference scaling through resampling. arXiv preprint arXiv:2411.17501, 2024.arxiv.org/abs/2411.17501
- [26]SWE-bench team. SWE-bench experiments: per-instance evaluation results of submitted systems. https://github.com/SWE-bench/experiments, 2026. Accessed October 2026.
- [27]Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representations, 2023.arxiv.org/abs/2203.11171
- [28]John Yang, Carlos E. Jimenez, Alexander Wettig, Kilian Lieret, Shunyu Yao, Karthik Narasimhan, and Qfir Press. SWE-agent: Agent-computer interfaces enable automated software engineering. arXiv preprint arXiv:2405.15793, 2024.arxiv.org/abs/2405.15793
- [29]Yingxuan Yang, Chengrui Qu, Muning Wen, Laixi Shi, Ying Wen, Weinan Zhang, Adam Wierman, and Shangding Gu. Understanding agent scaling in LLM-based multi-agent systems via diversity. arXiv preprint arXiv:2602.03794, 2026.arxiv.org/abs/2602.03794
- [30]Lunjun Zhang, Arian Hosseini, Hritik Bansal, Mehran Kazemi, Aviral Kumar, and Rishabh Agarwal. Generative verifiers: Reward modeling as next-token prediction. arXiv preprint arXiv:2408.15240, 2024.arxiv.org/abs/2408.15240










