History Doesn't Repeat Itself but Rollouts Rhyme: Accelerating Reinforcement Learning with RhymeRL

Training a large language model to reason with reinforcement learning is dominated by the "rollout" step, where the model slowly generates long chains of thinking tokens one at a time, leaving GPUs almost half idle; this paper (Shanghai Jiao Tong University and ByteDance — Jingkai He, Dong Du, Yubin Xia, Haibo Chen, and colleagues) presents RhymeRL, which exploits a striking fact — the model's answers from the previous training round are 75 to 95 percent identical to this round's — to speculatively generate rollouts far faster and to balance the uneven work across GPUs, all without changing the learning algorithm or hurting accuracy.

The argument in one glance

Problem

Reinforcement learning for reasoning leaves GPUs almost half idle

Reinforcement learning (RL) has become the main way to teach a large language model to reason — models like DeepSeek-R1 are trained this way to get better at math, coding, and logic. Unlike ordinary pre-training, an RL step has three stages that pass work between different kinds of workers: rollout (the model generates responses to a batch of prompts, with long chains of "thinking" tokens), reward (each response is scored, by running tests or a reward model), and train (the scores drive a weight update). The whole process repeats for many rounds, or epochs. The trouble is that the GPUs doing this sit idle much of the time — state-of-the-art RL systems waste more than 46 percent of their GPU capacity — for two reasons. First, the rollout stage dominates: because reasoning models generate very long responses (test-time scaling), rollout consumes 84 to 91 percent of the total step time, and worse, generating text is autoregressive — the model produces one token at a time, each step depending on the last — which is memory-bound and leaves the GPU's compute mostly unused. Second, the responses in a batch have wildly different lengths: some prompts yield short answers, others enormous ones, a long-tail effect. Because the step cannot move on to reward and training until the very longest response in the batch finishes, all the workers that finished early sit waiting — a GPU "bubble." So the most expensive stage is run in the least efficient way, and then everyone waits for the slowest.
What people did

Truncate long rollouts, shrink batches, or run fully asynchronously

Prior systems attack the idleness with scheduling tricks. Some truncate overly long rollouts so the batch is not held hostage by its longest member (as in Kimi-K2). Some reduce the batch size to lessen the long-tail effect (as in StreamRL). Others abandon the synchronous structure entirely and let rollout and training run fully asynchronously (as in AReaL), so the training GPUs need not wait for rollout to finish. Each of these reclaims some idle time.
Why it fell short

The fixes trade away accuracy or change what RL even is

The catch is that each fix pays a price the paper considers unacceptable. Truncating long rollouts throws away part of the model's reasoning, which trades accuracy for efficiency — you get a faster but worse-trained model. Shrinking the batch only modestly helps the long tail (about 10 percent) and does not address the fundamental inefficiency. Full asynchrony is the deepest change: if rollouts are generated while training proceeds, they end up using stale model weights, which alters the RL algorithm itself — the responses no longer reflect the current policy — and updating weights mid-rollout forces recomputing all the tokens generated so far, adding its own overhead. So the field faced a real dilemma: the obvious ways to fill the GPU bubbles either degrade the trained model or quietly rewrite what the reinforcement-learning procedure is doing. What was missing was a way to make rollout both faster and better-balanced while keeping the exact synchronous RL algorithm and its accuracy intact.
This paper's idea

Exploit that this round's rollouts rhyme with last round's

RhymeRL is built on an observation everyone had overlooked: across adjacent training epochs, the rollouts are remarkably similar. The reason is baked into the RL algorithm — methods like GRPO clip each update to keep the model evolving stably, so the model changes only slightly from one epoch to the next. As a result, for a given prompt, this epoch's response is 75 to 95 percent identical, token for token, to last epoch's response; and the ranking of prompts by response length is stable, with only 2 to 4 percent of responses changing rank meaningfully. History does not repeat exactly, but it rhymes — and that is enough. RhymeRL turns this into two innovations. First, HistoSpec is a speculative-decoding engine for the rollout: instead of generating tokens one at a time, it uses the previous epoch's response as a draft, proposes many tokens at once, and has the model verify them in a single batched forward pass, accepting the long correct prefix. Because the draft is 75 to 95 percent right, most tokens are accepted per pass, converting slow serial decoding into dense parallel verification — and it manages drafts with a reward-aware tree and a speculation strategy borrowed from TCP congestion control to tune how aggressively to guess. Second, HistoPipe is a two-tier scheduler that uses the stable length ranking to balance work across rollout workers ahead of time — packing long and short rollouts together so no worker becomes the lone straggler — with migration to handle the few rollouts that deviate from their history. Together these cut the idleness without touching the learning algorithm: RhymeRL reports up to a 2.6 times speedup over existing systems, scaling from dozens to thousands of GPUs, with no loss of accuracy and no change to the RL paradigm.

Why this problem is worth solving

Reinforcement learning is now the main lever for making LLMs reason better, and it is enormously GPU-expensive, so wasted GPU time is wasted money at the frontier of AI.

As the returns from ever-larger pre-training diminish, reinforcement-learning post-training has become the pivotal way to improve a model’s reasoning — the difference between a model that answers and one that thinks through hard math and code. But RL is voracious: it runs a full model-inference workload (the rollout) and a full training workload, over many epochs, on large GPU clusters. When state-of-the-art systems leave more than 46 percent of that hardware idle, the waste is measured in enormous quantities of the scarcest, most expensive compute in the industry. Cutting that idleness in half or better, as RhymeRL aims to, directly speeds up how fast reasoning models can be trained and how much they cost — which, given how central RL post-training has become, is a first-order concern for anyone building frontier models. And because the gain comes without altering the algorithm or the accuracy, it is a pure efficiency win rather than a trade-off, which is exactly the kind of improvement that gets adopted broadly.

The crucial move is recognizing structure that lets you predict the expensive work before you do it.

The reason RhymeRL can help without any trade-off is that it found genuine, exploitable redundancy where others assumed none. Rollout looks like fresh generation every epoch, so it seems inherently serial and unpredictable. But the very mechanism that stabilizes RL training — clipping updates so the model changes slowly — guarantees that the model’s behavior barely shifts between adjacent epochs, which means both what it will say (the token sequence) and how long it will say it (the length) are largely predictable from the previous epoch. That single insight is what makes the two hard problems tractable at once. The autoregressive-serialization problem yields to speculative decoding, because a highly accurate draft is exactly what speculative decoding needs to turn one-token-at-a-time into many-tokens-per-pass. The load-imbalance problem yields to proactive scheduling, because if you know each prompt’s likely response length in advance you can balance the workers before the bubble forms rather than reacting after. Both are the same idea — use history to predict the present — applied to the two distinct bottlenecks. Crucially, the prediction only needs to be approximately right: speculative decoding verifies every token so wrong guesses cost nothing but a re-draft, and the scheduler migrates the few rollouts that defy their history. That is why the similarity being a rhyme rather than a repeat is good enough.

What people did before, and where it broke

Truncate overly long rollouts. Cap response length so the batch is not held up by its longest member. Where it broke. It discards part of the model’s reasoning, trading accuracy for efficiency — a faster but worse-trained model.
Shrink the batch size. Reduce how many prompts share a batch to lessen the long-tail effect. Where it broke. It only helps the imbalance modestly (about 10 percent) and leaves the underlying inefficiency untouched.
Run rollout and training fully asynchronously. Decouple the stages so training GPUs never wait for rollout. Where it broke. Rollouts then use stale model weights, changing the RL algorithm itself, and mid-rollout weight updates force recomputing all tokens generated so far.
Generate rollouts token by token, as in normal inference. Treat rollout as ordinary autoregressive decoding. Where it broke. It is memory-bound and leaves GPU compute mostly idle, and it ignores that this epoch’s responses are nearly identical to last epoch’s.
The gap. No system exploited the strong similarity between adjacent epochs’ rollouts to make generation faster and load more balanced while keeping the exact synchronous RL algorithm and its accuracy.

How RhymeRL works

Using last epoch's rollouts to speed up and balance this epoch's

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Speculate the expensive serial work ahead of time and verify it in bulk. HistoSpec replaces one-token-at-a-time generation with a cheap draft from history that the model checks in a single parallel pass, so the slow serial dependency is broken whenever the guess is good. Turning a latency-bound serial computation into parallel work by speculatively producing it ahead of need and validating it, rather than waiting step by step, is the same approach the work on critical-slice prefetching (CRISP) covered elsewhere on this site takes, running ahead to hide a serial latency behind bulk work. RhymeRL applies it to token generation, where the historical rollout is the near-perfect speculation and the model’s batched forward pass is the verifier.

Predict from history and act before the problem happens, instead of reacting to it. RhymeRL’s scheduler does not wait for a straggler to appear; it uses each prompt’s stable length ranking to balance the workers in advance. Using a reliable prediction of what is coming to schedule proactively, rather than responding after the imbalance or stall has already cost you, is the same principle the work on predictive rather than reactive fine-grained GPU management (Predict, Don’t React) covered elsewhere on this site is built on, acting on a forecast instead of a measurement after the fact. RhymeRL’s forecast is the previous epoch’s length distribution, which tells it where the long rollouts will be before this epoch even runs.

Balance an inherently uneven workload by shifting work where it is needed. HistoPipe treats the long-tail of rollout lengths as something to actively balance — packing long and short together and migrating outliers — rather than a fixed cost to absorb. Embracing an imbalanced workload and dynamically shifting load so no worker becomes the bottleneck is the same idea the work on dynamic load shifting among microservice containers (Embracing Imbalance) covered elsewhere on this site develops, redistributing work to match uneven demand. RhymeRL does this for rollout workers, using historical length ranks as the guide for how to spread the load evenly.

Following an epoch through RhymeRL

Generating and balancing one epoch's rollouts using the last epoch's history

A trace, drawn from the paper, of how RhymeRL accelerates a rollout epoch and keeps the workers balanced.

Step 1 of 5

Assign prompts to workers by their historical length

Before generation, HistoPipe ranks the batch's prompts by the response lengths they produced last epoch and assigns them across rollout workers so each worker gets a balanced mix of long and short prompts, rather than one worker drawing all the long ones.

The stable length ranking makes this pre-balancing reliable.

Why it works

A near-perfect draft makes speculative decoding pay off. Token-by-token generation is serial and leaves the GPU idle → but a 75-to-95-percent-accurate historical draft verified in one batched pass → so many tokens are accepted per step and slow decoding becomes dense parallel compute.
Verification keeps it exact, so accuracy is untouched. Speculating tokens could risk producing different text → but the model verifies every drafted token and only accepts what it would have generated → so the output is identical to normal decoding and no accuracy is lost.
Predictable lengths let the scheduler balance in advance. Uneven response lengths create bubbles when discovered mid-flight → but each prompt’s length rank is stable across epochs → so HistoPipe assigns long and short together before generation and no worker becomes the lone straggler.
Migration absorbs the rollouts that do not rhyme. A few responses deviate from their historical length → but migrating those outliers between workers within or across steps → so occasional surprises do not recreate the long-tail bubble.
Using history changes nothing about the algorithm. Asynchrony and truncation alter accuracy or the RL paradigm → but drafting and scheduling from history only change how, not what, is computed → so RhymeRL keeps the exact synchronous RL procedure and its accuracy.

What it costs (trade-offs and scope)

It depends on the rollouts actually rhyming. The gains rest on adjacent epochs being 75 to 95 percent similar, which follows from clipped, stable RL updates; a training regime that changed the model sharply between epochs, or the very first epochs with no history, would offer less to speculate from.
Speculative decoding has overhead when guesses are poor. Each drafted-but-rejected token still costs verification work, so where the draft diverges badly the speculation can waste effort; the TCP-inspired tuning mitigates this but does not eliminate it.
It adds bookkeeping to store and index history. RhymeRL must retain each prompt’s previous-epoch response tokens and length ranking and manage a reward-aware draft tree, which is memory and management overhead a stateless rollout does not have.
Load balancing relies on the length ranking staying stable. HistoPipe’s pre-assignment assumes only a small fraction of rollouts change rank; if many did, migration would have to do more work and the balance would degrade toward the reactive case.
Reported gains are workload- and scale-dependent. The up-to-2.6-times speedup comes from specific models, datasets (math and code), and cluster sizes in a production setting; the exact improvement depends on how strongly the rollouts rhyme and how severe the imbalance is.

The evaluation

Reducing GPU idleness in LLM reinforcement-learning training

Property	Synchronous baseline (veRL)	Truncation or full async	RhymeRL
Rollout generation
Handling length imbalance
Effect on accuracy
Effect on the RL algorithm
GPU utilization and speed

A comparison of ways to reduce GPU idleness in LLM RL training. By exploiting that adjacent epochs' rollouts are 75 to 95 percent similar, RhymeRL uses HistoSpec (speculative decoding drafted from the previous epoch's response) to speed up generation and HistoPipe (load balancing by historical length ranking) to eliminate bubbles, reporting up to a 2.6 times speedup over existing methods with no accuracy loss and no change to the synchronous RL paradigm, scaling from dozens to thousands of GPUs. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (the authors’ arXiv copy, 2508.18588, of the ASPLOS 2026 paper; the arXiv title is “History Rhymes: Accelerating LLM Reinforcement Learning with RhymeRL”). The described system is the paper’s: RhymeRL accelerates LLM reinforcement-learning post-training by exploiting the observation that rollout responses are highly similar across adjacent training epochs — token-sequence similarity of 75 to 95 percent (fraction of reusable tokens) and length-distribution similarity where only 2 to 4 percent of responses change rank — a consequence of RL update clipping (for example, in GRPO) keeping model evolution stable. RhymeRL has two components. HistoSpec is a speculative-decoding inference engine that uses the previous epoch’s rollout token sequence as an accurate draft, verified in batched forward passes, with a reward-aware tree-based draft management and a speculation strategy inspired by TCP congestion control. HistoPipe is a two-tier scheduling strategy that uses the historical length distribution to balance workload among rollout workers, with intra-step and inter-step migration for anomalous rollouts. The paper reports up to a 2.6 times performance improvement over existing methods (such as veRL), without compromising accuracy or modifying the RL paradigm, evaluated in a real production environment scaling from dozens to thousands of GPUs; it states that state-of-the-art systems experience over 46 percent GPU idleness and that rollout consumes 84 to 91 percent of step time. The paper reports RhymeRL will be open source. The step-by-step walkthrough above is an illustration of the described mechanism. Exact algorithms, the draft-tree and TCP-inspired strategies, the migration policy, and the full evaluation should be read from the paper.

Background

Why training frontier models keeps becoming a hunt for hidden redundancy

It helps to see RhymeRL within a broad pattern: as training large models consumes ever more GPUs, the biggest efficiency wins increasingly come not from faster kernels but from noticing structure in the workload that lets you avoid or predict expensive work. Large-model training is a landscape of stalls — communication waits, pipeline bubbles, memory stalls, and, in reinforcement learning, the serial grind of generation and the long-tail of uneven work — and each of these is attacked by finding some regularity to exploit. RhymeRL’s regularity is temporal: the model barely changes between epochs, so its own recent history predicts its near future closely enough to speculate on and schedule around. This is a recurring shape of progress in these systems — locate a source of predictability or redundancy, then build the machinery to cash it in without changing the result. That the same insight simultaneously solves both the generation-speed problem (via speculation) and the load-balance problem (via prediction) shows how much leverage a single structural observation can carry. This drive to wring efficiency out of large-scale model training by exploiting the workload’s structure, without altering what is ultimately computed, is the same terrain the work on efficient large NLP model training with parallelism-aware optimization (Optimus-CC) covered elsewhere on this site occupies, squeezing idle time out of the training pipeline. RhymeRL’s contribution is to show that the rollouts of reinforcement learning, which look like fresh work each epoch, in fact rhyme closely enough with their own past to be generated speculatively and balanced predictively — cutting GPU idleness substantially while leaving the learning algorithm and its accuracy exactly as they were.

If you remember only three things

1. Reinforcement learning is now the main way to improve LLM reasoning, but it wastes GPUs badly — state-of-the-art systems are over 46 percent idle — for two reasons. The rollout stage (the model generating long reasoning responses) takes 84 to 91 percent of each step and is autoregressive, producing one token at a time, which is memory-bound and leaves GPU compute mostly unused. And response lengths within a batch vary wildly (a long tail), so finished rollouts wait for the single longest before reward and training can proceed, creating GPU bubbles. Existing fixes each pay an unacceptable price: truncation discards reasoning and hurts accuracy, batch shrinking helps only modestly, and full asynchrony makes rollouts use stale weights, changing the RL algorithm itself.
2. RhymeRL exploits an overlooked fact: because RL clips updates to evolve the model slowly, this epoch's rollouts closely resemble last epoch's — 75 to 95 percent of tokens are identical, and each prompt's length ranking is stable (only 2 to 4 percent change rank). It turns this into two innovations. HistoSpec is a speculative-decoding engine that uses the previous epoch's response as a draft, proposing many tokens and verifying them in one batched forward pass, so a highly accurate draft converts slow serial decoding into dense parallel verification (managed with a reward-aware draft tree and TCP-congestion-control-inspired tuning). HistoPipe is a two-tier scheduler that uses each prompt's historical length to balance rollout workers in advance — packing long and short together — and migrates the few rollouts that deviate from history.
3. RhymeRL reports up to a 2.6 times speedup over existing methods (such as veRL), scaling from dozens to thousands of GPUs in a real production environment, with no loss of accuracy and no change to the synchronous RL paradigm — because speculative verification is exact and scheduling only changes how, not what, is computed. The trade-offs: the gains depend on the rollouts actually rhyming (stable, clipped updates; not the first epochs), poor drafts waste some verification work, storing per-prompt history and a draft tree adds bookkeeping, and load balancing relies on the length ranking staying stable. The reported speedup depends on the models, datasets, and cluster scale.

Check yourself

Check your understanding

1. Why do state-of-the-art LLM reinforcement-learning systems leave GPUs so heavily underutilized (over 46 percent idle)?
2. What is RhymeRL's central observation, and why is it true?
3. How does HistoSpec use this similarity to speed up rollout generation without changing the output?
4. How does HistoPipe eliminate the long-tail bubbles, and what does RhymeRL achieve overall?

Sources

The paper is “History Doesn’t Repeat Itself but Rollouts Rhyme: Accelerating Reinforcement Learning with RhymeRL” (arXiv title “History Rhymes: Accelerating LLM Reinforcement Learning with RhymeRL”) by Jingkai He, Tianjian Li, Erhu Feng, Dong Du, Qian Liu, Tao Liu, Yubin Xia, and Haibo Chen (Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, and ByteDance), published at ASPLOS 2026, DOI 10.1145/3779212.3790172. It is available on arXiv as 2508.18588.

This explainer is written from the paper’s full text (the authors’ arXiv copy). RhymeRL accelerates LLM reinforcement-learning post-training by exploiting the strong similarity of rollout responses across adjacent training epochs (75 to 95 percent of tokens reusable, and stable length rankings with only 2 to 4 percent of responses changing rank), a consequence of RL update clipping keeping model evolution stable. It comprises HistoSpec, a speculative-decoding inference engine that uses the previous epoch’s rollout as an accurate draft verified in batched forward passes (with reward-aware tree-based draft management and TCP-congestion-control-inspired speculation tuning), and HistoPipe, a two-tier scheduler that balances workload across rollout workers using the historical length distribution, with intra-step and inter-step migration for anomalous rollouts. The paper reports up to a 2.6 times speedup over existing methods (such as veRL) without compromising accuracy or modifying the RL paradigm, evaluated in a real production environment scaling from dozens to thousands of GPUs, and notes state-of-the-art systems suffer over 46 percent GPU idleness with rollout taking 84 to 91 percent of step time. Numbers are the paper’s own; exact mechanisms and full results should be confirmed in the paper.