Single-stream Policy Optimization — part 1/4

Cleaned-text code points [0, 14865). Bibliography omitted here; source.md includes it.

# Single-stream Policy Optimization

Abstract: We revisit policy-gradient optimization for Large Language Models (LLMs) from a single-stream perspective. Prevailing group-based methods like GRPO reduce variance with on-the-fly baselines but suffer from critical flaws: frequent degenerate groups erase learning signals, and synchronization barriers hinder scalability. We introduce Single-stream Policy Optimization (SPO), which eliminates these issues by design. SPO replaces per-group baselines with a persistent, KL-adaptive value tracker and normalizes advantages globally across the batch, providing a stable, low-variance learning signal for every sample. Being group-free, SPO enables higher throughput and scales effectively in long-horizon or tool-integrated settings where generation times vary. Furthermore, the persistent value tracker naturally enables an adaptive curriculum via prioritized sampling. Experiments using Qwen3-8B show that SPO converges more smoothly and attains higher accuracy than GRPO, while eliminating computation wasted on degenerate groups. Ablation studies confirm that SPO’s gains stem from its principled approach to baseline estimation and advantage normalization, offering a more robust and efficient path for LLM reasoning. Across five hard math benchmarks with Qwen3-8B, SPO improves the average maj@32 by + 3.4 ​ percentage points ​ ( pp ) +3.4\penalty\ \text{percentage points}\penalty\ (\mathrm{pp}) over GRPO, driven by substantial absolute point gains on challenging datasets, including + 7.3 ​ pp +7.3\penalty\ \mathrm{pp} on BRUMO 25, + 4.4 ​ pp +4.4\penalty\ \mathrm{pp} on AIME 25, + 3.3 ​ pp +3.3\penalty\ \mathrm{pp} on HMMT 25, and achieves consistent relative gain in pass@ k k across the evaluated k k values. SPO’s success challenges the prevailing trend of adding incidental complexity to RL algorithms, highlighting a path where fundamental principles, not architectural workarounds, drive the next wave of progress in LLM reasoning.

## 1 Introduction

Reinforcement learning (RL) [ 36 ] has become a cornerstone for advancing the reasoning capabilities of Large Language Models (LLMs), notably the Reinforcement Learning with Verifiable Reward (RLVR) paradigm [ 21 , 11 ] . Methods like Group Relative Policy Optimization (GRPO) [ 34 , 11 ] have achieved remarkable success by adopting a multi-outcome approach, generating a group of responses for each prompt to construct an on-the-fly baseline for variance reduction. While this “group-based” paradigm has pushed the state of the art, it suffers from fundamental inefficiencies. When all responses in a group share the same outcome (e.g., all correct or all incorrect), the relative advantage collapses to zero, yielding no learning signal. This degeneracy represents a fundamental waste of computation and data. To counteract this, a series of engineering heuristics like dynamic sampling [ 42 ] have been developed. These workarounds, while functional, add significant complexity and create a less principled, more convoluted optimization process.

Group-based architectural choice also imposes a critical synchronization barrier. In distributed training, the entire group must wait for its slowest member, a bottleneck that becomes particularly acute in complex agentic tasks requiring multi-turn tool use or long-horizon reasoning [ 15 , 41 , 45 ] . In these settings, interaction times are highly variable (e.g., number of interaction turns, time per interaction, etc), and a single slow-running agentic trajectory can stall its entire group, severely hindering training throughput and scalability.

We advocate for returning to the classic single-stream paradigm for policy gradient optimization [ 36 ] , where each training sample is a single stream of prompt-response pair. This is not a mere simplification, but a deliberate re-alignment with foundational RL principles to address the aforementioned architectural flaws. To overcome the critical challenge of high gradient variance in this setting, we introduce Single-stream Policy Optimization (SPO). SPO replaces the noisy, on-the-fly group baseline with three synergistic components for stable and efficient learning. First, it employs a lightweight Bayesian value tracker to maintain a persistent, temporally-informed estimate of the success probability for each prompt, serving as a low-variance baseline. Second, it normalizes advantages globally across the entire batch, avoiding the instability of per-group statistics. Finally, this architecture naturally enables an adaptive curriculum via prioritized sampling, focusing computational resources on the most informative prompts.

The benefits of this principled approach are clear: SPO is inherently more scalable and eliminates the computational waste of degenerate groups. Our experiments confirm these advantages, demonstrating that SPO consistently outperforms GRPO on challenging reasoning benchmarks, improving the absolute point gains on challenging datasets, including 7.3 ​ percentage points ​ ( pp ) 7.3\penalty\ \text{percentage points}\penalty\ (\mathrm{pp}) on BRUMO 25, 4.4 ​ pp 4.4\penalty\ \mathrm{pp} on AIME 25, 3.3 ​ pp 3.3\penalty\ \mathrm{pp} on HMMT 25, and the pass@ k k curves of SPO are above GRPO for all k k s. The scalability benefit is particularly pronounced in agentic settings. Our simulations, designed to model these variable-time scenarios, show that SPO’s group-free design can achieve a 4.35 × 4.35\times training throughput speedup by eliminating group synchronization bottlenecks. SPO thus provides a more robust foundation for modern LLM optimization, prompting a re-evaluation of essential versus incidental complexity in the field.

## 2 Related Work

Group Relative Policy Optimization (GRPO) [ 34 ] addresses the computational overhead and training instability of PPO-style algorithms [ 31 ] by eliminating the need for a separate critic network. Instead, GRPO constructs baselines on-the-fly using multiple responses generated for each prompt. Specifically, GRPO samples a group of multiple responses for each prompt and normalizes the rewards within this group to have zero mean and unit variance, creating relative advantages for policy updates. However, this approach can be inefficient if all responses in a group receive the same reward (e.g., all incorrect or all correct), resulting in a zero-advantage for all samples and providing no learning signal. To address this, DAPO [ 42 ] enhances GRPO with engineering treatments like dynamic sampling, which continues generating responses until non-zero advantages are achieved, ensuring meaningful gradients.

Several other works have proposed improvements to group-based methods. Zheng et al. [44] introduce GRESO, an online filtering algorithm that leverages reward training dynamics to predict and skip uninformative prompts before generation. Qu et al. [28] introduce a Bayesian estimation of the prompt accuracy and use it to form a bandit strategy, significantly reducing rollout overhead. Liu et al. [25] propose “Lite PPO”, which simplifies RLVR training to only advantage normalization and token-level loss aggregation.

Other group-based approaches include RLOO [ 1 ] , which returns to the simpler REINFORCE [ 39 , 36 ] algorithm using a Leave-One-Out baseline that treats entire generations as single actions. Similarly, Hao et al. [17] propose On-Policy RL with Optimal Baseline (OPO), which uses a length-weighted average of rewards as an optimal simplified baseline. Despite these improvements, all group-based methods share fundamental limitations. They construct baselines from concurrently generated responses rather than persistent, historical estimates, inheriting the same core architectural constraints as GRPO: synchronization overhead and increased generation costs in distributed settings.

Moving beyond group-based methods, Brantley et al. [6] propose A ∗ A^{*} -PO, a two-stage framework that achieves single-sample efficiency through a different approach. In the first stage, A ∗ A^{*} -PO performs offline estimation to approximate the optimal value function V ∗ V^{*} rather than the policy-specific value function V π V_{\pi} . The second stage uses this pre-computed optimal value to construct optimal advantage estimates A ∗ A^{*} for a least-squares regression objective during online training. However, A ∗ A^{*} -PO has key limitations compared to our approach. It relies on a fixed , offline-computed estimate that does not adapt as the policy evolves during training. Additionally, A ∗ A^{*} -PO is constrained by KL-regularized policy optimization, which restricts how far the optimized policy can deviate from the reference policy.

## 3 Background

Reinforcement learning (RL) algorithms have been used to align Large Language Models (LLMs) with human preferences (RLHF) and to optimize verifiable reward signals (RLVR; e.g., [ 21 , 34 ] ).

### 3.1 Policy Gradient and the REINFORCE Algorithm

The foundational method for this optimization is the policy gradient theorem [ 39 , 36 ] . For LLMs, a trajectory consists of generating a single response y y from a prompt x x . The objective function is the expected reward: J ( θ ) = 𝔼 x ∼ 𝒟 , y ∼ π θ ( ⋅ | x ) [ R ( x , y ) ] , J(\theta)=\mathbb{E}_{x\sim\mathcal{D},y\sim\pi_{\theta}(\cdot|x)}[R(x,y)], (1) where 𝒟 \mathcal{D} is the prompt distribution and R ⁡ ( x , y ) R(x,y) is the reward for generating response y y for prompt x x . The gradient of this objective is given by: ∇ θ J ( θ ) = 𝔼 x ∼ 𝒟 , y ∼ π θ ( ⋅ | x ) [ R ( x , y ) ∇ θ log π θ ( y | x ) ] . \nabla_{\theta}J(\theta)=\mathbb{E}_{x\sim\mathcal{D},y\sim\pi_{\theta}(\cdot|x)}[R(x,y)\nabla_{\theta}\log\pi_{\theta}(y|x)]. (2) This formulation gives rise to the REINFORCE algorithm [ 39 , 36 ] , which updates the policy by taking a step in the direction of this estimated gradient. A significant drawback of REINFORCE is the high variance of its gradient estimator. The raw reward R ⁡ ( x , y ) R(x,y) can fluctuate widely, leading to noisy updates and unstable training.

To mitigate high variance, a baseline b ⁡ ( x ) b(x) that is conditionally independent of the action y y can be subtracted from the reward. This results in an unbiased gradient estimator with provably lower variance [ 16 ] : ∇ θ J ( θ ) = 𝔼 x ∼ 𝒟 , y ∼ π θ ( ⋅ | x ) [ ( R ( x , y ) − b ( x ) ) ∇ θ log π θ ( y | x ) ] . \nabla_{\theta}J(\theta)=\mathbb{E}_{x\sim\mathcal{D},y\sim\pi_{\theta}(\cdot|x)}[(R(x,y)-b(x))\nabla_{\theta}\log\pi_{\theta}(y|x)]. (3) The term A ⁡ ( x , y ) = R ⁡ ( x , y ) − b ⁡ ( x ) A(x,y)=R(x,y)-b(x) is known as the advantage. The optimal baseline that minimizes variance is the true value function V π ( x ) = 𝔼 y ∼ π θ ( ⋅ | x ) [ R ( x , y ) ] V_{\pi}(x)=\mathbb{E}_{y\sim\pi_{\theta}(\cdot|x)}[R(x,y)] , which is the expected reward for a given prompt x x . In practice, V π ​ ( x ) V_{\pi}(x) is unknown and must be estimated. The quality of this estimation is crucial for the stability and efficiency of the RL algorithm.

### 3.2 Variance Reduction Baselines for Large Language Models

Several strategies have been developed to estimate the baseline b ⁡ ( x ) b(x) in the context of LLM training. PPO [ 31 ] trains a parameterized critic network v ϕ v_{\phi} . However, learning v ϕ v_{\phi} is notoriously unstable and resource-intensive, as ϕ \phi typically matches the size of the LLM policy parameters θ \theta .

A common approach is to construct an empirical, on-the-fly baseline from multiple samples. Group Relative Policy Optimization (GRPO) [ 34 , 11 ] generates a group of G G responses { y 1 , … , y G } \{y_{1},\dots,y_{G}\} for a single prompt x x , then uses the mean rewards of the group as the baseline b GRPO b_{\text{GRPO}} . Another popular baseline is the Leave-One-Out (RLOO). For a given sample y i y_{i} , the baseline is the average reward of the other G − 1 G-1 samples in the group, denoted as b RLOO b_{\text{RLOO}} : b GRPO ​ ( x ) = 1 G ​ ∑ j R ⁡ ( x , y j ) , b RLOO ​ ( x , y i ) = 1 G − 1 ​ ∑ j ≠ i R ⁡ ( x , y j ) . b_{\text{GRPO}}(x)=\frac{1}{G}\sum_{j}R(x,y_{j}),\qquad b_{\text{RLOO}}(x,y_{i})=\frac{1}{G-1}\sum_{j\neq i}R(x,y_{j}). (4)

The raw advantage for sample y i y_{i} is then A ⁡ ( x , y i ) = R ⁡ ( x , y i ) − b GRPO ​ ( x ) A(x,y_{i})=R(x,y_{i})-b_{\text{GRPO}}(x) , then it is normalized with the standard deviation σ G \sigma_{G} . While simple to implement, this approach suffers from two key limitations. First, it is sample-inefficient, requiring G > 1 G>1 generations per prompt for each gradient step. Second, the baseline is estimated from a very small group ( G G ), making it a high-variance estimate of the true value function, which in turn leads to noisy advantage estimates.

## 4 Method

We introduce Single-stream Policy Optimization (SPO), a method designed for policy optimization in settings with verifiable feedback (RLVR) [ 21 ] . We assume the feedback is binary 1 1 1 Generalizing to non-binary rewards is straightforward, as discussed at the end of Section 4.1 . , i.e., + 1 +1 for success and 0 0 for failure. SPO addresses the challenge of estimating a non-stationary success probability for a policy that evolves over training iterations. It integrates a Bayesian value tracker with an adaptive memory mechanism into a policy gradient framework. The core components are: (1) a KL-adaptive tracker that provides a low-variance, single-sample estimate of the success probability; (2) a global advantage normalization scheme that ensures high sample efficiency and stable learning dynamics; and (3) prioritized sampling across training prompts to focus on prompts with high learning potential. The following subsections detail each component.

### 4.1 A KL-Adaptive Value Tracker

The definition of a value function is the expected reward of the prompt x x under policy π \pi , i.e., V π ( x ) = 𝔼 y ∼ π ( ⋅ | x ) [ R ( x , y ) ] V_{\pi}(x)=\mathbb{E}_{y\sim\pi(\cdot|x)}[R(x,y)] . We use v ^ ​ ( x ) \hat{v}(x) to denote the tracker’s running estimate of V π ​ ( x ) V_{\pi}(x) ; that is, v ^ ​ ( x ) ≈ V π ​ ( x ) \hat{v}(x)\approx V_{\pi}(x) . To estimate the non-stationary success probability of a prompt x x , we use a Bayesian tabular tracker instead of a separate value network 2 2 2 The development of core RL algorithms was on tabular representation [ 36 ] . . For the binary success/failure rewards common in RLVR, this is elegantly modeled using a Beta distribution, which is the conjugate prior for the Bernoulli process governing the outcomes. We therefore model the success probability v ^ ​ ( x ) \hat{v}(x) using a Beta distribution: v ^ ​ ( x ) ∼ Beta ​ ( α ⁡ ( x ) , β ⁡ ( x ) ) \hat{v}(x)\sim\text{Beta}(\alpha(x),\beta(x)) , where the value estimate is the posterior mean v ^ ​ ( x ) = α ⁡ ( x ) / ( α ⁡ ( x ) + β ⁡ ( x ) ) \hat{v}(x)=\alpha(x)/(\alpha(x)+\beta(x)) .