/Learn
Modules · Model serving · Coding pattern

Speculative Decoding Target-Draft Pair Verifier

PracticeCoding patternTier 2 · MechanismsApply15 minModel serving

You will be able to: implement the acceptance rule, and prove in a test that output still follows the target distribution.

Source: Leviathan et al., 2023 (ICML)

AI engineeringModules

Study with AI

Part 1 of 5

Basics

The whole idea first, then the terms the rest of this page uses.

1.1Whole idea

A small draft model guesses several tokens quickly. The large target model checks them all in one forward pass. Accepted guesses cost a fraction of normal decoding, and rejection sampling keeps the output statistically identical.

Why it matters

Modified rejection sampling accepts draft tokens without changing the target model's distribution.

1.2Key concepts

One idea per card, in plain words.

01Draft and target

The draft proposes tokens fast. The target decides, and only its distribution counts.

02Acceptance rule

Accept token x with probability min(1, p(x) / q(x)), where p comes from the target and q from the draft.

03Residual

On rejection, sample from max(0, p − q), normalised. It supplies exactly the probability that acceptance missed.

04Acceptance rate

Equals the overlap of the two distributions: the sum of min(p, q).

Part 2 of 5

Question

What exactly you must answer, and what to settle before you start.

2.1Question

Interviewer

Given target probabilities p and draft probabilities q, write one speculative step that returns a token whose distribution equals p exactly.

Part 3 of 5

Detailed answer

How it works, and how to build or explain it.

3.1Step by step

The mechanism, in the order you would explain it.

  1. Sample from the draft

    Draw x from q. In a real system the draft has already generated it.

  2. Accept or reject

    Keep x with probability min(1, p(x) / q(x)). Tokens the draft over-weights get rejected more often.

  3. Resample on rejection

    Draw from the normalised residual and discard the remaining draft tokens.

  4. Test the distribution

    Run many steps and compare frequencies with p. Averages hide bias, so test every token.

3.2Code

Working code for the core of it.

Accepting a speculative token

A small model guesses tokens, and the big model checks them. This rule keeps the output distribution exactly the big model's.

speculative-accept.tsTypeScript
1function sample(dist: number[], rand: () => number): number {2  let r = rand();3  for (let i = 0; i < dist.length; i++) {4    r -= dist[i];5    if (r <= 0) return i;6  }7  return dist.length - 1;8}9 10/**11 * One speculative step. The draft proposes x ~ q; the target accepts it with min(1, p(x)/q(x));12 * otherwise it samples from the leftover max(0, p - q). The output follows p exactly.13 */14export function speculativeStep(p: number[], q: number[], rand: () => number = Math.random) {15  const x = sample(q, rand);16  if (rand() < Math.min(1, p[x] / q[x])) return { token: x, accepted: true };17  const residual = p.map((pi, i) => Math.max(0, pi - q[i]));18  const mass = residual.reduce((a, b) => a + b, 0);19  return { token: sample(residual.map((r) => r / mass), rand), accepted: false };20}21 22/** Expected acceptance rate: the overlap of the two distributions. */23export const acceptRate = (p: number[], q: number[]) => p.reduce((sum, pi, i) => sum + Math.min(pi, q[i]), 0);
23 linesUTF-8TypeScript
Math.min(1, p[x] / q[x])
Accept the draft's token in proportion to how much the target agrees with it.
Math.max(0, pi - q[i])
On rejection, sample from what the draft under-weighted. This makes the maths come out exact.
acceptRate
The overlap of the two distributions, which predicts your speed-up.

Tested by npm run test:modules.

Part 4 of 5

Q&A

What interviewers ask next. Answer out loud, then open.

4.1Interview questions

Why does resampling use max(0, p − q)?
Accepted mass for token x equals min(p, q). The shortfall, p minus min(p, q), equals max(0, p − q). Adding them gives exactly p.
When does speculation hurt?
At low acceptance you pay for draft runs and rejected work. Under heavy batch load it can reduce throughput, so measure before enabling it.
Where do drafts come from?
A smaller model from the same family, n-gram lookup in the prompt, or a small speculator head trained on the target.
Part 5 of 5

Extra depth

Edge cases, counterpoints and what to read next.

5.1Edge cases and counterpoints

Includes the strongest argument against this approach.

Show detailsHide details
Cache rollback
Rejected tokens must leave both KV caches before the next step.
Batching
Requests accept different numbers of tokens, so sequence lengths drift apart within a batch.
Counterpoint
Speculation mainly improves latency at low load. Better batching often gives more throughput per dollar.
AI Engineer · Speculative Decoding Target-Draft Pair Verifier