Speculative decoding
AlgoLab runs no language model. The target and draft distributions below, and the token proposed at each position, were written by hand — shown in full in the Positions tab. A proposal is accepted or rejected by one fixed, computed rule. A real draft model’s vocabulary holds tens of thousands of tokens, not six.
accept the proposed token x with probability min(1, p_target(x) / p_draft(x))
Generates a short run of tokens using two distributions at each of several positions: a cheap draft distribution proposes one token per position, all at once, and a target distribution — the one that would otherwise be sampled from one token at a time — is then checked against each proposal in sequence. A proposal is accepted with probability min(1, target probability / draft probability); the first position where that check fails is rejected, a replacement is drawn from what the target distribution assigns beyond what the draft already covered, and every proposal after it is dropped unverified. When every proposal in a round is accepted, one further token is drawn fresh from the target distribution as a bonus.
Why it matters, and what it costs
This is the mechanism production language model servers use to generate text faster without changing what gets generated: a small, cheap model proposes several tokens, and the large, expensive model verifies them together instead of producing them one at a time. The saving only appears when verifying several positions costs about the same as producing one — true for a transformer forward pass dominated by loading its weights, not by how many new positions it scores — and the number of tokens kept per round depends entirely on how often the cheap proposals pass the target’s check.
How it works
- Start with an authored target distribution at each of several positions, and a draft distribution at the same positions.
- The draft proposes one token at every position, all before any of them are checked.
- Check each proposal in order: accept it with probability min(1, target probability of that token / draft probability of that token).
- At the first position that is not accepted, draw a replacement from the distribution left over once the draft’s own probability is subtracted from the target’s, floored at zero and rescaled to sum to one. Drop every proposal after that position; it is never checked.
- If every proposed position is accepted, draw one further token fresh from the target distribution.
Worth noticing
- A proposal where the target rates the token at least as likely as the draft did is accepted outright — the acceptance probability is capped at 1, never higher, so a draft assigning its own proposal a lower probability than the target does never causes a rejection by itself.
- A proposal the target assigns zero probability to is always rejected: the acceptance probability is exactly zero regardless of what probability the draft assigned it.
- Rejecting one position discards every proposal after it in the same round, even a later position whose own proposal would have been accepted had it been checked — the cost of a single rejection is not just that one token.
- The replacement drawn after a rejection is never the token that was just rejected: the residual distribution subtracts exactly the draft’s own probability for every token, including the rejected one, before anything is renormalised.
Where the numbers come from
Six tokens, a target distribution at five positions plus one bonus position, and two draft profiles over those same five positions — every entry an eighth, so every ratio and every residual is a small exact fraction a reader can check by hand. Held attools/speculative-decoding/src/data/profiles.v1.json and shown in full in the tool’s Positions tab. Nothing here was computed by a model, sampled from one, or derived from what a token means. One profile (“a closely aligned draft”) accepts every position outright; the other (“a divergent draft”) proposes a token at the third position the target assigns no probability to at all, which is always rejected — the fourth and fifth proposals are then discarded unverified, the cost of a single rejection landing on more than just the one token.
What rejection sampling guarantees, checked rather than asserted
if rejected, resample y from max(0, p_target(y) − p_draft(y)), renormalised to sum to 1. This is exact: min(p_target(y), p_draft(y)) + max(0, p_target(y) − p_draft(y)) = p_target(y), for every token y, whatever the draft distribution is — an algebraic identity, not an approximation, checked over both authored profiles and over 5,000 randomly generated distribution pairs intools/speculative-decoding/test/speculative-decoding.test.ts. The realised sampler is then checked numerically against what that identity promises: run thousands of times with fresh random draws, the committed token's own histogram converges to the target distribution, at every position of both shipped profiles and across twelve further randomly generated agreement profiles the shipped data never reaches — confirming the acceptance criterion stated in docs/ROADMAP.md §4: speculative decoding produces the identical output distribution to generating one token at a time from the target alone, for every agreement profile, not merely a run that happens to look similar.
Expected tokens committed per round, and the speedup figure
The accept probability at a position is a property of the two distributions there, averaged over every token the draft might propose — not a statistic of the one token a specific run happened to draft. From that, the expected number of tokens committed per round (including the bonus token a fully-accepted round earns) is computed directly: 3.92 for the closely aligned profile, 2.62 for the divergent one, out of five proposed positions each. Comparing against generating one token at a time, which costs exactly one unit per committed token, and assuming — stated plainly as an assumption, not measured from any real pair of models — that a draft step costs a tenth of an ordinary target step and that verifying every drafted position in a round costs the same as one ordinary target step, the two profiles come out at 2.62× and 1.75×respectively. Computed in and checked bytools/speculative-decoding/test/speculative-decoding.test.ts, including against a second, independent derivation from the sum of accept-probability partial products.
What this does not show
One target distribution and two draft profiles, over five positions and a six-token vocabulary. It does not show batching several requests' drafts together, speculative trees (proposing more than one candidate per position), or how a real draft model is trained or chosen to track a real target model. A real draft model's vocabulary holds tens of thousands of tokens, not six, and a real deployment measures its own speedup from real latency, not from the stated cost-model assumption this page uses.
Cost
- Best case: every proposal accepted
- O(k) target steps for k tokens, when every proposal is accepted
- Average case
- between O(1) and O(k) target steps for k tokens, depending on how often a proposal is accepted
- Worst case: the first proposal rejected
- O(k) target steps for k tokens, the same as generating one at a time
- Extra space
- O(k)
k is the number of positions proposed in a round.
Unlike every Track A tool here, this one has no ceiling and no input to refuse. The vocabulary and the position count are fixed by the data file, so the frame count — one propose frame, one verify frame per position actually attempted, one bonus frame only if every position was accepted, one closingdone frame — is a closed form of the chosen profile's own content: eight frames for the closely aligned profile, five for the divergent one, and never more than eight for either shipped profile. The only reader-facing setting is a choice between the two profiles; what is validated instead is the data file itself, at load, because that is the part a person could edit.
Source
Leviathan, Kalman & Matias, “Fast Inference from Transformers via Speculative Decoding” (2023) proves that the committed token’s distribution exactly equals the target model’s own, whatever the draft is; Chen et al., “Accelerating Large Language Model Decoding with Speculative Sampling” (2023) reaches the same result independently. The cost-model assumption this tool’s speedup figure uses — verifying several drafted positions costs about the same as one ordinary target step — is Leviathan et al.’s own simplifying assumption, not a measurement of any specific pair of models.