Speculative Decoding in LLMs

Why LLM Responses Can Feel Slow

An LLM does not write an entire answer in one operation. It produces the answer in small pieces called tokens. A token may be a word, part of a word, punctuation mark, or space. After producing one token, the model adds it to the text and uses the updated text to choose the next token.

The second round cannot begin until the first round has selected “42,” because that token becomes part of the second round's input. This dependency continues for the full answer. An eighty-token response therefore needs roughly eighty model rounds after the prompt has been read.

This repeated use of a large model creates the delay that speculative decoding tries to reduce. A smaller, faster helper suggests a few upcoming tokens. The large model checks those suggestions together and keeps the ones it agrees with.

1. How Normal LLM Generation Works

At any moment, the model receives the text written so far and assigns a score to every token in its vocabulary. Those scores become probabilities, and the decoding settings choose one next token. The chosen token is appended to the text, and the same process starts again.

This process is called autoregressive decoding. “Auto” refers to the sequence using its own earlier output, and “regressive” means the next prediction depends on what has already been produced. The important point is simpler than the name: each selected token changes the input for the next step.

2. Reading the Prompt vs Writing the Answer

An LLM request has two phases. First, the model reads the prompt. Then it writes the answer token by token. Engineers call these phases prefill and decode.

The stored attention information is called the KV cache. It prevents the model from recalculating the entire prompt during every decode round. The cache saves a large amount of repeated work, but the large model must still run again for each ordinary output token.

Speculative decoding focuses on the decode phase. It tries to turn one large-model round into several approved output tokens instead of only one. It does not make the initial prompt-reading phase disappear.

3. Speculative Decoding in Plain English

Suppose the large model has generated “The fastest route is.” Instead of asking it for exactly one more token, a smaller model quickly suggests the continuation “through the cache today.” The large model then checks the proposed tokens in one pass.

The first two suggestions are accepted. The third is rejected and replaced with a token sampled from a correction distribution built from the difference between the large and small models' probabilities. Everything after the first rejected token is discarded because it was written using a continuation that is no longer valid. The round still produces three approved tokens after one large-model check.

4. One Speculative Decoding Round, End to End

Now follow the same idea through a complete round. Start with the Draft tab and move from left to right. On the Verify tab, $q$ means the draft model's probability and $p$ means the target model's probability. The exact acceptance formula is explained later in Section 7.

The rejected example emits two accepted draft tokens and one correction token. The all-accepted example emits four draft tokens and one bonus token from the target's extra distribution. In both cases, one target verification round makes forward progress.

5. Why the Target Can Verify Several Positions Together

Future output tokens are unknown during ordinary decoding. Drafting makes a candidate continuation $y_1,\ldots,y_\gamma$ available before the target runs. With the usual causal mask, each candidate position can attend to the prompt and the candidate tokens before it. The target pass returns:

These distributions correspond to different sequence positions within one teacher-forced target pass. Accelerator kernels process their matrix operations concurrently. Acceptance remains ordered afterward because a later candidate can be committed only when all earlier candidates remain in the output prefix.

6. Greedy Verification and Speculative Sampling

The verification rule depends on how the target would normally choose tokens. Deterministic greedy decoding and probabilistic sampling need different logic.

Temperature, top-k filtering, nucleus sampling, and other logit processors must be incorporated consistently before computing the effective $p_i$ and $q_i$ used by the acceptance test.

7. The Exact Acceptance Rule

Suppose the draft samples token $y_i\sim q_i$. Draw $u_i$ uniformly from zero to one and accept the proposal when:

When the target assigns at least as much probability to the proposed token as the draft does, the ratio reaches one and the token is always accepted. When the draft overestimates that token, only a fraction $p_i(y_i)/q_i(y_i)$ of those samples survive.

At the first rejection, later draft tokens are discarded and the replacement token is sampled from:

Interactive: Accept or Correct One Draft Token

The example uses two complete distributions over a four-token vocabulary. Select a token sampled by the draft and adjust the uniform random value. The final column shows where correction probability goes if rejection occurs.

8. Why the Final Distribution Is Exactly the Target Distribution

For any token $x$, the probability that the draft samples it and the verifier accepts it is:

The probability of entering the correction branch is the remaining mass $Z=\sum_x\max(0,p(x)-q(x))$. Sampling from the normalized positive difference contributes $\max(0,p(x)-q(x))$ to token $x$. Adding the accepted and corrected contributions gives:

Applying this argument at each accepted prefix position preserves the target model's autoregressive distribution. The proof concerns the exact algorithm; approximate acceptance heuristics and relaxed verification schemes can make different quality tradeoffs.

9. Expected Tokens From One Target Round

A round accepts a prefix, so later proposals count only when every earlier proposal survives. If each proposal has independent mean acceptance probability $\alpha$ and the draft length is $\gamma$, the expected number of emitted tokens, including the correction or bonus token, is:

The first term is guaranteed because the round always emits a correction or bonus token. The term $\alpha^j$ is the simplified probability that at least $j$ proposals survive. Real acceptance probabilities vary with the prompt, position, sampling settings, and draft confidence, so serving systems often adjust the speculation length dynamically.

When $\alpha=1$, every proposal is accepted and the series equals $\gamma+1$. The fraction above is interpreted by that limit because direct substitution would divide by zero.

10. The Idealized Speedup Model

Let one ordinary target step cost $T$, and let one draft step cost $cT$. Under the paper's simplifying assumption that verifying $\gamma+1$ positions takes about one target-step latency, a speculative round costs $T(1+\gamma c)$. The expected wall-time improvement is:

Increasing $\gamma$ creates more opportunities to emit tokens, but it also adds draft steps and makes the target verification chunk longer. The best lookahead depends on acceptance and measured runtime costs rather than a universal constant.

11. Why Theoretical Speedup and Real Latency Differ

The analytical equation isolates the central tradeoff, but real target verification does not have perfectly constant latency as the candidate length grows. A deployment must account for several interacting costs.

12. The KV-Cache Lifecycle

Classic two-model speculation maintains separate caches because the target and draft have different weights and hidden states. Both represent the same committed output sequence, but the exact last token already stored in each cache depends on when the runtime processes newly sampled tokens.

The correction or bonus token is sampled from a target-derived distribution, but its target KV state has not necessarily been computed when it is emitted. Implementations commonly treat it as pending input to the next round. The same pending-input convention can apply to the draft model's final proposal. Cache layouts, paged allocation, and fused verification kernels determine how expensive rollback and commitment become.

13. What Makes a Good Draft Model?

The draft mechanism must balance two competing quantities: closeness to the target raises acceptance, while low execution cost keeps drafting cheap. The strongest draft in isolation may produce less speedup than a weaker model that runs much faster.

Classic two-model speculative sampling needs $p_i$ and $q_i$ over the same token support at each position, so deployments commonly pair models using the same tokenizer and vocabulary. Alternative proposal methods use extra heads, feature prediction, prompt matches, or token trees.

14. Speculative Decoding in a Batched Serving System

Single-request latency and multi-request throughput are different objectives. In a batch, every request can accept a different number of tokens. The scheduler must handle ragged progress while deciding whether accelerator time should serve more requests, longer speculative chunks, or a mixture of both.

Under light load, spare compute can make speculation attractive for reducing time per output token. Under heavy load, ordinary continuous batching may use the target hardware efficiently enough that extra verification work lowers aggregate throughput. A serving policy should select speculation per workload and load level.

15. Important Speculative Decoding Variants

Speculative decoding describes a family of systems that propose inexpensive future work and verify it with the target. Their proposal structures and training requirements differ.

16. Minimal Speculative Sampling Pseudocode

The following pseudocode shows one sampling round. It emphasizes the probability logic and omits batching, cache allocation, end-of-sequence handling, numerical safeguards, and device communication.

def speculative_step(prefix, gamma, draft, target):
    proposals = []
    draft_distributions = []

    for _ in range(gamma):
        q = draft.next_distribution(prefix + proposals)
        token = sample(q)
        draft_distributions.append(q)
        proposals.append(token)

    target_distributions = target.score_continuation(
        prefix,
        proposals,
        include_next=True,
    )

    accepted = []
    for i, token in enumerate(proposals):
        p = target_distributions[i]
        q = draft_distributions[i]
        keep_probability = min(1.0, p[token] / q[token])

        if uniform_0_1() <= keep_probability:
            accepted.append(token)
            continue

        residual = normalize(maximum(p - q, 0.0))
        correction = sample(residual)
        return accepted + [correction]

    bonus = sample(target_distributions[gamma])
    return proposals + [bonus]

Primary Sources and Further Reading

The algorithm, exactness argument, analytical speedup model, and architectural variants in this guide are grounded in the original papers below.

• Fast Inference from Transformers via Speculative Decoding, Leviathan, Kalman, and Matias (2023)
• Accelerating Large Language Model Decoding with Speculative Sampling, Chen et al. (2023)
• SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification, Miao et al. (2024)
• Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads, Cai et al. (2024)
• EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty, Li et al. (2024)
• Dynamic Speculation Lookahead Accelerates Speculative Decoding of Large Language Models, Mamou et al. (2024)