NgramRL: A New Speculative Decoding Approach That Uses Rollout History to Accelerate RL Post-Training

Reinforcement learning post-training substantially improves large models' reasoning capabilities, but the cost is steep: autoregressive rollout generation can account for over 70% of total training time. To address this bottleneck, NgramRL proposes building n-gram drafters from recent rollout history, significantly boosting decoding throughput without introducing auxiliary models.

Why speculative decoding is hard to bring directly into RL training

Existing speculative decoding performs well in inference settings but is constrained on multiple fronts in RL post-training. Model-based drafters consume already-scarce GPU memory, and more problematically, the policy evolves continuously during training, so the draft model quickly falls out of sync with the target model. Another class of model-free methods is lightweight but does not explicitly exploit repetition across training epochs—yet RL training is precisely a process in which the same prompts are rolled out repeatedly.

An overlooked draft source

The paper's key observation is straightforward: recent rollouts of the same prompt are themselves a high-quality and self-updating draft source. The continuation generated by the model itself in the previous round is often highly similar to the current round. Rather than training a draft model to guess, it is better to directly leverage this history. This is also the fundamental distinction between NgramRL and methods such as SuffixDecoding and prompt-lookup decoding: the latter mainly rely on prompt or suffix matching and do not incorporate per-epoch updates into their design.

Speculative decoding is a general framework for lossless decoding acceleration: a lighter-weight "draft" source first guesses several tokens in sequence, and then the target large model verifies these guesses in parallel in a single pass, accepting the matching prefix and rejecting tokens after the first mismatch. Because verification is a parallel forward pass and the accepted tokens follow the same distribution as the target model's own sampling results, speculative decoding theoretically does not change the output distribution—it only reduces the number of target-model forward passes. The draft source can be a small model (model-based methods) or a text-matching-based model-free method (such as prompt-lookup or SuffixDecoding). The speedup mainly depends on the "average accepted length," i.e., how many tokens can be committed per target forward pass, which in turn depends heavily on how consistent the draft is with the target distribution.

Autoregressive rollout refers to the process in RL post-training where the policy model generates complete trajectories token by token. Unlike a single request in inference serving, RL training repeatedly samples multiple trajectories for the same batch of prompts each epoch to compute advantages and gradients, making rollout a high-frequency, repetitive, and massive decoding workload. This is why rollout can account for over seventy percent of training time—it is the purest generation step in the training loop and cannot be amortized through batching like forward/backward passes.

SuffixDecoding and prompt-lookup decoding are both model-free speculative decoding methods: the former maintains a dynamic suffix tree and uses the longest suffix of the currently generated text to match continuations that have appeared in history; the latter performs n-gram matching directly within the prompt, treating segments already present in the prompt as drafts. What they share is that the draft source is static or semi-static text and is unaware of changes in the policy distribution during training. NgramRL differs by replacing the draft source with "recent rollout history" that rolls forward with epochs, allowing its draft distribution to track policy evolution—this is the structural reason it can achieve higher accepted lengths under a warm cache.

NgramRL's mechanism design

The core of NgramRL is to build a per-prompt n-gram drafter, with the draft source limited to a bounded recent rollout history. This design brings several direct benefits: no auxiliary model is needed, no drafter training is required, and no drafter state needs to reside on the GPU. The target model's verification step proceeds as usual, so the rollout distribution is preserved and no distribution shift is introduced by the acceleration.

Adaptive fan-out prefetching

CPU-side cache lookup and scheduling can eat into a substantial portion of the gains, so the paper introduces an adaptive fan-out prefetcher that predicts possible verification outcomes (j, b)—namely the accepted draft length j and the token b supplied by the target model. A causal budget allocator concentrates prefetching on high-probability outcomes, while uncovered outcomes fall back to sequential lookup without affecting committed tokens. This engineering layer is key to turning paper metrics into real throughput.

Fan-out here refers to the number of candidate continuation branches fetched in a single cache lookup. When the n-gram drafter performs CPU-side lookups, if it only probes a single path sequentially, then once the first candidate is rejected by the target model it must initiate a new lookup, and the round-trip latency between CPU and GPU cancels out the speedup gains. The adaptive fan-out prefetcher predicts the most likely verification outcome (j, b) based on historical statistics and fetches multiple candidates into a buffer in parallel in advance; the causal budget allocator then tilts resources toward high-probability outcomes under a limited budget, ensuring prefetching does not violate causality (i.e., does not depend on tokens not yet generated), and safely falls back to sequential lookup on a miss. This kind of CPU-GPU overlap engineering is a necessary step to convert theoretical accepted length into end-to-end throughput.

Measured performance and data interpretation

Across two model families and three types of reasoning and structured generation workloads, NgramRL can commit 3.60–7.77 tokens per target-model forward pass under warm-cache conditions—up to 1.99× higher than SuffixDecoding and 7.0× higher than prompt-lookup decoding. This magnitude indicates that it is not a marginal optimization but a structural improvement in rollout-stage efficiency.

On the Spider structured generation task, the prefetcher covered 96.6% of outcomes for Qwen3-8B at a candidate budget of 16, and measured rollout throughput improved by 1.38× over the synchronous version of NgramRL, approaching the 1.40× overlap upper bound. From this figure, the remaining optimization space lies mainly in the last small segment of coverage rather than in a restructuring of the overall architecture.

It is worth noting that the 3.60–7.77 accepted length is achieved under warm-cache conditions, and gains are expected to shrink on cold start or when prompt history is sparse; the paper's comparison baselines also focus on model-free speculative decoding methods and lack a side-by-side comparison with model-based drafter approaches. For teams concerned with RL training costs, NgramRL's appeal lies in zero additional GPU memory and zero drafter training, at the cost of maintaining a rollout history cache organized by prompt—shifting engineering complexity to the data pipeline side.

Warm cache refers to the situation where the drafter has accumulated enough recent rollout history for the same prompt and the n-gram hit rate is stably high. RL training naturally produces a warm cache: the same prompt is rolled out repeatedly each epoch, and history fills up quickly. During cold start or when the prompt set changes frequently, draft history is sparse and the hit rate drops, so accepted length shrinks noticeably. Therefore, the 3.60–7.77 accepted length reported in the paper should be understood as a steady-state metric for the mid-to-late stages of training, not an average over the entire process.

Spider is a cross-database Text-to-SQL benchmark whose outputs are highly structured and template-repetitive, giving it a natural advantage in n-gram hit rate—this is also why prefetch coverage on this task reaches 96.6%. The overlap upper bound refers to the theoretical throughput ceiling achievable when CPU-side prefetching and GPU-side verification fully overlap; 1.38× approaching 1.40× indicates that the remaining bottleneck is no longer in prefetch scheduling but in coverage and cache hits themselves.

Implications for RL post-training engineering

Rollout accounting for over seventy percent of training time means that any acceleration on the rollout side will be amplified almost proportionally in total training duration. NgramRL turns the intuition that "training history is the draft" into a deployable system, and the verification step guarantees the distribution remains unchanged, making it a low-risk modification. For tasks with high repetition such as structured generation, the gains are especially substantial; for open-ended, low-repetition generation scenarios, whether the n-gram hit rate can be maintained still requires validation on more tasks.

One-line Summary

NgramRL builds n-gram drafters from recent rollout history to losslessly accelerate rollout decoding in RL post-training.

Paragraph Summary

In RL post-training, autoregressive rollout can account for over 70% of training time and is the main cost bottleneck. Existing speculative decoding is hard to transfer directly: model-based drafters consume GPU memory and fall out of sync as the policy evolves, while model-free methods do not exploit the repetition of rolling out the same prompts in RL training. NgramRL proposes building per-prompt n-gram drafters from recent rollout history, requiring no auxiliary model, no drafter training, and no resident GPU state, and mitigates CPU-side lookup overhead with an adaptive fan-out prefetcher. In measurements, it commits 3.60–7.77 tokens per target forward pass under a warm cache—up to 1.99× higher than SuffixDecoding; on Spider, prefetch coverage reaches 96.6% and throughput improves by 1.38×. Target-model verification preserves the original rollout distribution, so acceleration introduces no shift, at the cost of maintaining a history cache organized by prompt.