Speculative Decoding

Your LLaMA-3.1-8B deployment meets its latency SLA at low concurrency. At peak traffic, tokens per second drop and the queue backs up. A colleague suggests adding a draft model to “get 2–3× speedup.” You enable it, latency improves for one request, but throughput under load gets worse. The draft model consumed memory and compute that the target needed for other requests.

Speculative decoding is a latency optimisation for a single request, not a universal throughput multiplier. It helps when the draft is fast, acceptance is high, and the GPU has spare capacity. It hurts when any of those conditions fail.

The one-sentence version

Draft-and-verify reduces single-request generation latency when the draft model is fast enough and the acceptance rate is high enough; otherwise the extra draft work and memory erase the gain or reverse it.

---

The serving dilemma

Consider a hypothetical deployment of Llama-3.1-8B on an H100 with Llama-3.2-1B as its draft model. Assume single-request ITL falls from 45 ms to 28 ms with speculation. At eight concurrent requests, assume p95 ITL instead rises from 45 ms to 52 ms and throughput falls from 1,200 to 1,050 tokens/s. These numbers illustrate a possible tradeoff; they are not measurements of this pair. The draft’s sequential passes and KV cache can compete with other requests for compute and memory.

The draft helped the one request it was designed for, but it starved the batch.

---

One request timeline: γ = 3, accepted A/B, rejected C, fallback D

One speculative iteration produces multiple emitted tokens from one target verification pass.

Setup: prompt prefix P. Draft model q proposes γ = 3 tokens autoregressively: A, B, C.

Verification pass (one target forward pass): the target model p scores all three candidates in parallel, producing p(A|P), p(B|P,A), p(C|P,A,B).

Position	Draft token	Target acceptance probability	Action
1	A	min(1, p(A)/q(A))	Emit A
2	B	min(1, p(B)/q(B))	Emit B
3	C	min(1, p(C)/q(C))	Rejected — stop; sample fallback D from residual

Emitted tokens this iteration: A, B, D (3 tokens). One rejection occurred, so no extra token from target.

Call counts for this iteration:

Component	Calls	Notes
Draft model q	3 autoregressive forward passes	One per proposed token
Target model p	1 verification forward pass	Scores all 3 candidates in parallel
Baseline (no speculation)	3 target forward passes	One per emitted token

Boundary case — all accepted: If A, B, C are all accepted (rejection probability 0), emit A, B, C plus one extra token E sampled from p (4 tokens total), still with 3 draft passes + 1 target pass.

Speculative decoding timeline

Baseline: 3 target decode steps. Speculative: 3 draft steps + 1 target verification. Accepted (green), rejected (red), residual fallback (amber). All-accepted bonus emits an extra target token.

Read this diagram as text

Two horizontal lanes show the draft and target models. Baseline row: target lane has three sequential decode blocks for tokens 1, 2, 3. Speculative row: draft lane shows three draft blocks (A, B, C) with a rejection marker on C; target lane shows one wide verification block scoring A, B, C. Fallback D is sampled from the residual at position C. Cost bars underneath compare 3 target steps vs 3 draft steps + 1 target step.

---

Exact target-distribution sampling ≠ identical output sequences ≠ lossy variants

Exact target-distribution sampling (the standard rejection sampler): the output distribution equals the target distribution p in exact arithmetic, provided:

• p and q are valid probability distributions on the same conditioning prefix;
• acceptance uses min(1, p(x)/q(x)) (sample u ~ U(0,1), accept if u ≤ p(x)/q(x));
• residual sampling uses the normalized positive residual r(x) ∝ max(0, p(x) − q(x));
• target verification logits are computed on the exact same prefix and candidate token;
• no deliberately lossy verifier (FLy, synthetic acceptance) is enabled.

The draft need not cover the target’s support. A token with q(x) = 0 cannot be proposed by the draft, so its acceptance ratio is never evaluated. If p(x) > 0, the positive residual (p − q)_+ assigns it mass after a rejection, allowing it to be sampled as the fallback. The guarantee does not require supp(q) ⊇ supp(p); it requires valid distributions on the same prefix and correct residual sampling.

Identical output sequences: Losslessness is distributional, not byte-identical. Two runs with the same seed can diverge at the first rejection because the residual sample differs from the non-speculative sample. Floating-point, batch-size numerical behaviour, and logprob instability in the runtime also cause divergence. Greedy-equality tests pass (greedy acceptance = 1 everywhere), but sampling equality is not guaranteed.

Lossy variants: FLy defers or relaxes verification; synthetic acceptance uses fixed acceptance rates. These are not distribution-preserving by design. If you enable them, label the configuration as lossy and exclude it from “lossless” claims.

What 'lossless' means in practice

The standard rejection sampler preserves the target distribution up to hardware numerics. It does not guarantee bit-identical outputs, stable logprobs across runs, or immunity to runtime numerical effects. Quality checks must compare the speculative configuration against the non-speculative configuration on the same runtime and model versions.

---

Single-request break-even model

This formula scopes to the simplified single-request equal-cost/geometric-acceptance model. It does not predict batched throughput.

Variables

• α — per-token acceptance probability (steady-state average; 0 ≤ α < 1)
• γ — draft length (number of speculative tokens per iteration)
• c — draft-to-target latency ratio: c = t_draft_per_token / t_target_per_verification (dimensionless)
• L_d — draft per-token latency (ms)
• L_t — target verification latency per iteration (ms), treated as one target step

Assumptions (explicit, not hidden)

1. Acceptance events are i.i.d. with probability α (geometric). Real workloads have position-dependent and token-dependent acceptance; treat α as an empirical average.
2. Target verification cost is one target step regardless of γ (prefill-like parallel scoring). This is optimistic for very large γ or long contexts.
3. Draft cost is γ sequential draft steps; no batching of draft across requests.
4. No extra overheads: KV-cache growth, sampling, scheduler, and network latency are ignored. They reduce real speedup.
5. Baseline is single-request autoregressive decoding.

Formula

From Leviathan et al. (2023), as restated in Yan et al. (2024, §3.3):

Expected tokens per iteration:

E[T] = (1 − α^(γ+1)) / (1 − α) = 1 + α + α^2 + ... + α^γ

Time per iteration (in target-step units):

T_iter = γ c + 1

Speedup relative to autoregressive target:

S(α, γ, c) = E[T] / (γ c + 1)
            = (1 − α^(γ+1)) / ((1 − α)(γ c + 1))

Break-even condition (S > 1):

(1 − α^(γ+1)) > (1 − α)(γ c + 1)

Maximum tolerable draft ratio:

c_break = (E[T] − 1) / γ

Fully worked hypothetical example

Given: α = 0.7, γ = 4, c = 0.10

Calculation:

E[T] = (1 − 0.7^5) / (1 − 0.7) = (1 − 0.16807) / 0.3 = 2.7731
T_iter = 4 × 0.10 + 1 = 1.40
S = 2.7731 / 1.40 = 1.9808

Result: expected tokens ≈ 2.773, modeled speedup ≈ 1.981.

Interpretation: With a 70% per-token acceptance rate, a draft length of 4, and a draft that takes 10% of the target verification time per token, a single request emits ~2.77 tokens per iteration in 1.4 target-step units — nearly 2× faster than baseline. If the draft is slower (c = 0.20), modeled speedup falls to 1.541. At that slower draft speed, reducing acceptance to α = 0.5 lowers it further to 1.076. At α = 0.85, γ = 4, c = 0.15, the model gives 2.318.

def speedup(alpha, gamma, c):
    expected = (1 - alpha ** (gamma + 1)) / (1 - alpha)
    return expected / (gamma * c + 1), expected

# Example: alpha=0.7, gamma=4, c=0.10
s, e = speedup(0.7, 4, 0.10)
assert round(s, 3) == 1.981
assert round(e, 3) == 2.773
print(f"Speedup: {s:.3f}, Expected tokens/iter: {e:.3f}")

---

Why this estimate cannot predict batched throughput

The single-request formula assumes the GPU has spare compute and memory to run the draft model without delaying other requests. Under batching:

1. No spare compute: Draft steps compete with target verification and prefill of other requests. If GPU utilisation is already high, throughput falls.
2. Batching amortises weights: In large batches, decode is less memory-bandwidth-bound. Speculative decoding’s parallel verification is less valuable, and draft overhead dominates.
3. KV-cache pressure: Two models’ caches reduce concurrent sequences; preemption/queuing can erase latency gains.
4. Acceptance drops on hard tokens: Code/math may accept well; creative or multilingual traffic may not. Per-category acceptance matters.
5. Long contexts: Verification pass cost grows with context length; the “one target step” assumption breaks.

Decision rule: Speculative decoding is justified when the workload has medium-to-low QPS, memory-bound decode, spare GPU memory, and measured acceptance length sufficient to beat c_break. It is usually wrong for saturated, high-batch, throughput-first serving.

---

Measurement gate for deployment

Before enabling speculative decoding in production, measure the named draft/target pair on representative traffic:

Metric	Target	Method
Acceptance rate (AR)	accepted / draft tokens	vLLM: spec_decode_num_accepted_tokens_total / spec_decode_num_draft_tokens_total
Acceptance length (AL)	(accepted_draft_tokens + iterations) / iterations	SGLang: sglang:spec_accept_length (windowed gauge)
TTFT p50/p95	No regression vs baseline	Closed-loop concurrency sweep
ITL p50/p95	Improvement at target concurrency	Same sweep, compare p95
Throughput (tokens/s, req/s)	No regression vs baseline	Open-loop Poisson at target QPS
GPU memory	Headroom for draft + target KV	nvidia-smi / DCGM, measure preemption
Quality	No regression on task metrics	Paired GSM8K exact match, MMLU, Wikitext-2 perplexity with confidence intervals

Go/no-go: Require AR > α_min where α_min solves S(α_min, γ, c_measured) ≥ 1, and throughput at target concurrency ≥ baseline, and quality deltas within statistical noise.

---

Concrete exercise

Goal: Verify the break-even model and understand why measured α and c decide the outcome.

Task: Run this pure-Python Monte Carlo simulator (no GPU needed):

import random
random.seed(42)
alpha, gamma, c, n = 0.7, 4, 0.10, 100_000
total_tokens = total_iters = 0
for _ in range(n):
    accepted = 0
    for _ in range(gamma):
        if random.random() < alpha:
            accepted += 1
        else:
            break
    total_tokens += accepted + 1   # accepted + fallback/extra
    total_iters += 1
al = total_tokens / total_iters
s = al / (gamma * c + 1)
print(round(al, 3), round(s, 3))

Expected results: acceptance length ≈ 2.773 and speedup ≈ 1.981 (matches the worked example).

Check: Vary α, γ, c to find break-even. What is the maximum c at α = 0.7, γ = 4 where S ≥ 1? (Answer: c_break ≈ 0.443. If the draft takes >44% of target verification time per token, it loses.)

Optional runtime exercise: Run vLLM offline spec-decode example with greedy sampling and assert output equality between spec and non-spec configurations.

Try it yourself

1. 01Your draft model takes 8 ms per token. Your target verification takes 40 ms per iteration. You measure α = 0.75 at γ = 4. Does speculative decoding help this single request? Show the calculation.

   Show a hint

   Compute c = 8/40 = 0.2. Then S = (1 − 0.75^5) / ((1 − 0.75)(4×0.2 + 1)). Compare to 1.

2. 02At concurrency 16, you enable the same draft/target pair. TTFT improves but throughput drops 15%. Name two mechanisms from this lesson that explain the throughput regression.

   Show a hint

   Consider KV-cache pressure on concurrency and draft compute competing with target verification under saturation.

---

Key takeaways

Key takeaways

• Speculative decoding is a single-request latency optimisation: a fast draft proposes γ tokens; the target verifies them in one pass; accepted tokens are emitted; the first rejection triggers a residual sample; if all γ are accepted, an extra target token is emitted.
• The standard rejection sampler preserves the target distribution exactly (in exact arithmetic) without requiring the draft to cover the target support — the positive residual (p−q)_+ handles p-only tokens.
• Speedup is S(α, γ, c) = (1 − α^(γ+1)) / ((1 − α)(γ c + 1)). For α=0.7, γ=4, c=0.10: expected tokens ≈ 2.773, speedup ≈ 1.981.
• This formula assumes spare GPU capacity. Under batching/saturation, draft compute, dual KV caches, and reduced concurrency can reverse the gain. Measure TTFT, ITL, throughput, acceptance length, GPU memory, and quality on the named pair before deploying.
• Lossy modes (FLy, synthetic acceptance) are not distribution-preserving. Label them explicitly and exclude from lossless claims.

---

Interview questions

Interview questions

Why does the standard rejection sampler not require the draft model to have full support over the target vocabulary?

A token with q(x)=0 cannot be proposed by the draft, so no acceptance ratio is evaluated for it. If p(x)>0, the positive residual (p−q)_+ can sample it as the fallback after a rejection. Valid p and q distributions on the same prefix and correct residual sampling preserve the target distribution.

A colleague says "speculative decoding gives 2–3× speedup." What is missing from that claim?

The claim omits the three variables that decide the outcome: acceptance rate α, draft length γ, and draft-to-target latency ratio c. Speedup is S(α,γ,c); it can be <1 if the draft is slow or acceptance is low. It also assumes single-request decode with spare GPU capacity — under batching, throughput can decrease.

You measure α = 0.85, γ = 4, c = 0.15 for a draft/target pair. The single-request model predicts S ≈ 2.318. You enable it at concurrency 32 and throughput drops. Why?

The single-request model assumes the GPU has spare compute and memory for the draft. At high concurrency, the draft model's sequential passes compete with target verification and prefill of other requests. Dual KV caches reduce the number of concurrent sequences. The extra work and memory pressure can erase the latency gain and reduce throughput.

---

Related lessons

Related lessons

• Inference Optimisation & AI Infrastructure · Schedule Requests and Manage KV MemoryBatching and Throughput26 min
• Inference Optimisation & AI Infrastructure · Schedule Requests and Manage KV MemoryContinuous Batching: Iteration-Level Scheduling30 min
• Inference Optimisation & AI Infrastructure · Schedule Requests and Manage KV MemoryPrefill Optimisation: Prefix Caching, Chunked Prefill, and Disaggregation35 min

---

Sources and scope

• Foundational guarantee: Leviathan et al., ICML 2023 and Chen et al., 2023 derive target-distribution preservation for standard speculative sampling with residual correction.
• Runtime limits: vLLM speculative decoding documentation describes version-sensitive configurations and numerical limits. Check the installed version before relying on any mode or metric.
• Simplified speedup model: Yan et al., NAACL 2025 studies draft latency and acceptance under its stated workloads. The calculation above is an analytical estimate, not a batched serving benchmark.
• Benchmark vocabulary: NVIDIA NIM speculative decoding documentation defines acceptance and serving measurements; its runtime details are version-sensitive.

The break-even formula and worked example are hypothetical single-request calculations to teach the decision variables. They are not benchmark results. Deployment claims require measured results from the named pair/workload/hardware/runtime stack.

The visual uses SpeculativeTimeline, an original diagram component for this lesson. The Monte Carlo exercise is hardware-independent and runnable in any Python environment.