Single-stream Policy Optimization

• When every response in a GRPO group has the same outcome, its relative advantage collapses to zero, wasting computation and providing no learning signal.Dynamic sampling and other engineering workarounds address this degeneracy but add complexity.Source: §1 · p. 1
• Group-based training makes each group wait for its slowest response, hindering throughput and scalability in variable-time, multi-turn tool-use or long-horizon tasks.A single slow trajectory can stall the entire group.Source: §1 · p. 1
• SPO uses a persistent Bayesian value tracker, globally normalized batch advantages, and prioritized sampling to provide a low-variance baseline and focus computation on informative prompts.The tracker maintains a temporally informed success-probability estimate for each prompt, replacing the noisy on-the-fly group baseline.Source: §1 · p. 2
• SPO gains 7.3 pp on BRUMO 25, 4.4 pp on AIME 25, and 3.3 pp on HMMT 25; its pass@k curves exceed GRPO for every k.The introduction also reports consistent outperformance on challenging reasoning benchmarks.Source: §1 · p. 2
• SPO’s group-free design achieves a 4.35× training throughput speedup in simulations of variable-time agentic settings.The simulations model variable interaction times and the synchronization bottlenecks that can stall group-based training.Source: §1 · p. 2

2. Related Work

• GRPO [34] uses within-prompt reward normalization for relative advantages, but equal-reward groups yield no learning signal; DAPO [42] uses dynamic sampling to avoid them.GRPO removes the separate critic network used by PPO-style algorithms [31].Source: §2 · p. 2
• GRESO [44] filters uninformative prompts, Qu et al. [28] use Bayesian accuracy estimates for bandit sampling, and Lite PPO [25] simplifies RLVR to advantage normalization and token-level loss aggregation.GRESO predicts which prompts to skip before generation, while Qu et al. aim to reduce rollout overhead.Source: §2 · p. 2
• RLOO [1] uses a Leave-One-Out baseline and OPO [17] a length-weighted reward average, yet group-based methods retain synchronization overhead and higher distributed generation costs.RLOO returns to REINFORCE and treats entire generations as single actions; OPO uses an optimal simplified baseline.Source: §2 · p. 2
• A*-PO [6] estimates V* offline for online optimal-advantage least-squares regression, but its estimate does not adapt with the policy and its optimization is KL-regularized.Its two stages are offline estimation of V*, followed by online training using precomputed optimal advantages A*.Source: §2 · p. 3

3. Background

• RL is used to align LLMs with human preferences and optimize verifiable reward signals [21] [34].Source: §3 · p. 3

3.1. Policy Gradient and the REINFORCE Algorithm

• The policy gradient theorem [36, 39] underlies REINFORCE, which optimizes expected reward for responses generated from prompts.REINFORCE’s raw-reward gradient estimator has high variance, causing noisy updates and unstable training.Source: §3.1 · p. 3

3.2. Variance Reduction Baselines for Large Language Models

• PPO [31] estimates the baseline with a parameterized critic, but critic learning is unstable and resource-intensive because its parameters typically match the policy’s scale.A baseline independent of the action can be subtracted without bias; the optimal baseline is the prompt’s expected reward, Vπ(x), which must be estimated.Source: §3.2 · p. 3, §3.1 · p. 3
• GRPO uses a group’s mean reward as its baseline, while RLOO uses the mean reward of the other G samples.GRPO advantages are normalized by the group standard deviation; group baselines require multiple generations per prompt and can be high-variance estimates, producing noisy advantages.Source: §3.2 · p. 4

4.1. A KL-Adaptive Value Tracker

• SPO estimates prompt success with a Bayesian Beta tracker and discounts past observations more as the policy diverges from the policy that produced them.Its posterior mean supplies the running value estimate; the update adapts to both policy shifts and statistical confidence.Source: §4.1 · pp. 4–5

4.2. Advantage Estimation and Policy Optimization

• SPO subtracts the pre-update value estimate from each reward, then normalizes advantages across the batch and applies them in a PPO-Clip policy update.Using a baseline independent of the sampled action preserves an unbiased policy-gradient estimate; a zero baseline is valid but can have high variance.Source: §4.2 · pp. 5–6

4.3. Prioritized Prompt Sampling

• SPO prioritizes prompts with uncertain success estimates while an exploration bonus of 0.05 by default preserves nonzero sampling probability for every prompt.The uncertainty score emphasizes prompts that are neither almost always solved nor almost always failed.Source: §4.3 · p. 6

4.4. Advantages over GRPO

• SPO’s group-free updates collect independent prompt-response pairs, avoiding GRPO’s wait for every response in a prompt group and improving flexibility under long-tail generation times.Prioritized sampling schedules informative prompts before generation, unlike approaches that discard samples afterward; this is especially relevant to tool-integrated and long-horizon training.Source: §4.4 · pp. 6–7

5.1. Experimental Setup

• Experiments evaluate Qwen3-8B on tool-integrated reasoning with English DAPO training data, outcome rewards, and five challenging math competition benchmarks.The study focuses on RL algorithm efficiency and scalability rather than leaderboard hill-climbing with specialized pipelines.Source: §5.1 · pp. 7–8

5.2. Empirical Comparison with GRPO

• +3.4 pp: SPO reaches maj@32 63.8 versus GRPO’s 60.4 on the weighted average, with gains across all five benchmarks, including +7.3 pp on BRUMO 25.SPO’s weighted-average pass@k curve also leads across all evaluated k values, with an average improvement of approximately 2.4 pp.Source: Table 1 · p. 8, §5.2 · pp. 8–9, Figure 2 · p. 8

5.3. Analysis of Signal Efficiency and Stability

• GRPO’s degenerate groups rise from roughly 60% to over 80%, while SPO’s history-informed baseline reduces variance by nearly 50%.SPO’s near-zero advantages remain far below GRPO’s degenerate rate and still produce gradients; GRPO’s effective signal among non-degenerate samples is highly volatile.Source: Figure 3 · p. 9, §5.3 · pp. 9–10

5.4. Agentic Training Demonstrations

• In simulation, group synchronization made a 508-second straggler stall a batch despite most samples finishing under 133 seconds; group-free sampling cut 24-sample collection from 486 to 112 seconds (4.35×).The group-free strategy starts 48 independent samples and collects the first 24 to finish, avoiding slow outliers.Source: §5.4 · pp. 10–11, Figure 4 · p. 10, Figure 5 · p. 11

6. Conclusions

• SPO replaces noisy per-group baselines with a persistent KL-adaptive value tracker and global advantage normalization.The paper identifies degenerate-group computation waste and synchronization bottlenecks as key problems in group-based methods.Source: §6 · p. 11
• SPO consistently outperformed GRPO on complex reasoning tasks while eliminating group-based methods’ systemic flaws.The paper presents SPO as a simpler single-stream approach and a robust, scalable foundation for future reasoning and agentic model training.Source: §6 · p. 11

A. SPO Initialization

• The experiments use n0=8 for initial baseline estimation, while an ablation tests omitting offline estimation in favor of the online moving estimator.The stated purpose of n0=8 is to obtain a good estimate of the initial baseline tracker.Source: A. SPO Initialization · p. 16
• Initialization sets effective sample size N0=1/(1-rho_min) and derives alpha0(x) and beta0(x) from the estimated initial baseline v0(x).The stated parameterization is alpha0(x)=N0·v0(x) and beta0(x)=N0·(1-v0(x)).Source: A. SPO Initialization · p. 16
• Offline estimation costs can be amortized because the authors share estimated datasets, and datasets such as Polaris pre-compute accuracy for Deepseek-R1-Distill-Qwen-7B.The authors also plan to share more dataset and base-model combinations.Source: A. SPO Initialization · p. 16

B. Batch Extensions

• SPO can use prompt repetition, processing each prompt G times per batch with a shared baseline estimator to better handle sparse rewards.Repeated prompts are treated as independent trajectories.Source: B. Batch Extensions · p. 16
• Removing group synchronization enables asynchronous batching that can manage slow trajectories and assemble a full batch from early finishers.The paper describes terminating, discarding, or partially rolling out problematic trajectories [20], and oversampling initial prompts (for example, by 50%) so optimization can proceed without waiting for stragglers.Source: B. Batch Extensions · p. 16

C.1. Inefficiency of Dynamic Sampling

• Dynamic sampling, used by methods like DAPO [42], continues generating responses until a prompt’s set contains both a success and a failure, guaranteeing non-zero advantage.The approach addresses information loss when all rewards in a sample group are identical.Source: §C.1 · p. 16
• Reported dynamic-sampling “steps” count learning steps, not sampling steps, which are normally a multiple of them, such as 5×.This distinction qualifies comparisons of reported step counts for methods using dynamic sampling.Source: §C.1 · p. 16
• For prompt success probability p, the expected samples E[N] to obtain a non-degenerate set are 1/(p(1-p)) - 1.Here, N is the number of samples required to collect both a success and a failure.Source: §C.1 · p. 17
• SPO uses exactly one sample per prompt and deprioritizes inefficient prompts, whereas dynamic sampling can be extremely data- and time-inefficient.Its adaptive curriculum allocates resources to prompts where learning is more effective.Source: §C.1 · pp. 16–17
• Expected sampling cost grows hyperbolically as policy success probability approaches either 0 or 1.These extremes correspond to prompts for which successes or failures are increasingly difficult to obtain.Source: §C.1 · p. 17
• At a 10% success rate, dynamic sampling requires an expected 10.11 generations to collect both a success and a failure.SPO requires one sample per prompt and uses its adaptive curriculum to deprioritize inefficient prompts.Source: §C.1 · p. 17

GRPO’s High-Variance Group-Based Advantage

• GRPO’s small-group advantage has three variance sources: a noisy baseline, noisy standard-deviation scaling, and zero-signal groups when rewards are identical.The noisy baseline inflates unnormalized advantage variance by a factor of (1 + 1/G); degeneracy is especially severe for easy or hard prompts.Source: §C.2 · p. 17

SPO’s Low-Variance Decoupled Advantage

• SPO uses a historical action-independent value tracker and normalizes advantages with one stable standard deviation across a large batch, avoiding group-degeneracy information loss.Its baseline estimates success probability, while global normalization uses batch size B≫G.Source: §C.2 · p. 17

Quantitative Comparison

• At G=8 and p=0.9 or 0.1, information loss dominates and the reported variance ratio swells to ≈1.97.For p=0.5 at G=8, normalization noise dominates instead.Source: §C.2 · p. 18
• Increasing G can mitigate GRPO’s information loss, but raises generation cost and cannot fix its small-sample baseline and scaling noise.SPO achieves lower variance more efficiently by design.Source: §C.2 · p. 18

D. Training and Evaluation Details

• Training uses verl [35] and ReTool [13], a 16,384-token response limit, a 1 × 10−6 learning rate, and Clip-Higher clipping at εlow = 0.2 and εhigh = 0.28 following DAPO [42].Sampling uses temperature 1.0, top-p = 1.0, and top-k = −1; forgetting thresholds ρmin = 0.875 and ρmax = 0.96 yield windows Wmin = 8 and Wmax = 25.Source: D. Training and Evaluation Details · p. 18
• For a fair comparison, GRPO uses a prompt batch of 256 with 8 responses per prompt, while SPO uses 2,048 prompts; both allow at most 8 Python-interpreter interaction turns.GRPO's training mini-batch size is 256, with 8 gradient updates per rollout step.Source: D. Training and Evaluation Details · p. 18
• Hard-math evaluation covers AIME 24, AIME 25, BeyondAIME [32], BRUMO 25 [5], and HMMT 25 [5], using temperature 0.6, top-p 0.95, top-k 20, and a 32,768-token response limit.Responses receive reward 1 when the final answer is correct and 0 otherwise; the same reward is used in training and evaluation.Source: D. Training and Evaluation Details · p. 18
• The evaluation metrics are avg@k for individual-response correctness, pass@k for solving within k attempts, and maj@k for whether the most frequent answer is correct.For pass@k, the method generates n ≥ k responses per problem to address high variance in direct computation [7]; maj@k uses majority voting [37].Source: D. Training and Evaluation Details · pp. 18–19

Ablation Studies

• The ablations use a streamlined setup on AIME 25, reporting avg@16 with a maximum generation length of 16,384 tokens.Each collected batch contains 256 prompt-response pairs, and the model receives four gradient steps per batch.Source: E. Ablation Studies · p. 19

SPO vs. A*-PO

• SPO’s adaptive baseline outperforms A*-PO’s static baseline, supporting a baseline that tracks the policy as it evolves.As policy drift increases, A*-PO’s precomputed value may become less representative of the current policy; its policy update also requires extra GPU memory for computing the reference policy.Source: E. Ablation Studies · pp. 19–20, Figure 6 · p. 19

Baseline Ablation

• Removing SPO’s value tracker causes substantial performance degradation, showing that global reward normalization alone does not remove prompt-specific difficulty.The history-informed baseline estimates expected difficulty and reduces per-sample reward variance, producing a more reliable learning signal.Source: Figure 6 · p. 19, E. Ablation Studies · p. 20

Offline Initialization Ablation

• Removing offline initialization causes early training instability and a performance dip, and the tracker does not reach the performance of the warm-started model.The standard tracker starts from estimates computed using a small set of n_0 offline samples; learning from scratch initially yields an inaccurate baseline and high-variance gradients.Source: Figure 6 · p. 19, E. Ablation Studies · p. 20