PagedAttention

Phase 7 · Document 04 · Production Serving Prev: 03 — Continuous Batching · Up: Phase 7 Index

Table of Contents

1. Why This Matters
2. Core Concept
3. Mental Model
4. Hitchhiker's Guide
5. Warmup Readings
6. Deep Readings and External References
7. Key Terms
8. Important Facts
9. Observations from Real Systems
10. Common Misconceptions
11. Engineering Decision Framework
12. Hands-On Lab
13. Verification Questions
14. Takeaways
15. Artifact Checklist

1. Why This Matters

PagedAttention is the memory-management trick that made high-concurrency serving affordable — the other half of vLLM's superpower alongside continuous batching (03). The KV cache is the scarce resource that caps how many users you can serve (Phase 6.02); PagedAttention lets you pack 2–4× more sequences into the same GPU memory by eliminating the waste in naïve KV allocation. Understanding it explains why vLLM exists, why your concurrency ceiling is what it is, and how server-side prefix caching (05) is even possible. It's also a beautiful, transferable systems idea: apply OS virtual-memory paging to the KV cache.

2. Core Concept

Plain-English primer: the problem with naïve KV allocation

Each request's KV cache grows one token at a time, up to its (unknown) final length (Phase 2.06). Naïve serving handles this by pre-allocating one big contiguous block per request, sized for the maximum possible context (e.g., 8k tokens). Three wastes result:

1. Internal fragmentation: a request that only generates 100 tokens still holds an 8k-token slab — ~98% wasted for that request.
2. Reserved-but-unused waste: memory reserved for tokens not yet generated can't be used by anyone else meanwhile.
3. External fragmentation: variable-sized contiguous blocks leave unusable gaps between them, like a fragmented disk.

The paper behind vLLM measured that naïve serving wasted 60–80% of KV memory this way. Since KV memory caps concurrency, that waste directly caps how many users you can serve.

The insight: page the KV cache like OS virtual memory

Operating systems solved the identical problem decades ago with paging: don't give a process one big contiguous chunk; give it small fixed-size pages on demand and use a page table to map logical addresses to scattered physical pages. PagedAttention applies this to the KV cache:

• The KV cache is split into fixed-size blocks (e.g., 16 tokens of K and V per block).
• A pool of physical blocks lives in GPU memory; blocks are allocated on demand as a sequence generates, and freed instantly when it finishes (03 admits a new request into the freed blocks).
• Each sequence has a block table mapping its logical token positions → scattered physical blocks. The attention kernel follows that indirection to gather K/V during the dot-product.

constexpr int BLOCK = 16;                          // tokens per block (a "page")
struct KVBlock { half K[BLOCK][HEADS][HEAD_DIM];    // physical block in the pool
                 half V[BLOCK][HEADS][HEAD_DIM]; };
KVBlock kv_pool[NUM_PHYSICAL_BLOCKS];               // the shared pool
int32_t block_table[NUM_SEQS][MAX_BLOCKS];          // per-seq: logical block → physical id
// attention gathers K/V block-by-block via block_table (an indirection, like a page table)

Because allocation is per-block on demand, a 100-token request uses ~7 blocks, not an 8k slab — internal fragmentation drops to <4% (at most one partially-filled block per sequence), and external fragmentation vanishes (all blocks are the same size). That recovered memory becomes more concurrent sequences.

The bonus: block sharing (copy-on-write) → prefix caching

Because KV is now in addressable blocks, two sequences that share a prefix can point their block tables at the same physical blocks — the shared prefix's KV is computed once and reused. This is copy-on-write sharing: if generations diverge, only the differing block is copied. It's the mechanism that makes server-side prefix caching (05) and parallel-sampling/beam efficient — multiple outputs from one prompt share the prompt's KV instead of duplicating it.

What it buys

• 2–4× more sequences in the same VRAM (waste 60–80% → <4%) → higher concurrency → lower cost/token.
• Near-100% KV utilization, which is why vLLM can run at high --gpu-memory-utilization (01).
• Enables prefix caching and efficient parallel sampling via block sharing (05).

3. Mental Model

   NAÏVE KV: one big CONTIGUOUS slab per request, sized for MAX context
     [■■■■□□□□□□□□□□□□]  ← 100 tokens used, 8k reserved → 60–80% wasted; gaps fragment

   PAGEDATTENTION: KV in fixed BLOCKS (pages) + a per-seq BLOCK TABLE (page table)
     seq A: table → [b3][b7][b1]      pool: a shared set of physical blocks
     seq B: table → [b3][b9]          ↑ B shares b3 with A (same prefix → copy-on-write)
     allocate on demand · free instantly · <4% waste · same-size blocks (no external frag)

   result: 2–4× more concurrent sequences in the same VRAM → the concurrency ceiling rises
           + block sharing = server-side PREFIX CACHING [05]

Mnemonic: OS virtual memory, applied to the KV cache. Blocks + a page table kill fragmentation and let prefixes be shared.

4. Hitchhiker's Guide

What to look for first: that your engine uses paged KV (vLLM/TGI/SGLang/TensorRT-LLM all do) and your KV utilization metric (vllm:gpu_cache_usage_perc). That number is your remaining capacity.

What to ignore at first: the block size and kernel internals — defaults (block=16) are well-tuned. You rarely touch them.

What misleads beginners:

• Thinking PagedAttention adds capacity for free without limit. It removes waste; the total KV pool is still finite and caps concurrency (Phase 6.02).
• Confusing it with continuous batching. They're complementary: continuous batching decides which sequences run each step (03); PagedAttention decides how their KV memory is stored. vLLM uses both.
• Assuming block sharing happens automatically across users. Prefix sharing needs the prefix to be identical and prefix caching enabled (05).
• Ignoring preemption. Under memory pressure the scheduler may evict/recompute or swap a sequence's blocks — a latency event worth knowing about.

How experts reason: they treat KV blocks as the capacity currency: concurrent_seqs ≈ KV_pool_blocks ÷ blocks_per_seq(context). They raise effective capacity by shrinking per-seq KV (lower --max-model-len, KV quant) and by block sharing (prefix caching), and they watch gpu_cache_usage_perc + preemption counts as the capacity/health signals.

What matters in production: KV utilization near 1.0 = at capacity (queue/scale); preemption/recompute events = thrashing under pressure; and the interaction with --max-model-len (bigger context = more blocks per seq = fewer seqs).

How to debug/verify: /metrics: gpu_cache_usage_perc (fullness), preemption counters, num_requests_waiting (KV-capped admission). Rising waiting + full cache = classic KV ceiling (01, 08).

Questions to ask: Does the engine page the KV cache? What's the KV pool size after weights? Block size? Is prefix sharing on? Does it preempt or reject at the limit?

What silently gets expensive/unreliable: oversized --max-model-len (blocks per seq balloon → fewer users), preemption thrash under pressure, and assuming compute (not KV) is your limit.

5. Warmup Readings

6. Deep Readings and External References

7. Key Terms

8. Important Facts

• Naïve KV allocation wastes 60–80% via internal/external fragmentation; PagedAttention cuts waste to <4%.
• It's OS paging applied to the KV cache: fixed blocks + a per-sequence block table (page table).
• Blocks are allocated on demand and freed instantly — feeding continuous batching's admission of new requests (03).
• Block sharing (copy-on-write) enables prefix caching and efficient parallel sampling (05).
• It removes waste, not the finite limit — KV pool still caps concurrency: seqs ≈ pool_blocks ÷ blocks_per_seq (Phase 6.02).
• It enables near-100% KV utilization, hence high --gpu-memory-utilization (01).
• PagedAttention ≠ continuous batching — complementary (memory layout vs scheduling).
• Under pressure the scheduler may preempt (evict/recompute/swap) — a real latency event to monitor.

9. Observations from Real Systems

• vLLM popularized PagedAttention and most engines now use a paged/block KV layout (02).
• SGLang's RadixAttention extends block sharing into a prefix tree, maximizing reuse across branching prompts (02, 05).
• The capacity ceiling you hit in practice is the KV pool — gpu_cache_usage_perc≈1 + rising num_requests_waiting is the universal "out of KV" signature (01, 10).
• Long-context serving is gated by blocks-per-seq — providers cap served context partly for this reason (Phase 5.10).
• The OS-paging analogy is why systems engineers find LLM serving approachable — it's virtual memory again.

10. Common Misconceptions

11. Engineering Decision Framework

RAISE EFFECTIVE CONCURRENCY (KV is the currency):
 seqs ≈ KV_pool_blocks ÷ blocks_per_seq(context)
 1. Grow the pool: ↑ --gpu-memory-utilization (keep headroom); fewer/smaller weights (quant). [Phase 6.06]
 2. Shrink per-seq KV: ↓ --max-model-len to real need; --kv-cache-dtype fp8 (KV quant). [Phase 6.02]
 3. Share blocks: enable prefix caching for common prompts. [05]
 4. Watch: gpu_cache_usage_perc (≈1 = full) + preemption counters + num_requests_waiting. [08]
 5. At the limit: queue/reject (admission control) rather than thrash on preemption. [07]

12. Hands-On Lab

Goal

Demonstrate that per-request KV size sets concurrency, and observe paged-KV utilization and (optionally) block sharing.

Prerequisites

• A vLLM endpoint (01); ability to read /metrics.

Steps

1. Baseline capacity: start vLLM with --max-model-len 8192. Ramp concurrent long-context requests until num_requests_waiting rises; record the max concurrent (that's your KV ceiling).
2. Shrink per-seq KV: restart with --max-model-len 1024; repeat. Far more sequences should fit — concurrency scales ~inversely with context (blocks per seq) — confirming seqs ≈ pool ÷ blocks_per_seq (Phase 6.02).
3. KV quant: add --kv-cache-dtype fp8; show even more sequences fit.
4. Watch utilization: during each run, curl /metrics | grep -E "cache_usage|waiting|preempt". Note utilization approaching 1.0 at the ceiling.
5. Block sharing: with --enable-prefix-caching, send many requests sharing a long system prompt; observe cache-usage growing sub-linearly with request count (shared blocks) and TTFT dropping (05).

Expected output

A table: --max-model-len (and KV dtype) → max concurrent sequences + peak gpu_cache_usage_perc, demonstrating the inverse context↔concurrency relationship and the KV-quant/sharing wins.

Debugging tips

• Concurrency doesn't scale with smaller context → you're compute- or client-bound, not KV-bound; check gpu_cache_usage_perc.
• OOM at high util → reduce --gpu-memory-utilization (headroom).

Extension task

Estimate fragmentation savings: compare measured max-concurrency to a naïve "contiguous max-context slab" estimate to see the paging multiplier.

Production extension

Alert on gpu_cache_usage_perc > 0.9 and preemption counters; wire to autoscaling/admission control (07, 08).

What to measure

Max concurrent seqs vs --max-model-len/KV dtype; peak KV utilization; preemption events; prefix-sharing effect on cache usage + TTFT.

Deliverables

• A context↔concurrency table showing KV is the ceiling.
• A KV-quant and prefix-sharing before/after.
• A capacity formula (seqs ≈ pool ÷ blocks_per_seq) calibrated to your GPU.

13. Verification Questions

Basic

1. What three wastes does naïve KV allocation cause, and roughly how much memory is lost?
2. What OS concept is PagedAttention modeled on, and how does the analogy map?
3. How does block sharing enable prefix caching?

Applied 4. Your KV pool holds 10,000 blocks (16 tokens each). How many concurrent 4k-context sequences fit (ignore prompt sharing)? 5. Why does halving --max-model-len roughly double concurrency?

Debugging 6. gpu_cache_usage_perc≈1.0 with requests queuing. Diagnosis and three levers. 7. Latency spikes correlate with preemption counters rising. What's happening?

System design 8. Design capacity planning that guarantees N concurrent users at C context on a given GPU, using the block math.

Startup / product 9. How does PagedAttention (and KV quant + prefix sharing) change how many users one GPU serves — and thus your cost per user?

14. Takeaways

1. PagedAttention = OS paging for the KV cache — fixed blocks + a per-seq block table.
2. It cuts KV waste from 60–80% to <4%, fitting 2–4× more sequences per GPU.
3. Complementary to continuous batching (memory layout vs scheduling); vLLM uses both.
4. Block sharing (copy-on-write) enables prefix caching and efficient parallel sampling.
5. KV is still finite — concurrency ≈ pool_blocks ÷ blocks_per_seq; shrink context / KV-quant / share to raise it.

15. Artifact Checklist

• A context↔concurrency table proving KV is the ceiling.
• A KV-quant (fp8) before/after on max concurrency.
• A prefix-sharing before/after on cache usage + TTFT.
• A calibrated capacity formula (seqs ≈ pool ÷ blocks_per_seq).
• Alerts on gpu_cache_usage_perc + preemption for 08.

Up: Phase 7 Index · Next: 05 — Prefix and Prompt Caching