Gradient-Aware Scheduling: Coupling Curriculum and Staleness for Async Reinforcement Learning

Asynchronous reinforcement learning (RL) accelerates LLM training through parallel data collection, but introduces *policy lag*: experiences are collected under stale policy weights, which destabilizes learning—especially on hard tasks. We identify why: **gradient variance scales exponentially with task difficulty under staleness**, because hard tasks have narrow solution spaces corresponding to sharp loss-landscape curvature (high Hessian eigenvalues). We formalize this as a *staleness budget optimization problem* and prove that the optimal allocation follows an exponential decay: $\eta^*(d) = \eta_{\text{base}} \cdot e^{-\lambda d}$ where $\lambda = \alpha/2$ is half the Hessian growth rate. Building on this principle, we propose **GAS (Gradient-Aware Scheduling)**, a drop-in recipe for fast and stable asynchronous RL with three components: (i) a bandit-based curriculum that selects task difficulty by learning signal (ACB); (ii) execution-aware staleness budgets that keep slow tasks from bottlenecking rollout (EAAS); and (iii) curriculum–staleness coupling that tightens the staleness budget as difficulty rises (CSC). Our mechanistic analysis validates the theoretical predictions: the "safe zone" of gradient coherence follows the derived exponential boundary. On code generation benchmarks, GAS improves Pass@1 from 39.7% to 60.1% while training at $2.3\times$ the throughput of synchronous GRPO, showing that matching each task's staleness budget to its difficulty (and thus to its loss-landscape curvature) makes asynchronous RL both fast and stable.

Modern AI systems that learn to write computer code do so by trial and error: they propose a solution, run it, see whether it works, and try again. To go faster, many copies of the AI run attempts in parallel, but this means each lesson can arrive after the AI has already moved on, like correcting yesterday's homework with notes you wrote today. We found that this "out of date" feedback hurts far more on hard programming tasks than on easy ones, because hard problems demand precise code that small drifts in the AI's strategy disrupt, while easy problems tolerate small differences. We proved mathematically that the staleness an AI can tolerate should shrink exponentially with task difficulty, and built a training system, GAS, that automatically chooses which difficulties to practice and matches each one to the right allowable lag. On standard coding benchmarks, GAS trains over twice as fast as conventional methods while raising correctness from 40% to 60%. Because the same trade-off appears whenever harder tasks demand more precision, in robotics, mathematical reasoning, and games, our principle could make many kinds of AI training cheaper and less energy-intensive.