Single-stream Policy Optimization — part 3/4
Cleaned-text code points [29992, 45740). Bibliography omitted here; source.md includes it.
Signal Stability and Advantage Variance. Figure 3b compares advantage variance across methods. As a reference, the green line (“SPO No Baseline”) corresponds to raw rewards, i.e., the high-variance signal faced by vanilla policy gradient. SPO’s history-informed baseline (red) delivers a substantial, stable variance reduction of nearly 50%. For GRPO, computing variance only over non-degenerate samples (“GRPO Effective”, blue) reveals a highly volatile signal with the largest variance among all conditions, exceeding even “SPO No Baseline”. We conclude that SPO’s baseline is effective, yielding stable, low-variance gradients, whereas GRPO’s on-the-fly baseline is noisy and destabilizing when it produces a signal. The apparent stability of GRPO’s overall variance is driven by the prevalence of zero-variance degenerate samples and thus reflects inefficiency rather than robustness.
### 5.4 Agentic Training Demonstrations
We perform simulations to demonstrate the practical implications of SPO’s group-free design in agentic training scenarios, where interaction times can be highly variable. Group-based methods like GRPO suffer from a critical scalability bottleneck due to their inherent synchronization barrier, a problem that is particularly acute in agentic tasks involving multi-turn tool use or long-horizon reasoning.
Figure 4 illustrates this fundamental issue. In an idealized low-variance setting (Figure 4a ), where all agentic trajectories complete in similar times, the group-based approach is efficient. However, in a more realistic high-variance setting (Figure 4b ) characterized by long-tail latencies, a single slow-running trajectory (a “straggler”) can stall the entire group. In our simulation, while most samples finish in under 133 133 seconds, the group must wait 508 508 seconds for its slowest member. This bottleneck effect forces faster samples to remain idle, severely hindering training throughput and wasting computational resources.
(a) Low-variance Group (b) High-variance Group
(a) Group-base (b) Group-free (c) Strategy Comparison
SPO’s group-free architecture directly resolves this inefficiency. Figure 5 compares the time required to assemble a training batch of 24 samples using both strategies. The group-based approach (left), even when optimized by running 6 groups in parallel and selecting the 3 fastest, is still constrained by the slowest trajectory within those selected groups, taking 486 s 486s to complete. In contrast, the group-free approach (middle) leverages asynchrony by starting 48 independent samples and simply collecting the first 24 to finish. In our simulated scenario, this process takes only 112 s 112s , as it naturally filters out the slow outliers. As shown on the right, this architectural difference results in a significant 4.35 × \mathbf{4.35\times} speedup in this realistic agentic simulation. Simulations show that SPO’s architecture can lead to significant throughput gains, making it a more scalable and robust foundation for training on complex, long-horizon agentic tasks.
## 6 Conclusions
We identified critical inefficiencies in group-based policy optimization methods for LLMs, namely computational waste from degenerate groups and scalability bottlenecks from synchronization. To address these, we proposed Single-stream Policy Optimization (SPO), a principled return to the classic single-stream paradigm. SPO replaces the noisy, per-group baseline with a persistent KL-adaptive value tracker and global advantage normalization, creating a more stable and efficient learning signal.
Our empirical results demonstrate that SPO’s design is not merely simpler, but superior. It consistently outperformed GRPO on complex reasoning tasks while eliminating the systemic flaws of its group-based counterpart. By demonstrating that a well-designed single-stream approach can surpass more complex methods, our work challenges the prevailing trend of adding incidental complexity to RL algorithms for LLMs. SPO provides a robust, scalable, and efficient foundation for future research in agentic and reasoning model training, highlighting the enduring power of foundational reinforcement learning principles. Future work can focus on refining the best practices for applying SPO and exploring its limits, pushing its effectiveness to power the next generation of reasoning and agentic LLMs.
## Appendix A SPO Initialization
We show the SPO initialization procedure in Algorithm 2 . In the experiments, we use n 0 = 8 n_{0}=8 to have a good estimation of initial baseline tracker. We ablate the setting where we use no offline estimation and rely on the online moving estimator in Section E .
Practically, one may concern about the extra cost during the offline estimation of v ^ 0 \hat{v}_{0} . We note that we share the offline estimation for our experiments so that people could skip this process and directly load our datasets, and there are datasets like Polaris [ 2 ] that pre-compute accuracy for Deepseek-R1-Distill-Qwen-7B [ 11 ] . The cost can be amortized across the experiments people run themselves, and we will share more (dataset, base_model) combinations to facilitate experiment efficiency.
## Appendix B Batch Extensions
We could adapt Single-stream Policy Optimization (SPO) into a prompt-repetition scheme 4 4 4 Batch SPO or BSPO , processing each prompt G G times per batch with a shared baseline estimator v ^ \hat{v} to better handle sparse rewards. Our method’s primary advantage over GRPO lies in its asynchronous nature, achieved by removing the group synchronization barrier. Treating repeated prompts as independent trajectories unlocks two key efficiency improvements. First, it enables robust handling of long-tail generation issues, as slow or problematic trajectories can be terminated early, discarded, or managed via partial rollouts [ 20 ] without delaying the entire batch. Second, it facilitates a more flexible batching strategy. By over-sampling the number of initial prompts (e.g., by 50%), a full training batch can be assembled from the first-finishing trajectories, allowing the optimization step to proceed immediately without waiting for stragglers. This design significantly reduces training latency compared to the rigid group synchronization required by GRPO. When tackling hard prompts, the batch extensions may help obtain learning signals more quickly.
## Appendix C Comparisons against GRPO
### C.1 Inefficiency of Dynamic Sampling
To address the information loss from degenerate sample groups (where all rewards are identical), methods like DAPO [ 42 ] employ dynamic sampling . This strategy continues generating responses for a prompt until the collected set contains at least one success and one failure, guaranteeing a non-zero advantage. While effective at ensuring a learning signal, this approach can be extremely data- and time-inefficient. Note that when people report performance with dynamic sampling, the “steps” indicate the learning steps rather than the sampling steps, where the latter is normally a multiple of the former (e.g., 5 × 5\times ).
We can formalize the expected computational cost. For a prompt x x with true success probability p = V π ( x ) p=V_{\pi}(x) , let N N be the number of samples required to obtain a non-degenerate set. We have: 𝔼 [ N ∣ p ] = p ( 1 + 1 1 − p ) + ( 1 − p ) ( 1 + 1 p ) = 1 p ( 1 − p ) − 1 . \mathbb{E}[N\mid p]=p\Bigl(1+\tfrac{1}{1-p}\Bigr)+(1-p)\Bigl(1+\tfrac{1}{p}\Bigr)=\frac{1}{p(1-p)}-1. This cost grows hyperbolically as the policy becomes either proficient ( p → 1 p\to 1 ) or incompetent ( p → 0 p\to 0 ). For example, if a policy has a 10% success rate ( p = 0.1 p=0.1 ), the expected number of generations needed to collect both a success and a failure is 𝔼 [ N ] ≈ 10.11 \mathbb{E}[N]\approx 10.11 . In contrast, SPO requires exactly one sample per prompt and uses its adaptive curriculum to actively de-prioritize these inefficient prompts, allocating resources to where learning is most effective. This makes SPO fundamentally more scalable and computationally efficient.
### C.2 Variance Reduction for Policy Gradient
The per-sample policy gradient is g = A ( x , y ) ∇ θ log π θ ( y | x ) g=A(x,y)\nabla_{\theta}\log\pi_{\theta}(y|x) , where the advantage A A is an estimate of the expected return over a baseline. The variance of this gradient, Var [ g ] \mathrm{Var}[g] , is a key driver of training efficiency. We analyze how the construction of the advantage A A leads to significant variance differences between GRPO and SPO.
GRPO’s High-Variance Group-Based Advantage : GRPO computes advantages by comparing outcomes within a small group of G G ( G = 8 , 16 , … G=8,16,... ) samples generated for the same prompt. The normalized advantage for sample x x with binary reward r ∈ { 0 , 1 } r\in\{0,1\} is A ~ GRPO = r − μ 𝒢 σ 𝒢 + ϵ \tilde{A}_{\text{GRPO}}=\frac{r-\mu_{\mathcal{G}}}{\sigma_{\mathcal{G}}+\epsilon} , where both the baseline μ 𝒢 \mu_{\mathcal{G}} (e.g., the group mean 1 G ∑ j r j \frac{1}{G}\sum_{j}r_{j} ) and the standard deviation σ 𝒢 \sigma_{\mathcal{G}} are estimated from the same small group of G G samples. This coupled, small-sample estimation introduces three fundamental sources of variance: • Noisy Baseline (Numerator): The baseline μ 𝒢 \mu_{\mathcal{G}} , estimated from only G G samples, where G G is small, is a high-variance quantity. This inflates the variance of the unnormalized advantage ( r − μ 𝒢 ) (r-\mu_{\mathcal{G}}) by a factor of ( 1 + 1 G ) (1+\frac{1}{G}) compared to using an optimal baseline.
• Noisy Scaling (Denominator): The standard deviation σ 𝒢 \sigma_{\mathcal{G}} , estimated from only G G samples, is also highly variable. Scaling the gradient by this noisy random variable further increases total variance.
• Information Loss (Degeneracy): When all rewards in the group are identical (e.g., all 0s or all 1s), the advantage for every sample becomes zero, providing no gradient signal. This event, which occurs with probability Z G ( p ) = p G + ( 1 − p ) G Z_{G}(p)=p^{G}+(1-p)^{G} where p = V π ( x ) p=V^{\pi}(x) , effectively reduces the batch size and inflates variance by a factor of 1 / ( 1 − Z G ( p ) ) 1/(1-Z_{G}(p)) , an issue that is especially severe for easy ( p ≈ 1 p\approx 1 ) or hard ( p ≈ 0 p\approx 0 ) prompts.
SPO’s Low-Variance Decoupled Advantage : In contrast, SPO is designed to minimize these variance sources by decoupling the advantage calculation from the current group of samples. It uses an action-independent baseline b = v ^ ( x ) b=\hat{v}(x) from a historical tracker, which provides a stable, low-variance estimate of the true success probability p p . The advantage is simply A SPO = batch_norm ( r ( x , y ) − v ^ ( x ) ) A_{\text{SPO}}=\texttt{batch\_norm}(r(x,y)-\hat{v}(x)) . Crucially, SPO then applies global normalization [ 31 , 3 , 25 ] , scaling all advantages in a large batch of size B ≫ G B\gg G by a single, stable standard deviation σ batch \sigma_{\text{batch}} . This design avoids GRPO’s pitfalls: the baseline b b is near-optimal, the normalization scaler σ \sigma is stable, and there is no systematic information loss from group-outcome degeneracy.
Quantitative Comparison : A simplified ratio of the reward-term variance quantifies the difference: Var [ g ] GRPO Var [ g ] SPO ≈ 1 + 1 G 1 + 1 N eff + 1 ⏟ Baseline Noise × 1 1 − Z G ( p ) ⏟ Information Loss × 1 + ψ G 1 + ψ ℬ ⏟ Normalization Noise . \frac{\text{Var}[g]_{\text{GRPO}}}{\text{Var}[g]_{\text{SPO}}}\approx\underbrace{\frac{1+\frac{1}{G}}{1+\frac{1}{N_{\text{eff}}+1}}}_{\text{Baseline Noise}}\times\underbrace{\frac{1}{1-Z_{G}(p)}}_{\text{Information Loss}}\times\underbrace{\frac{1+\psi_{G}}{1+\psi_{\mathcal{B}}}}_{\text{Normalization Noise}}. (12) Here, N eff N_{\text{eff}} is the effective sample count for SPO’s tracker, and ψ G > 0 \psi_{G}>0 captures the excess variance from per-group, ψ ℬ \psi_{\mathcal{B}} represents the excess variance introduced by estimating the normalization statistics (mean and standard deviation) from a large global batch of size N ℬ N_{\mathcal{B}} ( ψ ℬ ≈ 0 \psi_{\mathcal{B}}\approx 0 ). For a moderately difficult prompt ( p = 0.5 p=0.5 ) with G = 8 G=8 , the normalization noise dominates. However, for an easy/hard prompt ( p = 0.9 / p = 0.1 p=0.9/p=0.1 ), the information loss term dominates, and the ratio swells to ≈ 1.97 \approx 1.97 . While increasing G G in GRPO mitigates information loss, it does so at a multiple generation cost and cannot fix the inherent noise from its small-sample baseline and scaling. SPO achieves lower variance more efficiently by design.
## Appendix D Training and Evaluation Details
All experiments in this paper are implemented on top of verl [ 35 ] and ReTool [ 13 ] for the tool-integrated reasoning setup. During training, we set the maximum response length to 16,384 16{,}384 tokens. The policy learning rate is fixed at 1 × 10 − 6 1\times 10^{-6} . Following DAPO [ 42 ] , we adopt the Clip-Higher mechanism, with clipping parameters ε low = 0.2 \varepsilon_{\text{low}}=0.2 and ε high = 0.28 \varepsilon_{\text{high}}=0.28 , to balance exploration and exploitation. The sampling parameters are set to temperature 1.0, top- p = 1.0 p=1.0 , and top- k = − 1 k=-1 . The forgetting rate thresholds are chosen as ρ min = 0.875 \rho_{\min}=0.875 and ρ max = 0.96 \rho_{\max}=0.96 , yielding window sizes W min = 1 − 1 ρ min = 8 W_{\min}=1-\tfrac{1}{\rho_{\min}}=8 and W max = 25 W_{\max}=25 .
GRPO rollouts are collected with multiple responses per prompt, and training mini-batch sizes are chosen such that 8 8 gradient updates are performed per rollout step. For a fair comparison, the prompt batch size in SPO is set equal to the total number of responses in GRPO, as SPO generates only a single response for each prompt. Specifically, GRPO uses a prompt batch size of 256 256 with 8 8 responses per prompt and a training mini-batch size of 256 256 , while SPO operates on 2,048 = 256 × 8 2,048=256\times 8 prompts. Both algorithms are set with maximum of 8 8 Python interpreter interaction turns.
For evaluation on hard math competition benchmarks, i.e., AIME 24, AIME 25, BeyondAIME [ 32 ] , BRUMO 25 [ 5 ] and HMMT 25 [ 5 ] , we set sampling parameters to temperature 0.6 0.6 , top- p p 0.95 0.95 , and top- k k 20 20 , as officially recommended 5 5 5 https://huggingface.co/Qwen/Qwen3-8B . We define a binary reward function r i , j r_{i,j} such that a response receives r i , j = 1 r_{i,j}=1 if the final answer is correct, and r i , j = 0 r_{i,j}=0 otherwise. The same reward function is consistently used during training for policy optimization and during evaluation. We set the maximum response token to 32,768.
Given a test set with M M problems, and for each problem i i we independently sample k k responses with rewards { r i , 1 , r i , 2 , … , r i , k } \{r_{i,1},r_{i,2},\ldots,r_{i,k}\} , we define:
• avg@ k k : the expected correctness of an individual response: avg@ k = 1 M ∑ i = 1 M 1 k ∑ j = 1 k r i , j . \text{avg@}k=\frac{1}{M}\sum_{i=1}^{M}\frac{1}{k}\sum_{j=1}^{k}r_{i,j}.
• pass@ k k : the probability of solving a problem within k k attempts. Directly computing ( max 1 ≤ j ≤ k r i , j = 1 ) \mathbf{1}\!\bigl(\max_{1\leq j\leq k}r_{i,j}=1\bigr) can lead to high variance. Following [ 7 ] , we instead generate n ≥ k n\geq k responses per problem, count the number of correct ones c ≤ n c\leq n , and use the unbiased estimator: pass@ k = 1 M ∑ i = 1 M [ 1 − ( n − c i k ) ( n k ) ] , \text{pass@}k=\frac{1}{M}\sum_{i=1}^{M}\left[1-\frac{\binom{n-c_{i}}{k}}{\binom{n}{k}}\right], where c i c_{i} denotes the number of correct responses for problem i i .