NgramRL paper — Per-prompt rollout n-gram drafting — What does it mean?
The news. On October 23, 2026, researchers at UC San Diego and West Virginia University posted NgramRL, a drafter for the rollout stage of RL post-training. Across two model families and three workloads it commits 3.60–7.77 tokens per target-model forward once its cache is warm. Read the paper →
Picture a kitchen where the head chef, the policy being trained, cooks every dish one step at a time and thinks hard about each step. In RL training the same dishes come back every epoch, and the recipe changes only a little between services. So a sous-chef keeps a stack of sticky notes for each dish, copied from the last few times it was cooked. When the dish returns, the sous-chef reads the next few steps off the notes, and the head chef checks the whole run in one glance instead of cooking each step alone.
The real setting is the rollout stage of GRPO: the policy samples a group of completions for each prompt, and this stage alone can exceed 70% of step time. A separate draft model is a poor fit here because it sits in GPU memory beside the policy, optimizer state and KV cache, and it goes stale as the policy updates. NgramRL stores, for each prompt, a table from the previous n−1 tokens to the tokens that followed them in that prompt's recent rollouts. After each step it inserts the new rollouts' n-grams with a count and a step stamp, and it evicts entries older than a window of W steps. The table lives in host memory and is queried on the CPU, so it claims no persistent GPU memory.
To draft, it looks up the longest n-gram matching the current context and proposes the saved continuation; with no match, that position decodes normally. The policy then verifies the draft in one forward pass using the standard speculative-sampling rule: accept a drafted token x with probability min(1, π(x|c) / q(x|c)), and on rejection resample from the leftover probability mass. Because verification is exact, the sampled rollouts are distributed as in ordinary training, so accuracy and convergence are unchanged.
Why keyed by prompt? Across consecutive epochs, the paper reports that a prior rollout covers 48–96% of a later one, with recurring spans of 7–23 tokens. Its Spider example shows the same text-to-SQL prompt sharing 50% of its text between steps 10 and 115, 81% between steps 300 and 407, and 100% between steps 1200 and 1305. In these examples the overlap grows as training proceeds, so the cache tends to improve as a run goes on, though the paper also notes a mid-run decline on Spider when older rollouts go stale. Single-generation drafters such as prompt-lookup decoding cannot see this, because they only copy from the current prompt. The cost is a cold start: in the paper's ablation the per-prompt cache gives 1.00 tokens per step in the first epoch, before any rollout for that prompt exists.
| Drafter | Where drafts come from | Persistent GPU memory | Follows a changing policy? |
|---|---|---|---|
| Trained draft model or heads (EAGLE, Medusa) | Learned parameters | Yes | No: proposals are rejected more as the policy drifts |
| Prompt-lookup decoding | The current prompt and context | No | Not designed to: it sees one generation |
| REST | A fixed datastore | No | No: the datastore is fixed |
| SuffixDecoding | CPU suffix tree over recent responses | No | Built for a fixed model, not keyed by prompt |
| NgramRL | Per-prompt table from recent rollouts | No | Yes: rebuilt from the policy's own rollouts |
Two numbers from the paper's ablations show where the gain comes from. First, keying by prompt is the whole trick: replacing per-prompt keys with one global bucket drops the plateau from 3.05 to 2.41 tokens per step, close to SuffixDecoding's 2.43, and quadrupling SuffixDecoding's cache to 40k responses lifts it only to 2.65. Second, history has a knee. On Qwen3-8B with GSM8K, a window of 16 steps gives 3.38 tokens per step with 3181 MB of cache, while keeping all history uses 3634 MB and gives 3.34. That is 453 MB more cache for slightly fewer accepted tokens, because older rollouts go stale. At 3.38 tokens per forward, a 400-token completion (illustrative length) needs about 118 target forwards instead of 400. Tokens per forward is a proxy; wall-clock gain also depends on drafting overhead, which is the subject of the sibling explainer on prefetching.
The boundary: the paper finds the largest gains on structured outputs such as text-to-SQL and code, where completions share schema tokens and boilerplate, and a smaller gain on free-form math reasoning. The idea also needs prompts to recur, so a one-pass run over fresh prompts would only ever see a cold cache. The measurements are in the warm-cache regime.
Goes deeper in: LLM Serving → Speculative Decoding → The Draft-Verify Idea
Related explainers
- NgramRL: adaptive fan-out prefetching — how the CPU lookup is hidden behind GPU verification
- S3R: self-sparse speculative rollouts — a different way to draft RL rollout tokens