When a large language model writes a sentence, the hardest part to parallelize is not understanding the prompt. It is the wait that follows. Token 2 cannot be chosen before token 1 exists; token 3 waits for token 2. Producing 100 output tokens therefore requires at least 100 serial decoding steps through the target model. The GPU may be fast, but it is tied to a dependency chain.

Speculative decoding borrows an idea from CPU branch prediction. A cheap draft model guesses several tokens ahead, then the expensive target model checks the entire draft in one pass. Accepted guesses advance the sequence by several positions. A rejection corrects the first wrong position. The important part is not that a small model helps write the answer; it is that the correction rule makes the final sample come from exactly the target model’s distribution. The draft can change execution time, but it never receives final authority.

That makes speculative decoding an unusual optimization. It does not quantize or prune the target, modify its architecture, or trade output quality for latency. The original Google Research paper reported a 2–3× speedup on T5-XXL. Independent work from DeepMind reported a 2–2.5× decoding speedup for a distributed 70B Chinchilla setup. Those multipliers are workload-specific, but the idea—fold several serial steps into one parallel verification—has become part of mainstream inference engines.

Decoding Is Bottlenecked by a Dependency Chain

During Transformer training, many positions in a sentence can be processed together because the correct prefix at every position is already known. Generation lacks that answer key. At time \(t\), the target first computes \(p(x_t\mid x_{

A KV cache avoids recomputing keys and values for old tokens, but it does not remove the time dependency. Small-batch decoding is also commonly memory-bound: each step does a modest amount of work for one new position while reading a large set of weights and cached state. A target-model forward pass may leave compute units underused, yet the next token still cannot be selected early.

Speculative decoding exploits two facts. First, scoring a short continuation with the target often does not cost the same multiple as scoring one position; matrix operations can use more parallelism. Second, language contains many locally easy regions—fixed phrases, punctuation, code indentation, and spans copied from context—that a small model can often predict. A cheap model creates parallel work and the large model audits it in one pass.

What Happens in One Speculative Step

Let \(p\) be the target distribution, \(q\) the draft distribution, and \(\gamma\) the number of proposed tokens per round.

1. The draft model autoregressively produces \(x_1,\ldots,x_\gamma\), retaining each \(q_i(x)\). This stage remains serial, so the drafter must be cheap.
2. The target treats “original prefix + full draft” as a short batch and computes every candidate-position distribution \(p_i(x)\), plus the distribution after an entirely accepted draft, in one pass.
3. Verification proceeds left to right. Draft token \(x_i\) is accepted with probability \(\min(1,p_i(x_i)/q_i(x_i))\). Once one token is rejected, all later draft tokens are discarded.
4. On a rejection at position \(i\), the algorithm does not simply sample again from \(p_i\). It samples from a corrected residual distribution. If every proposal is accepted, it can draw one extra token from the already computed next-position target distribution.

One round therefore advances by at least one token and at most \(\gamma+1\). The draft itself is not parallel in the classic small-model version. What becomes parallel is the expensive target verification.

Why “Guess and Correct” Does Not Bias the Target

Keeping only proposals that the target also likes sounds as if it should favor safe tokens on which both models agree. The residual distribution after a rejection prevents that bias.

For one proposed token \(x\), sample first from \(q\). If \(q(x)\le p(x)\), always accept. Otherwise, accept with probability \(p(x)/q(x)\). The probability of obtaining \(x\) along the acceptance path is therefore

The accepted path captures the overlap between the two distributions. The target still has probability mass where \(p(x)>q(x)\), so a rejection is repaired by sampling from

Adding the overlap and residual paths reconstructs \(p\). Applying the same conditional argument at each position preserves the distribution over complete sequences.

For greedy decoding, the rule is simpler: accept while the draft token equals the target argmax, then replace the first mismatch with the target token. For stochastic decoding, “unchanged output” means an unchanged probability distribution, not necessarily an identical string under every nominally equal random seed. Floating-point precision, batch shape, and random-number consumption can still produce run-to-run differences. vLLM’s official documentation accordingly separates theoretical losslessness, algorithmic validation, and numerical stability.

Speed Depends on Two Numbers, Not Draft Accuracy Alone

Let \(\alpha\) be the mean token acceptance rate. Under the independent, identically distributed approximation used in the paper, the expected number of tokens emitted by one target verification is

A higher acceptance rate makes an entire draft more likely to survive. But acceptance is not yet speed. Let \(c\) be the ratio between one draft-model step and one target-model step. An idealized speedup is

This equation exposes the engineering tradeoff. A stronger drafter may improve \(\alpha\) while also increasing \(c\). A short draft misses parallelism; a long draft wastes more proposal and verification work after an early rejection. The original paper found that a drafter roughly two orders of magnitude smaller than the target often balanced these factors in its experiments, but that is not a universal recipe.

The formula also assumes that verifying \(\gamma+1\) target positions takes nearly the time of one position and that the machine has spare compute. Interactive, low-concurrency, memory-bound generation often fits this assumption. When a high-concurrency server already fills the GPU, a larger verification micro-batch can instead compete for arithmetic throughput. vLLM therefore frames speculative decoding as especially useful for latency-sensitive, medium-to-low-QPS workloads and supports changing speculation length with batch size.

The Drafter Does Not Have to Be Another Transformer

The classic algorithm only needs a cheap proposer; it does not require the proposer to share the target architecture. That interface has produced several families:

• Independent draft models are conceptually direct and expose a full \(q\) distribution, but add weights, KV state, and scheduling overhead. Different vocabularies require additional mapping.
• N-gram or prompt lookup reuses repeated spans in the prompt or generated text at nearly zero model cost. Code, structured output, and rewriting often contain useful copying patterns, while open-ended prose may not.
• Lightweight heads and EAGLE-style methods reuse target hidden states and predict future tokens with small additional modules. They reduce the cost of a separate drafter but require compatible learned weights.
• Native multi-token prediction teaches the model to predict several future positions during training. Deployment can reuse those predictions as speculative candidates, bringing the proposer inside the model rather than attaching another full model.

These methods change candidate generation, not the propose–verify principle. Current vLLM documentation lists draft models, EAGLE, MTP, n-gram, suffix decoding, and other methods. Speculative decoding has evolved from one algorithm into a family of systems sharing a verification protocol.

When It Does Not Win

A compelling acceptance-rate chart can hide the actual outcome. A deployment should measure at least mean accepted length, drafter overhead, GPU utilization during verification, and end-to-end time per output token. High acceptance with an expensive drafter may still lose; moderate acceptance with an almost-free proposer may win.

Speculation is often unfavorable when target and draft distributions diverge, high-temperature sampling reduces agreement, a large existing batch makes verification compute-bound, outputs are too short to amortize setup, or multi-GPU placement introduces communication overhead. The optimal \(\gamma\) can vary across requests and even across phases of one generation, so one static value rarely covers every workload.

Latency and throughput must also be separated. A user waiting for one response benefits when the system makes fewer serial large-model calls. A platform already saturated by continuous batching may not produce more total tokens per GPU-second. Speculative decoding can spend more total FLOPs to reduce wall-clock time. That is not a contradiction; it spends idle parallel capacity to buy latency.

The PagedAttention story is a useful contrast. PagedAttention fits more live sequences in memory and grows the batch horizontally. Speculative decoding tries to cross several time steps inside one sequence and advances vertically. Neither changes what the model should answer. One rewrites memory management; the other rewrites time scheduling.

The durable lesson is broader than “small model drafts, large model verifies.” When expensive computation is trapped behind a serial dependency, a cheap approximation can manufacture candidates and one parallel exact computation can restore correctness. The guess may be aggressive because the target retains the right to decide. The execution path changes; the answer standard does not.

References

1. Leviathan, Kalman, Matias, Fast Inference from Transformers via Speculative Decoding, ICML 2023.
2. Chen et al., Accelerating Large Language Model Decoding with Speculative Sampling, 2023.
3. vLLM Project, Speculative Decoding documentation.
4. vLLM Project, Speculators: training and deployment library.
5. Li et al., EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty, ICML 2024.
6. Cai et al., Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads, ICML 2024.