Paper deep dive
CERO: Where and When to Allocate Rollouts for RL Post-Training
Yiming Zong, Yige Wang, Xing Hu, Jiashuo Jiang, Zuo-Jun Max Shen
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 10/11/2026, 2:59:10 AM
Summary
The paper introduces CERO, an online primal-dual scheduler for optimizing rollout allocation in reinforcement learning post-training. CERO coordinates a finite rollout budget over the entire training horizon by adapting prompt admission, revisit frequency, and per-round spending. It uses a concave surrogate utility of cumulative prompt exposure, linearized via Fenchel representation, and updates prompt-specific slopes and a shared budget price using projected online gradient descent based on reward-variation feedback. CERO achieves superior performance on mathematical reasoning benchmarks compared to fixed-rate and time-varying benchmarks.
Entities (9)
Relation Signals (7)
CERO → optimizes → Rollout Allocation
confidence 95% · CERO: Where and When to Allocate Rollouts for RL Post-Training
CERO → uses → Projected Online Gradient Descent
confidence 95% · projected online gradient descent updates prompt-specific supporting slopes and a shared budget price
CERO → uses → Fenchel Representation
confidence 95% · A compact Fenchel representation linearizes the dependence on cumulative exposure
Beta State → providessignalfor → Reward Variation
confidence 90% · A prompt-level Beta state provides a predictive signal of future within-group reward variation
CERO → outperforms → VIP
confidence 80% · CERO attains the highest avg@16 macro-average... CERO outperforming each ablated variant
CERO → outperforms → KnapsackRL
confidence 80% · CERO attains the highest avg@16 macro-average... CERO outperforming each ablated variant... fixed-pacing, preset-pacing, and direct marginal-utility variants.
CERO → outperforms → HORA
confidence 80% · CERO attains the highest avg@16 macro-average... CERO outperforming each ablated variant
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2610.09679v1
- Canonical: https://arxiv.org/abs/2610.09679v1
Trouble viewing inline? Open PDF directly →
Full Text
81,343 characters extracted from source content.
Expand or collapse full text
CERO: Where and When to Allocate Rollouts for RL Post-Training Yiming Zonga Yige Wanga Xing Hub Jiashuo Jianga Zuo-Jun Max Shenc Abstract 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. keywordsReinforcement Learning, LLM Post-training, Online Resource Allocation, Rollout Optimization †runningauthor: Zong, Wang, Jiang†runningtitle: CERO: Adaptive Rollout Optimization†authors: †affiliation: †affiliation: a Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology b Innovation and Information Management, The University of Hong Kong c Faculty of Engineering & Faculty of Business and Economics, The University of Hong Kong 1 Introduction Reinforcement learning with verifiable rewards has become a standard approach for post-training reasoning models. Within this paradigm, recent work has increasingly focused on adaptive rollout allocation to improve training efficiency. Standard GRPO-style training typically assigns the same number of responses to each selected prompt (Shao et al. 2024, Guo et al. 2025), even though the resulting groups can differ substantially in informativeness. In particular, all-correct or all-incorrect groups provide no within-group reward contrast. Recent methods therefore adapt how rollout budgets are distributed across prompts: KnapsackRL (Li et al. 2025) allocates a fixed exploration budget according to estimated task value, VIP (Nguyen et al. 2026) allocates minibatch rollouts to reduce expected gradient variance, and HORA (Wang et al. 2026) redistributes a batch budget according to marginal hit utility. Collectively, these methods primarily adapt where rollouts are allocated within a given round-level budget. We focus on a complementary temporal dimension that arises when rollout decisions are coupled by a shared finite training budget: Given a finite rollout budget, when should we spend more, and when less, across training? This horizon-level problem remains nontrivial even when each admitted prompt receives a fixed-size response group. The scheduler must still decide which prompts to admit, how often to revisit them across rounds, and how much of the remaining budget to spend at different training stages. Rollouts spent now cannot be reassigned later, and repeated exposure to the same prompt may yield diminishing marginal utility. We capture this effect with a concave utility over cumulative prompt exposure. These couplings motivate a resource allocation formulation over prompts and rounds. However, this finite-horizon formulation is not directly separable across rounds: each prompt’s cumulative allocation appears inside a nonlinear concave utility, and the global budget further couples spending decisions over time. Our key methodological contribution is to adapt Fenchel dualization and projected online gradient descent (OGD) to this rollout optimization problem. The Fenchel representation linearizes dependence on cumulative exposure, reducing the coupled horizon objective to tractable round-level allocation problems. Projected OGD then adapts prompt-specific supporting slopes from reward feedback and a shared budget price from aggregate allocation deviations. These dual signals play complementary roles in CERO: prompt-specific slopes guide prompt prioritization, while the shared price regulates budget pacing across rounds. A prompt-level Beta state provides a predictive signal of future within-group reward variation, while the dual variables and the remaining budget are carried forward across rounds, enabling coordination throughout training. This online structure admits pathwise guarantees for the surrogate allocation objective under fixed rates and a same-path time-varying benchmark. Empirically, CERO achieves the highest avg@16 macro-average on all three evaluated backbones under matched training-response budgets. Matched controls and mechanistic analyses further connect these gains to prompt-aware assignment and horizon-level budget adaptation, with CERO outperforming each ablated variant in multi-seed average performance. Figure 1: Schematic comparison of rollout optimization. (a) Typical adaptive methods redistribute a fixed per-round budget across prompts. (b) CERO coordinates prompt admission and per-round budget pacing under a shared finite training budget, with admitted prompts receiving fixed-size response groups. Our contributions are threefold: • We formulate finite-horizon rollout optimization as a resource-allocation problem with a concave utility over cumulative prompt exposure, and derive an online primal–dual scheduler using a compact Fenchel representation and projected OGD. The resulting scheduler coordinates prompt admission, repeated exposure across rounds, and per-round spending under a shared finite budget. • We establish pathwise guarantees for the surrogate allocation objective under fixed rates and a same-path time-varying benchmark. The bounds explicitly separate online optimization error, reward-proxy discrepancy, and temporal rate variation. • We evaluate CERO on three backbones and five mathematical reasoning benchmarks under the same rollout budgets. CERO obtains the highest avg@16 macro-average on each backbone. Matched controls and multi-seed ablations further connect these gains to prompt-aware assignment and horizon-level coordination, with CERO outperforming fixed-pacing, preset-pacing, and direct marginal-utility variants. Relation to prior work. CERO lies at the intersection of three related directions: difficulty-aware sampling and filtering, adaptive rollout allocation, and online resource allocation. The first focuses on identifying and prioritizing informative prompts, the second studies how limited rollout budgets should be allocated across prompts, and the third provides a broader framework for coordinating sequential decisions under shared resource constraints. Appendix A provides a detailed review of these three lines of research. 2 Finite-Horizon Rollout Optimization 2.1 Problem Formulation We consider a finite training process of K rounds over a fixed pool =x1,…,xMX=\x_1,…,x_M\ of M prompts. Let Ni,kN_i,k denote the number of units assigned to prompt i in round k, where one allocation unit corresponds to a fixed quantum of g∈ℤ>0g _>0 generated responses. Define its cumulative exposure by zi,k:=∑t=1kNi,t,zi,0=0z_i,k:= _t=1^kN_i,t, \ z_i,0=0. Let Nmax,C,B∈ℤ≥0N_ ,C,B _≥ 0 be the per-prompt per-round cap, the aggregate per-round capacity, and the total rollout budget. Our goal is to maximize the total utility of cumulative prompt exposure by allocating a finite rollout budget across prompts and rounds: max∈0,…,NmaxM×K _N∈\0,…,N_ \^M× K ∑i=1MUi(zi,K) _i=1^MU_i(z_i,K) (1) s.t. .t. ∑i=1MNi,k≤C, _i=1^MN_i,k≤ C, k∈[K], k∈[K], ∑k=1K∑i=1MNi,k≤B. _k=1^K _i=1^MN_i,k≤ B. Here UiU_i is a nondecreasing concave utility of cumulative exposure, specified in the next subsection. We assume 0<B≤KC,C≤MNmax.0<B≤ KC, C≤ MN_ . (2) Denote the feasible set in eq. 1 by B,CN_B,C. We distinguish allocation units from generated-response counts using the superscript resp: Ni,kresp=gNi,kN_i,k^resp=gN_i,k, Nmaxresp=gNmaxN_ ^resp=gN_ , Cresp=gC^resp=gC, and Bresp=gB^resp=gB. Finally, define Z:=KNmax,B¯:=BK,R:=BM,Z:=KN_ , B:= BK, R:= BM, where Z is the maximum per-prompt exposure over training, B¯ B is the average per-round budget, and R is the equal-share exposure scale. 2.2 Value-capture utility We use a concave surrogate utility to model diminishing returns to cumulative prompt exposure. Each prompt has a latent value-capture rate qi∈[0,1/4]q_i∈[0,1/4], for which Section 3 provides a reward-variation proxy. We instantiate the utility with the normalized exponential form U(q,z):=1−exp(−4λqzR),q∈[0,1/4],z∈[0,Z],U(q,z):=1- (-4λ q zR ), q∈[0,1/4], z∈[0,Z], where λ>0λ>0 controls saturation and z/Rz/R measures exposure relative to the equal-share horizon scale. By construction, the utility is nondecreasing and concave in z, encoding diminishing marginal utility with exposure. The marginal utility of an additional allocation unit satisfies 0≤∂zU(q,z)=4λqRexp(−4λqzR)≤λR=:c¯.0≤ _zU(q,z)= 4λ qR (-4λ q zR )≤ λR=: c. (3) This bound yields the compact slope domain [0,c¯][0, c] used in the Fenchel representation below. For comparison, consider a full-information oracle that knows =(q1,…,qM) q=(q_1,…,q_M) in advance and chooses the feasible allocation maximizing total value capture: Kstat():=max∑i=1M∈B,CU(qi,zi,K). OPT_K^stat( q):= _N _B,C _i=1^MU(q_i,z_i,K). (4) Since the objective depends on the allocation history only through zi,Kz_i,K, the oracle problem is determined by the terminal exposure vector. Appendix C.2 gives its optimal allocation. 2.3 Compact Fenchel representation To simplify notation, let Ui(z):=U(qi,z)U_i(z):=U(q_i,z). Using the uniform slope bound in eq. 3, define the restricted concave conjugate Ui∗(θ):=inf0≤s≤Zθs−Ui(s),θ∈[0,c¯].U_i^*(θ):= _0≤ s≤ Z\θ s-U_i(s)\, θ∈[0, c]. The interval [0,c¯][0, c] contains a supporting slope at every exposure level, so the representation remains exact on this compact domain. By concavity, Ui(z)=min0≤θ≤c¯θz−Ui∗(θ),0≤z≤Z.U_i(z)= _0≤θ≤ c\θ z-U_i^*(θ)\, 0≤ z≤ Z. Thus, the nonlinear dependence on cumulative exposure can be represented exactly through affine functions of z. To capture the scarcity of the shared budget across rounds, let μ∈[0,c¯]μ∈[0, c] denote the corresponding dual price. For a single round, let =(n1,…,nM) n=(n_1,…,n_M) denote the allocation vector and define the continuous feasible region C:=∈ℝM:0≤ni≤Nmax,∑ini≤C.P_C:= \ n ^M:0≤ n_i≤ N_ ,\ _in_i≤ C \. Since C and NmaxN_ are integers, CP_C is integral, so the continuous relaxation is exact for the round-level linear problem. Let =(θ1,…,θM)∈[0,c¯]M θ=( _1,…, _M)∈[0, c]^M collect the prompt-specific supporting slopes. Combining the Fenchel representation with the shared budget price μ makes the horizon-level upper bound separable across rounds, yielding the per-round dual objective L(,μ)=B¯μ+max∑i=1M∈C(θi−μ)ni−1K∑i=1MUi∗(θi),L( θ,μ)= Bμ+ _ n _C _i=1^M( _i-μ)n_i- 1K _i=1^MU_i^*( _i), By weak duality, Kstat()≤KL(,μ) OPT_K^stat( q)≤ KL( θ,μ) for all (,μ)( θ,μ) in the stated domains. Let di:=θi−μd_i:= _i-μ, which compares prompt xix_i’s supporting slope against the shared budget price. 3 Reward-Variation Proxy We use predicted within-group reward variance as a proxy for the latent value-capture rate in Section 2.2. This quantity characterizes expected reward contrast in a fresh response group, rather than directly estimating the downstream improvement from a policy update. Let r(x,y)∈0,1r(x,y)∈\0,1\ be the verifiable reward. At the beginning of round k, we maintain an auxiliary Beta state for prompt xix_i: Pi,k|ℋik∼Beta(ai,k,bi,k),ai,k,bi,k>0,P_i,k _i^k (a_i,k,b_i,k), a_i,k,b_i,k>0, where ℋikH_i^k denotes the reward history of prompt i. This state provides a compact predictive summary of the prompt’s observed reward history. Let Gi,k:=Ni,kresp=gNi,kG_i,k:=N_i,k^resp=gN_i,k denote the number of responses generated for prompt xix_i in round k. Let Si,kS_i,k and Fi,kF_i,k denote the numbers of successful and failed responses, and set Si,k=Fi,k=0S_i,k=F_i,k=0 if there is no allocation to this prompt. After round k, we update the Beta state with forgetting factor ρ∈(0,1]ρ∈(0,1]: ai,k+1=a0+ρ(ai,k−a0)+Si,k,bi,k+1=b0+ρ(bi,k−b0)+Fi,k, a_i,k+1=a_0+ρ(a_i,k-a_0)+S_i,k, \ b_i,k+1=b_0+ρ(b_i,k-b_0)+F_i,k, (5) where a0,b0>0a_0,b_0>0 are the prior parameters. When ρ=1ρ=1, the update reduces to standard cumulative Beta–Bernoulli updating. When ρ<1ρ<1, older evidence is gradually discounted toward the prior, allowing the state to track changes in the policy. We use predicted reward variation as a proxy for the latent value-capture rate: q^i,k:=[Pi,k(1−Pi,k)∣ℋik]=ai,kbi,k(ai,k+bi,k)(ai,k+bi,k+1)∈[0,1/4]. q_i,k:=E[P_i,k(1-P_i,k) _i^k]= a_i,kb_i,k(a_i,k+b_i,k)(a_i,k+b_i,k+1)∈[0,1/4]. (6) Proposition 3.1 (Predicted within-group reward variance) For any group size G≥2G≥ 2, suppose that conditional on (Pi,k,ℋik)(P_i,k,H_i^k) the next G binary rewards are i.i.d. Bernoulli(Pi,k)(P_i,k). Let r¯G:=G−1∑j=1Gr(j) r_G:=G^-1 _j=1^Gr^(j) and Var^G(r):=1G−1∑j=1G(r(j)−r¯G)2. Var_G(r):= 1G-1 _j=1^G (r^(j)- r_G )^2. Then it holds that [Var^G(r)∣ℋik]=q^i,k.E[ Var_G(r) _i^k]= q_i,k. Thus, q^i,k q_i,k is the predictive expected within-group reward variance. Let mi,k:=[Pi,k∣ℋik]m_i,k:=E[P_i,k _i^k] denote the predictive mean and we can obtain q^i,k=mi,k(1−mi,k)−Var(Pi,k∣ℋik). q_i,k=m_i,k(1-m_i,k)-Var(P_i,k _i^k). Therefore, q^i,k q_i,k is largest when the predicted success rate is near 1/21/2, but is reduced when the Beta state is more uncertain. Proposition 3.2 (Fixed-sample stationary calibration) Let Y1,…,YnY_1,…,Y_n be i.i.d. Bernoulli(p)(p) observations with fixed sample size n. Define a:=a0+∑j=1nYj,b:=b0+n−∑j=1nYj,s0:=a0+b0,a:=a_0+ _j=1^nY_j, \ b:=b_0+n- _j=1^nY_j, \ s_0:=a_0+b_0, and let q^n:=ab/[(a+b)(a+b+1)] q_n:=ab/[(a+b)(a+b+1)] and q:=p(1−p)q:=p(1-p). Then it holds that |q^n−q|≤n2(n+s0)+s0n+s0+14(n+s0+1).E| q_n-q|≤ n2(n+s_0)+ s_0n+s_0+ 14(n+s_0+1). (7) Consequently, q^n q_n is consistent at rate O(n−1/2)O(n^-1/2) under a stationary Bernoulli model with a fixed, nonadaptive sample size Proposition 3.2 concerns fixed-sample stationary calibration. Our allocation guarantees instead hold pathwise for arbitrary realized proxy sequences, with the bounds explicitly accounting for proxy error relative to the target rates. 4 CERO Algorithm To solve the finite-horizon rollout-allocation problem, we develop CERO, an online primal–dual scheduler summarized in Algorithm 1. At each round, CERO maintains normalized prompt-specific supporting slopes and a normalized shared budget price: θik=c¯ϑik,μk=c¯νk,ϑik,νk∈[0,1]. _i^k= c\, _i^k, μ^k= c\,ν^k, _i^k,ν^k∈[0,1]. After generating the selected responses and observing their rewards, CERO updates the predictive state and dual variables for the next round. Round-level allocation Since θik−μk=c¯(ϑik−νk) _i^k-μ^k= c( _i^k-ν^k), define the normalized margin di,k:=ϑik−νk.d_i,k:= _i^k-ν^k. A positive margin indicates that prompt xix_i’s supporting slope exceeds the shared budget price. CERO first computes the capacity-constrained virtual allocation ~k∈argmax∑i=1M∈C∩ℤMdi,kni. N_k∈ _ n _C ^M _i=1^Md_i,kn_i. (8) This problem has a simple exact solution: prompts with positive margins are ranked in decreasing order, with up to NmaxN_ units assigned to each while capacity remains. CERO then allocates rollout units in this order up to the remaining global budget, which is updated as Bk+1=Bk−∑iNi,k.B_k+1=B_k- _iN_i,k. Since the round-level objective is linear in the allocation units, the ranked solution assigns selected prompts the per-prompt cap, except possibly for a residual allocation. In Section 6, we use Nmax=2N_ =2 and choose the round capacity and total budget as multiples of NmaxN_ , so every selected prompt receives one eight-response group. CERO therefore adapts which prompts receive groups, how often they are revisited across rounds, and how many groups are generated per round. Reward feedback and supporting exposure After observing the rewards from round k, CERO updates the Beta state using eq. 5 and recomputes the reward-variation proxy q^i,k+1 q_i,k+1 using eq. 6. Let U^i,k+1(z):=U(q^i,k+1,z),ci,k+1:=4λq^i,k+1R. U_i,k+1(z):=U( q_i,k+1,z), \ c_i,k+1:= 4λ q_i,k+1R. For a supporting slope θ, the corresponding exposure is z^i,k+1∗(θ)∈argmin0≤z≤Zθz−U^i,k+1(z). z^*_i,k+1(θ)∈ _0≤ z≤ Z \θ z- U_i,k+1(z) \. For our exponential utility, this minimizer has the closed form z^i,k+1∗(θ)=z^∗(θ,ci,k+1) z^*_i,k+1(θ)= z^*(θ;c_i,k+1), where z^∗(θ,c)=0,c=0 or θ≥c,Z,c>0 and 0≤θ≤ce−cZ,1clogcθ,c>0 and ce−cZ<θ<c. z^*(θ;c)= cases0,&c=0 or θ≥ c,\\[2.84526pt] Z,&c>0 and 0≤θ≤ ce^-cZ,\\[2.84526pt] 1c cθ,&c>0 and ce^-cZ<θ<c. cases (9) Dual updates Let GB:=maxB¯,C−B¯G_B:= \ B,C- B\ denote the normalization scale for the budget-price update. CERO applies the normalized projected updates ϑik+1=Π[0,1][ϑik−γϑN~i,k−z^i,k+1∗(c¯ϑik)/KNmax],νk+1=Π[0,1][νk−γνB¯−∑iN~i,kGB] _i^k+1= _[0,1] [ _i^k- _ N_i,k- z_i,k+1^*( c _i^k)/KN_ ], \ ν^k+1= _[0,1] [ν^k- _ν B- _i N_i,kG_B ] (10) The prompt-specific update compares the virtual allocation N~i,k N_i,k with the per-round supporting exposure z^i,k+1∗(c¯ϑik)/K z^*_i,k+1( c _i^k)/K: allocating above this level decreases the supporting slope, while allocating below it increases the slope. The shared price increases when total virtual allocation exceeds B¯ B and decreases when it falls below B¯ B. Both updates use the virtual allocations ~k N_k rather than the budget-clipped allocations. Overall, the prompt-specific dual variables adapt relative prompt priority, while the shared price regulates budget pacing across rounds. Algorithm 1 CERO: Cross-Epoch Adaptive Rollout Optimization 1: Prompt pool xii=1M\x_i\_i=1^M; horizon K; global budget B; round capacity C; per-prompt cap NmaxN_ . 2: Set R=B/MR=B/M, Z=KNmaxZ=KN_ , c¯=λ/R c=λ/R, B¯=B/K B=B/K, and GB=maxB¯,C−B¯G_B= \ B,C- B\ 3: Initialize B1=B_1=B, (ai,1,bi,1)=(a0,b0)(a_i,1,b_i,1)=(a_0,b_0), q^i,1 q_i,1 by (6), ϑi1=4q^i,1 _i^1=4 q_i,1, and ν1∈[0,1]ν^1∈[0,1] 4: for k=1,…,Kk=1,…,K do 5: Compute margins di,k=ϑik−νkd_i,k= _i^k-ν^k and virtual proposal ~k N_k by the top-score solution of (8) 6: Execute proposals in decreasing-margin order subject to remaining budget BkB_k, producing k N_k 7: for i=1,…,Mi=1,…,M do 8: If Ni,k>0N_i,k>0, generate Ni,kresp=gNi,kN_i,k^resp=gN_i,k responses from πϕk(⋅∣xi) _φ^k(· x_i) and observe Si,kS_i,k successes and Fi,kF_i,k failures; otherwise, set Si,k=Fi,k=0S_i,k=F_i,k=0. 9: Update (ai,k+1,bi,k+1)(a_i,k+1,b_i,k+1) by (5) and compute q^i,k+1 q_i,k+1 10: Compute z^i,k+1∗(c¯ϑik) z_i,k+1^*( c _i^k) by (9) 11: Update ϑik+1 _i^k+1 by (10) 12: end for 13: Update νk+1ν^k+1 by (10) and set Bk+1=Bk−∑iNi,kB_k+1=B_k- _iN_i,k 14: If ∑iNi,k>0 _iN_i,k>0, update the policy using all executed round-k groups; otherwise, set ϕk+1=ϕkφ^k+1=φ^k. 15: if Bk+1=0B_k+1=0 then 16: Terminate. 17: end if 18: end for 5 Performance Guarantees We now analyze CERO with respect to the surrogate allocation objective in Section 2, while the downstream policy performance is evaluated empirically in Section 6. Fixed-rate benchmark. Let CERON^CERO be the executed allocation and define Kstat():=∑i=1MU(qi,zi,KCERO),RegKstat:=Kstat()−Kstat(). ALG_K^stat( q):= _i=1^MU(q_i,z_i,K^CERO), _K^stat:= OPT_K^stat( q)- ALG_K^stat( q). Let N¯=BKM=RK N= BKM= RK denote the average per-prompt per-round budget. Let q^i,k+1 q_i,k+1 be the post-feedback proxy used in round-k prompt-specific dual update and define the average absolute proxy discrepancy e¯Kstat:=1MK∑k=1K∑i=1M|q^i,k+1−qi|. e_K^stat:= 1MK _k=1^K _i=1^M| q_i,k+1-q_i|. Theorem 5.1 (Fixed-rate pathwise guarantee) Assume eq. 2. For any fixed target vector ∈[0,1/4]M q∈[0,1/4]^M and any realized proxy sequence q^i,k+1\ q_i,k+1\, Algorithm 1 with γϑ=γν=1K _ = _ν= 1 K satisfies RegKstatM≤min1,λNmax+GB/MN¯1K+8λNmaxN¯e¯Kstat. Reg_K^statM≤ \1,\ λ N_ +G_B/M N 1 K+8λ N_ N e_K^stat \. (11) This pathwise bound separates online optimization error from reward-proxy discrepancy. In particular, if Nmax/N¯N_ / N, GB/(MN¯)G_B/(M N), and λ remain bounded and e¯Kstat=O(K−1/2) e_K^stat=O(K^-1/2), then the regret per prompt vanishes at rate O(K−1/2)O(K^-1/2). The proof is given in Appendix D. Time-varying rates and a same-path benchmark. For a realized rate path 1:K q_1:K, define the value of round-k exposure using the current rate: ΔUi,k(,qi,k):=U(qi,k,zi,k)−U(qi,k,zi,k−1). U_i,k(N;q_i,k):=U(q_i,k,z_i,k)-U(q_i,k,z_i,k-1). Using the same qi,kq_i,k in both terms ensures that ΔUi,k U_i,k reflects only the utility gained from the new exposure Ni,kN_i,k, rather than changes due to variation in the rate itself. Writing 1:K=(1,…,K) q_1:K=( q_1,…, q_K), the same-path offline benchmark evaluates every feasible allocation plan against the same realized rate path: Kdyn(1:K):=max∈B,C∑k=1K∑i=1MΔUi,k(;qi,k). OPT_K^dyn( q_1:K):= _N _B,C _k=1^K _i=1^M U_i,k(N;q_i,k). Define Kdyn ALG_K^dyn by evaluating the executed CERO allocation in the same way, and let RegKdyn=Kdyn−KdynReg_K^dyn= OPT_K^dyn- ALG_K^dyn. By holding the realized rate path fixed across allocation plans, the benchmark focuses specifically on the quality of allocation decisions along a common realized rate path. Set e¯Kdyn:=1MK∑k=1K∑i=1M|q^i,k+1−qi,k|,VK:=∑k=1K−1∥k+1−k∥∞. e_K^dyn:= 1MK _k=1^K _i=1^M| q_i,k+1-q_i,k|, \ V_K:= _k=1^K-1 q_k+1- q_k _∞. Theorem 5.2 (Same-path drifting-rate guarantee) Under the same algorithmic setup and step sizes as in Theorem 5.1, for every realized rate path 1:K q_1:K and proxy sequence q^i,k+1\ q_i,k+1\, Algorithm 1 satisfies RegKdynM≤minλ,λNmax+GB/MN¯1K+8λNmaxN¯e¯Kdyn+4λ(1+NmaxN¯)VK. Reg_K^dynM≤ \λ,\ λ N_ +G_B/M N 1 K+8λ N_ N e_K^dyn+4λ (1+ N_ N )V_K \. (12) Comparing with Theorem 5.1, the additional VKV_K term explicitly isolates the effect of temporal drift from reward-proxy discrepancy. The proof is given in Appendix E. 6 Experiments 6.1 Main Results Experimental setup. We evaluate DeepSeek-R1-Distill-Qwen-1.5B (Guo et al. 2025), Qwen3-4B-Base (Yang et al. 2025), and Qwen2.5-7B-Instruct (Qwen et al. 2025), training all methods on the same uniformly sampled 50% subset of DAPO-Math-17K. Each run spans K=500K=500 scheduler rounds with a training-response budget of Bresp=256,000B^resp=256,000, and CERO uses eight responses per admitted prompt, with adaptation occurring through prompt admission and per-round group counts. We evaluate on AIME, AMC, MATH, MINERVA, and OlympiadBench using 16 responses per problem. We report avg@16 as the mean binary reward across responses and problems within each benchmark, and macro-average the five benchmark scores. Implementation details and compute measurements are provided in Appendices G and B.4, respectively. Baselines. We evaluate four methods: (i) GRPO (Guo et al. 2025), a widely used reinforcement learning method for training reasoning models; (i) KnapsackRL (Li et al. 2025), a representative prior method for adaptive rollout allocation, which dynamically allocates different numbers of rollouts across prompts; (i) CERO, our proposed method; and (iv) Random-matched CERO, an ablation that preserves the rollout allocation produced by CERO while assigning it to a random permutation of prompts. The latter controls for the allocation pattern and isolates the effect of our prompt selection mechanism. Table 1 shows that 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. It also achieves a higher macro-average than the adaptive KnapsackRL baseline on all three backbones, with the clearest improvement on DSR1-Q1.5B and smaller margins on the larger models. The Random-matched control further isolates the contribution of prompt-aware assignment. Its macro-average falls below CERO by 3.63, 1.50, and 1.63 points across the three backbones. Since Random-matched CERO preserves allocation sizes and timing while randomizing prompt assignment, this comparison supports the contribution of prompt-aware assignment under the same rollout schedule. Table 1: Evaluation performance (avg@16) comparison across different models and benchmarks. Base Model Method AIME AMC MATH MINERVA Olympiad Avg. DSR1-Q1.5B GRPO 5.62 32.23 66.12 21.90 25.07 30.19 KnapsackRL 4.58 32.38 65.14 20.93 24.59 29.53 CERO (ours) 7.92 38.03 68.05 22.66 27.41 32.81 Random-matched CERO 4.17 31.02 64.54 21.48 24.69 29.18 Qwen3-4B GRPO 13.54 50.98 80.10 30.72 40.94 43.26 KnapsackRL 17.50 53.24 80.08 31.36 41.26 44.69 CERO (ours) 17.29 53.69 80.83 31.94 43.06 45.36 Random-matched CERO 17.50 50.00 79.13 32.84 39.82 43.86 Q2.5-7B-Inst GRPO 12.92 48.42 74.36 28.06 37.34 40.22 KnapsackRL 13.33 50.90 77.15 28.72 38.64 41.75 CERO (ours) 15.83 49.77 77.44 27.55 38.45 41.81 Random-matched CERO 11.88 46.23 76.35 29.30 37.17 40.18 6.2 Ablation and Mechanism Analysis Is the reward-variation proxy informative? We examine whether the proxy anticipates the reward contrast available in future rollout groups. On the DSR1-Q1.5B backbone, we pair each pre-decision prediction q^i,k q_i,k with the unbiased sample variance of the eight binary rewards generated afterward, covering 32,00032,000 selected prompt–round groups. Across ten equal-budget intervals, higher predicted means tend to coincide with greater observed reward variation (Pearson r=0.769r=0.769; Figure 3), showing that the proxy tracks changes in reward contrast during training. Across seven prediction bins, higher-prediction bins generally exhibit larger observed mean variance, with closely preserved relative ordering (Pearson r=0.971r=0.971, Spearman ρ=0.964ρ=0.964; Figure 6). Together, these analyses provide evidence that the proxy offers an informative pre-decision signal for subsequent reward contrast among selected prompt–round groups. Appendix B.2 further examines absolute calibration. Figure 2: Temporal tracking of CERO’s reward-variation proxy on DSR1-Q1.5B. Figure 3: Prompt-selection lift by pre-decision predicted success rate. Does CERO prioritize informative prompts? We characterize CERO’s selection pattern by partitioning the 500 scheduler rounds into five 100-round stages and binning candidate prompt–round pairs by their pre-decision predicted success rate. For bin b in stage t, we define the selection lift as Lb,t=nb,tsel/nb,tcandntsel/ntcand,L_b,t= n^sel_b,t/n^cand_b,tn^sel_t/n^cand_t, where nseln^sel and ncandn^cand denote the numbers of selected and candidate prompt–round pairs. Consequently, Lb,t=1L_b,t=1 corresponds to uniform random selection, while Lb,t>1L_b,t>1 and Lb,t<1L_b,t<1 indicate over-selection and under-selection respectively. Figure 3 shows that CERO preferentially selects prompts with intermediate predicted success rates. Over the full run, the [0.4,0.6)[0.4,0.6) bin has a 1.72×1.72× selection lift, while both extreme bins have approximately 0.65×0.65×. With the full prompt pool available in every round, the lift directly measures CERO’s selection preference across predicted-success ranges relative to uniform selection. This pattern aligns with CERO’s reward-variation-based design: prompts for which both success and failure remain plausible offer opportunities for the within-group reward contrast needed by group-relative learning. The strength and breadth of the preference vary across training stages, with all three interior bins over-selected in the final stage. Does prompt-aware admission increase the fraction of effective groups? Let Si,kS_i,k of Gi,kG_i,k responses in group (i,k)(i,k) be correct. A group is effective if 0<Si,k<Gi,k0<S_i,k<G_i,k. Define the following effective-group rate EGR:=∑i,k0<Si,k<Gi,k∑i,kGi,k>0,EGR:= _i,k1\0<S_i,k<G_i,k\ _i,k1\G_i,k>0\, the fraction of executed groups supplying nonzero reward contrast. Figure 5 shows that under the matched budget of 256,000256,000 training responses, CERO produces 18,34718,347 effective groups out of 32,00032,000 executed groups, yielding an EGR of 57.3%, compared with 52.7% for Random-matched CERO and 48.7% for KnapsackRL. Because Random-matched CERO preserves CERO’s group sizes and spending schedule while randomizing prompt assignment, the 4.6-point gap provides controlled evidence that prompt-aware admission increases the fraction of mixed-outcome groups under the same rollout schedule. Figure 4: Effective-group rate over consumed rollout budget. Figure 5: Cross-epoch budget pacing in CERO. Epoch boundaries are marked above trajectory. What do dual-based selection and adaptive pacing contribute? We first characterize CERO’s budget pacing through the cumulative response gap from a uniform spending schedule: Gkexec:=∑τ=1k∑iNi,τresp−kB¯resp,B¯resp:=BrespK=512.G_k^exec:= _τ=1^k _iN_i,τ^resp-k B^resp, B^resp:= B^respK=512. Positive and negative gaps indicate spending ahead of and behind the uniform schedule, respectively. Figure 5 shows that spending deviations persist across data-epoch boundaries. The cumulative surplus peaks at 1,920 responses and returns to zero at the end of training, exhausting the 256,000-response budget exactly. This trajectory characterizes CERO’s nonuniform budget consumption. Table 2 evaluates the contributions of selection and pacing. CERO-fixed retains CERO’s reward-proxy and prompt-dual updates but fixes ν=0ν=0 and allocates 512512 responses per round. CERO-preset follows a predetermined front-loaded schedule: 528528 responses per round for the first 250250 rounds and 496496 for the remaining 250250 rounds. CERO-greedy retains CERO-fixed’s proxy estimator, utility function, and per-round quota, but selects prompts by the marginal utility of an additional complete group rather than by prompt-dual scores. Table 2: Prompt-selection and pacing ablations on DSR1-Q1.5B. Avg. denotes the five-benchmark avg@16 macro-average (mean ± std over 3 seeds). Method Avg. CERO 32.26 ± 0.94 CERO-fixed 31.13 ± 0.72 CERO-greedy 30.97 ± 0.38 CERO-preset 30.71 ± 0.54 Across three training seeds, CERO achieves the highest macro-average of 32.26±0.9432.26± 0.94, outperforming CERO-fixed, CERO-preset, and CERO-greedy by 1.131.13, 1.551.55, and 1.291.29 points on average, respectively. The gains over CERO-fixed and CERO-preset support the value of adapting budget consumption over the training horizon rather than using a fixed or predetermined spending schedule. Under the fixed 512-response quota, dual-guided and direct marginal-utility ranking yield similar mean scores of 31.13 and 30.97, whereas full CERO improves on both by more than one point. Together, these results support CERO’s central design: jointly coordinating prompt prioritization and budget pacing over the training horizon. 7 Conclusion We introduced CERO, a finite-horizon scheduler that coordinates prompt admission, repeated selection, and budget pacing under a shared rollout budget. The Fenchel-based primal–dual formulation yields tractable round-level decisions and pathwise guarantees for the surrogate allocation objective under fixed-rate and same-path time-varying benchmarks. Under matched training-response budgets, CERO achieves the highest avg@16 macro-average on all three backbones. Mechanistic analyses link its prompt choices to stronger within-group supervision, while multi-seed ablations show gains from adaptive pacing over fixed and preset schedules. Together, these results demonstrate the practical value of horizon-level rollout coordination for efficient RL post-training. References Agrawal and Devanur (2014) S. Agrawal and N. R. Devanur Fast algorithms for online stochastic convex programming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, p. 1405–1424. Cited by: Appendix A. Agrawal et al. (2014) S. Agrawal, Z. Wang, and Y. Ye A dynamic near-optimal algorithm for online linear programming. Operations Research 62 (4), p. 876–890. Cited by: Appendix A. Balseiro et al. (2020) S. Balseiro, H. Lu, and V. Mirrokni Dual mirror descent for online allocation problems. In International Conference on Machine Learning, p. 613–628. Cited by: Appendix A. Buchbinder and Naor (2005) N. Buchbinder and J. Naor Online primal-dual algorithms for covering and packing problems. In European Symposium on Algorithms, p. 689–701. Cited by: Appendix A. Buchbinder and Naor (2006) N. Buchbinder and J. Naor Improved bounds for online routing and packing via a primal-dual approach. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), p. 293–304. Cited by: Appendix A. Chen and Wang (2015) X. A. Chen and Z. Wang A dynamic learning algorithm for online matching problems with concave returns. European Journal of Operational Research 247 (2), p. 379–388. Cited by: Appendix A. Chen et al. (2025) X. Chen, J. Lu, M. Kim, D. Zhang, J. Tang, A. Piché, N. Gontier, Y. Bengio, and E. Kamalloo Self-evolving curriculum for llm reasoning. arXiv preprint arXiv:2505.14970. Cited by: Appendix A. Devanur and Hayes (2009) N. R. Devanur and T. P. Hayes The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, p. 71–78. Cited by: Appendix A. Devanur and Jain (2012) N. R. Devanur and K. Jain Online matching with concave returns. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, p. 137–144. Cited by: Appendix A. Feldman et al. (2010) J. Feldman, M. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms, p. 182–194. Cited by: Appendix A. Guo et al. (2025) D. Guo, D. Yang, H. Zhang, J. Song, R. Zhang, R. Xu, Q. Zhu, S. Ma, P. Wang, X. Bi, et al. Deepseek-r1: incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948. Cited by: §1, §6.1, §6.1. Hu et al. (2025) Z. Hu, J. Qiu, T. Bai, H. Yang, B. Yuan, Q. Jing, C. He, and W. Zhang VADE: variance-aware dynamic sampling via online sample-level difficulty estimation for multimodal rl. arXiv preprint arXiv:2511.18902. Cited by: Appendix A. Jasin and Kumar (2012) S. Jasin and S. Kumar A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research 37 (2), p. 313–345. Cited by: Appendix A. Jiang et al. (2026) H. Jiang, H. Liu, and B. Mirzasoleiman Learning as reasoning unfolds: progressive rollout allocation for efficient reinforcement learning. arXiv preprint arXiv:2607.22002. Cited by: Appendix A. Jiang et al. (2025) J. Jiang, W. Ma, and J. Zhang Degeneracy is ok: logarithmic regret for network revenue management with indiscrete distributions. Operations Research 73 (6), p. 3405–3420. Cited by: Appendix A. Kesselheim et al. (2014) T. Kesselheim, A. Tönnis, K. Radke, and B. Vöcking Primal beats dual on online packing lps in the random-order model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, p. 303–312. Cited by: Appendix A. Kim et al. (2026) W. Kim, Z. Yang, J. N. Yan, and J. Liu Spend your rollouts where it counts: rollout allocation for group-based rl post-training. arXiv preprint arXiv:2605.26606. Cited by: Appendix A. Li and Ye (2022) X. Li and Y. Ye Online linear programming: dual convergence, new algorithms, and regret bounds. Operations Research 70 (5), p. 2948–2966. Cited by: Appendix A. Li et al. (2025) Z. Li, C. Chen, T. Yang, T. Ding, R. Sun, G. Zhang, W. Huang, and Z. Luo Knapsack rl: unlocking exploration of llms via optimizing budget allocation. arXiv preprint arXiv:2509.25849. Cited by: Appendix A, §1, §6.1. Liao et al. (2025) M. Liao, X. Xi, C. Ruinian, J. Leng, Y. Hu, K. Zeng, S. Liu, and H. Wan Enhancing efficiency and exploration in reinforcement learning for LLMs. In Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, Suzhou, China, p. 1451–1463. External Links: Link, Document, ISBN 979-8-89176-332-6 Cited by: Appendix A. Lin et al. (2025) Z. Lin, M. Lin, Y. Xie, and R. Ji Cppo: accelerating the training of group relative policy optimization-based reasoning models. arXiv preprint arXiv:2503.22342. Cited by: Appendix A. Mahrooghi et al. (2026) I. Mahrooghi, A. Lotfi, and E. Abbe Goldilocks rl: tuning task difficulty to escape sparse rewards for reasoning. arXiv preprint arXiv:2602.14868. Cited by: Appendix A. Mehta et al. (2007) A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani Adwords and generalized online matching. Journal of the ACM (JACM) 54 (5), p. 22–es. Cited by: Appendix A. Molinaro and Ravi (2014) M. Molinaro and R. Ravi The geometry of online packing linear programs. Mathematics of Operations Research 39 (1), p. 46–59. Cited by: Appendix A. Nguyen et al. (2026) T. H. Nguyen, B. Nguyen, W. Ma, Y. Zhao, R. She, and V. A. Nguyen Adaptive rollout allocation for online reinforcement learning with verifiable rewards. In International Conference on Learning Representations, Vol. 2026, p. 136100–136132. Cited by: Appendix A, §1. Qwen et al. (2025) Qwen, :, A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, H. Lin, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Lin, K. Dang, K. Lu, K. Bao, K. Yang, L. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Tang, T. Xia, X. Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, Z. Cui, Z. Zhang, and Z. Qiu Qwen2.5 technical report. External Links: 2412.15115, Link Cited by: §6.1. Shao et al. (2024) Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. Li, Y. Wu, et al. Deepseekmath: pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Cited by: Appendix A, §1. Sheng et al. (2025) G. Sheng, C. Zhang, Z. Ye, X. Wu, W. Zhang, R. Zhang, Y. Peng, H. Lin, and C. Wu Hybridflow: a flexible and efficient rlhf framework. In Proceedings of the Twentieth European Conference on Computer Systems, p. 1279–1297. Cited by: Appendix G. Shrivastava et al. (2025) V. Shrivastava, A. Awadallah, V. Balachandran, S. Garg, H. Behl, and D. Papailiopoulos Sample more to think less: group filtered policy optimization for concise reasoning. arXiv preprint arXiv:2508.09726. Cited by: Appendix A. Talluri and Van Ryzin (2006) K. T. Talluri and G. J. Van Ryzin The theory and practice of revenue management. Vol. 68, Springer Science & Business Media. Cited by: Appendix A. Tan et al. (2025) S. Tan, M. Luo, J. Wong, C. Cai, X. Shi, W. Y. Tang, M. Roongta, T. Zhang, L. E. Li, R. A. Popa, et al. DeepscaleR: effective rl scaling of reasoning models via iterative context lengthening. Cited by: Appendix G. Wang et al. (2026) T. Wang, S. Li, Y. Sun, D. Ding, and E. Dobriban Where to spend rollouts: hit-utility optimal rollout allocation for group-based rlvr. arXiv preprint arXiv:2605.07114. Cited by: §1. Xu et al. (2025) Y. E. Xu, Y. Savani, F. Fang, and J. Z. Kolter Not all rollouts are useful: down-sampling rollouts in llm reinforcement learning. arXiv preprint arXiv:2504.13818. Cited by: Appendix A. Yang et al. (2025) A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §6.1. Yao et al. (2026) Z. Yao, Y. Zhang, Y. Chen, Y. Sun, Z. Xu, Y. Yang, T. Hu, Q. Gu, H. Su, and X. Cai CoBA-rl: capability-oriented budget allocation for reinforcement learning in llms. arXiv preprint arXiv:2602.03048. Cited by: Appendix A. Yu et al. (2025) Q. Yu, Z. Zhang, R. Zhu, Y. Yuan, X. Zuo, Y. Yue, W. Dai, T. Fan, G. Liu, L. Liu, et al. Dapo: an open-source llm reinforcement learning system at scale. arXiv preprint arXiv:2503.14476. Cited by: Appendix G. Zhang et al. (2025a) R. Zhang, D. Arora, S. Mei, and A. Zanette Speed-rl: faster training of reasoning models via online curriculum learning. arXiv preprint arXiv:2506.09016. Cited by: Appendix A. Zhang et al. (2025b) Y. Zhang, W. Yao, C. Yu, Y. Liu, Q. Yin, B. Yin, H. Yun, and L. Li Improving sampling efficiency in rlvr through adaptive rollout and response reuse. arXiv preprint arXiv:2509.25808. Cited by: Appendix A. Zhang et al. (2026) Z. Zhang, Z. Han, C. Mavromatis, Q. Zhu, Y. Zhang, S. Guan, D. Wang, X. Zhou, S. Wang, S. Adeshina, et al. Train less, learn more: adaptive efficient rollout optimization for group-based reinforcement learning. arXiv preprint arXiv:2602.14338. Cited by: Appendix A. Appendix A Related Work Difficulty-aware sampling and filtering. Recent work has explored improving RL efficiency by prioritizing training examples and rollouts according to their difficulty or informativeness. At the query level, online curriculum and sample-selection methods dynamically adjust the training distribution to favor examples with greater learning value. Goldilocks RL [Mahrooghi et al., 2026] emphasizes problems of intermediate difficulty, while SPEED-RL [Zhang et al., 2025a], SEC [Chen et al., 2025], and VADE [Hu et al., 2025] similarly use online estimates of difficulty or training utility to prioritize informative samples. Related approaches operate after rollout generation by filtering or pruning trajectories with limited contribution to policy updates. CPPO [Lin et al., 2025] removes completions with low learning signals, PODS [Xu et al., 2025] selects informative subsets of generated responses, and GFPO [Shrivastava et al., 2025] filters rollouts based on their utility relative to generation cost. These methods collectively reduce computation spent on overly easy, overly difficult, redundant, or otherwise uninformative samples. Adaptive rollout allocation. Recent studies have increasingly treated rollout generation as a resource allocation problem, replacing the fixed group size in standard GRPO [Shao et al., 2024] with query-dependent rollout budgets. Some methods adapt allocation according to estimated difficulty, assigning more rollouts to challenging or uncertain queries and fewer to those with saturated outcomes [Liao et al., 2025, Zhang et al., 2025b]. Others formulate allocation through explicit estimates of training value, uncertainty, or marginal utility, including Knapsack RL [Li et al., 2025], CoBA-RL [Yao et al., 2026] and VIP [Nguyen et al., 2026]. A related direction makes allocation decisions progressively from intermediate rollout outcomes: Pilot-Commit [Kim et al., 2026], AERO [Zhang et al., 2026], and VIGOR [Jiang et al., 2026] use early samples to determine whether additional generation is worthwhile. Collectively, these methods improve rollout efficiency by directing computation toward queries where additional exploration is expected to provide the greatest learning value. Online resource allocation. Online resource allocation is a central topic in the online optimization literature and has been applied in many operational settings, including ad assignment [Mehta et al., 2007], revenue management [Talluri and Van Ryzin, 2006, Jasin and Kumar, 2012, Jiang et al., 2025], and online packing/covering problems [Buchbinder and Naor, 2005, Buchbinder and Naor, 2006, Feldman et al., 2010]. The existing algorithmic literature can be broadly organized according to how it exploits dual information. A dominant class of methods uses dual prices as signals for making online allocation decisions. Within this class, some papers adopt a learn-once strategy: they reserve an initial set of arrivals for estimation, compute a price vector from that sample, and then use the same prices for all future decisions [Devanur and Hayes, 2009, Feldman et al., 2010, Molinaro and Ravi, 2014, Devanur and Jain, 2012]. Other papers advocate adaptive updating, where the pricing rule is revised at multiple points over time through repeated re-solving, leading to stronger robustness and improved horizon dependence [Agrawal et al., 2014, Li and Ye, 2022, Chen and Wang, 2015]. In parallel, other works depart from this paradigm by developing primal-oriented algorithms [Kesselheim et al., 2014] or first-order schemes that do not require repeated computation of dual prices [Agrawal and Devanur, 2014, Balseiro et al., 2020]. Appendix B Additional Results and Diagnostics B.1 Pass@16 Evaluation In addition to the avg@16 results reported in the main text, we evaluate pass@16 performance to measure success coverage under repeated sampling. Pass@16 is the percentage of problems with at least one correct response among these 16 samples: pass@16=100||∑x∈∑j=116rx,j>0.pass@16= 100|D| _x 1 \ _j=1^16r_x,j>0 \. For binary rewards, this is equivalent to averaging the maximum reward among the 16 responses for each problem. Table 3 shows that CERO improves the pass@16 macro-average over GRPO on all three backbones, with gains of 1.711.71, 0.390.39, and 1.581.58 points. It achieves the highest macro-average on DeepSeek-R1-Distill-Qwen-1.5B and Qwen2.5-7B-Instruct, reaching 50.9950.99 and 62.3462.34, respectively. On Qwen3-4B, KnapsackRL achieves the highest score of 67.0967.09, compared with 65.4565.45 for CERO. Together with the avg@16 results, these findings show improvements over GRPO in both average response accuracy and repeated-sampling success coverage. Table 3: Evaluation performance (pass@16) comparison across different models and benchmarks. Base Model Method AIME AMC MATH MINERVA Olympiad Avg. DSR1-Q1.5B GRPO 20.00 55.42 83.40 46.69 40.89 49.28 KnapsackRL 20.00 56.63 82.80 42.65 40.59 48.53 CERO (ours) 20.00 62.65 84.20 44.85 43.26 50.99 Random-matched CERO 13.33 51.81 81.40 45.96 39.70 46.44 Qwen3-4B GRPO 40.00 79.52 92.00 51.10 62.67 65.06 KnapsackRL 46.67 80.72 92.20 51.84 64.00 67.09 CERO (ours) 40.00 83.13 92.20 52.21 59.70 65.45 Random-matched CERO 43.33 73.49 92.00 51.10 61.04 64.19 Q2.5-7B-Inst GRPO 33.33 73.49 91.40 47.79 57.78 60.76 KnapsackRL 30.00 74.70 92.00 48.53 60.30 61.10 CERO (ours) 36.67 78.31 89.40 48.53 58.81 62.34 Random-matched CERO 30.00 71.08 88.80 46.69 56.74 58.66 B.2 Reliability of the Reward-Variation Proxy We examine whether CERO’s pre-decision reward-variation proxy captures differences in subsequently observed group variance, both across prediction levels and over the training trajectory. Diagnostic setup. We analyze 32,000 executed prompt–round groups from the DSR1-Q1.5B run. For each group, we pair the pre-decision prediction q^i,k q_i,k with the unbiased sample variance vi,k=Var^8(ri,k)v_i,k= Var_8(r_i,k) of the eight binary rewards generated afterward. Figure 6 aggregates these pairs into seven nonempty prediction bins and plots the mean prediction q¯ℓ q_ against the mean observed variance v¯ℓ v_ . Vertical error bars show nominal 95% normal-approximation intervals, v¯ℓ±1.96sℓnℓ, v_ ± 1.96\, s_ n_ , where nℓn_ is the number of groups in bin ℓ and sℓs_ is the sample standard deviation of their observed group variances. These intervals use group-level standard errors within a single run, without adjustment for repeated-prompt or temporal dependence. Association across prediction levels. Figure 6 shows a strong positive association between predicted and observed bin means, with Pearson correlation r=0.971r=0.971 and Spearman correlation ρ=0.964ρ=0.964. Across the plotted prediction range, the observed mean group variance rises overall from approximately 0.03 to 0.20. Higher-prediction bins generally correspond to greater realized reward variation, and the ordering of the bin means is closely preserved despite a local fluctuation in the intermediate range. The proxy therefore distinguishes prediction ranges associated with substantially different levels of subsequent reward contrast. Because the predictions are recorded before the current-round responses are generated, this association reflects information available when CERO makes its allocation decisions. Absolute calibration. The predicted values also exhibit an upward offset in numerical scale. Across the selected groups, the mean predicted variance is 0.154, compared with a mean observed variance of 0.119. Consistent with this difference, the bin means in Figure 6 lie below the diagonal marking equality between predictions and observations. The strong correlations and the displacement from the diagonal characterize two distinct properties: the proxy captures differences across prediction levels while tending to overestimate absolute reward variance. This distinction matters for CERO because q^i,k q_i,k enters the surrogate utility and prompt-dual updates numerically, rather than serving only as a ranking statistic. The diagnostic thus identifies both the information carried by the proxy and the calibration offset present in the analyzed run. Temporal tracking and allocation relevance. Figure 3 provides a complementary view by aggregating the same trajectory into ten consecutive equal-budget intervals of 3,200 groups each. Predicted and observed interval means co-vary over training, with Pearson correlation r=0.769r=0.769. Their trajectories capture common decreases and rebounds, showing that the proxy reflects changes in reward variation as training progresses, in addition to the differences across prediction levels shown in Figure 6. This behavior is relevant to group-relative supervision: mixed-outcome groups provide positive reward variance, whereas all-correct and all-incorrect groups provide no within-group reward contrast. Together, the prediction-bin and temporal analyses support q^i,k q_i,k as an informative prospective signal for CERO’s allocation mechanism. They complement the selection-lift and effective-group analyses in Section 6.2, which examine how the resulting allocation translates that signal into prompt choices and usable supervision. Figure 6: Calibration of CERO’s reward-variation proxy on DSR1-Q1.5B. Points show predicted and observed bin means across seven prediction bins; vertical bars indicate nominal 95% within-run intervals for the observed means. The dashed diagonal marks perfect calibration. B.3 Cross-Round Prompt Exposure To examine how CERO redistributes repeated exposure over the training horizon, we compare terminal cumulative prompt exposure with GRPO. Following Section 2, we normalize each prompt’s terminal exposure by the equal-share scale R=B/MR=B/M. In Figure 7, the empirical CDF at x gives the fraction of prompts with zi,K/R≤xz_i,K/R≤ x. Because both methods use fixed-size response groups and the same total rollout budget, differences in terminal exposure reflect how many times each prompt is selected over the training horizon rather than differences in group size or aggregate exposure. Figure 7: Empirical CDF of normalized terminal prompt exposure zi,K/Rz_i,K/R for CERO and GRPO on DSR1-Q1.5B. The dashed line marks the equal-share exposure R=B/MR=B/M. Figure 7 shows that CERO induces a broader terminal-exposure distribution than GRPO. CERO spreads terminal exposure across three levels, with 57.5% of prompts at 0.84R0.84R, 27.8% at 1.12R1.12R, and a 14.7% high-exposure tail at 1.40R1.40R. GRPO is more concentrated, with 41.0% and 58.1% of prompts at 0.84R0.84R and 1.12R1.12R, respectively. Thus, CERO shifts exposure away from the more concentrated GRPO pattern: a larger fraction of prompts receive below-equal-share exposure, while a smaller subset is revisited sufficiently often to reach substantially above the equal-share level. Since both methods use the same total rollout budget, this broader distribution reflects a redistribution of repeated selections across prompts rather than additional aggregate exposure. In particular, CERO trades fewer revisits to some prompts for more persistent revisiting of others over the training horizon. B.4 Computational Cost We compare the training cost of CERO, Random-matched CERO, KnapsackRL, and vanilla GRPO. For every backbone, all methods use the same number of GPUs, 500 scheduler rounds, and a matched budget of 256,000 training responses. End-to-end GPU-hours are calculated as the Slurm elapsed time multiplied by the number of allocated GPUs. This measurement includes initialization, in-training validation, and checkpointing. Figure 8 provides a detailed comparison for the 1.5B backbone. In addition to end-to-end GPU-hours, we report core training time normalized by the number of generated response tokens. The normalized measurement excludes validation and checkpointing but includes rollout generation, reward computation, log-probability computation, policy optimization, and allocation-related operations. Figure 8: Training-compute comparison on DeepSeek-R1-Distill-Qwen-1.5B under a matched response budget. The left panel reports end-to-end GPU-hours, while the right panel reports core training time normalized by generated response tokens. On the 1.5B backbone, CERO, Random-matched CERO, KnapsackRL, and vanilla GRPO consume 16.9416.94, 17.1517.15, 17.5317.53, and 17.5717.57 GPU-hours, respectively. Their token-normalized core costs are 84.284.2, 84.584.5, 83.683.6, and 84.284.2 seconds per million generated response tokens. The normalized measurements differ by only approximately 1.1%1.1\% of their mean value, with CERO being nearly identical to vanilla GRPO. CERO therefore combines adaptive allocation with token-normalized core training cost comparable to the baselines in the 1.5B experiment. We also measure end-to-end GPU-hours for the larger backbones. On Qwen3-4B-Base, CERO uses 36.3136.31 GPU-hours, Random-matched CERO uses 36.7836.78 GPU-hours, KnapsackRL uses 35.8535.85 GPU-hours, and vanilla GRPO uses 36.8936.89 GPU-hours. These values correspond to wall-clock times of 9.089.08, 9.199.19, 8.968.96, and 9.229.22 hours, respectively, using four H800 GPUs. The differences among the four methods are within approximately 3%3\% of their mean compute cost. On Qwen2.5-7B-Instruct, CERO, Random-matched CERO, KnapsackRL, and vanilla GRPO use 31.4631.46, 32.7832.78, 34.9934.99, and 31.7231.72 GPU-hours, respectively. Their corresponding wall-clock times are 7.867.86, 8.198.19, 8.758.75, and 7.937.93 hours on four H800 GPUs. CERO therefore remains comparable to the baselines in end-to-end computational cost as the backbone size increases. The end-to-end measurements capture the practical cost of each complete training protocol under the matched response budget, including differences in response lengths and update counts. CERO and Random-matched CERO perform 488, 486, and 487 policy updates on the 1.5B, 4B, and 7B backbones, respectively, while GRPO and KnapsackRL perform 500. Zero-allocation rounds account for the lower update counts. Each cost measurement is obtained from one completed run per method and backbone. Across the reported runs, CERO combines adaptive prompt selection and cross-epoch budget pacing with comparable end-to-end training cost. On the 1.5B backbone, its token-normalized core cost matches GRPO at 84.2 seconds per million generated response tokens. Appendix C Utility Properties and Full-Information Oracle C.1 Exact Conjugate, Fenchel Representation, and Stability Fix q∈[0,1/4]q∈[0,1/4], set c=4λq/Rc=4λ q/R, and write Uc(z)=1−e−czU_c(z)=1-e^-cz on [0,Z][0,Z]. Define Uc,Z∗(θ):=inf0≤z≤Zθz−Uc(z).U_c,Z^*(θ):= _0≤ z≤ Z\θ z-U_c(z)\. (13) Lemma C.1 (Closed-form compact conjugate) If c=0c=0, then Uc,Z∗(θ)=0U_c,Z^*(θ)=0 for every θ≥0θ≥ 0. If c>0c>0, then Uc,Z∗(θ)=θZ−1+e−cZ,0≤θ≤ce−cZ,θclogcθ+θc−1,ce−cZ<θ<c,0,θ≥c.U_c,Z^*(θ)= casesθ Z-1+e^-cZ,&0≤θ≤ ce^-cZ,\\[2.84526pt] θc cθ+ θc-1,&ce^-cZ<θ<c,\\[5.69054pt] 0,&θ≥ c. cases (14) The minimizer is given by (9). Proof C.2 For c>0c>0, differentiate θz−1+e−czθ z-1+e^-cz. Its derivative is θ−ce−czθ-ce^-cz and is strictly increasing in z. If θ≤ce−cZθ≤ ce^-cZ, the objective is nonincreasing on [0,Z][0,Z] and the minimum is at Z. If ce−cZ<θ<cce^-cZ<θ<c, the unique root is z=c−1log(c/θ)z=c^-1 (c/θ). If θ≥cθ≥ c, the minimum is at 00. Substitution yields (14). The case c=0c=0 is immediate. We also write Uq∗(θ):=U4λq/R,Z∗(θ)U_q^*(θ):=U_4λ q/R,Z^*(θ) for the compact conjugate parameterized by q; in particular, Ui∗(θ)=Uqi∗(θ)U_i^*(θ)=U_q_i^*(θ) in Section 2.3. Lemma C.3 (Exact compact biconjugate and stability) For every q∈[0,1/4]q∈[0,1/4] and z∈[0,Z]z∈[0,Z], U(q,z)=min0≤θ≤c¯θz−Uq∗(θ).U(q,z)= _0≤θ≤ c\θ z-U_q^*(θ)\. (15) Moreover, for q,q′∈[0,1/4]q,q ∈[0,1/4], sup0≤z≤Z|U(q,z)−U(q′,z)| _0≤ z≤ Z|U(q,z)-U(q ,z)| ≤4λZR|q−q′|, ≤ 4λ ZR|q-q |, (16) sup0≤θ≤c¯|Uq∗(θ)−Uq′∗(θ)| _0≤θ≤ c|U_q^*(θ)-U_q ^*(θ)| ≤4λZR|q−q′|. ≤ 4λ ZR|q-q |. (17) Proof C.4 The slope of U(q,⋅)U(q,·) lies in [0,c¯][0, c]. For a fixed z, choose the supporting slope θz=∂zU(q,z) _z= _zU(q,z), with one-sided derivatives at the endpoints. Concavity gives U(q,s)≤U(q,z)+θz(s−z),U(q,s)≤ U(q,z)+ _z(s-z), (18) so Uq∗(θz)=θzz−U(q,z)U_q^*( _z)= _zz-U(q,z). The reverse inequality follows directly from the definition of the conjugate. For stability, |∂qU(q,z)|=4λzRe−4λqz/R≤4λZR.| _qU(q,z)|= 4λ zRe^-4λ qz/R≤ 4λ ZR. (19) The first bound follows from the mean-value theorem. Applying a common uniform perturbation before taking the infimum over z∈[0,Z]z∈[0,Z] gives the conjugate bound. C.2 Full-Information Oracle We characterize the fixed-rate full-information benchmark when the target rates q=(q1,…,qM)q=(q_1,…,q_M) are known. Since the objective depends only on terminal prompt exposures, the oracle can first determine the optimal exposure vector and then distribute these exposures across the K rounds. Terminal-exposure formulation. Writing zi=∑k=1KNi,kz_i= _k=1^KN_i,k and ci=4λqi/Rc_i=4λ q_i/R, the fixed-rate benchmark can be expressed as OPTKstat(q)=max∑i=1Mz∈ℤ≥0Mzi≤Z,∑izi≤B(1−e−cizi).OPT^stat_K(q)= _ subarraycz _≥ 0^M\\ z_i≤ Z,\ _iz_i≤ B subarray _i=1^M (1-e^-c_iz_i ). (20) Every feasible rollout plan induces an exposure vector satisfying these constraints. Conversely, every such integer vector admits a feasible round-level realization, as shown below. For the continuous relaxation, the uniform assignment Ni,k=zi/KN_i,k=z_i/K is feasible because zi≤KNmaxz_i≤ KN_ and ∑izi≤B≤KC _iz_i≤ B≤ KC. Continuous water-filling solution. Relaxing the integrality constraint gives a separable concave optimization problem. Let ξ≥0ξ≥ 0 be the multiplier for the total budget. For ci>0c_i>0, an interior optimum satisfies cie−cizi=ξc_ie^-c_iz_i=ξ. Consequently, for ξ>0ξ>0, the optimal exposure has the clipped water-filling form zicont(ξ)=[1cilogciξ][0,Z],ci>0,z_i^cont(ξ)= [ 1c_i c_iξ ]_[0,Z], c_i>0, (21) where [x][0,Z]=minZ,max0,x[x]_[0,Z]= \Z, \0,x\\. Let ℐ+=i:ci>0I_+=\i:c_i>0\. When 0<B<Z|ℐ+|0<B<Z|I_+|, the budget is binding and ξ can be chosen so that ∑i∈ℐ+zicont(ξ)=B _i _+z_i^cont(ξ)=B. The left-hand side is continuous and nonincreasing in ξ, allowing the price to be found by one-dimensional bisection. Prompts with ci=0c_i=0 contribute zero utility and may be assigned zero exposure. When B≥Z|ℐ+|B≥ Z|I_+|, assigning Z units to every positive-rate prompt is optimal; any remaining budget may be left unused or assigned to zero-rate prompts without changing the objective. Exact integer allocation. For integer exposures, the marginal utility of the ℓ -th allocation unit assigned to prompt i is Δi(ℓ):=U(qi,ℓ)−U(qi,ℓ−1)=(1−e−ci)e−ci(ℓ−1),ℓ=1,…,Z. _i( ):=U(q_i, )-U(q_i, -1)=(1-e^-c_i)e^-c_i( -1), =1,…,Z. (22) These marginal gains are nonnegative and nonincreasing in ℓ . Starting from zi=0z_i=0 for every prompt, the oracle repeatedly assigns one unit to an unsaturated prompt with the largest currently available gain Δi(zi+1) _i(z_i+1). Repeating this operation for B units produces an optimal integer exposure vector, allowing zero-gain assignments when necessary. The optimality follows from the decreasing marginal-gain sequences. A set of the B largest gains can be chosen to contain a prefix of each prompt’s sequence, with ties resolved in favor of earlier units. The greedy procedure constructs such a set while respecting zi≤Zz_i≤ Z. A max-heap containing the next available marginal gain for each unsaturated prompt computes the exposure vector in O(M+Blog(M+1))O(M+B (M+1)) time and O(M)O(M) auxiliary memory. Recovery of a feasible rollout plan. To realize any feasible integer exposure vector z, let T=∑iziT= _iz_i and list its T allocation units, placing the units for each prompt in one consecutive block. Assign the r-th unit in this list to round 1+((r−1)modK)1+((r-1) K). Each prompt’s units are thereby spread as evenly as possible across rounds, and the same is true of the total allocation. The resulting counts satisfy ∑k=1KNi,k=zi,Ni,k≤⌈ziK⌉≤Nmax,∑iNi,k≤⌈TK⌉≤C. _k=1^KN_i,k=z_i, N_i,k≤ z_iK ≤ N_ , _iN_i,k≤ TK ≤ C. (23) The final inequalities use zi≤KNmaxz_i≤ KN_ , T≤B≤KCT≤ B≤ KC, and the integrality of NmaxN_ and C. Thus, the exposure-level optimum is attainable under the original global-budget and per-round capacity constraints. Full-capacity boundary. When B=KMNmaxB=KMN_ and C=MNmaxC=MN_ , assigning Ni,k=NmaxN_i,k=N_ to every prompt in every round is feasible and yields zi,K=Zz_i,K=Z. Since each utility is nondecreasing in exposure, this allocation attains OPTKstat(q)=∑i=1MU(qi,Z).OPT^stat_K(q)= _i=1^MU(q_i,Z). The full-allocation rule therefore achieves zero fixed-rate regret without estimating the target rates. The oracle makes the diminishing-return structure explicit: additional units are assigned according to their remaining marginal utility rather than a prompt’s initial rate alone. It characterizes the fixed-rate benchmark, while CERO uses reward-derived proxy states and online dual updates to allocate rollouts as feedback becomes available. Appendix D Proof of the Fixed-Rate Guarantee For the analysis, if the execution budget is exhausted before round K, we continue the virtual iterates through the remaining rounds under the same update rules, with all subsequent executed allocations set to zero. For each round k, let U^i,k+1 U_i,k+1 be the post-feedback proxy utility and U^i,k+1∗ U_i,k+1^* its compact conjugate. Let ~k N_k be the virtual proposal and A~k=∑iN~i,k A_k= _i N_i,k. Work with the unnormalized duals θik=c¯ϑik _i^k= c _i^k and μk=c¯νkμ^k= cν^k. The normalized updates in (10) are equivalent to projected subgradient descent with αθ=c¯NmaxK,αμ=c¯GBK. _θ= cN_ K, _μ= cG_B K. (24) Define convex losses, after the round-k proposal and proxy utilities have been realized, by hk() h_k( θ) :=∑i=1M[θiN~i,k−1KU^i,k+1∗(θi)], := _i=1^M [ _i N_i,k- 1K U_i,k+1^*( _i) ], (25) mk(μ) m_k(μ) :=μ(B¯−A~k). :=μ( B- A_k). (26) Any z^i,k+1∗(θik) z_i,k+1^*( _i^k) is a supergradient of the concave conjugate at θik _i^k, so gθik=N~i,k−1Kz^i,k+1∗(θik)g_ _i^k= N_i,k- 1K z_i,k+1^*( _i^k) (27) is a subgradient of hkh_k. Also gμk=B¯−A~kg_μ^k= B- A_k is the gradient of mkm_k. The gradient bounds are ∥θk∥2≤MNmax,|gμk|≤GB. g_θ^k _2≤ MN_ , |g_μ^k|≤ G_B. (28) The domain diameters are c¯M c M and c¯ c. Standard projected-OGD analysis therefore gives ∑k=1Khk(k)−min∑k=1K∈[0,c¯]Mhk() _k=1^Kh_k( θ^k)- _ θ∈[0, c]^M _k=1^Kh_k( θ) ≤c¯MNmaxK, ≤ cMN_ K, (29) ∑k=1Kmk(μk)−min∑k=1Kμ∈[0,c¯]mk(μ) _k=1^Km_k(μ^k)- _μ∈[0, c] _k=1^Km_k(μ) ≤c¯GBK. ≤ cG_B K. (30) These inequalities are pathwise; the losses may depend on the realized feedback and current proposal. Define z~i:=∑k=1KN~i,k,T~:=∑iz~i,V~:=[T~−B]+. z_i:= _k=1^K N_i,k, T:= _i z_i, V:=[ T-B]_+. (31) Let U¯i∗(θ) U_i^*(θ) :=1K∑k=1KU^i,k+1∗(θ), := 1K _k=1^K U_i,k+1^*(θ), (32) U¯i(z) U_i(z) :=min0≤θ≤c¯θz−U¯i∗(θ). := _0≤θ≤ c\θ z- U_i^*(θ)\. (33) Separability gives min∑k=1Khk() _ θ _k=1^Kh_k( θ) =∑i=1MU¯i(z~i), = _i=1^M U_i( z_i), (34) min∑k=1K0≤μ≤c¯mk(μ) _0≤μ≤ c _k=1^Km_k(μ) =−c¯V~. =- c V. (35) Hence ∑k=1K[hk(k)+mk(μk)]≤∑iU¯i(z~i)+c¯(MNmax+GB)K−c¯V~. _k=1^K[h_k( θ^k)+m_k(μ^k)]≤ _i U_i( z_i)+ c(MN_ +G_B) K- c V. (36) Let ∗N^* attain (4), define zi∗=∑kNi,k∗z_i^*= _kN_i,k^*, and set ni∗=zi∗/Kn_i^*=z_i^*/K. Then 0≤ni∗≤Nmax0≤ n_i^*≤ N_ and ∑ini∗=1K∑izi∗≤BK=B¯≤C. _in_i^*= 1K _iz_i^*≤ BK= B≤ C. (37) Thus ∗∈C n^* _C. Since CP_C is integral, the integer proposal maximizes the same linear function over the continuous polytope. Therefore ∑i(θik−μk)N~i,k≥∑i(θik−μk)ni∗. _i( _i^k-μ^k) N_i,k≥ _i( _i^k-μ^k)n_i^*. (38) Using μk≥0μ^k≥ 0, ∑ini∗≤B¯ _in_i^*≤ B, and the proxy Fenchel representation yields hk(k)+mk(μk) h_k( θ^k)+m_k(μ^k) ≥1K∑i[θikzi∗−U^i,k+1∗(θik)] ≥ 1K _i [ _i^kz_i^*- U_i,k+1^*( _i^k) ] (39) ≥1K∑iU^i,k+1(zi∗). ≥ 1K _i U_i,k+1(z_i^*). (40) Summing and combining with (36) gives ∑i1K∑kU^i,k+1(zi∗)≤∑iU¯i(z~i)+c¯(MNmax+GB)K−c¯V~. _i 1K _k U_i,k+1(z_i^*)≤ _i U_i( z_i)+ c(MN_ +G_B) K- c V. (41) Let ei,k=|q^i,k+1−qi|e_i,k=| q_i,k+1-q_i| and δi,k:=4λZRei,k,Δ:=1K∑i,kδi,k. _i,k:= 4λ ZRe_i,k, := 1K _i,k _i,k. (42) By Lemma C.3, both the proxy utility and its conjugate differ from their target versions by at most δi,k _i,k. Consequently, Kstat()−∑iU(qi,z~i)+c¯V~≤c¯(MNmax+GB)K+2Δ. OPT_K^stat( q)- _iU(q_i, z_i)+ c V≤ c(MN_ +G_B) K+2 . (43) Since Z=KNmaxZ=KN_ , Δ=4λNmaxR∑i,kei,k=4λMNmaxN¯e¯Kstat. = 4λ N_ R _i,ke_i,k= 4λ MN_ N e_K^stat. (44) It remains to pass from virtual proposals to executed allocations. The prefix clipping rule implies ∑i(z~i−zi,KCERO)=V~. _i( z_i-z_i,K^CERO)= V. (45) Every target utility has derivative at most c¯ c, so 0≤∑i[U(qi,z~i)−U(qi,zi,KCERO)]≤c¯V~.0≤ _i[U(q_i, z_i)-U(q_i,z_i,K^CERO)]≤ c V. (46) This clipping loss is exactly absorbed by the violation term on the left of (43). Therefore RegKstat≤c¯(MNmax+GB)K+2Δ.Reg_K^stat≤ c(MN_ +G_B) K+2 . (47) Substitute c¯=λ/R c=λ/R, R=KN¯R=K N, use (44), and divide by M. Since every prompt utility lies in [0,1][0,1], the average regret is also at most one. Combining the two bounds gives (11). Appendix E Proof of the Same-Path Guarantee We first record a stability inequality for one incremental utility. Lemma E.1 (Increment stability) For any q,q′∈[0,1/4]q,q ∈[0,1/4] and z,n≥0z,n≥ 0 satisfying z+n≤Zz+n≤ Z, |[U(q,z+n)−U(q,z)]−[U(q′,z+n)−U(q′,z)]|≤4λRn|q−q′|. |[U(q,z+n)-U(q,z)]-[U(q ,z+n)-U(q ,z)] |≤ 4λRn|q-q |. (48) Proof E.2 Let κ=4λ/Rκ=4λ/R and G(q,z,n)=∫z+nκqe−κqss.G(q;z,n)= _z^z+nκ qe^-κ qs\,ds. (49) Then ∂qG(q,z,n)=∫z+nκ(1−κqs)e−κqss. _qG(q;z,n)= _z^z+nκ(1-κ qs)e^-κ qs\,ds. (50) Because |(1−x)e−x|≤1|(1-x)e^-x|≤ 1 for x≥0x≥ 0, the derivative magnitude is at most κnκ n. Apply the mean-value theorem. For each prompt choose the midpoint of its realized rate range, qi∘:=12(minkqi,k+maxkqi,k).q_i := 12 ( _kq_i,k+ _kq_i,k ). (51) Then |qi,k−qi∘|≤VK/2|q_i,k-q_i |≤ V_K/2 for every i,ki,k. For any feasible allocation N, let Jdyn() J^dyn(N) :=∑i,kΔUi,k(,qi,k), := _i,k U_i,k(N;q_i,k), (52) J∘() J (N) :=∑iU(qi∘,zi,K). := _iU(q_i ,z_i,K). (53) Using (48) and total budget feasibility, |Jdyn()−J∘()| |J^dyn(N)-J (N)| ≤4λR∑i,kNi,k|qi,k−qi∘| ≤ 4λR _i,kN_i,k|q_i,k-q_i | (54) ≤2λVKRB=2λMVK. ≤ 2λ V_KRB=2λ MV_K. (55) Applying this inequality to the dynamic optimum and to the executed CERO allocation gives RegKdyn≤Kstat(∘)−∑iU(qi∘,zi,KCERO)+4λMVK.Reg_K^dyn≤ OPT_K^stat( q )- _iU(q_i ,z_i,K^CERO)+4λ MV_K. (56) The average proxy error relative to ∘ q satisfies 1MK∑i,k|q^i,k+1−qi∘| 1MK _i,k| q_i,k+1-q_i | ≤e¯Kdyn+1MK∑i,k|qi,k−qi∘| ≤ e_K^dyn+ 1MK _i,k|q_i,k-q_i | (57) ≤e¯Kdyn+VK2. ≤ e_K^dyn+ V_K2. (58) Apply Theorem 5.1 with reference vector ∘ q and substitute the last inequality into (56). In addition, (3) and total budget feasibility imply that every same-path objective is at most λMλ M, so the normalized regret is at most λ. Dividing by M and combining the two bounds yields (12). Appendix F Proofs of the Beta-state Propositions Proof F.1 (Proof of Proposition 3.1) Conditional on Pi,kP_i,k, each pair of future Bernoulli rewards disagrees with probability 2Pi,k(1−Pi,k)2P_i,k(1-P_i,k). The unbiased sample variance for binary data satisfies 2Var^G(r)=(G2)−1∑1≤j<ℓ≤Gr(j)≠r(ℓ).2 Var_G(r)= G2^-1 _1≤ j< ≤ G1\r^(j)≠ r^( )\. Taking conditional expectations first given Pi,kP_i,k and then given ℋikH_i^k proves the claim. Proof F.2 (Proof of Proposition 3.2) Let t=n+s0t=n+s_0 and m^=a/t m=a/t. Then q^n=t+1m^(1−m^). q_n= tt+1 m(1- m). (59) The function x(1−x)x(1-x) is one-Lipschitz on [0,1][0,1], so |q^n−p(1−p)|≤|m^−p|+14(t+1).| q_n-p(1-p)|≤| m-p|+ 14(t+1). (60) Moreover, |m^−p|=|a0−ps0|t≤s0t,|E m-p|= |a_0-ps_0|t≤ s_0t, (61) and |m^−m^|≤Var(m^)=np(1−p)t≤n2t.E| m-E m|≤ Var( m)= np(1-p)t≤ n2t. (62) Combining the bounds proves (7). Appendix G Implementation Details Training. We use two locally modified veRL-based [Sheng et al., 2025] stacks with matched learner and decoding hyperparameters, vLLM 0.8.3 for generation, and FSDP for actor training. Bfloat16 is used for generation and actor computation. Experiments use two NVIDIA H800 GPUs for the 1.5B backbone and four for the 4B and 7B backbones. All methods use GRPO with within-group standard-deviation normalization, advantage clipping to [−5,5][-5,5], and loss averaged over valid response tokens. AdamW uses a constant learning rate of 10−610^-6, (β1,β2)=(0.9,0.999)( _1, _2)=(0.9,0.999), zero weight decay, and no warmup. We use one PPO epoch per collected batch, no reshuffling, and a global PPO mini-batch size of 32. The lower/upper policy clipping parameters are 0.20/0.280.20/0.28, the dual-clip constant is 1010, the importance-ratio cap is 22, and the gradient-norm threshold is 11. KL and entropy regularization are disabled. Training prompts are left-truncated to 2,048 tokens and responses are capped at 2,048 tokens; sampling uses temperature 1.01.0, top-p 1.01.0, and top-k −1-1. Training rewards are computed using the rule-based mathematical verifier from DAPO [Yu et al., 2025], which treats +1+1 as success and 00 as failure. The CERO run in Table 1 is included in the multi-seed results in Table 2. A scheduler round is one allocation opportunity, whereas a training step is one policy-update call on a collected rollout batch. Zero-allocation rounds advance the scheduler without updating the policy. A data epoch is one traversal of the training data loader, distinct from a PPO epoch over a collected rollout batch. Allocation settings. We use Algorithm 1 with g=4g=4 responses per allocation unit and Nmax=2N_ =2, C=132C=132, and B=64,000B=64,000 in allocation units. CERO uses a Beta(1,1)Beta(1,1) prior, λ=ρ=1λ=ρ=1, ν1=0.5ν^1=0.5, and γϑ=γν=1/500 _ = _ν=1/ 500. Ties use a fixed seed permutation. Reserve-aware catch-up was enabled but never activated in the reported CERO runs. KnapsackRL uses positive and negative base allocations of two, a reward-history buffer of length 16, a minimum initialized history length of four, and robust epoch estimation. CERO-greedy uses the same reward-proxy estimator, utility function, and fixed 512-response quota as CERO-fixed, but replaces prompt-dual scores with the marginal utility of one additional complete group. In our experiments, each group contains eight responses, corresponding to Nmax=2N_ =2 allocation units. At the beginning of round k, the selection score for prompt i is Δi,kgrp:=U(q^i,k,zi,k−1+Nmax)−U(q^i,k,zi,k−1), _i,k^grp:=U\! ( q_i,k,z_i,k-1+N_ )-U\! ( q_i,k,z_i,k-1 ), where q^i,k q_i,k is the pre-decision proxy and zi,k−1z_i,k-1 is the cumulative executed exposure in the control run. We use CERO’s exponential utility with the same saturation parameter and exposure normalization. Each round scores the full training prompt pool and selects the 6464 prompts with the largest scores, generating one eight-response group per prompt. This control preserves the reward-based utility and its diminishing-return structure while replacing dual-based selection with direct marginal-utility ranking. Evaluation. We follow Tan et al. [2025] and evaluate the checkpoint obtained after 500500 scheduler rounds using 16 responses per problem, temperature 0.60.6, top-p 1.01.0, and top-k −1-1. All methods use the same rule-based mathematical equivalence checker without an LLM judge. Metric definitions are given in Section 6 and Appendix B.1; computational costs and schedule audits are reported in Appendix B.4.