What does the NgramRL prefetcher do?

It builds the next step's draft tokens on the CPU while the GPU verifies the current step. It keys the prepared drafts by the possible verification outcome, a pair of accept length and bonus token, so the right one can be picked with a single probe once verification finishes.

What happens when the prefetcher guesses wrong?

Only the request that missed falls back to the normal sequential lookup. Committed tokens are unchanged, so the output stays what the target model would have produced and the worst case is the synchronous baseline.

Why not just make the cache lookup faster?

The paper measures the lookup as a negligible part of the gap. Synchronizing the GPU result to the host and scheduling the next step dominate the roughly 29% idle time, so the whole round trip has to be hidden.

How much does the prefetcher speed things up?

On Spider the paper reports 1.38× measured rollout throughput over synchronous NgramRL with Qwen3-8B at a budget of 16, and 1.21× with DeepSeek-7B. The paper frames the ceiling as set by the ratio of host time to GPU time.

LLM· 2026-10-27

NgramRL paper — Adaptive fan-out prefetching — What does it mean?

Jargon

Accept length (j): How many of the k drafted tokens the target model accepts in one verification pass, from 0 to k.
Bonus token (b): The extra token the target model emits right after the accepted prefix: resampled on a rejection, or a free token after a full accept. It is sampled on the GPU, so the CPU does not know it in advance.
Host round trip: The CPU waits for the GPU result, looks up the next draft, schedules the step and launches kernels. The GPU sits idle meanwhile. CUDA graphs attack the same kind of launch gap.
Fan-out: Preparing several candidate drafts at once, one per likely outcome, instead of waiting to learn which outcome happened.
Coverage (c): The probability that the outcome that actually happens was among the prefetched candidates.
Lossless: The committed tokens are exactly what the target model would have produced, so the optimization changes timing only, never output.

The news. On October 23, 2026, the NgramRL paper reported that its prefetcher covers 96.6% of verification outcomes on Spider with Qwen3-8B at a candidate budget of 16, and raises measured rollout throughput 1.38× over a synchronous version of the same drafter. Read the paper →

Picture a rail junction. The train, the GPU, is fast on the main line, but at the junction an operator, the CPU, must set the switches for the next siding. If the operator waits until the train arrives, the train stops. In NgramRL's measurements this host round trip idles the GPU for roughly 29% of each iteration, and the cache lookup itself is a negligible part of it; synchronization and scheduling dominate. So a faster lookup would not help. The wait has to be removed, not shortened.

The obstacle is that the next lookup depends on what verification decides. After the GPU checks k drafted tokens, the outcome is a pair (j, b): the accept length j, which the CPU can enumerate in k+1 values, and the bonus token b, which is sampled on the GPU from the whole vocabulary and ends the next context. The prefetcher predicts instead of waiting. While step t runs, it builds a draft table for step t+1 keyed by (j, b): for each accept length it takes the top few bonus-token candidates from the frequency-ranked successors in the prompt's cache and looks up a draft for each. After verification the GPU resolves the real pair with one key probe, with no content search.

Guessing wrong is cheap. On a miss only that request falls back to the ordinary sequential lookup, so a wrong guess costs time and does not change the target-sampled tokens; the committed tokens stay what the target model emitted. The guess budget is the trade: the candidate budget N is split across accept lengths to maximize expected coverage, using the recent histogram of accept lengths and each branch's coverage profile, solved greedily by marginal gain. A fully accepted draft needs only one candidate, because its bonus token is the top cached successor about 90% of the time. Past a budget of about 64 lookups, the prefetch chain itself approaches the host time it was meant to hide.

The gain follows one formula. If T_gpu is device-busy time per iteration, T_cpu is the host chain, and c is coverage, speedup is (T_gpu + T_cpu) / (T_gpu + (1 − c) × T_cpu). Take the paper's synchronous iteration of 26.1 ms with about 29% GPU idle, which gives roughly T_gpu = 18.5 ms and T_cpu = 7.6 ms (illustrative, reconstructed from those two reported figures). At c = 0.966, the Spider coverage with Qwen3-8B, speedup is 26.1 / (18.5 + 0.034 × 7.6) = about 1.39×, close to the 1.38× measured and to a ceiling of about 1.4× at full coverage. At half coverage it would be 26.1 / 22.3 = only 1.17×. The ceiling is set by the ratio T_cpu / T_gpu, so the paper notes that larger models or batches, which raise T_gpu, gain less: DeepSeek-7B reached 99.5% coverage yet a 1.21× speedup.

This prefetcher only pays when the drafter is CPU-side. It exists because the per-prompt cache lives in host memory to save GPU memory. The same instinct, keeping the GPU from waiting on launch and scheduling work, motivates CUDA graphs for decode.

Goes deeper in: LLM Serving → CUDA Graphs → Why Decode Is the Worst Case

Related explainers

NgramRL: per-prompt rollout n-gram drafting — where the drafts being prefetched come from

Frequently Asked Questions

Check what you knowMap your AI & GPU knowledge across every track — free, role-based