The exact decoding shortcut that burns compute when guesses miss

Large language models generate one token, append it, then run again. That serial loop leaves modern accelerators waiting on memory traffic. Speculative decoding borrows branch prediction from processors: let a cheap draft model guess several tokens, then ask the expensive target model to verify the whole guess in one parallel pass.

A good guess turns one target-model call into several output tokens. A bad guess is discarded. The surprising part of Leviathan, Kalman, and Matias's method is that this shortcut does not approximate the target distribution—the correction step makes it exact.

Let q be the draft's next-token probabilities andp the target's. A proposed token is accepted with probability min(1, p/q). Where the draft assigns too much probability, some proposals are rejected. The replacement is sampled only from the target's leftover mass: max(0, p − q), normalized.

def correction_distribution(target, draft):
    excess = [max(0, p - q) for p, q in zip(target, draft)]
    rejected_mass = sum(excess)
    if rejected_mass <= 1e-15:
        return target[:]
    return [value / rejected_mass for value in excess]

The site runs the tested TypeScript implementation; Python and C++ are faithful translations of the same correction. For the tiny example below, the draft over-proposes token B, so rejected B proposals are corrected to A.

The maximum numerical difference is 1.1e-16. More generally, the chance of accepting a draft token is the overlap Σ min(p, q)—one minus total-variation distance. Exactness holds even for a terrible draft; usefulness does not.

If the average acceptance rate is α and the draft proposesγ tokens, one target pass emits an expected1 + α + α² + … + αγ tokens. The paper's wall-time model divides that gain by 1 + γc, where c is one draft step's latency relative to one target step.

Here is the buried bill. Verification evaluates several target positions concurrently. When an early guess fails, later work is wasted. With five guesses and negligible draft arithmetic, low agreement can use almost five times the operations per emitted token even while reducing serial target calls.

These are implementation- and hardware-specific measurements, not our analytical chart. The authors used existing checkpoints and found draft acceptance between 0.53 and 0.75 in the four highlighted T5-small runs. In our deliberately mismatched two-token example it is 60%.

• Choose lookahead per token instead of fixing it for a whole run.
• Measure energy and throughput, not latency alone.
• Stress acceptance after domain, language, and temperature shifts.

To inspect the autoregressive target and its key-value cache mechanics, poke at the interactive transformer page.