Name the decoding law being preserved
Distinguish deterministic argmax agreement from stochastic distribution preservation, including tie rules, processed probabilities, and why plausible fallback rules can be biased.
On this page
The question for today
What you’ll understand
- State separate greedy-sequence and stochastic-distribution correctness claims.
- Explain why same-seed output equality is not the definition of sampling exactness.
- Calculate the bias from resampling the full target after partial acceptance.
A speculative decoder matches the target's greedy text on every test prompt, so the team declares its sampling mode exact. That conclusion does not follow. Greedy decoding preserves a deterministic argmax rule, while sampling must preserve all target probability mass, including less likely tokens. Different acceptance procedures can satisfy one claim and fail the other. Define the baseline decoding law and its numerical and stopping conventions before choosing a verification algorithm or deciding what a test result establishes.
Greedy verification follows a deterministic target path
Greedy decoding chooses the target's highest-probability token at each committed history, using a specified tie rule. A proposed token can be retained if it equals that choice; at the first mismatch, emit the target's chosen token and discard candidate descendants. This can preserve the baseline greedy sequence when the target conditionals, processors, tie behavior, and stopping rules match. A draft's own sampling or ranking method affects how often its tokens match, but does not authorize a different target greedy token. Tree verification must likewise follow the target's actual greedy path rather than whichever branch looks globally attractive.
Floating-point changes can alter a near tie even when two implementations use the same mathematical model. Pin model and tokenizer versions, logits processors, precision, and execution configuration, and report what equality is being tested. A deterministic target distribution can be represented as a point mass at its chosen token, but that is the greedy decoding law, not the unmodified softmax sampling law. Identifying these distributions separately avoids claiming that a sampler is exact merely because it consistently emits a high-probability answer.
Stochastic exactness concerns the full probability law
For target sampling, use a valid stochastic verifier and correction procedure at each history. The ratio-and-residual scheme preserves the processed p distribution under exact arithmetic and the required conditional randomness. A different correct construction can sample target tokens at candidate histories and keep a matching prefix, but its acceptance efficiency and random-number use differ. The proof belongs to the complete construction, not to a generic label such as assisted decoding. A heuristic rule that accepts every target-top-k proposal or relaxes a probability ratio changes the law unless a separate valid correction argument establishes otherwise.
Even exact stochastic algorithms need not produce the same text for one nominal seed because they consume random numbers in different orders and quantities. Conversely, many matching seeded strings do not prove distributional equality. Use analytic finite examples and statistical checks for the stochastic claim, and deterministic sequence checks for the greedy claim. Pinned Transformers 4.56.2 contains distinct assisted-generation branches depending on sampling mode and available candidate probabilities. Read the applicable path; its support and numerical behavior are implementation properties rather than a theorem covering every possible backend or generation feature.
Validate the claimed mode and stopping behavior
Include equal and nearly tied logits, zero-probability tokens introduced by constraints, early EOS, short maximum lengths, and mismatches at every proposal position. Apply the same target transformations and stop contract as the baseline. A decoder that emits a bonus token after accepted EOS can change the output law even if all earlier ratios were right. For approximate variants, report the changed acceptance rule and measure its consequences rather than presenting its speed as an exact-mode result. Quality similarity on a benchmark is a useful empirical finding but is not equality of probability distributions.
The probability lab separates a sampled law from a point mass. For each separate view, Reset, set both n=1 and lab p to 0.6 or 1, predict the two bars, then inspect. The first has masses 0.6 and 0.4; the second always selects the designated success outcome. This exact display contains no greedy verifier or model logits and does not test same-seed generation. It illustrates why replacing a nondegenerate target with its most likely token changes the target question, even when that token is the result people expect to see.
Work it through
A full-target fallback can overproduce the common token
At one fictional history, target p(A, B)=(0.6, 0.4) and proposal q(A, B)=(0.9, 0.1). A mistaken sampler uses the correct proposal acceptance ratios but redraws from the full p after any rejection.
Accepted masses are min(p, q)=(0.6, 0.1), givingα=0.7 and rejection probability 0.3.
The mistaken fallback adds 0.3p=(0.18, 0.12), so final output masses become(0.78, 0.22), not the intended(0.6, 0.4).
The correct positive-difference residual is entirely B, supplying the missing 0.3 mass there. Greedy target decoding would instead output A with probability one, a third clearly identified law.
The three laws are different: exact target sampling(0.6, 0.4), the mistaken mixture(0.78, 0.22), and greedy point mass(1, 0).
The living notebook
Explore the model
Interactive lab · probability
A greedy point mass is a different target law
For each view: Reset, set both n=1 and lab p, predict, then inspect. Compare p=0.6 and p=1: masses(0.4, 0.6) across failure/success become(0, 1). The p=1 law is degenerate. This instrument has no model, argmax tie rule, speculative verifier, or RNG trace.
- Mean · np
- 5
- Variance · np(1−p)
- 2.5
- Total probability
- 1
These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forState whether the intended baseline is greedy or stochastic. Probability mass away from the most likely token is part of the stochastic law.
Pause & reason
Check your understanding
Your turn
Try it yourself
For p=(0.5, 0.5) and q=(0.8, 0.2), compute the output of the incorrect full-target-after-rejection scheme.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Add accepted overlap masses to rejection probability times p.
Compare with the solution
The accepted masses are(0.5, 0.2), soα=0.7 and rejection mass 0.3. Adding 0.3p=(0.15, 0.15) gives(0.65, 0.35), differing from the intended target. The correct residual would put all correction mass on the second token.
Keep the idea
Take it with you
- Greedy and stochastic correctness are different claims with different tests.
- Exact sampling preserves the full declared processed target law.
- Fallback, stopping, numerical, and RNG semantics are part of the complete algorithm.
Read further
Original sources and deeper explanations to follow at your own pace.
- Leviathan et al.: Fast Inference from Transformers via Speculative Decoding, v 2
- Chen et al.: Accelerating Large Language Model Decoding with Speculative Sampling
- Transformers 4.56.2: Generation Strategies and Assisted Decoding
- Transformers 4.56.2: Assisted Generation and Speculative Sampling Implementation
- vLLM 0.10.2: Speculative Decoding, Compatibility, and Numerical Limits
- Cai et al.: Medusa Multiple Decoding Heads, v 3
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.