M4-050M4: Sequences & TransformersEfficient Attention & FlashAttentionMedium
⚡Flashcard Drill➔Mastery:
PagedAttention: Eliminating KV-Cache Memory Fragmentation via Virtual Memory Paging
🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
📐 Mathematical Definition
⚡ One-Sentence Core Answer
PagedAttention adapts OS virtual memory paging to LLM serving, storing non-contiguous KV-cache blocks in virtual pages to eliminate internal/external fragmentation and enable memory sharing.
📌 Key Takeaways
- •Core problem: traditional serving pre-allocates contiguous memory for maximum context (e.g., 2048 tokens), wasting 60–80% of VRAM on memory fragmentation
- •Virtual memory paging: partitions KV cache into fixed-size physical blocks (e.g., 16 tokens), mapped via dynamic page tables
- •Copy-on-write sharing: enables zero-memory duplication in parallel sampling, beam search, and shared system prompts
📐 Mathematical Derivations
Architecture and Mechanics (Kwon et al., SOSP 2023; vLLM):
In standard LLM serving systems, GPU memory for the KV cache of a request must be allocated contiguously. Because request generation lengths are unpredictable, systems must over-allocate memory for the maximum possible length (e.g., 2048 tokens).
- Memory Waste Taxonomy:
1. Internal Fragmentation: Allocated memory reserved for future tokens that are never generated.
2. External Fragmentation: Unusable memory holes scattered between terminated requests of variable lengths.
3. Reservation Waste: Total wasted memory typically reaches of total GPU VRAM.
PagedAttention Architecture:
- Partition physical GPU memory into a pool of fixed-size Physical Blocks (e.g., each block holds keys and values for 16 tokens).
- Each request maintains a Logical Page Table mapping logical token indices to arbitrary non-contiguous physical blocks in GPU VRAM.
- When a new token is generated, if the current block has space, it is appended locally; if full, the block manager allocates 1 new physical block from the global free pool.
- Zero-Copy Forking (Copy-on-Write):
In parallel sampling (generating responses for 1 prompt) or shared system prompts, multiple requests point to the exact same physical prompt blocks. Memory is duplicated only when a request writes a unique generated token.
In standard LLM serving systems, GPU memory for the KV cache of a request must be allocated contiguously. Because request generation lengths are unpredictable, systems must over-allocate memory for the maximum possible length (e.g., 2048 tokens).
- Memory Waste Taxonomy:
1. Internal Fragmentation: Allocated memory reserved for future tokens that are never generated.
2. External Fragmentation: Unusable memory holes scattered between terminated requests of variable lengths.
3. Reservation Waste: Total wasted memory typically reaches of total GPU VRAM.
PagedAttention Architecture:
- Partition physical GPU memory into a pool of fixed-size Physical Blocks (e.g., each block holds keys and values for 16 tokens).
- Each request maintains a Logical Page Table mapping logical token indices to arbitrary non-contiguous physical blocks in GPU VRAM.
- When a new token is generated, if the current block has space, it is appended locally; if full, the block manager allocates 1 new physical block from the global free pool.
- Zero-Copy Forking (Copy-on-Write):
In parallel sampling (generating responses for 1 prompt) or shared system prompts, multiple requests point to the exact same physical prompt blocks. Memory is duplicated only when a request writes a unique generated token.
🏭 Production Trade-offs
Throughput impact: By eliminating memory fragmentation and enabling prompt KV-cache sharing, PagedAttention (vLLM) increases serving batch sizes by , delivering an immediate boost in overall serving throughput.
⚠️ Common Interview Pitfalls
- ✕Setting block size too small (e.g., 1 or 2 tokens), causing page table lookup overhead to bottleneck GPU memory controllers
- ✕Setting block size too large (e.g., 256 tokens), which reintroduces internal memory fragmentation
🎯 Interviewer Follow-up Inquiries
- ?How does PagedAttention implement Copy-on-Write (CoW) during parallel sampling in vLLM?
- ?What is the optimal physical block size (e.g., 16 vs 32 tokens) in PagedAttention to balance memory efficiency and kernel throughput?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
📚