E7.4 · LESSON 4 OF 6

Expected progress

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

THE IDEA

How many tokens per verification?

Suppose each drafted token is accepted independently with the same probability a (a simplification for teaching). A verification of k drafted tokens then yields the accepted ones plus one token that the target supplies itself, for an expected 1 + a + a² + … + a^k = (1 − a^(k+1)) / (1 − a) tokens. With a = 1 and k = 4 that is 5. With a = 0.8 it is 3.3616.

acceptance rate a0.8drafted tokens k4

accepted	probability
0	0.2
1	0.16
2	0.128
3	0.1024
4 (all)	0.4096

expected tokens per verification = 1 + a + … + a^k = 3.3616 (accepted tokens + the one extra token the target always supplies) This assumes each token is accepted independently with the same probability: a teaching approximation.

Change a and k. The table is the probability of each number of accepted drafts.

Predict first. With acceptance one and four proposals, what is the ideal produced-token count?

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

Evaluate the formula for a few acceptance rates, then write it and confirm it by simulation.

acceptance rate a0.8drafted tokens k4

accepted	probability
0	0.2
1	0.16
2	0.128
3	0.1024
4 (all)	0.4096

a = 1, k = 4 a = 0.8, k = 4 a = 0.5, k = 4

To do: With acceptance rate 1 and k = 4 drafted tokens, the expected number of tokens produced per verification (including the bonus token)?
To do: With a = 0.8 and k = 4: 1 + 0.8 + 0.8² + 0.8³ + 0.8⁴ = (1 − 0.8⁵)/(1 − 0.8). Type it (4 decimals)
To do: With a = 0.5 and k = 4 (4 decimals)?

Part 2. Do it in code

expected_tokens(a, k): the expected number of tokens produced per verification when each drafted token is accepted independently with probability a: 1 + a + a² + … + a^k. Handle a = 1 (k + 1). a must be in [0, 1] and k >= 0 (ValueError).
accepted_distribution(a, k): the probability of exactly n accepted draft tokens for n = 0 … k: a^n·(1 − a) for n < k and a^k for n = k. Return a list of k + 1 numbers that sums to 1.
expected_from_distribution(a, k): 1 + Σ n·P(n accepted)... computed from accepted_distribution (it should agree with expected_tokens: tokens produced = accepted + 1).
simulate(a, k, trials, seed): the average number of tokens produced per verification over `trials` random rounds (np.random.default_rng(seed)).

import numpy as np

def expected_tokens(a, k):
    pass

def accepted_distribution(a, k):
    pass

def expected_from_distribution(a, k):
    pass

def simulate(a, k, trials, seed):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

With acceptance one and four proposals, what is the ideal produced-token count?

AOne, since only the target's token counts.BFive: four accepted drafts plus the extra token from the same verification pass.CFour, since only the accepted drafts count.

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.