E7.5 · LESSON 5 OF 6

Time and speedup

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

THE IDEA

From tokens per round to speed-up

Speed is tokens produced divided by time. One round costs k draft steps plus one verification. In the chapter's numbers (a = 0.8, k = 4, 1 ms per draft step, 12 ms verification) a round takes 16 ms and yields 3.3616 tokens: 210.1 tokens/s against 100 tokens/s for the target alone (10 ms per token), a speed-up of about 2.1×.

More drafted tokens are not always better: each extra one costs time and is accepted less and less likely. And an expensive draft can erase the gain entirely.

acceptance a0.8drafted tokens k4ms per draft step1ms per verification12

round = 4 × 1 + 12 = 16 ms for 3.362 tokens throughput = 210.1 tokens/s vs target alone (10 ms/token) 100 tokens/s → 2.101×

k	tokens per round	ms per round	tokens/s
1	1.8	13	138.5
2	2.44	14	174.3
3	2.95	15	196.8
4	3.36	16	210.1
5	3.69	17	217
6	3.95	18	219.5
7	4.16	19	219
8	4.33	20	216.4
9	4.46	21	212.5
10	4.57	22	207.8

Orange bars are slower than not speculating at all. More draft tokens help only while each extra one adds more accepted progress than it adds drafting time.

Find the best k; then make the draft expensive.

Predict first. Can higher acceptance still produce no speed-up if the draft is expensive?

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

Compute the chapter's speed-up and find the best k by hand, then write the throughput model.

acceptance a0.8drafted tokens k4ms per draft step1ms per verification12

round = 4 × 1 + 12 = 16 ms for 3.362 tokens throughput = 210.1 tokens/s vs target alone (10 ms/token) 100 tokens/s → 2.101×

k	tokens per round	ms per round	tokens/s
1	1.8	13	138.5
2	2.44	14	174.3
3	2.95	15	196.8
4	3.36	16	210.1
5	3.69	17	217
6	3.95	18	219.5
7	4.16	19	219
8	4.33	20	216.4
9	4.46	21	212.5
10	4.57	22	207.8

Orange bars are slower than not speculating at all. More draft tokens help only while each extra one adds more accepted progress than it adds drafting time.

tokens/s (a 0.8, k 4, 1 ms, 12 ms) speed-up best k from 1 to 8 speed-up with 5 ms drafts

To do: a = 0.8, k = 4. Four draft steps cost 1 ms each and verification costs 12 ms: 16 ms per round that yields 3.3616 tokens. Tokens per second (1 decimal)?
To do: The target alone makes 1 token per 10 ms = 100 tokens/s. Speed-up (3 decimals)?
To do: With a = 0.8, 1 ms per draft step and 12 ms verification, which k from 1 to 8 gives the most tokens per ms?
To do: If each draft step cost 5 ms (an expensive draft) with a = 0.8, k = 4, one round takes 20 + 12 = 32 ms. Speed-up over 100 tokens/s (2 decimals)?

Part 2. Do it in code

expected_tokens(a, k) as in the previous lesson (1 + a + … + a^k; k + 1 when a = 1).
round_ms(k, draft_ms, verify_ms): k · draft_ms + verify_ms.
tokens_per_second(a, k, draft_ms, verify_ms): expected_tokens / round_ms · 1000.
speedup(a, k, draft_ms, verify_ms, target_ms): tokens_per_second divided by the target-only rate 1000 / target_ms.
best_k(a, draft_ms, verify_ms, k_max=16): the k in 1 … k_max with the highest tokens per second (the smallest k on ties).

def expected_tokens(a, k):
    pass

def round_ms(k, draft_ms, verify_ms):
    pass

def tokens_per_second(a, k, draft_ms, verify_ms):
    pass

def speedup(a, k, draft_ms, verify_ms, target_ms):
    pass

def best_k(a, draft_ms, verify_ms, k_max=16):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Can higher acceptance still produce no speedup if the draft is expensive?

ANoBYes

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.