How Model-Free Drafters Skip the Model Entirely

—

19 min read

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.

Generalized Verify Loop TemplateGeneralized Verify Loop Template
The proposer supplies candidate tokens. The target verifies them, keeps the accepted prefix, and discards the rejected continuation before the next drafting step.

τ\tau 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 Drafter Tax Two CurvesSpeedup Drafter Tax Two Curves
Drafting cost reduces the time saved by accepting multiple tokens per verification pass. Lower drafting cost increases speedup when the accepted-token count and verification cost stay the same.

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 / N−N-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 nn 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 nn make accidental matches less likely, but they also make matches harder to find. The search produces the draft without additional model inference.

Prompt Lookup Match and CopyPrompt Lookup Match and Copy
Prompt lookup matches the latest $n$ tokens to an earlier occurrence in the context and copies the tokens that followed it. The target verifies the copied continuation before accepting its tokens.

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 τ\tau 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 Retrieval MechanismREST Retrieval Mechanism
REST retrieves continuations for the current suffix from the datastore on the CPU. It merges them into a trie and prunes branches with low occurrence counts. The target verifies the remaining tree in one pass.

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 τ\tau 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]

SuffixDecoding Two Trees and Adaptive DepthSuffixDecoding Two Trees and Adaptive Depth
The per-request tree indexes the current prompt and generated tokens. The global tree indexes outputs from earlier requests. SuffixDecoding matches the recent tokens against both trees. Longer matches permit larger speculation trees.

τ\tau 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 O(n)O(n) per query for the sequence s1⋯sns_1 \cdots s_n. A suffix tree indexes the sequence so that locating a pattern of length pp takes O(p)O(p) 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 O(n2)O(n^2) nodes, since it stores nn suffixes of average length n/2n/2. A suffix tree compresses each chain of single-child nodes into one edge labeled with the whole substring. The suffix tree for ABABC is:

Suffix trie compression and pattern matchingSuffix trie compression and pattern matching
The suffix tree compresses the trie’s single-child chains into labeled edges. The match for AB ends at a node with continuations ABC and C. The match for BA ends one token into an ABC edge, leaving BC as its only continuation.

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 n−1n - 1 internal nodes for nn leaves, so the number of nodes is O(n)O(n). Each edge label is stored as an index pair (i,j)(i, j) that refers to si⋯sjs_i \cdots s_j, so a label takes O(1)O(1) storage regardless of its length. Total storage is O(n)O(n).

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 pp comparisons for a pattern of length pp. The search takes O(p+r)O(p + r) time to report all rr 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 c(q)c(q) for the number of occurrences of pattern qq. The counts are c(AB)=2c(\texttt{AB}) = 2, c(ABA)=1c(\texttt{ABA}) = 1, and c(ABC)=1c(\texttt{ABC}) = 1 in the example.

The method estimates the probability that token tt follows pattern qq as

P^(t∣q)=c(qt)∑t′c(qt′).\hat P(t \mid q) = \frac{c(q t)}{\sum_{t'} c(q t')}.

The denominator counts occurrences with a recorded next token. Drafting stops when no continuation is available. The estimates at AB are P^(A∣AB)=P^(C∣AB)=1/2\hat P(\texttt{A} \mid \texttt{AB}) = \hat P(\texttt{C} \mid \texttt{AB}) = 1/2. 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:

score⁡(y1:k)=∏j=1kP^(yj∣q y1⋯yj−1).\operatorname{score}(y_{1:k}) = \prod_{j=1}^{k} \hat P(y_j \mid q\, y_1 \cdots y_{j-1}).

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 T\mathcal{T} 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:

∣T∣≤α p.|\mathcal{T}| \le \alpha\, p.

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 O(n)O(n) work per token and O(n2)O(n^2) 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]

References

[1]Apoorv Saxena. Prompt Lookup Decoding. 2023.
[2]He, Zhenyu, Zhong, Zexuan, Cai, Tianle, Lee, Jason, He, Di. Rest: Retrieval-based speculative decoding. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), 2024.
[3]Fu, Yichao, Bailis, Peter, Stoica, Ion, Zhang, Hao. Break the Sequential Dependency of LLM Inference Using Lookahead Decoding. International Conference on Machine Learning, 2024.
[4]Oliaro, Gabriele, Jia, Zhihao, Campos, Daniel, Qiao, Aurick. Suffixdecoding: Extreme speculative decoding for emerging ai applications. Advances in Neural Information Processing Systems, 2026.
[7]Yichao Fu et al. Lookahead Decoding. 2023.
[8]Esko Ukkonen. On-Line Construction of Suffix Trees. 1995.