PaperlayerView exact revision on arXiv

Source-linked AI summary

Speculative Evaluation of Stochastic LLMs

Qianli Shen, Xiang Li, Ruomeng Ding, Yanxi Chen, Daoyuan Chen, Yaliang Li

arXiv:2609.28560v1stat.MLcs.AIcs.LG

TL;DR

Stochastic LLM benchmark scores require costly repeated rollouts, and uniform allocation can overlook sharp differences in task-level variance. The paper develops hierarchical Bayesian Neyman allocation and an asynchronous variant that dispatches continuations from partial pilot feedback. Across tested profiles, the approach reduces variance relative to Uniform, while HBN-async mitigates synchronization overhead in real-generation experiments.

  • Problem

    The paper asks how to minimize the variance of a fixed-benchmark mean under an exact rollout budget when task-level rollout variances are unknown and uniform repetition ignores their differences.

    Source: §1 · p. 1

  • Method

    Speculative Evaluation uses a hierarchical Bayesian Neyman policy with ex-ante pilot and stage-weight design, then speculatively executes continuations from partial pilot feedback in HBN-async.

    Source: §1 · p. 2

  • Results

    Across 107 benchmark–checkpoint profiles and budgets of 8–64 rollouts per task, HBN reduces variance by 12.8%–33.6% on average relative to Uniform.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Real-generation experiments show that HBN-async mitigates pilot-barrier overhead, helping translate statistical efficiency into practical evaluation benefits.

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

    The analysis assumes conditionally independent Bernoulli outcomes, and efficiency depends on profile structure and prior specification, so gains are not guaranteed for every profile.

    Source: §5 · p. 9

Abstract

from arXiv · show

Evaluating a stochastic large language model is costly: benchmark scores estimate expected performance from randomized rollouts, yet uniform repetition ignores sharp differences in task-level rollout variance. We ask how to minimize the variance of a fixed-benchmark mean under an exact rollout budget. We develop Speculative Evaluation with a Hierarchical Bayesian Neyman (HBN) policy with pilot size and stage weight jointly chosen ex ante. It runs a short uniform pilot, pools per-task success counts with a hierarchical Bayesian model, and uses posterior expectations of task-level sampling variances for exact positive-integer Neyman allocation. To mitigate the pilot synchronization barrier, HBN-async speculatively executes continuations from partial pilot feedback and retains those selected by the final allocation. Across six checkpoints and 18 benchmark groups, we evaluate 107 nondegenerate benchmark-checkpoint profiles. For rollout budgets of 8-64 per task, Speculative Evaluation reduces variance relative to Uniform by 12.8%-33.6% on average across profiles, outperforming hindsight-tuned empirical and independent Bayesian baselines. Real-generation experiments that account for the pilot synchronization barrier show that HBN-async mitigates its overhead, helping translate statistical efficiency into practical evaluation benefits.

1 INTRODUCTION

Stochastic benchmark scores estimate expected performance from costly randomized rollouts, while uniform repetition can spend a fixed budget inefficiently when task variances differ. Speculative Evaluation combines hierarchical Bayesian allocation with asynchronous pre-allocation to reduce variance and mitigate the pilot barrier.

1 INTRODUCTION

  • Automated research repeatedly evaluates workflow or agent changes, making evaluation cost and precise feedback recurring concerns.Small candidate improvements can be difficult to distinguish from rollout noise, while increasing repetition raises each iteration’s cost.Source: §1 · p. 1
  • Uniform evaluation gives every task the same sample count despite potentially sharp differences in task-level rollout variance.Learning the variances needed for adaptive allocation consumes the same fixed budget the policy seeks to save.Source: §1 · pp. 1–2
  • HBN uses a uniform pilot, pools noisy task counts hierarchically, and allocates remaining rollouts using posterior expected variances.Pilot size and stage weight are jointly chosen ex ante, and fresh continuation samples allow unbiased reuse of the pilot.Source: §1 · p. 2
  • HBN-async uses partial pilot feedback to dispatch speculative continuations early, retaining those selected by the final allocation.This can reduce idle time at the synchronization barrier, although unselected speculation wastes computation.Source: §1 · p. 2
  • Across 107 benchmark–checkpoint profiles and budgets of 8–64 rollouts per task, HBN reduces variance by 12.8%–33.6% on average relative to Uniform.The reported comparison also exceeds tuned empirical and independent Bayesian baselines on this metric.Source: §1 · p. 2

2 BACKGROUND

The paper formulates a benchmark score as the mean of task pass probabilities under conditionally independent Bernoulli rollouts. Uniform sampling is simple, but task heterogeneity creates an opportunity for variance reduction if unknown task variances can be learned within the rollout budget.

2 BACKGROUND

  • For a fixed checkpoint and benchmark of N tasks, each rollout is a conditionally independent Bernoulli outcome with task-specific pass probability, and the target is the benchmark mean.The vector of task probabilities is called the task-probability profile.Source: §2 · p. 2
  • Uniform allocation assigns b rollouts to each task, while oracle Neyman allocation uses known task variances to reduce benchmark-mean variance.The oracle solution relaxes integrality and the per-task lower bound for analysis.Source: §2 · p. 2
  • Task heterogeneity creates a variance-reduction opportunity, but the task variances are unknown and must be learned from pilot observations.The pilot and adaptive allocation draw on the same budget.Source: §2 · p. 3
  • The two-stage design spends an integer pilot budget on every task, then chooses a positive-integer continuation allocation from the pilot.Fresh continuation rollouts are conditionally independent of the pilot, and a precommitted stage weight combines the pilot and continuation estimators without bias.Source: §2 · p. 3
  • The two-stage design introduces a synchronization point before the final continuation allocation.More stages can permit finer adaptation but add coordination overhead.Source: §2 · p. 3

3 SPECULATIVE EVALUATION WITH ASYNCHRONOUS HIERARCHICAL BAYESIAN NEYMAN ALLOCATION

HBN estimates task-level sampling variances from a hierarchical posterior and uses them to allocate continuation rollouts, with pilot size and stage weight selected ex ante. HBN-async applies partial-pilot allocation signals to start continuations before the pilot is complete, then recovers the same final allocation rule.

3 SPECULATIVE EVALUATION WITH ASYNCHRONOUS HIERARCHICAL BAYESIAN NEYMAN ALLOCATION

  • HBN chooses pilot size and stage weight by minimizing prior-averaged risk, because the task-probability profile is unknown.A hierarchical Bayesian model supplies the policy’s allocation scores.Source: §3 · p. 3

3.1 STATISTICAL SPECULATION: HIERARCHICAL BAYESIAN NEYMAN ALLOCATION

  • The hierarchical model represents a benchmark’s latent mean success probability and between-task dispersion, inducing expected task-level sampling variances.The reported analyses use an untuned reference specification, and prior choice can affect allocation efficiency but not unbiasedness.Source: §3.1 · p. 3
  • HBN uses pilot counts to form posterior expected sampling-variance scores, then assigns remaining rollouts by exact integer Neyman allocation.The allocation starts each task at one fresh rollout and greedily assigns each remaining rollout to the task with the largest marginal variance reduction.Source: §3.1 · p. 4
  • HBN selects pilot size and stage weight ex ante, and the pilot and continuation estimators are uncorrelated for fixed task probabilities.The expectation used in design selection covers hyperparameters, task probabilities, and pilot outcomes.Source: §3.1 · p. 4

3.2 SYSTEMS SPECULATION: ASYNCHRONOUS PRE-ALLOCATION

  • HBN-async uses partial pilot feedback to pre-allocate and execute continuations early, mitigating the synchronization barrier without changing the statistical design or final allocation rule.As pilot rewards arrive, partial counts update provisional allocation signals; after all designated pilot rewards are available, the method recovers the official allocation.Source: §3.2 · pp. 4–5
  • The asynchronous request queue prioritizes pilot requests, gates continuations by provisional allocations, and recovers results using fixed request IDs.The paper states that fixed-ID recovery prevents faster same-task requests from replacing designated IDs and introducing latency-dependent selection bias.Source: §3.2 · p. 5

4 EXPERIMENTS

The experiments evaluate HBN’s variance reduction across benchmark–checkpoint profiles and test whether asynchronous speculation can mitigate execution overhead from waiting for pilot feedback.

4.1 BENCHMARKS AND ROLLOUT DATA

  • The evaluation covers 107 nondegenerate profiles from six checkpoints and 18 benchmark groups, using budgets of 8, 16, 32, and 64 rollouts per task.The profiles are based on 1,024 sampled responses per problem–checkpoint combination; variance estimates average 8,192 pilot draws.Source: §4.1 · p. 5, §4.2 · p. 6

4.2 VARIANCE REDUCTION AND ROBUSTNESS

  • HBN reduces variance on nearly all profiles, but one adverse profile has variance at most 2.4% above Uniform.The experiment retains 107 nondegenerate profiles after excluding a profile with zero variance.Source: §4.1 · p. 5, §4.2 · p. 6
  • 87.2% at b = 8 to 66.4% at b = 64: HBN’s mean Uniform-normalized variance fell across 107 profiles.Uniform is 100% and lower is better.Source: Table 1 · p. 6, §4.2 · p. 6
  • HBN has lower mean variance than hindsight-tuned EN and IBN at every budget, and lower mean Uniform-normalized MSE than hindsight-tuned TS-Neyman at all four budgets.HBN chooses its pilot size and stage weight ex ante, while the cited baselines receive hindsight tuning.Source: §4.2 · pp. 6–7

4.3 COMPUTATION, SYSTEM OVERHEAD, AND PRACTICAL BENEFIT

  • Across budgets, HBN-async’s useful computation rises 2.00%–5.62% over Uniform, while wasted speculative computation falls from 2.23% to 0.026% of Uniform computation.The computation accounting separates accepted-rollout FLOPs from wasted FLOPs for discarded or aborted speculative requests.Source: §4.3 · pp. 7–8, Table 2 · p. 8
  • Across every budget, HBN-async reduces actual and useful-FLOP-normalized overhead relative to HBN-sync, despite speculative waste; the reduction persists after useful-computation adjustment, with the gap largest at b = 8 and narrowing as budget increases.HBN-sync and HBN-async receive identical pilot rewards and select the same final continuation IDs.Source: §4.3 · pp. 7–8, Table 3 · p. 8
  • At b ≥16, rounded-equivalent Uniform takes 13.64%–42.81% more total time than original-budget Uniform, versus 2.85%–6.56% for HBN-async; at b = 8 HBN-async is slower.The comparison rounds the variance-equivalent Uniform budget down; under this setup, the paper reports a clear benefit at b ≥16.Source: §4.3 · p. 9

5 CONCLUSION AND LIMITATIONS

Speculative Evaluation combines hierarchical Bayesian allocation with asynchronous pre-allocation; across 107 benchmark–checkpoint profiles, the combination yields aggregate benefits at budgets b ≥16 under the tested setup. The paper notes statistical and systems scope limits, while its algorithms describe pilot-based allocation and speculative continuation recovery.

5 CONCLUSION AND LIMITATIONS

  • Across 107 benchmark–checkpoint profiles, Speculative Evaluation yields clear aggregate benefits at b ≥16 under the tested setup.The conclusion attributes variance reduction to hierarchical information sharing and ex-ante pilot-and-weight design, while HBN-async mitigates the pilot barrier despite speculative waste.Source: §5 · p. 9
  • The statistical scope assumes conditionally independent Bernoulli outcomes, and profile structure or prior misspecification can affect efficiency, with gains not guaranteed for every profile.The paper also notes that systems results use coupled synthetic rewards, exclude benchmark scoring, and depend practically on generation and scoring costs and concurrency.Source: §5 · p. 9
  • Future work could extend the framework to nonbinary or correlated outcomes and cost-aware allocation with heterogeneous generation costs and real scoring feedback.Source: §5 · p. 9

A COMPLETE ALGORITHM

  • HBN-async uses partial pilot feedback to pre-allocate and execute continuations, then retains only requests selected by the final allocation.The algorithm discards completed surplus, cancels queued surplus, aborts running surplus, and submits missing required requests; the combined estimate uses pilot and continuation results.Source: A COMPLETE ALGORITHM · p. 12

B EXPERIMENTAL AND IMPLEMENTATION DETAILS

The implementation specifies response-generation settings, hardware configuration, benchmark-specific scoring, and the estimated generation workload. The reported corpus-generation estimate excludes scoring and is not an exact GPU-hour count.

B.1 ROLLOUT GENERATION AND SCORING

  • Responses use vLLM 0.23.0 with temperature 0.6, top-p 0.95, a 16,384-token cap, and bfloat16 inference.Qwen2.5 uses non-thinking mode; Qwen3.5 uses thinking mode with at most 8,192 thinking tokens within the total cap, and requests use deterministic per-request seeds.Source: §B.1 · p. 13
  • Generation workers use eight NVIDIA H20 GPUs with 96 GB per GPU, each hosting a persistent tensor-parallel-size-one replica.A routing process distributes requests among the eight replicas; the GPU-memory-utilization limit is 0.9.Source: §B.1 · p. 13
  • Scoring is benchmark-specific: mathematical tasks use normalized numeric or symbolic matching, while multiple-choice tasks use option extraction.HLE uses a fixed Qwen3.6-35B-A3B judge prompt; LiveCodeBench runs tests on separate CPU workers in network-isolated, resource-limited environments.Source: §B.1 · p. 13
  • Approximately 411 active model-job hours generated the 108-pair corpus, equivalent to 17.1 days if run sequentially on one independent eight-H20 worker.The estimate excludes scoring and is not an exact GPU-hour count because some jobs used multiple eight-GPU workers concurrently.Source: §B.1 · p. 13

B.2 HBN DESIGN AND NUMERICAL IMPLEMENTATION

HBN selects pilot size and stage weight ex ante using estimated Bayes risks under a hierarchical reference prior. The appendix also details how empirical and independent Bayesian baselines are tuned and replayed.

B.2 HBN DESIGN AND NUMERICAL IMPLEMENTATION

  • HBN evaluates every feasible pilot size, computes the optimal stage weight in closed form, and selects the design with the lowest Bayes risk under its hierarchical reference prior.The design uses eight independent 8192-draw replicates and common random numbers across candidate pilots; selected solutions are interior to the searched range.Source: §B.2 · p. 13, Table 5 · p. 13

B.3 BASELINE SCORES AND TUNING

  • EN uses evaluation profiles to select pilot size and weight for each task count and budget, then assigns continuation rollouts from nonnegative scores using a decreasing-marginal-gain allocator.If all EN scores are zero, continuation allocation is uniform.Source: §B.3 · p. 14
  • IBN designs pilot size and weight under candidate matched priors, then uses evaluation profiles to select the prior strength separately at each budget.The positive prior-strength grid is A = {0.01, 0.02, . . . , 0.20, 0.25, 0.50, 1.00}.Source: §B.3 · pp. 14–15

B.4 VARIANCE EVALUATION PROTOCOL

The variance-replay protocol uses distinct deterministic seed namespaces for design and replay, with equal profile weighting in the reported table.

B.4 VARIANCE EVALUATION PROTOCOL

  • Replay averages 8192 independent pilot vectors for each benchmark–checkpoint pair, budget, and candidate policy, with all 107 retained profiles equally weighted.Continuation contribution is evaluated analytically, and nested paths are shared across candidate designs to reduce Monte Carlo noise in comparisons.Source: §B.4 · p. 15

B.5 SYSTEM EXECUTION AND COST ACCOUNTING

The system study compares HBN execution schemes under a shared frozen reward protocol, measuring selected-request completion time and rollout and compute costs. It also estimates model computation with a sequence-length-aware FLOP proxy and compares HBN-async with rounded-equivalent Uniform runs.

B.5 SYSTEM EXECUTION AND COST ACCOUNTING

  • Pilot rewards and continuation IDs are shared across execution strategies, while real-generation timing excludes benchmark-scoring latency.Rewards are revealed only after generation completes.Source: §B.5 · p. 15
  • The timer includes dispatch, pilot-dependent inference, allocation, and queue management, ending when selected requests finish and rewards are available.Model loading, warmup, ex-ante design, static quadrature setup, and between-policy reset are excluded; serving uses eight replicas with a 256-request window.Source: §B.5 · p. 15
  • HBN-async is compared with fresh Uniform executions at rounded-equivalent budgets, using the same workload and timing definition.The comparison covers 428 profile–budget settings; Uniform accepts exactly its assigned rollout count.Source: §B.5 · p. 16
  • Actual rollout counts include accepted, completed-discarded, and running-aborted requests, while unobserved aborted computation makes waste estimates lower bounds.Aborted requests contribute observed prompt and generated tokens; queued cancellations with no observed model compute contribute zero.Source: §B.5 · p. 16
  • The sequence-length-aware FLOP proxy estimates text-core, output-projection, and attention work, but approximates computation rather than hardware execution cost.It omits explicit GDN recurrent-state updates, estimated to be marginal across the evaluated Qwen3.5 models and budgets.Source: §B.5 · p. 16, Table 7 · p. 16
  • Useful and wasted FLOPs are summed separately, while time ratios are averaged equally across profiles using each workload’s reference time.The wasted-FLOP denominator is Uniform’s useful FLOPs, so useful-compute increase and wasted-compute contribution add to actual-compute increase.Source: §B.5 · p. 16

C.1 VARIANCE GAINS ACROSS PROFILES AND FAILURE BOUNDARY

HBN improves on Uniform across nearly all profiles at each tested budget, with Figure 1 showing the distribution of Uniform-normalized variance. The adverse results are confined to one endpoint-concentrated profile, where a short pilot can misallocate samples.

C.1 VARIANCE GAINS ACROSS PROFILES AND FAILURE BOUNDARY

  • HBN improves on Uniform for 107/107, 106/107, 106/107, and 107/107 profiles at b = 8, 16, 32, and 64, respectively, under the estimate-plus-1.96-standard-errors criterion.Figure 1 shows individual profiles, interquartile ranges and medians, means, and the Uniform reference line.Source: §C.1 · p. 17, Figure 1 · p. 17
  • MATH-100 with Qwen3.5-4B is the only adverse profile, with mean variance ratios of 1.024 and 1.004 relative to Uniform at b = 16 and 32.With 96 of 100 tasks outside [0.2, 0.8], its short pilot may not rank task variances reliably, and resulting misallocation can hurt despite an Oracle ratio of approximately 0.774; HBN is at most 2.4% worse than Uniform.Source: §C.1 · p. 17

C.2 PROFILE CASE STUDY: AIME24 WITH QWEN3.5-4B

The AIME24–Qwen3.5-4B case study examines a heterogeneous profile with many task probabilities near the endpoints. HBN’s variance ratio improves as the budget increases, while remaining above the full-information Oracle ratio.

C.2 PROFILE CASE STUDY: AIME24 WITH QWEN3.5-4B

  • For AIME24 with Qwen3.5-4B as a heterogeneous task-probability profile, among 30 tasks, 33.3% have empirical probabilities below 0.2, 36.7% above 0.8, and four are empirical endpoints.Source: §C.2 · p. 17
  • At b = 32, HBN’s variance ratio is 0.842, versus one for Uniform and 0.646 for Oracle.Across b = 8 to 64, HBN’s ratio falls from 0.937 to 0.801, while Oracle is nearly flat at 0.655–0.644; Figure 2(d) shows HBN narrower than Uniform, with all three estimators centered.Source: §C.2 · p. 17

C.3 A SEQUENTIAL POSTERIOR-SAMPLING BASELINE

Bernoulli TS-Neyman adapts posterior-sampled sequential allocation to binary outcomes, and HBN has lower mean Uniform-normalized MSE at all four tested budgets, even against a hindsight-tuned TS baseline. The related work distinguishes this fixed-mean, low-budget rollout objective from online allocation, other evaluation estimands, and inference or training objectives.

C.3 A SEQUENTIAL POSTERIOR-SAMPLING BASELINE

  • Bernoulli TS-Neyman assigns each new observation using a posterior-sampled marginal variance-reduction index, adapting TS-Neyman (Morikawa et al., 2026) to binary outcomes and target weights.It uses independent Beta(α, α) working priors and Beta–Bernoulli conjugacy to sample task variances.Source: §C.3 · pp. 17–18
  • Because observations affect subsequent sample counts, the final sequential estimator need not be unbiased at finite budgets, so the comparison evaluates MSE rather than variance alone.TS begins with m0 observations per task and then allocates one new observation at a time.Source: §C.3 · p. 18
  • HBN has lower mean Uniform-normalized MSE than hindsight-tuned Bernoulli TS-Neyman at all four budgets, with gaps of 0.79–1.97 percentage points.The table reports means across 107 profiles and selects one common (α, m0) per budget; the hindsight selection may be optimistic due to Monte Carlo selection noise.Source: §C.3 · pp. 18–19, Table 8 · p. 19
  • The equal-rollout TS comparison does not charge sequential feedback overhead, which can limit concurrent generation; batched or asynchronous TS would be a different policy.HBN concentrates allocation dependence at the pilot boundary, where speculation can overlap generation with feedback collection.Source: §C.3 · p. 19

D RELATED WORK

  • Classical two-stage Neyman designs use preliminary samples, while later online methods update allocations as feedback arrives; the paper targets b = 8–64 rollouts per task.Cai & Rafi (2024) show small fixed pilots can make plug-in allocation less efficient than balanced allocation; TS-Neyman (Morikawa et al., 2026) and EST-IVWE (Lee et al., 2026) analyze large-budget behavior.Source: D RELATED WORK · p. 19
  • LLM-as-a-judge allocation studies target vector-score errors, whereas this work estimates one fixed-benchmark mean from low-budget Bernoulli rollouts.Saha et al. (2026) consider worst-coordinate error; Lee et al. (2026) extend to multiple judges and general ℓp error.Source: D RELATED WORK · p. 19
  • Active testing, proxy-assisted allocation, and benchmark-compression methods change queried items or measurement sources; this work retains every task and varies target-model replications.The passage contrasts active labeling, historical or semantic proxies, correlated autoraters, and reduced or coarse-to-fine benchmark suites.Source: D RELATED WORK · pp. 19–20
  • Adaptive inference and training methods allocate rollouts for answer quality or learning progress, while this work targets precision of an unbiased fixed-benchmark mean.Strategic Scaling (Zuo & Zhu, 2026) and VIGOR (Jiang et al., 2026) are examples of those neighboring objectives.Source: D RELATED WORK · p. 20
Loading 2609.28560v1…