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
Next: M4-051 →
📐 Mathematical Definition
logical block→physical block table;waste≤ one block per seq\text{logical block}\to\text{physical block table};\qquad \text{waste}\le\ \text{one block per seq}
⚡ 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 60%−80%60\%-80\% 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 0,…,T−10, \dots, T-1 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 NN 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 2−4×2-4\times, delivering an immediate 2−4×2-4\times 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.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM4-049: FlashAttention Backward Pass: Recomputing Softmax in SRAM Without Saving Intermediate Matrices📋 Back to BankNext →M4-051: Ring Attention and Sequence Parallelism for Near-Infinite Context Windows