Speculative Decoding · L4 Foundations

Proving speculative decoding is exactly lossless, and modeling its expected speedup.

Claim

Accepted/resampled tokens
Have distribution p (target model)
For every position, exactly

Proof idea

Decompose p as accept-mass + residual-mass
Rejection sampling recovers p exactly
True regardless of how good q is

What we're proving and how.

Claim: for any draft distribution $q$ and target distribution $p$ over the same support, the token produced by (a) sampling $x \sim q$ , (b) accepting with probability $min (1, p (x) / q (x))$ , and on rejection (c) sampling instead from the normalized residual $max (0, p - q)$ , has distribution exactly $p$ — regardless of how good or bad $q$ is.