Walk through KV-cache updates when speculative decoding rejects some draft tokens

Speculative decoding has a small draft model propose several candidate tokens at once, then a large target model verifies them in a single parallel pass. The cache bookkeeping is the part most people miss. Suppose the draft proposes 5 candidates. The target runs one forward pass over those 5 positions and, because it needs the per-position logits to verify, it also computes K and V at each of those positions. Those K and V get appended to the target's KV cache as part of the forward pass. Next, an acceptance test runs from left to right. The first rejection ends the streak. Say positions 1, 2, 3 are accepted and position 4 is rejected. The committed sequence ends at position 3, plus one corrected token resampled at position 4. Now you have to clean up the cache. Positions 4 and 5 in the cache hold K and V for tokens that are not in the final sequence. They must be removed. On a paged cache (vLLM) you free those pages; on a contiguous buffer you rewind the write pointer. The next decode step then sees a cache that matches exactly what a plain autoregressive decoder would have produced.

**Speculative decoding** is exact because the cache invariant is preserved every cycle: at the end of the cycle the cache holds K and V for exactly the committed sequence, no more, no less. The cycle itself goes like this. The draft model autoregressively proposes K candidates, say K equals 5. The target model runs one parallel forward pass over those 5 positions, producing logits and (as a side effect) K and V at each position. Those K and V get provisionally appended to the cache, you need them to score each position. Now the acceptance test runs left to right. At each position you compare the target distribution to the draft distribution using modified rejection sampling. The first rejection ends the run. Suppose positions 1 through 3 are accepted and position 4 is rejected. The cache rollback then truncates back to position 3. On a paged cache (PagedAttention) that means freeing the pages covering positions 4 and 5; on a contiguous cache it means rewinding the write pointer. After resampling a corrected token at the rejected position from the residual distribution (target minus draft mass) and committing one bonus token, the cycle restarts. The output distribution is provably identical to non-speculative target decoding, that's the whole reason the technique is exact.