Speculative decoding can draft tokens from existing text or from the target’s own predictions without adding learned parameters. The target then verifies the draft. Greedy verification preserves the target’s greedy output; exact speculative sampling preserves its output distribution through an acceptance and correction procedure.


is the mean number of draft tokens accepted per verification pass. It excludes the extra token the target emits after a rejection or a fully accepted draft. Hit rate is the fraction of lookup attempts that return a draft.


Speedup depends on the number of tokens emitted per pass and the time spent drafting and verifying them. Longer drafts can yield more accepted tokens but also increase verification work.
Prompt Lookup / Gram
Suppose the model is summarizing a document. Much of the output already appears somewhere in the input. Prompt lookup treats the current context window as its corpus. Take the last tokens the target produced. Find an earlier point in the context where that same sequence appeared. The tokens that followed become our draft guesses.[1]
Larger values of make accidental matches less likely, but they also make matches harder to find. The search produces the draft without additional model inference.


Greedy verification accepts copied tokens in order until the first mismatch, then emits the target’s correction. If every copied token matches, it appends one extra target token.
# ids: all tokens so far (prompt + generation), shape [T]
n, k = 3, 10
draft = []
suffix = ids[-n:] # the n-gram to match on
for j in range(len(ids) - n): # linear scan; first match wins
if ids[j:j+n] == suffix: # same n-gram seen before?
draft = ids[j+n : j+n+k] # copy what followed it
break # first match, up to k tokens
Prompt lookup works because many generation tasks are grounded in the input. Outputs often reuse phrases from the source in summarization. Answers frequently quote the passage in document QA. The model copies most of the existing file and changes only a few lines when editing code. The correct continuation is already in the context when the output reuses text from the input, so the lookup can recover it without running another model. A successful match can copy many tokens in a single verification pass, so can be high. Both vLLM and TensorRT-LLM include prompt lookup as an optional proposer.
Hit rate depends on the workload and matching settings. A lookup miss costs search time and returns no draft. A hit supplies a continuation that the target may still reject. Prompt lookup can only propose continuations already present in the current context.
REST
REST retrieves drafts from a datastore built offline from text chosen for the target workload, such as code for coding models or conversations for assistants. It searches for a suffix of the current token sequence, starting with a configured maximum length and trying shorter suffixes until it finds a match. The lookup runs on the CPU and requires no additional model inference.
The same suffix can appear many times in the datastore, so retrieval may return several continuations. REST merges these continuations into a trie, prunes low-frequency branches, and verifies the remaining tree in one pass using tree attention.[2]


REST finds matches in cases where prompt lookup finds none because the datastore can be orders of magnitude larger than any one context window. The retrieved spans come from real text, so accepted matches can be long and can remain high.
The guesses are only as good as the corpus. A datastore will miss the idioms of a specific codebase if it is built from generic web text; a code datastore is dead weight for medical dialogue. The datastore takes disk space and has to be served alongside the model. The datastore cannot adapt to what happens during the current session because it is built ahead of time.
SuffixDecoding
Agentic workloads are most likely to repeat text the model wrote a few steps earlier. A coding agent rewrites the same function across several attempts. A multi-step pipeline calls the same tool with nearly the same arguments on every iteration. SuffixDecoding builds its corpus from that output as it is generated.[4]
It keeps two suffix trees. The per-request tree indexes the current prompt and the tokens generated so far, so it covers what prompt lookup covered. The global tree indexes the outputs of earlier requests, so it covers part of what a REST datastore covered, except the corpus is the system's own past outputs rather than an external collection. The global tree grows as the system serves traffic. Text carries higher counts in the tree when it appears more often across requests.
SuffixDecoding matches recent token sequences of several lengths against both trees. Each match identifies previously observed continuations. The method uses occurrence counts to score candidate tokens and greedily builds a speculation tree for each match. The sum of a tree’s node scores estimates how many tokens the target will accept. The target verifies the highest-scoring tree in one pass using tree attention. The appendix explains how suffix trees locate matches and how occurrence counts become scores.
SuffixDecoding caps the size of the speculation tree in proportion to the length of the matched pattern. A long match means the current text has a precise precedent, so the method drafts many tokens. A short match is weaker evidence, so it drafts fewer tokens. Prompt lookup and REST propose roughly the same amount on every hit.[4]


can be very high when the model repeats a long block of its own earlier output. Small drafts limit wasted verification work when the output is new. The paper’s hybrid method uses the suffix draft when its score exceeds a configured threshold. Otherwise, it falls back to a model-based drafter such as EAGLE-3.
Lookahead Decoding
Lookahead decoding uses each target-model call to update provisional token sequences while verifying candidates from earlier calls. It combines tokens from successive updates into n-grams and caches their continuations for later verification. The walkthrough uses trigrams, three lookahead positions, and up to two cached candidates per call. Verification uses greedy decoding.[3]
Initialization
The method keeps the confirmed prefix in P, provisional tokens in a lookahead window, and cached continuations in pool. The initial guesses come from tokens sampled from the prompt.
import random
from collections import defaultdict
N, W, G = 3, 3, 2 # N-gram length, lookahead width, verification limit.
P = prompt.copy() # Confirmed tokens; accepted output is appended here.
limit = len(prompt) + max_new_tokens
# Map each anchor token to a set of cached two-token continuations.
pool = defaultdict(set)
def seed(count):
# Supply provisional inputs for startup or newly exposed window slots.
return random.choices(prompt, k=count)
seed_row = seed(W)
A Jacobi update takes the target’s next-token predictions as the next set of guesses.[9] The first forward pass creates a second history row and emits the ordinary next token. older retains the remaining seed tokens; newer holds predictions made after the seed tokens.[5][6]
# Run once to fill the two history levels needed for trigrams.
L = len(P)
logits = target(P + seed_row).logits
# Drop the seed position that the confirmed next token will occupy.
older = seed_row[1:]
# logits[L + j] predicts the token after seed_row[j].
newer = [argmax(logits[L + j]) for j in range(W)]
# The logit after P depends only on the confirmed prefix.
P.append(argmax(logits[L - 1]))
Decoding
Each iteration retrieves up to G continuations stored under the last confirmed token. The first iteration starts with an empty pool.
while P[-1] != eos_id and len(P) < limit:
L = len(P)
anchor = P[-1] # Already in P; retrieved drafts exclude this token.
# Select from the existing pool before this call adds new candidates.
# An empty pool gives drafts=[]; verification still has a fallback.
drafts = [
list(tail)
for tail in list(pool.get(anchor, ()))[:G]
]
The two history rows form three lookahead paths after P. The older row supplies earlier guessed tokens; the newer row supplies the last token of each path. The cached drafts form additional paths for verification.
# Each list is a separate continuation of the shared prefix P.
lookahead = [
[newer[0]],
[older[0], newer[1]],
[older[0], older[1], newer[2]],
]
# The first W paths generate candidates; the remaining paths verify.
paths = lookahead + drafts
The target evaluates all paths in one packed forward pass. They share P, attend causally within themselves, and cannot read each other’s speculative tokens. scores[i] contains next-token logits at every position of P + paths[i].
The new lookahead tokens come from the target’s argmax predictions at the ends of the three lookahead paths.[3]
# Conceptual API for one packed forward pass.
scores = target(
prefix=P,
paths=paths,
attention="separate causal paths",
).logits
# The last logit on each lookahead path predicts its next token.
fresh = [
argmax(scores[j][-1])
for j in range(W)
]
Greedy verification compares each cached draft with predictions from that same forward pass. It keeps consecutive matches and appends the target’s correction at the first mismatch, or an extra target token if the whole draft matches. The longest verified continuation wins. The ordinary next token remains the fallback when no draft matches.[3]
# Start with the ordinary next token predicted after P.
best = [argmax(scores[0][L - 1])]
for i, draft in enumerate(drafts, start=W):
# predicted[k] is the target's next token after P + draft[:k].
# The slice includes len(draft)+1 predictions, allowing a bonus.
predicted = argmax(scores[i][L - 1:], axis=-1)
k = 0
while k < len(draft) and draft[k] == predicted[k]:
k += 1
# Keep k matching guesses, then the correction or bonus token.
accepted = draft[:k] + [predicted[k]]
if len(accepted) > len(best):
best = accepted
Each new trigram combines its anchor, a retained guess, and a fresh target prediction. The pool stores the final two tokens under the anchor. These entries become available to subsequent iterations.
# Use the anchors from this call, before advancing P or the history.
anchors = [anchor] + older
for j in range(W):
# Complete trigram: (anchors[j], newer[j], fresh[j]).
pool[anchors[j]].add((newer[j], fresh[j]))
The loop commits the output and advances the history by the number of emitted tokens. A one-token advance gives older = newer[1:] and newer = fresh. Longer advances expose slots that receive new seeds. Later model calls update those guesses.[6]
# Stop at the length limit or the first EOS within the accepted span.
emitted = best[:limit - len(P)]
if eos_id in emitted:
emitted = emitted[:emitted.index(eos_id) + 1]
r = len(emitted) # Advance by the number actually emitted.
P.extend(emitted)
# Both right-hand sides read the previous state before assignment.
older, newer = (
newer[r:] + seed(r - 1), # Retain W-1 older guesses.
fresh[r - 1:] + seed(r - 1), # Retain W newer guesses.
)
The initialization call runs once. The decoding loop retains its history between iterations, so each subsequent call can complete three new trigrams while verifying older candidates and producing confirmed output.[7]
Each Lookahead call processes more tokens than an ordinary decoding call. Accepting several tokens per call can compensate for that extra latency. Small-batch, memory-bound decoding can leave compute capacity available for the speculative positions; poor candidate matches or a heavily loaded GPU can erase the gain.[7]
Appendix
Suffix trees
The query
Suffix decoding searches the token sequence for the most recent stretch of tokens at each step and retrieves the tokens that followed its earlier occurrences. A scan costs per query for the sequence . A suffix tree indexes the sequence so that locating a pattern of length takes time, assuming constant-time child lookup. The method needs additional work to retrieve occurrences or construct a draft.
Suffixes and substrings
Every substring is a prefix of some suffix. The sequence ABABC has suffixes ABABC, BABC, ABC, BC, and C. The pattern AB begins two of them, so it occurs twice. An index of suffixes therefore supports searches for any substring.
From trie to suffix tree
A trie stores each suffix as a path from the root, with one token per edge. Each root-to-node path spells a substring. A query follows one edge per token of the pattern. The pattern occurs in the sequence if the walk completes. It does not occur if an edge is missing.
The trie can have nodes, since it stores suffixes of average length . A suffix tree compresses each chain of single-child nodes into one edge labeled with the whole substring. The suffix tree for ABABC is:


The tree has five leaves, one per suffix, and two internal nodes below the root.
Every internal node has at least two children. Such a tree has at most internal nodes for leaves, so the number of nodes is . Each edge label is stored as an index pair that refers to , so a label takes storage regardless of its length. Total storage is .
Textbook constructions also append an end marker that occurs nowhere else in the sequence. A suffix can end at an internal node or partway along an edge instead of at its own leaf when the sequence has no end marker. The suffix AB ends inside the edge for ABAB when the sequence is ABAB, for example. The final C in ABABC is unique, so every suffix for that sequence already ends at its own leaf.
Match points and continuations
The search compares a pattern's tokens against the edge labels along one path from the root, using at most comparisons for a pattern of length . The search takes time to report all occurrences.
The search walks along the branches of a tree until it stops at a match point, which is either a node or a position partway along an edge. The match for AB ends at a node in the example. The match for BA follows the root's B edge to a node, matches the first token of that node's ABC edge, and stops one token into the edge.
Each leaf below a match point corresponds to one occurrence of the pattern. The paths below the match point are the recorded continuations of those occurrences. The continuations below AB are ABC and C. The only continuation below BA is the remaining BC on the edge. A match inside an edge has a single continuation until the edge ends.
Ranking continuations with counts
Suffix decoding stores occurrence counts in the tree. Write for the number of occurrences of pattern . The counts are , , and in the example.
The method estimates the probability that token follows pattern as
The denominator counts occurrences with a recorded next token. Drafting stops when no continuation is available. The estimates at AB are . The only recorded next token receives an empirical probability of 1 inside a compressed edge.[4]
A continuation's score multiplies its successive token estimates:
Each factor is at most 1, so the score of a path does not increase as the path gets longer.
Suffix decoding expands a speculation tree greedily using these scores. It adds the highest-scoring continuation token at each step until the tree reaches a size budget. The paper sets the budget in proportion to the matched pattern's length:
Longer matches permit larger drafts.[4]
Growing the tree online
The per-request index starts as a suffix tree of the prompt and adds each generated token. The tree would require work per token and per request if rebuilt at every step. Online algorithms such as Ukkonen's extend a suffix tree one token at a time, with linear total construction time under standard assumptions about the alphabet and child lookup. The occurrence counts require additional bookkeeping beyond the structural updates.[8]