PaperlayerView exact revision on arXiv

Source-linked AI summary

CERO: Where and When to Allocate Rollouts for RL Post-Training

Yiming Zong, Yige Wang, Xing Hu, Jiashuo Jiang, Zuo-Jun Max Shen

arXiv:2610.09679v1cs.LGcs.AI

TL;DR

The paper asks how to allocate a finite rollout budget across the training horizon. It introduces CERO, a scheduler for coordinating prompt admission, repeated selection, and budget pacing; under matched training-response budgets, it achieves the highest avg@16 macro-average on all three backbones.

  • Problem

    The paper asks when to spend more or less of a finite rollout budget across training.

    Source: §1 · p. 2

  • Method

    CERO is a finite-horizon scheduler that coordinates prompt admission, repeated selection, and budget pacing under a shared rollout budget.

    Source: §7 · p. 13

  • Results

    CERO achieves the highest avg@16 macro-average on all three backbones under matched training-response budgets.

    Source: §7 · p. 13

  • Takeaways & Limitations

    Mechanistic analyses link CERO’s prompt choices to stronger within-group supervision, and multi-seed ablations show gains from adaptive pacing over fixed and preset schedules.

    Source: §7 · p. 13

    The formulation assumes a nondecreasing concave utility of cumulative exposure and a latent value-capture rate q_i in [0, 1/4] for each prompt.

    Source: §2.1 · p. 4, §2.2 · p. 4

Abstract

from arXiv · show

Adaptive rollout methods for group-relative reinforcement learning typically allocate a fixed per-update budget across prompts. We instead study how to coordinate a finite rollout budget over the entire training horizon. We formulate this problem using a concave surrogate utility of cumulative prompt exposure and introduce CERO, an online primal dual scheduler for prompt admission and budget pacing. In our experiments, each admitted prompt receives a fixed-size response group. CERO instead adapts which prompts are selected, how often they are revisited across rounds, and how many groups are generated in each round. A compact Fenchel representation linearizes the dependence on cumulative exposure, while projected online gradient descent updates prompt-specific supporting slopes and a shared budget price using reward-variation feedback and budget deviations. We establish pathwise guarantees for the surrogate allocation objective against fixed-rate and same-path time-varying benchmarks, with explicit terms for proxy discrepancy and rate variation. Under matched training-response budgets, CERO attains the highest avg@16 macro-average on each of three backbones across five mathematical reasoning benchmarks. Mechanistic analyses link CERO's prompt choices to within-group reward contrast, while multi-seed ablations show gains from adaptive pacing over both uniform and preset spending schedules.

1. Introduction

The section frames rollout allocation as a horizon-level problem: a finite budget must be paced across rounds while prompts are admitted and revisited. CERO uses a Fenchel-based primal–dual scheduler, with the highest avg@16 macro-average on all three evaluated backbones under matched training-response budgets.

1. Introduction

  • Even with fixed-size response groups, the scheduler must choose which prompts to admit, how often to revisit them, and how much budget to spend at each stage.Source: §1 · p. 2
  • Fenchel dualization linearizes cumulative-exposure dependence, while projected OGD adapts prompt-specific supporting slopes and a shared budget price.Source: §1 · p. 2
  • Prompt-specific slopes guide prioritization, the shared price regulates pacing, and a prompt-level Beta state predicts future within-group reward variation.Source: §1 · p. 2
  • CERO achieves the highest avg@16 macro-average on all three evaluated backbones under matched training-response budgets.The comparison evaluates three backbones on five mathematical reasoning benchmarks.Source: §1 · pp. 2–3
  • Matched controls and multi-seed ablations link gains to prompt-aware assignment and horizon-level coordination, with CERO outperforming fixed-pacing, preset-pacing, and direct marginal-utility variants.Source: §1 · pp. 2–3
  • CERO's pathwise guarantees cover fixed-rate and same-path time-varying benchmarks, separating optimization error, reward-proxy discrepancy, and temporal rate variation.Source: §1 · p. 3

2. Finite-Horizon Rollout Optimization

The section formulates finite-horizon rollout allocation around cumulative prompt exposure and a concave utility. A compact Fenchel representation makes the horizon objective tractable through prompt-specific slopes and a shared budget price.

2.1. Problem Formulation

  • The formulation allocates fixed-quantum response units across prompts and K rounds to maximize total utility of cumulative exposure under a finite budget.Source: §2.1 · pp. 3–4

2.2. Value-capture utility

  • A nondecreasing concave utility models diminishing returns to cumulative prompt exposure, with prompt-specific value-capture rates.Source: §2.2 · p. 4

2.3. Compact Fenchel representation

  • A compact Fenchel representation expresses exposure utility exactly through affine functions, using prompt-specific supporting slopes and a shared budget price.Source: §2.3 · p. 5

3. Reward-Variation Proxy

CERO uses predicted within-group reward variation as a proxy for latent value-capture rates, updating a prompt-specific Beta state from observed successes and failures. The proxy reflects expected reward contrast and is calibrated under a fixed-sample stationary model, while allocation guarantees account for proxy error.

Reward-Variation Proxy

  • CERO uses predicted within-group reward variance as a proxy for latent value-capture rate, rather than directly estimating downstream policy improvement.The proxy is computed from a Beta state summarizing prompt reward history.Source: §3 · pp. 5–6
  • The Beta state updates from successful and failed responses, with a forgetting factor that discounts older evidence toward the prior when it is below 1.At ρ = 1, the update reduces to standard cumulative Beta–Bernoulli updating; for ρ < 1, it can track policy changes.Source: §3 · pp. 5–6
  • The predictive expected within-group reward variance is largest near a predicted success rate of 1/2 and decreases when the Beta state is more uncertain.Under the stated Bernoulli group model, this variance equals the latent value-capture rate in expectation.Source: §3 · p. 6
  • For fixed-sample stationary calibration, with i.i.d. Bernoulli(p) observations and fixed sample size n, bqn is consistent at rate O(n^-1/2).The allocation guarantees hold pathwise for arbitrary realized proxy sequences.Source: §3 · p. 6

4. CERO Algorithm

CERO is an online primal–dual scheduler for finite-horizon rollout allocation. It uses reward-variation feedback to adapt prompt selection and revisits, while a shared budget price regulates pacing across rounds.

4. CERO Algorithm

  • CERO combines prompt-specific supporting slopes with a normalized shared budget price to schedule prompt admission and rollout spending.The algorithm ranks positive-margin prompts, assigning up to the per-prompt cap while round capacity remains.Source: §4 · p. 7
  • CERO adapts which prompts receive groups, how often prompts are revisited across rounds, and how many groups are generated per round.In the reported setup, each selected prompt receives one eight-response group.Source: §4 · p. 7
  • After each round, CERO updates its Beta state from observed rewards and recomputes the reward-variation proxy for the next round.If a prompt receives no allocation, its success and failure counts are set to zero.Source: §4 · p. 7
  • Prompt-specific dual variables adjust relative prompt priority, while the shared price regulates budget pacing across rounds.The shared price rises when virtual allocation exceeds the average per-round budget and falls when it is below that level.Source: §4 · p. 8

5. Performance Guarantees

CERO’s allocation guarantees are pathwise and compare its surrogate objective with fixed-rate and same-path time-varying benchmarks. The time-varying guarantee separates temporal rate drift from reward-proxy discrepancy.

5. Performance Guarantees

  • The paper analyzes CERO with respect to the surrogate allocation objective, while downstream policy performance is evaluated empirically; a per-prompt quantity vanishes at rate O(K^-1/2).Source: §5 · pp. 8–9
  • The fixed-rate pathwise guarantee separates online optimization error from reward-proxy discrepancy.It applies to any fixed target-rate vector and any realized proxy sequence under the stated algorithmic setup.Source: §5 · p. 9
  • The same-path drifting-rate guarantee compares feasible allocation plans against the same realized rate path, isolating allocation quality along that path.Its additional V_K term isolates temporal drift from reward-proxy discrepancy.Source: §5 · p. 9

6. Experiments

Experiments compare CERO with fixed and adaptive rollout baselines across three backbones and five mathematical reasoning benchmarks. CERO leads the reported macro-average comparisons, while mechanism analyses examine prompt selection, effective groups, and budget pacing.

6.1. Main Results

  • With allocation sizes and timing preserved, Random-matched CERO trails CERO by 3.63, 1.50, and 1.63 macro-average points across the three backbones.The control randomizes prompt assignment, supporting a contribution from prompt-aware assignment under the same rollout schedule.Source: §6.1 · p. 10

6.2. Ablation and Mechanism Analysis

  • On DSR1-Q1.5B, the reward-variation proxy tracks observed contrast, with Pearson r = 0.769 over training and Pearson r = 0.971, Spearman ρ = 0.964 across seven bins.The bin-level analysis reports closely preserved relative ordering between predicted and observed variation.Source: §6.2 · pp. 10–11, Figure 2 · p. 11

6.1. Main Results

  • CERO attains avg@16 macro-averages of 32.81, 45.36, and 41.81, improving over GRPO by 2.62, 2.10, and 1.59 points, respectively, and exceeding KnapsackRL on all three backbones.The clearest improvement over KnapsackRL is on DSR1-Q1.5B, with smaller margins on the larger models.Source: §6.1 · p. 10, Table 1 · p. 11

6.2. Ablation and Mechanism Analysis

  • Over the full run, with the full prompt pool available in every round, CERO preferentially selects prompts with intermediate predicted success rates: the [0.4,0.6) bin has a 1.72× lift, while both extreme bins have approximately 0.65×.All three interior bins are over-selected in the final stage.Source: §6.2 · pp. 11–12
  • At the matched 256,000-response budget, CERO yields an effective-group rate of 57.3%, versus 52.7% for Random-matched CERO and 48.7% for KnapsackRL.CERO produces 18,347 effective groups out of 32,000 executed groups; the 4.6-point gap over Random-matched CERO is described as controlled evidence for prompt-aware admission.Source: Figure 4 · p. 12, §6.2 · p. 12
  • CERO’s cumulative surplus peaks at 1,920 responses and returns to zero at training’s end, exhausting the 256,000-response budget exactly.Spending deviations persist across data-epoch boundaries rather than following a uniform schedule.Source: Figure 5 · p. 12, §6.2 · pp. 12–13
  • Across three seeds, CERO exceeds CERO-fixed, CERO-preset, and CERO-greedy by 1.13, 1.55, and 1.29 average points, respectively.The fixed and preset comparisons support adapting budget consumption over the training horizon rather than using fixed or predetermined spending schedules.Source: Table 2 · p. 13, §6.2 · p. 13
  • With a fixed 512-response quota, dual-guided and marginal-utility prompt rankings score 31.13 and 30.97, while full CERO improves on both by more than one point.The authors interpret the ablations as supporting joint coordination of prompt prioritization and budget pacing.Source: §6.2 · p. 13

7. Conclusion

CERO coordinates prompt admission, repeated selection, and rollout-budget pacing over a finite horizon, with pathwise guarantees for its surrogate allocation objective. Under matched training-response budgets, it achieves the highest avg@16 macro-average on all three backbones; the related work covers difficulty- and utility-aware rollout allocation as well as broader online resource-allocation methods.

7. Conclusion

  • CERO coordinates prompt admission, repeated selection, and budget pacing through a Fenchel-based primal–dual formulation.The formulation yields tractable round-level decisions and pathwise guarantees for the surrogate objective under fixed-rate and same-path time-varying benchmarks.Source: §7 · p. 13
  • CERO achieves the highest avg@16 macro-average on all three backbones under matched training-response budgets.The conclusion also reports gains from adaptive pacing over fixed and preset schedules.Source: §7 · p. 13
  • Mechanistic analyses link CERO's prompt choices to stronger within-group supervision.Multi-seed ablations show gains from adaptive pacing over fixed and preset schedules.Source: §7 · p. 13

Appendix A: Related Work

  • Adaptive rollout-allocation work includes difficulty- or uncertainty-based budgets, training-value estimates, and decisions based on intermediate rollout outcomes.Some related approaches filter or prune trajectories after generation.Source: Appendix A · p. 17
  • Online resource-allocation methods differ in how they use dual information, including learn-once pricing, repeated adaptive updates, primal-oriented algorithms, and first-order schemes.The passage places these methods in settings including ad assignment, revenue management, and online packing or covering.Source: Appendix A · p. 17

B.1. Pass@16 Evaluation

This section reports CERO’s pass@16 evaluation, reward-variation proxy diagnostics, prompt-exposure patterns, and computational costs, alongside an exact Fenchel-related utility representation. It also derives the compact conjugate’s minimizer and establishes a compact biconjugate and stability result.

B.1. Pass@16 Evaluation

  • CERO improves pass@16 macro-average over GRPO on all three backbones by 1.71, 0.39, and 1.58 points; it leads on two, while KnapsackRL leads Qwen3-4B (67.09 versus 65.45).CERO reaches 50.99 on DeepSeek-R1-Distill-Qwen-1.5B and 62.34 on Qwen2.5-7B-Instruct.Source: §B.1 · p. 18

B.2. Reliability of the Reward-Variation Proxy

  • Across ten equal-budget training intervals, predicted and observed variance means co-vary (Pearson r = 0.769), tracking shared decreases and rebounds.The predictions are recorded before current-round responses, making this signal available to CERO’s allocation decisions.Source: §B.2 · p. 19
  • Across seven prediction bins, proxy predictions track observed variance (Pearson r = 0.971; Spearman ρ = 0.964) but overestimate its absolute level (0.154 predicted versus 0.119 observed).The plotted bin means lie below the equality diagonal.Source: §B.2 · p. 19, Figure 6 · p. 20

B.3. Cross-Round Prompt Exposure

  • CERO spreads terminal exposure across 0.84R (57.5%), 1.12R (27.8%), and 1.40R (14.7%); GRPO has 41.0% and 58.1% at the first two levels.With the same total rollout budget, the broader distribution reflects redistributed repeated selections rather than additional aggregate exposure.Source: §B.3 · pp. 19–20, Figure 7 · p. 21

B.4. Computational Cost

  • Random-matched CERO used 36.78 GPU-hours, KnapsackRL 35.85, and vanilla GRPO 36.89; compute costs for the four methods were within approximately 3% of their mean.Source: §B.4 · p. 21
  • On the 1.5B backbone, CERO’s token-normalized core training cost matches GRPO at 84.2 seconds per million generated response tokens.The reported normalized measurements differ by approximately 1.1% of their mean value.Source: §B.4 · pp. 21–22

C.1. Exact Conjugate, Fenchel Representation, and Stability

  • For q ∈ [0, 1/4], c = 4λq/R and U_c(z) = 1 − e^(-cz) on [0, Z].Source: §C.1 · p. 22
  • For c > 0, the compact-conjugate minimizer is Z when θ ≤ ce^-cZ, 0 when θ ≥ c, and c^-1 log(c/θ) otherwise.The intermediate case applies when ce^-cZ < θ < c.Source: §C.1 · p. 22
  • The compact biconjugate is exact on q ∈ [0,1/4] and z ∈ [0,Z], using a supporting slope θ_z = ∂_zU(q,z) with one-sided endpoint derivatives.Concavity gives U*(q, θ_z) = θ_z z − U(q,z); the reverse inequality follows from the conjugate definition.Source: §C.1 · p. 23
  • The stability argument bounds the conjugate after applying a common uniform perturbation before taking the infimum over z ∈ [0,Z].The first bound is attributed to the mean-value theorem.Source: §C.1 · p. 23

C.2. Full-Information Oracle

The full-information oracle optimizes terminal prompt exposures under the rollout budget, then characterizes both continuous and integer solutions. It also establishes when exposure vectors can be realized across rounds and identifies a full-capacity boundary case.

C.2. Full-Information Oracle

  • The oracle reduces the full-information problem to terminal prompt exposures because the objective depends only on those exposures.Every feasible rollout plan induces a constrained exposure vector, and every such integer vector admits a feasible round-level realization.Source: §C.2 · p. 23
  • For the continuous relaxation, optimal exposure has a clipped water-filling form governed by a multiplier for the total budget.For positive-rate prompts, an interior optimum equates marginal utility with the budget multiplier.Source: §C.2 · p. 23
  • For integer exposures, repeatedly assigning a unit to an unsaturated prompt with the largest available marginal gain yields an optimal exposure vector.The marginal gains are nonnegative and nonincreasing, so the greedy procedure selects the largest available gains subject to each prompt's exposure cap.Source: §C.2 · p. 24
  • Any feasible integer exposure vector can be spread as evenly as possible across rounds while satisfying the global-budget and per-round capacity constraints.The passage concludes that the exposure-level optimum is attainable under the original constraints.Source: §C.2 · p. 24
  • At full capacity, allocating the maximum exposure to every prompt in every round is feasible and achieves zero fixed-rate regret.This rule requires no estimate of the target rates.Source: §C.2 · p. 24

Appendix D: Proof of the Fixed-Rate Guarantee

The fixed-rate guarantee proof analyzes online updates using pathwise projected-OGD bounds, then accounts for proxy discrepancy and the difference between virtual proposals and executed allocations. The resulting regret bound also reflects clipping and is capped using the fact that average regret is at most one.

Appendix D: Proof of the Fixed-Rate Guarantee

  • The proof frames the normalized updates as projected subgradient descent and uses pathwise inequalities even when losses depend on realized feedback and the current proposal.The analysis defines round-level convex losses after the proposal and proxy utilities are realized.Source: Appendix D · pp. 24–25
  • Proxy utility and its compact conjugate each differ from their target versions by at most the stated proxy-discrepancy term.The proof then passes from virtual proposals to executed allocations using a prefix-clipping rule.Source: Appendix D · p. 26
  • The clipping loss is absorbed by the budget-violation term, and the final average-regret bound is combined with the trivial upper bound of one.The proof substitutes the specified parameter relations before dividing by the number of prompts.Source: Appendix D · p. 26

Appendix E: Proof of the Same-Path Guarantee

Appendix E bounds deviations used in the same-path guarantee, while Appendix F proves two Beta-state propositions.

Appendix E: Proof of the Same-Path Guarantee

  • For q,q′ in [0,1/4] and z,n ≥ 0 with z + n ≤ Z, the incremental-utility derivative magnitude is bounded by κn.The proof uses the mean-value theorem to establish the stability inequality.Source: Appendix E · p. 26
  • Choosing each prompt’s midpoint realized rate gives a per-round deviation bound of VK/2, used in the comparison of feasible allocations.The proof applies the resulting inequality to both the dynamic optimum and CERO’s executed allocation.Source: Appendix E · p. 27
  • Total-budget feasibility bounds every same-path objective by λM, yielding normalized regret at most λ.The proof divides by M and combines the bounds to obtain (12).Source: Appendix E · p. 27

Appendix F: Proofs of the Beta-state Propositions

  • Conditional on Pi,k, two future Bernoulli rewards disagree with probability 2Pi,k(1 − Pi,k), underpinning Proposition 1’s sample-variance claim.The proof takes conditional expectations given Pi,k and then Hk.Source: Appendix F · p. 27
  • Proposition 2’s proof bounds |bqn − p(1 − p)| by |bm − p| + 1/[4(t + 1)], then combines bounds to establish (7).It sets t = n + s0 and bm = a/t.Source: Appendix F · p. 27

Appendix G: Implementation Details

The implementation details specify the training configuration, allocation settings, scheduler controls, and evaluation procedure.

Appendix G: Implementation Details

  • Training uses GRPO with within-group standard-deviation normalization, one PPO epoch per collected batch, and AdamW at a constant learning rate of 10−6.The configuration also specifies advantage clipping to [−5,5], a global PPO mini-batch size of 32, and disabled KL and entropy regularization.Source: Appendix G · p. 28
  • Rewards use the DAPO rule-based mathematical verifier, assigning +1 for success and 0 for failure.The same passage notes that the CERO run in Table 1 is included in the multi-seed results in Table 2.Source: Appendix G · p. 28
  • A scheduler round is an allocation opportunity, and zero-allocation rounds advance the scheduler without a policy update.A training step updates the policy on a collected rollout batch, while a data epoch traverses the training data loader and differs from a PPO epoch.Source: Appendix G · p. 28
  • CERO-greedy ranks prompts by marginal utility, selecting 64 prompts per round and generating one eight-response group for each.It preserves the reward-based utility and diminishing-return structure while replacing dual-based selection.Source: Appendix G · p. 28
  • Evaluation uses checkpoints after 500 scheduler rounds, 16 responses per problem, and a rule-based mathematical equivalence checker without an LLM judge.Evaluation also uses temperature 0.6, top-p 1.0, and top-k −1.Source: Appendix G · p. 28

Related papers

Loading 2610.09679v1…