Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards
Authors: Hieu Trung Nguyen
Bao Nguyen
Wenao Ma
Yuzhi Zhao
Ruifeng She
Viet Anh Nguyen
Venue: ICLR 2026 Poster (2026)
Keywords: Reinforcement Learning
Reinforcement Learning from Verifiable Rewards
Resource Allocation
Large Language model post training
Primary area: reinforcement learning
TL;DR: VIP enhances rollout allocation in reinforcement learning for improved efficiency

Abstract: Sampling efficiency is a key bottleneck in reinforcement learning with verifiable rewards. Existing group-based policy optimization methods, such as GRPO, allocate a fixed number of rollouts for all training prompts. This uniform allocation implicitly treats all prompts as equally informative, and could lead to inefficient computational budget usage and impede training progress. We introduce VIP, a Variance-Informed Predictive allocation strategy that allocates a given rollout budget to the prompts in the incumbent batch to minimize the expected gradient variance of the policy update. At each iteration, VIP uses a lightweight Gaussian process model to predict per-prompt success probabilities based on recent rollouts. These probability predictions are translated into variance estimates, which are then fed into a convex optimization problem to determine the optimal rollout allocations under a hard compute budget constraint. Empirical results show that VIP consistently improves sampling efficiency and achieves higher performance than uniform or heuristic allocation strategies in multiple benchmarks.

Published as a conference paper at ICLR 2026
ADAPTIVE ROLLOUT ALLOCATION FOR ONLINE REINFORCEMENT LEARNING WITH
VERIFIABLE REWARDS
Hieu Trung Nguyen C+1, Bao Nguyen Wenao Ma Yuzhi Zhao", Ruifeng She Viet Anh Nguyen The Chinese University of Hong Kong. Huuawei Hong Kong Research Center [thnguyen, htgggyyennnnguunnn.n. nbnguyen, nguyen] @se. cuhk. edu.hk hk
(ma , wenao, she. ruifeng) @wwwwei.................. com
yzzhao2-c@my eeehoo--@m..cityueeeu ciw.y.edu..uu...........
O Source Code: https://ggthhiii com Hitp/H9t/uNNTIPPP
ABSTRACT
Sampling efficiency is key bottleneck in reinforcement learning with verifiable rewards. Existing group-based policy optimization methods, such as GRPO, allo- cate a fixed number of rollouts for all training prompts. This uniform allocation implicitly treats all prompts as equally informative, and could lead to inefficient computational budget usage and impede training progress. We introduce VIP, a Variance-Informed Predictive allocation strategy that allocates a given rollout budget to the prompts in the incumbent batch to minimize the expected gradient variance of the policy update. At each iteration, VIP uses a lightweight Gaussian process model to predict per-prompt success probabilities based on recent roll- outs. These probability predictions are translated into variance estimates, which are then fed into a convex optimization problem determine the optimal rollout allocations under a hard compute budget constraint. Empirical results show that VIP consistently improves sampling efficiency and achieves higher performance than uniform or heuristic allocation strategies in multiple benchmarks.
INTRODUCTION
The advent of Language Models (LMs) has marked a new era in artificial intelligence, transforming
models from static knowledge bases into dynamic, intelligent agents capable of complex reasoning.
creative generation, and intricate problem-solving This evolution has been largely driven by the
advancement of post-training methods (Tong et 2024 Rafailov et al. 2023 Shao et al. (024)
and test-time scaling methods (Snell et al.] 2024 Feng el al.] 2023 Nguyen et al. 2025a b). which are crucial for aligning base LM's vast, general knowledge with specific human intentions, ethical
guidelines, and desired taiketrie behaviors. These refinement processes bridge the gap between a model that understands language and one that can reliably and safely act as a collaborator, sim- ulator, or autonomous agent. As LMs become more integrated into real-world applications, the effectiveness and efficiency of these post-training stages have become a primary focus of research and development.
While test-time scaling methods are training-free and effective in many scenarios, post-training gen- erally yields higher performance gains at lower inference budget. Two prominent paradigms are used for post-training LMs: Supervised Fine-Tuning (SFT) and Reinforcement Learning (RL). SET is computationally efficient approach that trains the model on curated dataset of onput- pairs, effectively equipping it with domain-specific knowledge. However, its effectiveness is of- ten hampered by the difficulty of curating high-quality and comprehensive datasets. In contrast, RL-based methods, which treat the model as an agent optimizing for reward signal derived from human preferences Reiinforcement Learning from Human Feedback, RLHF) or external verification
"Wor done during internship at Huawei Hong Kong Research Center
1 Equal contribution
"orrrsponniig author

---

Published as a conference paper at ICLR 2026
mechanisms (Reinforcement Learning from Verifialle Rewards, RLVR), can explore a broader tion space and achieve superior performance on complex, open-ended tasks. RLVR, in particular, has gained wide popularity thanks to its low reliance human input. However, the performance of RL methods comes at significant computational cost. Algorithms like Proximal Policy Optimization (PPO, [Schulman et al. (2013)) require the simultaneous training of separate value model to esti- mate the advantage of actions, which can be prohibitively memory-intensive in resource-constrained situations. To address this, family of "critic-free" or group-based RL methods has emerged, es- timating the advantage as a relative measure within a group of rollouts, essentially trading speed for memory efficiency. Such methods include GRPO, (Shao et al., (024), Dr. GRPO (Liu et al.] 2025), RLOO (Ahmadian et al.) 2024), and other variants. A direct drawback of these methods is the additional computation time required to generate multiple rollouts for a training example. The number of generations often needs to be large enough (e.g., 16) to obtain a stable training process, which exacerbates the generation overhead and eventually leads to a memory- bound system. Such high computational demands consequently highlight the need for greater sampling efficiency in the RL training process.
The high computational demands of RL algorithms have led to a body of work dedicated optimiz- ing this performance-com trade-off. One line research involves hybrid approaches that combine an initial SFT phase with a subsequent RL refinement stage (Chen al. 2025a) or merge the two stages into a single method (Fu et al., (025). These methods demonstrated improvement in smoothening or even accelerating the training process, but often fail to dynamically adapt to the training process based on the model's evolving capabilities for solving the training problems. The observation that simply filtering out problems where the accuracy is close either
can boost performance (Yu et al. 2025) hints at the potential for more adaptive control. To the best of our knowledge, there lack of crucial metries for such capabilities and, consequently, a lack of an adaptive control mechanism for the GRPO process.
To address such challenges, we introduce the Variance-Informee Predictive allocation strategy (VIP), principled training framework for efficient and adaptive rollout allocation in group-based policy optimization. We first provide a theoretical analysis of the gradient variance for three promi- nent RL algorithms, establishing the relationship between the gradient variance contributed by prompt and the probability that is solved by the current model. Building on this insight, at the beginning of each training iteration, VIP predicts the expected gradient variance of each prompt in a batch Based on these predictions, VIP then solves a convex optimization problem followed by integer rounding heuristic to allocate rollouts across prompts to minimize the total expected gra- dient variance under the given computational budget. The core contributions of this paper are the following:
Gradient variance analysis. We provide rigorous analysis of the effect of gradient variance on the RL training process. We derive the connection between gradient variance and success proba- bility for prevailing group-based RL methods, including Dr. GRPO and RLOO. This establishes the theoretical foundation for adaptively controlling budget allocation during training.
Variance prediction. VIP employs a Gaussian process (GP) over prompt embeddings to model the probability of success for each prompt in any training step. This enables recursive Bayesian updates that leverage both past rollout outcomes and the similarity structure of the prompts. The GP prediction allows the framework estimate the gradient variance for each prompt in the minibatch at every training step.
Variance-minimiznng rollout allocation. Given the predicted variances, VIP formulates a con- vex optimization problem to determine the optimal allocation of rollouts on prompts. This al- location minimizes the gradient variance subject to rollout budget constraint. We derive an efficient algorithm that provides the exact solution to the continuous relaxation and further de- velop a greedy incentive-based rounding heuristic to produce a feasible integer solution. This process enables fast resource allocation under computational budget constraints.
Our paper unfolds follows. Section 2 discusses related work on adaptive strategies over group- based RL frameworks for RLVR, while SectionBlaays the technical background on RLVR. Section presents our analysis of the per-prompt gradient variance. Section SariionnS@dd dellnnetes our VIP framework for variance prediction via Gaussian process, and the optimization problem for rollout allocation. Section 6 presents empirical results mathematical reasoning and information retrieval datasets.
2

---

Published as a conference paper at ICLR 2026
2 RELATED WORK
Recent advancements in group-based RL for LMs have focused on adaptive strategies to enhance both training efficiency and performance. These methods move beyond static training pipelines by dynamically selecting and managing data used for policy updates. Initial research empirically demonstrated that filtering out inon-informative" problems to which the model's accuracy is either 0 or can improve training efficiency, as these problems lead to rollout batches with zero variance and consequently make no contribution the gradient signal (Yu et al. 2025). Along similar lines, (Lin et al. 2025) filtered out rollouts with low absolute advantage, while (Xu et al. 2025) proposed to retain examples with the highest variance. Lacking an a priori measure of training prompt infor- mativeness, these methods require the pre-sampling of an large batch of rollouts before each update iteration, potentially negating efficiency gains from the significant sampling overhead.
Several works adopted pre-rollout estimation of the prompt informativeness. (Zheng et al. 2025) proposed skipping each problem with a probability determined by the number recent consecutive rollouts where the prompt is non-informative. (Zhang et al., 2025) proposed a signal-to-noise ratio indicating a problem's 's contribution to the gradient, and showed that training can be accelerated by generating small trial batch of rollouts to identify and filter out non-informative problems, and then continue sampling on intermediate-difinnn difficclly ones. (Sun et al. (025) designed a difficulty-targeted online selection algorithm with attention- based difficulty prediction and rollout replay. (Liao al., 2025) ranked problems by difficulty, indicated by the average rewards from past rollouts, and al- located resources to sample larger batches for difficult prompts. (Yang et al., 2025) took a similar approach as (Zhang et al. 2025) to estimate problem difficulty, and assigned a larger budget and higher gradient weights to difficult prompts. (Kong et al. 2025) estimates prompt difficulty by ag- gregating historical performance discrepancies of the problems, then adaptively selects the set of problems whose difficulty is in alignment with the current competence of the model. Other works also considered the entroyy-reward trade-off to mitigate the risk of premature convergence. (Liao) al., 2225) combined difficulty-awan reallocation with entropy-stabilizin to effectively balance efficiency and exploration. Another approach steers exploration by maximiz- ing information gain throughout the training process (Lee et al. 2024).
temperature scheduling
BACKGROUND ON RLVR
We study the prominent family of methods for RL training that employs group-based advantage estimation to stabilize learning and better utilize reward signals. This family includes Group Relative Policy Optimization (GRPO) (Shao al. 2024) and its variants, such as Dr. GRPO (Liu et al. 2025)
and RLOO (Ahmadian et al. 2024). Given a dataset of Q prompts Q = (41, ................................ 9Q the general objective function for group- group-based policy optimization methods is
16:1
J(0) Egg E on
[Apr- 3 DKL. (mo((: q. 0z || Tree(: (: 1/, ((:0
(1)
where n is the number of rollouts for each prompt, o; is the j-th rollout from policy Told, رöا1 is the number of tokens in oj, and Ty is the current policy with its learnable parameters 0. Here, DKL (To(- q, Ōj.rr) || Trer(- g, (r))
)) is the Kullback-Leibler divergence between the policy na and a reference policy Tzet. both of which are conditioned on the prompt q and the tokens generated thus far ōj.<r. We use tilde (~) to emphasize the stochastic nature of the quantities.
For prompt q, the term A/,- is the clipped surrogate at token 7 for output ōy:
A/.-- = min (re.AAr clip(ryr, 1 e, +c) Ai.:). A with (3.= Tota(oj,r (ōj,r i q, Ōj,er)
To(ō,r 11, 0,0
(2)
Notice that we momentarily omit the index y to avoid clutter. Here, ryrr is the relative ratio between current and data-generating policies; while Å - is the advantage estimator for token 7 in output oj. Let R(ō;) be the reward for output ō; prompt g, taking values of -1 (incorrect) or I (correct). Based on the whole set of n rollouts {ō there are two popular advantage estimators:
In Dr. GRPO LLu et al. 2025 A, = A,, = R(ō,) - + E. R(ōz), which uses all rollouts to compute the mean.
3

---

Published as a conference paper at ICLR 2026
In RLOO (Ahmadian et al. 2024), A, AJ,r R(ō,) -n-1 -n-IEx4 R(ōx), which excludes the j-th output when computing the mean.
Both advantage estimators are token-independent all tokens in the j-th rollout admit the same advantage Az. In this paper, we will focus on particular training regime under the next assumption. Assumption 3.1. We set the Kl. regularization term to zero, ie., 3 = 0.
Assumption 3.1 both practical and non-restrictive for the following reasons. In RLHF, reward models are only reliable near the distribution of the reference policy (Gao et al. 2023 Chen et al.) 2024 Huang al. 2024, Ramé al. 2024), which makes KI. regularization essential prevent reward hacking (Laidlaw et al. 2024] Song et al., 2024 Skalse al. (022). In contrast, our work focuses on the RLVR setting, where rewards are computed by rule-based verifiers. These verifiable rewards eliminate concerns about reward miscalibration. Indeed, recent studies in RLVR have cessfully removed the KL term while still achieving ofte--of-thearr performance (Yu et al. 2025
Liu et al. 2025).
Assumption simplifies the training objective by climinating the KL term. The objective function reduces to:
11
1 Σ min (r,, clip(rs,r, - 1,,, 2,))
J(0) E. o on
Whenever Vj.r falls outside the clipping region in direction that worsens the surrogate, min Aj. clip(ry,;, - 1 43) collapses to the clipped term and contributes no gradient. To isolate precisely when the gradient is active, we introduce the indicator
j.r = 1 - (11r > + 2 03 + 1(r,, < - = 1| 03).
Using this indicator, we define F3
Σ
|,
nune T,r and rewrite the objective as:
Tayl
J(O) EE o E
Σ
A Ag
A)((ūx))r3
n
The next section studies the gradient variance of J.
4 ANALYSIS FOR GRADIENT VARIANCE
In this section, we analyze the variance of the gradient estimator arising from sampling rollouts in RLVR algorithms such as GRPO and RLOO. Each update step combines two types of data: previ- ously collected rollouts from past batches (off-policy and newly generated rollouts for the current batch of prompts B (on-policy). However, as discussed the subsequent Section our research objective is determine how many rollouts should be allocated to the prompts in B. This alloca- tion decision influences only the on-policy component of the gradient. The off off-policy contributions, while present in the overall update, are determined entirely by past data and therefore remain un- affected by the number of new rollouts we choose to sample. Consequently, to understand how allocation impacts gradient variance, it is both natural and sufficient isolate the variance arising from the on-policy rollouts generated by the current policy тT. For these on-policy samples, the behavior and target policies coincide 7oid me, hence fj
The gradient contribution of these on-policy rollouts is:
18 Vo log no (6 0j,zz)
Jo (8) = EyE F
A)((oz
(4)
n
H(())
Above, Hō,;) is the average log-likelihoul gradient, where the average is taken over all tokens in the j-th rollout. Consider specific prompt g and the rollouts {ōx]. the contribution of y the
4

---

Published as a conference paper at ICLR 2026
calculation of the sample gradient is 1. A and we omit the subscript avoid clutter. This quantity is random vector because (0₃) random vector. To make the variance analysis mathematically tractable while accurately proxying the scale of the parameter updates, we will study the L2 norm of this gradient gradient contribution. To this end, we are interested in the (univariate) random variable:
G a j-1 A)((o=))11H(0))I
To simplify the notation, we define the random variables R2 R(āā) and 2, - ||H(0))]22 for all j. We first consider the Dr. GRPO case. The gradient G has the specifie form:
غ -, Σ -= Pi, 1z.
To have a rigorous analysis of the variance of G, we make the following assumption explicitly. Assumption 4.1. (i) R1...., Rm are independent and identically distributed (i.i.d)) copies of R, and ZI...., ,,,n are also i..d copies of Z,
(ii) {2,} and { are uncorrelated up to recond-orded Cov 2,) = 0 for any (k, and Cov (Rt Ryy ZzZz) ) = for any (,,j,,,j'))
Assumption 4.1 is realistic in common settings: given the same prompt and fixed sampling proce- dure, different rollouts are independent samples from the same distribution тy. Thus, it is reasonable to assume that }oj} are i.i.d., which induces Assumption 4. i)). Assumption 4.1 needs further justification because for the j-th rollout, the reward Rg may be correlated with the average gradient Zy. However, have strong reasons believe that it holds because R is Bernoulli distribu- tion, and Z; aggregates variations both over the number of tokens (from the definition of H (ō,) )) and across the high-dimensional parameter space (from (o;)ll). Empirically, we include in Ap- pendix B statistical test to support our assumption.
The next result establishes the variance for the Dr. GRPO case.
Proposition 4.2 (Dr. GRPO gradient variance). Consider a prompt with binary reward R(ōş) E (1,-1) with (P(((ū;) 1) = p. If d'Assumption' holds and the variance of the projected gradient Z 2, the variance of the per-prompt projected Dr. GRPO gradient estimator with n rollouts
Var(G) = (n
40 202p(11 ( p-)
n²
We now switch gears the RLOO case. The RLOO gradient Ö has the specific form:
R
Ra) Rz)
Proposition 4.3 (RLOO gradient variance). Consider prompt with binary reward R(ō,) {1. -1) with P(R(O)) = 1) = If Asssmption holls and the variance of the projected gradient Z is oz the variance of the per-prompt projected RLOO gradient estimator with n rollouts is
(ar(G)) n 40 - pp).
PREDICTIVE ROLLOUT ALLOCATION STRATEGY
Consider specific iteration when we have drawn a mini-batch B, from the set of training prompts. indicate that the gradient variance for prompt depends the number of rollouts. Consequently, a uniform allocation of rollouts for every prompt could be inefficient. Section reveals that the per-prompt gradient variance depends the success probability Pg. which the probability that model 6, answers prompt q correctly. However, this probability is not observ- able ex ante without performing rollouts, and need to resort estimate p, to make allocation
Propositions 4.2 4.3

---

Published as a conference paper at ICLR 2026
decisions. Building estimator for the success probability is challenging for at least two reasons: First, the success probability is, unfortunately, not static: it depends on the model weights, which evolve after every training iteration. As the weights updated, the distribution changes, and consequently, the success probability drifts. Second, prompt embeddings may not contain sufficiently informative signal for parametric classifiers.
the outputs
To improve rollout efficiency, we propose VIP, the Variance-Informed Predictive allocation strategy, which minimizes the minibatch gradient variance by allocating different number of rollouts {m,) for each prompt in the minibatch. The complete workflow of VIP, from prediction to optimized roll- allocation, is illustrated in Figure [] VIP comprises two main components: (i) nonparametric Gaussian process model for predicting the success probability of the current model on each training prompt (green boxes), and (ii) an optimization model for making optimal allocation decisions given the computing budget (blue box). At the heginning of iteration 1, we first predict the success prob- ability for all q B, as described in Section [.1 The probability estimates serve as input to our optimization framework for allocating rollouts across prompts in Section 5.2
(B,)
Eaeli Budget allocation |Section 5.2)
Success probability belief
Success probability B,
m2 Cendone Posterior update (Section 5.1)
Repeat for iteration
2
B
Mini-batch schedule
G2 52 .... Sta
Roll-outs generation
Gradient update
Talre Final model
Base model
Current model
The process starts with an initial belief over prompt success probabilities. At each step t, a mini-batch B, selected, and the belief function m²(+) predicts the success probabilities of the prompts in B, A budget allocation module assigns rollout budgets {mg]. rollouts are generated, and the resulting data updates the model and beliefs. Repeated for T steps, this yields a fine-tuned model Tor+1 with improved performance and efficient rollout usage.
Figure 1:
5.1 GP PRIOR AND RECURSIVE POSTERIOR UPDATE
Given the training prompts Q {4 ........94... :90 we denote their embeddings as D { At every iteration the success probability of the current model on prompt q is modeled using sigmoid link function on the latent value ge (Ir,):
Pq. sigmoid(g.Ez..) = 1/[1 exp(-9: E (0,1).
where St RRd R latent function over prompt embeddings. Because gr is real-valued, is simpler to place Gaussian process on 9t- Toward this goal, we set where m, is the mean function and K. is a radial basis function (RBF) kernel with bandwidth 0: K(x, x') exp(- x' (2)))).
(P.m,(-)..C(( (.(-,))..
Initialization. At t this gives 91 (D) (0, Σ) where Σ K(D, D) is the kernel matrix over all prompts.
1,
zero-mean prior 91 GP(O, K.). Over the dataset D = {
Prediction. At iteration f, the prior m, is used to predict p..: = sigmoid (m (Iz)) for E B,. These predicted values will be sent to the optimization problem to compute the rollout allocation.
Sequential updates. At iteration t 2 1, the latent values for all prompts are captured by a random vector [g] (z1)...., (.....9((()))) (IQ)) ~ N((m, E). For E B,, we observe ny rollouts and rewards Rgg E {-1,1) for ,,..., Then, we compute the clipped average:
Mg.
R2
Rig
Rag [-1,1 p., = clip
R
e, -)) (c,
Thg
2
which induces an observation for the latent value Ig.- = sigmoid 1 (D.,.) E R for E B, Clipping necessary here to avoid the situation when R₁ = -1 or 1, which leads to infinite values for the latent variable. The collection of these latent values is denoted 9v,- Let B; be the complement set

---

Published as a conference paper at ICLR 2026
containing all prompts that nor in the mini-batch Be. We can partition the vector and the covariance matrix into the block form:
Mr,8. mt,B5]
B. M8,B; EBpB,
my
Σ
the posterior over unqueried prompts at iteration t 90,15; 08, ~ NN(mm Σn) with
mi. = M4,8 + B LB. (ūB. m,,B.), E' = E EBB Lg,8, E,,
Next-step prior. The prior mean at iterate i is updated into the posterior mean as follows: we m++1 (Ig) = Dg.tt if E B, and set m4+1 (Igg) = mi (Ing) E Bi. This posterior mean m will serve as the prior in iteration + 1.
5.2 ADAPTIVE BUDGET ALLOCATION FOR GRADIENT VARIANCE MINIMIZATION
Consider mini- B, of B prompts, and every prompt B, has a predicted success probability Pg under the GP model from Section 5.1 We now focus on deciding the number of rollouts {mg) assigned to each prompt in this batch B, under hard constraint of total budget of C rollouts. Additionally, we impose that the number of rollouts should be between a lower bound and an upper bound U: if the number of rollouts is small, it is unlikely obtain discriminative reward signals, while large number of rollouts may lead to overfitting, For a meaningful setting, we require 2 3, and assume that BL C S BU.
Our objective is to minimize the sum of the gradient variance induced by prompts in the mini-batch B, This problem can be formulated as an integer optimization problem:
min {En 9EB. Var(GG)
Σ
n4 = C, ng E [L,L+1, U} Ay E B.
(5)
The variance Var(C,)) is likely a nonlinear function of the rollout allocation Vig and (5) becomes a nonlinear integer optimization problem. To tackle this problem, we will first solve its continuous relaxation and then apply heuristic rounding algorithm.
Relaxed Solution for Budget Allocation. Proposition 4.2 provides the per-prompt gradient vari- ance Var(Gg) for Dr. GRPO. By defining ag - 1402,0000 p.) for every E Br, the continuous relaxation problem (5) for Dr. GRPO
min Σ
Og
flg n
Σ LG
qEB, myy= C, LS SU ng EEREEB.
(6)
The next theorem asserts a computationally efficient method to solve 6
Theorem 5.1 (Continuous allocation, Dr. GRPO). For each E Br, let n be the function:
if S 0g 0
U-2
(2(
the unique solution to À ag
nn-2 no
L-2 if U-2 <> < ag
T,
if ag 1
BL < C BU, the algebraic equation E, (A() = C has a unique solution X². Then the unique minimizer of 6 is given by n ny (X*) for all q. Moreover, X* can be found by bisection.
Similarly, for the RLOO case, we can leverage Proposition 4.3 to define the same parameters ag A 202,20 P. (1 P.)) for E B. The continuous relaxation of 5 for RLOO is
4 40%
min Σ
GEB Og
Σ
9EB, n4y C, L ng S U, ng ERREEB,
(8)
nig
We solve 8 efficiently thanks to the next result.

---

Published as a conference paper at ICLR 2026
Theorem 5.2 (Continuous allocation, RLOO). For each q Bi, let ny be the function:
U
if = a - 1)
(2)2)=
1+ V fa,/(U 11) <> X < ag/ 1)
(9)
if> 2 (L --1-11- 1)²
If BT. S C S BU, the algebraic equation Eg (x*) = C has a unique solution X Then the unique minimizer of 8 is given by n. n. (X*) for all q. Moreover, X can be found by bisection.
Heuristic Rounding. First, ni is rounded down to [ng]] Let (n) denote the per-prompt objective: fy(n) = ay 7 for Dr. GRPO and (n) Oq x-I for RLOO. The remaining budget then distributed iteratively to prompts with the largest decrease in fg if additional rollout is allocated.
This process continues until the total budget C' is exhausted, while ensuring that the per-prompt bounds, S fgg S U. are satisfied. The procedure is detailed in Appendix D
NUMERICAL EXPERIMENTS
We now showcase the empirical benefit of our VIP framework on the mathematical reasoning task and the -uggeened reasoning task. The common setup for both tasks is as follows: we encode each prompt q into 384-dimensionil vector 24 using 1111-MnniM---6-- we pre-compute and cache the pairwise Fuclidean distances between all prompt pairs, making the runtime overhead negligible. We use median heuristic set the bandwidth h of the kernel K.. We also assume that Z, has the same variances over all q when we compute the allocation; we support this assumption with a statistical test presented in Appendix B.3 We train all models for two epochs under two total rollout budgets, 8 x Q and 16 Q, where Q is the dataset size. We integrate VIP on top of two group-relative policy optimization baselines, RLOO and Dr. GRPO. implemented using VERL (Sheng al., 2024) for math experiments and following (Chen al. 2025b; Jin al.) (025) for tool-augmented tasks. We closely follow the default hyperparameter settings used in RL. training.
Before training,
Mathematical Reasoning Task. For mathematical reasoning, we train on DAPO-MATH- 17k (Yu et al.] (2025) and evaluate on AIME2024 and AIME2025. We evaluate VIP by com- paring Dr. GRPO and RLOO, each with and without our adaptive rollout allocation method. We experiment with three backbone LMs (Qwen2. 5-22..5Mat 5-Mathh1..555 5B, 5-Mathh--Mahh-77 and Llama-3 3. 2-3---3---- 22-BBIInSE Instrrcc),, on AIME24/25, under two rollout-budget settings C {8 x Q,16 16 x Q}. We report Pass 32, Mean @ 32, and Maj@ 32 metrics, capturing the accuracy and consensus of multiple rollouts. We summarize the results in Table Overall, adding VIP yields con- sistent improvements on Pass@ 32 and Mean @ 32 across all three base models and both budgets. For example, on Qwen2.5 5-tthh---15-55 at 8 x Q RLO0+ improves Pass @2 by + +12.3 and Mean (tram@31 @2 by +6.3 points over RLOO. Similar patterns hold for -lama-3.2-3B--Instee
and Qwen2.5-Math-7B.
We see that the relative performance gain from VIP is larger for the 1.5B and 3B models than for the 7B model. This suggests that VIP's budget-aware variance reduction may particularly help weaker backbones that otherwise underutilize the rollout budget.
We implement our allocation strategy teach LMs to use retrieval tool during generation. We follow [hen et al.] (2025b) and train on MuSiQue (19, ,388 prompts) (Trivedi et al. 2022), evaluating on the Bamboogle benchmark (Press et al. 2022) and MuSiQue test set. During training we use int www.llltteeebbaaaeeeeeeeeee 2022) for the retrieval model. We choose Qwen2. 5 IB-Instruct as our base model for this experiment. We use Precision @ and @ to evaluate retrieval quality, and Exact Match (EM) for final generation correctness. We summarize the results in Table
Tool-Augeeteed Reasoning Task.
embeddings (Wang et al.,
Under a fixed rollout budget, VIP improves both answer accuracy and retrieval quality in coupled manner. On Bamboogle, Dr. GRPO.vIP raises EM from 20 to 23.2 while simultaneously lifting Fl @ 11///Pecciiio @5 by 10.00/11--00 0.060, and RLOO.vr vIP shows larger absolute gains (EM 10.4- 17.6, F 0.190 + 0.264, Precision @5 0.225 - 0.294). The parallel improvements in F1 @5 and Precision 5 suggest fewer false positives and better ranking of useful contexts, while EM gains indicate that retrieved evidence is more reliably integrated into final answers. These patterns support VIP as sample-efficient, domain-agnostic mechanism for togl-nugee reasoning.
8

---

Published as a conference paper at ICLR 2026
Table 1: Percentage results on AIME24 and AIME25. The upper block total rollout budget
of C = 8 x Q, and the lower block uses C = 16 x Q. For each pair (Dr. GRPO vs Dr. GRPO.vIP and RLOO vs RLO0+vip). higher values are highlighted green.
AIME24
AIME25
Model
Method
Pass
M2
Maj@
Pass
Mcan 32
Maj@
11.26
24.03
GRPO+VIP
33.63
9.167
15.5
29.82
6.14
10.76
Owen2.5-Math-I.5 1.50--1..B.
RLOO
18.29
6.88
15.90
2.29
RLOO+VIP
30.55
9.68
13.65
26.54
6.35
13.72
Qwen2.5-Mah-77
GRPO+VIP
58.98
38.15
36.08
10.0
19.74
RLO0
53.0
18.0
24.0
45.0
11.0
16.0
RLOO+VIP
58.0
20.0
35.0
34.0
11.0
18.0
24.68
10.62
4.28
GRPO+VIP
17.21
9.37
2aama-3.23B--nnstrur
RLOO
28.84
8.229
13.95
9.157
0.5208
0.3633
RLOO+VIP
35.59
9.479
19.0
9.99
0.625
0.61
GRPO
23.96
13.64
28.21
5.83
GRPO+VIP
15.01
33.05
8.43
13.77
Qweu2.5-Math-I33
22.0
GRPO
52.0
19.0
35.0
36.0
10.0
20.0
GRPO+VIP
57.0
20.0
33.0
36.0
13.0
21.0
Qwen2.5-Mat-7B
RLOO+VIP
35,59
38.32
10.31
GRPO
23.26
6.35
10.09
5.49
0.63
1.31
GRPO+VIP
10.67
IJamn-3 3.2mm.33..333 22-3B-IInstunn
RLOO
1.74
Table 2: Performance on Bamboogle and MuSiQue. Green cells indicate improvements of the +VIP variant over its base method.
Bamboogle
MuSiQue
Method
EM
F165
Precision@15
EM
F105
Precision
0.282
0.126
Dr. GRPO+VIP
23.2
0.333
0.353
10.5
0.214
0.225
RLOO
0.190
0.225
8.5
0.178
0.179
0.211
Table 3: Ablation study on AIME24 and AIME25. All values are percentages. For each metric, the highest value across methods is highlighted in green.
AIME24
AIMEZ5
Method
Pass @ 32
Mcan 32
Maj@32
Pass@ 32
Mcan@
Maj@32
2.29
RLOO+GG++NVERRE ACC
24.61
7.90
19.10
3.33
RLO0++P++NVERRE VAR
25.83
4.90
10.90
21.11
2.08
3.79
ALL
29.90
6.97
14.79
24.85
5.20
12.12
RIPO+VIP
30.55
9.68
15.65
26.54
6.35
13.72

---

Published as a conference paper at ICLR 2026
Ablation Studies. We dissect VIP by ablating its two core components: (i) the variance predictor and (ii) the adaptive budget allocator. We replace the Gaussian process predictor (Section 5.1) with Ridge Regression baseline and substitute the adaptive allocator (Section (.2) with two heuristies,, Inverse Accuracy and Inverse Variance (details in the Appendix). Ablation results on Qwen2.5- Math-1.5B are summarized in T RLOO+ VIP achieves the hest performance across metries, outperforming every ablated variants. Among components, adaptive allocation is the most critical: replacing with heuristics yields substantial drops on all metrics. Substituting the Gaussian pro- cess with Ridge Regression produces milder but consistent degradations, showing that calibrated uncertainty further boosts allocation effectiveness. Overall, these results confirm that VIP benefits primarily from variance-aware budget allocation.
Runtime comparison. We report the average runtime of each component of our method during a single gradient step in Table 4 The total computational overhead is extremely small: our method adds only 1.12% and 0.83% to the overall RI. training time for the 1.5B par-maraeterr and 7B-parameter models, respectively, when including computations cached before training. When excluding cached computations, the overhead further reduces to 0.79% and 0.58%. Because mrowel-forward and rollout costs dominate at larger scales, this relative overhead decreases as model size grows.
Table 4: Wall-clock runtime of core computational components and model-specific operations for Qwen2.5-Math-1.57 and Qwen2.5-Math-77 measured on single GPU.
Model
Operation
Time (s)
Kernel matrix computation (A (Algorithm 1)^
10.652
Gaussian process training and prediction (A (Algorithm)
0.745
Rollout allocation (Section 5.2 Algorithm
29.956
1wen2.5-Math-1.58
Rollout sampling
2781.2
Owen2.5-Mathh11.
Log probability computation Policy update
627.68
Qwen2.5-Math-1.5B
263.9
Swen2.5-Math-2
Rollout sampling
3134.4
Qwen2.5-Math-7
Log probability computation Policy update
1388.8
Qwen2.5-
713.5
*Cached before training.
Success probability prediction quality. To evaluate the quality of our Gaussian Process predic- tor, we construct time-series dataset by training Qwen2.5-Math- 1.5B and (wwe2.5-Math-- with RLOO for 55 gradient steps and logging per-prompt success probability at every step. Because the policy changes after each update, the underlying success probabilities drift over time, requiring any predictor to adapt to this non-stationarity. We compare VIP's GP predictor against two baselines, Moving Average and Ridge Regression, using 1024 most recent samples to predict the next mini- batch's ' success probability. Figure 3 reports the MAE across steps. While the Moving Average and Ridge Regression baselines struggle to track rapid changes in model's behavior, the GP main- tains consistently lower MAE throughout training for both model sizes. This indicates that the GP provides a more accurate and adaptive estimator under the non-stationary dynamics of RL training.
CONCLUSION
This paper introduced Bariance-Informe Predictive allocation, framework for minimizing gradi- ent variance in group-based reinforcement learning. By combining Gaussian process-based predic- tions of prompt success probabilities with an optimization approach to rollout allocation, VIP uses limited sampling budgets more efficiently. Our experiments on mathematical reasoning and tool- augmented benchmarks demonstrated consistent gains over heuristic or uniform strategies. VIP step toward more adaptive, resource-efficient, and principled training pipelines for large language models. Future work will explore its integration with non- non-verifiable or noisy rewards, opening av- enues for its application in RLHF and other alignment paradigms.
10

---

Published as a conference paper at ICLR 2026
Ethics Statement. All authors read and agree adhere the ICLR Code of Ethics throughout the development, submission, and potential publication of this work. Our research does not involve human subjects, personal data, or any sensitive information. All datasets used are publicly available and do not contain personally identifiable information. We have taken care to ensure that our meth- ods do not introduce amplify bias, discrimination, unfaimeess, as the reward signals in RLVR are determined by rule-based verifiers rather than subjective human judgment. We release all code and experimental protocols to promote transparency and reproducibility. We potential confticts of interest, legal compliance issues, research integrity concerns associated with this work.
aware any
Reproducibility Statement. We have made every effort to ensure that our results are reproducible. All of the models, algorithms, and experiments described the paper are accompanied by detailed explanations in the main text and appendix. To further support reproducibility, we have provided an anonymized repository containing the full source code, along with instructions for running the experiments and replicating our results. The datasets used are publicly available, and we include clear descriptions of any preprocessing steps in the appendix. For all theoretical results, we have stated our assumptions explicitly and included complete proofs in the supplementary material.
LLM Usage Statement. In preparing this paper, we used large language models as general-purpose purpose tools for tasks such proofreading, rephrasing, and checking the clarity of some sections. The research ideas, experiments, analysis, and the main writing were carried out by the authors.
Acknowledgments. Viet Anh Nguyen gratefully acknowledges the support from the CUHK's Improvement on Competitiveness in Hiring New Faculties Funding Scheme, UGC ECS Grant 24210924, and UGC GRF Grant 14208625. The authors would like the thank Dongxuan Zhu and Hongzheng Yang for their helpful discussion regarding Resource Allocation and Reinforcement Learning.
REFERENCES
Arash Ahmadian, Chris Cremer, Matthias Gallé, Marzieh Fadace, Julia Kreutzer, Olivier Pietquin, Ahmet Üstün, and Sara Hooker. Back to basics: Revisiting reinforce style optimization for learn- ing from human feedback in LLMs. arXiv preprint arXiv:2402.14740 2024.
Jack Chen, Fazhong Liu, Naruto Liu, Yuhan Luo, Erqu Qin, Harry Zheng, Tian Dong, Haojin Zhu, Yan Meng, and Xiao Wang. Step-wise adaptive integration of supervised fine-tuning and rein- forcement learning for task-specific 1lms. arXiv preprint arXiv:2505. 13026, 2025a.
Lichang Chen, Chen Zhu, Davit Soselia, Jiuhai Chen, Tianyi Zhou, Tom Goldstein, Heng Huang, Mohammad Shoeybi, and Bryan Catanzaro. Odin: Disentangled reward mitigates hacking in rlhf. arXiv preprint arXiv:2402.07319 2024.
Mingyang Chen, Tianpeng Li. Haoze Sun, Yijie Zhou, Chenzheng Zhu, Haofen Wang. Jeff Z Pan, Wen Zhang, Huajun Chen, Fan Yang, et al. Learning to reason with search for LLMs via rein- forcement learning. arXiv preprint arXiv:2503. 19470, 2025b.
Xidong Feng, Ziyu Wan, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17179 2023.
Yuqian Fu, Tinghong Chen, Jiajun Chai, Xihuai Wang, Songjun Tu, Guojun Yin, Wei Lin, Qichao Zhang, Yuanheng Zhu, and Dongbin Zhao. Srft: A single-stage method with supervised and reinforcement fine-tuning for reasoning. arXiv preprint arXiv:2506.191: 19767, 2025.
Leo Gao, John Schulman, and Jacob Hilton. Scaling laws for reward model overoptimization. In International Conference Machine Learning, pp. 10835-10866. PMLR, 2023.
Audrey Huang, Wenhao Zhan, Tengyang Xie, Jason D Lee, Wen Sun, Akshay Krishnamurthy, and Dylan J Foster. Correcting the mythos of kl-regularization: Direct alignment without overopti- mization via chi-squared preference optimization. arXiv preprint 2tth:2407.13999 2024.

---

Published as a conference paper at ICLR 2026
Jiajie Jin, Yutao Zhu, Zhicheng Dou, Guanting Dong, Xinyu Yang. Chenghao Zhang, Tong Zhao, Zhao Yang, and Ji-Rong Wen. Flashrag: A modular toolkit for efficient retrieval-augmen -uggented generation research. In Companion Proceedings of the ACM Web Conference 2025, pp. 737- 740, 2025.
Deyang Kong, Qi Guo, Xiangyu Xi, Wei Wang, Jingang Wang, Xunliang Cai, Shikun Zhang, and Wei Ye. Rethinking the sampling criteria in reinforcement learning for Ilm reasoning: A competence-difficlly alignment perspective. arXiv preprint arXiv:2505. /7652, 2025.
Cassidy Laidlaw, Shivam Singhal, and Anca Dragan. Correlated proxies: new definition and improved mitigation for reward hacking. arXiv preprint arXiv:2403.03/85, 2024.
Min Lee, Jinsu Kim, Seongmin Park, Young Choi, Sungmin Jung, and Sangjun Han. MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximization. arXiv preprint arXiv:2412. 12098, 2024.
Mengqi Liao, Xiangyu Xi, Chen Ruinian, Jia Leng, Yangen Hu, Ke Zeng, Shuai Liu, and Huaiyu Wan. Enhancing efficiency and exploration in reinforcement learning for llms. In Proceedings of the 2025 Conference Empirical Methods in Natural Language Processing, pp. 1451-1463, 2025.
Zhihang Lin, Mingbao Lin, Yuan Xie, and Rongrong Ji. Cppo: Accelerating the training of group relative policy optimization reasoning models. arXiv preprint 22Xi:22503.23342, 2025.
Zichen Liu, Changyu Chen, Wenjun Li, Penghui Qi. Tianyu Pang, Chao Du, Wee Sun Lee, and Min Lin. Understanding rl-zero-like training: A critical perspective. arXiv preprint 2003::2003.2078., 2025.
Bao Nguyen. Hieu Trung Nguyen, Ruifeng She, Xiaojin Fu, and Viet Anh Nguyen. Reasoning planning for language models. In The Thirty-ninth Annual Conference Neural Information Processing Systems, 2025a.
Hieu Trung Nguyen, Bao Nguyen, and Viet Anh Nguyen. Structured pruning for diverse best-of-n reasoning optimization. In Findings of the Association for Computational Linguistics: ACL 2025, pp. 2391 2-922 2025b.
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A Smith, and Mike Lewis. Measuring and narrowing the compositionality gap in language models. arXiv preprint 10003:2200.03350, 2022.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. vol- ume 36, pp. 13728-537411 2023.
Alexandre Ramé, Nino Vieillard, Léonard Hussenot, Robert Dadashi, Geoffrey Cideron, Olivier Bachem, and Johan Ferret. Warm: On the benefits of weight averaged reward models. arXiv preprint arXiv:2401. 2024.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pp. 1889-1897. PMLR, 2015.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song. Xiao Bi. Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathemati- cal reasoning in open language models. arXiv preprint arXiv:2402.03300 2024.
Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng, Haibin Lin, and Chuan Wu. Hybridflow: A flexible and efficient RLHF framework. arXiv preprint arXiv: 2409. 19256, 2024.
Jour Skalse, Nikolaus Howe, Dmitrii Krasheninnikov, and David Krueger. Defining and character- izing reward gaming. Advances in Neural Information Processing Systems, 35:9460-9447 2022.
12

---

Published as a conference paper at ICLR 2026
Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute optimally can be more effective than scaling model parameters. arXiv preprint 24Xx::24088.331444 2024.
Yuda Song, Gokul Swamy, Aarti Singh, Bagnell, and Wen Sun. The importance of online data: Understanding preference fine-tuning via coverage. Advances in Neural Information Processing Systems, 37:1 2223322222220, 2024.
Yifan Sun, Jingyan Shen, Yibin Wang, Tianyu Chen, Zhendong Wang, Mingyuan Zhou, and Huan Zhang. Improving data efficiency for IIm reinforcement fine-tuning through difficulty-taggeted online data selection and rollout replay. arXiv preprint 2xXi::5506.03166 2025.
Yuxuan Tong, Xiwen Zhang, Rui Wang, Ruidong Wu, and Junxian He. Dart-math: Difficulty-awan rejection tuning for mathematical problem-solving. volume 37, pp. 7821-7846, 2024.
Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. Musique Multihop questions via single-hop question composition. Transactions of the Association for Computational Lingnistics, 10:539-554, 2022.
Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang. Daxin Jiang, Rangan Ma- jumder, and Furu Wei. Text embeddings by weakly-supervised contrastive pre-training. arXiv preprint arXiv:2212.03533. 2022.
Yixuan Even Xu, Yash Savani, Fei Fang, and J Zico Kolter. Not all rollouts are useful: Down- sampling rollouts in Ilm reinforcement learning. arXiv preprint arXiv:2504. 13818, 2025.
Zhicheng Yang, Zhijiang Guo, Yinya Huang, Yongxin Wang, Dongchun Xie, Yiwei Wang, Xiaodan Liang, and Jing Tang. Depth-breadth synergy in rlvr: Unlocking Ilm reasoning gains with adaptive exploration. arXiv preprint arXiv:2508. 13755, 2025.
Qiying Yu, Zheng Zhang, Ruofei Zhu, Yufeng Yuan, Xiaochen Zuo, Yu Yue, Weinan Dai, Tiantian Fan, Gaohong Liu, Lingjun Liu, et al. Dapo: An open-source LLM reinforcement learning system at scale. arXiv preprint 2503. 2025.
Ruiqi Zhang, Daman Arora, Song Mei, and Andrea Zanette. Speed-rl: Faster training of reasoning models via online curriculum learning. arXiv preprint arXiv:2506.09016, 2025.
Haizhong Zheng, Yang Zhou, Brian R Bartoldson, Bhavya Kailkhura, Fan Lai. Jiawei Zhao, and Beidi Chen. Act only when pays: Efficient reinforcement learning for Ilm reasoning via selective rollouts. arXiv preprint ar arXiv:2506.021777 2025.
13

---

Published as a conference paper at ICLR 2026
A PROOFS OF TECHNICAL RESULTS
A.1 PROOFS OF SECTION 4
Proof of Proposition 4.2
We recall the expression of Ggi:
G
R
1
Σ Rz)
11
π
j=1
k=1
The expectation of G is:
1 Σ
E E|G = E
RR
71 k=
1=1
- Σ N34
k=
1
E 2g
k= k=1
E - =
(by Assumption 4.1 i)).
The variance of Gg is:
Gg)
G[G2] 9)
(T((G,))
E(G 7)
0
B[G.]
27
n2
1
E
R
n²
n j=1
j=
2
2
E
Σ
RyZ,
+
1
R
2
Σ
Rz
ΣXRRZ RaZs
n2
n
33
j=1k=1
j=1k=1 k=1
27
E
RyZ,
+
R
-
E
2
R
Σ> Razy
2
n
n
j=1
Arm
J=1
yim 1 Am
AC2
ACa
14

---

Published as a conference paper at ICLR 2026
Next compute each term. We find for C1:
27
27
1
C1
E
Z
E
Σ
Zg
11
n2
j=1
j=l
E
R3
+2
Σ
R
n
15j<kgn
E
[323
+2
Σ
E
RRiZZ
122
1Sicken
Σ IE
12
+2 Σ
E
R [5
E Pi 2in]
(independence between j and k)
122
15jckEn
1
nB 12
+n(n 1)(B((2))2)
(identically distributed)
n²
1
RR 22
+ (n (n-1) (E(2
n
n
1 EERR
1u2 2 + +02)+ + n 1- u (B(
=E -z + - 022) + (E]R)) ( n - 12)
1 2
We next compute for C2:
27
1
C
=
E
RsZy
Zi
E
Ru 25Z0
4
We can decompose the quadruple sum by whether the indices are equal or not. There are four index-pattern types:
When A: = K and j = jí: there are n² such terms, each term is 1T = (u² (E
Total contribution to C2 is
Ti n + 1RR
When = k and j + jr: there are nn 1) such terms. For any fixed and distinct j.j'. L = E1 Zp] = )² Total contribution to C2 is
T, n n 2 [(TP).
When A + k and j = j/: there are n²² - 1) such terms. For distinct k, W, ElRi 22 ERR [E[2 = (42 + o (E) Total contribution to C2 is
T3 = n - 1 + +
When 1: * k and j # J:: there are n²(nn - 1)2 such terms. For all indices different, Elit Ry 2, = (B(R))2 Total contribution to C₂ is
T4 T = nn - (m[)))²
15

---

Published as a conference paper at ICLR 2026
Therefore, we find
C
nd n (Ti + T- + +3+
1 ( + -3)
nd
+ nn - 1)(13)))))))) +03) -
112 +
02
- 1 n-
+ (B
1z +
n2 0%
n²
We next compute for C3:
C
E
2
2g
ΣΣ
n
n
Ry
2
E
Σ
n
ΣΣ>X
12
Σ
1
Ra
32
n
s'=lk=
j=1"==kk1
We can decompose the triplet sum by whether the indies are equal or not. There are five index- pattern types:
When = k = J¹: there are such terms. For each j. E|R32]] = E[R = (w3 +
a2 BB R2). Total contribution:
Ti = n(pž + E
When j = l + j': there are nn - 1) such terms. For each j and j' # J. E[R3,,2,1 =
E|R]|E[Z, =
B[2y, = || 1 Total contribution is
T: = n 1)
. When j= j + k: there are n(n 1) such terms. For each j and K # J. RlR
E|R = (02 + o (E 2 Total contribution is
T3 = n(n - 1) + (E)
When j + j: there are nn - 1) such terms. For each and h + J. Rx
EjR |1 = (E Total contribution is
T4 n (F(R)?
When j.j'. 1s are all distinct: there are n - 1) 2) such terms. For each triple of distinct indices, 1R 2, Rs 2x1 )2 Total contribution is
T3 = nnn - 1) - 2) (
Therefore, we find
2 C
(Ti + T: +T T4 + Ts)
n
2
n(u2 + 22) n(n - (0m-1)T((PP) 1
3
+ +n(n 1)(13 + oz)) (E(R)
nnnn 1)p2 (B[R)
+ +n(n 1) 2) (B(Ā)
2 2
2
2n
2 2
2n 2)
E(P2]
uzz +
n2
0z
(E
n²
oz
16

---

Published as a conference paper at ICLR 2026
Group terms with E|R²] and (E[R)) coefficients:
C + - C3 = C
1 12 + 00
+
22
+
-
(2 uz +
n² 0z
2
2n 2 nn 022 ]
+ (B[
n
n
u1 +
72
11z
+
T1
n2
0
-
( 2n 2
n
112
+
We simplify each bracket to obtain:
Var(C,) = C1 +2 C23 n 1 2
n² [ [ - (B(R))))
= n2 12-11 2 n2 R.
For a given prompt, Rt takes 1 with probability p and -1 with probability 1 p, leading to its variance of 4p(1 - p). We obtain the final variance of the per- per-prompt gradient estimator:
Var(a,) = 03 1)
4p(1 p)-
n²
This completes the proof.
Proof of Proposition 4.3 We recall the expression of G.z:
G
R2
1
Rk
Zs-
71 j=1
n1
The expectation of Gg is:
n
n
B[G,] =
R
R
Z
n j=1
n2
1
kfj
E
R2 25
2
nnn 1)
j=1
j=1
k=1
Σ 21 -
Bj
nin - 1)
1=1
= -[ - E(
(by Assumption 4.1
0.
The variance of G₂ is:
Var(G,)
E[G2] 4 - (I = =E[GA] - B[G
E
1 12
Zz
1
Σ Zi
n
n j=1
nnn 1)
kzj
2
2
E
Σ
Rz
n Σ
12
Ru 2g
2
Σ
12
N ΣΣ |ー
Rac3
11
n² (n 1)2
ne(n 1)
1=1
1=1 k+)
/=1
2
27
E
Σ
R3
+E
1
Σ
12
RaZi
EE
2
n
Rzgy
Σ
Ro
2
1i2 n2(mn 1)2
112 122(n (n - 1)
j=1
j=1
j=1
20
402
17

---

Published as a conference paper at ICLR 2026
The first term C1 is already computed in the proof of Proposition
4.2 and we have:
G =
= _112 112
+
1 -02) +
(
n (2
n
n
Next, we consider the term Cz:
27
1
C2 E
RR Zn
n1 (1 1)2
27
1
Σ Σ
Rs
->
n Σ j=1
n2 1)a
-
k=1
27
1
E
Σ>
n
n
Rsx
2
n
Re
R5
12
Rg.
2p
+
(-
n2 n2
1)2
k=1
y'=1
We can utilize the computation from the proof of Proposition 4.2 to have:
27
π
R
2
=
Pz
+
0% n²
+
(B
n 1
11
+
n 02
0%
n
n
n22
j=1
km l
]
2
>
n
R2 2/
Σ
m
-
112
2
+
n 03
2
+ (F(
(2n 2
112
+
2n 2
03
n
n
n
n²
k=1
E
2g
R2
199
1 2
uz
+
1 -
+ (E(()))
n2 (n-1
112
n2
n
n
n1
Therefore,
1
2
2
1
C22 = E[
(n 1)2 H2
2
+
(n 1)2 12
(n - 1)2
2
+
n(n - 1)202
n(n - 1)2t/ 12
n(n - 1)2 1320
+ (E(R))
(n 1) 2 +
n
2
1
02
2
12z 3
n(nn - 1) 02
2
n(n - 1) 11
(n - 1)
7
=
n²=
2n + 1
112
+
n(n- 1)2 0
n 1
+ (E( 2
T1² 2n 1
11 + n
n(n - 1) 02
nlnn - 1)2
n(nn - 1)
1
1
n 2
11z + n2n 1)
03
+ (E(R))2 2
n 12
n(n - 1) 07
n
We compute C3 as follows:
2
n Σ
12
C3 =
R2 2,
Σ
n2 (n- 1)
j=1
j'=
2
n Σ
Z
Σ
n2
n
Rr
Σ Ry
n nn 1)
j=1
1=1
j'=1
]
2
BB
Σ ΣΣ
Ra
-E E
Σ
n
n²(n
1)
1
y'=1kmm kml
18

---

Published as a conference paper at ICLR 2026
We can utilize the computation of Na C3 and n²C1 from the proof of Proposition 4.2 to have:
R2 Z5
Σ
Rr
= TR[R2] (n² + ==oz) + (E[R))² (n² - 1)12 + +n(n - -1)02)
y'=1 k=1
Σ
Z
Σ
Ry. Zy
En + nn=3) + (E(R)) - -1)2))
Plugging these terms to the computation of C's yields us:
C3 = n²(n-
E[RR (n²p² + no3) + (E)A)) (n² 1)x2 + n(n 1)02)
-[E[(E)] (1112 + +oo2) + (B (n - 1)x }
n2(n 1) 2z + (B(RR)2 2n(n - 1)
2(n² - 11)
R
- ((2-1)63
+ +0%)
n²
[ + (B(RR))
(2m
2m - 2 fzz
+ -02 2
We have:
1
n (- 02
Var( C1 C2 C3 = E[
02 (B(7))²
n
o2
(E( 2 (E(R))
02
Var (R).
For a given prompt, R takes with probability p and with probability 1 - p, leading to its variance of 4p(1 pp). We obtain the final variance of the per-prompt gradient estimator:
Var( = 0z - 4p(1 - p).
This completes the proof.
A.2 PROOFS OF SECTION 5
Proof of Theorem 5.7
For clarity and continuity, we restate problem (6) before proceeding with the
proof:
0g Tly 1
min
m2
2
BEB,
(10)
s.t.
C
Thy SU
4q B..
Let (((n,)) be the objective function of the above problem. We compute the first and second derivatives the objective function with respect to each coordinate ng:
OV
72 ag
On,
n
av Since n, 2 L 2 3. so for all g, ong feasible set.
< 0. Thus, V is decreasing with respect to each n, on the
19

---

Published as a conference paper at ICLR 2026
For the second derivatives:
QV O
2ng
6
ba $ d
0g
2 0
4q
(Since
2 L 2 3, and 0g 2 0)
On.
dng
Therefore, V is convex and decreasing in each ny the feasible set
NERB
n
gEB. Σ T4y C2 L Ln n4 S VV
Hence, the minimizer exists and is unique whenever the feasible set is nonempty BL < C BU. The Lagrangian function is
c
0)+
L where À E R, and Pgg Ug 2 0 are Lagrangian multipliers. The KKT conditions are:
0g
Bly
Σ Tlg
C + ++E Mn(L n₂) + Σ (n - U)
geB,
gEB,
9EB,
qEB,,
ng
0g n
pig + 1/g =0 =0
yq.
Mg 2 0,
1/4 2 0
dg.
Mg (2g L) 0,
Mg (n U)= =0
dq.
L L n U
dq.
Σ nl C.
gEB,
We consider three cases of ngg
For each with I. < Ry < U, the KKT stationarity condition is
fhg
== ag n
where À is the Lagrange multiplier for the sum constraint. Note that the right-hand side is decreasing in ngg.
U-2 Therefore, for each For n2 = L, the right-hand side is ag 1,2 and for ny = U, it is Ou U and any X (ag Og L-2), ). there is most one solution n, ag n
U-2
n-=2 in the interior
(I, U). If 2 ag be at bound.
S ag 2-2 there is no interior solution, and the optimum for n, must
If mg I., then By 0 and Vg 0. According the KKT condition, obtain:
L-2 X dg 1 1g 2 0g I
L-2
If ng U. then My and My 2 0. According to the KKT condition, we obtain:
-
U 2
0g
U3 14 S ag U3
For value of X, for each coordinate, the KKT solution for n, is defined as:
U
if A 0g U-2
Us
n (A)
(A)
the unique solution to Og
a U 1-2 < < 0u L-2
if ag 1
20

---

Published as a conference paper at ICLR 2026
The coupling constraint EqeB, n4 C is enforced by selecting À such that
((A)
Σ qEB,
m)(A) C.
Each (A) is non non-inoneenn non-increasing in À since ag ng= "
is decreasing and the projection preserves mono- tonicity. Consequently, S()) is also non-increasing. In particular:
As -c, m, + U. so S(-20) BU.
As A + +00, +, ()) + L. so S(+00 = -BL.
Therefore, for any feasible C' with BL SC < BU, there exists a unique such that S(\*) = Moreover, because 5 is non-increasing, finding X can be done by bisection. If C > BU or C BL. the problem is infeasible.
Proof of T'heorem 5.2 proof:
For clarity and continuity, we restate Problem g hefore proceeding with the
min
0g
nlg
gEB.
s.t.
Σ Tly C
(11)
geB,
L ng SU U
E B.
Let (((ng) be the objective function of the above problem. We compute the first and second derivatives of the objective function with respect to each coordinate ng:
0V 0g (ng 1)²
On,
Since n2 2 L 2 and ag > O, we have
< for all q. Thus, V is decreasing with respect to 8ng
0V
each mg on the feasible set. For the second derivatives:
8ºV
8²v
24g (ng - 1)3 20 Ag
On.ōng
dn?
Therefore, V is convex and decreasing in each ng on the feasible set
NERB Σn= Lsn,
E
Hence, the minimizer exists and unique whenever the feasible set is nonempty (BL S C BU). The Lagrangian function is
L Σ 0g ng
Σ nig
+
Σ
Mg - ng) +
Σ uy(ng - U)
GEB,
9EB,
9EB.
EEB.
where À E R. Mgg My
0. The KKT conditions are:
1
aq (m, 1)2
+ - Mg + M4 =0
bA
My 2 0, Vg 2
Mgg (1 L) = 0,
(n - -U) =0
DA
< ng <
DA
ng C.
gEB,
We consider three cases of ny:
21

---

Published as a conference paper at ICLR 2026
For each y with L < ny U, the KKT stationarity condition is
1 x= ag (ng - 1)2
where À the Lagrange multiplier for the sum constraint. Note that the right-hand side is decreasing in By since ny 2 3.
For n2 L. the right- side is ag -T-ITZ and for ny U, it Og 1V- Therefore, for each 1 to ag 1m X
q and any À E (ag (リ- au (I- there is one solution Bl
in the interior (L, U). If A 2 ag (I- À Og -1 there is no interior solution, and the optimum for ny must be at a bound.
If ng L, then My 2 and Vq According the KKT condition, we obtain:
a (L - 1) Mq 2 0g [L 1)2
If ni = U. then Ma = and Vy 2 0. According to the KKT condition, we obtain:
A= tgy (U - 1)2 Uq S 0g (U 1)2
For value of X, for each coordinate, the KKT solution for mg is defined as:
U
if S 0g (U 11=
(1
1 if ag 1- < < < ag IT.-13+
if IT-
The coupling constraint EgeB, ng
C is enforced by selecting À such that
S(A) = Σ (A) =C
gEB.
Each ni nī(A) (A) is non-increasing in À (since ag IIz decreasing and the projection preserves mono-
tonicity), so S(A) is also non-increasing. In particular:
As - 0o, n2, + U. so S(-20) BU.
As +00, +o0, + L, so S(+00) = BL.
Therefore, for any feasible C with BL C BU, there exists unique À such that S(A) C. C> BU or C' < BL, the problem is infeasible.
B STATISTICAL TESTS FOR SECOND-ORDER UNCORRELATION
In this section, we provide statistical tests to validate the assumptions in our paper.
B. FIRST-ORDER CORRELATION TEST VIA FISHER'S 'S METHOD
For each question g, consider the random variables R2 and 2,p with n independent observations ((Ry.j 7g.:))
Compute per-question Pearson correlation. The sample Pearson correlation for question ş is
Pg ΣØ (Ry.s - R R2) 2z)) プラ= [Rg.j R2,) Σソ=
(Zy.5 22
22

---

Published as a conference paper at ICLR 2026
where
Rg
R
2g =
Z
Compute per-question p-values. For each question q. test the null hypothesis
Ho.q Pq O.
The p-value Py is obtained directly from the standard Pearson correlation test.
Combine p-values across questions using Fisher's method. Let Q be the total number of ques- tions. Fisher's method combines the per-question p-values {p1)g=1 into single test statistic:
Q In Pa
2 Xisshrr
g=1
Under the global null hypothesis
Ho Pq = 4g. the statistic Xiisher follows chi-squared distribution with 2Q degrees of freedom:
XFrsher ~ X2Q
Global p-value and decision rule.
The global p-value for testing Ho across all questions
Palotal = Pr (x2Q 2 XFisher)
Given significance level (e.g.. 0.05), we make the following decision:
If Polobul a, reject the global null hypothesis Ho. which indicates that least of the correlations are significantly different from zero across the questions.
If Pplobal 2 a, we fail to reject Ho, which supports the hypothesis that the correlations Pa are zero for all questions at the significance level a.
We conduct the correlation test described above on benchmark of Q = 600 questions, each with n independent rollouts. For each question q, we compute the Pearson correlation between R2 and Zy. obtain the corresponding p-value Py, and aggregate across all questions using Fisher's method to compute the global p-value Pglobul-
We evaluate the policy model ne, at four checkpoints during training Qwen2. 5-Math-1. 5B, corresponding to 0.0, 0.5, 1.0 epochs. At each checkpoint, we report the resulting Pylohal values in Table[3] Since all global p-values exceed the chosen significance level a 0.05, we not reject the null hypothesis, which supports assumption that the correlations Py are zero across all questions.
Epoch
Global p-value
2, (,,
0.0
0.7322
0.5
0.1
1.0
0.2186
Table 5: Global p-values (Petoba) across training epochs for -wen22.-Math-1
B.2 FIRST-ORDER CORRELATION TEST VIA EDGINGTON'S METHOD
For each question q, let P, denote the sample Pearson correlation computed from independent rollouts, and let Py be the corresponding two-sided p-value for testing the null hypothesis
Ho.g 0q
23

---

Published as a conference paper at ICLR 2026
To aggregate evidence across all Q questions, apply Edgington's 's sum-of-p method.
Sum of p-values. Each per-question Py is treated as a realization of a Uniform(O, 1) variable under its null hypothesis. Edgington's 's statistic is defined by the simple sum
Q
Spa
Σ 9=1
Pa
Null distribution. Under the global null hypothesis
Ho Py =0 4gg.
each Py Uniform 1), and therefore
SEd Irlin-Hall(Q),
with mean and variance
[[[Sa]] Q
Q
Var(Sga)
12
For large Q, SEa is well approximated by normal distribution:
Sea N Q Q
2 12
Global p-value and decision rule. Small values of SEa indicate joint evidence against Hg. The corresponding one-sided global p-value is
Q/2
Pelobal
VQ/12
where & denotes the standard normal CDF. Given significance level a = 0.5, we reject Ho when Pglobal <
We set up the experiment identically to the Fisher's method test in Appendix B. using the same benchmark of Q 600 questions, each with 16 independent rollouts. For each checkpoint of the policy model ne. we compute the Edgington statistic and report the global p-value. Since all global valuus exceed the chosen significance level a 0.05, we do reject the null hypothesis, which supports our assumption that the correlations Pg are zero across all questions.
Epoch
Global p-value
2, [H
0.0
0.7894
0.5
0.3964
1.0
0.2148
Table Global p-values (Paloba) across training epochs for Qwen2. 5-Math 1. using Edging- ton's method.
B.3 EQUAL VARIANCE TEST VIA LEVENE'S TEST
In the numerical experiments, we have assumed that the variance for 2, is constant across different prompts y. We proceed with hypothesis test:
Ho 22, 2 Vq # d'
H1 At least 022 + oz
For each question 9. consider the random variable Z, with ny independent observations (Z,,) 3 Transform observations for Levene's test. Let Yg. denote the absolute deviation from the per- question median:
Yg. 12 median ........, 1.....,,,,,. 7y.n,,1
24

---

Published as a conference paper at ICLR 2026
Compute group means of transformed observations. The mean of the transformed observations for question is
1
Y
B4
j=1
and the overall mean across all questions is
Q
Q
Y
Yas
N
n4
q=1
Compute Levene's test statistic. The test statistic is given by
(N Q) q== Ry Y) Q)
W
(Q -Q-1) プラ= (Xy. - y₂)²
Under the null hypothesis that the variances are equal across questions,
Ho 02 = oz2 Vg + d'
the statistic W approximately follows an F-iitribbution with Q and N degrees of freedom W FQ-1.N-Q-
Compute p-value and decision rule. The p-value for testing Ho is
= Pr((F--1,N-Q 2 W).
Given a significance level a (e.g., 0.05), we make the following decision:
If PLevene < at, we reject Hlg indicating that the variances of Ž, differ across questions.
If PLevene 2 a, we fail to reject Ho, the hypothesis that the variances are equal across all ques- tions, at the significance level a.
We conduct the variance homogeneity test described above on benchmark of Q = 600 questions, each with n 16 independent rollouts. We perform Levene's test across all questions to assess the equality of variances. We evaluate the policy model тæ, at four checkpoints during training of 0.0, 0.5, 1.0 epochs. At each checkpoint, we report the
5- 5-.5thhhhh1 1BB, corresponding resulting global p-values PLovene in Table 7 Since all Plevene exceed the chosen significance level 0.05, we can not reject the null hypothesis, which supports our assumption that the variances o3 are equal across all questions.
Epoch
Global p-value
2, = (TH(),)
2, = (H1))
0.0
0,5019
0.2705
0.5
0.4785 0.4132
1.0
0.3847
0.3847
Table 7: Ptevenne from Levene's test across training epochs for Qwen2.5 5-Math-- 5B, assessing variance homogeneity of Zq.
B.4 EQUAL VARIANCE TEST VIA O'BRIEN'S S TEST
In the numerical experiments, we have assumed that the variance for 2, is constant across different prompts q. We proceed with hypothesis test:
Ho 0z = 4q d.
H1 At least one 07 + oz
For each question g, consider the random variable 7 with ny independent observations (2,3) 1
25

---

Published as a conference paper at ICLR 2026
Transform observations for O'Brien's test. Let 9. denote O'Brien's transformation of the ob- servations:
(ng 1. (Z 2,) 0.55 -
Y q.j
(ny mm
where 2g the sample mean for question 4 and sy the unbiased sample variance for question g. Compute group means of transformed observations. The mean of the transformed observations for question q is
1 ng
Yg
Y 2.
j=1
and the overall mean across all questions is
Q Σ
Y
N
ngg
Compute O'Brien's test statistic. The test statistic is given by
(N - -N-Q)E
0) mg Y 8)2
WoB
(Q (Q-1) 1) Eラ (Y,, 8²)²
Under the null hypothesis that the variances are equal across questions,
Ho 22 2,4 Vy + d'
the statistic WoB approximately follows an F. F-distribution with Q and N Q degrees of freedom WoB FQ-1,N-Q-
Compute p-value and decision rule. The p-value for testing Ho is
Pon = Pr(FQ-1.N-Q 2 Won).
Given a significance level a (e.g., 0.05), we make the following decision:
If Pon < o, reject Ho, indicating that the variances of 2y differ across questions.
If Pos 2 we fail to reject Ho, the hypothesis that the variances are equal across all questions, at the significance level
We conduct the variance homogeneity test described above on benchmark of Q 600 questions, each with the equality of variances. We evaluate the policy model тe, at three checkpoints during training of Qwen2. 5-Math-1- 5B, corresponding to 0.O, 0.5, 1.0 epochs. At each checkpoint, we report the resulting global p-values PoB in Table 8] Since all POB exceed the chosen significance level 0.05, we cannot reject the null hypothesis, which supports our assumption that the variances 222 are equal across all questions.
16 independent rollouts. We perform O'Brien's test across all questions to assess
Epoch
Global p-value
2, (1,)))
0.0
0.3009
0.5
0.2563
1.0
0.2420
Table 8: Pon from O'Brien's test across training epochs for 5amn2h.-MMMhh--- 5B, assessing variance homogeneity of Z
C ADDITIONAL INFORMATION ON NUMERICAL EXPERIMENTS
Hepepparameters. We curate list of important training hyperparameters for our experiment in
T
26

---

Published as a conference paper at ICLR 2026
Table 9: Hyperparameter configuration.
Category
Hyperparameter
Value / Setring
Optimizer
Optimizer
AdamW
Learning rate Warm-up
1 x 10-6
20 rollout steps
rollout
Prompt batch size
512
Responses per prompt
6/8/Dynamic
Training
Mini-batch size
512
Max generation length
10 240 tokens
Temperature
1.0
C.I ADDITIONAL INFORMATION ON ABLATION STUDIES
Inverse-accuracy allocation. We allocate more rollout budget to prompts with lower empirical accuracy. Concretely, letting acc; denote running accuracy estimate for prompt i, we set target weights w, acc; + E) and normalize to meet the global budget and per- per-prompt bounds.
inverse-variance allocation. We allocate more rollout budget to prompts whose answers exhibit lower variance. Letting of be the (running) answer variance estimate, set w; 1/(a, + with the same normalization.
Both heuristics implemented via continuously relaxed, constrained optimization that enforces the tudgl-budget and box constraints; we solve it with an online solver and then map fractional solutions to integers using the rounding heuristic.
Comparison of Optimal Allocations Across Objectives B=16, C=256, Box [4.0, 32.0]
Our Adaptive Allocation
30
Inverse-Accuracy heuristic Inverse-Variance heuristic
n. (optimal rollouts)
25
20
15
10
5
0.0
0.2
0.4
0.6
0.8
1.0
Pq (per-prompt success probability)
Figure 2: Comparison of optimal rollout allocations produced by different heuristics versus our proposed variance- awaarce--wware allocation strategy. The figure plots the optimal number of rollouts nf against prompt difficulty Pt, highlighting how our method allocates budget differently from inverse- accuracy and inverse-variance basclines.
C.2 PROMPT TEMPLATE.
During training, we only use one prompt template for every prompt the dataset. There are two prompt templates, one for mathematical reasoning and one for tool-augmented reasoning.
27

---

Published as a conference paper at ICLR 2026
Prompt rate prediction
Prompt success rate prodiction error
[Gaussin Procesa)
Pooea))
0.25
Moving Avcrage
Moving Averge
Rlöge Segression
Ridge Regreaion
Mcan Abrolute Error
Mean Absollute Error
0.15
0.10
0.05
0.1
0.0
20
40
50
20
50
Gradient step
Gradient step
(a) Qwen2.5-
(b) Qwen2.5-Math-78
Figure 3: Prediction mean absolute error (MAH) over training steps for two model scales. Our GPR-based predictor achieves consistently lower MAE than moving average and Ridge Regression baselines for both the 1.5B and 7B models.
Figure 4: Prompt template for mathematical reasoning
Solve the following math problem step by step. The last line of your response should where $Answer is the answer to the problem. Do not wrap $Answer with \bexed().
the form Answer: Sänswer (without quotes)
current question: [[question)]
Below are two examples for format reference. Example question 1: Solve for x: 3x = 16.
Response:
Add 5 to both sides: 3x 21. Divide both sides by 3: x 7. Answer: 7
Solve the current question. Remember to put your answer on its own line after "Answer:".
D ALGORITHMS
The algorithm capturing the complete flow the posterior update for the Gaussian Process is provided in Algorithm I
Algorithm presents our heuristic rounding procedure, which maps a continuous solution to a dis- crete one while ensuring that the budget constraints remain satisfied.
E EXTENSION TO CONTINUOUS REWARDS
This section details the necessary adaptations to our predictive rollout allocation strategy for the case where the reward R(ō,) is real-valued random variable. All definitions, assumptions, and notation follow the main text unless otherwise stated.
E.I GRADIENT VARIANCE FOR CONTINUOUS REWARDS
We first state the analogues of variance propositions for the continuous reward setting. The proofs are intermediate results from proofs for binary case in Appendix A
28

---

Published as a conference paper at ICLR 2026
Figure 5: Prompt template for tool augmented reasoning
In this envirenment you have access to a set of tools you can use to assist with the user query.
You may perform multiple rounds of function calls. In each round, you call
functions.
Here are avai waileabl functions in JSONSchema format:
In "anjjonooffunc_scheeee
In your respense, you need first think about the reasoning process in the mind and then conduct function calling to get the information or perform the actions if needed. \
The reasoning process and functicn calling are enclosed within <think> </think> and <tool_cali> </tool_call> tags.
The results of the function calls will be given back to you after execution, \
and you can cont inue to call functions until you get the final answer for the user's question.
Finally, if you have got the answer, enclose it within \booxed with
latex format and do not continue to call functions, i.e., <think> Based on the response from the function call, I get the weather information. </think> The weather in Beijing on 2025-04-01 is WI \booxed (200)) W..
For each function call, return a jsen object with function name and arguments within stoi_call><<tool_car XML tags: <tool_call> [1"name": sfunction-nane "arguments"; <arge-json-object>]
</tool_call>
29

---

Published as a conference paper at ICLR 2026
Algorithm Recursive GP Posterior Update
Require: Mini-batch B;; rollout allocation {ng (/g):=: prior mean m2(D) E IR?, kernel matrix E E
R
1: for each E B, do
2: # Run ny rollouts and observe outcomes Rg E {-1,1)
Rg 1 دド= R
3:
4: 9g + sigmoid -aaiidd-(hhh
ccli Rg+1 , ;,, -()) ())
5: end for
6: geteerve + (89)
7: Partition m, and Σ according to B₁ and B
8: mi,5; +- M4 + L EB,, (gobserve m.,,,)
9: N + 8; B, \=1 B, B.
for q to Q do
11: if B3 then mx+1(xg) t 0g else m4+1(1g) + (x,8 end if
12: end for
Pt+1 = =igmoid(me+11()
14: return {p++1). }, m4+1
Algorithm& 2 Heuristic rounding for integer rollout allocation
Require: Solution {m,} total budget C, bounds {L, U), objective functions f.(+) for each g
For each 9. set fgg [n]]
2: Crem + CC- 0g
3: for each y with fy < U do
4: Compute incentive: Ay + f(4 fy( + 1)
5: end for
6: while Crem > 0 do
7: Select q² = arg maxxs < Ag
8: Set fly. t frg +1
9: Recompute Dg f- fa (fhrr) ) fq (fhp + 1)
10: Crem +- Cram -1
11: end while
12: return Integer allocation ( with EyEB, fgg Cnddd L s fg S U for all q
Proposition E.1 (Dr. GRPO gradient variance, continuous reward). Let R(ō,) R be a real-
valued random variable with variance Var R). If Assumption 4.1 holds and Var 2) = o2 then the variance of the per-prompl projected Dr. GRPO gradient estimator with rollouts is
Var(C) (m 1)02 Var(ft).
n2
Proposition E.2 (RLOO gradient variance, continuous reward). Let R(ōū) = R be a real-valued
random variable with variance Var R). If Assumption 4.1 holds and Var Z) 0z then the variance of the per-prompt projected RLOO gradient estimator with n rollouts
0z Var
Var(C)
E.2 GAUSSIAN PROCESS PREDICTION OF REWARD VARIANCE
For continuous rewards, the per-promp gradient variance depends on Var(R,), which is not directly observable prior to rollout. To predict this quantity, replace the GP model for success probability with GP model for reward variance. Specifically, for each prompt q, we model the reward variance as Vg,t softplus(gt (xg)) log(1 + (xp(g((x,))) where gr is a latent GP in the main text. After observing rewards R = compute the sample variance 82 and the observation for
30

---

Published as a conference paper at ICLR 2026
the latent variable Iy.t leg(exp($)) ( 1). The GP posterior update and recursive prediction
steps proceed identically, replacing the sigmoid link with the softplus link.
E.3 BUDGET ALLOCATION OPTIMIZATION
Given predicted reward variances Var( we define ag :- = Var(Pg): The continuous relax- ation of the rollout allocation problem for Dr. GRPO becomes
min- Σ
2EB EEB.
Og
nig
n1 C LS ny U, nl R Va)
n
and for RLOO,
min Σ
Σ
qEB. n4 C, L S ny U. ny ER
2g
Og n2g
2g
The optimal solutions are given by Theorems 5.1 and 5.2 the main text, with the updated definition of ag. The rounding procedure described in Appendix D applies without modification.
F TRAINING EVOLUTION COMPARISON
In this section, we compare training evolution on model Qwen2. 5 5-Math-11 1..5. 5B using GRPO and GRPO+VIP. Figures 6 report training metries (mean advantages, mean rewards) and multiple performance metrics (best@32 32, maj 32, mean @ 32).
To ensure that all training trajectories are directly comparable, every model is trained on the same dataset under identical optimization settings: the same fixed ordering of 17k training prompts, two epochs of training, batch size of 512, mini-batch size of 64, and rollout budget per batch of 512 and 512 16. As a result, each gradient step corresponds to the same amount of data and computation across all methods.
Across most of evaluation checkpoints, we observe consistent and pronounced improvements from using VIP. During training, we observe that using VIP, we obtain consistently far-from-zer advan- tages and higher rewards. This indicates that our learning algorithm provides richer learning signal and our rollout allocation strategy is effective. Further empirical evidence are provided in Figures] where VIP performance exceeded GRPO at most training steps.
31

---

Published as a conference paper at ICLR 2026
Mean training advantage
0.00
VIP (mean)
VIP (mean)
GRPO (mean)
Mean training rewards
GRPO (mean)
-0.5
-0.6
-0.8
0.05
1.0
Gradient Steps
Gradient Steps
0.00
Mean training advantage
(mean)
(mean)
Mean training rewards
-0.2
-0.01
GRPO (mean)
GRPO (mean)
MV AMM
00.02
-0.6
0.04
-0.05
10
20
30
40
50
60
10
30
40
50
Gradient Steps
Gradient Steps
Figure 6:
Mean advantages and mean rewards of GRPO vs. GRPO+VIP using rollout budgets of
and 16.
32

---

Published as a conference paper at ICLR 2026
0.2
VP (mrcan) GRP1 (mmer))
VP Imeen)) GRPO (msen))
VP Itrcan) GRP9 (meen))
40
38
40
(a) AIME 2024, hest ( 32
AIME 2024, maj @ 32
(c) AIME 2024,
3.50
Vir (meen)
Imean)
VI" Itren)
SAPO
AMM22005 May012
GRPO
GAPO (meen))
8.0
4.00
0.00
(d) AIME 2025, best
AIME 2025, maj @
AIME 2025, mean
0.50
GRPO
VI [mean)
0.14
VP [meen)
GRPO Imcoin)
820
(g) AIME 2025, best@
(h) AIME 2025, maj@3>
(i) AIME 2025, mean
VP [meen)
VP [mean]
GRPO
GRPO
8.00
(i) AIME 2025, best@32 32
(k) AIME 2025, m2
(I) AIME 2025, mean
Figure 7: GRPO vs. GRPO+VIP using rollout budget 8 and 16 AIME 2024 and 2025 across different accuracy metrics.
33


Reviews:
[{"review_id": "gfF5JqdGXK", "reviewer": "Reviewer_dXiM", "summary": "The paper proposes adaptive rollout allocation for group-based RL with verifiable rewards: instead of using a fixed number of rollouts per prompt, it predicts each prompt’s success probability and allocates the rollout budget to minimize expected gradient variance. Concretely, the method (“VIP”) fits a lightweight Gaussian Process over prompt embeddings to estimate per-prompt success probabilities, translates them into variance proxies, and solves a convex budget-allocation problem (with an integer rounding heuristic) under a hard rollout budget. Experiments on math reasoning and tool-augmented reasoning show higher accuracy than uniform or heuristic allocation at the same total rollout budget.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "he paper derives per-prompt gradient-variance formulas for Dr.GRPO and RLOO, motivating variance-aware allocation rather than uniform rollouts.\n\nOn AIME24/25 and tool-augmented retrieval, VIP consistently improves accuracy/quality over uniform allocation while keeping the same total number of rollouts.\n\nReplacing either the GP predictor or the optimizer degrades performance, suggesting both components contribute meaningfully.", "weaknesses": "Results are reported under the same rollout budget; however, adaptive per-prompt rollout counts can change the number of optimizer steps and total time. The paper should add (a) wall-clock time vs. accuracy and (b) equal-step comparisons to isolate compute-efficiency.\n\nTraining a GP and solving the allocation each iteration adds overhead; the paper does not provide detailed runtime/memory profiling vs. uniform baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4FbtEzON9V", "reviewer": "Reviewer_6M1P", "summary": "The submitted manuscript introduces VIP (Verifiable Importance-based Policy), a method for adaptive rollout allocation in reinforcement learning with verifiable rewards.\nInstead of assigning a fixed number of rollouts per prompt, the proposed scheme dynamically allocates rollout budgets based on estimated gradient variance, aiming to improve sample efficiency. This allocation is based on simplified variance computations and the computation of a budget constraint optimization problem. Experiments on math reasoning and question-answering tasks show that VIP achieves better accuracy and reward efficiency compared to uniform rollout allocation.", "questions": "- Under Assumption 3.1, what is the difference between the proposed method and the REINFORCE algorithm?\n- In equation (3), where does $\\tau$ appear? Shouldn’t $A_j$ depend on $\\tau$?\n- Why is it feasible to project the vector $H$? While projecting the gradient of $J$ would correspond to a projected gradient method, projecting $H$ itself appears to introduce a bias.\n- How do the results in Table 1 change when considering computational cost? Does the budget-allocation procedure introduce significant additional runtime?\n- Are the variances of $Z_q$ assumed to be known? If so, why is this assumption considered feasible in practice?\n\nTypos:\n- Line 50: …ha[ve] emerged…\n- Line 97: Section title should be Related Work[]\n- Line 171: However, [o]ur paper…\n- Line 266: …denote… denoted…\n- In general, I suggest to work over the reference list. In some references there are publisher information missing (Liao et al. 2025, Lin et al. 2025, Sun et al. 2025).\n- Some abbreviations are multiple times defined.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "- The paper addresses a relevant and timely problem in reinforcement learning for language models, focusing on efficient rollout allocation under limited budgets.\n- The proposed VIP framework is clearly motivated and presented as a practical enhancement to existing RL with verifiable rewards (RLVR) methods.\n- The topic is well aligned with current interest in improving training efficiency for large models.\n- The proposed idea of allocating samples based on variance estimates, where the unknown dependencies are modeled through a predictive Gaussian process approximation, is both interesting and promising.", "weaknesses": "The theoretical analysis is developed under very restrictive assumptions. It sometimes feels as though several of the key challenges of the original setting have been simplified away in order to make the variance computations tractable. While this makes the analysis cleaner, it also raises concerns about the realism and relevance of the resulting conclusions and the potential for counterintuitive sample allocations.\n\nConcern about Assumption 3.1: The assumption $\\pi_{old} = \\pi_\\theta$ effectively removes the off-policy nature of the considered algorithms. Under this setting, the approach seems to reduce to a REINFORCE-style algorithm (with a baseline), where the importance weights are omitted. This simplification has a substantial impact on the resulting variance expressions, since dropping (even clipped) importance weights can alter the underlying variance structure. Consequently, the proposed allocation behaves as if the algorithm were purely on-policy, which does not reflect how these methods are typically used in practice.\n\nThere also appears to be a conceptual inconsistency in the motivation. The paper begins by discussing algorithms such as PPO and GRPO, which rely on partially off-policy training through clipped importance weights. Later, however, by adopting Assumption 3.1, the analysis assumes all weights are one and argues that purely on-policy training is preferable. This shift in perspective makes it unclear why the analysis focuses on those off-policy algorithms rather than directly studying the on-policy methods.\n\nConcern about Assumption 4.1: Both parts of this assumption seem rather strong. The independence between $\\tilde R$ and $\\tilde Z$ is understandable as a simplifying step, but the second part appears difficult to justify in practice. The statistical tests in Appendix B do not provide convincing evidence for these assumptions, they only show that there is insufficient evidence to reject $H_0$. Similar concerns apply to the assumption that all $\\tilde Z_q$ share the same variance.\n\nTaken together, Assumptions 3.1 and 4.1 make the variance derivations in Propositions 4.2 and 4.3 relatively straightforward. However, this comes at the cost of removing much of the complexity inherent in the real algorithms. As a result, the computed variances differ substantially from those of the actual gradient estimators used in the experiments.\n\nFinally, while the empirical results show that VIP yields consistent improvements over uniform rollout allocation on several reasoning benchmarks, the gains are difficult to interpret without additional context. In particular, computational costs are not reported (solving the allocation optimization and fitting the Gaussian process introduce extra overhead), and the experiments lack statistical validation such as error bars or multiple runs, making it difficult to assess the robustness of the observed improvements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p4kN4wlwa4", "reviewer": "Reviewer_NY2y", "summary": "This paper studies adaptive selection for rollout trajectories for online reinforcement learning (RL)-based language model (LM) training. Specifically, algorithms like GRPO need a batch of rollouts to calculate the (batch normalized) value function, and there are acquisition cost vs. performance tradeoff depending on the number of sample. The paper discuss how to improve the data efficiency of trajectory retrieval by adaptively allocating the rollout budget in a way to minimize the variance of the policy gradient. In particular, the proposed method adapts Baysian approach to estimate the probability of the outcome becomes positive. The experiment results indicates that adding the adaptive rollout components, the algorithm improves the performance compared to uniform rollout allocation.", "questions": "- How does the proposed method track the non-stationarity of the expected reward (occurring by the policy's generation probability)?\n\n- How to generalize the idea to the continuous outcome case?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The motivation for the rollout budget cost and performance tradeoff is well-explained.\n\n- The proposed method can be integrated with off-the-shelf learning algorithms, and the experiment results show an improvement in the result.\n\n- The parameter update for adaptive allocation can be done in an online learning approach using Bayesian updates, and does not seem to require huge computation when new data is added.", "weaknesses": "- One concern I have is whether the Bayesian estimation results in biased estimation of the success probability. If I understand correctly, the probability $p$ measures the probability that the outcome sampled on some query results in a positive reward. This probability should depend on the policy's sentence generation probability, and given that the policy is updated during the training phase, the algorithm should be able to handle the non-stationarity of the reward. However, this discussion is not provided, and I wonder whether the estimation is biased towards past policy or the results can change depending on the choice of initial policy.\n\n- Application may be limited to the binary outcome case. It is not obvious how to generalize the idea to the continuous outcome case, especially, how to track the distribution of rewards in such cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)