给开源教程修了个 demoFixing a Tutorial Demo: An Open-Source PR Retrospective

In The KV-Cache Memory Ledger, I accounted for where the memory goes with formulas. The tutorial itself is well written, but while reading its third companion experiment (Tutorial 03: KV-Cache) I found that the §5 Paged Attention demo printed identical results for all three configurations. So I opened an issue, wrote a PR to rewrite it. This post documents the whole ride.

1. What Was Wrong with the Demo: an Experiment That Couldn’t Fail

Section 5 wants to show the value of PagedAttention: carve the KV-Cache into fixed-size blocks, allocate on demand, and waste far less than statically reserving whole segments. But the demo printed this:

Three page sizes, identical results. It did not break (no error), but it demonstrated nothing. This is the most dangerous kind of bug: “it looks like it runs” and “it actually demonstrates the idea” are two different things.

2. Cause: Four Coincidences Stacked on Top of Each Other

It was not a single point of failure; four things collided:

#4 is the killer: even with the batch cap and the divisibility problem removed, the output still would not vary with page size — because the solver being demoed does not distinguish allocation strategies at all. Conclusion: this demo needed a rewrite, not a patch.

3. The Rewrite: Let the Experiment Tell the Theory Itself

The PR’s idea was to drop the engine call and replace it with a self-contained analytical simulation: two small allocators sharing one KV budget —

• Static contiguous: every request reserves a whole max_seq slot; simple but wasteful;
• Paged block pool: fixed-size blocks allocated on demand, with a block table;

Fed the same long-tailed request stream (fixed random seed, reproducible), so each of the four problems above got its own experiment:

1. Internal fragmentation: 77.8% waste for static reservation vs 0.4% for 16-token pages; concurrent users 65 → 314;
2. External fragmentation: after churn, the static first-fit allocator hits 97.1% fragmentation and admits 0 of 10 fresh 8K requests despite free space; paged admits 10/10;
3. Page-size sweep (8→1024 tokens): the trade-off between waste and block-table bookkeeping;
4. Prefix sharing: 8 requests sharing a 1K system prompt cut peak KV by 58%.

Every conclusion is directly visible in a table, and every number is reproducible. After the PR landed, the maintainer Vijay Janapa Reddi replied quickly: “diagnosis is spot on and the new demo actually shows the idea” — then he pushed a small fix and merged.

4. The Merge: More Honest Code

Before merging, the maintainer made one more round of changes on top of my commit. Each one is worth studying:

1. The cutoff: stop at the first request that does not fit, instead of feeding the whole stream.

My version fed all 100,000 requests to the allocator — including the ones arriving after memory was exhausted. PagedAllocator.admit() internally rejects requests that do not fit, so short requests after a rejected long one kept getting in; the allocator “picked its food” and the numbers flattered. The maintainer changed it to:

def fill(alloc, lengths):
    """Admit requests in arrival order; stop at the first one that does not fit."""
    for t in lengths:
        if not alloc.admit(t):
            break
    return alloc

Cut off in arrival order. It makes the experiment more “honest”: in a real system, requests keep coming whether you have memory or not, and an allocator should not quietly accept short requests after refusing long ones.

2. Shrink the numbers; embrace the less pretty truth.

My version: 314 users, 1.78x throughput speedup. After the merge: 259 users, 1.47x. The difference is exactly what the “food-picking” had fed. The maintainer preferred a plain but true number over a pretty but cheating one.

5. Three Takeaways from Being Edited

1. Demo code is ground zero for “looks like it runs”. Crashes and errors get caught instantly; an experiment that prints numbers on every row can be demonstrating nothing. Before writing a demo, ask: does this output actually vary with the independent variable, and by how much?

2. Honest experiments cut off in arrival order. Feeding the whole stream gives the allocator a choice it should not have. In any queuing/allocation simulation, stop at the first failure; otherwise you are measuring a “food-picking allocator”, not the allocator.

3. Modeling granularity decides how far a conclusion travels. A fixed 0.6 speedup factor means the “allocation-strategy benefit” dimension is distorted inside the engine — conclusions only hold within that granularity. Understanding what a tool decouples beats memorizing its output.

6. References

• Issue: #2134 Paged Attention demo returns identical results for every page size
• PR: #2135 fix(mlsysim): redesign §5 Paged Attention demo in KV-Cache tutorial (merged)
• Related post: The KV-Cache Memory Ledger — my study notes for tutorial 03; that is where I ran into this demo.

If this retrospective helps you, feel free to reach out.

• Previous
  KV-Cache 的显存账本：长上下文、并发与量化剪枝的取舍The KV-Cache Memory Ledger: Long Context, Concurrency, and the Quantization–Pruning Trade-off
• Next
  GPU 为什么会挨饿：数据墙、投机解码与设计空间探索Why Does the GPU Starve: The Data Wall, Speculative Decoding, and Design-Space Exploration