Research Paper Teardown
arXiv:2309.06180

PagedAttention Paper Breakdown: Virtual Memory Allocation for LLM KV Cache Serving

Definitive paper teardown of vLLM's PagedAttention architecture detailing virtual memory block translation, dynamic copy-on-write sequence forks, and prefix caching.

14 min readVerified 2026-07-261 primary sourcesOriginal Paper
Technical paper breakdown illustration.

Paper Methods

  • Paged KV Cache Virtual Memory Manager
  • Block Table Logical-to-Physical Address Translation
  • Copy-on-Write Sequence Branching
  • RadixTree Shared Prefix Caching

Engineering Limitations

  • •Internal block memory fragmentation when block size is set too high (> 32 tokens)
  • •Non-contiguous physical GPU memory strides can reduce memory bandwidth utilization on older GPU architectures
  • •CPU-GPU block swapping adds PCI-e transfer latency under extreme memory pressure

PagedAttention Paper Breakdown

A detailed technical teardown of vLLM: Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al., SOSP 2023).

1. The KV Cache Memory Bottleneck

In standard LLM serving (e.g. HuggingFace Transformers), the Key-Value (KV) cache for a request is allocated as a contiguous memory tensor matching the maximum possible sequence length (e.g., 4,096 or 8,192 tokens).

This leads to three forms of severe memory waste:

  1. Reserved Over-allocation: Allocating memory for 4,096 tokens when the user prompt and response only consume 300 tokens (up to 80% wasted).
  2. Internal Fragmentation: Pre-allocating space for future tokens that may never be generated.
  3. External Fragmentation: Virtual memory fragmentation between active concurrent streams.

2. Virtual Memory Paging & Block Table Architecture

PagedAttention solves memory waste by borrowing the concept of virtual memory paging from operating systems.

Instead of contiguous allocation, KV cache blocks are divided into fixed-size physical blocks (e.g., B = 16 tokens per block).

Address Translation Formula

For a token at logical position i, its logical block number b and block offset o are computed as:

b = floor(i / B),    o = i mod B

The physical memory location of Key tensor K_i is resolved via the block table T:

PhysicalAddr(K_i) = T[b] * B + o

Logical KV Tokens [0 .. 31]
  |
  +-- Logical Block 0 [Tokens 0..15]   ==>  Physical Block 17 (GPU VRAM)
  +-- Logical Block 1 [Tokens 16..31]  ==>  Physical Block 4 (GPU VRAM)

3. Dynamic Copy-on-Write (CoW) Parallel Sampling

When generating multiple outputs for a single prompt (e.g., n = 4 parallel completions), PagedAttention shares prompt KV cache blocks across all 4 streams without duplication.

If Stream 2 generates a new token that modifies its local state, a Copy-on-Write (CoW) trigger allocates a new physical block only for Stream 2, leaving the shared prompt blocks untouched for Streams 1, 3, and 4.

Performance Impact

  • Memory Overhead Reduction: Near 0% wasted KV cache memory (reduced from 60–80% waste to < 4%).
  • Throughput Increase: 2.2x to 4x higher throughput on identical hardware (NVIDIA A100 80GB) compared to FasterTransformer and HuggingFace TGI.