arXiv:2607.01083v1 [cs.LG] 1 Jul 2026
Staleness–Learning Rate Scaling Laws for Asynchronous RLHF
Jingwei Song1,2,3* , Haofeng Xu1* , Jie Xiao3 , Chengke Bao3 , Jingwei Shi4 , Pengbin Feng5 , Weixun Wang, Yuhang Han2 , Chuan Wu1† , Linfeng Zhang2† , Bill Shi3† 1 The University of Hong Kong 2 Shanghai Jiao Tong University 3 Gradient 4 University of Southern California 5 The Hong Kong Polytechnic University [email protected], [email protected] ∗
Equal contribution, † Corresponding author
Abstract High-throughput RLHF systems often decouple rollout generation from policy optimization, causing the learner to update on stale rollouts. We study this effect in asynchronous GRPO. The analysis makes the behavior policy explicit in the GRPO surrogate and distinguishes the surrogate-gradient mapping used by the learner from the total derivative of a distribution-dependent population objective. Under local boundedness, distributional smoothness, and behavior-policy smoothness assumptions, stale rollouts induce a per-step surrogate-gradient bias of order O(Sη), where S is the maximum rollout lag and η is the learning rate. We further formulate a conditional collapse-time scaling: when within-cycle drift remains below a batch-level clipping radius, the observed collapse horizon is governed primarily by cumulative learner drift T η; when the local stale-rollout condition is binding, stability instead depends explicitly on Sη. This yields the two-constraint rule η ≪ min{Rbatch /(SGupd ), Rcrit /(T Gupd )}, explaining why the maximum stable learning rate can appear weakly dependent on staleness only in the horizon-limited regime.
1
Introduction
Reinforcement Learning from Human Feedback (RLHF) has emerged as a pivotal technique for aligning Large Language Models (LLMs) with human intent, enabling improvements in instruction following, reasoning capabilities, and safety [Ouyang et al., 2022, Christiano et al., 2017, Kaufmann et al., 2023]. The canonical RLHF pipeline, exemplified by InstructGPT [Ouyang et al., 2022], typically comprises three stages: supervised fine-tuning (SFT), reward model training on human preference data, and policy optimization via Proximal Policy Optimization (PPO) [Schulman et al., 2017]. Despite its empirical success, this paradigm faces substantial computational challenges: PPO requires maintaining a separate value network (critic) alongside the policy and reward models, creating significant memory overhead and synchronization bottlenecks in distributed training environments [Shao et al., 2024, Rafailov et al., 2023]. To address these limitations, Group Relative Policy Optimization (GRPO) was introduced by Shao et al. [2024] as an efficient alternative to PPO for LLM fine-tuning. GRPO eliminates the critic network by estimating baselines from group-wise reward statistics, reducing memory consumption and computational cost. This design choice has proven effective for mathematical reasoning tasks and has been adopted in subsequent large-scale systems such as DeepSeek-R1 [Guo et al., 2025]. By removing the critic and lowering the memory and compute cost of each optimization step, GRPO makes distributed asynchronous training increasingly attractive for RLHF pipelines. Preprint.
Asynchronous training architectures have long been recognized as a promising avenue for accelerating large-scale optimization [Recht et al., 2011, Agarwal and Duchi, 2011, Lian et al., 2015]. In the standard asynchronous parameter-server framework [Li et al., 2014], multiple rollout workers generate experience in parallel using potentially stale policy snapshots, while a central learner continuously applies gradient updates. This decoupling of rollout generation from policy optimization maximizes throughput by reducing idle waiting time. The same idea underlies a long line of decoupled actorlearner architectures in deep RL, beginning with Gorila [Nair et al., 2015] and A3C [Mnih et al., 2016] and continuing through IMPALA [Espeholt et al., 2018], Ape-X [Horgan et al., 2018], and SEED RL [Espeholt et al., 2020], where dedicated actors stream experience to a centralized learner. A recurring lesson from this literature is that decoupling is not free: because the actor policy lags the learner, training becomes off-policy, and stable high-throughput learning required explicit corrections—most notably the V-trace off-policy correction introduced by IMPALA [Espeholt et al., 2018]. Indeed, some distributed PPO systems deliberately remain synchronous to avoid staleness altogether; DD-PPO [Wijmans et al., 2020], for instance, is designed so that “no computation is ever stale,” and reproducibility studies show that even a single step of staleness in actor-learner pipelines measurably alters the learning dynamics [Huang et al., 2023]. However, the resulting staleness—the discrepancy between the policy used to generate rollouts and the current learner policy—introduces off-policy bias that can destabilize training [Lian et al., 2015, Zhou et al., 2018]. Existing convergence analyses of asynchronous SGD typically characterize staleness as a bounded delay [Recht et al., 2011, Lian et al., 2015], yet do not directly quantify how this delay interacts with the distribution shift inherent in policy-gradient methods. Crucially, modern RLHF pipelines based on GRPO [Shao et al., 2024] typically rely on clipped importance ratios and KL regularization rather than the dedicated off-policy corrections used in classic distributed RL, which makes the staleness–learning-rate interaction the primary lever for controlling stability. The tension between throughput and stability becomes particularly acute in RLHF because policyinduced distribution shift compounds the staleness effect: as the learner policy evolves, rollouts generated by stale policies become progressively less representative of the current optimization landscape. Empirical observations in asynchronous GRPO suggest a characteristic two-phase pattern— stable improvement followed by abrupt degradation—indicating that the interaction between staleness and learning rate follows structured regimes rather than arbitrary failure. Understanding these regimes is useful for designing asynchronous RLHF systems that exploit parallelism while controlling training instability. Scaling laws have provided foundational insights into the training dynamics of neural language models [Kaplan et al., 2020, Hoffmann et al., 2022], characterizing how loss evolves with model size, data volume, and compute budget. More recently, scaling-law formulations have been extended to incorporate learning rate schedules and optimization hyperparameters [McCandlish et al., 2018]. However, the interaction between pipeline staleness and learning rate remains less understood, particularly in policy-gradient-based RLHF. Contributions. This paper develops a local theoretical framework for the staleness–learning rate interaction in asynchronous GRPO training. Our main contributions are: 1. Behavior-policy-aware formulation. We make the behavior policy explicit in the GRPO surrogate and define a surrogate-gradient mapping H(θ, ϕ), separating the learner parameter θ from the rollout policy ϕ. This avoids identifying the GRPO surrogate gradient with the total derivative of a distribution-dependent objective. 2. Per-step staleness bias. Under local boundedness, distributional smoothness, and behaviorpolicy smoothness assumptions, we prove that the stale-rollout surrogate-gradient bias scales as O(Sη), yielding a single-step safe region controlled by Sη. 3. Conditional collapse-time scaling. We refine the collapse-time argument by distinguishing batch-level clipping from horizon-level learner drift. When the local stale-rollout condition is not binding, collapse follows a T η-type horizon law; otherwise, stability can depend explicitly on Sη. 4. Two-constraint stability rule. Combining the two regimes gives a practical condition of the form η ≪ min{Rbatch /(SGupd ), Rcrit /(T Gupd )}, explaining why the maximum stable learning rate may appear nearly independent of S only in the horizon-limited regime. 2
2
Preliminaries
We study Reinforcement Learning from Human Feedback (RLHF) for Large Language Models (LLMs). Let πθ (· | x) denote an autoregressive policy parameterized by θ ∈ Rd that maps a prompt x to a distribution over completions y. Throughout, θ denotes the trainable policy parameters, and all norms and constants are understood in this parameter space. GRPO surrogate objective. Our analysis focuses on Group Relative Policy Optimization (GRPO) [Shao et al., 2024], a critic-free RLHF algorithm suited to high-throughput asynchronous pipelines. For each prompt x ∼ D, GRPO samples a group of Ggrp completions y1:Ggrp ∼ πϕ (· | x) from a behavior policy πϕ , computes per-completion rewards ri = rmodel (x, yi ), and forms groupnormalized advantages Âi =
ri − µ(r1:Ggrp ) , σ(r1:Ggrp )
i = 1, . . . , Ggrp .
(1)
For a rollout batch generated by πϕ , define the importance ratio πθ (yi | x) . πϕ (yi | x)
ρi (θ, ϕ) =
(2)
The behavior-policy-dependent GRPO surrogate, with KL regularization to a reference policy πref , is Ggrp i 1 Xh clip(ρi (θ, ϕ), 1 − ϵ, 1 + ϵ) Âi − β KL(πθ (· | x) ∥ πref (· | x)) , ℓGRPO (z; θ, ϕ) = Ggrp i=1 (3) where z = (x, y1:Ggrp ) is a group instance. The explicit behavior-policy argument ϕ captures the denominator of the importance ratio, the clipping boundary induced by the rollout policy, and the group statistics of the sampled batch. We reserve Ggrp for the GRPO group size; gradient and update magnitude constants are denoted separately below.
Rollout distribution. Let p(·; ϕ) denote the distribution over group instances induced by sampling x ∼ D and y1:Ggrp ∼ πϕ (· | x). Because this distribution depends on the policy used to generate rollouts, the theory below works with the GRPO surrogate-gradient mapping rather than the total derivative of an objective of the form Ez∼p(·;θ) [ℓ(z; θ)]. Stochastic gradients under stale rollouts. In practice, stochastic gradients are computed at learner parameters θ using a batch Bϕ collected under a possibly different behavior policy πϕ : 1 X g(θ; Bϕ ) ≜ ∇θ ℓGRPO (z; θ, ϕ), z ∼ p(·; ϕ). (4) |Bϕ | z∈Bϕ
We use gradient ascent notation throughout, treating ℓGRPO as a utility to be maximized. While the notation is specialized to GRPO, the bias decomposition in Section 3 applies to RLHF policyoptimization methods whose stochastic gradient has the behavior-policy-dependent form in (4). Synchronous vs. asynchronous updates.
Let η > 0 denote the learning rate.
Synchronous (on-policy) update. Rollouts are generated by the current policy (ϕ = θt ), and the learner updates θt+1 = θt + η g(θt ; Bθt ). (5) Asynchronous (stale-rollout) update. To maximize throughput, rollout workers may generate trajectories using a stale snapshot θt−kt , where kt ≥ 0 is the staleness lag at step t. The learner updates θt+1 = θt + η g(θt ; Bθt−kt ). (6) We denote the maximum staleness by S ≜ supt kt . Throughout this paper, S is the central pipeline design knob: a larger S permits higher rollout throughput at the cost of greater off-policy error. Our goal is to quantify the bias introduced by staleness in (6) and derive scaling rules relating (S, η) for both a single-step safe region and a finite training horizon. 3
3
Method: The Staleness-Aware Scaling Law
Asynchronous SGD analyses typically assume bounded delay, but do not directly characterize how delay interacts with policy-induced distribution shift in RLHF. In this section, we study this interaction in asynchronous GRPO. We first define a behavior-policy-aware surrogate-gradient mapping and use it to bound the per-step staleness bias induced by stale rollouts. This gives a single-step scaling rule controlled by Sη (Theorem 1). We then state a conditional collapse-time scaling that applies when the local stale-rollout condition is not the binding failure mode (Theorem 2). 3.1
Assumptions
Assumption 1 (Local bounded surrogate gradient and update). Within the local training region considered by the analysis, there exist constants Ggrad , Gupd > 0 such that for all relevant learner parameters θ, behavior policies ϕ, and group instances z, ∇θ ℓGRPO (z; θ, ϕ) ≤ Ggrad ,
(7)
and the applied update direction satisfies g(θ; Bϕ ) ≤ Gupd .
(8)
The first part controls the magnitude of the per-instance surrogate gradient; the second part controls the actual learner displacement and can be enforced by update or gradient clipping. For plain minibatch ascent, one may take Gupd ≤ Ggrad under (7). The boundedness assumption is used as a local condition in the stable training region rather than as a global statement about all language-model parameters. Assumption 2 (Local distributional smoothness). There exists Cπ > 0 such that for any behavior policies ϕ, ϕ′ in the local training region, KL(p(·; ϕ) ∥ p(·; ϕ′ )) ≤ Cπ ∥ϕ − ϕ′ ∥2 ,
(9)
where p(·; ϕ) denotes the distribution over group instances induced by πϕ . Assumption 3 (Behavior-policy smoothness of the surrogate). There exists Lρ > 0 such that, for any learner parameter θ and behavior policies ϕ, ϕ′ in the local training region, Ez∼p(·;ϕ) [∇θ ℓGRPO (z; θ, ϕ) − ∇θ ℓGRPO (z; θ, ϕ′ )] ≤ Lρ ∥ϕ − ϕ′ ∥.
(10)
Assumption 3 captures the local sensitivity of the importance-ratio denominator, clipping boundary, and group-normalized advantages to the behavior policy. It is not intended as a global smoothness claim; it is the regime in which the stale-rollout analysis is meant to be applied. Remark 1 (Relevance to GRPO). The KL regularizer in GRPO, either with a fixed coefficient β or through a target-KL controller, keeps successive policies locally close in the stable training regime, supporting the local nature of Assumption 2. All norms and constants are understood in the policy’s trainable-parameter space. Pipeline convention. We follow the asynchronous-GRPO pipeline in which a rollout batch generated by πθτ is consumed by the learner for S consecutive optimization steps before being refreshed. Thus the policy lag kt at learner step t ranges from 0 to S − 1 within each rollout cycle, and S is both the maximum staleness and the rollout reuse factor. Consequently, the M -th rollout batch corresponds approximately to learner steps t ∈ {(M − 1)S, . . . , M S − 1}, so t ≈ M S. 3.2
(11)
Staleness as a Controlled Bias
Let θt be the learner policy at optimization step t and let ϕt ≜ θt−kt
(12)
be the behavior policy used to generate the batch consumed at step t. Define the population GRPO surrogate-gradient mapping H(θ, ϕ) ≜ Ez∼p(·;ϕ) [∇θ ℓGRPO (z; θ, ϕ)] , 4
(13)
and the on-policy surrogate-gradient mapping Hon (θ) ≜ H(θ, θ). (14) These quantities are the gradients actually used by the GRPO surrogate update; they should not be confused with the total derivative of a distribution-dependent objective. Taking expectation over batch sampling, E[g(θt ; Bϕt )] = H(θt , ϕt ). (15) Adding and subtracting the on-policy surrogate gradient gives E[g(θt ; Bϕt )] = Hon (θt ) + δt , (16) where δt ≜ H(θt , ϕt ) − H(θt , θt ). (17) The term δt is the staleness bias: it captures the systematic difference between optimizing on stale rollout data and optimizing on data sampled from the current policy, including both distribution shift and behavior-policy dependence of the surrogate. 3.3
Bounding the Staleness Bias
Lemma 1 (Per-step staleness bias). Under Assumptions 1–3, ∥δt ∥ ≤ Cstale ∥θt − ϕt ∥, where p Cstale ≜ Lρ + 2Ggrad Cπ /2. Proof. Using ϕt = θt−kt , decompose δt = Ez∼p(·;ϕt ) [∇θ ℓGRPO (z; θt , ϕt )] − Ez∼p(·;θt ) [∇θ ℓGRPO (z; θt , θt )] = Ez∼p(·;ϕt ) [∇θ ℓGRPO (z; θt , ϕt ) − ∇θ ℓGRPO (z; θt , θt )] | {z }
(18) (19)
(20) (21)
behavior-policy surrogate shift
+ Ez∼p(·;ϕt ) [∇θ ℓGRPO (z; θt , θt )] − Ez∼p(·;θt ) [∇θ ℓGRPO (z; θt , θt )] . {z } |
(22)
rollout distribution shift
The first term is bounded by Lρ ∥θt − ϕt ∥ by Assumption 3. For the second term, let h(z) = ∇θ ℓGRPO (z; θt , θt ). By Assumption 1, ∥h(z)∥ ≤ Ggrad . Therefore, for P = p(·; ϕt ) and Q = p(·; θt ), ∥EP [h(z)] − EQ [h(z)]∥ ≤ 2Ggrad TV(P, Q). (23) Pinsker’s inequality and Assumption 2 give r p 1 TV(p(·; ϕt ), p(·; θt )) ≤ KL(p(·; ϕt ) ∥ p(·; θt )) ≤ Cπ /2 ∥θt − ϕt ∥. (24) 2 Combining the two bounds yields (18). 3.4
Single-Step Staleness Scaling
We next relate the stale-policy drift ∥θt − ϕt ∥ to the learning rate and policy lag. From the asynchronous update rule and Assumption 1, kt X ∥θt − ϕt ∥ = ∥θt − θt−kt ∥ ≤ η g(θt−j ; Bθt−j−kt−j ) ≤ kt ηGupd ≤ SηGupd . (25) j=1
Combining Lemma 1 with (25) gives the main single-step scaling law. Theorem 1 (Single-step staleness scaling). Under Assumptions 1–3, the staleness bias at step t satisfies ∥δt ∥ ≤ Cstale kt ηGupd ≤ Cstale SηGupd . (26) Consequently, the asynchronous GRPO update can be written as θt+1 = θt + η (Hon (θt ) + ξt + δt ) , (27) where ξt ≜ g(θt ; Bϕt ) − H(θt , ϕt ) (28) is a zero-mean sampling noise term conditional on (θt , ϕt ), and δt obeys (26). 5
Single-step implication. The bias in the gradient estimator scales as O(Sη), and the stalenessinduced perturbation to a single parameter update scales as η∥δt ∥ = O(Sη 2 ).
(29)
Keeping the stale-rollout drift small relative to the local trust region gives a single-step safe region of the form Sη ≲ Csafe , (30) where Csafe absorbs the local trust-region radius, target-KL budget, curvature, and effective update scale. 3.5
Collapse-Time Scaling
Theorem 1 bounds the per-step bias, but it does not by itself determine when an unstable configuration will fail. Empirically, high-learning-rate configurations can train normally for several rollout batches and then collapse abruptly (Figures 1 and 2). We now separate two mechanisms: batch-level stale-rollout clipping and horizon-level learner drift. Batch-level clipping radius. Consider a rollout batch generated by πϕ and consumed under learner policy πθ . The clipped importance ratio clip(ρi (θ, ϕ), 1 − ϵ, 1 + ϵ) provides a meaningful policygradient signal only while a sufficient fraction of sampled ratios remain inside, or close to, the clipping interval. Let Rbatch (ϵ) denote a local radius such that the batch-level clipped-ratio signal remains non-degenerate whenever ∥θ − ϕ∥ ≪ Rbatch (ϵ).
(31)
Within one rollout reuse cycle, Eq. (25) gives ∥θt − ϕt ∥ ≤ SηGupd . Thus batch-level stale-rollout clipping is controlled by Sη, not by the cumulative number of learner steps since initialization. Horizon-level learner drift.
Suppose the local stale-rollout condition SηGupd ≪ Rbatch (ϵ)
(32)
is satisfied, so within-cycle clipping caused by stale rollouts is not the binding failure mode. Training may still collapse when the learner leaves a broader local surrogate-validity region of radius Rcrit . This radius summarizes the range over which the GRPO surrogate, local curvature, and referencepolicy regularization continue to provide a reliable optimization signal. Under the update bound in Assumption 1, t−1 X ∥θt − θ0 ∥ ≤ η g(θs ; Bϕs ) ≤ tηGupd . (33) s=0
Therefore, reaching a horizon-level radius Rcrit requires tηGupd ≳ Rcrit . Theorem 2 (Conditional collapse-time scaling, informal). Assume Assumptions 1–3 and the local stale-rollout condition (32). If collapse is governed by the learner leaving a surrogate-validity region of radius Rcrit , then the first collapse step satisfies Rcrit tcollapse · η ≳ . (34) Gupd Equivalently, in rollout-batch units, using tcollapse ≈ Mcollapse S, Mcollapse Sη ≳
Rcrit . Gupd
(35)
If SηGupd is comparable to or larger than Rbatch (ϵ), collapse can instead be governed by withincycle stale-rollout clipping, and the learner-step collapse time may depend explicitly on S. When S does not appear in the learner-step horizon. Theorem 1 and Theorem 2 describe different quantities. Theorem 1 bounds the direction error of an individual gradient estimator and therefore produces an Sη condition. Theorem 2 describes the horizon-level learner displacement after the Sη condition is already controlled. In that horizon-limited regime, increasing S mainly changes how many rollout batches correspond to a fixed number of learner steps: a larger S packs more learner steps into each rollout batch, so collapse can occur at a smaller batch count Mcollapse even if the learner-step horizon is similar. 6
Two-tier picture.
Combining the two results gives the following interpretation:
• Local stale-rollout condition: SηGupd ≪ Rbatch (ϵ) keeps within-cycle stale-rollout bias and clip saturation controlled. • Horizon-level drift condition: tηGupd ≲ Rcrit , equivalently M SηGupd ≲ Rcrit , keeps the cumulative learner drift inside the surrogate-validity region. The first condition can make the stable learning rate decrease with S; the second can make the observed threshold appear nearly independent of S when it is the active constraint. 3.6
Practical Stability Rule
For a target training horizon of T learner steps, a configuration (S, η) should satisfy both a local stale-rollout condition and a horizon-level drift condition: Rbatch (ϵ) Rcrit Sη ≪ , Tη ≪ . (36) Gupd Gupd Equivalently, Rbatch (ϵ) Rcrit . (37) , η ≪ min SGupd T Gupd The apparent dependence of the maximum stable learning rate on S depends on which constraint is active. When the horizon-level condition is binding,
Rcrit Rbatch (ϵ) ≪ , T Gupd SGupd
(38)
the maximum stable learning rate is approximately independent of S, and increasing S primarily reduces the number of rollout batches before collapse through Mcollapse Sη ≳ Rcrit /Gupd . When the local stale-rollout condition is binding, however, the stable learning rate decreases as 1/S. Scope. This analysis does not claim that stale rollouts are harmless. It separates two effects: the per-step stale-rollout bias controlled by Sη, and the horizon-level learner drift controlled by T η. The empirical observation that the learning-rate threshold can be weakly dependent on S should therefore be interpreted as evidence for the horizon-limited regime, not as a general guarantee that staleness never affects stability.
4
Experiments
Our experiments are designed to test the two-tier picture of Section 3 term by term, rather than merely to demonstrate that staleness can destabilize training. Each of the three result subsections below targets one prediction of the theory and follows the same Prediction → Observation → Takeaway structure, so that every empirical claim is tied to a specific theorem or equation. Table 1 summarizes this correspondence. Table 1: Mapping from theory to experiments. Each result subsection isolates one prediction of the staleness-aware scaling law. Theoretical prediction
Empirical question
Evidence
Local stale-rollout condition Sη ≲ Rbatch /Gupd (Thm. 1, Eq. (30))
Does the maximum stable learning rate fall as ηmax ∝ 1/S?
§4.2, Figs. 1–2
Horizon-limited collapse tcollapse η ≳ Rcrit /Gupd (Thm. 2, Eqs. (34)–(35))
For collapsing runs, is the collapse horizon set by T η and independent of S?
§4.3, Table 2
Update decomposition g = Hon +ξt +δt with ∥δt ∥ = O(Sη) (Thm. 1, Eq. (27))
Do the stable/unstable regimes correspond to diffusive/ballistic drift?
§4.4, Fig. 3
7
4.1
Datasets, Models, and Evaluation Metrics
Task and reward. We train on a mathematical-reasoning task with a rule-based, verifiable reward: a completion receives reward 1 if its final answer matches the ground truth and 0 otherwise. This binary, low-variance signal isolates the optimization dynamics of interest from reward-model noise, so that any collapse can be attributed to the staleness–learning-rate interaction rather than to reward hacking. We hold out a fixed validation split that is never used for rollouts. Models. We use two instruction-tuned policies of different scale, Llama-3.2-1B-Instruct and Llama-3.2-3B-Instruct, optimized with GRPO [Shao et al., 2024]. Following the convention of Section 2, all parameter norms, drift quantities, and constants are measured in the policy’s trainableparameter space. A KL penalty to the SFT reference policy keeps successive policies locally close, consistent with the local-smoothness regime of Assumptions 2–3. Asynchronous pipeline. We adopt the rollout-reuse pipeline of Section 3: a rollout batch generated by the snapshot πθτ is consumed by the learner for S consecutive optimization steps before the rollout workers refresh their weights. A weight synchronization (or weight sync) thus marks the boundary between consecutive rollout cycles, and the M -th weight sync occurs at learner step t ≈ M S (Eq. (11)). We sweep the maximum staleness S ∈ {8, 16, 32} against the learning rate η ∈ {1×10−6 , 5×10−7 , 2×10−7 , 1×10−7 }, holding all other hyperparameters (group size, batch size, clip range ϵ, KL coefficient β) fixed across runs so that (S, η) is the only varying factor. Evaluation metrics.
We track three quantities, each chosen to probe a specific term in the theory.
• Training Reward: the mean group reward per optimization step. A collapse manifests as the reward dropping to and remaining at zero; this is our operational definition of instability. • Gradient Cosine Similarity (Grad CosSim): the cosine similarity between consecutive applied update directions, cos g(θt ; Bϕt ), g(θt−1 ; Bϕt−1 ) . This is our direct probe of which term dominates the update in Eq. (27): a persistently high value indicates a coherent direction (the staleness bias δt ), whereas a value near zero indicates that the zero-mean sampling noise ξt dominates and successive steps decorrelate. • Validation Reward: the reward on the held-out split, evaluated periodically, used to confirm that a training-reward collapse reflects a genuine loss of the optimization signal rather than a metric artifact. 4.2
Staleness Lowers the Maximum Stable Learning Rate
Theory prediction. The single-step safe region Sη ≲ Csafe of Eq. (30), equivalently the first term Sη ≪ Rbatch /Gupd of the two-constraint rule (37), predicts that the maximum stable learning rate should scale inversely with staleness, ηmax ∝ 1/S, so that the product S ηmax is approximately constant. Observation. Figures 1 and 2 sweep (S, η) for the 1B and 3B policies. Reading across each row (fixed η, increasing S) and down each column (fixed S, decreasing η) reveals a clear monotone phase structure: the larger the staleness, the smaller the learning rate required to maintain stability. At the largest learning rate η = 10−6 , every staleness setting eventually collapses to zero reward. As η is reduced, the stable region expands from large-S to small-S configurations, and at η = 10−7 the small- and moderate-staleness runs (S = 8, 16) converge stably while only S = 32 remains unstable. Quantitatively, the stability boundary ηmax (S) moves down by roughly a factor of two each time S doubles: S = 8 is stable up to η = 2×10−7 , S = 16 up to η = 1×10−7 , and S = 32 collapses even at η = 10−7 . The product S ηmax ≈ 1.6×10−6 is invariant across the three staleness levels, and the same trend holds at both model scales. Takeaway
The maximum stable learning rate obeys ηmax ∝ 1/S (S ηmax ≈ 1.6×10−6 ), confirming that the stability boundary is set by the local stale-rollout constraint Sη ≲ Rbatch /Gupd (Thm. 1). Staleness and learning rate trade off through their product Sη, not independently.
8
4.3
An Escape-Time Scaling Law: Mcollapse S η ≈ const
Theory prediction. Once a run is in the unstable regime, Theorem 2 predicts that collapse occurs when the cumulative learner drift reaches the surrogate-validity radius Rcrit , i.e. tcollapse η ≳ Rcrit /Gupd (Eq. (34)). In learner steps this horizon depends only on η and is independent of S; in rollout-batch units it becomes Mcollapse S η ≳ Rcrit /Gupd (Eq. (35)). Observation. We record Mcollapse , the index of the weight synchronization at which the training reward first drops to zero. Table 2 reports these counts for every collapsing configuration. Table 2: Weight-synchronization index Mcollapse at which training collapses, as a function of staleness S and learning rate η (results consistent across the 1B and 3B policies). “stable” denotes runs that survive the full training horizon. In each collapsing cell we report, in parentheses, the normalized product Mcollapse · S · η̃ with η̃ ≜ η/10−7 . The product is invariant at 320 across all collapsing configurations, i.e. Mcollapse S η ≈ 3.2×10−5 ; equivalently the learner-step collapse time tcollapse = Mcollapse S depends only on η.
S=8 S = 16 S = 32 tcollapse = Mcollapse S
η = 10−6
η = 5×10−7
η = 2×10−7
η = 10−7
4 (320) 2 (320) 1 (320)
8 (320) 4 (320) 2 (320)
stable 10 (320) 5 (320)
stable stable 10 (320)
32
64
160
320
Two regularities stand out. First, converting weight-sync counts to learner steps via tcollapse = Mcollapse S (bottom row of Table 2), the collapse step depends only on η and is identical across S = 8, 16, 32: tcollapse = 32, 64, 160, 320 for η = 10−6 , 5×10−7 , 2×10−7 , 10−7 , so that tcollapse η ≈ 3.2×10−5 in every collapsing run—exactly the S-independent horizon law of Eq. (34). Second, because Mcollapse = tcollapse /S, the same fixed step budget is reached in fewer weight syncs as S grows, giving Mcollapse S η ≈ const (the normalized product equals 320 in all nine collapsing cells). This explains why collapse appears to “arrive faster” at higher staleness when watching the weight-sync counter (e.g. S = 32, η = 10−6 fails after a single rollout cycle): a larger S packs more learner steps into each batch, even though the underlying learner-step horizon is unchanged. Takeaway
For runs that collapse, the learner-step collapse time satisfies tcollapse η ≈ 3.2×10−5 , independent of S, and equivalently Mcollapse S η ≈ const (Thm. 2). The collapse horizon is governed by cumulative learner drift T η, not by staleness; S only rescales how many weight syncs fit inside that horizon. The escape-time law applies only to runs already in the unstable regime, and does not contradict the stability boundary of §4.2: by the bare horizon budget, S = 8, η = 2 × 10−7 would reach tcollapse = 160 within the training window, yet it does not collapse. The next subsection resolves this apparent tension. 4.4
Coherent vs. Diffusive Drift: Reading the Gradient Cosine Similarity
Theory prediction. The asynchronous update decomposes as g = Hon (θt ) + ξt + δt (Eq. (27)), with a systematic staleness bias ∥δt ∥ = O(Sη) (Thm. 1) and zero-mean noise ξt . When δt dominates, consecutive updates share a direction and drift is ballistic (∼ tη), reaching√Rcrit on the escape-time horizon; when ξt dominates, updates decorrelate and drift is diffusive (∼ tη), which accumulates too slowly to reach Rcrit . The Grad CosSim between consecutive updates should therefore read out which regime a run is in. Observation: unstable runs are ballistic. In every configuration that collapses (Figures 1–2), the Grad CosSim remains persistently high—frequently near 1—throughout the run leading up to the collapse. A high cosine similarity means successive updates point in a common direction, so per-step displacements add up linearly and the learner drifts ballistically toward the surrogate-validity 9
boundary, consistent with the tcollapse η ≈ Rcrit /Gupd timescale of Table 2. The collapse in the reward and validation-reward panels is correspondingly abrupt rather than gradual. Observation: stable runs are diffusive. Figure 3 isolates the small-learning-rate regime (η ∈ {8, 7, 6, 5}×10−8 ) on the 3B policy, deliberately trained over an extended horizon of roughly 1.4×103 steps—more than twice the window of the main sweep. Here the Grad CosSim rises only briefly during the initial reward climb and then decays toward zero, where it remains for the rest of training: consecutive updates are essentially √ uncorrelated, so ξt dominates δt and the learner performs a diffusive walk. This sub-linear ( tη) accumulation is the decisive point: were the drift ballistic, the escape-time law tcollapse η ≈ const would place no lower bound on η below which collapse is forbidden, so even these tiny learning rates would eventually exhaust the horizon budget. Instead, all four runs train stably for the entire extended horizon with monotonically improving validation reward and show no sign of collapse, ruling out a merely-delayed ballistic escape. Takeaway
The Grad CosSim directly witnesses the decomposition of Eq. (27): high cosine (coherent √ δt , ballistic, collapses on the tη horizon) versus near-zero cosine (noise ξt dominates, diffusive tη, stable indefinitely). The extended-horizon stability of small-η runs confirms that small Sη does not merely delay collapse—it removes the coherent drift that would cause it. Reconciling the two constraints. The two regimes are two facets of the same decomposition, and together they instantiate the two-constraint rule η ≪ min{Rbatch /(SGupd ), Rcrit /(T Gupd )} of Eq. (37). The local stale-rollout condition Sη ≲ Rbatch /Gupd governs whether δt is large enough to dominate ξt and make the drift coherent; crossing it flips a run from the diffusive (stable) to the ballistic (collapsing) regime, yielding ηmax ∝ 1/S (§4.2). The horizon-level condition T η ≲ Rcrit /Gupd then governs when a ballistic run reaches the boundary, yielding the S-independent escape-time law (§4.3). The case S = 8, η = 2×10−7 survives not because its horizon budget is unspent, but because its small Sη keeps it on the diffusive side of the first constraint, where the escape-time argument does not apply.
5
Related Work
RLHF policy optimization. RLHF commonly combines supervised fine-tuning, reward modeling, and policy optimization [Ouyang et al., 2022, Christiano et al., 2017, Kaufmann et al., 2023]. PPOstyle methods use clipped importance ratios and value baselines [Schulman et al., 2017], while GRPO removes the critic by using group-relative reward statistics [Shao et al., 2024]. Our analysis focuses on the asynchronous behavior-policy mismatch that arises when such surrogate objectives are optimized using stale rollout batches. Asynchronous and delayed optimization. Asynchronous SGD has been studied in shared-memory and parameter-server settings [Recht et al., 2011, Agarwal and Duchi, 2011, Lian et al., 2015, Li et al., 2014, Zhou et al., 2018]. Those analyses typically model staleness as a bounded delay in gradient computation. In RLHF, the delay also changes the data distribution and the behavior-policy denominator in the policy-ratio surrogate; the resulting bias is therefore not captured by delayed-SGD bounds alone. Decoupled actor-learner architectures in RL. Decoupling acting from learning is the central design pattern of large-scale distributed RL, from Gorila [Nair et al., 2015] and A3C [Mnih et al., 2016] to IMPALA [Espeholt et al., 2018], Ape-X [Horgan et al., 2018], and SEED RL [Espeholt et al., 2020]. A consistent theme is that the throughput gained by decoupling must be paid for in off-policy bias: IMPALA stabilizes high-throughput training only after adding the V-trace off-policy correction [Espeholt et al., 2018], while DD-PPO [Wijmans et al., 2020] avoids the problem by remaining fully synchronous, and reproducibility studies highlight how stale rollouts perturb actorlearner PPO dynamics [Huang et al., 2023]. Our setting differs in two respects. First, GRPO-based RLHF [Shao et al., 2024] relies on clipped importance ratios and KL regularization rather than a dedicated off-policy estimator, so the burden of stability falls on the (S, η) configuration itself. 10
Grad CosSim
Reward
lr=1e-6
lr=5e-7
0.0
0.6 0.5 0.4 0.3 0.2 0.1 0.0
1.0
1.0
1.0
0.5
0.5
0.5
0.0
0.0
0.0
0.5
0.5
S=8 S=16 S=32
0.5 0.4 0.3 0.2 0.1 0.0
0.6 0.4 0.2
lr=1e-7 0.5 0.4 0.3 0.2 0.1 0.0
1.0
1.0 0.8 0.6 0.4 0.2 0.0 0.2
0.3
0.3
0.3
0.2
0.2
0.2
0.2
0.1
0.1
0.1
0.1
0.5 1.0 0.3
Val Reward
lr=2e-7
0.0
0
200
400
Training Steps
600
0.0
0
200
400
Training Steps
600
0.0
0
200
400
Training Steps
600
0.0
0
200
400
Training Steps
600
Figure 1: Staleness–learning-rate sweep on Llama-3.2-1B-Instruct. Columns vary the learning rate (lr = η) and within each panel the curves correspond to staleness S ∈ {8, 16, 32}. Top: training reward; collapse appears as the curve dropping to and staying at zero. Middle: cosine similarity between consecutive update directions (Grad CosSim). Bottom: held-out validation reward. Reading left-to-right, reducing η enlarges the stable region from large-S to small-S settings, so that the maximum stable learning rate scales as ηmax ∝ 1/S (Section 4.2). In every collapsing run the Grad CosSim stays high before the collapse, indicating a coherent, bias-driven (ballistic) drift toward the surrogate-validity boundary; the abrupt zero-reward transition is the resulting escape (Section 4.4).
lr=1e-6
Val Reward
Grad CosSim
Reward
0.6 S=8 S=16 S=32
0.4 0.2
lr=5e-7
0.8
lr=2e-7
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.0
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0 0.5
0.0
0.5
0.5
0.5
1.0 0.5
0.5
0.5
0.5
0.4
0.4
0.4
0.4
0.3
0.3
0.3
0.3
0.2
0.2
0.2
0.2
0.1
0.1
0.1
0.1
0.0
0.0
0.0
1.0
0
200
400
Training Steps
600
0
200
400
Training Steps
600
lr=1e-7
0.8
0
200
400
Training Steps
600
0.0
0
200
400
Training Steps
600
Figure 2: Staleness–learning-rate sweep on Llama-3.2-3B-Instruct, with the same layout as Figure 1 (columns: η; curves: S ∈ {8, 16, 32}; rows: training reward, Grad CosSim, validation reward). The same monotone phase structure holds at the larger scale: higher staleness requires a smaller learning rate for stability, and collapsing runs again exhibit persistently high gradient cosine similarity preceding an abrupt collapse. The collapse weight-sync counts of Table 2 are consistent across both model scales, supporting the Mcollapse Sη ≈ const escape-time law (Section 4.3).
11
Reward 0.8
0.8
0.7
0.6
0.6
0.4
0.5 lr=8e-8 lr=7e-8 lr=6e-8 lr=5e-8
0.4 0.3 0
200 400 600 800 1000 1200 1400
Training Steps
Grad CosSim
Val Reward
0.50 0.45 0.40
0.2
0.35
0.0
0.30
0.2 0
200 400 600 800 1000 1200 1400
Training Steps
0
200 400 600 800 1000 1200 1400
Training Steps
Figure 3: Small-learning-rate regime on Llama-3.2-3B-Instruct (η ∈ {8, 7, 6, 5}×10−8 ), shown over a long horizon. Left: training reward; middle: gradient cosine similarity; right: validation reward. Unlike the collapsing runs of Figures 1–2, the Grad CosSim rises only briefly during the initial reward climb and then decays toward zero, where it remains. Near-zero cosine similarity indicates that the √ zero-mean sampling noise ξt dominates the staleness bias δt , so the learner drift is diffusive (∼ t η) rather than ballistic (∼ t η). The surrogate-validity boundary is therefore never reached, and all four runs converge stably (Section 4.4). Second, rather than proposing a new correction, we characterize when stale rollouts are tolerable, separating a per-step bias controlled by Sη from a horizon-level drift controlled by T η. Scaling laws and training stability. Scaling laws for language models relate loss or efficiency to model size, data, compute, and optimization hyperparameters [Kaplan et al., 2020, Hoffmann et al., 2022, McCandlish et al., 2018]. This paper studies a complementary scaling interaction between rollout staleness and learning rate in asynchronous policy optimization.
6
Conclusion
We analyzed asynchronous GRPO training with stale rollout batches by making the behavior policy explicit in the surrogate gradient. The resulting decomposition shows that stale rollouts introduce a perstep surrogate-gradient bias of order O(Sη) under local smoothness assumptions. The collapse-time argument should be interpreted conditionally: when within-cycle stale-rollout drift remains below a batch-level clipping radius, the observed collapse horizon is governed primarily by cumulative learner drift T η; otherwise, the stable learning rate can depend directly on Sη. This yields a two-constraint stability rule that reconciles the single-step stale-bias bound with the empirical observation that learning-rate thresholds may appear weakly dependent on staleness in the horizon-limited regime.
References Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. In Advances in Neural Information Processing Systems, volume 24, 2011. Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, volume 30, 2017. Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures. In International Conference on Machine Learning (ICML), pages 1407–1416, 2018. Lasse Espeholt, Raphaël Marinier, Piotr Stanczyk, Ke Wang, and Marcin Michalski. SEED RL: Scalable and efficient deep-RL with accelerated central inference. In International Conference on Learning Representations (ICLR), 2020. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025. 12
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556, 2022. Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado van Hasselt, and David Silver. Distributed prioritized experience replay. In International Conference on Learning Representations (ICLR), 2018. Shengyi Huang, Jiayi Weng, Rujikorn Charakorn, Min Lin, Zhongwen Xu, and Santiago Ontañón. Cleanba: A reproducible and efficient distributed reinforcement learning platform. arXiv preprint arXiv:2310.00036, 2023. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020. Timo Kaufmann, Paul Weng, Viktor Bengs, and Eyke Hüllermeier. A survey of reinforcement learning from human feedback. arXiv preprint arXiv:2312.14925, 2023. Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), pages 583–598, 2014. Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems, volume 28, 2015. Sam McCandlish, Jared Kaplan, Dario Amodei, and OpenAI Dota Team. An empirical model of large-batch training. arXiv preprint arXiv:1812.06162, 2018. Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning (ICML), pages 1928–1937, 2016. Arun Nair, Praveen Srinivasan, Sam Blackwell, Cagdas Alcicek, Rory Fearon, Alessandro De Maria, Vedavyas Panneershelvam, Mustafa Suleyman, Charles Beattie, Stig Petersen, et al. Massively parallel methods for deep reinforcement learning. arXiv preprint arXiv:1507.04296, 2015. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, volume 35, pages 27730–27744, 2022. Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36, 2023. Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems, volume 24, 2011. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024. Erik Wijmans, Abhishek Kadian, Ari Morcos, Stefan Lee, Irfan Essa, Devi Parikh, Manolis Savva, and Dhruv Batra. Dd-ppo: Learning near-perfect pointgoal navigators from 2.5 billion frames. In International Conference on Learning Representations (ICLR), 2020. Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. Distributed asynchronous optimization with unbounded delays: How slow can you go? In International Conference on Machine Learning, pages 5970–5979. PMLR, 2018. 13
A
Relaxing Bounded Updates
Assumption 1 is a convenient main-text condition. A weaker version can replace the almost-sure update bound with a bounded second moment, for example E ∥g(θt ; Bϕt )∥2 | θt , ϕt ≤ G22 . (39) Then the expected stale-policy drift obeys E [∥θt − θt−kt ∥] ≤ ηkt G2 ≤ ηSG2 ,
(40)
by Jensen’s inequality and the triangle inequality. Under standard sub-Gaussian or clipped-update conditions, the same scaling holds with high probability up to logarithmic factors. Thus the main-text O(Sη) staleness scaling is not tied to an almost-sure bound, although the constants and probability statements change.
B
Separate Rewards lr=1e-6
lr=5e-7
lr=2e-7
lr=1e-7
S=8
0.6 0.4 0.2 0.0
S=16
0.6 0.4 0.2 0.0
S=32
0.6 0.4 0.2 0.0
0
200
400
Training Steps
600
0
200
400
Training Steps
600
0
200
400
Training Steps
600
0
200
400
Training Steps
600
Figure 4: Per-staleness training-reward curves on Llama-3.2-1B-Instruct, separated into individual panels for legibility (companion to Figure 1). Each panel fixes one (S, η) pairing; collapse corresponds to the reward dropping to zero. The onset of collapse follows the escape-time scaling Mcollapse Sη ≈ const of Table 2.
14
lr=1e-6
0.8
lr=5e-7
lr=2e-7
lr=1e-7
S=8
0.6 0.4 0.2 0.0
S=16
0.8 0.6 0.4 0.2 0.0
S=32
0.8 0.6 0.4 0.2 0.0
0
200
400
Training Steps
600
0
200
400
Training Steps
600
0
200
400
Training Steps
600
0
200
400
Training Steps
600
Figure 5: Per-staleness training-reward curves on Llama-3.2-3B-Instruct, separated into individual panels for legibility (companion to Figure 2). As with the 1B policy, the collapse onset across (S, η) is consistent with the S-independent collapse horizon tcollapse η ≈ const (Section 4.3).
15