Unit 5.7 · about 2 h
324 / 324Beyond one cache: prefix sharing, paging and speculation
Single-request caching stops at the serving door. Shared prefixes, paged blocks and draft verification are the vocabulary that later tracks use to reason about real serving.
- explain
You can now
- Explain prefix sharing, paged blocks with block tables and copy-on-write vocabulary without implementing a server.
- Explain the speculative-decoding promise (draft guesses, target verifies in parallel) and its exactness contract (output equals target-only sampling).
- Draw a small block-sharing diagram for a shared prefix and a divergence.
Covers
- Prefix sharing and paged-cache vocabulary
- Speculative decoding promise and exactness contract
- One small prefix-sharing state diagram
Study, in this order
3 steps
- CS336 Lecture 10: paged attention and speculative samplingStanford CS336 - Lecture 10 Inference
paged_attention(blocks, fragmentation, sharing the system prompt and parallel samples, copy-on-write at block level) andspeculative_sampling(draft \(p\) guesses 4 tokens with target \(q\) verifying in parallel, exact-sample guarantee with the \(\{A,B\}\) proof, 70B/8B and 8B/1B pairs, Medusa and EAGLE) - Modern LLM Notebook 21 Section 7: PagedAttention wasteModern LLM Notebook - KV cache and inference acceleration
Section 7 (contiguous versus paged diagram with fixed-size pages,
simulate_memorywithblock_size16 showing paged waste 3 to 5 percent versus contiguous 13 to 20 percent) - Modern LLM Notebook 23 Sections 2 and 3: acceptance and exactnessModern LLM Notebook - KV cache and inference acceleration
Section 2 (draft guesses \(K\) tokens, target verifies in one pass) and Section 3 (
accept_probas \(\min(1, p_{\text{target}}/p_{\text{draft}})\)) with Exercise 1 (0.5 versus 0.8 giving 1.0)Depth · Do Sections 2 and 3 and Exercise 1 only. Skip Exercises 2 and 3: their expected-token formula drops the extra token the target always contributes, so their numbers disagree with the \(K+1\) ceiling. Skip draft-model training and variants; they belong to later tracks.
Focus on
- Sharing needs exact token equality on the prefix. One differing token ends sharing after that point, and only later blocks diverge.
- Pages are fixed-size blocks with a table from logical to physical positions. Waste per sequence caps at \(\text{block\_size}-1\) instead of \(\text{max\_len}-1\).
- Forks share prefix pages and copy on write. Only the diverged block is copied, not the whole prefix.
- Speculation is exact: the acceptance ratio plus the residual correction reproduce target-only sampling. Speed depends on draft quality, not on luck.
Reproduce closed-book
block_size 4, show the copy-on-write step on divergence, and state the speculative exactness contract with the acceptance formula.Traps
- Treating speculative decoding as approximate sampling. Unverified draft tokens change the distribution; only the accept plus correction loop preserves it.
- Expecting sharing across different prefixes. Similar text with different token ids shares nothing; the match is on tokens, not meaning.
- Paging away the math. Blocks only relocate storage; attention still gathers the same \(K\) and \(V\), so outputs must match contiguous storage exactly.
Practice
Modern LLM Notebook 23 Exercise 1: acceptance probability
Exercise 1 (acceptance probability for draft 0.5 versus target 0.8, asserting 1.0)
Skip Exercises 2 and 3, whose expected-token formula is off by one token. Then compute the expected tokens per pass for \(K=4\) at acceptance 0.5 and 0.8 with the \(K+1\) form, and draw the 8-token shared-prefix diagram from the reproduce step.
Self-test
-
Two requests share an 8-token system prefix with
block_size4. How many physical prefix blocks with sharing versus without?2 shared blocks versus 4 (2 per request). Sharing saves half the prefix memory, and a divergence copies only the affected block. -
Draft assigns token \(A\) 0.5 and target assigns 0.8. What is the acceptance probability?
\(\min(1, 0.8/0.5)=1.0\), so always accept. -
A draft proposes \(K=4\) tokens and each is accepted with probability 0.5, independently. How many tokens does one target pass yield on average, and what is the ceiling?
\((1-0.5^5)/(1-0.5)=1.94\), counting the token the target always adds after the last accepted draft token. A perfect draft gives \(K+1=5\). Notebook 23's exercises use \(1-\alpha^K\) and drop that token, so trust the \(K+1\) form. -
Does speculative decoding change the output distribution?
No. With the residual correction it is exact and equals target-only sampling. It changes speed, not the distribution.
Completion criterion
Stop when
Exercise 1 passes, your expected-token numbers use the \(K+1\) form, and your diagram shows shared blocks plus the copy-on-write step with the exactness contract stated.
Only mark this when you can do it without notes.Comes after
- 5.5 Two regimes: prefill and decodeSee how paging and speculation change the picture.
- 5.6 Measuring time to first token and inter-token latencyPlace sharing and speculation after solid measurements.
Resources for this unit
- Modern LLM Notebook - KV cache and inference acceleration Use the KV-cache portions of English notebooks 11-mla-kv-cache and 21-inference-acceleration. Skip MLA and advanced acceleration as core work. Recalculate cache sizes and verify timing after warmup and explicit synchronization.
- Stanford CS336 - Lecture 10 Inference Use the Spring 2026 inference lecture to connect KV arithmetic, phase behavior and batching vocabulary. Keep kernels, distributed serving and expensive performance experiments for the later tracks.
Also in this section
- LLMs from Scratch companion - KV cache and GQA Use ch04/03_kv-cache and ch04/04_gqa with the chapter model code. Add explicit per-layer ownership, position offsets, variable lengths, EOS compaction and MHA-versus-GQA cache arithmetic to the runnable comparison.
- How to Scale Your Model - inference chapter After cache equivalence and phase measurement pass, read the inference chapter for arithmetic intensity, parallelism and production-scale reasoning. Treat it as the handoff to inference and performance tracks, not required foundation work.
- AI Performance Engineering - inference-engine bridge Use Sections 4 and 5 only after this gate to choose the next inference, KV-cache, scheduling, quantization or distributed-serving resource. Do not treat its GPU and kernel material as unfinished LLM Foundations work.
- No Magic - micro KV or paged-cache simulation Use one small CPU simulation such as microkv.py or micropaged.py only to visualize state ownership. Do not present Python timing as GPU or serving-performance evidence.