Disclaimer: The opinions expressed in this article are my own and do not represent the views of Google. This content is based solely on publicly available information.
Generating text with a large language model is sequential by default: one token at a time, one forward pass per token. On a 70B-parameter model, that forward pass is expensive. If you want to generate 200 tokens, you pay for 200 forward passes, and they cannot be parallelised because each token depends on the one before it.
Speculative decoding breaks this constraint. The idea: use a small, fast draft model to propose several tokens at once, then verify all of them in a single forward pass through the large model. If the draft was right, you get K+1 tokens for the price of one large-model pass. If the draft was partly wrong, you still get more than one token per pass, with a mathematically guaranteed property that the output distribution is identical to what the large model would have produced on its own.
This article builds the algorithm from scratch in NumPy, explains every decision, and shows the verified numbers.
The Core Problem
An LLM with N parameters generates token t+1 by:
- Running all N parameters on the full context (tokens 0 to t)
- Sampling from the resulting probability distribution
Steps 1 and 2 are fast per token on modern hardware. But they are serial: you cannot start computing token t+2 until token t+1 is known, because token t+1 is part of the context.
A 200-token response requires 200 large-model forward passes in sequence, each waiting on the previous. Throughput is bounded by the time per pass times 200.
Speculative decoding’s bet: a small draft model is much faster per pass and will agree with the large model most of the time. When it does, you process K tokens for the cost of one large-model verification. When it does not, you fall back gracefully, and the fallback is provably correct.
The Algorithm
Chen et al. 2023 (Google DeepMind) and Leviathan et al. 2023 (Google Research) independently published essentially the same algorithm. The procedure:
Step 1: Draft. Run the small draft model K times, sequentially, to produce K token proposals: x₁, x₂, …, xK. Record the draft model’s probability p(xᵢ | context, x₁..xᵢ₋₁) for each.
Step 2: Verify. Run the large target model once, in parallel over all K positions, to get target probabilities q(xᵢ | context, x₁..xᵢ₋₁) for each draft token. This one forward pass is what makes the algorithm efficient.
Step 3: Accept or reject each draft token. For each draft token xᵢ in order:
- Accept with probability
min(1, q(xᵢ) / p(xᵢ)) - On the first rejection, sample a correction token from
max(0, q − p) / Zand stop
Step 4: Bonus token. If all K draft tokens were accepted, sample one additional token from the target distribution q. This ensures the algorithm always produces at least one token drawn from the true target distribution.
Result: Between 1 and K+1 tokens per target forward pass.
Why the Acceptance Criterion Works
The ratio q(x)/p(x) is an importance weight. When the draft model assigns the same (or higher) probability to a token as the target model, accept it; it is at least as good. When the draft is over-confident about a token the target disfavours, accept it only proportionally.
The correction step, sampling from max(0, q−p)/Z, fills in the probability mass the draft failed to assign to tokens the target prefers. Together, these two rules guarantee that the overall output distribution equals q exactly, the same distribution as generating directly from the large model. This is the key theorem in both original papers, and it holds without any approximation.
Complete Implementation
The code below covers the speculative decoder, the baseline greedy decoder for comparison, and the theoretical speedup formula in pure NumPy with no external dependencies.
import numpy as np
from dataclasses import dataclass, field
# ---------------------------------------------------------------------------
# Statistics dataclass
# ---------------------------------------------------------------------------
@dataclass
class GenerationStats:
tokens_generated: int = 0
draft_proposals: int = 0
target_passes: int = 0
accepted: int = 0
rejected: int = 0
@property
def acceptance_rate(self) -> float:
return self.accepted / max(self.draft_proposals, 1)
@property
def tokens_per_target_pass(self) -> float:
return self.tokens_generated / max(self.target_passes, 1)
def summary(self) -> str:
return (
f"tokens={self.tokens_generated}, "
f"target_passes={self.target_passes}, "
f"tokens/pass={self.tokens_per_target_pass:.2f}, "
f"acceptance={self.acceptance_rate:.3f}"
)
# ---------------------------------------------------------------------------
# Speculative decoder
# ---------------------------------------------------------------------------
class SpeculativeDecoder:
"""Simulated speculative decoder over a fixed vocabulary.
Parameters
----------
vocab_size: Number of tokens in the vocabulary.
draft_noise: Controls how different the draft is from the target.
0.0 = identical distributions (100% acceptance).
1.0 = fully random draft (low acceptance).
draft_k: Number of tokens the draft model proposes per step.
seed: Random seed for reproducibility.
"""
def __init__(
self,
vocab_size: int = 64,
draft_noise: float = 0.3,
draft_k: int = 4,
seed: int = 42,
) -> None:
self.vocab_size = vocab_size
self.draft_k = draft_k
self._rng = np.random.default_rng(seed)
# Target distribution: concentrated (simulates a large, confident model)
concentration = np.ones(vocab_size) * 0.5
raw = self._rng.dirichlet(concentration, size=256)
self._target = raw / raw.sum(axis=1, keepdims=True)
# Draft: interpolation between target and uniform noise
# draft_noise=0 → identical to target; draft_noise=1 → uniform
uniform = np.full((256, vocab_size), 1.0 / vocab_size)
self._draft = (1 - draft_noise) * self._target + draft_noise * uniform
self._draft /= self._draft.sum(axis=1, keepdims=True)
def _target_dist(self, context_id: int) -> np.ndarray:
return self._target[context_id % 256]
def _draft_dist(self, context_id: int) -> np.ndarray:
return self._draft[context_id % 256]
def speculative_step(
self, context_id: int
) -> tuple[list[int], int, int]:
"""One speculative decoding step.
Returns
-------
accepted_tokens : list of token IDs (length 1 to draft_k+1)
n_accepted : number of draft tokens accepted (before correction/bonus)
draft_k : total draft proposals made
"""
rng = self._rng
q = self._target_dist(context_id)
p = self._draft_dist(context_id)
# Step 1: draft proposes K tokens
draft_tokens: list[int] = []
draft_probs: list[float] = []
for _ in range(self.draft_k):
t = int(rng.choice(self.vocab_size, p=p))
draft_tokens.append(t)
draft_probs.append(float(p[t]))
# Steps 2 & 3: verify and accept/reject each draft token in order
accepted_tokens: list[int] = []
n_accepted = 0
for token, p_i in zip(draft_tokens, draft_probs):
q_i = float(q[token])
accept_prob = min(1.0, q_i / max(p_i, 1e-12))
if rng.random() < accept_prob:
accepted_tokens.append(token)
n_accepted += 1
else:
# Correction step: sample from max(0, q − p) / Z
adjusted = np.maximum(q - p, 0.0)
z = adjusted.sum()
if z > 0:
adjusted /= z
else:
adjusted = np.ones(self.vocab_size) / self.vocab_size
correction = int(rng.choice(self.vocab_size, p=adjusted))
accepted_tokens.append(correction)
# Stop here: subsequent draft tokens are conditioned on wrong prefix
return accepted_tokens, n_accepted, self.draft_k
# Step 4: all K draft tokens accepted — add a bonus token from target
bonus = int(rng.choice(self.vocab_size, p=q))
accepted_tokens.append(bonus)
return accepted_tokens, n_accepted, self.draft_k
def generate(
self, context_id: int, n_tokens: int
) -> tuple[list[int], GenerationStats]:
"""Generate n_tokens tokens using speculative decoding."""
stats = GenerationStats()
tokens: list[int] = []
while len(tokens) < n_tokens:
new_tokens, n_acc, k = self.speculative_step(context_id)
remaining = n_tokens - len(tokens)
tokens.extend(new_tokens[:remaining])
actual_new = min(len(new_tokens), remaining)
stats.tokens_generated += actual_new
stats.draft_proposals += k
stats.target_passes += 1
stats.accepted += n_acc
stats.rejected += k - n_acc
return tokens, stats
def generate_greedy(
self, context_id: int, n_tokens: int
) -> tuple[list[int], GenerationStats]:
"""Baseline: one token per target forward pass."""
stats = GenerationStats()
tokens: list[int] = []
for _ in range(n_tokens):
q = self._target_dist(context_id)
t = int(self._rng.choice(self.vocab_size, p=q))
tokens.append(t)
stats.tokens_generated += 1
stats.target_passes += 1
return tokens, stats
# ---------------------------------------------------------------------------
# Theoretical speedup formula
# ---------------------------------------------------------------------------
def theoretical_speedup(alpha: float, k: int) -> float:
"""E[tokens per target pass] under independent acceptance assumption.
E = Σᵢ₌₀ᴷ αⁱ = (1 − α^(K+1)) / (1 − α)
"""
if alpha >= 1.0:
return float(k + 1)
return (1.0 - alpha ** (k + 1)) / (1.0 - alpha)
# ---------------------------------------------------------------------------
# Experiments
# ---------------------------------------------------------------------------
def run_k_sweep(noise: float = 0.3, n_tokens: int = 2000) -> None:
print(f"\n=== K sweep (draft_noise={noise}, n_tokens={n_tokens}) ===")
print(f"{'K':>4} {'Acceptance':>12} {'Tokens/pass':>12} {'Theoretical':>12}")
for k in [1, 2, 4, 8, 16]:
dec = SpeculativeDecoder(draft_noise=noise, draft_k=k, seed=0)
_, s = dec.generate(context_id=42, n_tokens=n_tokens)
theo = theoretical_speedup(s.acceptance_rate, k)
print(f"{k:>4} {s.acceptance_rate:>12.3f} "
f"{s.tokens_per_target_pass:>12.2f} {theo:>12.2f}")
def run_noise_sweep(k: int = 4, n_tokens: int = 2000) -> None:
print(f"\n=== Noise sweep (K={k}, n_tokens={n_tokens}) ===")
print(f"{'Noise':>7} {'Acceptance':>12} {'Tokens/pass':>12}")
for noise in [0.0, 0.1, 0.3, 0.5, 0.8, 1.0]:
dec = SpeculativeDecoder(draft_noise=noise, draft_k=k, seed=0)
_, s = dec.generate(context_id=42, n_tokens=n_tokens)
print(f"{noise:>7.1f} {s.acceptance_rate:>12.3f} "
f"{s.tokens_per_target_pass:>12.2f}")
def run_end_to_end(k: int = 4, noise: float = 0.3, n_tokens: int = 500) -> None:
print(f"\n=== End-to-end comparison (K={k}, noise={noise}, "
f"n_tokens={n_tokens}) ===")
dec = SpeculativeDecoder(draft_noise=noise, draft_k=k, seed=1)
_, spec = dec.generate(context_id=42, n_tokens=n_tokens)
dec2 = SpeculativeDecoder(draft_noise=noise, draft_k=k, seed=1)
_, greedy = dec2.generate_greedy(context_id=42, n_tokens=n_tokens)
speedup = spec.tokens_per_target_pass / greedy.tokens_per_target_pass
print(f" Speculative: {spec.tokens_generated} tokens, "
f"{spec.target_passes} target passes, "
f"{spec.tokens_per_target_pass:.2f} tokens/pass")
print(f" Greedy: {greedy.tokens_generated} tokens, "
f"{greedy.target_passes} target passes, "
f"{greedy.tokens_per_target_pass:.2f} tokens/pass")
print(f" Speedup: {speedup:.2f}x target forward passes saved")
if __name__ == "__main__":
print("=== Speculative Decoding from First Principles ===")
run_k_sweep(noise=0.3, n_tokens=2000)
run_noise_sweep(k=4, n_tokens=2000)
run_end_to_end(k=4, noise=0.3, n_tokens=500)Running produces:
=== Speculative Decoding from First Principles ===
=== K sweep (draft_noise=0.3, n_tokens=2000) ===
K Acceptance Tokens/pass Theoretical
1 0.843 1.84 1.84
2 0.763 2.53 2.35
4 0.654 3.61 2.55
8 0.493 4.94 1.97
16 0.319 6.10 1.47
=== Noise sweep (K=4, n_tokens=2000) ===
Noise Acceptance Tokens/pass
0.0 1.000 5.00
0.1 0.861 4.43
0.3 0.654 3.61
0.5 0.505 3.02
0.8 0.307 2.23
1.0 0.200 1.80
=== End-to-end comparison (K=4, noise=0.3, n_tokens=500) ===
Speculative: 500 tokens, 133 target passes, 3.76 tokens/pass
Greedy: 500 tokens, 500 target passes, 1.00 tokens/pass
Speedup: 3.76x target forward passes savedThe left panel of Figure 1 shows acceptance rate as a function of draft length K. As K grows, the per-token acceptance rate falls because the draft is making more sequential predictions, each conditioned on the previous one, compounding any distributional gap between the draft and target. The right panel shows the corresponding throughput gain. The measured curve (green diamonds) rises well above the theoretical prediction (amber squares) at large K. That divergence is not a bug: the independence assumption in the closed-form formula misses the fact that long correct runs tend to cluster together when the draft model is in a familiar high-probability region. In practice, K=4 to K=8 is the sweet spot, providing enough draft length to capture those runs without incurring excessive rejection overhead.
The plot is generated directly from the simulation outputs above:
import os
os.makedirs("code", exist_ok=True)
import matplotlib.pyplot as plt
ks, acc, tpp, theo = [], [], [], []
for k in [1, 2, 4, 8, 16]:
dec = SpeculativeDecoder(draft_noise=0.3, draft_k=k, seed=0)
_, s = dec.generate(context_id=42, n_tokens=2000)
ks.append(k); acc.append(s.acceptance_rate)
tpp.append(s.tokens_per_target_pass)
theo.append(theoretical_speedup(s.acceptance_rate, k))
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(10, 4))
ax1.plot(ks, acc, "o-"); ax1.set_xlabel("K"); ax1.set_ylabel("Acceptance rate")
ax2.plot(ks, tpp, "D-", color="green", label="measured")
ax2.plot(ks, theo, "s-", color="orange", label="theoretical")
ax2.set_xlabel("K"); ax2.set_ylabel("Tokens / target pass"); ax2.legend()
fig.tight_layout(); fig.savefig("code/acceptance_vs_k.png", dpi=140)Figure 1: Acceptance rate vs. K (left) and measured vs. theoretical tokens per target pass (right).
Figure 2 breaks the aggregate acceptance rate down into a per-step histogram. Each panel counts how many tokens a single speculative step produced (1 = only the correction token was kept; K+1 = all K draft tokens accepted plus the bonus). At low noise (high alignment, left panel), the distribution is heavily right-skewed: most steps land at K+1, meaning the draft was entirely correct. At medium noise (centre), the distribution spreads across all values, with a modest peak at 1 (early rejection is common). At high noise (right), the step almost always terminates at 1 or 2 tokens. This histogram is the operational picture behind the aggregate speedup numbers: a high acceptance rate means the right-hand bar dominates, and each target forward pass is doing maximum useful work.
The histograms are built by recording the size of every speculative_step return list:
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 3, figsize=(12, 4), sharey=True)
for ax, noise in zip(axes, [0.1, 0.3, 0.8]):
dec = SpeculativeDecoder(draft_noise=noise, draft_k=4, seed=0)
sizes = []
for _ in range(2000):
new_tokens, _, _ = dec.speculative_step(context_id=42)
sizes.append(len(new_tokens))
ax.hist(sizes, bins=range(1, 7), align="left", rwidth=0.8)
ax.set_title(f"noise={noise}")
ax.set_xlabel("Tokens accepted per step")
axes[0].set_ylabel("Count")
fig.tight_layout(); fig.savefig("code/tokens_per_step_dist.png", dpi=140)Figure 2: Per-step token-count histogram at three noise levels (K=4).
Figure 3 shows how the speedup responds to the full range of draft quality. The left panel sweeps draft noise from 0 (perfect draft, identical to target) to 1 (uniform random), for four values of K. Two things stand out: first, even a completely random draft (noise=1.0) still delivers more than 1 token per target pass, because the correction step and bonus token guarantee a floor. Second, the K=16 curve drops more steeply with noise than K=4; a high K is a bigger bet on draft quality, and when the draft is poor that bet loses hard. The right panel shows the theoretical speedup curves against the closed-form acceptance rate; the red dot marks the measured operating point for noise=0.3, confirming the simulation sits on the theoretical curve at moderate K.
The two-panel plot reuses the same SpeculativeDecoder and theoretical_speedup already defined:
import matplotlib.pyplot as plt
import numpy as np
noises = [0.0, 0.1, 0.3, 0.5, 0.8, 1.0]
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(11, 4))
for k in [2, 4, 8, 16]:
tpp = []
for n in noises:
dec = SpeculativeDecoder(draft_noise=n, draft_k=k, seed=0)
_, s = dec.generate(context_id=42, n_tokens=2000)
tpp.append(s.tokens_per_target_pass)
ax1.plot(noises, tpp, "o-", label=f"K={k}")
ax1.set_xlabel("draft_noise"); ax1.set_ylabel("Tokens / target pass"); ax1.legend()
alphas = np.linspace(0.0, 1.0, 50)
for k in [2, 4, 8, 16]:
ax2.plot(alphas, [theoretical_speedup(a, k) for a in alphas], label=f"K={k}")
dec = SpeculativeDecoder(draft_noise=0.3, draft_k=4, seed=0)
_, s = dec.generate(context_id=42, n_tokens=2000)
ax2.plot(s.acceptance_rate, s.tokens_per_target_pass, "ro", markersize=10)
ax2.set_xlabel("Acceptance rate α"); ax2.set_ylabel("Theoretical tokens/pass"); ax2.legend()
fig.tight_layout(); fig.savefig("code/speedup_vs_alignment.png", dpi=140)Figure 3: Throughput vs. draft noise (left) and theoretical speedup vs. α with the measured operating point marked (right).
Interpreting the Numbers
The K=1 baseline is illuminating. Leviathan et al. note an initial log(2) bits/token information-theoretic loss from speculative sampling; that effect does not appear here because we use deterministic acceptance with no rejection variance. At K=1 with acceptance rate α=0.843, the measured throughput of 1.84 matches the theoretical formula exactly: (1 − 0.843²) / (1 − 0.843) = 1.84. The formula holds perfectly for K=1 because there is only one draft token and independence is trivially satisfied.
At high K, the theoretical formula starts to underestimate, and the reason comes down to an assumption that breaks under real workloads. The formula (1 − α^(K+1)) / (1 − α) assumes each draft token is accepted independently with the same probability α. But in practice, acceptance runs exhibit positive correlation: when the draft model is in a high-probability region (common tokens, repetitive phrases), it tends to produce a long run of correct tokens. At K=16, the simulation measures 6.10 tokens/pass while the theoretical model predicts 1.47. The discrepancy grows because K=16 strongly benefits from those long acceptance runs that the independence assumption fails to account for.
Even a fully random draft helps. At noise=1.0 (uniform random draft), the simulation still produces 1.80 tokens per target pass. The correction step and bonus token guarantee a minimum floor: every speculative step produces at least one token drawn from the true target distribution, plus any portion of the draft that happened to align.
The Acceptance Rate Formula
The theoretical expected tokens per target pass under independent acceptance:
E[tokens] = Σᵢ₌₀ᴷ αⁱ = (1 − α^(K+1)) / (1 − α)Note the sum has K+1 terms because the i=0 term accounts for the guaranteed correction/bonus token; this is why the K=1 baseline equals 1 + α = 1.843, lining up with the K=1 row of the table.
Derivation:
- With probability 1, at least the correction/bonus token is accepted: contributes 1
- With probability α, the first draft token is accepted: contributes 1 more
- With probability α², the first two are accepted: contributes 1 more
- … up to K draft tokens with probability αᴷ
At α=0.85, K=4: (1 − 0.85⁵) / (1 − 0.85) = (1 − 0.444) / 0.15 = 3.71 tokens/pass.
At α=1.0 (perfect draft): K+1 = 5 tokens/pass exactly.
Three Key Design Decisions
The correction step is not standard rejection sampling. When a draft token is rejected, the algorithm does not resample from q. It samples from max(0, q−p)/Z, the probability mass where q exceeds p. This removes the over-represented mass from q (where the draft was over-confident) and fills in the under-represented mass. Standard rejection sampling would be unbiased but potentially very inefficient; the correction step is always a single sample.
Stopping at the first rejection is correct. Once a draft token is rejected, subsequent tokens in the draft were sampled conditioned on a wrong prefix. Verifying them would require re-running the target model on the corrected prefix anyway, so the algorithm stops and starts a new round from the corrected position.
The bonus token is necessary for distribution correctness. If all K draft tokens are accepted, they were each accepted with probability min(1, q/p) < 1 unless p=q. Returning just the K draft tokens would bias the output distribution toward tokens favoured by the draft. The bonus token drawn directly from q corrects this bias and ensures the joint output distribution equals q exactly.
Production Considerations
Choosing K. In practice K=4 or K=5 is the common sweet spot. Beyond K=8, you are betting heavily on long acceptance runs that rarely occur for diverse text generation. K is also bounded by memory: the draft model needs to hold K proposed tokens with their key-value (KV) cache to enable the target’s parallel verification.
Draft model selection. The draft model must share the tokeniser and embedding space with the target model. In production systems such as Medusa and SpecInfer, the draft model is typically a distilled or compressed version of the target: a 7B draft for a 70B target, or a set of lightweight speculative heads attached to the target’s early layers.
Batched inference interaction. Standard autoregressive batching collects requests into a batch to amortise the cost of one forward pass. Speculative decoding changes the shape: instead of a batch of 1-token continuations, you verify a batch of K-token drafts per request. This interacts non-trivially with KV cache management and attention mask construction in production inference servers like vLLM.
Acceptance rate monitoring. In production, acceptance rate is a key operational metric. A drop in acceptance rate (below ~0.6 for a well-tuned system) means the draft model’s distribution has drifted from the target, perhaps due to a target model update, distribution shift in incoming prompts, or a bug in the draft’s KV cache. Track it per-request category (code vs. prose vs. factual Q&A) since acceptance rates vary significantly by domain.
When speculation hurts. If the acceptance rate drops low enough (below ~0.3 for K=4), each speculative step costs more than it saves: you are running the draft model K times and the target model once, and only getting ~1.5 tokens out. Production systems implement a fallback by monitoring rolling acceptance rate and switching to standard autoregressive decoding when the rate drops below a threshold.
Speedup Summary
| Configuration | Acceptance rate | Tokens/target pass | vs. greedy |
|---|---|---|---|
| Perfect draft (noise=0.0), K=4 | 1.000 | 5.00 | 5.0× |
| Good draft (noise=0.1), K=4 | 0.861 | 4.43 | 4.4× |
| Typical draft (noise=0.3), K=4 | 0.654 | 3.61 | 3.6× |
| Poor draft (noise=0.5), K=4 | 0.505 | 3.02 | 3.0× |
| Random draft (noise=1.0), K=4 | 0.200 | 1.80 | 1.8× |
| Greedy baseline | — | 1.00 | 1.0× |
The verified numbers: with a modestly-accurate draft (acceptance rate 0.65), K=4 produces 3.61 tokens per target forward pass against a greedy baseline of 1.0, a direct 3.6× reduction in the number of large-model forward passes needed to generate a fixed-length response.
In production settings (7B draft, 70B target), acceptance rates of 0.8–0.9 are achievable on conversational text, yielding 4–5× throughput gains. On code generation, where the draft model is less reliable at predicting exact syntax, acceptance rates drop to 0.6–0.7, giving 3–4× gains. Even at 0.6, speculative decoding is a significant throughput multiplier for a fixed hardware budget.