Azimuth

Model Efficiency & Scaling2023intermediate11 min read

Fast Inference from Transformers via Speculative Decoding

تسريع الاستدلال في المُحوِّلات باستخدام فك الترميز التخميني

Leviathan, Y. · Kalman, M. · Matias, Y. — ICML

The problem

from large autoregressive Transformers is slow because decoding K tokens requires K sequential forward passes — each depending on the output of the previous one. The is typically , not arithmetic: the model's weights must be loaded from memory for every single . Existing acceleration methods like , quantization, or early exits usually require retraining, architecture changes, or alter the output distribution. There was no general way to speed up inference while keeping outputs identical and models unchanged.

The contribution

: a lossless inference acceleration algorithm that uses a small "draft" model to speculatively generate γ tokens, then verifies all of them in a single parallel forward pass of the large "target" model. A novel sampling method — speculative sampling — guarantees the output distribution is identical to the target model alone. No retraining, no architecture changes. Demonstrated 2–3× wall-time speedup on T5-XXL (11B) for translation and summarization with identical outputs.

The impact

Speculative decoding has become a standard inference-time optimization in production LLM serving systems. It inspired a family of follow-up techniques (EAGLE, Medusa, SpecInfer, staged speculative decoding) and is now built into frameworks like vLLM, TensorRT-LLM, and HuggingFace TGI. The core insight — that verification is cheaper than generation because it can be parallelized — fundamentally changed how the industry thinks about .

Imagine a court stenographer and a senior judge. The stenographer types blazingly fast but sometimes makes mistakes. The judge reads slowly but is always right. In the standard system, the judge dictates one word at a time — painfully slow. With speculative decoding, the stenographer types ahead by five words, and the judge reads all five at once: "Correct, correct, correct, wrong — here's the right word." One glance replaced four dictation steps. The transcript is exactly as if the judge dictated every word, but the courtroom finishes three times sooner.

The bottleneck: why autoregressive decoding is slow

A large autoregressive generates text one token at a time. To produce K tokens, the model must perform K sequential forward passes — each one loading the model's billions of parameters from memory, computing over the full context, and outputting a single token. The next pass cannot start until the previous token is generated.

The critical insight is that these forward passes are almost never compute-bound. Modern GPUs have enormous arithmetic , but they sit idle waiting for memory reads. This is the memory bottleneck: the time to decode a token is dominated by the time to load the model weights from high-bandwidth memory (HBM), not by the matrix multiplications themselves. The arithmetic units have spare capacity — and speculative decoding exploits exactly that spare capacity.

Open in Lab
Compare wall-time: standard decoding uses one target-model run per token; speculative decoding batches γ draft tokens into one parallel verification.
The demo wakes as you arrive…

The core idea: draft, verify, accept

Speculative decoding has three steps per iteration. First, a small, fast draft model (Mq) generates γ candidate tokens autoregressively — this is cheap because the draft model is typically 100× smaller than the target. Second, the large target model (Mp) evaluates all γ candidates plus one additional position in a single forward pass — this is the parallel verification step. Because the target model processes all positions at once (like an ), this single pass costs roughly the same as generating one token in the standard method. Third, we walk through the draft tokens one by one: accept each one whose probability under Mp is high enough relative to its probability under Mq, reject at the first failure, and sample a correction from the target model's adjusted distribution.

The result: each iteration produces between 1 and γ+1 tokens using only one serial run of the expensive target model. In the best case, all γ drafts are accepted plus one bonus token — a (γ+1)× reduction in the number of target-model calls.

Open in Lab
Watch one iteration: the draft model proposes, the target model verifies in parallel, and accepted tokens are kept while the first rejection is corrected.
The demo wakes as you arrive…

Speculative sampling: preserving the distribution exactly

The mathematical heart of the paper is the speculative sampling method. The goal is to sample a token from the target distribution p(x) while using the draft distribution q(x) to speed things up — without changing the output distribution at all.

The rule is elegant. Sample a token x from q(x). Draw a uniform random number r. If q(x) ≤ p(x), the draft model underestimated this token — the target model would have been even more likely to produce it — so accept unconditionally. If q(x) > p(x), the draft model overestimated — accept with probability p(x)/q(x), and if rejected, resample from an adjusted distribution p′(x) = normalize(max(0, p(x) − q(x))).

The key theorem proves that tokens sampled this way are distributed identically to sampling from p(x) directly. This is what makes speculative decoding lossless: the output text has exactly the same distribution as if you had run the target model alone, token by token.

P(accept x)=min⁡ ⁣(1,  p(x)q(x))P(\text{accept } x) = \min\!\left(1,\; \frac{p(x)}{q(x)}\right)
Acceptance criterion — when q(x) ≤ p(x), always accept — If the draft model's probability for token x is at most the target's, accept. Otherwise, accept with probability p(x)/q(x). This elegant rule ensures the final distribution matches p(x) exactly.
p′(x)=max⁡ ⁣(0,  p(x)−q(x))∑x′max⁡ ⁣(0,  p(x′)−q(x′))p'(x) = \frac{\max\!\bigl(0,\; p(x) - q(x)\bigr)} {\sum_{x'} \max\!\bigl(0,\; p(x') - q(x')\bigr)}
Adjusted distribution for resampling after rejection — When a draft token is rejected, we don't resample from p(x) directly — that would double-count the already-attempted region. Instead, p′(x) covers only the "excess" probability mass of p over q, guaranteeing an unbiased overall sample.
Open in Lab
Click any token to compare p(x) vs q(x) and see whether it would be accepted.
The demo wakes as you arrive…

How many tokens do we gain? The acceptance rate α

The key quantity governing speedup is α, the expected acceptance rate — the probability that a draft token passes the verification criterion. α measures how well the draft model Mq approximates the target model Mp at each step.

The paper shows that α has a clean formula: α = Σ_x min(p(x), q(x)) = 1 − D_LK(p,q), where D_LK is a symmetric divergence measuring the overlap between the two distributions. When p and q are identical, α = 1 and every draft is accepted. When they have disjoint support, α = 0.

Assuming acceptance decisions are roughly independent (the i.i.d. simplification), the expected number of tokens per iteration follows a capped geometric distribution. The speedup is then governed by two factors: α (how good the draft model is) and c (how expensive the draft model is relative to the target). When the draft model is tiny (c ≈ 0), the speedup approaches 1/(1−α). Even a modest α of 0.7 gives roughly 3× fewer target-model calls.

E[tokens]=1−αγ+11−αE[\text{tokens}] = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha}
Expected tokens per iteration (capped geometric) — With acceptance rate α and draft length γ, this formula gives the expected number of tokens produced per speculative decoding iteration. As α → 1 this approaches γ+1.
Speedup=1−αγ+1(1−α)(γc+1)\text{Speedup} = \frac{1 - \alpha^{\gamma+1}}{(1 - \alpha)(\gamma c + 1)}
Wall-time speedup factor (Theorem 3.8) — The overall speedup accounts for both the tokens gained (numerator) and the cost of running the draft model γ times (denominator, via the cost coefficient c). When c ≈ 0, the speedup equals the expected tokens per iteration.
Open in Lab
Drag α and c to see how speedup and tokens-per-iteration change for different γ values.
The demo wakes as you arrive…

Choosing the draft model and γ

The speculative sampling guarantee holds for any draft model — even a random token generator or a simple bigram model. The output distribution is always identical to the target. What changes is how fast you get there: a better draft model means higher α, which means more accepted tokens per iteration.

In practice, the authors found that draft models about two orders of magnitude smaller than the target work best. For T5-XXL (11B parameters), T5-Small (77M) gave the highest speedup — it's fast enough that its cost coefficient c is near zero, yet it's good enough to achieve α values between 0.53 and 0.75 depending on the task.

The optimal γ can be found numerically given α and c. Higher α supports larger γ before diminishing returns set in. With very low c (tiny draft model), optimal γ can be large. The paper also notes that an "oracle" that dynamically adjusts γ based on predicted acceptance could yield up to ~60% further improvement — a direction explored by later work.

The idea in code

Speculative decoding — one iteration of the core algorithmpython

Simplified to show the idea — not the real implementation.

import numpy as np

def speculative_decode_step(target_model, draft_model, prefix, gamma=5):
    """One iteration: draft γ tokens, verify in parallel, accept or correct."""

    # Step 1: Draft model generates γ candidate tokens autoregressively
    draft_tokens = []
    draft_probs = []
    current = prefix
    for _ in range(gamma):
        q = draft_model.get_distribution(current)   # q(x | prefix)
        token = np.random.choice(len(q), p=q)       # sample from draft
        draft_tokens.append(token)
        draft_probs.append(q)
        current = current + [token]

    # Step 2: Target model evaluates ALL positions in ONE forward pass
    # This is the key: verification is parallel, not sequential!
    target_probs = target_model.get_distributions_parallel(
        prefix, draft_tokens
    )  # returns p(x) for each position

    # Step 3: Accept or reject, left to right
    accepted = []
    for i in range(gamma):
        p = target_probs[i]         # target's distribution at position i
        q = draft_probs[i]          # draft's distribution at position i
        x = draft_tokens[i]         # the draft's proposed token

        # Acceptance criterion: accept if r < p(x)/q(x)
        if np.random.random() < min(1.0, p[x] / q[x]):
            accepted.append(x)      # keep the draft token
        else:
            # Reject: sample correction from adjusted distribution
            adjusted = np.maximum(0, p - q)
            adjusted /= adjusted.sum()
            correction = np.random.choice(len(adjusted), p=adjusted)
            accepted.append(correction)
            break                   # stop at first rejection

    # If all accepted, sample one bonus token from the last target dist
    if len(accepted) == gamma:
        bonus = np.random.choice(len(target_probs[gamma]),
                                 p=target_probs[gamma])
        accepted.append(bonus)

    return prefix + accepted        # 1 to γ+1 new tokens

Empirical results: 2–3× speedup with identical outputs

The authors tested speculative decoding on T5-XXL (11B parameters) on two tasks — English→German translation (WMT) and text summarization (CNN/DailyMail) — with various draft models. Using T5-Small (77M) as the draft model on a single TPU-v4:

  • Translation with (T=0): 3.4× speedup, α = 0.75
  • Translation with sampling (T=1): 2.6× speedup, α = 0.62
  • Summarization with greedy decoding (T=0): 3.1× speedup, α = 0.65
  • Summarization with sampling (T=1): 2.3× speedup, α = 0.53

Greedy decoding consistently yields higher α and greater speedup because the distributions are sharper — a concentrated distribution is easier for the draft model to match. All speedups came with provably identical outputs: not approximately the same, but drawn from the exact same distribution.

Open in Lab
Filter by task and sampling method to explore the full results table from the paper.
The demo wakes as you arrive…

Compute trade-offs: latency vs. arithmetic operations

Speculative decoding trades arithmetic operations for latency. Each iteration runs the target model on γ+1 positions in parallel — when drafts are rejected, those extra computations are "wasted." The total arithmetic operations may increase by 1.1–1.6× depending on α and γ.

But this trade-off is favorable because inference is memory-bound, not compute-bound. The GPU's arithmetic units have spare cycles anyway. What matters is how many times you must load the model weights from memory — and speculative decoding reduces that count dramatically (by the speedup factor). Each weight read now produces multiple tokens instead of one.

Crucially, the memory access pattern improves: the target model's weights and are read once per iteration rather than once per token. This is why the method works best when memory bandwidth is the bottleneck — which is almost always the case for large model inference with small batch sizes.

What speculative decoding unlocked

  1. 2022

    Speculative Decoding (this paper)

    Introduced the draft-verify-accept framework with lossless output guarantee. 2–3× speedup on T5-XXL without retraining.

  2. 2023

    Speculative Sampling (DeepMind)

    Independent concurrent work by Chen et al. confirming 2–2.5× speedup on Chinchilla 70B with the same theoretical framework.

  3. 2023

    SpecInfer & Medusa

    Extended speculation to tree-structured drafts, verifying multiple candidate sequences in one pass for higher acceptance rates.

  4. 2024

    EAGLE & EAGLE-2

    Learned draft heads that predict feature representations rather than tokens, achieving 3–5× speedup with dynamic draft trees.

  5. 2024

    Framework Integration

    vLLM, TensorRT-LLM, and HuggingFace TGI all shipped built-in speculative decoding support, making it a production standard.

The deepest impact of speculative decoding is the paradigm shift it introduced: the realization that verification is fundamentally cheaper than generation in autoregressive models. Generation must be sequential — each token depends on the previous one. But verification is parallel — given a proposed sequence, the model can check all positions at once. This asymmetry is now exploited across the entire LLM serving stack, from custom hardware schedulers to inference APIs, and has become one of the most important optimization primitives in the era of large language model deployment.

CitationLeviathan, Kalman, Matias. Fast Inference from Transformers via Speculative Decoding. ICML, 2023.

Terms in this paper