BASIS: Batchwise Advantage Estimation from Single-Rollout Information Sharing for LLM Reasoning
May 26, 2026
Abstract
Reinforcement learning with verifiable rewards has become a standard recipe for improving the reasoning abilities of large language models. Existing algorithms face a tradeoff between computational efficiency and sample efficiency in value estimation and policy learning. We introduce BASIS, a critic-free post-training algorithm designed to address this tradeoff. At each online training step, BASIS samples only one rollout per prompt, but leverages rich information across prompts in the entire batch to improve value function estimation. Our experiments demonstrate that BASIS reduces MSE in value function estimation by 69% compared to REINFORCE++, a representative single-rollout baseline, and achieves lower MSE with one rollout than group mean estimators with 8 rollouts. This improvement in value estimation translates to better policy optimization: using substantially less training time, BASIS achieves performance close to multi-rollout GRPO-type baselines and often outperforms single-rollout REINFORCE-type baselines.
1 Introduction↩︎
Recent progress in large language model (LLM) reasoning has increasingly relied on large-scale reinforcement learning (RL). In particular, RL with verifiable rewards [1] scores LLM responses using automated task verifiers and uses these scores as rewards to update the model’s policy. Popularized by DeepSeekMath and DeepSeek-R1 [2], [3], RLVR has become a standard post-training framework for open-source large reasoning models [4]–[6], with numerous follow-up works appearing shortly thereafter (Section 2).
Existing RLVR algorithms face a fundamental tradeoff between computational efficiency and sample efficiency. More accurate value or advantage estimates can improve the sample efficiency of the resulting policy optimization algorithm, but they are often expensive to obtain. PPO-type algorithms train an auxiliary critic network for value estimation [7], while GRPO-type algorithms sample multiple rollouts per prompt and use their average reward for the estimation [2], [6], [8], [9]. These algorithms improve sample efficiency at the cost of additional computation. In contrast, single-rollout critic-free algorithms are computationally cheaper, but their value estimates are less accurate and lead to noisier policy updates.
In response to this tradeoff, we propose BASIS, short for Batchwise Advantage estimation from Single-rollout Information Sharing, a critic-free RLVR algorithm that samples only one rollout per prompt at each online training step.
Methodologically, BASIS introduces a novel batchwise advantage estimator that borrows rich information across prompts in the whole batch to improve value and advantage estimation (see Figure 1 for an illustration). Together with offline estimation and online calibration (Section 4), this enables BASIS to retain much of the sample efficiency of multi-rollout algorithms while using only a single rollout during online training.
For value estimation, BASIS is highly sample efficient: it substantially reduces the MSE of single-rollout baselines and achieves lower MSE than multi-rollout baselines using 8 rollouts. Moreover, unlike existing baselines, BASIS is robust to reward heterogeneity and prompt difficulty, while producing informative advantage estimates (Section 5.1).
For policy optimization, the BASIS advantage estimator can serve as a plug-in component for a range of RLVR algorithms. It stabilizes training and mitigates collapse during optimization. The resulting fine-tuned model often outperforms single-rollout baselines and remains competitive with multi-rollout baselines while requiring considerably less training time (Section 5.2).
2 Related Work↩︎
The algorithmic foundations of RLVR trace back to a long line of policy gradient algorithms in the RL literature [10], [11]. One central theme in this literature is variance reduction: more accurate value or advantage estimates can reduce the variance of policy gradient estimation and improve the quality of policy optimization [12]. Motivated by this observation, existing approaches can be divided into four categories:
The first category, represented by PPO, employs a deep neural network to learn the value function and applies generalized advantage estimation for variance reduction [13], [14]. While effective, this approach introduces an additional value network, making training substantially more costly.
The second category, represented by GRPO, removes the value network and uses the average reward over multiple rollouts of the same prompt as a proxy for the value function [2], [15].
The third category follows the critic-free spirit of the second category, but aims to reduce the number of rollouts required per prompt. One approach uses the reward of a greedy, deterministic rollout, which only requires one rollout per prompt [16]. Another approach reduces the required number of rollouts while maintaining sample efficiency by borrowing reward information either across training iterations for the same prompt [17]–[19], or across different prompts in the same batch [20]–[22].
The last category studies variance reduction baselines beyond standard value functions [23].
BASIS is most closely related to the third category, especially those methods that exploit batch-level reward information. However, as our experiments show, BASIS achieves substantially smaller MSE in value estimation than REINFORCE++ [20], a representative batch-level baseline.
Beyond value and advantage estimation, existing work also studies exploration, clipping, rejection sampling, experience reuse, rollout down-sampling and pruning, uncertainty and difficulty-aware updates [24]–[33]. Since BASIS only modifies the value function baseline, it can serve as a plug-in component for many of these RLVR pipelines.
Finally, recent work has begun to study the theoretical properties of RLVR [34]–[39].
3 Preliminaries↩︎
We first introduce notation that will be used throughout the paper. We then describe how the classical REINFORCE algorithm [11] applies to LLM post-training. Finally, we use PPO, GRPO, and REINFORCE++ as representative variance reduction baselines to illustrate the first three categories of algorithms reviewed in Section 2.
Notation. We use \(x\sim \mathcal{D}\) to denote a prompt drawn from a training dataset \(\mathcal{D}\), and \(y \sim \pi_\theta(\bullet|x)\) to denote a rollout sampled from the LLM policy \(\pi_\theta\) that we wish to fine-tune, with parameters \(\theta\). For reasoning tasks, \(y\) contains both a reasoning trace and a final answer. An automated task verifier returns a scalar reward \(r(x,y)\in\mathbb{R}\), where the reward function \(r\) usually measures the correctness of the final answer. Let \(\mathcal{B}=\{x_i\}_{i=1}^B\) denote a batch of prompts. To simplify the notation, we use \(r_i\) to denote \(r(x_i,y_i)\) for a given prompt-rollout pair \((x_i,y_i)\). We use \(\theta_t\) to denote the model parameters at training iteration \(t\), and define \(V_{i,t}=\mathbb{E}_{y\sim \pi_{\theta_t}(\bullet|x_i)}[r(x_i,y)]\), \(A_{i,t}=r_i-V_{i,t}\) as the policy’s value and advantage.
REINFORCE. RLVR algorithms fine-tune the parameters \(\theta\) by maximizing the expected reward \[\label{eqn:Jtheta} \mathcal{J}(\theta) = \mathbb{E}_{x\sim\mathcal{D}} \Big\{\mathbb{E}_{y\sim\pi_\theta(\bullet|x)} \bigl[r(x,y)\bigr]\Big\},\tag{1}\] which can be optimized using stochastic gradient methods [40]. Specifically, its gradient \(\nabla_\theta \mathcal{J}(\theta)\) can be shown to equal \[\mathbb{E}_{x\sim\mathcal{D}} \Big\{\mathbb{E}_{y\sim\pi_\theta(\bullet|x)} \bigl[r(x,y)\nabla_{\theta}\log \pi_{\theta}(y|x) \bigr]\Big\}.\] This identity motivates REINFORCE-type algorithms: starting from an initial parameter \(\theta_1\), at each training step \(t\), the algorithm samples a batch of prompts \(\mathcal{B}=\{x_i\}_{i=1}^B\) and one rollout \(y_i\sim \pi_{\theta_t}(\bullet|x_i)\) per prompt. It then estimates \(\nabla_{\theta} \mathcal{J}(\theta_t)\) by averaging the product of the reward \(r_i\) and policy score \(\nabla_{\theta} \log \pi_{\theta_t}(y_i|x_i)\) over the batch, and applies stochastic gradient ascent to update \(\theta_t\) to \(\theta_{t+1}\).
Variance reduction baselines. The REINFORCE policy gradient estimator is unbiased, but often suffers from high variance, especially when the model is uncertain and sampled rollouts can vary substantially in quality. This variability leads to noisy rewards and gradient estimates, making policy optimization less stable. A standard remedy is to construct an advantage estimate \(r_i-b_i\) by subtracting a baseline \(b_i\) from the reward \(r_i\) before multiplying by the policy score. Under suitable conditions, the optimal baseline that minimizes the variance of the policy gradient estimator is the value function [12].
PPO, GRPO, and REINFORCE++ all adopt this variance reduction principle, but differ in how they construct \(b_i\), and hence the resulting advantage estimate. PPO sets the baseline to an estimated value function learned by an auxiliary neural network, which improves sample efficiency but introduces substantial computational cost. GRPO sets \(b_i\) to the average reward over multiple rollouts from the same prompt, which eliminates the need for a value network but also increases computation through repeated rollout sampling. REINFORCE++ instead uses a global batch baseline, given by a simple average of \(\{r_i\}_i\), which avoids both a value network and multiple rollouts per prompt, but the resulting baseline is shared across all prompts and may poorly approximate each prompt’s individual value.
These choices highlight the central tradeoff addressed in this paper: accurate baseline estimation can be obtained by learning a value model or by repeating rollouts for each prompt, but both approaches increase computation.
4 BASIS↩︎
We now introduce BASIS to address the tradeoff between accurate baseline estimation and computational efficiency. At each online training step, BASIS samples only one rollout per prompt while leveraging the rich information available across the entire training batch to improve each prompt’s value and advantage estimation.
BASIS proceeds in three steps: offline value estimation, batchwise refinement, and online calibration. It first constructs an initial prompt-level value estimate through offline estimation. It then refines this estimate online using reward information from the entire training batch. Finally, it calibrates the refined estimator at each training step. Algorithm 3 summarizes the procedure for each training step. Below, we first describe the second step, which is the key ingredient of BASIS. We then explain how the offline value estimates are computed, and how the refined estimators are calibrated.
Batchwise refinement. At each training step \(t\), given a prompt-rollout batch \(\{(x_i,y_i)\}_{i=1}^B\), BASIS estimates the value \(V_{i,t}\) for each \(x_i\). Its main idea is simple: each \(V_{i,t}\) is estimated by a weighted average of rewards from other prompts in the batch: \[\label{eq:linear-baseline} \widetilde{V}_{i,t}=\sum_{j\ne i} w_{ij} r_j,\tag{2}\] where the weights \(\{w_{ij}\}_{j\ne i}\) are prompt-dependent. Such a linear combination allows BASIS to borrow information across prompts in the same batch, yielding a low-MSE estimate from only one rollout per prompt, as we show in the experiments.
Before specifying the weights \(w_{ij}\), we highlight two features of this estimator. (i) It is prompt-dependent: the weights vary with \(i\), unlike the global batch baseline used by REINFORCE++. With a proper choice of weights, this allows BASIS to better approximate the prompt-level value. (ii) It follows the leave-one-out principle of RLOO [15]: the reward \(r_i\) of the target prompt is excluded from its own baseline.
It remains to specify the weights \(w_{ij}\). The following proposition motivates our choice.
Proposition 1 (Best linear unbiased estimator (BLUE)). For each prompt \(i\), among all linear estimators of the form 2 that are unbiased for \(V_{i,t}\), i.e., \(\mathbb{E}(\widetilde{V}_{i,t}|\mathcal{B})=V_{i,t}\), the weights minimizing \(\mathbb{E} [(V_{i,t}-\widetilde{V}_{i,t})^2|\mathcal{B}]\) are \[\label{eqn:wij} w_{ij}=\frac{V_{i,t}V_{j,t}/\sigma_j^2}{\sum_{k\ne i} V_{k,t}^2/\sigma_{k}^2}, \quad \forall j\in \{1,\cdots,B\}\setminus\{i\},\qquad{(1)}\] where \(\sigma_j^2=\operatorname{Var}(r_j|x_j)\).
Proposition 1 characterizes the ideal weights one would use to minimize the MSE of the resulting value estimator while preserving its unbiasedness. Intuitively, when estimating the value of the \(i\)th prompt, the weight increases with both the target value \(V_{i,t}\) and the source value \(V_{j,t}\), and decreases with the source reward variance \(\sigma_j^2\).
Of course, the BLUE weights cannot be used directly during online training, because the true values \(V_{i,t}\) and variances \(\sigma_i^2\) are unknown. BASIS therefore uses this proposition as a guiding principle. For binary rewards, given an initial value estimate \(\widehat V_{i,t}\), we estimate the reward variance by \(\widehat{\sigma}_i^2= \widehat{V}_{i,t}(1-\widehat V_{i,t})\). We then plug these estimates into ?? to construct the refined estimator \(\widetilde{V}_{i,t}\).
When some initial values are close to zero or one, their Bernoulli variance estimates are close to zero, making the weights in ?? numerically unstable. To address this, we define the following active set \[\mathcal{A}_t=\{i:\epsilon<\widehat V_{i,t}<1-\epsilon\},\] for some small threshold \(\epsilon>0\). For prompts in the active set, the sums in 2 and the denominator of ?? are taken over \(\mathcal{A}_t\setminus\{i\}\) rather than all prompts. For prompts outside the active set, BASIS falls back to the conservative zero baseline \(b_i=0\).
We will describe how the initial value estimates are obtained below. To conclude this batchwise refinement step, we note that these initial estimates could also be used directly for advantage estimation without refinement. However, the batchwise refinement yields a substantially more accurate estimator by leveraging information shared across prompts. Figure 2 illustrates this effect by comparing the MSEs of the initial and refined estimators at three checkpoints. It can be seen that the refined estimator achieves considerably lower MSE and is much less sensitive to a calibration hyperparameter.
Offline value estimation. We next describe how BASIS computes the initial value estimates \(\widehat{V}_{i,t}\). The idea is motivated by direct preference optimization [41] and its extension to LLM reasoning [42]. To begin with, consider the following Kullback–Leibler (KL)-regularized objective function, \[\mathbb{E}_{x\sim \mathcal{D}} \mathbb{E}_{y\sim \pi(\bullet|x)}[r(x,y) - \beta\,\mathrm{KL}\!\left(\pi(\bullet|x)\,\|\,\pi_{\mathrm{ref}}(\bullet|x)\right)],\] where \(\pi_{\mathrm{ref}}=\pi_{\theta_1}\) denotes the reference policy, taken to be the initial policy before fine-tuning, and \(\beta>0\) controls the strength of the KL penalty.
This objective is particularly appealing because its maximizer \(\pi_\beta^*\) admits the following closed-form expression [41]: \[\pi_\beta^*(y|x) = \frac{\pi_{\mathrm{ref}}(y|x)}{Z_\beta(x)} \exp\Big(\frac{r(x,y)}{\beta}\Big),\] where \(Z_\beta(x)\) is a normalizing constant. This expression connects \(\pi_{\beta}^*\) directly to \(\pi_{\mathrm{ref}}\). As a result, estimating the value of \(\pi_\beta^*\) does not require training or sampling from \(\pi_\beta^*\) itself. Instead, it can be done offline by sampling rollouts from \(\pi_{\mathrm{ref}}\) [42]. We formalize this observation in the following proposition.
Proposition 2 (Closed-form value under \(\pi_\beta^*\)). For any prompt \(x\) and \(\beta>0\), the value function under \(\pi_{\beta}^*\) equals \[\begin{align} \label{eqn:Vbetaxstar} \begin{aligned} &V_\beta^*(x) := \mathbb{E}_{y\sim \pi_\beta^*(\bullet|x)}[r(x,y)]\\ =& \frac{ \mathbb{E}_{y\sim\pi_{\mathrm{ref}}(\bullet\mid x)} \!\left[r(x,y)\exp(r(x,y)/\beta)\right] }{ \mathbb{E}_{y\sim\pi_{\mathrm{ref}}(\bullet\mid x)} \!\left[\exp(r(x,y)/\beta)\right] }. \end{aligned} \end{align}\qquad{(2)}\]
The expectations in both the numerator and denominator of ?? are taken with respect to the reference policy \(\pi_{\mathrm{ref}}\). This makes it feasible to estimate \(V_\beta^*(x)\) offline, without training or sampling from \(\pi_\beta^*\) itself. Specifically, for each prompt, we sample a set of reference rollouts from \(\pi_{\mathrm{ref}}\) and score them using the same automated verifier. We then compute \(\widehat{V}_{\beta}(x)\), a plug-in estimate of ?? by replacing the expectations in the numerator and denominator with their empirical averages over these reference rollouts. These offline estimates are then used as the initial value estimates in BASIS. Below, we describe how the hyperparameter \(\beta\) is adaptively selected across training steps.
Online calibration. To illustrate how the KL-regularized optimal values \(V_\beta^*\) can be used to approximate the values \(V_{i,t}\) across training steps, consider two extreme cases:
At the first training step, the value \(V_{i,t}\) is computed under the initial policy, which is essentially the reference policy. This corresponds to setting \(\beta\) to infinity: the KL penalty becomes dominant, and the induced optimal policy \(\pi_\beta^*\) coincides with the reference policy.
When the algorithm converges, for sufficiently large \(t\), \(V_{i,t}\) approaches the value under the reward-optimal policy that maximizes 1 . This corresponds to setting \(\beta\) close to zero: the KL penalty vanishes, and the induced optimal policy \(\pi_\beta^*\) approaches the reward-optimal policy.
More generally, the KL-regularized optimal values provide a continuum of value estimates that approximate how the policy value evolves from the reference policy toward a reward-optimal policy during training. Motivated by this observation, for an arbitrary training step \(t\) and prompt \(x\), we use the family of values \(\{V_\beta^*(x):\beta\in\mathbb{B}\}\) to approximate the value of the current learning policy \(V_{i,t}\).
In our implementation, we set \(\mathbb{B}=[0.01,5]\). The calibration parameter \(\beta\) is selected adaptively at each training step, allowing its value to vary as training progresses. Specifically, at each training step \(t\), we select \(\beta\) by minimizing \[\label{eq:online-beta-selection} \beta_t \in \arg\min_{\beta\in\mathbb{B}}\; \frac{1}{|\mathcal{A}_{t,\beta}|} \sum_{i\in\mathcal{A}_{t,\beta}} \bigl(r_i^{(t)}-\widetilde{V}_{i,t,\beta}\bigr)^2,\tag{3}\] where \(\widetilde{V}_{i,t,\beta}\) and \(\mathcal{A}_{t,\beta}\) denote, respectively, the batchwise refined estimator and the active set obtained by using \(\widehat V_{\beta}(x_i)\) as the initial value estimate.
Figure 8 in Appendix 10 visualizes the selected \(\beta_t\). As expected, it generally decreases over training. Finally, we set the baseline \(b_i=\widetilde{V}_{i,t,\beta_t}\) and compute the advantage as \(\widehat A_{i,t}=r_i-b_i\).
5 Experiments↩︎
We conduct numerical experiments to evaluate BASIS along two dimensions: value estimation (Section 5.1), where we measure the accuracy of the estimated values, and policy optimization (Section 5.2), where we assess the downstream performance of the fine-tuned models.
5.1 Value estimation↩︎
We begin with a high-level summary of our findings and provide details in the following paragraphs. BASIS is highly sample efficient and robust for value estimation:
It reduces the REINFORCE++ value estimator’s MSE by \({\boldsymbol{6}9}\%\), and with only a single rollout per prompt, achieves smaller MSE than GRPO-type estimators with 8 rollouts (Figure 4 (a)).
Its estimator is also robust to reward heterogeneity within a batch, unlike the global baseline used by REINFORCE++ (Figure 4 (b)), and remains robust across prompt difficulty levels, unlike GRPO-type algorithms (Figure 4 (c)).
Moreover, unlike GRPO, BASIS often produces an informative nonzero advantage (Figure 4 (d)).
Setup. We post-train Qwen2.5-Math-7B with GRPO on a subset of the MATH dataset consisting of Level 3–5 problems [43]. We then use an intermediate training checkpoint to evaluate the accuracy of different value estimators.
Specifically, for each prompt, we first approximate its oracle value by averaging rewards over 256 Monte Carlo rollouts from the checkpoint. We then repeat the following procedure: In each repeat, we independently sample a batch of prompts from the same checkpoint, compute the BASIS, GRPO, RLOO and REINFORCE++ value estimators, and compute their squared errors against the Monte Carlo oracle values. We then average these squared errors over different repeats to obtain the MSE. More details are provided in Appendix 7.
Finding 1: BASIS is sample efficient. Figure 4 (a) reports the MSE of different value estimators averaged over all prompts. Compared with single-rollout baselines such as REINFORCE++, BASIS reduces the MSE by \({\boldsymbol{6}9}\%\). More strikingly, even with one rollout per prompt, BASIS achieves lower MSE than GRPO and RLOO with \({\boldsymbol{8}}\) rollouts. This demonstrates the utility of batchwise learning: by borrowing information across the entire batch, BASIS substantially improves value estimation without requiring repeated rollouts from the same prompt. Additionally, RLOO has larger MSE than GRPO, since its leave-one-out construction uses one fewer rollout for value estimation.
Finding 2: BASIS is robust. Figure 4 (b) reports the MSE of different value estimators across data batches grouped by the heterogeneity of their prompt-level values, measured by the standard deviation of \(\{V_{i,t}\}_{i=1}^B\). Figure 4 (c) reports the MSE across subsets of prompts grouped by their values.
We make three observations. (i) First, BASIS is nearly flat across all five groups in both figures, demonstrating its robustness to both within-batch reward heterogeneity and prompt difficulty. (ii) Second, REINFORCE++ is sensitive to both factors. As batch-level heterogeneity increases from 0.21 to 0.31, its MSE nearly doubles. This is expected because the variance of the global batch baseline used by REINFORCE++ increases naturally with the within-batch reward heterogeneity. Similarly, across prompt difficulty levels, REINFORCE++ performs best on medium-difficulty prompts but incurs much larger MSEs on easy and hard prompts, since the global batch mean pulls all baseline estimates toward the middle. (iii) Finally, GRPO and RLOO perform worst on medium-difficulty prompts. This is also expected for binary rewards: prompts with values near the middle have the largest reward variance.
Finding 3: BASIS is informative. Figure 4 (d) reports how often the estimated baseline is exactly \(0\) or \(1\), leading to a zero advantage and therefore a zero contribution to the policy gradient estimator. BASIS never returns a \(0\) or \(1\) baseline in this setting, and therefore consistently provides an informative signal. In contrast, GRPO often produces such extreme baselines, particularly for easy and hard prompts.
5.2 Policy optimization↩︎
We now show that improved value and advantage estimation leads to more effective policy optimization. In particular, our experiments demonstrate three major findings:
The BASIS advantage estimator can be used as a versatile plug-in component for a number of multi-rollout GRPO-type algorithms, roughly halving computation time while preserving most of their downstream performance (Table 1).
Compared with single-rollout REINFORCE-type baselines, BASIS often achieves better downstream accuracy, with absolute improvements of up to 44.8 and 9.5 percentage points over REINFORCE and REINFORCE++, respectively, while using roughly one-half of their computation (Table 1).
REINFORCE can collapse during training: its downstream accuracy may drop considerably as the number of training iterations increases. BASIS shows a much more stable learning curve, suggesting that more accurate value and advantage estimation stabilizes single-rollout policy optimization and helps avoid such collapse (see Figure 6 in Appendix 9).
Setup. We compare different algorithms by applying them to post-train Qwen3-4B on the DAPO-Math-17K training split [5] and evaluating the resulting models on seven benchmarks: AIME 2024, AIME 2025, AMC 2023, MATH-500 [43], Minerva Math [44], OlympiadBench [45], and HMMT 2025 [46]. For AIME, AMC, and HMMT, we report avg@32, the average accuracy of the resulting model over 32 sampled rollouts per problem. For MATH-500, Minerva Math, and OlympiadBench, we report accuracy from a single greedy deterministic rollout per problem.
To demonstrate the versatility of BASIS as a plug-in advantage estimation method, we combine it with the original GRPO and two representative follow-up variants: GPG [9], which removes the PPO step that requires importance sampling, and GSPO [6], which replaces the per-token importance ratio with a sequence-level importance ratio. In each of these combinations, BASIS modifies only the advantage estimator: we use the BASIS baseline with a single rollout per prompt, and compare it against three baselines: the original GRPO-type algorithm, which uses eight rollouts per prompt and the group mean as the baseline; its vanilla single-rollout version, which uses a zero baseline; and REINFORCE++, which uses a global batch baseline. To ensure a fair comparison, all algorithms use the same sampling budget of \(512\) rollouts per training step. Thus, the 8-rollout methods sample 64 prompts per training step, while the single-rollout methods sample 512 prompts per step. We train all baseline algorithms for \(300\) steps, corresponding to approximately \(1.1\) passes over the training set with \(17{,}398\) prompts for 8-rollout methods and approximately \(8.8\) passes for single-rollout methods. For BASIS, we train for only 150 steps, requiring roughly half the compute time. As shown below, despite this reduced training budget, BASIS achieves performance comparable to the multi-rollout methods and often better performance than the single-rollout baselines.
4.0pt
| Objective | Setting | Time | ||||||||
| 2024 | ||||||||||
| 2025 | ||||||||||
| 2023 | ||||||||||
| -500 | ||||||||||
| Math | ||||||||||
| Bench | ||||||||||
| 2025 | Avg | |||||||||
| GRPO | \(G=8\), step 300 | 15.5h | 0.312 | 0.298 | 0.716 | 0.880 | 0.467 | 0.537 | 0.088 | 0.471 |
| GRPO Vanilla | \(G=1\), step 300 | 20.7h | 0.023 | 0.021 | 0.331 | 0.444 | 0.279 | 0.234 | 0.015 | 0.192 |
| \(\quad+\)REINFORCE++ | \(G=1\), step 300 | 17.7h | 0.277 | 0.271 | 0.662 | 0.826 | 0.408 | 0.487 | 0.088 | 0.431 |
| \(\quad+\)BASIS | \(G=1\), step 150 | 8.3h | 0.303 | 0.281 | 0.758 | 0.892 | 0.426 | 0.559 | 0.093 | 0.473 |
| \(\Delta\) vs \(G=8\) | -7.2h | -0.8 | -1.7 | +4.2 | +1.2 | -4.0 | +2.2 | +0.4 | +0.2 | |
| \(\Delta\) vs Vanilla | -12.4h | +28.0 | +26.0 | +42.7 | +44.8 | +14.7 | +32.5 | +7.8 | +28.1 | |
| \(\Delta\) vs REINFORCE++ | -9.4h | +2.6 | +1.0 | +9.5 | +6.6 | +1.8 | +7.3 | +0.4 | +4.2 | |
| GPG | \(G=8\), step 300 | 14.0h | 0.369 | 0.286 | 0.788 | 0.880 | 0.426 | 0.570 | 0.123 | 0.492 |
| GPG Vanilla | \(G=1\), step 300 | 18.6h | 0.056 | 0.093 | 0.558 | 0.488 | 0.184 | 0.182 | 0.025 | 0.227 |
| \(\quad+\)REINFORCE++ | \(G=1\), step 300 | 12.9h | 0.272 | 0.281 | 0.748 | 0.874 | 0.426 | 0.558 | 0.082 | 0.463 |
| \(\quad+\)BASIS | \(G=1\), step 150 | 6.4h | 0.338 | 0.284 | 0.762 | 0.884 | 0.430 | 0.574 | 0.107 | 0.483 |
| \(\Delta\) vs \(G=8\) | -7.6h | -3.0 | -0.2 | -2.7 | +0.4 | +0.4 | +0.5 | -1.6 | -0.9 | |
| \(\Delta\) vs Vanilla | -12.2h | +28.2 | +19.2 | +20.4 | +39.6 | +24.6 | +39.2 | +8.2 | +25.6 | |
| \(\Delta\) vs REINFORCE++ | -6.5h | +6.7 | +0.3 | +1.4 | +1.0 | +0.4 | +1.6 | +2.5 | +2.0 | |
| GSPO | \(G=8\), step 300 | 14.4h | 0.365 | 0.296 | 0.794 | 0.896 | 0.463 | 0.588 | 0.117 | 0.502 |
| GSPO Vanilla | \(G=1\), step 300 | 13.0h | 0.234 | 0.241 | 0.751 | 0.868 | 0.423 | 0.586 | 0.105 | 0.458 |
| \(\quad+\)REINFORCE++ | \(G=1\), step 300 | 13.0h | 0.350 | 0.265 | 0.794 | 0.908 | 0.441 | 0.599 | 0.108 | 0.495 |
| \(\quad+\)BASIS | \(G=1\), step 150 | 7.2h | 0.320 | 0.269 | 0.754 | 0.888 | 0.460 | 0.565 | 0.114 | 0.481 |
| \(\Delta\) vs \(G=8\) | -7.2h | -4.5 | -2.7 | -4.0 | -0.8 | -0.4 | -2.2 | -0.3 | -2.1 | |
| \(\Delta\) vs Vanilla | -5.8h | +8.5 | +2.8 | +0.3 | +2.0 | +3.7 | -2.1 | +0.8 | +2.3 | |
| \(\Delta\) vs REINFORCE++ | -5.8h | -3.0 | +0.4 | -4.0 | -2.0 | +1.8 | -3.4 | +0.5 | -1.4 |
Additional implementation details as well as the computational cost of BASIS for baseline estimation are provided in Appendix 10. In Appendix 9.0.0.3, we report an additional study in which we post-train Qwen2.5-Math-7B and compare BASIS against the GRPO algorithm under the same protocol.
Finding 1. BASIS is competitive with 8-rollout methods while halving the compute budget. Table 1 reports the results. Compared with 8-rollout GRPO, BASIS achieves a slightly higher average accuracy across the seven benchmarks, with a gain of 0.2 percentage points, and outperforms GRPO on 4 of the seven benchmarks. Compared with 8-rollout GPG and GSPO, BASIS is slightly lower on average, by 0.9 and 2.1 percentage points, respectively. Importantly, these results are obtained with half the sampling budget: BASIS uses 76.8K sampled responses, compared with 153.6K for the 8-rollout baselines, reducing wall-clock training time by 7.2 to 7.6 hours across the three GRPO-type algorithms.
Finding 2. BASIS often outperforms single-rollout methods using roughly one-half of their computation. Table 1 further shows that BASIS improves the average accuracy across the seven benchmarks by 28.1 and 25.6 percentage points over single-rollout vanilla GRPO and GPG, respectively, and by 4.2 and 2.0 percentage points over their REINFORCE++ variants. These gains are positive on every individual benchmark, ranging from 0.3 to 44.8 percentage points. Importantly, BASIS achieves these improvements with substantially less training time, ranging from about half the compute used by the REINFORCE++ variants to about one-third of that used by single-rollout GPG.
Compared with single-rollout GSPO, the improvement is more modest. Using roughly 55% of the training time of the two GSPO single-rollout variants, BASIS improves the average accuracy over vanilla GSPO by 2.3 percentage points, but is 1.4 percentage points lower than its REINFORCE++ variant with half of the compute budget.
Finding 3. BASIS prevents collapse in single-rollout policy optimization. A closer look into the learning curves in Figure 6 (Appendix 9) reveals that vanilla GRPO and GPG collapse during training: vanilla GRPO barely learns, and its accuracy measure generally decreases over training. Vanilla GPG improves at first, but after peaking before the middle of training, its performance steadily declines. In contrast, BASIS does not suffer from this collapse. Together with the results in Section 5.1, these findings suggest that sample efficient value and advantage estimation stabilizes single-rollout policy optimization and helps prevent collapse.
6 Conclusion↩︎
This paper introduces BASIS for rollout-efficient RLVR. Methodologically, BASIS samples only one rollout per prompt during online training, while leveraging batchwise information sharing to improve value and advantage estimation (Figure 2). Empirically, BASIS is highly sample efficient and robust for value function estimation, and often produces informative advantage estimates (Figure 4). For policy optimization, BASIS often improves over single-rollout baselines, helps prevent collapse during training and achieves similar performance to multi-rollout baselines with substantially less computation (Table 1).
Limitations↩︎
This work has a few limitations. First, BASIS is designed for settings with verifiable rewards, and our experiments focus primarily on reasoning tasks with automated task verifiers. Extending our proposal to tasks with noisy, partial, or preference-based rewards may require additional calibration. Second, BASIS improves value and advantage estimation by borrowing information across prompts within the same training batch. A complementary line of work borrows information for the same prompt across different training steps [17]–[19]. These approaches could potentially be combined with BASIS to share information both across prompts within a batch and across training iterations, further improving the post-training algorithm’s sample efficiency.
Appendix↩︎
7 Baseline Estimator Experiments Details↩︎
This section provides the details of the experiments for the estimator evaluation in Section 5.1. All experiments are conducted at a fixed GRPO-trained checkpoint \(\pi_{\theta_t}\), initialized from Qwen2.5-Math-7B and optimized on the Level 3–5 subset of the MATH dataset [43]. For each repeat, we sample a batch of prompts and estimate each prompt’s oracle value \(V_{i,t}\) using 256 Monte Carlo rollouts from the checkpoint. The baseline estimators are then constructed from a separate set of reward samples from the same checkpoint, so that the oracle estimate and the evaluated baselines are computed from disjoint samples.
7.0.0.1 Baseline algorithms.
We compare BASIS with three baseline algorithms here:
GRPO uses the within-prompt group reward mean as its baseline: \[b^{\mathrm{GRPO}}_{i,g} = \bar r_i := \frac{1}{G}\sum_{\ell=1}^{G} r_{i,\ell}\]
RLOO uses a leave-one-out group baseline, where the baseline for each sample is computed from the other completions generated from the same prompt: \[b^{\mathrm{RLOO}}_{i,g} = \bar r_{i,-g} := \frac{1}{G-1}\sum_{\ell\ne g} r_{i,\ell},\]
REINFORCE++ uses the reward mean within the current batch as its baseline: \[b^{\mathrm{R++}}_{i} = \bar r_{\mathrm{batch}} := \frac{1}{B}\sum_{j=1}^{B}r_{j},\]
BASIS corresponds to the information-borrowing estimator defined by Eqs. 2 and ?? with single-rollout settings (\(G=1\)).
7.0.0.2 Group-size sweep.
This experiment evaluates how the estimator quality changes with the number of within-prompt rollouts. We fix the batch size at \(B=64\) and vary \(G\in\{1,2,4,8\}\) for GRPO and \(G\in\{2,4,8\}\) for RLOO (which requires at least two rollouts to leave one out), while BASIS is evaluated in the single-rollout setting with \(G=1\). For each repeat, we draw a batch of prompts without replacement and sample up to eight rewards per prompt. To ensure a paired comparison across different values of \(G\), the estimator for each \(G\) is computed using the first \(G\) rewards from the same sampled reward set. The reported metric is the mean squared error \((\widehat V_{i,t}-V_{i,t})^2\), averaged over prompts and then over 10 repeats.
7.0.0.3 Batch heterogeneity experiment.
This experiment examines how baseline estimation quality varies with the heterogeneity of the sampled batch. We fix \(B=64\) and sample 500 batches so that a broad range of batch-level heterogeneity is represented. For each batch \(b\), we define its heterogeneity score as \(s_b=\operatorname{std}_{i\in b}(V_{i,t}),\) which is the population standard deviation of the 64 oracle prompt values in that batch. The spread bins are constructed post hoc from the empirical range of these 500 scores. The minimum and maximum observed values are \(0.206\) and \(0.307\), and we divide this interval into five bins using uniformly spaced edges. This gives the bins \([0.206,0.226)\), \([0.226,0.246)\), \([0.246,0.266)\), \([0.266,0.287)\), and \([0.287,0.307]\). Within each bin, we report the baseline MSE against \(V_{i,t}\), first averaged over prompts within each batch and then averaged across batches in the bin.
7.0.0.4 Per-difficulty MSE analysis.
This experiment evaluates estimator behavior across different prompt-difficulty levels without constructing difficulty-conditioned batches. For each repeat, we first sample a batch of \(B=64\) prompts without conditioning on difficulty. Then, the baseline estimate for each prompt is computed using the full sampled batch. Only after these estimates are obtained do we stratify prompts by their oracle values into five difficulty bins: \([0,0.2)\), \([0.2,0.4)\), \([0.4,0.6)\), \([0.6,0.8)\), and \([0.8,1]\) to keep the comparison fair. In particular, forming batches separately within each difficulty bin would artificially reduce within-batch heterogeneity, thereby making the cross-prompt baseline in BASIS easier to estimate. Summaries are computed by first averaging within each batch-bin group and then across 10 repeats. BASIS uses a single-rollout setting in this experiment, while GRPO is shown with \(G\in\{1,2,4,8\}\) and RLOO is shown with \(G\in\{2,4,8\}\) due to its leave-one-out strategy. We report both the baseline MSE against \(V_{i,t}\) and the probability that the estimated baseline is exactly \(0\) or \(1\), corresponding to a collapsed signal for binary rewards.
8 Supplementary Information-Sharing Baselines↩︎
In Section 4, we construct the BASIS baseline as a weighted average of rewards from the same batch, with data-adaptive weights chosen to form a best linear unbiased baseline; we refer to this main estimator as UNB for unbiasedness in this section. More broadly, batchwise information can be shared in other ways, such as using weighted averages without the unbiasedness constraint, or using importance weights based on ratios of initial value estimates. In this appendix, we study two such alternatives, namely, the Variance-OPtimized shrinkage baseline (VOP) and the Ratio-average Value-Guided baseline (RVG). On Qwen2.5-Math-7B at \(G{=}1\), VOP and RVG perform on par with UNB and match or exceed GRPO \(G{=}8\) on most math benchmarks while using roughly half the training time (Appendix 9.0.0.3, Table 3).
Before defining each variant, we note that both rules reuse the same offline initial value estimator and the same calibration method to select \(\beta_t\) as UNB. We keep similar notations from Section 4: \(\widehat V_{i,t}=\widehat V_{\beta_t}(x_i)\), \(\widehat\sigma_i^2=\widehat V_{i,t}(1-\widehat V_{i,t})\), and \(\mathcal{A}_t\) is the active set in Algorithm 3. The formulas below apply only to active prompts; prompts outside \(\mathcal{A}_t\) use the implementation fallback described in Appendix 10. For reference, the UNB rule used in the main text can be written, after plugging \(\widehat V_{i,t}\) and \(\widehat\sigma_i^2\) into Eq. ?? , as \[\widetilde{V}_{i,t}^{\mathrm{UNB}} = \widehat V_{i,t}\, \frac{\displaystyle \sum_{j\in\mathcal{A}_t\setminus\{i\}} \widehat V_{j,t} r_j/\widehat\sigma_j^2}{\displaystyle \sum_{j\in\mathcal{A}_t\setminus\{i\}} \widehat V_{j,t}^2/\widehat\sigma_j^2}, \qquad i\in\mathcal{A}_t . \label{eq:app-unb-baseline}\tag{4}\] The leave-one-out exclusion is what gives the main estimator its unbiasedness interpretation. Both variants below share the same idea of weighting the batch rewards by the offline values \(\widehat{V}_{i,t}\), and they differ only in the weighting rules.
8.0.0.1 Variance-OPtimized shrinkage baseline (VOP).
It uses the same weighting as UNB except that it drops the unbiasedness constraint. The following proposition is the unconstrained counterpart of Proposition 1; its proof follows the same quadratic calculation and is given in Appendix 11.
Proposition 3 (Unconstrained MSE shrinkage). Fix a training step \(t\), a target prompt \(i\), and condition on the prompt batch \(\mathcal{X}_B:=\{x_k\}_{k=1}^B\). Among all leave-one-out linear baselines \(b_i=\sum_{j\ne i}w_{ij}r_j\), without imposing the unbiasedness constraint, the weights minimizing \(\mathbb{E}[(V_{i,t}-b_i)^2\mid\mathcal{X}_B]\) are \[w_{ij}^{\mathrm{VOP}} = \frac{V_{i,t}V_{j,t}/\sigma_j^2}{1+\sum_{k\ne i}V_{k,t}^2/\sigma_k^2}, \qquad j\ne i .\]
By Proposition 3, for each active prompt \(i\), we define the VOP baseline \[\widetilde{V}_{i,t}^{\mathrm{VOP}} = \widehat V_{i,t}\, \frac{\displaystyle\sum_{j\in\mathcal{A}_t\setminus\{i\}}\widehat V_{j,t} r_j/\widehat\sigma_j^2}{\displaystyle 1+\sum_{j\in\mathcal{A}_t\setminus\{i\}}\widehat V_{j,t}^2/\widehat\sigma_j^2}, \quad i\in\mathcal{A}_t . \label{eq:app-vop-baseline}\tag{5}\] Compared with the UNB projection in Eq. 4 , the additional \(1\) in the denominator shrinks the borrowed baseline toward zero, trading unbiasedness for stability when the active set is small.
8.0.0.2 Ratio-average Value-Guided baseline (RVG).
It first removes the prompt-level value scale from each observed reward, averages the resulting normalized ratios across the active batch, and then rescales the batch-level quantity back to prompt \(i\): \[\widetilde{V}_{i,t}^{\mathrm{RVG}} = \frac{\widehat V_{i,t}}{|\mathcal{A}_t|-1} \sum_{j\in\mathcal{A}_t\setminus\{i\}} \frac{r_j}{\widehat V_{j,t}}, \quad i\in\mathcal{A}_t. \label{eq:app-ratio-baseline}\tag{6}\] Intuitively, dividing \(r_j\) by \(\widehat{V}_{j, t}\) normalizes away the prompt-level difficulty so that \(r_j / \widehat{V}_{j, t}\) is comparable across prompts; multiplying by \(\widehat{V}_{i, t}\) rescales the batch average back to prompt \(i\).
9 Additional Online Experiment Results↩︎
The main-text Qwen3-4B comparison reports performance at fixed checkpoints. This appendix collects the underlying per-step compute budget and the full evaluated trajectories.
9.0.0.1 Compute budget.
Each Qwen3-4B experiment uses the same \(512\) sampled responses per step. The \(G{=}8\) rows sample \(64\) prompts \(\times\) \(8\) responses per prompt; the \(G{=}1\) rows (Vanilla, REINFORCE++, or BASIS) sample \(512\) distinct prompts \(\times\) \(1\) response per prompt. The total response budget at step \(300\) is therefore identical (\(153{,}600\) sampled responses for every step-\(300\) row).
4pt
| Objective | Setting | Step | Responses | Time |
|---|---|---|---|---|
| GRPO | \(G=8\) | 300 | 153.6K | 15.5h |
| GRPO Vanilla | \(G=1\) | 300 | 153.6K | 20.7h |
| \(\quad+\)REINFORCE++ | \(G=1\) | 300 | 153.6K | 17.7h |
| \(\quad+\)BASIS | \(G=1\) | 150 | 76.8K | 8.3h |
| \(\quad+\)BASIS | \(G=1\) | 300 | 153.6K | 16.6h |
| GPG | \(G=8\) | 300 | 153.6K | 14.0h |
| GPG Vanilla | \(G=1\) | 300 | 153.6K | 18.6h |
| \(\quad+\)REINFORCE++ | \(G=1\) | 300 | 153.6K | 12.9h |
| \(\quad+\)BASIS | \(G=1\) | 150 | 76.8K | 6.4h |
| \(\quad+\)BASIS | \(G=1\) | 300 | 153.6K | 12.7h |
| GSPO | \(G=8\) | 300 | 153.6K | 14.4h |
| GSPO Vanilla | \(G=1\) | 300 | 153.6K | 13.0h |
| \(\quad+\)REINFORCE++ | \(G=1\) | 300 | 153.6K | 13.0h |
| \(\quad+\)BASIS | \(G=1\) | 150 | 76.8K | 7.2h |
| \(\quad+\)BASIS | \(G=1\) | 300 | 153.6K | 14.3h |
9.0.0.2 Full trajectories and ablation studies on the contributions of BASIS.
Figures 6 and 7 extend the Qwen3-4B comparison to step \(150-300\) and isolate the contribution of BASIS in two stages on the same single-rollout budget. Figure 6 compares the vanilla \(G{=}1\) version of each objective against the version that uses BASIS as the baseline, and exposes the single-rollout failure mode: GRPO and GPG Vanilla collapse after step \({\approx}150\). Only GSPO survives without modification (perhaps due to the variance reduction from the length-normalized importance sampling ratio and sequence-level loss aggregation). BASIS lifts every objective onto a monotonically improving trajectory. Figure 7 re-runs the comparison against a much stronger single-rollout baseline—REINFORCE++ with the global batch-mean as \(b_i\)—under which all three objectives train stably with naive cross-prompt information sharing. Even on this harder bar, BASIS dominates uniformly, with a visible gap from step \({\sim}100\) onward and reaches higher accuracies across all seven benchmarks. Taken together, the two figures separate “having any cross-prompt signal” (the improvement from vanilla to REINFORCE++) from “exploiting cross-prompt information” (the improvement from REINFORCE++ to BASIS); both increments are positive, but the second is what BASIS substantially contributes.
9.0.0.3 Qwen2.5-Math-7B online RL ablation.
We further ran the same online-RL protocol on Qwen2.5-Math-7B, comparing the three BASIS weighting variants under a matched per-step response budget. Qwen2.5-Math-7B was the first model on which we developed the cross-prompt baseline; we report these numbers as an ablation that (i) confirms BASIS is not Qwen3-specific, and (ii) lets us inspect the three weighting variants side-by-side.
4pt
| Method | |||||||
| 2024 | |||||||
| 2025 | |||||||
| 2023 | |||||||
| -500 | |||||||
| Math | |||||||
| Bench | |||||||
| 2025 | |||||||
| GRPO \((G=8)\) | 0.244 | 0.102 | 0.597 | 0.762 | 0.324 | 0.406 | 0.019 |
| \(\quad+\)BASIS-UNB \((G=1)\) | 0.245 | 0.107 | 0.655 | 0.780 | 0.309 | 0.409 | 0.019 |
| \(\quad+\)BASIS-RVG \((G=1)\) | 0.256 | 0.117 | 0.622 | 0.773 | 0.298 | 0.417 | 0.015 |
| \(\quad+\)BASIS-VOP \((G=1)\) | 0.240 | 0.118 | 0.634 | 0.768 | 0.303 | 0.416 | 0.018 |
The three BASIS variants at \(G{=}1\) match or exceed GRPO \(G{=}8\) on five of seven benchmarks: UNB on AMC 2023 and MATH-500, RVG on AIME 2024 and OlympiadBench, VOP on AIME 2025. The cross-prompt baseline therefore generalizes across both the model family (Qwen2.5-Math vs.Qwen3) and the three weighting variants, suggesting that the information-sharing idea is not tied to a particular choice of weights.
10 Implementation Details for Online Experiments↩︎
10.0.0.1 Offline value-table generation: one-time cost.
Before online RL, we sample \(n\) completions from the frozen reference policy on each training prompt and score them with the same verifier used for online rewards. For each prompt \(x_i\) the cache stores the sample count \(n_i = n\) and the empirical mean reward \(\hat{p}_i\). We use \(n{=}64\) for Qwen3-4B and \(n{=}32\) for Qwen2.5-Math-7B; both are large enough that the empirical reward mean is essentially saturated for binary rewards, and we recommend \(n \in \{32, 64\}\) depending on the available reference-sampling budget.
For binary rewards we use the same plug-in value formulation as in the main text, \[\widehat V_\beta(x_i) = \frac{\hat{p}_i \exp({1/\beta})}{1-\hat{p}_i + \hat{p}_i \exp({\,1/\beta})},\] the expected reward under the KL-tilted reference policy at \(\beta\). We evaluate it on a fixed grid of \(230\) values of \(\beta\) spanning \([0.01, 5.0]\) (\(200\) steps of width \(0.01\) in \([0.01, 2.00]\) and \(30\) steps of width \(0.1\) in \([2.1, 5.0]\)), giving a \(17{,}398 \times 230\) table (about \(16\) MB on disk). The trajectory of calibrated \(\beta\) is plotted in Figure 8. The dominant precompute cost is the reference-rollout sampling, which takes a few hours on the same four-GPU node used for training; the closed-form \(\widehat V_\beta\) evaluation that follows runs in seconds on a single CPU. After these calculations, the initial estimator can be reused across the three policy objectives and the three weighting variants (UNB / RVG / VOP); amortized over the BASIS rows reported for Qwen3-4B, the per-experiment precompute overhead is well under \(5\,\%\) of training wall-clock.
![Figure 8: Calibrated values of \beta_t during BASIS training on Qwen3-4B when coupled with GRPO, GPG, and GSPO. At each training step the calibrator selects \beta_t by minimizing Eq. 3 over the precomputed 230-point grid \beta\in[0.01, 5.0]. All three runs start near the upper end of the grid and settle into a narrow band around \beta\approx 0.4 by step {\approx}80 and remain there. Solid lines show the smoothed calibrated \beta_t values; lighter curves in the same colors show the corresponding raw per-step selected \beta_t values.](/article/2605.27293/latex/figure/qwen3_basis_beta_calibration.png "fig:")
10.0.0.2 Online cost.
At each training step, BASIS chooses \(\beta_t\) by minimizing Eq. 3 over the precomputed grid. This reduces to taking an argmin over the 230 precomputed grid values for each of the 512 active prompts, costing well under a millisecond per step on a single GPU.
10.0.0.3 Active set and fallback.
Prompts whose selected offline value falls outside the active set use the vanilla \(G=1\) fallback; all other prompts use the cross-prompt BASIS baseline. We set \(\epsilon = 10^{-6}\) for the active set threshold throughout.
10.0.0.4 Per-objective implementation.
We use the implementations from verl [47] unchanged, replacing only the advantage estimator with BASIS in the
corresponding rows.
10.0.0.5 Training hyperparameters.
The Qwen2.5-Math-7B experiments use max prompt length \(1024\), max response length \(2048\), learning rate \(10^{-6}\), rollout temperature \(1.0\), top-\(p{=}1.0\), top-\(k{=}-1\), DAPO-Math-17K training data [5], on four GH200 GPUs. The Qwen3-4B experiments use the same learning rate and temperature with max response length \(4096\), on four GH200 GPUs. In both cases the response budget is \(512\) per optimization step. PPO mini-batch size is \(256\) for \(G=1\) runs and \(32\) for \(G=8\) runs, respectively, so that each optimization step performs \(2\) PPO inner updates in both runs. We did not enable KL regularization, following the recent consensus in e.g., [5].
11 Proof↩︎
11.1 Proof of Proposition 1↩︎
Proof. Fix a training step \(t\), a target prompt \(i\), and condition on the prompt batch \(\mathcal{X}_B:=\{x_k\}_{k=1}^B\). Under the independent rollout sampling used by BASIS, the rewards from different prompts are conditionally uncorrelated given the prompt batch. Hence, for any leave-one-out linear baseline \(b_i=\sum_{j\ne i}w_{ij}r_j\), \[\mathbb{E}[b_i\mid \mathcal{X}_B] = \sum_{j\ne i}w_{ij}V_{j,t}.\] The unbiasedness constraint is therefore \[\sum_{j\ne i}w_{ij}V_{j,t}=V_{i,t}.\] On this constrained set, the conditional MSE equals the conditional variance: \[\begin{align} \mathbb{E}[(V_{i,t}-b_i)^2\mid \mathcal{X}_B] &= \operatorname{Var}(b_i\mid \mathcal{X}_B)\\ &= \sum_{j\ne i}w_{ij}^2\sigma_j^2 . \end{align}\] Thus the optimal weights solve the quadratic program \[\begin{align} \min_{(w_{ij})_{j\ne i}}\quad &\sum_{j\ne i}w_{ij}^2\sigma_j^2\\ \text{s.t.}\quad &\sum_{j\ne i}w_{ij}V_{j,t}=V_{i,t} . \end{align}\] In the non-degenerate case \(\sum_{k\ne i}V_{k,t}^2/\sigma_k^2>0\), the Lagrangian \[\begin{align} \mathcal{L}(w_i,\lambda) = \sum_{j\ne i}w_{ij}^2\sigma_j^2 +\lambda\Bigl(\sum_{j\ne i}w_{ij}V_{j,t}-V_{i,t}\Bigr) \end{align}\] has first-order condition \[2w_{ij}\sigma_j^2+\lambda V_{j,t}=0, \qquad j\ne i.\] Therefore \(w_{ij}=-\lambda V_{j,t}/(2\sigma_j^2)\). Substituting this expression into the unbiasedness constraint gives \[-\frac{\lambda}{2}\sum_{k\ne i}\frac{V_{k,t}^2}{\sigma_k^2}=V_{i,t}, \qquad \lambda = -\frac{2V_{i,t}}{\sum_{k\ne i}V_{k,t}^2/\sigma_k^2}.\] Hence \[w_{ij} = \frac{V_{i,t}V_{j,t}/\sigma_j^2}{\sum_{k\ne i}V_{k,t}^2/\sigma_k^2}, \qquad j\ne i,\] which is Eq. ?? . Since the objective is strictly convex whenever \(\sigma_j^2>0\), these weights are the unique minimizer. ◻
11.2 Proof of Proposition 2↩︎
Proof. Fix a prompt \(x\) and \(\beta>0\). We first derive the optimizer of the KL-regularized objective using the same variational calculation as in DPO-style derivations [41]. Let \[p_y=\pi(y\mid x),\qquad p_y^{\mathrm{ref}}=\pi_{\mathrm{ref}}(y\mid x),\] where the sums below range over responses in the support of \(\pi_{\mathrm{ref}}(\bullet\mid x)\). For this fixed prompt, the objective is \[\begin{align} J_x(p) &= \sum_y p_y r(x,y) - \beta\sum_y p_y \log\frac{p_y}{p_y^{\mathrm{ref}}}. \end{align}\] The maximization is over distributions \(p\) satisfying \(\sum_y p_y=1\). Its Lagrangian is \[\begin{align} \mathcal{L}(p,\lambda) &= \sum_y p_y r(x,y) - \beta\sum_y p_y \log\frac{p_y}{p_y^{\mathrm{ref}}}\\ &\quad +\lambda\Bigl(\sum_y p_y-1\Bigr). \end{align}\] For any response \(y\) with \(p_y^{\mathrm{ref}}>0\), the first-order condition is \[\begin{align} 0 &= \frac{\partial\mathcal{L}}{\partial p_y}\\ &= r(x,y) - \beta\!\left( \log\frac{p_y}{p_y^{\mathrm{ref}}}+1 \right) + \lambda . \end{align}\] Solving this equation gives \[p_y = C\,p_y^{\mathrm{ref}} \exp\!\left(r(x,y)/\beta\right),\] where \(C=\exp(\lambda/\beta-1)\) does not depend on \(y\). Enforcing \(\sum_y p_y=1\) yields \[\begin{align} C^{-1} &= \sum_y p_y^{\mathrm{ref}} \exp\!\left(r(x,y)/\beta\right)\\ &= \mathbb{E}_{y\sim\pi_{\mathrm{ref}}(\bullet\mid x)} \!\left[ \exp\!\left(r(x,y)/\beta\right) \right] =:Z_\beta(x). \end{align}\] Therefore the unique maximizer is \[\pi_\beta^*(y\mid x) = \frac{ \pi_{\mathrm{ref}}(y\mid x) \exp\!\left(r(x,y)/\beta\right) }{ Z_\beta(x) }.\] The objective is concave in \(p\) because it is a linear reward term plus \(-\beta\) times a convex KL term, so the stationary point is globally optimal.
Now substitute this optimizer into the reward value: \[\begin{align} V_\beta^*(x) &= \sum_y \pi_\beta^*(y\mid x) r(x,y)\\ &= \frac{N_\beta(x)}{Z_\beta(x)}, \end{align}\] where \[\begin{align} N_\beta(x) &:= \sum_y p_y^{\mathrm{ref}} r(x,y) \exp\!\left(r(x,y)/\beta\right). \end{align}\] Writing the sums in \(N_\beta(x)\) and \(Z_\beta(x)\) as expectations under \(\pi_{\mathrm{ref}}(\bullet\mid x)\) gives Eq. ?? . ◻
11.3 Proof of Proposition 3↩︎
Proof. Fix a training step \(t\), a target prompt \(i\), and condition on the prompt batch \(\mathcal{X}_B\). For a leave-one-out linear baseline \(b_i=\sum_{j\ne i}w_{ij}r_j\), the conditional MSE decomposes as \[\begin{align} &\mathbb{E}[(V_{i,t}-b_i)^2\mid \mathcal{X}_B] \\ &\quad = \Bigl(V_{i,t}-\sum_{j\ne i}w_{ij}V_{j,t}\Bigr)^2 +\sum_{j\ne i}w_{ij}^2\sigma_j^2 . \end{align}\] This is the same quadratic objective as in the proof of Proposition 1, but without the linear unbiasedness constraint. Its first-order condition is \[\begin{align} &-2V_{j,t}\Bigl(V_{i,t}-\sum_{k\ne i}w_{ik}V_{k,t}\Bigr) +2w_{ij}\sigma_j^2=0, \\ &\qquad j\ne i . \end{align}\] Let \(c=V_{i,t}-\sum_{k\ne i}w_{ik}V_{k,t}\). Then \[w_{ij}=\frac{cV_{j,t}}{\sigma_j^2}.\] Substituting this expression into the definition of \(c\) gives \[c = V_{i,t} -c\sum_{k\ne i}\frac{V_{k,t}^2}{\sigma_k^2}, \qquad c = \frac{V_{i,t}}{1+\sum_{k\ne i}V_{k,t}^2/\sigma_k^2}.\] Therefore \[w_{ij} = \frac{V_{i,t}V_{j,t}/\sigma_j^2}{1+\sum_{k\ne i}V_{k,t}^2/\sigma_k^2}, \qquad j\ne i,\] which proves the claim. The objective is strictly convex whenever \(\sigma_j^2>0\), so the minimizer is unique. ◻