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

1 Introduction

• Rollout generation can exceed 70% of RL post-training step time, making it a major target for reducing training cost [8].Each GRPO step samples many autoregressive completions per prompt before gradient computation [17] [19] [20] [6].Source: §1 · p. 1
• Existing model-based drafters consume scarce GPU memory and can become misaligned as the policy changes, while model-free drafters use only single-generation evidence [2] [12] [13].The single-generation limit leaves cross-rollout repetition unused.Source: §1 · p. 1
• Across consecutive epochs, prior rollouts cover 48–96% of later rollouts, with recurring spans of 7–23 tokens.This prompt-conditioned temporal locality motivates using recent policy outputs as drafts.Source: §1 · p. 2
• NgramRL builds a bounded per-prompt n-gram drafter from recent policy rollouts, without an auxiliary model, drafter training, or persistent GPU-resident drafter state.Its own policy outputs provide a self-updating draft source as the policy evolves.Source: §1 · pp. 1–2
• An adaptive fan-out prefetcher prepares drafts for likely verification outcomes during the forward, while uncovered outcomes fall back without changing committed tokens or the rollout distribution.A causal budget allocator concentrates candidates on likely outcomes.Source: §1 · p. 2

2.1 Background: The Rollout Bottleneck

• Rollout generation can exceed 70% of GRPO step time, and GPU-memory saturation, a changing policy, and cross-step repetition constrain suitable speculative drafters [8] [13].GRPO samples completion groups, scores them, and updates the policy from group-relative advantages [20].Source: §2.1 · p. 2

2.2 Related Work

• Model-based drafters add trainable parameters and assume a fixed target, while model-free methods draw on a prompt, datastore, or single decode; SuffixDecoding serves a fixed model [2] [12] [3] [10] [14].NgramRL instead operates during RL training, where prompts recur and the policy changes.Source: §2.2 · p. 2
• Structured-generation outputs share schema tokens, keywords, and boilerplate, and repeated prompts amplify this regularity for rollout-derived n-gram caching.The paper identifies text-to-SQL, code generation, and tool or API calls as examples.Source: §2.2 · p. 2

3.2 Per-Prompt N-gram Cache

• For each prompt, NgramRL builds a cache from prior rollouts, maps n−1-token contexts to observed continuations and frequencies, and retains a recent window to limit size and policy mismatch.The cache extracts n-grams across a configurable order range; that range trades memory against drafting quality.Source: §3.2 · p. 3

3.3 Draft-and-Verify

• The policy verifies proposed continuations, accepting drafts or resampling on rejection so the resulting tokens remain exactly distributed as the policy’s outputs.This correction leaves rollouts, rewards, advantages, and gradients identical in distribution to non-speculative training.Source: §3.3 · p. 3

3.4 N-Gram Prefetcher

• NgramRL’s CPU cache prefetches next-step drafts during the current forward, addressing host–device serialization that otherwise leaves the GPU idle for ∼29% of each iteration.Figure 3 illustrates the overlap and reports an iteration reduction from 26.1 to 19.2 ms.Source: §3.4 · pp. 3–4, Figure 3 · p. 4

3.4.1 Adaptive Bonus-Token Fan-out Prefetcher.

• The prefetcher prepares step t+1 drafts keyed by the prior verification outcome (j, b), then resolves the realized outcome with a constant-time key probe.On a miss, only that request performs the ordinary sequential lookup; committed tokens remain unchanged and decoding falls back at worst to the synchronous baseline.Source: §3.4.1 · p. 4
• The allocator uses trailing accept-length and bonus-candidate coverage statistics to distribute the candidate budget, concentrating fan-out near recent acceptance modes.Full-accept branches need only one candidate because the bonus is the next token of a cached trajectory and is the top candidate about 90% of the time.Source: §3.4.1 · p. 4

3.5 Integration and Generality

• The cache attaches to verl’s vLLM rollout worker and requires no changes to the reward model, optimizer, or policy architecture.The authors state that it applies to RL-style setups where prompts recur.Source: §3.5 · p. 4

4.1.3 Accepted-Length Comparison and Dynamics.

• 3.6–7.8 tokens per step in the stable regime, with 1.2–1.99× improvement over SuffixDecoding and up to 7.0× over PLD; NgramRL leads on every task overall.The advantage is largest where completions are prompt-specific and smallest on CodeContests, where cross-prompt boilerplate favors a global cache.Source: §4.1.3 · p. 5, Table 1 · p. 5
• At k=16, accepted lengths have a heavy tail: on Spider, at least 12 tokens are accepted on 14.1% of steps and all 16 on up to 10.1%.These long accepts are verbatim replays of prior-epoch solutions; the authors use k=16 to capture them.Source: §4.1.3 · p. 5, Figure 5 · p. 6
• Spider acceptance peaks mid-run then declines as SQL outputs diversify and older rollouts go stale, while GSM8K and CodeContests acceptance strengthens through training.Consecutive-epoch Spider rollouts share 7–23-token substrings, and an earlier rollout covers 48–96% of a later one.Source: §4.1.3 · p. 5, Figure 4 · p. 6

4.1.4 N-gram Cache Design Ablations.

• For Qwen3-8B on GSM8K, acceptance saturates beyond nmax=6 as cache size grows super-linearly, so the authors set nmax=6.A longer k raises acceptance until it saturates near 16 without changing cache size; both values are set at the knee of their speedup curves and transfer to other experiments.Source: §4.1.4 · p. 5, Figure 6 · p. 6
• A per-prompt cache reaches 3.05 accepted tokens per step, versus 2.41 for a global bucket and 2.43 for SuffixDecoding; expanding SuffixDecoding to 40k responses reaches only 2.65.The comparison attributes the gain to prompt-conditioned lookup rather than cache size.Source: §4.1.4 · p. 5, Table 2 · p. 6
• A window of 4 retains 79–91% of full acceptance at a fraction of the memory; beyond w=16, more history does not help and slightly lowers GSM8K acceptance.The authors connect the decline to stale rollouts and Spider’s mid-run decrease.Source: §4.1.4 · p. 5, §4.1.3 · p. 5, Table 3 · p. 6

4.1.5 N-gram Prefetcher.

• At N=8, Spider prefetch coverage reaches 0.95 and saturates at 0.97 by N=16; GSM8K and CodeContests reach 0.65 and 0.49 at N=32.Coverage plateaus within a few training steps, and pushing N past the knee buys little while prefetch-chain cost grows linearly.Source: §4.1.5 · pp. 6–7, Figure 7 · p. 6
• 1.38× of the 1.40× overlap ceiling on Spider for Qwen3-8B at N=16, with 96.6% coverage; DeepSeek-7B reaches its 1.21× ceiling with 99.5% coverage.On GSM8K and CodeContests, the mechanism yields 1.05–1.06× against ceilings of 1.10× and 1.14×, respectively; misses fall back to sequential lookup.Source: Figure 7 · p. 6, §4.1.5 · p. 7

• Across two model families and three workloads, NgramRL commits 3.60–7.77 tokens per target-model forward, up to 1.99× more than SuffixDecoding and 7.0× more than prompt-lookup decoding.Source: §5 · p. 7
• NgramRL builds bounded per-prompt n-gram caches from recent policy rollouts, avoiding auxiliary models, drafter training, and GPU-resident drafter state.Source: §5 · p. 7
• The adaptive fan-out prefetcher improves measured rollout speed by up to 1.38× over synchronous execution while preserving the rollout distribution.It prepares drafts for likely verification outcomes; uncovered requests fall back to sequential lookup without altering the rollout distribution.Source: §5 · p. 7