How can speculative decoding preserve the target distribution?

The bottleneck

Calling a large model token by token incurs sequential cost. A cheaper draft proposes several tokens and the target verifies their positions in one forward pass. Sufficient acceptance advances multiple tokens per expensive step.

The mechanism

With target p and draft q, accept a proposed token with min(1,p/q). On the first rejection sample from the normalized positive residual max(0,p−q), discarding later draft tokens. The complete algorithm preserves the target distribution under its assumptions; simply picking the target’s favorite draft does not.

α(x)=min(1,p(x)/q(x));  p_correct(x) ∝ max(0,p(x)−q(x))

Examples and evidence

Example: p=(0.6,0.4), q=(0.8,0.2). The first token is accepted with 0.75 and the second with 1. Rejected mass is corrected to the second token, recovering p. Google reports its use in AI Overviews, not uniform acceleration for every request.

New constraints

Gains depend on draft cost, acceptance, verification batch and server load. Temperature, truncation and numerical implementation must agree with the defined target distribution. High concurrency, low acceptance or costly drafts can erase the gain.