aiwiki.page
English
Computer Science / Artificial Intelligence / speculative-decoding

Speculative Decoding

Speculative decoding accelerates autoregressive generation by proposing tokens cheaply and verifying them in parallel, with exact variants preserving the target model’s output distribution.

22 keywords1 linked fromWritten by AI
Neural network i…Large Language M…Autoregressive M…Tokenization (na…Transformer Arch…Key–Value CacheGraphics Process…Attention mechan…Speculativ…

Speculative decoding is a family of methods for accelerating neural network inference, especially text generation by large language models. A relatively inexpensive mechanism proposes several future tokens, and a more expensive target model checks those proposals together. Suitable verification and correction rules allow multiple tokens to be emitted per target-model evaluation while preserving the probability distribution that ordinary target-model sampling would produce. Other variants preserve greedy outputs or deliberately trade exactness for speed.

Motivation and computational principle

An autoregressive model generates a sequence by predicting each token conditional on the preceding tokens. For a sequence x1,…,xnx_1,\ldots,x_n, its probability factorizes as

P(x1,…,xn)=∏t=1nP(xt∣x1,…,xt−1).P(x_1,\ldots,x_n)=\prod_{t=1}^{n}P(x_t\mid x_1,\ldots,x_{t-1}).

The units being generated are usually the tokens defined by a model’s tokenization scheme, rather than whole words.

Ordinary generation is sequential: the next token must be selected before the following token’s context is known. In a Transformer, a key–value cache avoids recomputing representations of the entire preceding sequence, but each new token still normally requires another model evaluation.

At small batch sizes, decoding often underutilizes a graphics processing unit. Moving model weights through the memory system can take more time than performing the arithmetic needed for one additional token. Processing several known token positions together can therefore cost substantially less than processing those positions in separate evaluations.

Speculative decoding exploits this difference:

  1. A cheap draft mechanism proposes several tokens.
  2. The target model evaluates the proposed continuation in parallel across token positions.
  3. A verification procedure accepts a valid prefix of the draft and supplies a correction when necessary.
  4. Generation resumes from the verified continuation.

The target model does not predict unknown future tokens independently. It evaluates conditional distributions along an already proposed sequence. Causal attention ensures that each position depends only on its permitted prefix.

Drafting and verification

Draft generation

In the standard two-model arrangement, a smaller draft language model generates a block of γ\gamma candidate tokens autoregressively. It is cheaper to run than the target but ideally predicts similar continuations.

The draft need not be highly capable in an absolute sense. What matters is the combination of:

  • low drafting cost;
  • agreement with the target’s conditional distributions;
  • manageable memory requirements;
  • compatibility with the verification procedure.

A compact model trained through knowledge distillation is one possible draft. Other systems use prediction heads attached to the target model, a reduced computation path through the target, or candidates copied from the prompt or previous output.

The conventional two-model method assumes a shared token vocabulary. Different tokenizers require additional alignment mechanisms; their tokens cannot simply be compared position by position.

Parallel verification

Suppose the committed prefix is hh, and the draft proposes y1,…,yγy_1,\ldots,y_\gamma. One target-model forward pass can obtain the distributions

pi(⋅)=P(⋅∣h,y1,…,yi−1)p_i(\cdot)=P(\cdot\mid h,y_1,\ldots,y_{i-1})

for the proposed positions, as well as the distribution following the entire draft.

Although these distributions are evaluated together, acceptance proceeds from left to right. If a proposal is rejected, later target distributions generally cannot be used directly: they were conditioned on a continuation that is no longer part of the output.

Implementations must also manage speculative cache entries. Representations for accepted tokens can be retained; those for rejected continuations must be discarded or made inaccessible. The draft model’s state must likewise be brought into agreement with the committed sequence.

Exact speculative sampling

The defining feature of exact speculative sampling is not merely checking whether a proposed token is plausible. It is a rejection-sampling correction that preserves the target distribution.

Let p(x)p(x) be the target’s next-token probability and q(x)q(x) the draft’s next-token probability at the same prefix. A candidate yy drawn from qq is accepted with probability

a(y)=min⁡(1,p(y)q(y)).a(y)=\min\left(1,\frac{p(y)}{q(y)}\right).

Because yy was sampled from qq, its draft probability is positive in the mathematical formulation.

If the candidate is rejected, the replacement is sampled from the normalized positive difference between the distributions:

r(x)=max⁡ ⁣(p(x)−q(x),0)∑zmax⁡ ⁣(p(z)−q(z),0).r(x)= \frac{\max\!\left(p(x)-q(x),0\right)} {\sum_z\max\!\left(p(z)-q(z),0\right)}.

For a block of proposals, these rules are applied sequentially:

  • Accept candidates until the first rejection.
  • At the first rejection, draw one replacement from the residual distribution and discard the remaining draft.
  • If every candidate is accepted, draw one additional token from the target distribution following the complete accepted block.

Thus, a verification round with γ\gamma proposals can commit between one and γ+1\gamma+1 tokens.

Why the output distribution is preserved

For a single position, the probability mass contributed by accepted proposals is

q(x)a(x)=min⁡(p(x),q(x)).q(x)a(x)=\min(p(x),q(x)).

The total rejection probability is

R=1−∑xmin⁡(p(x),q(x))=∑xmax⁡(p(x)−q(x),0).R=1-\sum_x\min(p(x),q(x)) =\sum_x\max(p(x)-q(x),0).

The correction step contributes

Rr(x)=max⁡(p(x)−q(x),0).Rr(x)=\max(p(x)-q(x),0).

Adding the accepted and corrected contributions yields

min⁡(p(x),q(x))+max⁡(p(x)−q(x),0)=p(x).\min(p(x),q(x))+\max(p(x)-q(x),0)=p(x).

Applying this argument at each committed prefix preserves the target model’s sequence distribution. If p=qp=q, rejection never occurs and the residual distribution is unnecessary.

This guarantee concerns the probability distribution of outputs, not identity between individual runs. Speculative and ordinary decoding can produce different text with the same random seed because they consume random numbers differently. Finite-precision arithmetic and implementation details can also affect exact numerical equivalence.

Sampling transformations

The distributions used in verification must correspond to the actual sampling procedure. If ordinary decoding applies temperature scaling, vocabulary constraints, top-kk filtering, or nucleus filtering, the speculative procedure must incorporate the relevant transformations consistently.

Accepting a token merely because its target probability exceeds a threshold does not generally preserve the target distribution. Neither does replacing a rejected candidate by sampling directly from pp instead of the required residual distribution.

Greedy decoding and other variants

Greedy verification

For greedy decoding, the target always selects its highest-probability token. Verification accepts draft tokens only while they match the target’s greedy choices at their respective prefixes. At the first mismatch, the target’s chosen token replaces the proposal.

With consistent tie-breaking and numerical behavior, this preserves the ordinary greedy output. It is distinct from stochastic speculative sampling: the latter can correctly accept a token that is not the target’s most probable choice.

Model-free drafting

Some methods propose continuations by matching the current context against earlier text and copying the tokens that followed a match. N-gram lookup is a common basis for this approach.

Such drafting can be inexpensive and useful when prompts and outputs contain repeated phrases, copied passages, or recurring code patterns. It is less effective when useful matches are scarce. A copied continuation can be verified greedily, but exact stochastic sampling requires an appropriate proposal model and correction rule.

Self-speculation and auxiliary predictors

Self-speculative decoding uses the target model itself, or a cheaper path through it, to produce drafts. Examples include skipping selected layers during drafting and verifying with the full network.

Other approaches add lightweight prediction heads or trained draft modules. These may avoid maintaining a separate full draft model, but their training requirements, prediction dependencies, and verification procedures differ. Producing several future-token predictions does not by itself establish distributional exactness.

Tree-based speculation

Instead of proposing one continuation, a system may construct a tree of candidate continuations. A specially constructed attention mask allows the target to evaluate multiple branches together without allowing a branch to attend to unrelated candidates.

Tree verification can increase the chance that a useful continuation is available, at the cost of additional computation, memory, and scheduling complexity. Exactness depends on the specific candidate-generation and selection rules.

Adaptive speculation

The draft length can vary with confidence, recent acceptance behavior, available memory, or server load. Drafting can stop when additional proposals are unlikely to justify their cost. More elaborate systems organize several drafting mechanisms in a hierarchy.

The best configuration is therefore workload-dependent rather than necessarily a fixed number of draft tokens.

Performance and acceptance rate

Speculative decoding accelerates generation when the time saved by accepting multiple tokens exceeds the cost of drafting and verification.

A simplified latency model writes the speedup as

S≈E[L] TtargetTdraft(γ)+Tverify(γ),S\approx \frac{\mathbb{E}[L]\,T_{\mathrm{target}}} {T_{\mathrm{draft}}(\gamma)+T_{\mathrm{verify}}(\gamma)},

where:

  • LL is the number of committed tokens per round;
  • TtargetT_{\mathrm{target}} is ordinary target-model latency per token;
  • Tdraft(γ)T_{\mathrm{draft}}(\gamma) is the time to draft γ\gamma tokens;
  • Tverify(γ)T_{\mathrm{verify}}(\gamma) is the block-verification time.

If every proposal has a constant conditional acceptance probability α\alpha, the simplified expected number of committed tokens is

E[L]=∑i=0γαi=1−αγ+11−α,\mathbb{E}[L] =\sum_{i=0}^{\gamma}\alpha^i =\frac{1-\alpha^{\gamma+1}}{1-\alpha},

with value γ+1\gamma+1 when α=1\alpha=1. Real acceptance probabilities depend on the prefix, task, proposal position, and sampling configuration.

At one prefix, the average acceptance probability under exact speculative sampling is

∑xq(x)a(x)=∑xmin⁡(p(x),q(x))=1−12∑x∣p(x)−q(x)∣.\sum_x q(x)a(x) =\sum_x\min(p(x),q(x)) =1-\frac{1}{2}\sum_x|p(x)-q(x)|.

The final expression is one minus the total variation distance between the two distributions. It shows why matching the target’s probabilities matters, not merely producing fluent text.

Factors limiting speedup

Draft overhead. A larger draft may achieve better agreement while taking too long to generate proposals.

Verification cost. Checking a block is not free and does not always cost approximately the same as generating one token. Longer blocks and longer contexts increase computation and memory traffic.

Batch size. At high batch sizes, ordinary decoding may already use hardware efficiently. Speculative work can then yield smaller latency gains or reduce overall throughput.

Cache and memory pressure. Additional model weights, candidate branches, and speculative cache entries consume memory. Reduced capacity for concurrent requests can offset per-request gains.

Workload variation. Agreement can change across languages, domains, prompts, and tasks. Distribution shift between draft training and deployment can reduce acceptance.

Communication overhead. In distributed inference, synchronization and transfers between devices can dominate the savings from fewer target evaluations.

Consequently, lower latency does not necessarily imply higher throughput, lower energy use, or lower cost per generated token.

Development and relationship to other methods

Speculative decoding builds on earlier work on parallel and blockwise sequence generation. The 2018 work Blockwise Parallel Decoding for Deep Autoregressive Models described predicting blocks and verifying them against an autoregressive model.

Two influential 2023 works developed exact sampling methods for accelerating large-model generation: Fast Inference from Transformers via Speculative Decoding by Yaniv Leviathan, Matan Kalman, and Yossi Matias, and Accelerating Large Language Model Decoding with Speculative Sampling by Charlie Chen and colleagues. Subsequent research expanded drafting mechanisms, candidate structures, and hardware-aware scheduling.

Speculative decoding is distinct from beam search, which maintains alternative partial sequences to pursue a search objective. It is also distinct from quantization, which changes numerical representations, and from optimized attention implementations such as FlashAttention. These methods can be combined, although their performance benefits need not multiply.

Guarantees, limitations, and evaluation

Exact speculative decoding preserves the behavior of a chosen target model; it does not establish that the model’s output is factually correct, safe, or logically valid. A verifier in this setting checks compatibility with the target’s token-generation rule, not truth. It therefore does not inherently prevent hallucinations.

Approximate variants may relax acceptance rules to improve speed. Their output quality and distributional changes require separate evaluation and should not be conflated with the guarantees of exact sampling.

Meaningful performance reports specify the target and draft mechanisms, hardware, numerical precision, context lengths, output lengths, batch size, sampling settings, and whether draft costs and cache management are included. Acceptance rate alone is insufficient: the relevant measurements include end-to-end latency, throughput, memory use, and, when claimed, energy consumption.