How a cheap draft and parallel target verification accelerate autoregressive generation, with an exact two-token sampling correction.
Speculative decoding
Speculative decoding accelerates autoregressive generation by letting a cheaper draft model propose tokens and a target model verify them in a block. With the exact sampling correction, the output follows the target's configured distribution. For a quant research assistant using a large language model to process financial text, the potential benefit is lower generation latency; it does not make the model's answers more reliable. Leviathan, Kalman and Matias describe the method.
Propose a block, keep a prefix
Ordinary autoregressive generation waits for each sampled token before generating the next. Once a short draft is available, a causal transformer can score its positions in parallel, each conditioned on the prompt and preceding draft tokens. Verification still proceeds left to right: keep the accepted prefix, replace the first rejected token using a corrected draw, and discard the remaining draft. If the whole block is accepted, draw an additional token from the target. See Chen et al., §§4.1–4.2.
The target's scores after a rejected proposal were conditioned on a continuation that will no longer be used. They cannot simply be retained after inserting a different token.
Why a rejection needs a special draw
At one fixed prefix, let p(x) be the target's next-token distribution and q(x) the draft's. Draw a proposal x from q and accept it with probability
a(x)=min(1,q(x)p(x)).
For rejection, draw from the normalised positive difference:
r(x)=∑ymax(p(y)−q(y),0)max(p(x)−q(x),0).
Only proposed tokens need the ratio, so its denominator is positive. If the two distributions coincide, every proposal is accepted and the residual is unnecessary. These are conditional probabilities at the same prefix, not unconditional token frequencies. This modified rejection-sampling construction is established in Leviathan et al., §2.3 and Appendix A.1.
Consider a fictional vocabulary containing only A and B:
Token
Target probability
Draft probability
Acceptance given proposal
Accepted probability mass
A
0.6
0.8
0.75
0.6
B
0.4
0.2
1
0.2
Acceptance contributes 0.8 in total. Rejection occurs with probability 0.2, entirely from A proposals. The positive target-minus-draft difference is zero for A and 0.2 for B, so the residual draw always returns B. The final probabilities are therefore A: 0.6 and B: 0.4, exactly matching the target.
Fictional two-token example at a fixed prefix: draft mass A 0.8 and B 0.2 becomes accepted mass A 0.6 and B 0.2, with rejection mass 0.2. The residual always draws B, restoring final target mass A 0.6 and B 0.4.
Original finite example. The hatched B segment is the unconditional probability mass supplied by the residual draw, not an additional draft proposal.
Redrawing from the unadjusted target after rejection would instead give A probability 0.6+0.2×0.6=0.72 and B probability 0.2+0.2×0.4=0.28. The correction supplies missing mass rather than adding a fresh copy of the entire target distribution.
Distributional exactness has conditions
The baseline above assumes a common token vocabulary, correctly evaluated conditional distributions and independent acceptance randomness. Temperature or vocabulary filtering must be reflected in the distributions used for correction. The guarantee concerns the configured decoding distribution, subject to numerical precision; it does not promise the same sampled string from a fixed seed. The stochastic example is not a greedy token-matching algorithm. Chen et al., §4.2.
Latency gains depend on draft cost, acceptance, block length and hardware. Parallel scoring must save enough time to cover drafting and discarded work. An 80% acceptance probability in this example is not an 80% speed improvement. Leviathan et al., §3.3.
