Speculative Decoding: Drafting, Verification, and Real Speed Gains

When generating a long answer, the target model normally runs again after each token is chosen to obtain the probabilities for the next one. Speculative decoding uses cheaper computation to propose a sequence, then has the target verify its candidates in parallel. A verification round can commit several tokens, spreading the cost of expensive serial steps across them. Leviathan et al.'s original paper gives an algorithm that preserves the target sampling distribution.

Start with prefix dependencies in autoregressive generation and the prefill, decode, and throughput boundaries in inference performance. The question here is how to reduce target calls during decode, and when fewer calls save elapsed time.

Known candidates make parallel verification possible

In ordinary generation, choosing the second token requires the first, and choosing the third requires both. The KV cache retains the existing prefix's state; the target still processes each new position.

Let $h$ be the committed prefix and let the draft propose $x_1,x_2,x_3$. All candidate prefixes are now known, so a causal target forward pass can obtain:

$$\begin{aligned} p_1&=p(\cdot\mid h),\\ p_2&=p(\cdot\mid h,x_1),\\ p_3&=p(\cdot\mid h,x_1,x_2),\\ p_4&=p(\cdot\mid h,x_1,x_2,x_3). \end{aligned}$$

Verify $x_1$ against $p_1$, $x_2$ against $p_2$, and so on: the offset between logits and candidate positions matters. If all three are accepted, sample a bonus token from $p_4$. If the second is rejected, retain only the first and add a correction at the second position. Discard the original third candidate and its verification result because they depend on the rejected prefix. EOS or an output limit can end the round early.

The target verification is parallel; a linear draft may still generate candidates sequentially. Verifying more positions adds computation. The benefit depends on amortizing reads of weights and historical state.

Acceptance and rejection preserve the distribution

The rule in Section 2.3 and Appendix A.1 of the original paper uses normalized target distribution $p$ and actual proposal distribution $q$ for the same prefix over the same token identifiers. Here, $p$ includes the target's temperature, top-k, top-p, or other sampling transformations; $q$ must likewise describe the draft's actual proposal procedure.

Accept a candidate $x$ sampled from $q$ with probability:

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

A proposed token has $q(x)>0$. At the first rejection, sample a replacement from the remaining probability mass:

$$r(x)=\frac{\max(0,p(x)-q(x))}{\sum_y\max(0,p(y)-q(y))}.$$

When $p=q$, every candidate is accepted and the zero-denominator correction branch is never entered. Applying these rules correctly at successive prefixes preserves the target sequence distribution. Rejecting low-probability candidates and simply resampling from $p$ generally changes it.

Account for all probability mass with three tokens

Consider a constructed vocabulary A, B, C with $p=(0.5,0.3,0.2)$ and $q=(0.6,0.1,0.3)$. Their acceptance probabilities are $5/6,1,2/3$. Multiplying by proposal probabilities gives accepted mass $(0.5,0.1,0.2)$ and total acceptance $0.8$. The remaining $0.2$ goes entirely to B, restoring $(0.5,0.3,0.2)$.

This Python 3 example checks the probabilities using exact fractions, then replays one verification round with fixed candidates and draws. Here, $p$ and $q$ are normalized distributions over the same finite vocabulary, each proposed token has $q(x)>0$, and draws lie in $[0,1)$. The toy distributions are identical at every prefix to keep the arithmetic simple; real model distributions change with the prefix. The code samples from the correction distribution at the first rejection, or from $p$ for a bonus token if all candidates are accepted. When $p=q$, it skips the correction distribution. The default inputs reject C and replace it with B with probability 1.

from fractions import Fraction as F

tokens = ['A', 'B', 'C']
p = dict(zip(tokens, map(F, ['0.5', '0.3', '0.2'])))
q = dict(zip(tokens, map(F, ['0.6', '0.1', '0.3'])))
accepted = {x: min(p[x], q[x]) for x in tokens}
alpha = sum(accepted.values())
if alpha < 1:
    residual = {x: max(p[x] - q[x], 0) / (1 - alpha) for x in tokens}
    restored = {x: accepted[x] + (1 - alpha) * residual[x] for x in tokens}
else:
    residual = None
    restored = accepted
assert restored == p
print('accepted mass:', [float(accepted[x]) for x in tokens])
print('acceptance:', float(alpha))
print('residual:', None if residual is None else [float(residual[x]) for x in tokens])
print('reconstructed:', [float(restored[x]) for x in tokens])

def sample(distribution, u):
    assert 0 <= u < 1
    cumulative = F(0)
    for x in tokens:
        cumulative += distribution[x]
        if u < cumulative:
            return x
    raise ValueError('distribution must sum to 1')

draft = ['A', 'C', 'B']
draws = list(map(F, ['0.7', '0.9', '0.2']))
final_draw = F('0.2')
assert len(draft) == len(draws)
emitted = []
for i, (x, u) in enumerate(zip(draft, draws)):
    assert q[x] > 0 and 0 <= u < 1
    threshold = min(F(1), p[x] / q[x])
    ok = u < threshold
    print(f'{x}: u={float(u):.1f}, threshold={float(threshold):.3f}, accept={ok}')
    if not ok:
        assert residual is not None
        emitted.append(sample(residual, final_draw))
        print('discard:', draft[i:])
        break
    emitted.append(x)
else:
    bonus = sample(p, final_draw)
    emitted.append(bonus)
    print('bonus:', bonus)
print('emit:', emitted)

accepted mass: [0.5, 0.1, 0.2]
acceptance: 0.8
residual: [0.0, 1.0, 0.0]
reconstructed: [0.5, 0.3, 0.2]
A: u=0.7, threshold=0.833, accept=True
C: u=0.9, threshold=0.667, accept=False
discard: ['C', 'B']
emit: ['A', 'B']

The round commits A, B. Although the last draft B happens to match the correction token, its original state depended on prefix A, C and must be discarded.

Identical distributions do not require word-for-word identical answers with the same seed: algorithms can consume random numbers in different orders. vLLM's lossless-guarantee documentation also retains qualifications about floating-point precision, batch size, and logprob stability. The guarantee concerns decoding from a fixed target; changes introduced by target quantization or approximate caching require a separate comparison.

A good draft must also be cheap

At a fixed prefix, acceptance is $\sum_x\min(p(x),q(x))$. Similar draft and target distributions make acceptance more likely. The draft's ability to answer questions on its own does not substitute for this measure.

Use a simplified cost budget to decide whether speculation is worth testing. Suppose each round proposes $\gamma$ candidates, each position has conditional acceptance probability $\alpha$, acceptance events are independent and identically distributed, and there is no early stopping. Including a correction or bonus token, expected committed tokens per round are:

$$E[N]=1+\alpha+\alpha^2+\cdots+\alpha^\gamma.$$

These are the simplifying conditions used in Section 3.1 of the original paper. When acceptance varies by position and task, measure actual tokens committed per round rather than inserting an overall average acceptance rate without checking those conditions.

The following timings are all hypothetical: ordinary target decode takes 10 ms per token, $\gamma=4$, a whole target verification round takes 12 ms, and state handling takes 2 ms. With draft cost $d$ ms per token and no overlap between these stages, a cycle costs $4d+12+2$ ms. For a sufficiently long generation, dividing that budget by $E[N]$ gives the long-run average time per token.

gamma = 4
baseline_ms = 10
verify_ms = 12
state_ms = 2
for alpha, draft_ms in [(0.8, 1), (0.9, 3)]:
    expected = sum(alpha ** j for j in range(gamma + 1))
    cycle_ms = gamma * draft_ms + verify_ms + state_ms
    per_token = cycle_ms / expected
    speedup = baseline_ms / per_token
    print(f'alpha={alpha:.1f} tokens={expected:.4f} cycle_ms={cycle_ms} '
          f'ms/token={per_token:.3f} speedup={speedup:.3f}x')

alpha=0.8 tokens=3.3616 cycle_ms=18 ms/token=5.355 speedup=1.868x
alpha=0.9 tokens=4.0951 cycle_ms=26 ms/token=6.349 speedup=1.575x

The first draft costs 1 ms per token; the second costs 3 ms. The second commits more tokens on average but runs slower: about 1.575 times baseline speed, compared with 1.868 for the first. Real verification time can also vary with candidate count, batch size, context, and tree shape. Insert measured costs before tuning draft length; acceptance, drafting speed, verification, and state handling belong in the same calculation.

Chains, trees, and self-speculation describe different choices

The September 21, 2026 DeepSeek-V4 adaptation preprint discusses linear chains and candidate trees. The original LayerSkip paper provides a concrete self-speculation example: training uses layer dropout and an early-exit loss; inference drafts with early layers, then verifies and corrects with the remaining layers. Good early exits therefore cannot be assumed for an arbitrary unadapted model.

Choice	Organization of candidates or computation	Cost to account for
Linear chain	One continuous candidate path per round	An early rejection wastes later candidates
Candidate tree	Several continuations branch from shared prefixes, with a bounded verification-node count	Tree-aware causal attention, branch state, and path commitment
Self-speculation	Part of the same model drafts; the full target computation verifies	Early-exit capability, compute reuse, and rollback

The first two rows describe candidate shape; the third describes where the draft comes from. A candidate tree ultimately commits one continuous path, with acceptance and sampling rules that must still preserve the target distribution. The chain's single-candidate correction rule cannot simply be applied to an arbitrary tree, and selecting the highest-probability branch is not target sampling. This differs from beam search, which explores prefixes to optimize a sequence score.

KV state must follow the accepted path

The KV-cache note explains reuse and compression. Speculation additionally requires cache contents to represent the committed prefix: remove a rejected suffix in a chain; in a tree, expose only the committed context and each node's ancestors, never sibling branches. Reuse shared prefixes and isolate temporary state after branching. If a newly sampled correction or bonus token has not yet passed through the model, compute its KV state later rather than reusing a rejected candidate's state.

Sections 2–4 of the DeepSeek-V4 preprint explain that CSA (Compressed Sparse Attention) and HCA (Heavily Compressed Attention) also compress history along the sequence. Branches can produce different compressed states, so a tree-shaped attention mask alone is insufficient. The implementation isolates branches in a temporary scratch pad, then refreshes the chosen path's KV, compressed state, and intermediate buffers. This compression across positions differs from MLA (multi-head latent attention), which reduces the width of each token's cached representation.

The paper tests DeepSeek-V4-Flash on eight NVIDIA GPUs, with verification budgets 5–8, batch sizes 1–64, and GSM8K, MBPP, and ShareGPT. It reports a peak decode-throughput improvement of about 18.5% over matched-budget linear speculation, on ShareGPT with s3_k2_d6 and batch size 4. That baseline already uses speculation. As budgets grow, accepted length can continue rising while throughput plateaus: branch management and state refresh consume the gains.

Compare matched workload and quality

The official vLLM documentation identifies medium-to-low QPS, memory-bound workloads as a setting for reducing inter-token latency. First check model, draft, and backend compatibility using local inference runtimes. Make two comparisons: speculation off versus on, then chains versus trees at a matched verification budget when linear speculation is already available.

Fix the target checkpoint, precision, tokenizer, prompt template, sampling and stopping rules, cache policy, hardware, and runtime version. Use the same prompt set and input-length distribution, record actual output lengths, and compare at the same concurrency or the same arrival rate in separate tests. Measure low-load latency separately from saturated throughput.

Record	How to interpret the gain
Committed tokens per round, candidate counts, and the acceptance-rate definition	Separate draft acceptance from useful output; total tree nodes are not accepted-path length
Drafting, verification, state-refresh time, and peak device memory	Check whether extra accepted tokens repay extra work; include draft weights and temporary branch state
Median and p95 TTFT, token intervals, and end-to-end latency	Speculation can emit bursts; average token speed hides gaps between bursts
Final output tokens/s, completed requests/s, errors, and timeouts	Rejected candidates do not count as useful throughput; retain failed requests
Accuracy, format validity, and completion rate on the same tasks	Distinguish preserved target sampling from quality changes due to precision, cache, or sampling settings

Acceptance measures how well the draft matches. Cycle time divided by committed tokens connects that match to speed. Report results with the measurement boundaries in inference performance to show whether savings occur in decode, the whole request, or the service as a whole.

My reading · Opened notes are remembered in this browser.