Faster Decoding

The previous two chapters separated request timing from memory allocation. They also established a rule for execution: reserve the state required by a token plan before launching it. Faster decoding changes that plan. Instead of asking the target model for exactly one new token, a proposer supplies several candidates and the target scores them together. A successful cycle can return more than one token, but it also consumes proposal time, verification work, and temporary KV state.

This trade is attractive when target decoding is underutilizing the accelerator, as low-batch dense decoding often does when weight traffic is the main cost. It is not a universal property of decoding. Long contexts add KV traffic; model parallelism adds communication; and larger batches may make verification compute-bound. The proposal must therefore be judged as part of the measured serving regime.

Two 2023 papers established exact versions of this idea: speculative decoding by Leviathan, Kalman, and Matias (Leviathan et al. 2023), and speculative sampling by Chen and colleagues (Chen et al. 2023). Later work changed where candidates come from and how they are arranged. Medusa and Hydra add draft heads (Cai et al. 2024; Ankner et al. 2024), the EAGLE family learns a feature or token drafter (Li et al. 2024; Li et al. 2024; Li et al. 2025), lookahead decoding builds candidates through iteration (Fu et al. 2024), and multi-token prediction trains future-token modules with the model (Gloeckle et al. 2024). These are design choices, not stages in a required lineage.

Verification can be parallel even when generation is sequential

Autoregressive generation still has a sequential dependency: token $i+1$ depends on token $i$. A proposed suffix makes those dependencies available as inputs. Under a causal mask, one target pass can then score every position in that suffix in parallel. The target remains authoritative; the proposal only creates candidate work.

Here $\gamma$ is the length of a linear proposal. Define $A_k$ as the event that draft position $k$ is accepted after every earlier position was accepted, and let

$$s_k=\Pr(A_1\cap\cdots\cap A_k),\qquad s_0=1.$$

If a cycle emits the accepted prefix plus one corrected or bonus token, and no stop condition truncates that output, its token yield $Y$ satisfies

$$\mathbb E[Y]=1+\sum_{k=1}^{\gamma}s_k.$$

This expectation means that an aggregate accepted-token rate does not determine prefix survival. Early positions may be easier than later ones, and acceptance events may be correlated. Only under the additional assumption of a constant conditional acceptance probability $\alpha$ at every position does $s_k=\alpha^k$, giving

$$\mathbb E[Y] =\sum_{k=0}^{\gamma}\alpha^k =\frac{1-\alpha^{\gamma+1}}{1-\alpha}, \qquad \alpha\ne1,$$

with $\mathbb E[Y]=\gamma+1$ when $\alpha=1$. This is expected tokens per verification cycle, not a latency speedup. It says nothing yet about the time or memory spent on that cycle.

Here the runnable compares heterogeneous conditional probabilities with an IID estimate formed from their arithmetic mean. The two results differ even in this small deterministic example.

conditional = [0.85, 0.75, 0.60, 0.40]

survival = []
alive = 1.0
for probability in conditional:
    alive *= probability
    survival.append(alive)

expected = 1.0 + sum(survival)
alpha = sum(conditional) / len(conditional)
iid_estimate = sum(alpha**k for k in range(len(conditional) + 1))

print("survival by position:", ", ".join(f"{value:.4f}" for value in survival))
print(f"expected tokens/cycle: {expected:.4f}")
print(f"iid estimate at alpha={alpha:.2f}: {iid_estimate:.4f}")

Modified rejection sampling preserves the target distribution

speculative decoding is proposal-and-verification with a correction rule that leaves the target model's output distribution unchanged. Consider one position after applying the intended decoding policy, including temperature, logit constraints, and any top-$k$ or top-$p$ truncation. Here $p$ denotes the target distribution, $q$ the proposal distribution, and $\mathcal V$ their common token space. A candidate $X\sim q$ is accepted with probability

$$a(v)=\min\!\left(1,\frac{p(v)}{q(v)}\right).$$

The denominator is defined for a sampled candidate because such a token has $q(v)>0$. On rejection, sample from the residual distribution

$$Z=\sum_{u\in\mathcal V}[p(u)-q(u)]_+, \qquad r(v)=\frac{[p(v)-q(v)]_+}{Z},$$

where $[z]_+=\max(0,z)$. The rejection probability is $Z$. For any token $v$, the probability mass contributed by acceptance and correction is

$$q(v)a(v)+Zr(v)=\min(p(v),q(v))+[p(v)-q(v)]_+=p(v).$$

If $Z=0$, the rejection probability is zero and the residual is never sampled. This one-position identity is applied left to right: stop at the first rejection, emit a corrected token, and discard the remaining proposal. If all $\gamma$ candidates are accepted, sample one bonus token from the target distribution at the next position. The target pass must therefore provide distributions for all candidate positions and for that bonus position (Leviathan et al. 2023; Chen et al. 2023).

"Exact" here means equal output distributions, not identical sampled token sequences for the same seed. Floating-point kernels, batching, and random-number consumption can change a particular realization. Exactness also requires the same sampling transformation and stopping policy on the distributions being compared: temperature, truncation, constraints, and token mapping cannot be silently different. EOS, stop sequences, and maximum length may shorten a cycle and suppress the bonus token.

Greedy verification is a separate deterministic contract. It can accept the longest run that matches the target's greedy tokens and then take the target's first mismatch. Relaxed rules, such as a typical-acceptance mode, deliberately trade distribution equality for another quality or speed criterion. A system must label these contracts separately.

Proposal source, candidate topology, and acceptance policy are separate choices

Implementations make three independent choices: who proposes candidates, how candidates are arranged, and which rule authorizes output. A proposal mechanism does not by itself make sampling exact.

This table is not a ranking. A deployer may already have a compatible small model, while another model may ship with useful heads. Proposal quality can also change with domain, context length, sampling settings, and quantization. The cheapest proposal is the one that reduces measured target-cycle cost for the actual workload.

Linear chains and candidate trees spend work differently

Here a linear suffix contains $\gamma$ candidate positions. If an early token is rejected, its later positions cannot be emitted in that cycle. A candidate tree hedges by carrying several continuations. A tree attention mask packs branches into one target operation while ensuring that each node attends only to its own ancestry.

flowchart TD
  C[context] --> A1[A1] --> A2[A2]
  C --> B1[B1] --> B2[B2]
  B1 --> B3[B3]

The mask makes joint scoring possible; it does not make a verifier exact. Greedy tree search, distribution-preserving tree sampling, and relaxed tree acceptance are different algorithms. Tree width can improve the chance of finding a useful path, but verification time and temporary KV grow with the number of scored nodes. Rejected branches are real work, not free alternatives.

Speedup is a wall-clock measurement

Here $t_1$ denotes the measured time for one baseline target decode step, $t_{\mathrm{propose}}(\gamma)$ the proposal time, $t_{\mathrm{verify}}(\gamma,m)$ the target time for a proposal containing $m$ scored candidate nodes, and $t_{\mathrm{reconcile}}$ the acceptance, synchronization, and state-management time. For a chain, $m=\gamma$. A useful first-order latency ratio is

$$S_{\mathrm{latency}} \approx \frac{\mathbb E[Y]t_1} {t_{\mathrm{propose}}(\gamma) +t_{\mathrm{verify}}(\gamma,m) +t_{\mathrm{reconcile}}}.$$

The denominator represents $t_{\mathrm{cycle}}$. In words, speculation improves average token time only when

$$\frac{t_{\mathrm{cycle}}}{\mathbb E[Y]}<t_1.$$

Verification time grows with candidate positions, tree nodes, context length, KV traffic, batch composition, kernels, and communication. In a low-batch, weight-bandwidth-bound regime, that growth may be small enough that fewer target synchronizations win. At higher utilization, rejected candidate work can compete with other requests. Compute-bound operation can reduce the advantage, but it does not prove that every proposal must lose; proposal placement, overlap, kernels, and synchronization still matter.

Paper results demonstrate feasibility in their evaluated settings, not portable multipliers. Leviathan and colleagues reported twofold to threefold improvement on their T5 experiments (Leviathan et al. 2023), while EAGLE reported 2.7 to 3.5 times lower latency on its evaluated LLaMA2-Chat configurations (Li et al. 2024). Those numbers used different models, hardware, software, sampling settings, and baselines. Reproduce the configuration before comparing them.

The scheduler must plan speculative work

Chapter 32's reserve, execute, and commit protocol applies directly. Before a cycle begins, the scheduler should reserve candidate positions and workspace. A linear proposal needs room for its candidate suffix; a tree needs room for all scored nodes. Admission must use that planned maximum, not the expected accepted length.

After verification, commit target KV only for the accepted draft prefix and release every rejected tail or branch. Draft and target caches are separate namespaces: their tensors come from different models or modules and are not interchangeable. The corrected or bonus token becomes input to the next target cycle, where its own target KV is materialized. The scheduler must roll reservations back on cancellation or failure before the same blocks are offered elsewhere.

Different requests accept different prefix lengths, so the next batch is ragged. The scheduler must preserve each request's positions, masks, stop state, and cache ownership while repacking work. Under memory pressure or rising concurrency, it may shorten $\gamma$, narrow a tree, select a cheaper proposal, or fall back to ordinary one-token decoding. No universal batch cutoff chooses among those policies.

Choose from workload evidence

A deployment decision starts with a contract and ends with a load test.

1. Fix the output contract. Decide whether the service promises exact sampling, greedy sequence equality, or a documented relaxed rule. Confirm the target, tokenizer, vocabulary mapping, model revision, adapters, sampling transforms, constraints, and stopping behavior. Here the named transforms include top-$k$ and top-$p$.
2. Profile proposal budgets. Sweep chain length or tree-node budget across representative context lengths, output types, batch shapes, and sampling settings. Include low-acceptance workloads rather than tuning only on the easiest prompts.
3. Measure the whole cycle. Record the accepted-prefix length distribution, proposed, verified, accepted, corrected, and bonus tokens; target cycles per output token; proposal, verification, and reconciliation time; and temporary KV and workspace high-water marks.
4. Evaluate as a service. Compare at matched admitted load and report TTFT, TPOT, inter-token latency, end-to-end latency, output throughput, goodput, rejection rate, cost, and energy. Inspect both medians and tails.
5. Keep a fallback. Disable speculation when its predicted cost exceeds baseline decoding, when capacity cannot be reserved, or when compatibility checks fail. Record when and why fallback occurs.

No single acceptance rate or paper speedup answers whether the deployment wins. For example, two systems can accept the same fraction of candidates but place rejections at different positions, producing different $\mathbb E[Y]$. They can also have the same yield but very different target verification times.

Correctness and failure tests

Test the sampler and the memory protocol independently, then together.

• On a tiny vocabulary, compare empirical output frequencies with the target distribution for $p=q$, partial overlap, and disjoint support. Here partial overlap means that only part of the proposal's probability mass matches the target. Force first rejection, later rejection, and full acceptance.
• Compare greedy output token for token with baseline decoding. Exercise EOS, stop sequences, and maximum length, including full acceptance at a boundary.
• Repeat under temperature, top-$k$, top-$p$, grammar constraints, and logit processors. Reject a tokenizer, adapter, or constraint mismatch before work begins.
• Batch requests with mixed accepted-prefix lengths. Verify positions, masks, output order, and per-request random state after repacking.
• Cross a cache-block boundary, reject a wide tree, cancel during verification, and inject a target failure. Reconcile every reservation, committed block, reference count, and released branch.
• Compare numerical distributions within a stated tolerance across batch and kernel configurations. Do not require bitwise-identical stochastic samples.
• Drive acceptance low and memory pressure high. Confirm bounded queueing and a clean return to baseline decoding.

Payoff and boundary

Proposal-and-verification does not remove autoregression. It supplies candidate dependencies so the target can verify several positions in parallel, then commits only output authorized by an explicit acceptance contract. Its payoff is fewer expensive target cycles per output token; its price is proposal work, wider verification, temporary memory, and more complex reconciliation.

The next chapter changes a complementary quantity. Quantization reduces the bytes used to represent model state, while fused kernels reduce data movement and launch overhead inside a cycle. Those changes can alter both baseline time and proposal acceptance, so faster decoding, quantization, and kernels should be measured together rather than treated as independent multipliers.

Further reading