NgramRL: Accelerating RL Post-Training for Structured Generation via Rollout-Aware N-gram Speculative Decoding

Nilesh Prasad Pandey; Jangseon Park; Jason Kong; Onat Gungor; Tajana Rosing

cs.AIOct 23, 2026

NgramRL: Accelerating RL Post-Training for Structured Generation via Rollout-Aware N-gram Speculative Decoding

Authors: Nilesh Prasad Pandey, Jangseon Park, Jason Kong, Onat Gungor, Tajana Rosing

Organizations: University of California San Diego La Jolla, CA, USA · West Virginia University Morgantown, WV, USA

Abstract

Reinforcement learning (RL) post-training improves the reasoning capabilities of large language models, but its cost is dominated by autoregressive rollout generation, which can exceed 70% of training time. Existing speculative-decoding methods are poorly suited to this setting: model-based drafters consume scarce GPU memory and may become misaligned as the policy evolves, while existing model-free methods do not explicitly exploit repetition across training epochs. We observe that recent rollouts of the same prompt provide a high-quality, self-updating draft source. Based on this insight, we propose NgramRL, a per-prompt n-gram drafter constructed from bounded recent rollout history. NgramRL requires no auxiliary model, drafter training, or persistent GPU-resident drafter state, while target-model verification preserves the rollout distribution. To hide CPU cache lookup and scheduling, we further introduce an adaptive fan-out prefetcher that predicts likely verification outcomes (j, b), consisting of the accepted draft length j and target-emitted continuation token b. A causal budget allocator concentrates prefetches on high-probability outcomes, while uncovered outcomes fall back to sequential lookup without changing committed tokens. Across two model families and three reasoning and structured-generation workloads, NgramRL commits 3.60-7.77 tokens per target-model forward in the warm-cache regime, up to 1.99x more than SuffixDecoding and 7.0x more than prompt-lookup decoding. On Spider, the prefetcher covers 96.6% of Qwen3-8B outcomes at a candidate budget of 16 and improves measured rollout throughput by 1.38x over synchronous NgramRL, approaching its 1.40x overlap ceiling.

Figures & tables

Figure 1. Overview of NgramRL’s CPU-GPU model-free speculative decoding across training epochs. Two adjacent epochs show the same prompt entering GPU policy verification. A per-prompt CPU n-gram cache proposes draft tokens and receives accepted tokens to update its history. Cache contents persist into the next epoch, connecting recurring prompts to policy-aligned, model-free drafts.

Panel of Figure 3 — Figure 3. Decode-iteration timelines illustrating the mechanism. Prefetching overlaps host work with GPU verification, reducing the iteration from 26.1 to 19.2 ms Two CPU and GPU timelines compare synchronous lookup with asynchronous fan-out prefetching. In the synchronous case, CPU launch and scheduling wait on GPU verification, leaving exposed GPU idle intervals in a 26.1-millisecond iteration. With prefetching, draft-table construction and scheduling overlap GPU execution, and the depicted iteration takes 19.2 milliseconds.

Figure 4. Tokens per decoding step over GRPO training with Qwen3-8B on GSM8K, Spider 1.0, and CodeContests. The dashed line marks the end of the first epoch. Three line charts compare PLD, REST, SuffixDecoding, and NgramRL over training steps on GSM8K, Spider 1.0, and CodeContests. NgramRL starts near one token per step while the cache is cold, then increases after prompts recur. Its largest gains occur on Spider. PLD is dashed, REST dotted, SuffixDecoding dash-dot, and NgramRL solid, so the methods can also be distinguished without color. The end of the first epoch is marked by a vertical dashed line.

Qwen3-8B
Method	GSM8K	Spider	CodeCont.
PLD ( Saxena, 2023 )	1.31 / 1.31	1.10 / 1.11	1.28 / 1.30
REST ( He et al., 2024 )	1.32 / 1.31	1.02 / 1.02	1.07 / 1.07
SuffixDec. ( Oliaro et al., 2026 )	2.42 / 2.32	4.01 / 4.15	2.50 / 2.96
NgramRL	4.00 / 4.36	5.94 / 7.77	2.70 / 3.60
DeepSeek-7B

Table 1. Tokens committed per decoding step (TPS;

k{=}16

), as overall training mean / mean over the final 30% (the stable regime; see Metrics). Best per task in bold .

Figure 5. Accepted-length distribution using

k{=}16

, aggregated over each run. A log-scale line chart shows the fraction of decode steps at each accepted draft length from zero through sixteen for four model and task combinations. Most mass occurs at zero, while all curves retain a long-acceptance tail and rise at full acceptance of sixteen draft tokens.

Panel of Figure 6 — Figure 6. Hyperparameter ablations (GSM8K, Qwen3-8B). We fix $n_{\max}{=}6$ and $k{=}16$ , each at the knee of its speedup curve. Two plots show Qwen3-8B on GSM8K. Increasing maximum n-gram order raises tokens per step with diminishing gains beyond order six, while host cache memory rises rapidly. Increasing speculation length raises tokens per step with diminishing gains beyond sixteen tokens.

Configuration	Cold epoch	Plateau
Ours, global bucket	1.55	2.41
Ours, per-prompt keys	1.00	3.05
SuffixDecoding ( Oliaro et al., 2026 )	1.90	2.43

Table 2. Global vs per-prompt cache design ablation.

Qwen3-8B
	Accepted / step (cache MB)
Task	$w{=}1$	$w{=}4$	$w{=}16$	$w{=}\infty$
GSM8K	1.87 (841)	2.81 (1878)	3.38 (3181)	3.34 (3634)
Spider	3.39 (236)	5.13 (255)	5.82 (309)	5.82 (309)
CodeCont.	1.72 (249)	2.64 (591)	2.89 (1742)	2.91 (1744)
DeepSeek-7B

Table 3. History-window ablation: accepted tokens per decode step (cache MB) as the per-prompt window

w

grows.

Panel of Figure 7 — Figure 7. Fan-out prefetcher: (a) prefetch coverage $c$ vs. candidate budget $N$ ; (b) Spider speedup over the sequential synchronous baseline at $N{=}16$ . The left plot shows prefetch coverage rising with candidate budget. Spider approaches full coverage with a small budget; GSM8K and CodeContests remain lower. The right plot reports Spider speedups at budget sixteen: 1.38 times for Qwen3-8B with coverage 0.966, and 1.21 times for DeepSeek-7B with coverage 0.995.

Speculative Decoding

Speculative decoding accelerates generation by drafting multiple tokens and verifying them in parallel with a larger target model.

See all 309 papers

Accelerating RL Post-Training Rollouts via System-Integrated Speculative Decoding
Apr 29, 2026Hayate Iso, Tiyasa Mitra, Sudipta Mondal +15Reinforcement Learning Speculative Decoding
NVIDIA
SPARK: Learning from Verification in Speculative GRPO Rollouts
Aug 5, 2026Nhat Minh Pham, Duy Tung Doan, Quang Huy Phung +3RL for Language Model Reasoning Speculative Decoding
VNU University of Engineering and Technology, Vietnam National University, Hanoi, Vietnam · Viettel AI, Viettel Group, Hanoi, Vietnam
EfficientRollout: System-Aware Self-Speculative Decoding for RL Rollouts
Jun 17, 2026Minseo Kim, Minjae Lee, Seunghyuk Oh +7RL for Language Models Reinforcement Learning
FuriosaAI · University of California, Berkeley

Apr 29, 2026J/K move · Enter open · S save

Accelerating RL Post-Training Rollouts via System-Integrated Speculative Decoding

Hayate Iso, Tiyasa Mitra, Sudipta Mondal, Rasoul Shafipour+14

NVIDIA

Reinforcement Learning Speculative Decoding LLM Inference Acceleration RL Post-Training

Open paper AskPDF arXiv

RL post-training of frontier language models is increasingly bottlenecked by autoregressive rollout generation, making rollout acceleration a central systems challenge. Many existing efficiency methods improve throughput by changing the rollout or optimization regime, for example, through off-policy execution, replay, or lower-precision generation. We study speculative decoding as a lossless acceleration primitive for RL rollouts that preserves the target model's output distribution. We implement speculative decoding in NeMo-RL with a vLLM backend, supporting both synchronous and asynchronous pipelines and enabling speculation during RL rollouts. This benefit is realizable across speculation mechanisms, such as pretrained MTP heads, small external draft models or even techniques such as Eagle3, which are traditionally applied after RL phase. This yields a deployment path for state-of-the-art speculative decoding inside RL training. In a reasoning post-training workload at 8B scale under synchronous RL, speculative decoding improves rollout throughput by 1.8x. Using a high-fidelity performance simulator, we project that combining speculative decoding with asynchronous RL yields up to 2.5x end-to-end training speedup at 235B scale.

Abstract

Speculative Decoding

Explore similar work

Accelerating RL Post-Training Rollouts via System-Integrated Speculative Decoding

SPARK: Learning from Verification in Speculative GRPO Rollouts

EfficientRollout: System-Aware Self-Speculative Decoding for RL Rollouts