E7.1 · LESSON 1 OF 6

Draft and verify

Trace draft-and-verify decoding, explain distribution-preserving acceptance, and calculate a simplified speedup.

THE IDEA

Guess cheaply, check in one pass

Decoding is slow because the big model must run once per token. Speculative decoding uses a much cheaper draft to guess several tokens ahead, then has the big (target) model check all the guesses in a single pass. Guesses that the target agrees with are kept; at the first disagreement the target's own token is used and the rest of the guesses are discarded. One expensive pass can therefore yield several tokens.

draft proposes (cheap, not trusted):

7359

the big model, in ONE pass, would itself pick (change them to see the effect):

target at position 17target at position 23target at position 38target at position 41target at position 5 (bonus)2

accepted draft tokens: 2 emitted this round: [7, 3, 8] = 3 tokens at the first disagreement the target's own token replaces the draft's, and the rest of the draft is thrown away

Nothing from the draft is output before the target has checked it. Every verification yields at least one token.

The draft proposes 7 3 5 9. Change what the big model would pick.

Predict first. Can every draft token be emitted before verification in exact speculative sampling?

Chapter context

A cheap draft proposes several tokens and a target model verifies them with parallel work. The opportunity comes from amortizing an expensive target step, but drafting, verification and rejection recovery all cost time.

TRY IT YOURSELF

Part 1. Do it hands-on

Trace verification by hand, then write the verifier and a full speculative generator that must equal plain greedy decoding.

draft proposes (cheap, not trusted):

7359

the big model, in ONE pass, would itself pick (change them to see the effect):

target at position 17target at position 23target at position 38target at position 41target at position 5 (bonus)2

accepted draft tokens: 2 emitted this round: [7, 3, 8] = 3 tokens at the first disagreement the target's own token replaces the draft's, and the rest of the draft is thrown away

Nothing from the draft is output before the target has checked it. Every verification yields at least one token.

tokens produced (draft 7 3 5 9, target 7 3 8) draft tokens accepted tokens when all four agree

To do: A small draft model proposes 4 tokens [7, 3, 5, 9] in a row. The big model checks them all in ONE pass and (greedily) would itself have picked [7, 3, 8, …] at the first three positions. Draft tokens are accepted while they agree; at the first disagreement the big model's own token is emitted instead and the rest are discarded. How many tokens are produced by this one verification?
To do: How many of the draft's tokens were accepted in that case?
To do: If the big model agrees with all 4 draft tokens, the same verification pass also yields the big model's prediction for the NEXT position. How many tokens are produced?

Part 2. Do it in code

verify_greedy(draft, target_next): draft is the list of k proposed tokens. target_next has k + 1 entries: the target's own choice at each of the k positions, plus its choice for the position after the last draft token. Walk through the draft: while draft[i] equals target_next[i] the token is accepted; at the first mismatch emit target_next[i] and stop. If every draft token is accepted, also emit target_next[k]. Return the list of emitted tokens. ValueError if target_next does not have len(draft) + 1 entries.
accepted_count(draft, target_next): how many draft tokens were accepted.
speculative_generate(draft_model, target_model, prompt, n_tokens, k): both models are functions seq → next token (greedy). Repeat: draft k tokens one by one with draft_model, then compute target_model on each drafted prefix (this is the single verification pass), call verify_greedy, append the emitted tokens, until at least n_tokens tokens have been generated; return exactly the first n_tokens generated tokens. The result must equal plain greedy generation with target_model.

def verify_greedy(draft, target_next):
    pass

def accepted_count(draft, target_next):
    pass

def speculative_generate(draft_model, target_model, prompt, n_tokens, k):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can every draft token be emitted before verification in exact speculative sampling?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

Under constant independent acceptance a and k draft proposals:

E[N]=\sum_{i=0}^{k}a^i=\frac{1-a^{k+1}}{1-a}\quad(a\ne1).

At a=1 the sum is k+1. A simple speed estimate is $E[N]/(t_{verify}+k t_{draft})$ . Exact samplers use conditional probabilities; this constant-a model is not their full correctness proof.

Worked example

For a=0.8,k=4, expected produced tokens are 1+0.8+0.64+0.512+0.4096=3.3616. If target-only generation takes 10 ms/token, verification costs 12 ms and four draft steps cost 1 ms each, speculative throughput is 3.3616/0.016=210.1 tokens/s versus 100 tokens/s baseline: an illustrative 2.101× speedup.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
a,k=.8,4
expected=sum(a**i for i in range(k+1))
assert isclose(expected,3.3616)
assert isclose(expected/.016,210.1)
assert isclose((expected/.016)/(1/.010),2.101)
assert sum(1**i for i in range(k+1)) == 5

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Expected accepted draft tokens alone omit the final target token in this model. a=1 needs the finite-sum limit. A correctness-preserving acceptance rule is more than an agreement heuristic.