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.
Modified rejection sampling accepts draft tokens without changing the target model's distribution.
1.2Key concepts
One idea per card, in plain words.
The draft proposes tokens fast. The target decides, and only its distribution counts.
Accept token x with probability min(1, p(x) / q(x)), where p comes from the target and q from the draft.
On rejection, sample from max(0, p − q), normalised. It supplies exactly the probability that acceptance missed.
Equals the overlap of the two distributions: the sum of min(p, q).
Question
What exactly you must answer, and what to settle before you start.
2.1Question
Given target probabilities p and draft probabilities q, write one speculative step that returns a token whose distribution equals p exactly.
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.
- Sample from the draft
Draw x from q. In a real system the draft has already generated it.
- Accept or reject
Keep x with probability min(1, p(x) / q(x)). Tokens the draft over-weights get rejected more often.
- Resample on rejection
Draw from the normalised residual and discard the remaining draft tokens.
- 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.
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);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.
Q&A
What interviewers ask next. Answer out loud, then open.
4.1Interview questions
Why does resampling use max(0, p − q)?
When does speculation hurt?
Where do drafts come from?
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.