Fast Inference from Transformers via Speculative Decoding

ArXiv: 2211.17192

🎯 Pitch

A standard 11B-parameter Transformer can be made 2–3× faster at generating text without changing a single model weight or the output distribution, simply by having a tiny 77M-parameter draft model guess multiple future tokens that the large model then checks in parallel.

---

1. Executive Summary

This paper introduces speculative decoding, an algorithm that accelerates sampling from large autoregressive models without changing their output distribution by computing multiple tokens in parallel. The core idea pairs a fast approximation model (e.g., a 77M-parameter T5-small) with a slow target model (e.g., a 11B-parameter T5-XXL)—the approximation model generates multiple candidate tokens, and the target model evaluates them all concurrently using a novel speculative sampling procedure that accepts or rejects guesses to guarantee exact equivalence to the target distribution. Evaluated on T5-XXL across translation and summarization tasks, the method achieves a 2×–3× walltime speedup over the optimized T5X implementation—for instance, a 3.4× improvement with T5-small on English-to-German argmax decoding—establishing that autoregressive decoding can be meaningfully accelerated without retraining, architecture changes, or output modification whenever spare compute resources are available to absorb the additional arithmetic operations.

2. Context and Motivation

The Core Problem: Autoregressive Decoding Is Inherently Sequential

The fundamental bottleneck this paper tackles is deceptively simple: decoding K tokens from a large autoregressive model requires K serial calls to that model. Each call depends on the previous one's output—the model generates token $t$, appends it to the prefix, then feeds the extended sequence back through the entire model to generate token $t+1$. This is not a software implementation artifact; it is baked into the autoregressive formulation itself, where the joint probability is factorized as $p(x_1, x_2, \dots, x_K) = \prod_{i=1}^{K} p(x_i \mid x_{<i})$, and each factor requires a full forward pass through the model.

This serial dependency is especially painful for large Transformers (GPT-3, LaMDA, PaLM, T5-XXL), where a single forward pass is already computationally expensive. Making matters worse, the authors note that inference from these large models is often not bottlenecked on arithmetic operations but rather on memory bandwidth and communication—reading the model's weights from memory and managing the key-value (KV) cache dominates the walltime. This means additional arithmetic compute units often sit idle during decoding. The paper frames this as an opportunity: since spare compute is available, increasing concurrency could reduce latency even if total arithmetic operations increase.

The real-world stakes are substantial. As Section 1 notes, large autoregressive models have become dominant across text and image domains (GPT-3, LaMDA, Parti, PaLM), and they are deployed in production settings where latency directly impacts user experience. A chatbot that takes 500ms to generate a response with an 11B-parameter model is a fundamentally different product than one that takes 200ms. The gap is not merely a matter of patience—it determines whether large models can be used at all in interactive applications, on-device settings, or high-throughput serving environments.

Why Prior Approaches Fall Short

The paper identifies three broad categories of prior work on accelerating inference, each with significant limitations relative to what the authors aim to achieve:

1. Uniformly applied efficiency methods (distillation, sparsification, quantization, architecture modification). These approaches—including knowledge distillation (Hinton et al., 2015), sparsification (Jaszczur et al., 2021), quantization (Hubara et al., 2016), and architectural changes like multi-query attention (Shazeer, 2019) or efficient Transformer designs (So et al., 2021)—aim to reduce the cost of every inference step equally. They can be effective but share a common set of drawbacks:

• They require changing the model architecture or training procedure. You cannot take an off-the-shelf T5-XXL checkpoint and apply quantization without retraining or fine-tuning to recover quality.
• They change the model's outputs. Distillation produces a different model with different behavior; even aggressive quantization can alter numerical precision in ways that shift the output distribution. There is no guarantee of identical outputs to the original large model.
• They require a separate development and evaluation pipeline. Organizations must invest in training, validating, and deploying a new model variant, which adds risk and engineering complexity.

2. Adaptive computation methods (early exits, adaptive attention spans, confidence-based adaptive Transformers). These methods—including depth-adaptive Transformers (Elbayad et al., 2019), adaptive attention spans (Sukhbaatar et al., 2019), early exits (Schuster et al., 2021; Scardapane et al., 2020; Bapna et al., 2020), and the Wisdom of Committees approach (Schwartz et al., 2020)—stem from the observation that not all inference steps are equally difficult. Some tokens in a sequence require the full depth or width of the large model; others can be accurately predicted by a smaller, faster sub-component.

These approaches are a closer conceptual match to speculative decoding because they share the insight that some steps are "harder" and some are "easier." However, the paper identifies specific shortcomings that distinguish its contribution:

• They typically require architectural changes and custom training. Early exit methods need the model to be trained with auxiliary loss terms at intermediate layers; adaptive attention spans require modifying the attention mechanism itself.
• They change the model's outputs. The Wisdom of Committees method (Schwartz et al., 2020), which is perhaps the closest prior work because it leverages off-the-shelf smaller models, uses a heuristic to decide when to stop using the large model and therefore "loses the guarantee of identical outputs." The paper explicitly calls this out as a limitation that speculative decoding addresses.
• They save on both inference time AND arithmetic operations, which is generally a good thing, but means they don't exploit the spare compute resources that the authors identify as commonly available in memory-bandwidth-bound regimes.

3. Prior speculative-execution-based decoding methods (Blockwise Parallel Decoding, Shallow Aggressive Decoding). Two prior works directly apply speculative execution to autoregressive decoding, making them the closest predecessors to this paper:

• Blockwise Parallel Decoding (Stern et al., 2018) decodes several tokens in parallel by training a custom auxiliary model that predicts multiple future tokens. The paper identifies three key limitations: (a) it only supports greedy (temperature=0) decoding, not general stochastic sampling, (b) it requires training a custom model rather than using off-the-shelf approximations, and (c) it focuses on preserving downstream task quality rather than guaranteeing exact output distribution equivalence. The distinction between "preserving quality" and "guaranteeing identical outputs" is subtle but important: the former means the method may produce different but similarly-good outputs, while the latter means the probability distribution over all possible outputs is provably unchanged.

• Shallow Aggressive Decoding (SAD) (Sun et al., 2021) also decodes multiple tokens in parallel but only supports copying input tokens to the output—it is designed specifically for tasks where inputs and outputs are very similar, like grammatical error correction. It does not support general-purpose approximation models (e.g., a smaller Transformer) and, like Blockwise Parallel Decoding, does not support stochastic sampling.

The Gap This Paper Fills

The authors position speculative decoding as filling a specific, previously unoccupied point in the design space: a method that simultaneously

1. Accelerates inference without changing the model architecture or requiring retraining. You can take existing off-the-shelf model checkpoints (T5-XXL, LaMDA) and accelerate them immediately, using existing smaller models (T5-small, LaMDA-100M) as the approximation model. This matters enormously for production deployment—it means no model development cycle, no quality regression testing, no new training infrastructure.

2. Preserves the exact output distribution, provably. The paper does not aim for "similar quality" or "comparable behavior"—it provides a mathematical proof (Appendix A.1) that speculative sampling produces tokens distributed identically to sampling from the target model alone. This is what allows the authors to claim the method is a drop-in replacement: any code that currently calls the target model can call the speculative decoding wrapper and get identical results faster.

3. Supports arbitrary sampling methods (not just greedy). By casting all sampling methods (argmax, top-k, nucleus, temperature-based) into a unified "standardized sampling" framework (Section 2.2), the method works with any of them. This is critical because real-world deployments rarely use pure argmax—they use temperature, top-p, or other mechanisms to control diversity.

4. Exploits the spare compute resources available in memory-bandwidth-limited regimes. Unlike adaptive computation methods that aim to reduce total operations, speculative decoding increases total arithmetic operations while decreasing walltime by trading compute for concurrency. This counterintuitive tradeoff—doing more work to finish faster—is what makes the method uniquely suited to the hardware landscape the authors describe, where Transformer inference is bottlenecked on memory bandwidth rather than arithmetic throughput.

The Conceptual Foundation: Stochastic Speculative Execution

The paper generalizes speculative execution from its well-known application in CPU branch prediction (Burton, 1985; Hennessy & Patterson, 2012) to the stochastic setting. In a CPU, branch prediction speculates on which path the instruction stream will take and executes ahead; if the prediction is correct, the results are committed, and if not, the speculative work is discarded. The key adaptation here is that in a stochastic setting, an action may be "needed" with some probability rather than being a binary yes/no. The speculative sampling procedure (Section 2.3) is designed to handle this probabilistic acceptance/rejection while maintaining exact distributional equivalence.

This framing is important because it connects the paper's contribution to a well-understood optimization technique in computer architecture, making the innovation legible beyond the ML community, and because it clarifies why the method works on general autoregressive models: any model that predicts a probability distribution over the next token can serve as the "branch predictor" (the approximation model $M_q$), and any model that verifies those predictions serves as the "execution unit" (the target model $M_p$).

Practical Motivation: The 2×–3× Production Reality

The paper's empirical demonstration is not theoretical—it is measured walltime against T5X, the production-grade serving framework for T5 models (Roberts et al., 2022). The 2×–3× speedup is not a simulation or a FLOPs calculation; it is actual latency reduction on a TPU-v4 running batch size 1 inference. This practical framing is central to the paper's positioning: speculative decoding is not a research prototype requiring special infrastructure; it can be integrated into existing serving stacks with minimal changes, using existing model checkpoints, and deployed immediately.

The independent replication by Chen et al. (2023) showing similar 2×–2.5× improvements on Chinchilla 70B, published shortly after this paper's initial release, is cited (Section 5) as evidence that the method generalizes across model families and implementation details, further strengthening the practical positioning.

3. Technical Approach

3.1 Reader Orientation

The paper builds speculative decoding—a drop-in replacement for the standard autoregressive sampling loop that produces tokens from a large language model faster by using a smaller, cheaper model to guess multiple future tokens at once, then having the large model check all guesses in parallel, accepting the correct ones and fixing any mistakes. It solves the problem that decoding K tokens from a Transformer requires K sequential forward passes—each dependent on the previous one's output—by converting some of that serial dependency into parallel work, trading increased arithmetic operations (doing more total computation) for reduced walltime (finishing sooner), with the critical guarantee that the probability distribution over generated sequences is provably identical to what the large model would have produced on its own.

3.2 Big-Picture Architecture (Diagram in Words)

The system has four major components arranged in a producer-verifier loop:

1. Target Model ($M_p$) — the large, slow autoregressive model whose sampling we want to accelerate (e.g., T5-XXL with 11B parameters). This model defines the ground-truth distribution $p(x_t \mid x_{<t})$ that must be preserved.

2. Approximation Model ($M_q$) — a smaller, faster autoregressive model that approximates the target's behavior (e.g., T5-small with 77M parameters). It generates guesses: sequences of $\gamma$ tokens that $M_p$ might produce. The quality of the approximation determines the speedup; the model can be any autoregressive model, an n-gram model, or even a heuristic—there are no architectural constraints.

3. Speculative Sampling Procedure — the core algorithmic innovation (Algorithm 1 in the paper, detailed in Section 2.3). It takes the $\gamma$ tokens generated by $M_q$ and the $\gamma+1$ probability distributions computed by $M_p$ (one distribution per prefix position, all computed in parallel), and determines which guesses to accept and which to reject, using a token-by-token acceptance criterion based on comparing $p(x)$ and $q(x)$ at each position. When it rejects a guess, it resamples from a corrected distribution that guarantees exact equivalence to $p(x)$. The procedure guarantees that every accepted token from $M_q$ would have been sampled with the correct probability under $M_p$, and every correction token is sampled from the right residual distribution.

4. Orchestration Loop — the outer loop that repeatedly calls the speculative sampling procedure, accumulating accepted tokens into the prefix, until a stopping condition is reached (e.g., end-of-sequence token or maximum length). Each iteration produces between 1 and $\gamma+1$ new tokens while requiring only one serial call to $M_p$ (all $\gamma+1$ evaluations of $M_p$ run in parallel).

Information flows as follows: the current prefix enters the system → $M_q$ generates $\gamma$ candidate tokens autoregressively (a sequential loop, but fast because $M_q$ is small) → $M_p$ evaluates all $\gamma+1$ prefixes in parallel (the prefix plus each successively longer candidate prefix) → speculative sampling accepts $n \in [0, \gamma]$ guesses and produces one correction token → the prefix is extended by $n+1$ tokens → repeat.

3.3 Roadmap for the Deep Dive

• First, the standardized sampling framework (Section 2.2), because it is the prerequisite that lets the paper treat all sampling methods (argmax, temperature, top-k, nucleus) uniformly—everything downstream operates on adjusted probability distributions, not raw logits.
• Second, the speculative sampling procedure itself (Section 2.3 and Algorithm 1), because it is the paper's core intellectual contribution: the acceptance/rejection criterion and the corrected resampling distribution that together guarantee distributional equivalence.
• Third, the mathematical analysis of expected tokens per iteration (Section 3.1–3.2), including the derivation of the acceptance rate $\alpha = 1 - \text{DLK}(p,q)$ and its relationship to a natural divergence measure, because this analysis is what lets practitioners predict speedup from measurable properties of $M_p$ and $M_q$.
• Fourth, the walltime and operations analysis (Sections 3.3–3.4), including the cost coefficient $c$, the speedup formula, and the tradeoff between latency and total arithmetic, because this determines when speculative decoding is actually beneficial versus when it wastes resources.
• Fifth, the choice of $\gamma$ (Section 3.5), because the number of guesses is the primary tunable parameter and its optimal value depends on both model similarity ($\alpha$) and relative cost ($c$).
• Sixth, the approximation model taxonomy (Section 3.6), because the paper tests several qualitatively different types of $M_q$—smaller Transformers, n-gram models, heuristic copiers—each with different cost/accuracy tradeoffs, and the framework supports all of them without modification.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a systems and algorithms paper whose core idea is that autoregressive decoding can be accelerated by speculatively executing a cheaper model's predictions and verifying them in parallel with the expensive model, using a novel acceptance procedure that preserves the exact target distribution.

---

Standardized Sampling: Reducing All Sampling Methods to a Common Form

Before introducing speculative sampling, the paper establishes a critical reduction (Section 2.2): all common sampling methods can be cast as standard sampling from an adjusted probability distribution. This is important because the speculative sampling procedure operates on probability distributions $p(x)$ and $q(x)$—it needs to compare them pointwise, accept or reject samples based on their ratio, and compute normalized residual distributions. If different sampling methods (argmax, top-k, nucleus, temperature) were handled at the logits level with bespoke logic, the acceptance procedure would need separate implementations for each. By standardizing first, the paper's Algorithm 1 works identically regardless of the sampling method.

The reduction works as follows. Any sampling method defines a deterministic transformation from a raw probability distribution (output by the model's softmax) to an adjusted distribution from which tokens are actually drawn:

• Argmax sampling (temperature = 0): Zero out all probabilities except the maximum, then normalize. The adjusted distribution is a one-hot vector at the argmax token.
• Top-k sampling: Zero out all probabilities except the $k$ largest, then normalize.
• Nucleus (top-p) sampling: Sort probabilities descending, zero out tokens beyond the cumulative probability threshold $p$, then normalize.
• Temperature sampling: Divide all logits by a temperature $T$ before softmax, which sharpens ($T < 1$) or flattens ($T > 1$) the distribution. This is just a different raw distribution entering the same pipeline.

In all cases, the output is a proper probability distribution $\tilde{p}(x)$ over the vocabulary. The authors define $p(x)$ and $q(x)$ throughout the paper as these post-standardization distributions—the distributions that would actually be sampled from, not the raw model outputs.

This means that when Algorithm 1 refers to $p_i(x)$ and $q_i(x)$, these are the standardized distributions at position $i$. When $M_q$ samples $x_i \sim q_i(x)$, it samples according to whatever standardization is in effect (e.g., argmax means always taking the mode). When speculative sampling compares $p_i(x)$ and $q_i(x)$, it compares the post-standardization distributions, which is what ensures the guarantee holds for any sampling method.

The paper's experiments use two settings: temperature = 0 (argmax) and temperature = 1 (standard sampling from the unmodified softmax), but the framework is general.

Design choice: The authors could have implemented separate acceptance logic for each sampling method—e.g., for argmax, simply check whether the guessed token equals the target's argmax. The standardization approach is cleaner because it factors the sampling-method-specific logic into a preprocessing step, leaving the core algorithm sampling-method-agnostic. This is both mathematically elegant (the proof in Appendix A.1 holds for any proper distributions $p$ and $q$) and practically convenient (adding a new sampling method requires only implementing its standardization, not modifying the speculative decoding loop).

---

Speculative Sampling: The Core Algorithm

The speculative sampling procedure (Algorithm 1, Section 2.3) is the paper's central technical contribution. It addresses the following problem: given a prefix, we have access to (1) an approximation model $M_q$ that can quickly generate candidate tokens from its distribution $q(x)$, and (2) a target model $M_p$ that can compute its distribution $p(x)$ for any prefix—how do we use $M_q$'s guesses to produce multiple tokens per call to $M_p$, while guaranteeing that the resulting token sequence is distributed exactly as if we had sampled from $M_p$ autoregressively?

The naive approach—just take $M_q$'s output whenever it matches $M_p$'s most likely token—fails for two reasons. First, it doesn't handle stochastic sampling: if $p(x)$ assigns probability 0.4 to token A and 0.6 to token B, sometimes $M_q$ should generate B even though A is the mode. Second, it would change the distribution: always accepting $M_q$'s output when it's the argmax of $p(x)$ would increase the probability of the mode beyond what $p(x)$ specifies.

The solution is a token-by-token acceptance/rejection procedure with a specific corrected resampling distribution when rejection occurs.

Algorithm Walkthrough

Algorithm 1 proceeds in four phases for each iteration of the outer loop:

Phase 1: Generate $\gamma$ guesses from $M_q$ (sequential). Starting from the current prefix, $M_q$ generates $\gamma$ tokens autoregressively. For $i = 1$ to $\gamma$:

• Compute $q_i(x) = M_q(\text{prefix} + [x_1, \dots, x_{i-1}])$ — the approximation model's distribution given the prefix plus any previously generated guesses.
• Sample $x_i \sim q_i(x)$.

This is a standard autoregressive loop, but running $M_q$ is fast because it's much smaller than $M_p$. The output is a sequence of $\gamma$ tokens $x_1, \dots, x_\gamma$ that form a candidate continuation of the prefix.

Phase 2: Evaluate all prefixes with $M_p$ (parallel). For each position $i = 1$ to $\gamma+1$, compute $p_i(x) = M_p(\text{prefix} + [x_1, \dots, x_{i-1}])$. Specifically:

• $p_1(x)$ is $M_p$'s distribution given just the original prefix (no guesses added).
• $p_2(x)$ is $M_p$'s distribution given prefix + $[x_1]$.
• $p_3(x)$ is $M_p$'s distribution given prefix + $[x_1, x_2]$.
• ...and so on, up to $p_{\gamma+1}(x)$ given prefix + $[x_1, \dots, x_\gamma]$.

These $\gamma+1$ evaluations are independent of each other—each is a forward pass through $M_p$ on a different input sequence. On hardware that supports batching (GPUs, TPUs), they can all run in parallel, so the walltime cost is approximately one $M_p$ forward pass (plus the overhead of processing a batch of $\gamma+1$ sequences, which for Transformer decoders with KV-caching can be implemented efficiently by extending the KV-cache by one position at a time while masking appropriately).

Phase 3: Determine how many guesses to accept (sequential logic, negligible cost). Walk through the guesses from $i = 1$ to $\gamma$, and for each one, decide whether to accept or reject based on comparing $p_i(x_i)$ and $q_i(x_i)$:

• If $q_i(x_i) \leq p_i(x_i)$: accept the guess. The intuition is that $M_q$ was less confident in this token than $M_p$ is, so it's a "safe" guess—$M_p$ would have been at least as likely to produce it.
• If $q_i(x_i) > p_i(x_i)$: accept with probability $\frac{p_i(x_i)}{q_i(x_i)}$, otherwise reject. The intuition is that $M_q$ was overconfident relative to $M_p$, so we need to reject some fraction of these guesses to avoid oversampling tokens that $M_q$ likes more than $M_p$ does. The rejection probability $1 - \frac{p_i(x_i)}{q_i(x_i)}$ exactly compensates for the discrepancy.

This decision is made independently for each position $i$. The process stops at the first rejection—once a guess is rejected at position $n$, no further guesses ($x_{n+1}, \dots, x_\gamma$) are considered, even if some of them might have been acceptable. All $\gamma$ guesses are accepted only if every single one passes its individual acceptance test. This "stop at first rejection" property is what makes the algorithm correct: the distribution at position $n+1$ depends on what token was actually accepted at position $n$, and if we reject $x_n$, the prefix going forward changes, so all subsequent $p_i(x)$ distributions computed in Phase 2 become invalid for the corrected prefix.

Let $n$ be the number of accepted guesses ($0 \leq n \leq \gamma$, where $n=0$ means the very first guess was rejected).

Phase 4: Resample from corrected distribution if needed. If $n = \gamma$ (all guesses accepted), sample one additional token $t \sim p_{\gamma+1}(x)$ from $M_p$'s distribution at the final position. This gives $\gamma+1$ new tokens total.

If $n < \gamma$ (rejection occurred at position $n+1$), we need to replace the rejected token $x_{n+1}$ with a correctly sampled token. We cannot simply sample from $p_{n+1}(x)$ because that would overrepresent tokens: the acceptance procedure already accepted $x_1, \dots, x_n$ with specific probabilities, and unconditionally sampling from $p_{n+1}(x)$ would double-count the probability mass that was already "used up" by the acceptance decisions. Instead, we sample from an adjusted distribution:

$p'(x) = \text{norm}(\max(0, p_{n+1}(x) - q_{n+1}(x)))$

where $\text{norm}(\cdot)$ renormalizes the result to sum to 1. This adjusted distribution removes the probability mass that was already accounted for by the possibility of accepting $M_q$'s guess, leaving only the residual probability that $M_p$ assigns to tokens beyond what $M_q$ would have produced. The $\max(0, \cdot)$ ensures we never get negative probabilities (which would happen if $q(x) > p(x)$ for some $x$, but in that case the excess was handled by the rejection probability in Phase 3).

The final output is $\text{prefix} + [x_1, \dots, x_n, t]$: $n$ accepted guesses plus one corrected token, for $n+1$ total new tokens (between 1 and $\gamma+1$).

Why This Procedure Preserves the Target Distribution

The proof in Appendix A.1 shows that for a single step ($\gamma = 1$), a token sampled via speculative sampling is distributed exactly according to $p(x)$. Let's walk through the proof to build intuition:

Let $X$ be the token produced by speculative sampling. There are two ways to produce $X = x'$:

Case 1: The guess is accepted, and it equals $x'$. This happens when $M_q$ samples $x'$ (probability $q(x')$) and the acceptance test passes. The acceptance probability is $\min(1, \frac{p(x')}{q(x')})$, so the joint probability is:

$P(\text{guess accepted}, X = x') = q(x') \cdot \min\left(1, \frac{p(x')}{q(x')}\right) = \min(q(x'), p(x'))$

Case 2: The guess is rejected, and the corrected sample equals $x'$. The probability that any guess gets rejected is $1 - \beta$, where $\beta = \sum_x \min(p(x), q(x))$ is the overall acceptance probability (Theorem 3.5, proved below). The corrected distribution is $p'(x) = \frac{p(x) - \min(q(x), p(x))}{1 - \beta}$ (this is the normalized version of $\max(0, p(x) - q(x))$; the denominator $1-\beta$ is exactly the normalizing constant). So:

$P(\text{guess rejected}, X = x') = (1 - \beta) \cdot p'(x') = (1 - \beta) \cdot \frac{p(x') - \min(q(x'), p(x'))}{1 - \beta} = p(x') - \min(q(x'), p(x'))$

Total: $P(X = x') = \min(p(x'), q(x')) + p(x') - \min(p(x'), q(x')) = p(x')$. The $\min$ terms cancel exactly.

The proof generalizes to $\gamma > 1$ because each position's acceptance decision is independent (given the prefix up to that point), and the "stop at first rejection" rule ensures that the distribution at position $n+1$ correctly accounts for the fact that positions $1$ through $n$ were accepted.

Key insight: The acceptance probability $\min(1, \frac{p(x)}{q(x)})$ can be understood as importance sampling: we sampled from $q$, we want to sample from $p$, and we're using the ratio $\frac{p(x)}{q(x)}$ as an importance weight. When the weight is $\geq 1$, we always accept (we wanted this token more than $q$ did); when it's $< 1$, we accept with probability equal to the weight. The residual distribution $p'(x)$ handles the probability mass that importance sampling "missed."

Comparison to Rejection Sampling

Appendix A.2 explicitly contrasts speculative sampling with standard rejection sampling. In rejection sampling, one would sample $x \sim q(x)$, accept with probability $\frac{p(x)}{M q(x)}$ where $M = \max_x \frac{p(x)}{q(x)}$, and otherwise reject and start over. The expected acceptance probability in rejection sampling is $\sum_x p(x) \min_{x'} \frac{q(x')}{p(x')} \leq \sum_x \min(p(x), q(x)) = \alpha$. That is, it's lower than $\alpha$ (potentially much lower, since $\min_{x'} \frac{q(x')}{p(x')}$ can be very small if there's a token where $q$ assigns near-zero probability but $p$ doesn't). Speculative sampling achieves a higher acceptance rate because it only penalizes individual overconfident tokens (where $q(x) > p(x)$), not the global maximum ratio. This is what makes speculative sampling practical whereas rejection sampling would be too inefficient.

---

Expected Number of Generated Tokens: The Acceptance Rate $\alpha$

Section 3.1 analyzes the reduction factor in serial calls to $M_p$. The key quantity is the acceptance rate $\beta_{x_{<t}}$, defined (Definition 3.1) as the probability of accepting a single guess $x_t \sim q(x_t \mid x_{<t})$ under the speculative sampling criterion, given a specific prefix $x_{<t}$.

The paper then makes a simplifying assumption: the $\beta$s are independent and identically distributed (i.i.d.) across positions, with expected value $\alpha = \mathbb{E}[\beta]$. This is acknowledged as an approximation—in reality, $\beta$ varies based on context (some prefixes are "easier" for $M_q$ to match $M_p$ than others)—but it makes the analysis tractable and provides a useful nominal value.

Under the i.i.d. assumption, the number of accepted guesses $n$ before the first rejection follows a geometric distribution with success probability $1 - \alpha$ (where "success" here means rejection—the process stops). However, $n$ is capped at $\gamma$ (we only generated $\gamma$ guesses), so it's a capped geometric or truncated geometric variable. The expected number of generated tokens (including the final corrected token) is:

$\mathbb{E}[\text{\# generated tokens}] = \frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$

where $\alpha$ is the expected acceptance rate per token and $\gamma$ is the number of guesses.

What it computes: given an average per-token acceptance probability $\alpha$ and a guess budget $\gamma$, this formula gives the expected number of tokens produced per iteration of Algorithm 1. For example, if $\alpha = 0.6$ and $\gamma = 5$, we get $\frac{1 - 0.6^6}{1 - 0.6} = \frac{1 - 0.0467}{0.4} = 2.38$ tokens per iteration on average. If $\alpha = 0.9$ and $\gamma = 10$, we get $\frac{1 - 0.9^{11}}{1 - 0.9} = \frac{1 - 0.314}{0.1} = 6.86$ tokens per iteration.

Why this form: the numerator $1 - \alpha^{\gamma+1}$ is the probability that at least one rejection occurs within $\gamma+1$ trials, which is exactly the probability that we don't accept all $\gamma$ guesses (plus need a $\gamma+1$-th). The denominator $1 - \alpha$ is the expected number of trials until first rejection in an untruncated geometric distribution. The ratio of these terms gives the capped expectation. As $\gamma \to \infty$, the formula approaches $\frac{1}{1-\alpha}$, which is the untruncated geometric mean—if we could guess indefinitely, we'd get $\frac{1}{1-\alpha}$ tokens per $M_p$ call (e.g., $\alpha = 0.8$ yields 5 tokens per call).

Figure 2 in the paper plots this function for various $\gamma$ values, showing diminishing returns: going from $\gamma=3$ to $\gamma=5$ adds more benefit when $\alpha$ is high (steep curve region) than when $\alpha$ is low (flat region), because with low $\alpha$, you rarely get past the first few guesses anyway.

---

Computing $\alpha$ from $p$ and $q$: The $\text{DLK}$ Divergence

Section 3.2 derives a clean formula for $\alpha$ in terms of $p(x)$ and $q(x)$. This is important because it lets practitioners estimate expected speedup without running the full speculative decoding loop—they can just sample the two models' distributions on representative prefixes and compute the expected overlap.

The derivation introduces a new divergence measure:

Definition 3.2 (DLK Divergence):

$\text{DLK}(p, q) = \sum_x |p(x) - M(x)| = \sum_x |q(x) - M(x)|$

where $M(x) = \frac{p(x) + q(x)}{2}$ is the elementwise mean of the two distributions.

What it computes: $\text{DLK}$ measures the total variation between $p$ and $q$ but computed against their mean $M$ rather than against each other. The second equality ($\sum_x |p - M| = \sum_x |q - M|$) holds because $M$ is exactly the midpoint between $p$ and $q$, so the distance from $p$ to $M$ equals the distance from $M$ to $q$ at every point.

Lemma 3.3 shows an alternative characterization:

$\text{DLK}(p, q) = 1 - \sum_x \min(p(x), q(x))$

Proof: $\sum_x |p(x) - M(x)| = \sum_x \frac{|p(x) - q(x)|}{2}$. Now, for any two numbers $a, b$, we have $\frac{|a-b|}{2} = \frac{a+b}{2} - \min(a,b)$. So $\sum_x \frac{|p(x)-q(x)|}{2} = \sum_x \left(\frac{p(x)+q(x)}{2} - \min(p(x), q(x))\right) = 1 - \sum_x \min(p(x), q(x))$, since $\sum_x p(x) = \sum_x q(x) = 1$.

This characterization gives immediate intuition:

• $\text{DLK}(p, q) = 0$ if and only if $p = q$ (complete overlap—the min equals the full distribution).
• $\text{DLK}(p, q) = 1$ if and only if $p$ and $q$ have disjoint support (no overlap—the min is zero everywhere).
• $\text{DLK}$ is symmetric: $\text{DLK}(p, q) = \text{DLK}(q, p)$.

Theorem 3.5 connects this divergence to the acceptance rate:

$\beta = 1 - \text{DLK}(p, q)$

Proof: The per-token acceptance probability (for a specific prefix) is:

$\beta = \mathbb{E}_{x \sim q(x)}\left[\begin{cases} 1 & \text{if } q(x) \leq p(x) \\ \frac{p(x)}{q(x)} & \text{if } q(x) > p(x) \end{cases}\right] = \mathbb{E}_{x \sim q(x)}\left[\min\left(1, \frac{p(x)}{q(x)}\right)\right]$

This expectation expands to $\sum_x q(x) \cdot \min(1, \frac{p(x)}{q(x)}) = \sum_x \min(q(x), p(x))$. So $\beta = \sum_x \min(p(x), q(x))$, and by Lemma 3.3, $\beta = 1 - \text{DLK}(p, q)$.

Corollary 3.6 gives the global expected acceptance rate:

$\alpha = 1 - \mathbb{E}[\text{DLK}(p, q)] = \mathbb{E}\left[\sum_x \min(p(x), q(x))\right]$

What this computes in practice: to estimate $\alpha$ for a given pair of models on a given task, generate a corpus of prefixes (e.g., by running $M_p$ autoregressively), and for each prefix, compute $\sum_x \min(p(x), q(x))$ by evaluating both models' full output distributions. The average across prefixes is $\alpha$. This is exactly how the paper produces the $\alpha$ values in Table 3—they evaluate on 10K tokens generated by $M_p$.

Why this form matters: $\alpha$ cleanly decomposes into a property of the two models' distributions that can be measured without running the full speculative decoding algorithm. $\alpha = 0.75$ means that, on average, the two distributions share 75% of their probability mass (in the $\min$ sense). A practitioner can compute $\alpha$ once for a given $(M_p, M_q)$ pair and then plug it into the speedup formulas to predict performance before implementing speculative decoding. Table 3 shows this is predictive: T5-small on EnDe translation has $\alpha = 0.75$ at temperature 0, yielding 3.4× speedup; T5-large has $\alpha = 0.82$ but higher cost, yielding only 1.7×.

---

Walltime Improvement Analysis

Section 3.3 translates the reduction in serial $M_p$ calls into actual walltime speedup, accounting for the cost of running $M_q$.

Definition 3.7 (Cost Coefficient):

$c = \frac{\text{time for one run of } M_q}{\text{time for one run of } M_p}$

where $c$ is a hardware and implementation-dependent ratio. In the paper's experiments, $M_q$ is typically two orders of magnitude smaller than $M_p$ (e.g., T5-small at 77M vs. T5-XXL at 11B), so $c$ values range from 0.015 to 0.11 (Table 4).

Theorem 3.8 (Walltime Improvement Factor):

$\text{Improvement factor} = \frac{1 - \alpha^{\gamma+1}}{(1 - \alpha)(\gamma c + 1)}$

where $\alpha$ is the expected acceptance rate, $\gamma$ is the number of guesses, and $c$ is the cost coefficient.

What it computes: the ratio of walltime per token for standard autoregressive decoding to walltime per token for speculative decoding. An improvement factor of 3 means speculative decoding generates tokens 3× faster (in wall-clock time) than standard decoding.

Derivation: Let $T$ be the walltime of one $M_p$ forward pass (which produces one token in standard decoding). One iteration of Algorithm 1 costs:

• $\gamma c T$ for running $M_q$ $\gamma$ times (each run costs $cT$).
• $T$ for running $M_p$ once (all $\gamma+1$ evaluations run in parallel, so walltime = one forward pass).
• Total per iteration: $T(\gamma c + 1)$.

This iteration produces $\frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$ tokens on average (Equation 1). So the cost per token is $\frac{T(\gamma c + 1)(1 - \alpha)}{1 - \alpha^{\gamma+1}}$. Standard decoding costs $T$ per token. The improvement factor is the ratio of these: $\frac{T}{T(\gamma c + 1)(1 - \alpha) / (1 - \alpha^{\gamma+1})} = \frac{1 - \alpha^{\gamma+1}}{(1 - \alpha)(\gamma c + 1)}$.

Why this form: it separates model-intrinsic factors ($\alpha$) from hardware/implementation factors ($c$, $\gamma$). The numerator $\frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$ is the pure algorithmic speedup—how many fewer serial $M_p$ calls we need. The denominator $\gamma c + 1$ accounts for the overhead of running $M_q$, which grows linearly with $\gamma$. If $M_q$ is negligibly cheap ($c \approx 0$), the improvement factor approaches the pure algorithmic speedup. If $M_q$ is expensive ($c$ is large), the overhead eats into the gains, and for a given $\alpha$, there's a maximum $\gamma$ beyond which adding more guesses actually reduces speedup.

Corollary 3.9 provides a simple existence condition: if $\alpha > c$, then there exists some $\gamma$ for which speculative decoding improves upon standard decoding, and the improvement factor is at least $\frac{1 + \alpha}{1 + c}$. This lower bound comes from evaluating $\gamma = 1$: with one guess, the improvement is $\frac{1 - \alpha^2}{(1 - \alpha)(c + 1)} = \frac{1 + \alpha}{1 + c}$. If even this minimal configuration doesn't help ($\alpha \leq c$), then no $\gamma$ will help because the approximation model is too expensive relative to how well it matches the target.

In the paper's experiments (Table 4), $c$ ranges from 0.015 (T5-small) to 0.11 (T5-large), while $\alpha$ ranges from 0.53 to 0.82. The condition $\alpha > c$ is easily satisfied in all cases, confirming that speculative decoding is in the beneficial regime.

Assumption: Theorem 3.8 assumes "long enough generations" so that boundary effects (the first and last iterations) are negligible. It also assumes that $\gamma+1$ evaluations of $M_p$ can run in parallel without increasing per-evaluation walltime, which is true on GPUs/TPUs with sufficient memory to batch the sequences.

---

Number of Arithmetic Operations: The Latency-Compute Tradeoff

Section 3.4 explicitly addresses the tradeoff that speculative decoding makes: reduced walltime at the cost of increased total arithmetic operations. This is the central distinction between speculative decoding and methods like distillation or quantization that reduce both latency and total compute.

Definition 3.10 (Operations Cost Coefficient):

$\hat{c} = \frac{\text{arithmetic operations per token of } M_q}{\text{arithmetic operations per token of } M_p}$

Analogous to the walltime cost $c$, but measured in FLOPs rather than seconds.

Theorem 3.11 (Operations Increase Factor):

$\text{Operations factor} = \frac{(1 - \alpha)(\gamma \hat{c} + \gamma + 1)}{1 - \alpha^{\gamma+1}}$

What it computes: the ratio of total arithmetic operations (FLOPs) per generated token for speculative decoding versus standard decoding. A factor of 1.5 means speculative decoding uses 50% more total FLOPs per token.

Derivation: Let $\hat{T}$ be the operations per token of standard decoding (one $M_p$ forward pass). One iteration of Algorithm 1 costs:

• $\hat{T} \hat{c} \gamma$ for $\gamma$ runs of $M_q$.
• $\hat{T}(\gamma + 1)$ for $\gamma+1$ parallel runs of $M_p$.
• Total per iteration: $\hat{T}(\gamma \hat{c} + \gamma + 1)$.

Dividing by expected tokens per iteration ($\frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$) and by $\hat{T}$ gives the factor.

When does the compute cost matter? The paper identifies two regimes:

• Accepted guesses cost nothing extra: when a guess is accepted, the $\gamma+1$ evaluations of $M_p$ were done in parallel with the evaluation that produced the accepted token, so the arithmetic was "free" in terms of latency—it ran concurrently and didn't increase walltime. The total operations are higher, but latency is lower.
• Rejected guesses waste computation: when a guess is rejected at position $n+1$, the $M_p$ evaluations at positions $n+2$ through $\gamma+1$ become irrelevant (they were computed for prefixes that never materialize). This is the compute waste—it increases total operations without contributing to output. The higher the rejection rate (lower $\alpha$), the more waste.

The paper notes an important bound: for Transformer decoders, the total arithmetic operations of speculative decoding (excluding $M_q$ runs) can be bounded from above by a single run of a same-size Transformer encoder. This is because an encoder processes all positions in parallel anyway, and speculative decoding's $\gamma+1$ parallel decoder forward passes have similar asymptotic complexity to one encoder forward pass. So even the increased operations stay within a factor of roughly 2× of the original decoder cost, which is acceptable in many deployments.

The memory bandwidth benefit: Critically, while arithmetic operations may increase, the number of memory accesses can decrease. The target model's weights and KV-cache are read once per iteration of Algorithm 1 (for all $\gamma+1$ parallel evaluations, batching amortizes the weight reads), whereas standard decoding reads them once per token. So the number of weight and KV-cache memory reads shrinks by a factor of $\frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$. Since Transformer inference is often memory-bandwidth-bound (not compute-bound), this reduction in memory traffic is what actually produces the walltime speedup, more than compensating for the extra arithmetic.

Table 1 and Figure 4 quantify this tradeoff for various $\alpha$ and $\gamma$ values. For example, with $\alpha = 0.8$ and $\gamma = 5$, operations increase by 1.63× while speed improves by 3.69×—a favorable tradeoff. With $\alpha = 0.6$ and $\gamma = 2$, operations increase by 1.53× for 1.96× speed—less favorable but still beneficial. The relationship is not linear: as $\gamma$ increases, the operations factor grows, but the speed factor grows faster when $\alpha$ is high (diminishing operations overhead relative to gains).

---

Choosing $\gamma$: The Optimal Number of Guesses

Section 3.5 addresses how to set $\gamma$, the primary tunable parameter. Given $c$ and $\alpha$, the optimal $\gamma$ maximizes the walltime improvement factor:

$\gamma^* = \arg\max_{\gamma \in \mathbb{Z}^+} \frac{1 - \alpha^{\gamma+1}}{(1 - \alpha)(\gamma c + 1)}$

How to find $\gamma^*$ in practice: since $\gamma$ is a small integer (typically 1–10), it can be found by simply evaluating the improvement factor for $\gamma = 1, 2, 3, \dots$ and picking the maximum. Figure 3 plots $\gamma^*$ as a function of $\alpha$ for various values of $c$, showing that:

• Higher $\alpha$ supports larger $\gamma$ (if $M_q$ matches $M_p$ well, it's worth guessing more aggressively).
• Higher $c$ reduces the optimal $\gamma$ (if $M_q$ is expensive, the overhead of many guesses outweighs the benefit).
• For $c \approx 0$ (negligible-cost approximation models like n-grams), $\gamma^*$ grows rapidly with $\alpha$, approaching infinity as $\alpha \to 1$ (but in practice capped by the $\frac{1}{1-\alpha}$ bound).

In the experiments (Table 2), $\gamma$ values range from 3 to 7 for Transformer-based $M_q$ models, chosen to balance $\alpha$ and $c$. T5-large uses smaller $\gamma$ (3) than T5-small (5–7) because its higher $c$ (0.11 vs. 0.015–0.02) makes additional guesses more expensive.

Oracle $\gamma$ and further improvements: The paper notes that since $\beta$ varies across tokens (the i.i.d. assumption is only an approximation), using a single fixed $\gamma$ for the entire generation is suboptimal. If we had an oracle that could predict the per-token $\beta$ (or equivalently, the difficulty of each prediction for $M_q$), we could dynamically vary $\gamma$: use more guesses when $M_q$ is matching $M_p$ closely, and fewer when it's not. The expected number of generated tokens with a perfect $\gamma$-oracle would be $\frac{1}{1-\alpha}$, which can be up to ~60% higher than the fixed-$\gamma$ optimum (for typical $\alpha$ and $c$ values). The paper leaves this dynamic-$\gamma$ exploration to future work but establishes the upper bound.

---

Taxonomy of Approximation Models

Section 3.6 discusses what kinds of models can serve as $M_q$. The framework is agnostic to the architecture, training procedure, or even parameterization of $M_q$—any mechanism that produces a probability distribution $q(x)$ over the next token can be used. The authors categorize approximation models into three types, each with different operating characteristics:

1. Smaller Transformers (same architecture as $M_p$). These are the primary type tested in the paper: existing off-the-shelf smaller models from the same family (T5-small, T5-base, T5-large for T5-XXL; LaMDA-100M, LaMDA-2B, LaMDA-8B for LaMDA-137B; a 6M-parameter GPT-like model for a 97M-parameter GPT-like model). Key characteristics:

• Best $\alpha$ values: typically 0.5–0.9 (Table 3), meaning substantial overlap with $M_p$'s distribution.
• Non-negligible cost: $c$ values of 0.015–0.11, meaning the overhead of running $M_q$ must be accounted for in the speedup calculation.
• Production-friendly: requires no training—just use existing model checkpoints.
• Optimal sizing: the authors find that models roughly two orders of magnitude smaller than $M_p$ (e.g., 77M for 11B target) provide the best balance of $\alpha$ and $c$. Larger approximation models increase $\alpha$ but also increase $c$, eventually reducing net speedup (T5-large with $\alpha=0.82$ gives only 1.7× speedup vs. T5-small with $\alpha=0.75$ giving 3.4×).

2. Negligible-cost models ($c \approx 0$). These include n-gram models and simple heuristics whose evaluation cost is essentially zero compared to running $M_p$. With $c \approx 0$, the walltime improvement factor simplifies to $\frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$, bounded above by $\frac{1}{1 - \alpha}$ as $\gamma \to \infty$.

• N-gram models: In the English-German translation task (Table 3), a bigram model achieves $\alpha = 0.20$, yielding a 1.25× speedup at $\gamma = 3$—modest but non-trivial for a model that is just a table lookup. The unigram model achieves $\alpha = 0.08$, yielding minimal improvement.
• Context-copying heuristics: For tasks like summarization or chat interactions where outputs often repeat or lightly modify input text, an approximation model that copies tokens from matching prefixes in the context can yield surprisingly high $\alpha$ values, though the paper doesn't provide empirical measurements for this case.
• Random token selection: Even an approximation model that chooses tokens at random guarantees some (very small) improvement for all $M_p$, since $\alpha$ would be the probability of the random token matching $M_p$'s distribution, which is non-zero. This is noted as mostly a theoretical curiosity.
• Deployment advantage: these parameter-less models are even simpler to deploy from a production standpoint because they require no model loading, no GPU memory, and no separate serving infrastructure.

3. Non-autoregressive models. Instead of generating $\gamma$ tokens sequentially (the for i = 1 to γ loop in Algorithm 1), a non-autoregressive model (like those from Stern et al., 2018) could generate all $\gamma$ guesses in one shot. This would eliminate the sequential cost of running $M_q$ $\gamma$ times, replacing it with a single parallel generation step. The paper mentions this as a possibility without implementing it.

General design principle: The paper emphasizes that the choice of $M_q$ is unconstrained by the speculative sampling correctness guarantee—any $q(x)$ whatsoever yields exact distributional equivalence to $M_p$. The only effect of $M_q$'s quality is on $\alpha$, and therefore on speedup. This means $M_q$ can be optimized aggressively for speed or simplicity without fear of compromising output quality. The paper suggests that future work could train custom $M_q$ models specifically to maximize $\alpha$ (e.g., via distillation with soft targets from $M_p$, or by directly optimizing the $\min(p, q)$ objective), potentially yielding higher speedups than off-the-shelf approximation models.

---

Summary of Design Choices and Their Justifications

• Token-by-token acceptance with "stop at first rejection" over accepting all guesses independently: guarantees that the corrected distribution at position $n+1$ is computed with the correct conditioning prefix (the one where $x_1, \dots, x_n$ were actually accepted). If guesses were accepted independently, the prefix for later positions would be ambiguous when intermediate guesses are rejected.

• Corrected distribution $p'(x) = \text{norm}(\max(0, p(x) - q(x)))$ over sampling from $p(x)$ directly: removing the $\min(p, q)$ mass that was already accounted for by the acceptance probability prevents double-counting. Sampling from unmodified $p(x)$ would overrepresent tokens that $q(x)$ also assigns high probability to.

• Acceptance criterion $\min(1, \frac{p(x)}{q(x)})$ over always accepting when $q(x) \leq p(x)$ and rejecting otherwise: the probabilistic acceptance when $q(x) > p(x)$ is essential for stochastic sampling—it ensures that even when $M_q$ is "overconfident," the tokens it generates are accepted with exactly the right probability to maintain $p(x)$ as the marginal distribution.

• Parallel evaluation of all $\gamma+1$ prefixes by $M_p$ over sequential evaluation: this is what converts reduced serial calls into actual walltime reduction. Without batching the $\gamma+1$ evaluations, speculative decoding would be slower than standard decoding because it would require $\gamma+1$ serial $M_p$ calls per iteration instead of 1.

• Standardized sampling pre-processing over sampling-method-specific acceptance logic: cleanly separates concerns, makes the core algorithm independent of sampling method, and simplifies the proof of correctness.

• Off-the-shelf approximation models over custom-trained ones: prioritizes deployability and zero-friction adoption over maximum theoretical speedup. Organizations can accelerate existing models immediately without a training pipeline.

4. Key Insights and Innovations

Innovation 1: Generalizing Speculative Execution to the Stochastic Setting

What makes this distinctive at the idea level: The paper takes a classic systems optimization—speculative execution, where a processor guesses which branch an instruction stream will take and executes ahead—and generalizes it to a setting where the "correct answer" is not binary but probabilistic. In a CPU branch predictor, the speculation is either correct or incorrect, and incorrect work is simply discarded. In autoregressive decoding, the target model produces a probability distribution over tokens, not a single correct next token. The paper's conceptual leap is recognizing that this probabilistic verification can be made exact: you can accept or reject a guess with probabilities chosen so that the marginal distribution of accepted tokens precisely matches the target distribution.

This is not an obvious generalization. The authors had to invent a specific acceptance criterion (accept when $q(x) \leq p(x)$, accept with probability $p(x)/q(x)$ otherwise) and a specific corrected resampling distribution ($\text{norm}(\max(0, p(x) - q(x)))$) that together make the math work out. The fact that these choices are not arbitrary—they emerge from the requirement that the procedure be a valid importance sampler with the highest possible acceptance rate—is what elevates this from an engineering trick to an algorithmic contribution.

Comparison to prior work: Before this paper, speculative execution had been applied to neural decoding by Stern et al. (2018) in Blockwise Parallel Decoding and by Sun et al. (2021) in Shallow Aggressive Decoding. Both methods treated decoding as a deterministic process: they supported only greedy (temperature=0) sampling, where the model always picks the single most likely token. Under greedy decoding, verification is binary—the guess either matches the target's argmax or it doesn't—so standard speculative execution applies directly. The dominant assumption in these prior works was implicitly that stochastic sampling doesn't admit speculative execution because there's no single correct answer to verify against.

The paper shatters this assumption by showing that stochastic speculative execution is not only possible but comes with a provable correctness guarantee (Appendix A.1) that the output distribution is identical to sampling from the target model alone. The proof is clean and short—a few lines of algebra showing that the min terms cancel—but the conceptual move of treating the token distribution as the verification target rather than a single token is what makes it work.

Significance beyond raw performance: This generalization matters because real-world deployments of large language models rarely use pure greedy decoding. Production systems use temperature, top-p, or nucleus sampling to control diversity, avoid repetitive outputs, and enable multiple distinct generations from the same prompt. By making speculative execution compatible with any sampling method (via the standardized sampling reduction in Section 2.2), the paper opens the technique to essentially all practical use cases. Without this generalization, speculative decoding would be a niche optimization for a specific decoding mode; with it, it's a drop-in replacement for the standard sampling loop.

The generalization also has implications beyond language models. As the authors note in Section 6, stochastic speculative execution could apply to any setting where a slow function $f$ generates a distribution from which a second function $g$'s input is sampled—for example, in physics simulations or reinforcement learning where a policy model produces action distributions and a world model simulates outcomes. The core algorithmic idea (accept/reject from a cheap proposal distribution with exact distributional recovery) is domain-agnostic.

Evidence: The paper demonstrates the generalization empirically by reporting speedups for both temperature=0 and temperature=1 settings across all tasks (Table 2). The stochastic case (temp=1) consistently shows lower but still substantial speedups (2.3×–2.6× for T5-small) compared to greedy (3.1×–3.4×), which makes sense: stochastic distributions are "broader" and therefore harder for $M_q$ to match exactly, yielding lower $\alpha$ values (e.g., 0.62 vs. 0.75 for T5-small on EnDe). But the critical point is that the speedups exist at all, confirming that the probabilistic acceptance mechanism works in practice, not just in theory.

Fundamental vs. incremental: This is a fundamental contribution. It opens an entire class of algorithms—stochastic speculative execution—that didn't exist before. The specific application to autoregressive decoding is one instance, but the conceptual framework is general.

---

Innovation 2: Exact Distribution Preservation as a First-Class Design Constraint

What makes this distinctive at the idea level: Most work on accelerating inference treats output quality as something to be preserved approximately—you quantize the model, you hope the accuracy doesn't drop too much; you distill to a smaller model, you evaluate whether the smaller model performs comparably on benchmarks. The paper adopts a qualitatively different stance: output distribution equivalence is a hard constraint, not an optimization target. The method is designed so that for any input prefix, the probability of generating any particular output sequence is mathematically identical to what the target model would produce. This is not "similar quality" or "comparable behavior"—it's an equality that can be proven in a few lines of algebra.

This is a distinctive intellectual move because it reframes the problem from "how much can we accelerate before quality degrades unacceptably?" to "what is the maximum acceleration achievable under the constraint of exact equivalence?" The former requires empirical quality evaluations, careful benchmarking, and ongoing vigilance about regressions. The latter admits a clean mathematical analysis (the speedup formulas in Section 3) and eliminates the need for output-quality validation entirely—if the proof holds and the implementation is correct, the outputs are guaranteed correct.

Comparison to prior work: Prior acceleration methods fall into two categories regarding output preservation:

• Methods that change outputs and acknowledge it: Distillation (Hinton et al., 2015) produces a different model with different behavior; you evaluate it on benchmarks and accept some quality tradeoff. Quantization (Hubara et al., 2016) introduces numerical errors that can shift predictions. Early exit methods (Schuster et al., 2021) use heuristics to decide when to stop computing, losing the guarantee of full-model predictions. These methods all require empirical validation that the quality degradation is acceptable for the target use case.

• Methods that claim to preserve outputs but don't prove it: Blockwise Parallel Decoding (Stern et al., 2018) "focuses on preserving down-stream task quality, instead of guaranteeing identical outputs" (Section 5). The Wisdom of Committees (Schwartz et al., 2020) uses a heuristic to determine when the small model's output is "good enough" and stops there, again without a formal guarantee. These methods may work well in practice but leave open the possibility of rare failures where the accelerated system produces different (and potentially worse) outputs than the original model.

The paper's insistence on provable exact equivalence is what distinguishes it from both categories. The proof in Appendix A.1 is simple enough to verify by inspection, and the only assumption it makes is that $M_p$ and $M_q$ produce valid probability distributions—which they do by construction (softmax output). There's no hidden reliance on model calibration, no asymptotic approximation, no empirical validation needed.

Significance beyond raw performance: This design constraint has enormous practical consequences for adoption. When a production team considers deploying an inference acceleration method, they must weigh the speedup against the risk of output degradation. For applications where correctness matters—code generation, medical summarization, legal document analysis—even rare failures can be unacceptable. Speculative decoding's exact equivalence guarantee removes this risk entirely: the accelerated system is, from a statistical perspective, indistinguishable from the original. This means the method can be adopted without a quality evaluation pipeline, without A/B testing output quality, and without ongoing monitoring for regression. It's a pure engineering win: same outputs, less latency.

The constraint also forces a specific architectural decomposition that clarifies the problem structure. By requiring exact equivalence, the paper separates the acceleration mechanism (speculative execution of $M_q$'s guesses) from the statistical correctness mechanism (the acceptance/rejection procedure with corrected resampling). This separation means you can swap in any $M_q$—a smaller Transformer, an n-gram model, a heuristic copier, even a random token generator—and the outputs are guaranteed unchanged. The only thing that varies is the speedup. This is a powerful modularity that prior approaches didn't achieve.

Evidence: The paper empirically verifies the distributional equivalence by noting that the outputs are "identical" to those from the target model alone (Section 4.1: "without any change to the outputs"). More concretely, the theoretical predictions of speedup based on $\alpha$ match the empirical measurements (Table 4), which would not happen if the method were silently altering the output distribution in ways that changed the acceptance rate.

Fundamental vs. incremental: This is a fundamental reframing. The field's default assumption had been that inference acceleration necessarily involves a quality tradeoff. The paper demonstrates that, at least for the regime where spare compute is available, this tradeoff is not inherent—you can have both speedup and exact equivalence, bounded only by how well a cheap model approximates the expensive one's per-token distribution.

---

Innovation 3: The Acceptance Rate as an Interpretable, Measurable Quantity ($\alpha = 1 - \text{DLK}(p, q)$)

What makes this distinctive at the idea level: Rather than treating the relationship between the target model $M_p$ and the approximation model $M_q$ as a black-box similarity to be discovered empirically through end-to-end speedup measurements, the paper derives a clean, interpretable formula: $\alpha = \mathbb{E}[\sum_x \min(p(x), q(x))] = 1 - \mathbb{E}[\text{DLK}(p, q)]$, where $\text{DLK}$ is a newly introduced symmetric divergence measure. This formula lets practitioners predict speedup before implementation by simply evaluating the two models' output distributions on a representative corpus of prefixes and computing the expected overlap.

This is a diagnostic contribution, not a performance contribution. The formula doesn't make speculative decoding faster—it makes it analyzable. Before this work, if someone asked "how much speedup will I get if I use model X to accelerate model Y on task Z?", the answer would require implementing the full speculative decoding system and measuring walltime. Now, the answer can be estimated by computing $\alpha$ from the models' distributions, which requires only inference (no training, no implementation of the acceptance logic). The formula decomposes speedup into two factors: (1) a model-intrinsic property ($\alpha$, measuring how well $M_q$ matches $M_p$), and (2) a hardware/implementation property ($c$, the relative cost of running $M_q$), which are cleanly separated in Theorem 3.8.

Comparison to prior work: Prior approaches to measuring model similarity for acceleration purposes were ad hoc and task-specific. Distillation approaches might measure the KL divergence between teacher and student logits as a training loss, but they didn't provide a formula connecting that divergence to expected inference speedup. Early exit methods trained confidence estimators whose relationship to speedup was complex and architecture-dependent. The field lacked a simple, general-purpose diagnostic for how "acceleratable" a given pair of models is.

The $\text{DLK}$ divergence itself is an interesting contribution to the space of distributional distance measures. Unlike KL divergence, it's symmetric and bounded in $[0, 1]$. Unlike total variation distance, it has a direct operational meaning: $1 - \text{DLK}(p, q)$ is exactly the expected acceptance rate of speculative sampling. The paper introduces it not as an abstract mathematical object but as a quantity that emerges naturally from the algorithm's mechanics—it's the right divergence for this specific problem, discovered rather than imposed.

Significance beyond raw performance: The $\alpha$ formula enables model selection without implementation. A practitioner considering speculative decoding can evaluate multiple candidate $M_q$ models by measuring their $\alpha$ values and $c$ costs, then plug into Theorem 3.8 to predict which will give the best speedup, all without writing a line of speculative decoding code. This dramatically lowers the barrier to adoption: you can determine whether speculative decoding is worth implementing for your specific model and task before investing engineering effort.

The formula also provides debugging insight into why speedup is or isn't working. If measured speedup is lower than predicted, you know something is wrong with the implementation (e.g., the $\gamma+1$ evaluations aren't truly parallel, or $c$ was misestimated). If $\alpha$ is low, you know the approximation model is a poor match and should consider a different $M_q$ rather than tuning $\gamma$ or other hyperparameters. This diagnostic clarity is valuable in production settings where inference performance issues can be opaque.

Table 3, which reports $\alpha$ values across a wide range of model pairs and tasks, serves as a lookup table for practitioners: if you're using a large Transformer on a similar task, you can expect $\alpha$ in the 0.5–0.9 range for an approximation model ~100× smaller, and you can use the n-gram baselines ($\alpha \approx 0.03$–$0.23$) to calibrate expectations for extremely cheap approximations.

Evidence: The $\alpha$ values in Table 3 are empirically measured on 10K tokens generated by $M_p$ using the formula from Corollary 3.6. The walltime predictions based on these $\alpha$ values closely match the empirically measured speedups (Table 4), confirming that the formula is not just theoretically elegant but practically accurate. For example, T5-small on EnDe at temp=0 has $\alpha = 0.75$ and $c = 0.02$, predicting a 3.2× speedup at $\gamma=7$, versus 3.4× measured—well within the variance expected from the i.i.d. approximation.

Fundamental vs. incremental: This is a fundamental diagnostic contribution. It transforms speculative decoding from a "try it and see" empirical technique into an analyzable system with predictable performance. The $\text{DLK}$ divergence may have broader applications beyond this specific algorithm, wherever the expected overlap between two distributions determines the efficiency of a sampling procedure.

---

Innovation 4: Trading Total Compute for Reduced Latency as a Viable Acceleration Strategy

What makes this distinctive at the idea level: The paper explicitly embraces a tradeoff that most prior work on inference acceleration tried to avoid: increasing total arithmetic operations in exchange for reducing wall-clock time. Standard efficiency methods (distillation, quantization, sparsification) aim to reduce both latency and total compute—they make the model cheaper to run. Adaptive computation methods (early exits, dynamic depth) also reduce total compute by allocating it selectively. Speculative decoding is the first method to say: we will do more total work (more FLOPs, more memory for batching, more model evaluations), but we will do it in parallel so that the wall-clock time decreases.

This is not a minor engineering detail—it's a fundamentally different design philosophy that recognizes an empirical reality of modern hardware: large Transformer inference is often memory-bandwidth-bound, not compute-bound. The arithmetic units sit idle waiting for weights and KV-cache entries to be read from memory. By batching $\gamma+1$ evaluations of $M_p$, speculative decoding amortizes the weight reads across multiple sequences simultaneously, converting spare compute capacity into latency reduction. The memory accesses decrease (weights read once per iteration instead of once per token), while arithmetic operations increase (more total forward passes, some of which are wasted on rejected guesses). In a compute-bound regime, this tradeoff would be nonsensical; in a memory-bandwidth-bound regime, it's the key insight that makes the whole approach viable.

Comparison to prior work: Prior works on speculative execution for neural decoding (Stern et al., 2018; Sun et al., 2021) did not explicitly analyze or justify this tradeoff—they simply observed that parallel execution of multiple guesses reduced latency. The paper provides a quantitative framework (Theorems 3.8 and 3.11, Table 1, Figure 4) that makes the tradeoff explicit and lets practitioners assess whether their hardware configuration falls in the beneficial regime. The condition $\alpha > c$ (Corollary 3.9) cleanly separates when the tradeoff is favorable from when it's not: if the approximation model is too expensive relative to how well it matches the target, the extra compute isn't worth it.

The paper also provides an asymptotic bound that contextualizes the compute overhead: even in the worst case, the total arithmetic operations of speculative decoding (excluding $M_q$ runs) are bounded by a single run of a same-size Transformer encoder. Since an encoder processes all positions in parallel anyway, this means speculative decoding is never more than ~2× the operations of standard decoding for models of comparable architecture, which is acceptable in most deployment scenarios.

Significance beyond raw performance: This innovation legitimizes a previously underexplored region of the design space for inference acceleration. Before this paper, the implicit assumption was that reducing latency meant reducing compute. The paper shows that, under common hardware conditions, you can increase compute and decrease latency simultaneously by exploiting parallelism. This opens the door to other methods that might similarly trade compute for concurrency—for instance, ensemble methods that run multiple cheap models in parallel and vote, or tree-search methods that explore multiple decoding paths concurrently and select the best one.

The paper is careful to acknowledge the limitation: "our method is not helpful for configurations where additional computation resources are not available" (Section 6). This is not a weakness but a precise characterization of the method's applicability. In edge deployments where every FLOP counts, speculative decoding is indeed not the right choice. But in cloud or datacenter deployments where TPUs/GPUs have substantial idle arithmetic capacity due to memory bottlenecks, it's an effective strategy.

Evidence: Table 1 and Figure 4 quantify the tradeoff across a range of $\alpha$ and $\gamma$ values. For $\alpha = 0.8$ and $\gamma = 5$, the speedup is 3.69× while operations increase by only 1.63×—a strongly favorable tradeoff. For $\alpha = 0.6$ and $\gamma = 2$, the speedup is 1.96× with a 1.53× operations increase—more modest but still net positive. The empirical walltime measurements in Table 2 confirm that the theoretical tradeoff translates to actual latency reduction on TPU-v4 hardware, with speedups of 2×–3× across tasks and approximation models.

Fundamental vs. incremental: This is a fundamental reframing of the inference acceleration problem. It challenges the field's default assumption that "more efficient" means "less total work" and replaces it with a more nuanced understanding: efficiency can mean "less wall-clock time" even when total work increases, as long as the extra work can be parallelized on underutilized hardware. This reframing has implications beyond speculative decoding and may influence the design of future inference acceleration techniques.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper evaluates on two primary tasks from the T5 paper (Raffel et al., 2020) using the standard T5 version 1.1 model: (1) English-to-German translation fine-tuned on WMT EnDe, and (2) text summarization fine-tuned on CNN/DailyMail (CNNDM). For additional tasks, the paper measures acceptance rates on: unconditional language generation using a 97M-parameter GPT-like model trained on the One Billion Word Benchmark (lm1b; Chelba et al., 2013), and a dialog task using the LaMDA model (Thoppilan et al., 2022). The acceptance rate measurements (Table 3) are computed on 10K tokens generated by the target model $M_p$ for each setting. No further detail is provided about the exact test splits, evaluation protocol, or preprocessing for any of these datasets.

• Base model(s). The walltime improvement experiments use T5-XXL (11B parameters) as the target model $M_p$ (Raffel et al., 2020), a standard encoder-decoder Transformer. For approximation models $M_q$, the paper tests three existing off-the-shelf T5 configurations: T5-large (800M), T5-base (250M), and T5-small (77M). The acceptance-rate experiments (Section 4.2, Table 3) additionally evaluate: a 97M-parameter GPT-like Transformer decoder (12 layers, dim 768, dim feed-forward 3072, 12 attention heads, Gelu activations) with a 6M-parameter approximation model (2 layers, dim 256, dim feed-forward 1024, 4 attention heads), both trained on lm1b with 8k-token BERT tokenization; and LaMDA 137B as $M_p$ with LaMDA 8B, LaMDA 2B, and LaMDA 100M as approximation models. The model scale range spans approximately three orders of magnitude for the approximation models (77M to 8B) and two target scales (11B and 137B).

• Metrics. Two primary metrics are reported:

  1. Walltime improvement factor: The ratio of wall-clock time per generated token for standard autoregressive decoding to that of speculative decoding, measured on a single TPU-v4 with batch size 1. This is an empirical, end-to-end latency measurement comparing the paper's implementation against the T5X production serving framework (Roberts et al., 2022).
  2. Acceptance rate $\alpha$: Defined by Corollary 3.6 as $\alpha = \mathbb{E}[\sum_x \min(p(x), q(x))] = 1 - \mathbb{E}[\text{DLK}(p, q)]$, computed empirically by evaluating both models' full output distributions on 10K tokens generated by $M_p$ and averaging the $\min$ overlap. This is a model-intrinsic diagnostic that predicts speedup without requiring a full speculative decoding implementation.

  The paper also reports the cost coefficient $c$ (ratio of $M_q$ walltime to $M_p$ walltime, estimated from profiler traces) and the number of guesses $\gamma$ used in each configuration.

• Baselines. The primary baseline is standard autoregressive decoding from the target model $M_p$ using the T5X implementation (Roberts et al., 2022)—the production-grade serving framework for T5 models. This is the strongest available baseline for the T5 architecture family. There is no comparison to other inference acceleration methods (e.g., distillation, quantization, early exits, Blockwise Parallel Decoding) because the paper's goal is to demonstrate acceleration over the default decoding method, not to compete with alternative acceleration techniques. The paper explicitly positions speculative decoding as complementary to other methods (Section 5: "these methods and our speculative decoding method might be effective in tandem"), so the omission of head-to-head comparisons with other acceleration methods is consistent with this framing, though it leaves open the question of how the speedups compare to what could be achieved by, say, simply using a distilled model.

• Generation budget / compute accounting. The unit of computation is wall-clock time per token for latency measurements, and model forward passes for theoretical analysis. The paper does not use a FLOPs or token-generation budget in the traditional sense because speculative decoding does not alter the number of output tokens—it changes how many serial $M_p$ calls are required to produce them. The key accounting is: each iteration of Algorithm 1 costs $\gamma$ runs of $M_q$ (sequential) plus one parallel batch of $\gamma+1$ runs of $M_p$, and produces between 1 and $\gamma+1$ tokens. The theoretical analysis in Section 3 tracks both walltime (Theorem 3.8) and total arithmetic operations (Theorem 3.11) as functions of $\alpha$, $\gamma$, $c$, and $\hat{c}$. All walltime measurements use batch size 1 on a single TPU-v4, with no specification of TPU memory capacity or whether the $\gamma+1$ evaluations of $M_p$ fit within the available memory for the tested $\gamma$ values (which are modest: 3–7 for Transformer-based $M_q$).

• Cross-validation / statistical protocol. The paper does not employ cross-validation or statistical significance testing. The walltime measurements are point estimates from a single hardware configuration (one TPU-v4, batch size 1), with no reported variance across multiple runs, different random seeds, or different hardware instances. The $\alpha$ values in Table 3 are averaged over 10K tokens generated by $M_p$, which provides a statistically stable estimate of the expected acceptance rate, but no confidence intervals or standard deviations are reported. The theoretical predictions in Table 4 are compared to single empirical measurements with no formal goodness-of-fit assessment. This is typical for systems papers reporting walltime improvements, but it means the reported speedups (e.g., 3.4× for T5-small on EnDe at temp=0) should be understood as measurements from a specific hardware/software configuration rather than as guaranteed improvements across all deployment environments.

---

Main Quantitative Results

Walltime Improvement on T5-XXL (Section 4.1, Table 2)

The headline empirical finding is a 2×–3× walltime speedup over the T5X baseline across two tasks, three approximation model sizes, and two sampling methods (temperature = 0 for argmax, temperature = 1 for standard sampling).

English-to-German translation (WMT EnDe):

• T5-small (77M) achieves the best speedup: 3.4× at temperature = 0 with $\gamma = 7$ and $\alpha = 0.75$, and 2.6× at temperature = 1 with $\gamma = 7$ and $\alpha = 0.62$.
• T5-base (250M): 2.8× at temperature = 0 ($\gamma = 7$, $\alpha = 0.80$), 2.4× at temperature = 1 ($\gamma = 5$, $\alpha = 0.68$).
• T5-large (800M): 1.7× at temperature = 0 ($\gamma = 7$, $\alpha = 0.82$), 1.4× at temperature = 1 ($\gamma = 3$, $\alpha = 0.71$).

News summarization (CNN/DailyMail):

• T5-small: 3.1× at temperature = 0 ($\gamma = 5$, $\alpha = 0.65$), 2.3× at temperature = 1 ($\gamma = 5$, $\alpha = 0.53$).
• T5-base: 3.0× at temperature = 0 ($\gamma = 5$, $\alpha = 0.73$), 2.2× at temperature = 1 ($\gamma = 3$, $\alpha = 0.55$).
• T5-large: 2.2× at temperature = 0 ($\gamma = 3$, $\alpha = 0.74$), 1.7× at temperature = 1 ($\gamma = 3$, $\alpha = 0.56$).

Key patterns in Table 2:

1. Smaller approximation models yield higher speedups despite lower $\alpha$. T5-small ($\alpha = 0.75$) achieves 3.4× while T5-large ($\alpha = 0.82$) achieves only 1.7× on EnDe at temp=0. This is the crucial empirical validation of Theorem 3.8's prediction that $c$ (the relative cost of $M_q$) can dominate $\alpha$ in determining net speedup. T5-large's higher $\alpha$ is outweighed by its higher $c$ (0.11 vs. 0.02 per Table 4). This is a non-obvious result: one might naively expect the best approximation model to be the largest one available, but the speedup formula reveals a sweet spot around two orders of magnitude smaller than the target.

2. Temperature = 0 yields higher speedups than temperature = 1 across all configurations. For T5-small on EnDe, the drop is from 3.4× to 2.6×; on CNNDM, from 3.1× to 2.3×. This follows from the acceptance rate behavior: the sharper the distribution (lower temperature), the higher the overlap between $p$ and $q$, because both models concentrate probability mass on fewer tokens. Table 3 confirms this pattern: $\alpha$ values are consistently higher at temperature = 0 than at temperature = 1 (e.g., T5-small EnDe: 0.75 vs. 0.62; LaMDA 100M: 0.61 vs. 0.57).

3. Summarization shows slightly lower speedups than translation for comparable configurations, despite similar $\alpha$ values. For T5-base at temp=0: 2.8× on EnDe ($\alpha = 0.80$) vs. 3.0× on CNNDM ($\alpha = 0.73$). The relationship between $\alpha$ and speedup is not monotonic across tasks, reflecting differences in the $\beta$ distribution (the i.i.d. assumption is only approximate) and implementation-level factors.

Matching Theoretical Predictions to Empirical Measurements (Table 4)

Table 4 compares the expected speedup from Theorem 3.8 (using measured $\alpha$ and $c$ values) to the empirical speedup from Table 2. The theoretical predictions mostly match the empirical measurements, with larger discrepancies attributed to (1) optimization differences between the paper's implementation and the T5X baseline, and (2) the simplifying i.i.d. assumption on $\beta$.

Key comparisons:

• T5-small on EnDe at temp=0: predicted 3.2×, empirical 3.4× (overprediction by ~6%). The implementation is slightly faster than the formula predicts, possibly because the baseline T5X has overhead not present in the paper's implementation, or because $c$ was slightly overestimated.
• T5-large on EnDe at temp=0: predicted 2.5×, empirical 1.7× (overprediction by ~47%). This is the largest discrepancy. The paper attributes this to the i.i.d. approximation breaking down for larger $M_q$ models and optimization differences.
• T5-base on CNNDM at temp=0: predicted 2.6×, empirical 3.0× (underprediction by ~15%).
• T5-small on CNNDM at temp=1: predicted 1.9×, empirical 2.3× (underprediction by ~21%).

The formula works best when $\alpha$ is high and $c$ is low (T5-small), and worst when $c$ is high (T5-large). For T5-large, the cost of running $M_q$ begins to dominate, and small errors in estimating $c$ or in the i.i.d. assumption have outsized effects on the speedup prediction.

Empirical Acceptance Rates Across Model Families and Tasks (Section 4.2, Table 3)

Table 3 reports $\alpha$ values for 32 configurations spanning three target model families (GPT-like 97M, T5-XXL 11B, LaMDA 137B), multiple approximation models, and two sampling methods (temperature = 0 and 1).

GPT-like (97M $M_p$, lm1b unconditional generation):

• Unigram $M_q$: $\alpha = 0.03$ (both temperatures)
• Bigram $M_q$: $\alpha = 0.05$ (both temperatures)
• GPT-like 6M $M_q$: $\alpha = 0.88$ (temp=0), $\alpha = 0.89$ (temp=1)

The near-identical $\alpha$ values across temperatures for the 6M model are notable—unlike T5-XXL, this model's distributional overlap with $M_p$ is nearly invariant to temperature, suggesting the approximation model has learned a distribution similar to the target's sharpness profile.

T5-XXL (11B $M_p$, EnDe translation):

• Unigram: $\alpha = 0.08$ (temp=0), $\alpha = 0.07$ (temp=1)
• Bigram: $\alpha = 0.20$ (temp=0), $\alpha = 0.19$ (temp=1)
• T5-small (77M): $\alpha = 0.75$ (temp=0), $\alpha = 0.62$ (temp=1)
• T5-base (250M): $\alpha = 0.80$ (temp=0), $\alpha = 0.68$ (temp=1)
• T5-large (800M): $\alpha = 0.82$ (temp=0), $\alpha = 0.71$ (temp=1)

T5-XXL (11B $M_p$, CNNDM summarization):

• Unigram: $\alpha = 0.13$ (temp=0), $\alpha = 0.08$ (temp=1)
• Bigram: $\alpha = 0.23$ (temp=0), $\alpha = 0.16$ (temp=1)
• T5-small: $\alpha = 0.65$ (temp=0), $\alpha = 0.53$ (temp=1)
• T5-base: $\alpha = 0.73$ (temp=0), $\alpha = 0.55$ (temp=1)
• T5-large: $\alpha = 0.74$ (temp=0), $\alpha = 0.56$ (temp=1)

LaMDA (137B $M_p$, dialog):

• LaMDA 100M: $\alpha = 0.61$ (temp=0), $\alpha = 0.57$ (temp=1)
• LaMDA 2B: $\alpha = 0.71$ (temp=0), $\alpha = 0.71$ (temp=1)
• LaMDA 8B: $\alpha = 0.75$ (temp=0), $\alpha = 0.74$ (temp=1)

Key takeaways from Table 3:

1. Approximation models ~100× smaller than the target consistently achieve $\alpha$ in the 0.5–0.9 range. This is an empirical regularity that suggests speculative decoding will be broadly applicable: for typical large Transformer models, a smaller model from the same family will share enough of the output distribution to provide meaningful acceleration.

2. Even trivial n-gram models yield non-negligible $\alpha$ values. The bigram model on EnDe gives $\alpha = 0.20$ at temp=0, which translates to a 1.25× speedup at $\gamma = 3$ with $c \approx 0$. This is "surprisingly high" (Section 4.2) for a model that is just a table lookup—it suggests that even extremely cheap approximations can provide some acceleration.

3. $\alpha$ increases with approximation model size but with diminishing returns. Going from T5-small (77M) to T5-base (250M) on EnDe at temp=0 increases $\alpha$ from 0.75 to 0.80 (+0.05), but going from T5-base to T5-large (800M) increases $\alpha$ from 0.80 to 0.82 (+0.02) at the cost of a much higher $c$. This explains why T5-small is the optimal choice despite not having the highest $\alpha$.

4. Temperature dependence of $\alpha$ is model-dependent. For T5-based models, the temp=0 vs. temp=1 gap is substantial (e.g., 0.75 vs. 0.62 for T5-small EnDe). For LaMDA and the 6M GPT-like model, the gap is minimal or zero. The paper doesn't explain this difference, but it likely reflects differences in how the models were trained (e.g., with or without label smoothing, which flattens the distribution at training time and reduces the temperature sensitivity at inference).

Theoretical Speedup vs. Operations Tradeoff (Table 1, Figure 4)

Table 1 and Figure 4 quantify the tradeoff between inference speedup and total arithmetic operations for various ($\alpha$, $\gamma$) pairs, assuming $c = \hat{c} = 0$ (negligible-cost approximation model). Key data points:

• $\alpha = 0.6$, $\gamma = 2$: 1.96× speed, 1.53× operations
• $\alpha = 0.7$, $\gamma = 3$: 2.53× speed, 1.58× operations
• $\alpha = 0.8$, $\gamma = 2$: 2.44× speed, 1.23× operations
• $\alpha = 0.8$, $\gamma = 5$: 3.69× speed, 1.63× operations
• $\alpha = 0.9$, $\gamma = 2$: 2.71× speed, 1.11× operations
• $\alpha = 0.9$, $\gamma = 10$: 6.86× speed, 1.60× operations

The pattern is clear: higher $\alpha$ enables both higher speed and lower operations overhead, because more guesses are accepted (wasting less computation on rejected prefixes) and more tokens are produced per $M_p$ call (amortizing the fixed cost of running $M_p$). At $\alpha = 0.9$, one can achieve 6.86× speedup for only 1.60× operations—a highly favorable tradeoff that suggests speculative decoding could scale to very large speedups if sufficiently accurate approximation models are available.

---

Ablation Studies and Robustness Checks

The paper does not report traditional ablation studies in the sense of systematically removing components of the method and measuring the impact. Instead, Table 2 and Table 3 together serve as an implicit ablation across the two primary axes of variation: approximation model size (T5-small vs. T5-base vs. T5-large, LaMDA 100M vs. 2B vs. 8B, n-gram vs. Transformer) and sampling method (temperature = 0 vs. temperature = 1). The following findings emerge:

• Approximation model size (Table 2, Table 3): Increasing $M_q$ size consistently increases $\alpha$ but does not consistently increase speedup. On EnDe at temp=0, speedup decreases from 3.4× (T5-small) to 2.8× (T5-base) to 1.7× (T5-large) despite $\alpha$ increasing from 0.75 to 0.80 to 0.82. This is the paper's most important empirical lesson: bigger approximation models are not better because $c$ grows faster than the incremental $\alpha$ gains. The sweet spot is approximately two orders of magnitude smaller than the target model, at least for the T5 family.

• Sampling method (all tables): Moving from temperature = 0 to temperature = 1 consistently reduces both $\alpha$ and speedup, but the reduction is moderate rather than catastrophic. T5-small on EnDe drops from 3.4× to 2.6× (a 24% reduction in speedup for a 17% reduction in $\alpha$). This validates the paper's claim that speculative decoding works for stochastic sampling, not just greedy—but it also reveals that stochastic sampling is inherently harder to accelerate because broader distributions have less overlap.

• Negligible-cost approximations (Table 3, Section 4.2): The bigram model achieves $\alpha = 0.20$ on EnDe (temp=0), which translates to a 1.25× speedup at $\gamma = 3$. This establishes a lower bound on achievable speedup: even without any neural approximation model, a simple statistical model can provide non-trivial acceleration. The unigram model achieves $\alpha = 0.08$, which yields minimal speedup (~1.09× at $\gamma = 3$) but is still technically positive.

• Theoretical prediction accuracy (Table 4): Comparing expected vs. empirical speedup across 12 configurations shows that Theorem 3.8 predicts speedup within ~20% for configurations where $c$ is low (T5-small, T5-base), but accuracy degrades substantially for T5-large where $c = 0.11$. This is effectively an ablation of the i.i.d. assumption: when $c$ is small, errors in the $\beta$ independence assumption have minor impact because the formula is dominated by $\alpha$ and $\gamma$; when $c$ is large, small misestimations of either $c$ or $\alpha$ propagate more aggressively.

Cross-task generalization: The method generalizes from translation (EnDe) to summarization (CNNDM) with similar speedups (3.4× vs. 3.1× for T5-small at temp=0), confirming that the approach is not task-specific. However, the paper tests only two tasks on T5-XXL and one on LaMDA (dialog), plus one on the GPT-like model (unconditional generation). This is a limited task diversity compared to the range of applications where autoregressive models are deployed.

No lenience ablation in main results: Appendix A.5 explores introducing a "lenience" parameter $l \in [0,1]$ that multiplies $q(x)$ before comparing with $p(x)$, allowing some deviation from exact distributional equivalence in exchange for higher acceptance rates. With $l = 0.1$ (meaning no token can be sampled with probability greater than 10× its ground-truth probability), $\alpha$ for T5-small on EnDe increases from 0.62 to 0.84, enabling a 5× speedup. This is presented as an optional extension rather than a main result, and the paper emphasizes that all primary experiments use $l = 1$ (strict equivalence).

---

Critical Assessment

Do the Experiments Support the Central Claims?

Claim 1: Speculative decoding achieves 2×–3× walltime speedup over standard decoding with no output changes.

This claim is directly supported by the empirical walltime measurements in Table 2, which show speedups ranging from 1.4× (T5-large, EnDe, temp=1) to 3.4× (T5-small, EnDe, temp=0). All 12 configurations achieve non-trivial speedup over the T5X baseline.

However, several qualifications narrow the scope of this claim more than the paper's abstract and introduction suggest:

• The claim is validated on exactly one hardware configuration (single TPU-v4, batch size 1). The paper provides no measurements on GPUs, on multi-TPU configurations, on different batch sizes, or on different TPU generations. The speedup magnitude is hardware-dependent because it depends on the relative cost $c$ of running $M_q$ versus $M_p$, which varies across hardware architectures. A configuration where $M_p$ is less memory-bandwidth-bound (e.g., a GPU with high memory bandwidth relative to compute) might show smaller speedups.

• The claim is validated on exactly one model architecture (encoder-decoder T5) for walltime measurements. While Table 3 reports acceptance rates for GPT-like decoder-only and LaMDA models, no walltime measurements are reported for these architectures. The paper does not demonstrate that the theoretical speedup predictions (which match for T5) actually materialize as walltime improvements on decoder-only models.

• The "no output changes" guarantee is proven mathematically (Appendix A.1) but is not empirically validated through distributional comparisons. The paper does not, for example, generate 10K outputs with and without speculative decoding and verify that the token distributions match within sampling error. The guarantee rests entirely on the proof, which is correct given the algorithm as specified, but implementational bugs (e.g., incorrect standardization of sampling methods, numerical issues in the acceptance probability computation) could violate the guarantee in practice.

• The batch size 1 configuration is favorable to speculative decoding because it maximizes the ratio of idle compute to memory bandwidth. At larger batch sizes, the target model's forward pass becomes more compute-bound (amortizing weight reads across more sequences), which reduces the relative benefit of batching $\gamma+1$ evaluations. The paper does not explore how speedup scales with batch size, which is a critical practical consideration for serving systems that use dynamic batching.

Claim 2: The method works with off-the-shelf models without retraining or architecture changes.

This claim is supported by the experimental design: all models used are existing checkpoints (T5 version 1.1, LaMDA, GPT-like), and the method requires no fine-tuning, distillation, or architectural modification. The paper demonstrates this by simply loading existing checkpoints and measuring speedup.

However, there is a subtle dependency that the paper downplays: the method requires that $M_q$ use the same tokenizer as $M_p$, produce distributions over the same vocabulary, and apply the same sampling standardization. This is satisfied when using models from the same family (T5-small, T5-base, T5-large all use the same SentencePiece tokenizer), but it is not universally true—a random off-the-shelf smaller model might use a different tokenizer, different vocabulary, or different output format, which would require adaptation before it could serve as $M_q$. The claim of "off-the-shelf" compatibility is true within model families but may not be true across model families.

Claim 3: The acceptance rate $\alpha = 1 - \mathbb{E}[\text{DLK}(p, q)]$ accurately predicts speedup.

This claim is partially supported. Table 4 shows that theoretical predictions match empirical measurements within ~20% for configurations with low $c$ (T5-small, T5-base), but the discrepancy grows to ~47% for T5-large on EnDe at temp=0 (predicted 2.5× vs. empirical 1.7×). The paper attributes this to the i.i.d. assumption on $\beta$ breaking down, but it does not investigate how the assumption breaks down or provide a more refined model. The formula is useful for rough estimation and model selection, but it should not be treated as a precise predictor for production deployment—the actual speedup may differ enough to change the decision of which $M_q$ to use.

Moreover, the $\alpha$ values in Table 3 are measured on 10K tokens generated by $M_p$. This means they are measured on the target model's own output distribution, which is subtly different from the distribution of prefixes that speculative decoding actually encounters during operation—those prefixes include tokens accepted from $M_q$, which may have a slightly different distribution (even though the marginal distribution is preserved, the joint distribution of prefixes may differ between standard decoding and speculative decoding because the latter produces tokens in batches). This could cause a small distributional mismatch between the $\alpha$ used for prediction and the effective $\alpha$ during operation.

Claim 4: Even trivial approximation models (n-grams) yield non-trivial speedup.

This claim is supported in principle but not empirically validated with walltime measurements. Table 3 shows $\alpha = 0.20$ for a bigram model on EnDe, and the paper states this yields a 1.25× speedup at $\gamma = 3$, but no actual walltime measurement is reported for n-gram approximation models—the claim is purely theoretical, based on plugging $\alpha$ into Theorem 3.8 with $c \approx 0$. Given that the theoretical formula has discrepancies of up to ~47% for Transformer-based $M_q$, it's unclear whether the 1.25× figure would materialize in practice.

Genuine Weaknesses in the Experimental Design

1. Single hardware platform, single batch size. The entire empirical case for speculative decoding's practical utility rests on measurements from one TPU-v4 at batch size 1. This is the most favorable possible configuration for the method. In production serving, batch sizes are often larger (for throughput) or dynamic (for latency-throughput tradeoffs). The paper provides no evidence that speedups persist under realistic serving conditions.

2. No comparison to alternative acceleration methods. The paper compares against standard decoding but not against distillation, quantization, or other acceleration techniques. A practitioner choosing an inference acceleration strategy needs to know not just "is speculative decoding faster than standard decoding?" but "is it faster than using a distilled model that doesn't require running two models simultaneously?" The paper's claim that speculative decoding is "complementary" to other methods is plausible but unsubstantiated—it does not demonstrate that the combination actually works or that speculative decoding provides benefits beyond what simpler methods achieve.

3. Walltime measurements are point estimates with no variance information. The paper reports single speedup numbers (e.g., 3.4×) with no confidence intervals, no standard deviations, and no indication of how many runs were averaged. TPU performance can vary due to thermal throttling, memory allocation, and other factors. Without variance estimates, it's impossible to assess whether the differences between configurations (e.g., 3.4× vs. 2.8× for T5-small vs. T5-base) are statistically meaningful or within noise.

4. The $\gamma$ values are tuned per configuration but the tuning methodology is opaque. Table 2 reports different $\gamma$ values for different configurations (ranging from 3 to 7), but the paper does not describe how these were selected. Section 3.5 describes the theoretical method for choosing $\gamma$ (maximizing the improvement factor given $\alpha$ and $c$), but Table 4 shows that the theoretical predictions don't always match empirical measurements, leaving unclear whether the $\gamma$ values in Table 2 were chosen by formula, by grid search, or by manual tuning. This matters for reproducibility and for practitioners who need to set $\gamma$ for their own models.

5. No analysis of memory overhead. Speculative decoding requires holding $\gamma+1$ sequences in memory simultaneously (for the parallel $M_p$ evaluation), plus the KV-cache for multiple prefixes. For large target models with long context lengths, this memory overhead could be substantial and might limit the maximum practical $\gamma$, especially on resource-constrained hardware. The paper mentions memory only in passing (Section 3.4: "the target model's weights and KV cache can be read once per execution") without quantifying the memory requirements or discussing whether memory constraints ever limit $\gamma$ in practice.

6. Limited task diversity. The walltime experiments cover only two tasks (translation and summarization), both of which are relatively constrained generation tasks with predictable output structures. Tasks with more open-ended generation (creative writing, long-form QA, code generation) might exhibit different acceptance rate patterns—for example, tokens that are highly unpredictable might see lower $\alpha$ values and thus lower speedup. The paper provides no evidence on this.

7. The theoretical analysis assumes $\gamma+1$ evaluations of $M_p$ can be done in parallel with no overhead, but in practice, batching incurs some overhead (memory allocation, padding, masking). The empirical walltime measurements absorb this overhead (it's included in the measured time), but the theoretical speedup formula does not account for it, which contributes to the prediction errors in Table 4.

8. No ablation on the effect of $\gamma$ on measured speedup. While Table 2 reports different $\gamma$ values per configuration, the paper does not show a sweep of $\gamma$ values with empirical walltime measurements for a fixed ($M_p$, $M_q$) pair. This means the reader cannot assess whether the reported speedups are near-optimal or whether further tuning could yield additional gains. Figure 2 shows theoretical curves, but there is no empirical analog.

Missing Experiments That Would Have Strengthened the Paper

• Walltime scaling with batch size: How does speedup change at batch sizes of 4, 8, 32? This would reveal the boundary between memory-bandwidth-bound and compute-bound regimes.

• Walltime measurements for decoder-only models (GPT-like, LaMDA): The paper reports $\alpha$ values for these models (Table 3) but no walltime speedups. Demonstrating that theoretical predictions based on $\alpha$ translate to actual walltime improvements on decoder-only architectures would substantially strengthen the generalizability claim.

• Walltime measurements for n-gram approximation models: The claim that bigram models achieve 1.25× speedup is purely theoretical. An empirical walltime measurement would validate whether the theoretical formula holds for $c \approx 0$.

• Head-to-head comparison with distillation: Train a distilled T5-small model (using standard knowledge distillation from T5-XXL), measure its accuracy on EnDe and CNNDM, and compare the speedup vs. quality tradeoff against speculative decoding with T5-small. This would directly address the question: is speculative decoding better than just using the approximation model directly?

• Measurement variance across multiple runs and hardware instances: Report mean and standard deviation of speedup across at least 5 independent measurements, ideally on different physical TPU-v4 chips, to give readers a sense of reproducibility.

• Analysis of where accepted vs. rejected guesses occur: The paper reports aggregate $\alpha$ but doesn't analyze whether guesses are more likely to be accepted at certain positions (e.g., beginning of sequences, after punctuation, for function words vs. content words). Such an analysis could inform better approximation model design.

• Lenience experiments with walltime measurements: Appendix A.5 reports theoretical speedups for $l < 1$ but provides no empirical walltime measurements. Validating that lenience actually produces the predicted additional speedup would strengthen the case for using it as an optional relaxation when exact equivalence is not strictly required.

6. Limitations and Trade-offs

The Method Is Fundamentally Limited to Memory-Bandwidth-Bound Regimes

The assumption or constraint. Speculative decoding trades increased arithmetic operations for reduced walltime by executing multiple forward passes of $M_p$ in parallel. This tradeoff only reduces latency when the hardware has spare arithmetic capacity—that is, when inference is bottlenecked on memory bandwidth rather than compute throughput. The paper explicitly acknowledges this in Section 6:

"One limitation of speculative execution in general, and of speculative decoding in particular, is that latency is improved through increased concurrency at the cost of an increased number of arithmetic operations. Thus, our method is not helpful for configurations where additional computation resources are not available."

The assumption is baked into the theoretical analysis: Theorem 3.8 assumes that $\gamma+1$ parallel evaluations of $M_p$ can run with zero walltime overhead beyond a single evaluation, which is only true when the hardware has enough idle arithmetic units to absorb the extra work.

The consequence. In compute-bound regimes—which arise with large batch sizes, models that heavily utilize arithmetic units, or hardware with high compute-to-memory-bandwidth ratios—speculative decoding may provide little to no speedup, or could even be slower than standard decoding due to the overhead of running $M_q$ and managing the additional parallel evaluations. Since production serving systems often use dynamic batching to maximize throughput, the effective regime for a deployed model may shift between memory-bandwidth-bound and compute-bound depending on query load, making the speedup inconsistent in practice.

What evidence exists in the paper. All walltime measurements in Table 2 are taken at batch size 1 on a single TPU-v4—the configuration most likely to be memory-bandwidth-bound. The paper provides no measurements at larger batch sizes, no analysis of how speedup degrades as batch size increases, and no characterization of the TPU-v4's compute-to-memory-bandwidth ratio to help practitioners assess whether their hardware falls in the beneficial regime. The operations increase factor (Theorem 3.11, Table 1) quantifies the extra arithmetic cost (e.g., 1.63× more operations for 3.69× speedup at $\alpha = 0.8$, $\gamma = 5$), but this is presented as a tradeoff to be accepted, not as a condition that limits applicability.

Mitigation status. The paper acknowledges the limitation in Section 6 but does not attempt to characterize the boundary between beneficial and detrimental hardware configurations. There is no guidance on how to measure whether a given deployment is memory-bandwidth-bound, no model of the relationship between batch size and speedup, and no experiments exploring the transition. The framing is essentially: "this works when you have spare compute," without characterizing when that condition holds. The paper suggests (Section 5) that speculative decoding might be combined with methods that reduce arithmetic operations (quantization, sparsification) to shift hardware into the memory-bandwidth-bound regime, but no experiments validate this combination.

---

All Walltime Measurements Come from a Single Hardware Configuration

The assumption or constraint. The empirical case for speculative decoding's practical utility rests entirely on walltime measurements from one TPU-v4 chip running batch size 1 inference. Table 2 reports speedups of 2×–3×, and Table 4 compares these to theoretical predictions, but there is no evidence that the speedups generalize across hardware.

The consequence. The cost coefficient $c$ (the ratio of $M_q$ walltime to $M_p$ walltime) is hardware-dependent: it depends on the relative throughput of the arithmetic units, the memory bandwidth, the cache hierarchy, and the software stack's ability to batch the $\gamma+1$ parallel evaluations efficiently. On a different hardware platform—a GPU with different memory bandwidth, a CPU with different parallelism characteristics, a newer TPU generation with different compute-to-memory ratios—both $c$ and the effective parallelism available for batching $\gamma+1$ evaluations may differ substantially. The optimal $\gamma$ and the best choice of $M_q$ depend on $c$ (Figure 3), so results that hold on TPU-v4 may not transfer. The paper's claim of being "easy to employ in actual production settings" (Section 1) is undermined by the lack of evidence that the speedups materialize on the hardware that production teams actually use (NVIDIA GPUs dominate production LLM serving).

What evidence exists in the paper. The paper provides no multi-hardware evaluation. All walltime numbers (Tables 2 and 4) are from a single TPU-v4. The independent implementation by Chen et al. (2023) showing "similar 2X-2.5X improvements on Chinchilla 70B" is cited in Section 5, but the Chen et al. paper is not included or analyzed—its hardware configuration, batch size, and measurement methodology are unknown from this paper alone. The acceptance rate $\alpha$ (Table 3) is hardware-independent (it depends only on the models' output distributions), so it is portable, but the translation from $\alpha$ to actual walltime improvement depends on $c$ and on the hardware's ability to parallelize the $\gamma+1$ evaluations, which are not portable.

Mitigation status. The paper does not address this. There is no discussion of how speedup might vary across hardware, no ablation on batch size, and no guidance for practitioners on how to estimate whether their hardware configuration will yield similar speedups. The suggestion in Section 6 to explore "further investigating the compatibility of speculative decoding with beam search" and other extensions is orthogonal to the hardware generalization question. The independent replication citation provides some reassurance but is too thin a reed to support claims of broad applicability.

---

The Memory Overhead of Batching $\gamma+1$ Evaluations Is Not Quantified

The assumption or constraint. Algorithm 1 requires running $\gamma+1$ evaluations of $M_p$ in parallel, which means holding $\gamma+1$ input sequences, their KV-caches, and their intermediate activations in device memory simultaneously. For large target models with long context lengths, this memory footprint could be substantial. The paper mentions memory only in passing (Section 3.4):

"the target model's weights and KV cache can be read once per execution of Algorithm 1, so the number of memory accesses for reading them shrinks by a factor of $\frac{1 - \alpha^{\gamma+1}}{1 - \alpha}$"

This analysis addresses memory bandwidth (fewer reads of weights) but not memory capacity (how much total memory is needed to hold $\gamma+1$ sequences).

The consequence. On memory-constrained hardware—edge devices, smaller GPUs, or configurations with long context lengths—the maximum practical $\gamma$ may be limited not by the optimality analysis of Section 3.5 but by available device memory. If $\gamma$ must be reduced to fit in memory, the achievable speedup may be substantially lower than the theoretical optimum. In extreme cases (very long sequences, very large models), even $\gamma = 1$ might exceed memory capacity, making speculative decoding infeasible regardless of theoretical speedup. This is particularly relevant for the largest models the paper studies: LaMDA 137B with long dialog contexts could easily exhaust device memory with even modest $\gamma$ values.

What evidence exists in the paper. None. The paper does not report memory usage for any configuration, does not discuss how memory scales with $\gamma$, and does not mention memory capacity as a constraint on $\gamma$ selection. The $\gamma$ values used in experiments are modest (3–7 for T5-XXL at batch size 1, long sequence lengths unspecified), which likely kept memory usage within the TPU-v4's capacity, but there is no evidence that larger $\gamma$ values (which would be optimal at higher $\alpha$) are achievable. The theoretical analysis in Figure 3 suggests optimal $\gamma$ values up to 24 for $\alpha = 0.9$ and $c = 0.01$, but the paper never tests whether such large $\gamma$ values are practically feasible.

Mitigation status. Not addressed. The paper does not mention memory capacity as a constraint, does not provide a memory model, and does not discuss how practitioners should determine the maximum feasible $\gamma$ for their hardware. The theoretical bound in Section 3.4—that total arithmetic operations of speculative decoding (excluding $M_q$) are bounded by a same-size Transformer encoder—is about arithmetic, not memory. An encoder processes all positions in parallel and has its own memory footprint, which is not compared to the decoder's speculative decoding footprint.

---

The Method Is Only Validated on a Narrow Set of Tasks and Model Architectures for Walltime

The assumption or constraint. The paper's headline empirical claim—2×–3× walltime speedup—is validated on exactly two tasks (English-to-German translation and CNN/DailyMail summarization) using one model architecture (encoder-decoder T5). While Table 3 reports acceptance rates ($\alpha$) for additional settings—a GPT-like decoder-only model on unconditional language generation and LaMDA on dialog—no walltime measurements exist for these settings. The paper implicitly assumes that $\alpha$ values measured on these models will translate to walltime speedups comparable to those observed on T5-XXL.

The consequence. The relationship between $\alpha$ and actual walltime speedup depends on implementation details that may differ across model architectures. Encoder-decoder models (T5) process the full input sequence in the encoder once, then decode autoregressively; decoder-only models (GPT-like, LaMDA) process the entire prefix at every step. The mechanics of batching $\gamma+1$ evaluations differ: for encoder-decoders, the encoder output is shared across all $\gamma+1$ decoder evaluations, potentially making the parallel execution more efficient; for decoder-only models, each evaluation is fully independent, potentially introducing different batching overhead. The paper's theoretical prediction formula (Theorem 3.8) abstracts these differences into the single parameter $c$, but $c$ was only measured for T5. Whether the formula accurately predicts walltime for decoder-only models is unknown.

Additionally, the two tasks tested—translation and summarization—are both constrained generation tasks where the output is a transformation of the input. Tasks with more open-ended generation (creative writing, long-form QA, code generation) might exhibit different patterns in where $M_q$ matches $M_p$: for example, tokens that are highly constrained by the input (entity names in summarization, technical terms in translation) might have high $\beta$, inflating the average $\alpha$, while genuinely creative tokens might have low $\beta$ that the average obscures. The paper provides no task-diversity analysis.

What evidence exists in the paper. The evidence for generalization is purely in the $\alpha$ values (Table 3): T5-small achieves $\alpha = 0.62$–$0.75$ on EnDe, the GPT-like 6M model achieves $\alpha = 0.88$–$0.89$ on lm1b, and LaMDA 100M achieves $\alpha = 0.57$–$0.61$ on dialog. These $\alpha$ values are in a similar range, suggesting that substantial token-level overlap between $M_p$ and $M_q$ is a general phenomenon. However, $\alpha$ alone does not guarantee walltime speedup—the translation from $\alpha$ to speedup requires $c$, which is not reported for non-T5 models, and requires validation that the batching parallelism assumed in Theorem 3.8 actually materializes.

Mitigation status. The paper partially addresses this by citing independent replication: Chen et al. (2023) showed "similar 2X-2.5X improvements on Chinchilla 70B" (Section 5), which is a decoder-only model. This provides some external validation, but the citation appears in the related work section and the details of that implementation are not analyzed. Within the paper itself, the walltime generalization gap is not acknowledged as a limitation. The paper's abstract claims the method "can accelerate existing off-the-shelf models without retraining or architecture changes," and the introduction states it works on "large autoregressive models like Transformers," language that suggests broader validation than the experiments provide.

---

The Exact Distributional Equivalence Guarantee Depends on Implementation Correctness and Is Not Empirically Validated

The assumption or constraint. The paper's most distinctive claim is that speculative decoding produces outputs "with identical outputs" (abstract), "without changing the distribution" (abstract), with the guarantee that tokens are "distributed identically to those sampled from $p(x)$ alone" (Appendix A.1). This guarantee is proven mathematically under the assumption that the implementation correctly standardizes sampling methods (Section 2.2), correctly computes the acceptance criterion $\min(1, p(x)/q(x))$, correctly computes the corrected distribution $\text{norm}(\max(0, p(x) - q(x)))$, and correctly samples from it. The proof does not cover numerical precision issues, subtle bugs in distribution manipulation, or edge cases in how different sampling methods interact with the acceptance logic.

The consequence. While the mathematical guarantee is strong, its realization in practice depends on implementation correctness that the paper does not empirically validate. A practitioner deploying speculative decoding in a production system cannot simply trust the proof—they would need to verify that their implementation actually preserves the output distribution, which requires running statistical tests comparing the output distributions with and without speculative decoding. The paper provides no such validation, nor does it provide guidance on how to perform it. This shifts the burden of verification from the authors to the adopter.

Specific failure modes that could silently violate the guarantee include: floating-point underflow in computing $p(x) - q(x)$ for very small probabilities, incorrect normalization of the residual distribution when $\max(0, p(x) - q(x))$ sums to a value close to 0, off-by-one errors in which position's distribution is used for resampling after rejection, or incorrect handling of the interaction between the sampling standardization (e.g., top-k filtering) and the acceptance criterion (which uses the full post-standardization distribution but the acceptance probability depends on individual token probabilities that may have been zeroed out).

What evidence exists in the paper. None for empirical distributional validation. The paper does not report any experiment that compares the empirical output distribution of speculative decoding to that of standard decoding—no KL divergence measurements, no token frequency comparisons, no statistical tests of distributional equality. The proof in Appendix A.1 is correct and complete, but it is a proof about the idealized algorithm, not about any particular software implementation. The only evidence that the implementation is correct is that the empirical speedups roughly match the theoretical predictions (Table 4), which would be unlikely if the acceptance logic were systematically wrong, but this is a weak consistency check, not a direct validation.

Mitigation status. Not addressed. The paper treats the proof as sufficient evidence for the distributional guarantee and does not acknowledge the gap between mathematical proof and software implementation. Appendix A.5's lenience analysis—which relaxes the exact equivalence guarantee in exchange for higher speedup—implicitly acknowledges that exact equivalence may not always be necessary, but it does not address the separate question of whether the strict ($l=1$) version actually achieves exact equivalence in practice.

---

The Framework Requires a Suitable Approximation Model, and Not All Deployments Have One

The assumption or constraint. Speculative decoding requires an approximation model $M_q$ that satisfies two conditions: (1) it must be fast enough relative to $M_p$ (low $c$) for the speedup formula (Theorem 3.8) to yield net improvement, and (2) it must share enough of $M_p$'s output distribution (high enough $\alpha$) for the improvement factor to be substantial. The paper demonstrates that off-the-shelf smaller models from the same family (T5-small, LaMDA-100M) satisfy these conditions, but this is a contingent empirical finding, not a guarantee that holds for all model families.

The consequence. For model families without a spectrum of smaller pre-trained checkpoints—for example, a custom-trained large model where no smaller variant exists, or a model using a novel architecture with no smaller public implementation—obtaining a suitable $M_q$ requires either training one from scratch (which defeats the "no retraining" benefit) or using a simple statistical model like n-grams (which yields only modest speedup: $\alpha = 0.20$ gives 1.25× at best, per Table 3). The paper's claim of applicability to "existing off-the-shelf models" (abstract) is true for the model families tested (T5, LaMDA) but may not generalize.

Even when smaller variants exist, the optimal size for $M_q$ is not obvious without measurement. Table 2 shows that T5-large (800M) underperforms T5-small (77M) despite higher $\alpha$, because its $c$ (0.11) outweighs its $\alpha$ advantage. A practitioner with access to T5-small, T5-base, and T5-large cannot know which to use without measuring both $\alpha$ and $c$, which requires implementing speculative decoding or at least profiling both models' inference costs. The paper's diagnostic framework (measuring $\alpha$ on 10K tokens) provides a way to estimate $\alpha$ without full implementation, but estimating $c$ still requires hardware profiling.

What evidence exists in the paper. The paper experiments specifically with T5 variants (small/base/large for XXL), LaMDA variants (100M/2B/8B for 137B), and a custom 6M GPT-like model for a 97M target. This covers models from roughly 100× to 1000× smaller than the target. For all these configurations, $\alpha$ falls in the 0.5–0.9 range (Table 3), and speedup is positive. The paper also tests n-gram models as a fallback ($\alpha = 0.03$–$0.23$) and notes that even these provide nonzero improvement. However, the paper provides no evidence on what happens when the only available $M_q$ is, say, only 10× smaller than $M_p$ (where $c$ might be too high for net improvement) or when no smaller model from the same family exists.

Mitigation status. The paper partially addresses this by discussing alternative approximation model types (Section 3.6): n-gram models, non-autoregressive models, heuristics like context-copying, and distillation-trained custom models. These are described as options but not empirically evaluated for walltime speedup. The paper frames future work on training custom $M_q$ models optimized for $\alpha$ (Section 6: "greater improvements might be obtained via custom approximation models... such as those with custom architectures or with custom training procedures"), implicitly acknowledging that off-the-shelf models may not always be optimal or available. However, the paper's primary claim of zero-training deployment only holds when a suitable off-the-shelf $M_q$ already exists.

7. Implications and Future Directions

How This Work Changes the Landscape

Speculative decoding introduces a new category of inference acceleration that sits between two previously disconnected approaches: uniform efficiency methods (distillation, quantization) that require retraining, and adaptive computation methods (early exits) that change outputs. By proving that exact distributional equivalence can be maintained while achieving 2×–3× walltime speedup on off-the-shelf models, the paper establishes that the serial dependency in autoregressive decoding is not a hard bottleneck—it can be partially circumvented through parallelism without compromising statistical guarantees.

This is neither a paradigm shift nor a mere incremental refinement. It is a reframing of the inference acceleration problem along two axes:

First, it legitimizes trading total compute for reduced latency as a first-class design strategy. Before this work, the dominant assumption was that making inference faster meant making it computationally cheaper. The paper demonstrates—through both the theoretical framework of Theorems 3.8 and 3.11 and the empirical results in Table 2—that doing more arithmetic operations can produce lower walltime when hardware is memory-bandwidth-bound. This reframing opens design space that prior work avoided. It also provides the analytical tools (the cost coefficient $c$, the operations factor of Theorem 3.11, the condition $\alpha > c$ from Corollary 3.9) to determine when the tradeoff is favorable. These tools are portable: a practitioner can measure $c$ and $\alpha$ on their own hardware and models to decide whether speculative decoding applies, without implementing the full algorithm.

Second, it redefines the relationship between model quality and inference cost. The finding that T5-small (77M) outperforms T5-large (800M) as an approximation model for T5-XXL (Table 2: 3.4× vs. 1.7× on EnDe at temp=0) is counterintuitive but follows directly from the speedup formula: $\alpha$ grows slowly with approximation model size while $c$ grows quickly, creating a sweet spot roughly two orders of magnitude smaller than the target. This means the best approximation model is not the most accurate one but the one with the best ratio of accuracy to cost. This insight changes how practitioners should think about model selection: "smaller and faster" can beat "larger and more accurate" when the metric is end-to-end latency, not per-token agreement.

The paper also reconciles an apparent contradiction in prior speculative execution work for neural decoding. Stern et al. (2018) and Sun et al. (2021) both applied speculative execution to language model decoding, but both restricted themselves to greedy (temperature=0) sampling. The implicit assumption—that stochastic sampling doesn't admit speculative verification because there is no single "correct" next token—was so strong that prior work didn't even frame it as a limitation. The paper shows that this assumption is false by inventing the speculative sampling procedure, which uses the acceptance probability $\min(1, p(x)/q(x))$ and the corrected residual distribution $\text{norm}(\max(0, p(x) - q(x)))$ to recover exactly the target distribution. The proof in Appendix A.1 is only a few lines, but the conceptual move—treating the entire probability distribution as the verification target rather than a single argmax token—is what makes stochastic speculative execution possible.

This resolution has the practical effect of making speculative decoding applicable to real-world deployments, which almost universally use stochastic sampling (temperature, top-p, nucleus) to control output diversity. Without it, speculative decoding would be a niche technique for greedy decoding, which is rarely used in production outside of constrained tasks like translation.

Research directions that become more attractive:

• Custom approximation model training. The paper shows that off-the-shelf smaller models work (Table 2), but the acceptance rate $\alpha = \mathbb{E}[\sum_x \min(p(x), q(x))]$ provides a direct optimization target for training $M_q$. Rather than distilling $M_p$ to minimize KL divergence (which doesn't directly optimize for speculative decoding efficiency), one could train $M_q$ to maximize the expected min-overlap. The paper's characterization of $\alpha$ as an interpretable, measurable quantity (Section 3.2) makes this optimization problem well-defined.

• Dynamic resource allocation during inference. Section 3.5 notes that varying $\gamma$ based on predicted per-token $\beta$ could yield up to ~60% additional improvement beyond the fixed-$\gamma$ optimum. This suggests a line of work on lightweight $\beta$-predictors that run alongside $M_q$ and adjust the guess budget adaptively. The paper provides the upper bound ($\frac{1}{1-\alpha}$) and the diagnostic framework; the open problem is building a predictor that approaches this bound with minimal overhead.

• Speculative execution for non-autoregressive or hybrid decoding schemes. Section 3.6 mentions non-autoregressive $M_q$ models as an option. If $M_q$ can produce $\gamma$ tokens in one parallel shot (rather than sequentially), the $\gamma c$ term in Theorem 3.8 effectively disappears, potentially enabling much larger $\gamma$ and higher speedups for the same $\alpha$. The paper does not explore this, but the framework supports it directly.

Research directions that become less critical:

• Further complexity in search-based decoding acceleration. The paper demonstrates that a simple parallel-verification scheme with off-the-shelf models achieves meaningful speedups. This reduces the urgency of developing more sophisticated tree-search or MCTS-based decoding schemes, which add algorithmic complexity without necessarily improving on the basic speculative execution pattern. The paper's focus on exact distributional equivalence also raises the bar for alternative methods: they must either match this guarantee or justify why approximate equivalence is acceptable.

• Architecture modifications purely for inference speed. If speculative decoding can accelerate existing architectures 2×–3× without modification (Table 2), the marginal benefit of architectural changes (multi-query attention, mixture-of-experts routing, etc.) must be weighed against the engineering cost of retraining and revalidating models. The paper does not argue against architectural improvements—Section 5 explicitly says speculative decoding can be combined with them—but it reduces the pressure to modify architectures solely for inference latency.

Follow-Up Research This Work Enables

Training approximation models that directly maximize the speculative acceptance rate $\alpha$. The paper uses off-the-shelf smaller models as $M_q$ and achieves $\alpha$ values of 0.5–0.9 (Table 3). But the objective $\mathbb{E}[\sum_x \min(p(x), q(x))]$ is differentiable with respect to $q$'s parameters, and it differs from the standard distillation objective (KL divergence). A natural follow-up would train a small model to maximize this $\min$-overlap on samples from $M_p$, then measure whether the resulting $\alpha$ exceeds what off-the-shelf models achieve at the same parameter count. The key experiment: compare walltime speedup using (a) an off-the-shelf T5-small as $M_q$, (b) a T5-small fine-tuned with standard distillation from T5-XXL, and (c) a T5-small fine-tuned to maximize $\mathbb{E}[\sum_x \min(p(x), q(x))]$. The prediction from this paper's framework: (c) should achieve higher $\alpha$ than (a) and (b) because the training objective directly aligns with the acceptance criterion, whereas distillation minimizes a different divergence.

Measuring and modeling the breakdown of the i.i.d. assumption on $\beta$. Table 4 shows that the theoretical speedup formula (Theorem 3.8) overpredicts empirical speedup by ~47% for T5-large, attributed to the i.i.d. assumption on $\beta$. But the paper never characterizes how $\beta$ varies across tokens or contexts. A follow-up study would measure $\beta$ at each position during speculative decoding, compute its autocorrelation structure (do hard-to-predict tokens cluster together? does $\beta$ drop after punctuation? is there a systematic relationship with token frequency or part-of-speech?), and build a Markov model or conditional predictor for $\beta$ that improves the speedup prediction. The paper's diagnostic framework (Corollary 3.6) provides the measurement tool; the open question is whether a simple low-order model of $\beta$ variation can close the gap between predicted and empirical speedup in Table 4.

Dynamic $\gamma$ scheduling with a learned $\beta$-predictor. Section 3.5 establishes an upper bound of $\frac{1}{1-\alpha}$ expected tokens per iteration with a perfect $\gamma$-oracle, which is up to ~60% higher than the fixed-$\gamma$ optimum. The natural next step is to train a small model (or even a linear classifier on features of the prefix and $M_q$'s output distribution) to predict $\beta$ for the next token, and use this prediction to dynamically set $\gamma$. The experiment: implement speculative decoding where $\gamma$ is adjusted at each iteration based on predicted $\beta$, measure the resulting tokens-per-iteration against the fixed-$\gamma$ baseline from Table 2, and compare against the $\frac{1}{1-\alpha}$ upper bound. The key design choice is whether the $\beta$-predictor runs on top of $M_q$ (adding to its cost) or is extracted from $M_q$'s internal representations (adding negligible cost). The paper's analysis suggests this is the highest-ROI extension, since it improves speedup without changing $M_q$ or $M_p$ and the analytical framework already characterizes the potential gain.

Walltime measurements for decoder-only models at scale. Table 3 reports $\alpha$ values for LaMDA 137B (0.57–0.75) and a GPT-like 97M model (0.88–0.89), but no walltime measurements exist. A follow-up should implement speculative decoding for a decoder-only architecture (GPT, LLaMA, or PaLM) at a scale comparable to T5-XXL (10B+ parameters), measure walltime speedup across batch sizes 1, 4, 8, 32, and compare against the theoretical predictions from Theorem 3.8 using the measured $c$ and $\alpha$. This would address the paper's primary limitation: the walltime results are confined to one architecture (encoder-decoder T5) on one hardware configuration (TPU-v4, batch size 1). The experiment should also measure memory consumption as a function of $\gamma$, since decoder-only models with long contexts may hit memory limits before reaching the optimal $\gamma$.

Hierarchical speculative decoding with a chain of approximation models. Section 6 mentions the possibility of "a hierarchical version of the algorithm, where the approximation model is itself accelerated by an even faster model." The experiment: use T5-large as $M_q$ for T5-XXL, but accelerate T5-large itself with T5-small as $M_{q2}$, forming a three-tier hierarchy. Measure whether the compounded speedup (T5-small accelerates T5-large, which accelerates T5-XXL) exceeds using T5-small directly as $M_q$ for T5-XXL. The tradeoff: the hierarchical approach lets you use a more accurate intermediate $M_q$ (T5-large, with higher $\alpha$ against T5-XXL) while keeping the per-token cost low (because T5-large is itself accelerated). But the additional layer introduces another acceptance/rejection step, which could compound variance. The paper's framework supports analyzing this with a nested version of Theorem 3.8, but no empirical evidence exists for whether the compounding works in practice or whether overhead dominates.

Lenience-controlled speculative decoding with formal guarantees and empirical validation of output quality vs. speedup. Appendix A.5 introduces lenience parameter $l \in [0,1]$ and reports theoretical $\alpha$ values (e.g., T5-small on EnDe goes from $\alpha=0.62$ at $l=1$ to $\alpha=0.84$ at $l=0.1$, suggesting 5× speedup). But no walltime measurements exist, and the output quality guarantee weakens to "no token can be sampled with probability greater than $\frac{p(x)}{l}$." A follow-up should implement lenient speculative decoding for a range of $l$ values, measure empirical walltime speedup (not just predicted), and evaluate output quality degradation using standard metrics (BLEU for translation, ROUGE for summarization, perplexity for language modeling) and human evaluation. The key question: does a small relaxation of exact equivalence ($l=0.5$, guaranteeing no token's probability is more than doubled) yield a disproportionate speedup gain (as Table 5 suggests: $\alpha$ jumps from 0.62 to 0.71 for T5-small on EnDe)? If so, lenience could become the default operational mode, with the strict $l=1$ guarantee reserved for applications where exact equivalence is non-negotiable.

Practical Applications and Downstream Use Cases

Latency reduction for interactive LLM applications (chatbots, code assistants, writing tools). In these settings, user-perceived latency directly determines product quality—a 200ms response feels instantaneous while 600ms feels sluggish. The paper's 2×–3× walltime improvement on T5-XXL (Table 2: 3.4× on EnDe translation at temp=0) translates directly to latency reduction without any change to model quality. For a production chatbot running a 137B-parameter LaMDA model, the $\alpha$ values in Table 3 (0.57–0.75 depending on approximation model) suggest speedups in the same 2×–3× range are achievable without retraining, using an existing LaMDA 100M or 2B checkpoint as $M_q$. The key implementation requirement is that the serving infrastructure supports batching $\gamma+1$ evaluations of the large model, which is straightforward on GPU/TPU serving stacks that already batch requests. This is the paper's most immediately actionable application: the method can be deployed into existing serving pipelines as a drop-in replacement for the autoregressive sampling loop.

Cost-efficient high-throughput batch inference (translation services, summarization pipelines, data labeling). For applications that process large volumes of text—translating millions of documents, summarizing news articles, generating training data for other models—the primary cost driver is total inference time across all queries. Even though speculative decoding increases total arithmetic operations (1.23×–1.63× for typical configurations in Table 1), the walltime reduction of 2×–3× means the same hardware can process 2×–3× more queries per unit time. If the cost of additional arithmetic operations is lower than the cost of provisioning additional hardware to handle the query volume (which is typically the case in cloud deployments where you pay for accelerator time, not FLOPs), speculative decoding directly reduces per-query cost. For a summarization pipeline using T5-XXL, Table 2 shows 2.3×–3.1× speedup depending on the approximation model and sampling method, suggesting a corresponding reduction in accelerator-hours per million summaries.

Enabling larger models in resource-constrained deployment scenarios (on-device, edge, or single-GPU serving). The paper's conceptual framework shows that speculative decoding is most effective when the target model is deployed in a memory-bandwidth-bound regime with spare compute—exactly the conditions that arise when running large models on single accelerators with limited memory bandwidth. For a team that wants to deploy a 11B-parameter model on a single GPU but finds the latency unacceptable, speculative decoding with a 77M-parameter $M_q$ (analogous to T5-small for T5-XXL) can bring latency into an acceptable range without the quality degradation of switching to a smaller model. The paper's diagnostic framework (measure $\alpha$ and $c$, plug into Theorem 3.8) lets the team assess whether this is viable before implementing the full system. The finding that n-gram models achieve $\alpha = 0.20$ (Table 3, bigram on EnDe) with $c \approx 0$ also provides a fallback: even without a trained smaller Transformer, a simple statistical model can provide 1.25× speedup, which may be sufficient to meet a latency target.