Supply exactly the target mass missing from accepted proposals

Accepted proposals contribute min(p(x), q(x)) to each token's unconditional output mass. Subtracting that from p(x) gives max(0, p(x)−q(x)), the mass still required. Its sum Z is exactly the rejection probability 1−α because p and q are normalized. When Z>0, divide those nonnegative values by Z to form the correction distribution r. Draw the correction with fresh randomness so its conditional law given rejection and the current history is r. The correction can assign mass to tokens that q never proposes, which is how the algorithm preserves target support without requiring a full-support draft.

The residual is attached to the current verified history. In a block, once the first rejection occurs, use p and q from that position and discard downstream speculative states that assumed the rejected token. The replacement is sampled once from the residual, then subsequent generation conditions on the replacement. Do not keep testing later proposals as though they followed the corrected prefix. The normalized residual is not a distribution over only the rejected token or over whichever candidates happened to be in a small tree; it is defined over the target's stated vocabulary domain.

A token can emerge by being proposed and retained, or by being selected after a rejection. The first contribution is min(p, q); the second is Z times r. Their sum is p token by token, giving the exact one-step law under the stated probability and random-draw assumptions. Inductively applying the valid conditional rule after every committed prefix preserves the autoregressive target law, with matching stop semantics. This argument concerns distributions, so it does not require the same pseudorandom seed to produce the same text as an ordinary sampler using a different sequence of random draws.

If Z=0, normalized finite p and q are identical and the ideal proposal is accepted with probability one. No rejection event occurs and the residual 0/0 is never evaluated. An implementation should follow the appropriate nonrejection branch rather than add a numerical floor and claim the resulting fallback is part of this proof. If a finite-precision path reports rejection together with a zero residual sum, that is a numerical or consistency case requiring explicit investigation. For disjoint supports, α=0 and Z=1, so every proposal is rejected and r=p; correctness remains possible even though speculation provides no acceptance benefit.

Test simple finite distributions where the entire output law can be enumerated, including equal distributions, disjoint support, partial zeros, and near equality. Check that every residual probability is nonnegative and sums to one when its branch is reachable. Preserve the actual processed p and q used for proposing and checking. Small numerical errors can be important when Z is tiny because normalization magnifies them. Pin dtype and backend, compare with a precise reference on small cases, and distinguish tolerances in implementation testing from the mathematical identity itself.

The probability lab displays the residual's two positive outcomes in the example below. Reset, set both lab success p=0.75 and n=1, predict the B/C bars, then inspect. Interpret success as B and failure as C; A has zero residual mass and is outside this two-outcome display. This is an exact Bernoulli visualization of a stipulated conditional residual, not a rejection sampler or a three-token model. Multiply the displayed probabilities by the separately calculated rejection probability before adding accepted masses to recover the unconditional target vector.