E7.2 · LESSON 2 OF 6

Acceptance tests

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

THE IDEA

The acceptance test

When decoding by sampling, comparing top choices is not enough. The standard exact method takes the drafted token x, with probability q(x) under the draft and p(x) under the target, and accepts it with probability min(1, p(x)/q(x)). If the target likes the token at least as much as the draft did it is always accepted; if the draft was over-confident it is accepted only sometimes. Averaged over what the draft proposes, the chance of acceptance is Σ min(p, q).

target probability p of the drafted token0.5draft probability q of that token0.8

accept with probability min(1, p/q) = min(1, 0.625) = 0.625 the draft was over-confident about this token: accepted only part of the time

token	p (target)	q (draft)	min(p, q)
0	0.5	0.25	0.25
1	0.3	0.5	0.3
2	0.2	0.25	0.2
chance a drafted token is accepted = Σ min(p, q)			0.75

Agreeing on the single top choice is not the full rule: the test uses the probabilities of the drafted token under both models, which is what keeps the final text exactly distributed like the target.

Change p and q for a drafted token, and see the table for a whole distribution.

Predict first. Is accepting whenever the target and draft top choices match the full sampling algorithm?

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 acceptance probabilities by hand, then write them and check the overall rate by simulation.

target probability p of the drafted token0.5draft probability q of that token0.8

accept with probability min(1, p/q) = min(1, 0.625) = 0.625 the draft was over-confident about this token: accepted only part of the time

token	p (target)	q (draft)	min(p, q)
0	0.5	0.25	0.25
1	0.3	0.5	0.3
2	0.2	0.25	0.2
chance a drafted token is accepted = Σ min(p, q)			0.75

Agreeing on the single top choice is not the full rule: the test uses the probabilities of the drafted token under both models, which is what keeps the final text exactly distributed like the target.

accept probability (q 0.8, p 0.5) (q 0.25, p 0.5) Σ min(p, q) for the table

To do: The draft proposes a token to which it gave probability q = 0.8 and the target gives p = 0.5. Acceptance probability min(1, p/q)?
To do: A token with q = 0.25 and p = 0.5. Acceptance probability?
To do: Target p = [0.5, 0.3, 0.2], draft q = [0.25, 0.5, 0.25]. The chance that a drafted token is accepted is Σ min(p_i, q_i). Type it

Part 2. Do it in code

accept_prob(p, q): min(1, p/q) for the target probability p and draft probability q of the drafted token (ValueError if q <= 0).
overall_acceptance(p, q): Σ min(p_i, q_i) over the two distributions.
propose_and_test(p, q, rng): draw a token from q with rng.choice, then accept it with probability accept_prob using rng.random() < that probability. Return (token, accepted).
empirical_acceptance(p, q, trials, seed): run propose_and_test `trials` times with np.random.default_rng(seed) and return the fraction accepted.

import numpy as np

def accept_prob(p, q):
    pass

def overall_acceptance(p, q):
    pass

def propose_and_test(p, q, rng):
    pass

def empirical_acceptance(p, q, trials, seed):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Is accepting whenever target and draft top choices match the full sampling algorithm?

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.