Speculative Decoding

There is an awkward moment when a large language model is generating text: the expensive GPU is busy, yet much of its time is spent producing one token at a time. The prompt can be processed in parallel, but the answer cannot. Token 503 depends on token 502, which depends on token 501, so decoding becomes a long chain of small, serial steps.

Some of those steps are painfully predictable. After for i in, a small model may be perfectly capable of guessing range. It would be wasteful to ask the large model to discover every easy token from scratch. It would be equally dangerous to trust the small model whenever it sounds confident.

Speculative decoding sits between those two choices. A cheap draft model proposes a short continuation. The target model checks the whole proposal in one pass, accepts the parts that agree closely enough, and repairs the first disagreement. With the right acceptance rule, the result is not merely similar to ordinary target-model sampling. It follows the same distribution.

That last sentence is the important one. Speculative decoding is not model compression, and it does not lower the target model’s standard. It is a systems technique for doing fewer serial target-model calls.

The Bottleneck It Is Trying to Move

Transformer inference has two rather different phases:

• Prefill processes the prompt. Its tokens are already known, so the model can work on many positions in parallel.
• Decode produces the continuation. Only one new token is known after each step, so the model repeatedly reads its weights and advances the KV cache by one position.

For a single request or a small batch, decode is often limited more by memory traffic than arithmetic. A target model may move billions of weights through the accelerator to produce one token, while leaving much of the available matrix-multiplication throughput unused.

Speculative decoding tries to turn several narrow decode steps into one wider verification step. The target still evaluates the candidate tokens. The saving comes from evaluating them together, with better hardware utilization and fewer serial weight reads, kernel launches, and synchronization points.

This is why the technique should not be described as “doing less target-model computation” without qualification. A verification pass may perform work for candidates that are later discarded. The bet is that parallel work is cheaper in wall-clock time than a sequence of tiny target passes.

Target and Draft Distributions

Let the target model define a next-token distribution

where $h$ is the committed prefix. Let a faster draft model define

The draft model proposes $k$ tokens autoregressively:

Here, $q_i$ is conditioned on the original prefix and the earlier draft tokens. The target then scores those same positions, producing $p_1,\ldots,p_k$, plus the distribution for the token after the full candidate block.

The candidates are checked from left to right. Candidate $\tilde{x}_i$ is accepted with probability

If it is accepted, verification moves to the next candidate. At the first rejection, the remaining draft suffix is thrown away and a replacement token is sampled from

where $[u]_+=\max(u,0)$. If all $k$ candidates are accepted, the target emits one additional token from its distribution after the candidate block. This extra token is often called the bonus token.

That is the entire correction mechanism. It is modified rejection sampling applied one autoregressive position at a time.

Why the Correction Is Exact

The ratio in the acceptance rule can look like a heuristic until the probability mass is written down.

For one position, the draft proposes token $x$ with probability $q(x)$. The probability mass contributed by accepting that proposal is

Where the draft assigns too much probability, acceptance trims its contribution down to the target’s probability. Where the draft assigns too little, every proposed token is accepted, but some target probability is still missing.

The total probability of rejection is

On rejection, the residual distribution puts precisely that missing mass back:

So the output at that position follows $p$. Applying the same argument after every accepted prefix gives the target model’s autoregressive distribution over complete sequences.

There is another useful interpretation. The probability that a single draft proposal is accepted, conditioned on its prefix, is

where $\operatorname{TV}$ is total variation distance. Draft quality matters because overlap with the target distribution determines how often useful work survives verification.

“Exact” still needs two footnotes:

1. The claim assumes the acceptance and residual-sampling algorithm is implemented correctly using the distributions that the decoder actually intends to sample from.
2. Different kernels, floating-point reductions, and random-number consumption can produce different individual strings. Distribution-preserving does not mean bit-for-bit identical output for the same seed.

For greedy decoding, the simpler rule is to accept draft tokens until one differs from the target’s argmax, then use the target token. Under deterministic execution, that reproduces ordinary greedy output.

One Round in Pseudocode

The following leaves cache mutation and end-of-sequence handling out of the way so the sampling logic remains visible:

def speculative_round(prefix, draft, target, k, rng):
    proposals = []
    draft_distributions = []
    working_prefix = list(prefix)

    for _ in range(k):
        q = draft.next_distribution(working_prefix)
        token = sample(q, rng)
        proposals.append(token)
        draft_distributions.append(q)
        working_prefix.append(token)

    # p[i] predicts proposals[i] under the corresponding prefix.
    # p[k] predicts one bonus token after all proposals.
    target_distributions = target.score_block(prefix, proposals)

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

        if rng.uniform() > acceptance:
            residual = positive_part(p - q)
            replacement = sample(residual / residual.sum(), rng)
            return proposals[:i] + [replacement]

    bonus = sample(target_distributions[k], rng)
    return proposals + [bonus]

In production code, probabilities are usually handled through stable log-space operations, and a rejection whose residual mass is numerically tiny needs careful treatment. Sampling filters also belong inside the definition of $p$ and $q$; bolting temperature or top-$p$ onto only one side invalidates the ratios.

How Many Tokens Does a Round Buy?

Let $A$ be the number of accepted draft tokens in one round. Ignoring an early end-of-sequence token, the round commits $A+1$ tokens: either a replacement after the first rejection or a bonus after every proposal is accepted.

The expectation is

If acceptance were independent and equal to a constant $\alpha$ at every position, this would reduce to

With $k=4$ and $\alpha=0.8$, a round commits about

tokens on average. That sounds like a $3.36\times$ speedup, but it is not. We have not paid for the draft model or verification yet.

Let $T_p(1)$ be the time for one ordinary target decode step, $T_q(1)$ the time for one draft step, $T_p(k)$ the time for target verification of a block, and $T_o$ the orchestration overhead. A rough latency model is

Suppose, purely as an illustrative profile, that one draft step costs $0.08T_p(1)$, block verification costs $1.15T_p(1)$, and cache plus sampling overhead costs $0.05T_p(1)$. The round costs $1.52T_p(1)$ and the estimate becomes $3.3616/1.52\approx2.21\times$.

Change the batch size, context length, quantization, tensor-parallel layout, or draft placement and those numbers can move sharply. The equation is more useful than a borrowed headline benchmark because every term can be measured on the system that will actually serve traffic.

Choosing a Draft Model

The best draft is not necessarily the smallest model available, nor the one with the lowest validation perplexity.

A useful draft needs three properties:

• Low serial latency. It still generates its $k$ proposals one by one. A draft that occupies the same distributed mesh as the target can spend its advantage on communication.
• High agreement where the application operates. Code completion, casual chat, and mathematical reasoning can have very different acceptance profiles.
• Compatible tokenization and sampling. Sharing a vocabulary makes token-level verification straightforward. Retokenizing draft text introduces alignment and bookkeeping problems.

Parameter count is only a rough proxy for latency. A small model with an unfriendly architecture, poor kernels, or repeated device transfers may be slower than a larger but well-optimized draft. Quantization can help, provided the resulting change in $q$ does not destroy enough acceptance to cancel the latency saving.

The draft also does not need to be a conventional smaller language model. It only needs a cheap way to propose continuations and, for exact stochastic sampling, a well-defined proposal distribution.

The Cache Work Is Part of the Algorithm

The sampling proof fits on a whiteboard. The cache state does not.

A two-model implementation normally maintains a target KV cache and a draft KV cache for the same committed prefix. During a round:

1. The draft cache advances through all proposed tokens.
2. The target verifies the proposed block and temporarily creates target KV entries for it.
3. If proposal $j$ is rejected, only proposals before $j$ are committed. KV entries for the rejected token and its suffix must not survive.
4. The replacement token is committed, but neither cache necessarily contains its final KV state yet. It can be ingested at the beginning of the next round.

Blindly retaining the target’s entire verification cache is a correctness bug: positions after a rejection were computed from a token that is no longer in the sequence. Blindly rebuilding both caches from the full prefix is correct but can erase the speedup.

Paged KV-cache managers make truncation and block reuse easier, but speculative decoding increases metadata work and temporarily reserves space for uncommitted tokens. Memory capacity can become the constraint before compute does, especially under continuous batching.

Batching Makes the Result Less Obvious

For one request, “accepted tokens per target call” is an intuitive metric. A serving engine handles requests whose draft blocks survive for different lengths.

If one sequence accepts five tokens and another rejects its first, the batch must compact, mask, or carry uneven work into the next iteration. Wider verification blocks also push the target pass toward a more compute-bound regime. That can be beneficial at low batch sizes and less helpful when ordinary decoding already saturates the accelerator.

Distributed inference adds another choice: where should the draft run? Co-locating it with the target avoids network transfers but consumes memory and compute on target devices. Running it elsewhere frees those resources but sends tokens, probabilities, and synchronization across a link. Tensor parallelism can make a supposedly cheap draft pay collective-communication costs at every proposed token.

This is why throughput and inter-token latency need separate measurements. A method can make one stream feel faster while reducing total tokens served per second, or improve aggregate throughput while worsening tail latency.

Beyond a Separate Draft Model

The original form is only one point in a larger design space.

Self-speculative decoding

The target model can draft with a cheaper version of itself, for example by skipping selected layers, then verify with the full network. This avoids loading a second model and guarantees tokenizer compatibility. The difficulty is finding a skip pattern that is substantially faster without making the proposals too weak. It also complicates kernels when the draft and verification paths traverse different layer sets.

Multiple prediction heads

Medusa attaches heads that predict several future positions from a target-model hidden state. Instead of one autoregressive chain, the heads create candidates that can be arranged into a tree and checked with tree attention. Drafting can become very cheap, but training the heads, choosing the tree, and managing branching verification replace the problem of selecting a separate draft model.

Feature and token drafting

EAGLE-family methods train lightweight drafters using internal features from the target. EAGLE-2 allocates a dynamic draft tree according to context-dependent confidence rather than using the same tree everywhere. EAGLE-3 moves to direct token prediction while fusing features from several target layers. These methods aim to spend verification slots on branches likely to be accepted, but they require target-specific training and integration.

Prompt and n-gram lookup

Copy-heavy workloads offer an almost free source of guesses. If the current suffix occurred earlier in the prompt or generated text, the following tokens from that occurrence can form a draft. This works surprisingly well for document editing, retrieval-grounded answers, and code with repeated identifiers. It is far less useful when the answer is novel, and stochastic correction still has to match the intended target distribution.

Trees instead of chains

A chain bets on one future. A tree verifies several alternatives in one target pass, increasing the chance that some path survives. Tree attention prevents branches from attending to one another, and the cache manager commits only the accepted path. More branches raise acceptance opportunities, but also consume verification compute and temporary KV memory. “More candidates” is not a free setting.

These families should not be treated as interchangeable implementations with a universal ranking. Some preserve arbitrary target sampling exactly; some target greedy decoding; some use approximate acceptance schemes. The guarantee belongs to the complete algorithm, not to the phrase speculative decoding.

Sampling Details That Quietly Break Correctness

Real decoders rarely sample raw softmax probabilities. They apply temperature, top-$k$, top-$p$, minimum probability thresholds, repetition penalties, token bans, and grammar masks.

The safe rule is simple: $p_i$ and $q_i$ in the acceptance ratio must be the actual normalized distributions after their respective configured transformations. The residual must be computed from those same distributions. If the target applies a grammar mask after verification but the acceptance ratio used its unmasked probabilities, the proof no longer describes the code.

Other common traps include:

• comparing probabilities conditioned on different prefixes;
• accepting every token below a fixed probability-distance threshold;
• forgetting to discard the suffix after the first rejection;
• reusing target KV entries computed after a rejected token;
• changing top-$p$ candidate sets without renormalizing;
• assuming matching output for one random seed is a test of distributional exactness.

Greedy verification avoids the residual sampler, but it does not validate the stochastic path. Both modes deserve tests.

A Benchmark That Can Answer the Deployment Question

A credible evaluation begins with an optimized autoregressive baseline using the same target weights, precision, runtime, attention kernels, and hardware. Comparing a tuned speculative stack with an untuned baseline mostly measures engineering effort.

I would record at least:

• time to first token, median and tail inter-token latency;
• output tokens per second per request and for the whole server;
• mean accepted draft length and its distribution;
• draft tokens proposed per committed token;
• target verification calls per committed token;
• target and draft KV-cache occupancy;
• GPU utilization, memory bandwidth, and power if available;
• quality or distribution checks for every supported sampling mode.

The workload matrix matters just as much:

Then ablate draft size, speculation length, and tree width. Plot speed against accepted length rather than reporting only the best configuration. A fixed $k$ that wins on repetitive code may waste work on a high-temperature conversation.

Recent benchmarking work reinforces this point: speculative-decoding results are sensitive to domain, concurrency, and implementation. Low-diversity synthetic prompts can make acceptance and throughput look better than they do on varied production traffic. A single “tokens per second” number is not a deployment result.

For stochastic correctness, do not expect runs with the same seed to match token by token; speculative execution consumes randomness differently. Instead, test the implementation on small, controlled distributions where output frequencies, conditional frequencies, and sequence probabilities can be compared with the target sampler. Keep deterministic greedy tests as a separate, stricter regression check.

When It Is Worth Using

Speculative decoding is a strong candidate when target decode is latency-bound, the draft is genuinely cheap, continuations are predictable enough to yield multi-token acceptance, and the serving engine can verify blocks without painful cache or batching overhead.

It is less compelling when ordinary decoding already runs in a large saturated batch, the draft must cross a slow device boundary, the workload uses high-entropy sampling, memory is too tight for another model and speculative cache blocks, or output sequences are so short that setup costs dominate.

The practical decision is not “does speculative decoding work?” It plainly can. The decision is whether a particular draft, target, workload, and serving stack satisfy

Everything interesting is hidden inside those measured terms.

Closing Thought

Speculative decoding does not remove autoregression. The committed sequence is still built from left to right, and the target model still decides its distribution. What changes is how much uncertain future work the system is willing to do in parallel.

That makes it a neat example of systems design around an immutable dependency. When the next token cannot be known early, guess several, verify them efficiently, and make rejection mathematically harmless. The algorithm is elegant. Getting a real speedup without damaging correctness is where the engineering begins.

References

• Yaniv Leviathan, Matan Kalman, and Yossi Matias, Fast Inference from Transformers via Speculative Decoding, 2022.
• Charlie Chen et al., Accelerating Large Language Model Decoding with Speculative Sampling, 2023.
• Jun Zhang et al., Draft & Verify: Lossless Large Language Model Acceleration via Self-Speculative Decoding, 2023.
• Tianle Cai et al., Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads, 2024.
• Yuhui Li et al., EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees, 2024.
• Yuhui Li et al., EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test, 2025.
• Talor Abramovich et al., SPEED-Bench: A Unified and Diverse Benchmark for Speculative Decoding, 2026.
• Tri Dao et al., Flash-Decoding for Long-Context Inference, 2023.