Lesson 13.9 · 25 min

N-gram Speculation: Draft Tokens Without a Draft Model

When an LLM is rewriting your code and most of the answer is copied from the prompt, why should it generate every copied token the slow way?

In short: Speculative decoding speeds up generation by letting cheap guesses be verified by the big model in one pass, but a separate draft model costs memory, engineering and compute. N-gram speculation drops the draft model: it finds the last few generated tokens earlier in the text (usually the prompt) and proposes whatever followed them there. The big model verifies the guesses as usual, so the output is unchanged, and on copy-heavy tasks like code editing, summarisation with quotes or RAG answers, many tokens arrive per pass almost for free.

How an LLM generates text, and why it is slow

An LLM produces text one token (word piece) at a time. Each step is a full forward pass through the model that outputs a probability for every possible next token; we pick one, append it and repeat. A 200-token reply needs 200 sequential passes.

Each pass is slow for a surprising reason: not the math, but the memory traffic. The GPU must stream all the weights (16 GB for an 8B model in FP16) from memory to produce a single token, while its compute units mostly wait. This makes decoding memory-bound. The flip side is good news: processing a handful of tokens in the same pass costs barely more than processing one.

Our running example: a code assistant asked to fix a bug in a function the user pasted. The answer is the same function with one line changed, so 90% of the output tokens already appear in the prompt.

Think of it like retyping a document with one correction A typist asked to retype a letter with one word changed does not compose each sentence from scratch. They glance at the original and copy whole phrases, slowing down only around the change. N-gram speculation lets the model “glance at the original” for its guesses.

Speculative decoding and the cost of a draft model

Speculative decoding (previous lesson) uses that cheap-to-verify property. Something fast proposes k future tokens (the draft); the big target model runs one pass over all of them, keeps the longest prefix that matches what it would have produced, and adds one token of its own. When guesses are good, several tokens are produced per target pass.

The classic drafter is a small draft model. That works, but has real costs:

• Memory: the draft model's weights and its own KV cache take GPU memory away from user batches.
• Compute: k draft passes per round are not free; a draft too large eats the savings.
• Compatibility: the draft must use the same tokenizer as the target and should be well aligned with it, so you need the right model pair.
• Engineering: two models to load, schedule, version and keep in sync.

So a natural question is: can we get useful guesses with no model at all?

What an n-gram is

An n-gram is a sequence of n consecutive tokens. In the token list s = 0 ; for x in items, the 1-grams (unigrams) are single tokens like for; the 2-grams (bigrams) are pairs like for x and x in; the 3-grams (trigrams) are triples like for x in.

Classic language models before neural networks were n-gram models: they predicted the next word from counts of what followed the previous n−1 words in a big corpus. N-gram speculation borrows the same intuition but uses a tiny, local “corpus”: the current prompt and the text generated so far.

What n-gram speculation is, step by step

N-gram speculation (also known as prompt lookup decoding) drafts tokens by pattern matching. Take the last n tokens of the current text as a search key. Look for an earlier place in the context where the same n tokens appear. If found, propose the k tokens that followed that earlier occurrence as the draft. Then verify with the target model exactly as in ordinary speculative decoding.

One round of n-gram speculation

1. Take the key: Use the last n generated tokens, e.g. n = 2: def total.
2. Search the context: Scan the prompt and earlier output for def total. It appears in the pasted code.
3. Copy the continuation: Propose the k tokens that followed it there, e.g. k = 4: ( items ) :.
4. Verify in one target pass: Run the target over the text plus the 4 draft tokens; it gives its own prediction at every position.
5. Accept and add one: Keep drafts up to the first mismatch, then append the target's own next token. No match found? Just do a normal decode step.

Practical knobs Implementations let you set the key length (often trying a longer n first, then falling back to shorter) and the maximum draft length k. Hugging Face Transformers exposes prompt lookup through a generation argument (prompt_lookup_num_tokens), and vLLM offers an ngram speculative method; check current docs for exact names.

Code: prompt lookup on a bug fix

Here the “target model” is a stand-in that returns the next token of a fixed greedy answer, so we can focus on the drafting and verification logic. In a real system, the target's predictions for all draft positions come from one forward pass.

prompt_lookup.py

# Prompt-lookup (n-gram) speculation with a stand-in "target model".
prompt = ("Fix: def total ( items ) : s = 0 ; for x in items : "
"s += x.price ; return s Answer:").split()
answer = ("def total ( items ) : s = 0 ; for x in items : "
"s += x.price * x.qty ; return s").split()   # target's greedy output
FULL = prompt + answer
def target_next(seq):                 # stand-in for one greedy model step
return FULL[len(seq)]
def ngram_draft(seq, n=2, k=4):
# find the last n tokens earlier in the text; propose what followed them
key = seq[-n:]
for i in range(len(seq) - n - 1, -1, -1):
if seq[i:i + n] == key:
return seq[i + n:i + n + k]
return []                         # no match: no draft this step
seq, passes = list(prompt), 0
while len(seq) < len(FULL):
draft = ngram_draft(seq)
passes += 1                       # ONE target pass verifies all drafts
accepted = 0
for tok in draft:                 # keep drafts while they match target
if len(seq) < len(FULL) and tok == target_next(seq):
seq.append(tok); accepted += 1
else:
break
if len(seq) < len(FULL):
seq.append(target_next(seq))  # the same pass yields one more token
print(f"pass {passes}: draft={draft} accepted={accepted}")
print("output identical:", seq == FULL)
print(f"{len(answer)} tokens in {passes} target passes (plain decoding: {len(answer)})")

Output:

pass 1: draft=[] accepted=0
pass 2: draft=[] accepted=0
pass 3: draft=['(', 'items', ')', ':'] accepted=4
pass 4: draft=['+=', 'x.price', ';', 'return'] accepted=0
pass 5: draft=['0', ';', 'for', 'x'] accepted=4
pass 6: draft=['items', ':', 's', '+='] accepted=4
pass 7: draft=[';', 'return', 's', 'Answer:'] accepted=0
pass 8: draft=[] accepted=0
pass 9: draft=[] accepted=0
pass 10: draft=[] accepted=0
pass 11: draft=['s', 'Answer:', 'def', 'total'] accepted=1
output identical: True
23 tokens in 11 target passes (plain decoding: 23)

Read the trace. Passes 1–2 find no match (Answer: def never appeared before), so they behave like plain decoding. In pass 3 the key def total matches the prompt and all 4 copied tokens are accepted, plus one target token: 5 tokens for one pass. Pass 4 shows a wrong match: the key : s matched the later spot items : s += rather than ) : s =, so the draft was rejected, costing nothing but a little wasted verification. Passes 8–10 sit around the actual bug fix (* x.qty), which appears nowhere in the prompt, so there is nothing to copy. Overall: 23 tokens in 11 passes, about 2.1× fewer target passes.

Pause and think: Why did pass 7's draft get rejected even though ; return s really does follow in the answer?

Because the target's next token after x.price was (the fix), not ;. The draft copied the old, buggy code. The first mismatch ends acceptance, and the target supplies itself.

Why the output stays exactly the same

The n-gram lookup only proposes. Every token that ends up in the output is either (a) a draft token the target model confirmed it would have produced at that position, or (b) a token the target produced itself. With greedy decoding that means token-by-token equality with plain decoding, as our output identical: True line shows.

With sampling, the same speculative-sampling acceptance rule applies. The n-gram drafter acts like a draft model whose distribution puts all its probability on the copied token, so the target accepts it with probability equal to the target's own probability of that token, and otherwise samples a replacement from its distribution with that token excluded and renormalised. The output distribution is still exactly the target's.

Small print As with any batched computation on GPUs, tiny floating-point differences between processing 1 and k + 1 positions can occasionally flip a near-tie. This is a numerical effect, not a flaw of the method.

Where it works well and where it fails

• Works well: editing or reformatting code or documents, answering from retrieved passages (RAG) with quotes, extracting fields from a document, chat where the model restates earlier content. Long, repetitive contexts help.
• Fails or does nothing: open-ended creative text, translation (output is in a different language), short prompts with little to copy, and the novel parts of any answer (like our bug fix). When no match is found it falls back to normal decoding, so the cost is small.
• Watch out for: frequent wrong matches in very repetitive text, which waste verification work, and large batch sizes, where verification is no longer nearly free.

Common mistake Turning on n-gram speculation and expecting a universal speedup. On tasks with little overlap between input and output, it rarely drafts anything useful. Measure the acceptance rate and tokens per target pass on your real traffic.

N-gram speculation vs draft-model speculative decoding

Related ideas LLMA (“Inference with Reference”, 2023) copies spans from retrieved reference documents. Lookahead decoding builds its pool of n-grams from the model's own parallel guesses rather than from the prompt. Both share the idea of cheap drafting plus exact verification.

Pause and think: Our RAG bot answers by quoting policy documents, and we cannot spare GPU memory for a draft model. Which drafting method fits, and why?

N-gram speculation (prompt lookup): the answers copy long spans from the retrieved documents in the prompt, so matches are frequent, and it needs no extra GPU memory.

Going one level deeper

The key length n is the main setting we control, and the trace of prompt_lookup.py already showed why it matters. Pass 4 used the 2-token key : s. That key appears twice in the prompt: in ) : s = 0 and in items : s += x.price. The search took the most recent one, which was the wrong one, and the whole draft was rejected.

Replaying pass 4 with a longer key

1. Use three tokens: With n = 3 the key is ) : s. This appears only once in the prompt.
2. Copy what follows: The draft becomes = 0 ; for, which is exactly what the target writes next. A rejected round turns into a fully accepted one.
3. The price of a long key: Right after the fix, the text ends in * x.qty ;. No 3-token or 2-token key ending there exists in the prompt, because x.qty is new. A long key finds nothing.
4. Fall back: So we try the long key first and shorten it only when there is no match: n = 3, then 2, then 1. The 1-token key ; does match, and we get a guess where we would otherwise have none.
5. Trust short keys less: A 1-token key matches almost anywhere, so its guess is often from the wrong place. It is worth trying only because a wrong draft costs little.

There is a second choice hidden in the search: which occurrence to copy from when there are several. Our code took the most recent one. In text that repeats a pattern with small changes, such as similar functions one after another, the most recent occurrence is often the closest match, but in pass 4 it was the wrong one. Neither choice is always right, which is another reason to measure acceptance on real traffic.

Practice: try it yourself

We will measure the drafter on its own, with no verification loop. A support bot must quote a refund policy from its prompt. For each token of the answer we ask: does the key find a match in the prompt, and is the first copied token the one the target will write? We repeat this for key lengths 1, 2 and 3. To keep it short, the index covers only the prompt.

practice_ngram_index.py

# How good is an n-gram drafter's FIRST guess, for different key lengths n?
from collections import defaultdict
context = ("policy : refunds are issued within 14 days of purchase . "
"exchanges are sent within 30 days of purchase . "
"question : when are refunds issued ? answer :").split()
answer = "refunds are issued within 14 days of purchase .".split()
def build_index(tokens, n):
# map every n-gram to the positions of the token that follows it
index = defaultdict(list)
for i in range(len(tokens) - n):
index[tuple(tokens[i:i + n])].append(i + n)
return index
print("n  lookups  hits  correct  wrong")
for n in (1, 2, 3):
index = build_index(context, n)
seq, hits, correct, wrong = list(context), 0, 0, []
for tok in answer:                       # tok = what the target will write
key = tuple(seq[-n:])
if key in index:                     # the key appears in the prompt
hits += 1
guess = context[index[key][-1]]  # use the most recent occurrence
if guess == tok:
correct += 1
else:
wrong.append(f"{' '.join(key)} -> {guess}")
seq.append(tok)
print(f"{n}  {len(answer):7d}  {hits:4d}  {correct:7d}  {wrong}")

Output:

n  lookups  hits  correct  wrong
1        9     9        4  [': -> when', 'refunds -> issued', 'are -> refunds', 'issued -> ?', 'within -> 30']
2        9     8        8  []
3        9     7        7  []

A 1-token key hits on all 9 lookups but is right only 4 times. A 2-token key hits 8 times and is right every time. A 3-token key is also always right but hits only 7 times. Now change it:

• Change index[key][-1] to index[key][0] to copy from the earliest occurrence. Predict which of the wrong n = 1 guesses become right.
• Replace answer with new text that is not in the policy, such as "you will get your money back soon .".split(). Predict the hits and correct counts for each n.
• Add fallback: for each token try n = 3, then 2, then 1, and use the first key that hits. Predict the total hits and how many guesses are right, compared with the best single n.

Pause and think: A wrong draft only costs a little wasted verification. So why not always use n = 1, which finds a match every time?

Because its guess often replaces a better one. When a longer key would have matched the right place, n = 1 may copy from the wrong place, the first draft token is rejected, and the pass yields one token instead of several. Short keys are useful only as a fallback, when longer keys find nothing.

Pause and think: Our practice index covers only the prompt. The real method also searches the text generated so far. Give a case where that matters.

When the model repeats something it wrote itself that is not in the prompt: a new variable name it uses again, or a phrase it repeats in each item of a list. The first use must be generated the slow way, but every later use can be copied from the earlier output.

Key takeaways

• Decoding is memory-bound, so verifying several guessed tokens in one pass is nearly as cheap as generating one.
• N-gram speculation drafts by matching the last n tokens earlier in the context and copying what followed.
• Target-model verification keeps the output exactly the same as plain decoding.
• It shines on copy-heavy tasks (code edits, RAG, rewriting) and does little for novel text.
• It needs no draft model, memory or training, so it is a cheap first speculative method to try.

Key terms

• N-gram: A sequence of n consecutive tokens.
• N-gram speculation: Speculative decoding where drafts are copied from earlier text that follows a matching n-gram.
• Prompt lookup decoding: Another name for n-gram speculation that searches mainly in the prompt.
• Draft: The k candidate tokens proposed before the target model verifies them.
• Target model: The main LLM whose output must be preserved.
• Acceptance rate: The fraction of draft tokens the target model confirms.

← 13.8 Speculative Decoding: Draft Fast, Verify in Parallel · 13.10 Medusa: Parallel Decoding via Multiple Prediction Heads →