Async rollout, derived from the longest trajectory

09a found that rollout is usually the dominant term — ~95% of the step for reasoning RL. This lesson opens the rollout box and finds the reason async exists hiding inside one fact: a synchronous batch finishes when its slowest trajectory finishes, not its average one. Everything else — partial rollout, repacking, streaming queues, bounded staleness — is forced by that, and bounded by the off-policy cost of fixing it.

1 · Why the global batch is hostage to its longest trajectory

A synchronous step samples K completions per prompt and cannot start training until all of them return. So the rollout time is a max, not a mean (RL 22b):

This would be harmless if lengths were tight. They are not — reasoning outputs are heavy-tailed: most completions are short, a few think for 10,000+ tokens. For a length distribution with coefficient of variation c = σ/μ, the expected maximum of K draws grows like (lognormal extreme-value):

Plug in the typical reasoning-RL regime — K = 16, c = 1 — and the longest of the 16 is about 5× the mean. Since decode time is roughly linear in length (lesson 04), the batch spends most of its wall-clock waiting on one straggler while 15 actors sit idle. That idle is not a tuning problem; it is the shape of the distribution. This is the entire motivation for breaking the synchronous barrier.

2 · The fixes are all "stop waiting for the straggler"

Once you see τ_R as a max over a heavy tail, every rollout optimization is the same move — decouple the fast trajectories from the slow one so the batch boundary no longer pins the cluster. They compose multiplicatively (RL 22b's ladder, relative to a static-padded baseline of 1.0×):

The endpoint of that ladder is trajectory-level asynchrony: don't wait for any batch at all. Consume each finished trajectory as it lands, repack stragglers into the next micro-batch, and let the learner step on a stream. Partial rollout (pause a long generation, train, resume it later under newer weights) is the same idea pushed into a single trajectory. But every one of these moves the data off the policy that will train on it — which is the cost we have to price next.

3 · The price of overlap — staleness, and why it is a budget

Break the barrier and the learner is now training on trajectories that were generated by older weights. RL corrects for this with an importance-sampling ratio (RL 06, RL 10): a sample generated under π_θ−Δ but trained under π_θ is reweighted by

The correction is only valid while ρ stays near 1. As staleness Δ (in learner steps) grows, the two policies drift apart, more tokens fall outside the clip range, and the gradient becomes biased and high-variance. Empirically the freshness wall sits around Δ ≈ 4–8 steps, where the clipped fraction crosses ~20–25% and learning destabilizes (RL 22c). So:

4 · So a trajectory must carry its version — the systems object

Now the data schema is not bureaucracy — it is derived. To compute ρ you need the logprobs and the policy version each token was sampled under; to repack and prioritize you need lengths and rewards; to debug a reward bug you need the env events. The trajectory therefore has to be a record, not a triple:

Trajectory {
  prompt_id, task_id, curriculum_bin,
  policy_version, reference_version,   // ← needed to compute ρ and the KL baseline
  tokens, logprobs, masks, tool_calls, // ← logprobs are the denominator of ρ
  env_events, reward_components, verifier_logs,
  started_at, finished_at, actor_id, env_id,
  length_tokens, wall_time_ms, stale_by_versions  // ← the freshness check
}

That schema is the control surface for every optimization in §2 and §3: partial rollout, dynamic sampling, retry, reward caching, staleness admission, replay prioritization, and regression analysis all read or write fields of it. A framework that logs only "prompt + response + reward" cannot do any of them correctly.

5 · The async graph and where it stalls

Wire those records through services and you get the SOTA rollout plane: a prompt queue feeds an actor fleet, completions go to env/reward, finished trajectories stream into a versioned store, the learner pulls from the store, and a weight service pushes fresh policy back to the actors while a controller enforces admission SLOs.

Each edge is a place the plane can stall, and each stall has a fix and a quality risk — the risk being the §3 staleness budget cashed out in a specific way:

6 · Backpressure and admission — the controller's SLOs

Async does not mean unbounded. The controller enforces a small set of SLOs that encode the §3 budget and the §1 tail directly:

• Max policy lag: reject or downweight trajectories older than k versions (the freshness wall).
• Max rollout wall time: abort, retract, or isolate requests past the task budget (the tail cap).
• Min batch quality: avoid batches dominated by one task, one reward mode, or one length bucket.
• Queue pressure: throttle prompt admission when the store or reward services saturate.
• Replay policy: decide whether old high-reward samples are allowed, and under which objective.

SOTA patterns — each is one move on this graph

Interactive · rollout data-plane planner

Compare the synchronous wall (wait for the tail) to an async plane (overlap + repack the tail, pay a freshness penalty if lag grows). Push tail skew up and watch the synchronous wall explode while async stays flat — that gap is §1 made visible.

What carries forward

• Rollout time is a max, not a mean: τ_R = max_i τ_traj,i, and with heavy-tailed reasoning lengths the longest of K=16 is ~5× the mean. The synchronous batch is hostage to one straggler.
• Capping the tail beats shrinking K: the max grows like √(ln K) but with the full width c — so length caps, repacking, and partial rollout pay nearly linearly while lowering K barely helps.
• The endpoint is trajectory-level async — consume each finished trajectory immediately — which is why frameworks chase it.
• Overlap costs staleness, priced by the IS ratio ρ = π_θ/π_θ−Δ; the freshness wall (Δ ≈ 4–8, clip frac ~20–25%) bounds the dial. Measure reward at fixed compute.
• Therefore the trajectory is a versioned record, not a triple — the logprobs and policy version are literally the inputs to the correction, and the control surface for every other optimization.

Sources used