PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Srinivasan Iyengar

arXiv:2610.23255v1cs.LGcs.CL

TL;DR

Imperfect verifiers can make the correctness of a submitted answer lag behind candidate coverage, leaving practitioners to allocate a fixed inference budget among sampling, models, and verification. SPLIT fits an exact selection model from a labelled pilot and plans that allocation. Across the evaluated settings, it comes close to the hindsight-best allocation, while fixed rules lose at least 2.5 points somewhere.

  • Problem

    With imperfect, correlated verifiers, more samples can raise coverage without reliably improving the submitted answer, and fixed-budget choices about sampling, models, and verification lack a dependable rule.

    Source: §1 · p. 1

  • Method

    SPLIT fits an exact success formula from a labelled pilot and uses it to choose generators, sample counts, verifier calls, or thresholds under a budget.

    Source: §1 · p. 2, §4 · p. 6

  • Results

    0.02–0.8 points from the hindsight-optimal allocation on unseen tasks, SPLIT beats every tested fixed rule, each of which loses at least 2.5 points somewhere.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The model identifies when re-verification can lower precision and supports near-optimal allocation under varied sample costs and online replanning.

    Source: §1 · p. 2

    The theory assumes candidates are conditionally independent given a task, so within-task dependence such as duplicated answers is unmodelled and may bias SPLIT, especially at large N.

    Source: §7 · p. 15

Abstract

from arXiv · show

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.

1 Introduction

More inference-time sampling can raise coverage without raising the correctness of the submitted answer, because imperfect, correlated verifiers can cap selection. SPLIT uses a labelled pilot and an exact selection model to allocate a fixed budget; it performs near the hindsight-best allocation across the evaluated settings.

1 Introduction

  • SPLIT fits an exact selection formula from a small labelled pilot and chooses how to split a fixed budget across generators, samples, and verification.The model accounts for task difficulty, shared generator blind spots, and correlated repeated verifier calls.Source: §1 · p. 2
  • 0.02–0.8 points from the hindsight-optimal allocation on unseen tasks, SPLIT outperforms every tested fixed rule, each of which loses at least 2.5 points somewhere.Its regret stays within 0.62 points under five sample-pricing schemes, and an online variant matches the best static configuration in hindsight.Source: §1 · p. 2
  • The paper reports three measured verifier mechanisms: re-verification can lower precision under a stated condition, pooling task-dependent judge accuracy biases forecasts, and scored-verifier false-positive trends reflect threshold calibration.The re-verification condition is met by real LLM judges on MATH-500 but not GPQA.Source: §1 · p. 2
  • SPLIT beats power-law extrapolation under simulated verification and on agentic SWE-Bench Verified, modestly but significantly on code with real tests, but not for pure coverage or argmax selection.The long-horizon comparison uses a pool of 175 SWE-bench agent systems.Source: §1 · p. 2
  • The experiments use publicly released samples and verdicts, with no API budget spent.The authors report locally re-executing 80,403 CodeContests programs and paired significance tests for every headline comparison.Source: §1 · p. 2
  • Majority voting on MATH can stall near 43% verified success while coverage reaches 98%, illustrating why more samples do not ensure a better submitted answer.Real verifiers may accept wrong answers, reject right ones, and make correlated mistakes.Source: §1 · p. 1, Figure 1 · p. 3

2 Related work

Prior work studies coverage scaling, imperfect-verifier limits, compute allocation, and agent rollouts. SPLIT adds pilot-calibrated prediction and allocation that explicitly model selection and correlated errors.

Repeated sampling and coverage laws

  • Prior coverage work models how success probability rises with sample count, while SPLIT adds a mechanistic model of selection and pilot-calibrated allocation.The paper also derives an exact condition for verification-call non-monotonicity, related to prior findings on voting accuracy.Source: §2 · p. 3

Imperfect verifiers

  • SPLIT turns imperfect-verifier bounds into a pilot-estimated predictive model with correlated errors, then uses it to allocate compute.It replicates the accuracy–false-positive-rate correlation on HumanEval+, MBPP+, and CodeContests, and refines the finding for scored verifiers.Source: §2 · p. 3

Compute-optimal test-time scaling

  • Compared with compute-optimal power-law allocation, SPLIT models cross-generator and repeated-verifier correlations and jointly chooses generators, samples, calls, and thresholds.Singhi et al. (2025) provide the power-law rule used as a baseline.Source: §2 · p. 3

Agents and best-of-N for software engineering

  • SPLIT tests agent allocation using public R2E-Gym rollouts and per-instance results from 175 SWE-bench submissions.Prior agent-scaling work described here finds outcomes depend on scaffold and agent diversity, not only rollout count.Source: §2 · p. 4

Statistical tools

  • The paper combines empirical Bayes estimation, Gaussian-copula dependence analysis, and correlated-vote theory for its statistical tools.The cited foundations include Efron (2010), Kiefer & Wolfowitz (1956), Müller & Scarsini (2000), and Ladha (1992).Source: §2 · p. 4

3 The success formula for verified best-of-N

The section derives success probabilities for accepted-candidate and top-score selection, incorporating task-level difficulty and dependence. It identifies precision ceilings and conditions under which mixing generators or adding verifier calls helps or hurts.

Setting and assumptions

  • The model represents task-varying difficulty, cross-generator dependence, task-dependent verifier rates, and dependence across repeated calls on a candidate.Candidates are assumed conditionally independent given the task; repeated-call dependence enters through a candidate-level propensity.Source: §3 · p. 4

The success formula

  • Uniform selection among accepted candidates has success equal to the probability some candidate is accepted times acceptance precision, and success approaches the precision ceiling a/s.With false-positive rate bounded away from zero, saturation is exponential; when false-positive rates have mass near zero, the bound is polynomial.Source: §3 · p. 4

Shared blind spots

  • Mixing a second generator strictly improves coverage when it performs better on tasks the first generator still fails, and the gain from an even mix decreases as Gaussian-copula correlation rises.The planner needs a pairwise correlation estimate from the pilot.Source: §3 · p. 4

Correlated re-verification

  • More majority-vote calls lower the large-sample precision ceiling exactly when they inflate false acceptances proportionally more than true acceptances; a higher FPR alone is insufficient.Whether this happens depends on how often the same wrong answers fool judges and how strongly the calls also improve acceptance of correct answers.Source: §3 · p. 5

Argmax selection

  • For argmax selection, the formula uses class-conditional score distributions; as sample count grows, success converges to precision at the top of the score distribution.Whether top-score precision exceeds average acceptance precision depends empirically on the score-distribution upper tails.Source: §3 · p. 5

4 From a pilot to a plan

SPLIT estimates the selection model from a labelled pilot, evaluates candidate configurations under a cost budget, and chooses the highest predicted success. Its regret bound depends on relative forecast errors, while its theory and evaluation have explicit scope limits.

Pilot estimation

  • Pilot calibration typically uses 8–64 labelled samples per task; empirical Bayes estimates the joint distribution of task difficulty and verifier behaviour.The described variants include task-varying verifier rates, empirical task populations for judges, and per-task score calibration for argmax selection.Source: §4 · pp. 5–6

Planner

  • The planner evaluates configurations under a budget and returns the one with highest predicted success, accounting for generator and verifier costs.Costs can represent compute, sublinear per-token prices, or decode latency; judge calls cost one generation in the stated setup.Source: §4 · p. 6

What accuracy the planner needs

  • Planner regret is bounded by the spread of prediction errors across configurations, so a shared error does not affect which configuration is selected.The finite-sample regret guarantee's constant is loose at the paper's task counts.Source: §4 · p. 6

Data

  • The benchmark table lists datasets spanning math, code, science QA, and software engineering, including MATH, GPQA, and SWE-Bench Verified.The data and verdicts are from public releases; no new samples are generated.Source: Table 1 · p. 7

5 Experimental setup

The experiments use public benchmark and agent-system releases, calibrate on pilot data, and evaluate allocation and forecasting on held-out tasks. They compare SPLIT with fixed rules and forecasting baselines using repeated splits and paired statistical tests.

5 Experimental setup

  • The benchmark data span math, code, science QA, software-engineering rollouts, and 175 SWE-bench agent systems, with verifier and ground-truth labels drawn from public releases.CodeContests programs were run against public tests and all tests; HumanEval and MBPP use original tests and EvalPlus tests, respectively.Source: §5 · p. 7
  • For unseen-task allocation, pilots use a random 50% of tasks and chosen configurations are scored on the other half against the hindsight-best configuration.Evaluation uses five splits for simulated verifiers or ten for real verifiers, with sampling budgets of 4–256 or judge budgets of 16–1,024 cost units per task.Source: §5 · p. 7
  • Forecasting fits on pilots of 8–64 samples per task and predicts success beyond the pilot horizon, using held-out samples or exact hypergeometric pass@N for coverage as truth.Mean absolute error is averaged over post-pilot N values and 6–10 random pilots.Source: §5 · p. 7
  • Headline comparisons use paired Wilcoxon signed-rank tests and bootstrap 95% intervals over shared model, pilot, seed, or budget units.The statistical procedures are specified in Section D.Source: §5 · p. 7
  • Table 2 reports mean allocation regret for samples and generators, while Table 3 reports regret for solve-versus-verify and patch-verifier threshold choices.Both captions define regret relative to hindsight-optimal configurations; Table 2 specifies percentage points below that optimum, with lower values better.Source: Table 2 · p. 8, Table 3 · p. 8
  • Allocation baselines include model-selection and verification heuristics, fixed thresholds, no-verifier or verifier-extreme choices, and an independence ablation; forecasting baselines include power-law and plug-in estimates.The allocation comparison adapts Singhi et al. (2025) to these settings; the paper cautions that their original study concerns a narrower solve-versus-verify setting.Source: §5 · p. 8

6 Results

SPLIT allocates test-time compute near the hindsight optimum, while fixed rules fail in some settings. The results identify when verification, online re-planning, and long-horizon forecasting help or fall short.

6.1 The pilot-calibrated planner allocates near-optimally

  • Across settings, SPLIT variants finish within 0.8 points of the hindsight optimum (best: 0.02–0.65); on CodeContests, Figure 2 shows an approximately 1.2-point oracle gap.Every fixed rule fails somewhere.Source: §6.1 · p. 8, Figure 2 · p. 9
  • Fixed policies break across contexts: extra judge calls are useless on MATH-500 but help GPQA, while a fixed 0.5 threshold cuts SWE-Bench resolution at one rollout.For the threshold case, the resolve rate falls from 32.5% to 25.1%.Source: §6.1 · p. 9

6.2 Why regret is small, other costs, and online re-planning

  • On CodeContests, absolute forecast errors average 3.2–8.5 points while regret is 0.2–1.2; planner regret stays 0.45–0.62 across five price models.Regret tracks pairwise error between the chosen and optimal configurations, rather than absolute forecast error.Source: §6.2 · pp. 9–10
  • Online early stopping spends 5–25% less under per-task budgets; pooled savings raise success by 0.56 points on average, with most gain from early stopping.Generator switching adds to gains only at small budgets.Source: §6.2 · p. 11

6.3 Mechanisms

  • Task-specific judge rates remove pooling bias, predicting GPQA gains within 0.2 points; nine calls lower the precision ceiling on 61% of MATH-500 tasks.The judge rates are coupled to task difficulty.Source: §6.3 · p. 11
  • On HumanEval+, generator pass@1 correlates with per-task false-positive rates (ρ = 0.97); for reward models, the effect disappears after equal-TPR threshold retuning.The study reports the same ordering on CodeContests and a correlation of ρ = 0.95 on MBPP+.Source: §6.3 · p. 12
  • Shared blind spots limit the value of model mixing: independence overstates mixing gains by up to about 7 points, while the copula predicts them with 0.43-point mean error.On MATH, independence predicts a 5-point gain for Llama-3-8B-Instruct and Gemma-7B, compared with a measured 1.6-point gain.Source: §6.3 · p. 12

6.4 Forecasting success far beyond the pilot

  • At 8,192 samples, power-law forecast error is 7.6 points versus SPLIT’s 1.9 with a simulated verifier; power law remains better for pure coverage and SWE-Bench argmax.The 175-system SWE-Bench pool tests coverage only, not selection.Source: §6.4 · pp. 13–14

7 Limitations and conclusion

SPLIT uses a small labelled pilot and an exact success model to allocate test-time compute, reaching near-optimal decisions across the reported settings. The conclusion also identifies limits in forecasting, long-horizon agent evidence, pilot representativeness, cost modelling, verifier-model choice, theory assumptions, and online evaluation.

7 Limitations and conclusion

  • Forecasting gains over power laws are small with real tests, absent for pure coverage, and negative for argmax selection.The authors frame their claims around decisions and mechanisms, not forecasting accuracy.Source: §7 · p. 15
  • Same-agent selection at long horizons remains untested: public releases support only 16 held-out rollouts per issue, and 64 would require about 32,000 runs.The 175-system pool tests long-horizon coverage, not one agent’s repeated sampling or selection.Source: §7 · pp. 15–16
  • Estimators assume pilot-deployment exchangeability; under capability drift, every method fails for small pilots, and some refinements require repeated labelled judge verdicts.Source: §7 · p. 15
  • Cost comparisons use a one-parameter price family and additive latency, ignoring parallel sampling; judge calls count as one generation.Source: §7 · p. 15
  • Verifier models trade off across datasets, and the selection rule is significantly behind the better model on two of three datasets.Theory assumes conditional independence of candidates given a task; within-task dependence may bias SPLIT, especially at large N. Online replanning is greedy, ignores false-acceptance stopping risk, and is simulated only on CodeContests.Source: §7 · p. 15
  • Within a fraction of a point of hindsight’s best allocation, SPLIT supports compute, price, and latency budgets, while fixed rules can lose 2.5–20 points.Its regret depends on differential rather than absolute forecast error; online replanning recovers the gap to the best static configuration in hindsight.Source: §7 · p. 16

Broader Impact Statement

  • Automated verification can optimize a flawed benchmark target, and stronger generators can pass fixed checks more often with wrong outputs.The authors recommend remeasuring verifier error rates when generators change; all data are public releases, with no human data collected.Source: Broader Impact Statement · p. 16

A Proofs

The appendix proves the exact success formula by representing uniform selection among accepted candidates through random arrival order. It also gives a one-generator closed form and reports numerical agreement with Monte Carlo for the mixed-generator integral.

A.1 Proposition 1 (exact success formula)

  • Uniform choice among accepted candidates is represented by selecting the earliest-arriving accepted candidate, with arrival times independent of correctness and acceptance.Source: §A.1 · p. 19
  • Conditioning on candidate i’s arrival time, the proof requires it to be accepted and correct while all earlier candidates are rejected, then integrates and sums these probabilities.Source: §A.1 · p. 19
  • For one generator, success is non-decreasing in N and approaches a/s when s > 0; if s = 0, success is zero.Source: §A.1 · p. 19
  • The mixed-generator integral uses 480-node log-spaced trapezoidal quadrature and agrees with Monte Carlo within 3 × 10^-3.Source: §A.1 · p. 19

A.2 Convergence regimes

The convergence regimes bound how quickly success approaches its limiting value under different task-difficulty and verifier conditions. They include exponential bounds when acceptance rates stay positive and power-law behavior when task success rates have substantial mass near zero.

A.2 Convergence regimes

  • When correct answers are accepted at rate at least τ and false-accept rates are bounded below by f0 > 0, the gap to the limit is at most S∞e^-N min(τ,f0).Source: §A.2 · p. 19
  • If task success probabilities have density asymptotic to c p^(α−1) near zero, expected uncovered probability decays as c Γ(α)N^-α.Source: §A.2 · p. 19
  • If the false-positive-rate distribution satisfies P(ft ≤ x) ≤ Kx^af near zero, the success gap has an upper bound combining (1−τ)^N, KΓ(af + 1)N^-af, and e^-Nx0.The authors note this is an upper bound only, and the true gap can decay faster.Source: §A.2 · p. 19
  • For any false-positive rates, the gap from the zero-FPR success benchmark is at most N E[ft(1−p)], hence at most N E[ft].The comparison couples selectors so they differ only when a wrong candidate is accepted.Source: §A.2 · p. 19

A.3 Shared blind spots

The diversity analysis characterizes when splitting a sample budget across generators improves success and how shared task-level correlation affects that gain. Its results assume a perfect verifier; for imperfect verifiers, the planner evaluates the mixing weights numerically.

A.3 Shared blind spots

  • F is concave in the budget share, and an interior mix strictly beats both single-generator endpoints exactly when the endpoint derivatives point inward.The stated conditions are F′+(0) > 0 and F′−(1) < 0.Source: §A.3 · p. 20
  • A mix improves on generator A for some positive budget share exactly when A-weighted log failure is lower for B than for A.The weighting is wA = (1 − pA)^N.Source: §A.3 · p. 20
  • With identical generator marginals, the equal split’s gain over using A alone is non-increasing as Gaussian-copula correlation rises, and tends to zero as correlation approaches one.With unequal marginals, the gain is only shown to be non-increasing; the analysis makes no analytic claim for imperfect verifiers.Source: §A.3 · p. 20

A.4 Proposition 2 (re-verification)

The appendix gives conditions for re-verification to raise or lower the large-sample precision ceiling, derives a success ceiling for top-score selection, and bounds planner regret by forecast error. It also details how the pilot data fit the allocator’s task, generator, and verifier models.

A.4 Proposition 2 (re-verification)

  • At p = 0.4, increasing majority calls lowers the precision ceiling from 0.561 to 0.500 in one example, but raises it from 0.460 to 0.526 in a counterexample.In the latter case, correct-answer acceptance grows proportionally more than wrong-answer acceptance, despite F∞ > F1.Source: §A.4 · p. 20

A.5 Proposition 3 (argmax selection)

  • For top-score selection, success approaches the correctness probability among candidates at the top of the score range, provided that this limit exists.In the binned case, the ceiling is the correct share in the highest bin that can be occupied.Source: §A.5 · p. 20

A.6 Proposition 4 (planner regret)

  • Planner regret is bounded by twice the largest absolute configuration-level forecast error; the regret bound also combines calibration-task error spread with a finite-sample task-gap term.The proof uses the forecast error’s oscillation and a Hoeffding bound across configurations.Source: §A.6 · p. 21

B Estimation details

  • Pilot estimation fits task difficulty with beta-binomial marginals, generator dependence with a Gaussian copula, and verifier rates with pooled or task-varying models.For the two verifier models, an automatic choice uses the first half of pilot samples to predict success at full pilot size, then selects the closer prediction to model-free success.Source: B Estimation details · p. 21

C Additional results

Additional results compare verifier-model choice, top-score selection, and allocation or extrapolation behavior across simulated and real-verifier settings. Paired headline comparisons use shared units for the reported error and regret tests.

C Additional results

  • Automatic verifier-model choice is significantly better than the worse fixed model on every dataset, ties the better model on HumanEval, and trails it on CodeContests and SWE-bench by 0.28 and 0.71 points.The HumanEval tie has p = 0.52; the two deficits have p < 0.01.Source: Table 7 · p. 21
  • The theory figure contrasts sampling, diversification, and verification as budget levers, and reports that optimal verifier calls stay at one when repeated calls are highly correlated.Other figures show simulated-verifier allocation and pilot extrapolation, while the shared-blind-spots figure compares copula-based mixing with an independence assumption.Source: Figure 9 · p. 22, Figure 10 · p. 23, Figure 11 · p. 23
  • On HumanEval, base-test FPR pooled over tasks has Spearman correlation 0.98 with pass@1, or 0.97 using per-task FPRs.The figure also plots coverage, verified success, held-out predictions, pilot-size error, and error by generator.Source: Figure 13 · p. 25
  • At every tested N, argmax selection exceeds the best fixed accept/reject threshold, by 1.8 points at N = 1 and 4.4 points at N = 16.The fixed thresholds tested are 0.3, 0.5, and 0.7; runs with no accepted rollout count as failures.Source: Figure 14 · p. 25

D Significance tests

  • The paired tests report mean differences as ours minus comparator, with bootstrap 95% intervals and Wilcoxon signed-rank p-values, using shared units for MAE and regret.Planner-regret diagnostics decompose error into pairwise error, model spread, task gap, and a Hoeffding term.Source: Table 10 · p. 23, Table 11 · p. 26

E Data, compute and reproducibility

The paper documents public data sources, local compute requirements, and the planned code release. It also describes an additional same-agent rollout pipeline for experiments not supported by public data alone.

E Data, compute and reproducibility

  • Experiments draw samples and verdicts from public releases spanning math, code, LLM-judge and reward-model evaluations, and SWE-Bench rollouts; outputs are not redistributed.The code release includes derived per-sample correctness labels and verifier verdicts, allowing the main experiments to run without multi-gigabyte downloads.Source: E Data, compute and reproducibility · p. 26
  • All experiments ran on a single 8-core laptop CPU without a GPU or model API; CodeContests execution took about 1.5 hours and the rest roughly 5–8 hours.Source: E Data, compute and reproducibility · p. 26
  • The planned public code release includes estimators, planner and online policies, scripts to regenerate figures and numbers, 35 unit tests, and 26 proposition checks.Random seeds are fixed, and compute-matched and price token counts are measured from released samples.Source: E Data, compute and reproducibility · p. 26
  • For unsupported public-data experiments, the release includes a pipeline for same-agent SWE-Bench Verified rollouts scored by the official harness and an execution-free LLM verifier.At R = 64, this requires 32,000 agent runs; the pipeline supports pilots of 4–16 rollouts and horizons up to R − 16.Source: E Data, compute and reproducibility · p. 27

Related papers

Loading 2610.23255v1…