GPU memory waste (60, 80%) stems from rigid contiguous allocations, but virtual paging principles now enable dynamic, fragmentation-resistant KV caching without pre-allocation overhead.
Fixed-size KV blocks (16, 32 tokens) use address translation to decouple logical sequences from physical memory, eliminating pre-allocation waste.
Hardware-aligned blocks and free-region pooling resolve internal/external fragmentation via logical-physical address decoupling.
Exceeding block capacity triggers microsecond block allocation, preventing OOM crashes but increasing manager overhead.
Adjust block size (16/32 tokens) based on GPU free pool fragmentation to balance locality and allocation overhead.
Paged attention memory represents the most influential systems-level breakthrough in large language model inference since the invention of the transformer architecture itself. Before its introduction by Woosuk Kwon and the UC Berkeley Sky Computing Lab in 2023, production AI servers suffered from an invisible crisis: between sixty and eighty percent of expensive GPU High-Bandwidth Memory was completely wasted due to internal and external memory fragmentation. By drawing direct inspiration from classic operating system virtual memory paging, PagedAttention decoupled logical sequence representations from physical hardware memory addresses, transforming how modern data centers serve high-concurrency generative models.
Foundations of Paged Attention Memory
To understand the necessity of paged attention memory, one must examine how standard deep learning frameworks allocate memory tensors. In frameworks like PyTorch, tensors must reside in contiguous physical memory buffers. When a language model begins generating an answer, the inference engine cannot predict in advance how many tokens the model will produce. Will the response be a concise three-word confirmation, or an exhaustive two-thousand-token technical essay?
To prevent mid-generation Out-Of-Memory (OOM) crashes, conventional systems had to pre-allocate a contiguous memory block equal to the maximum possible sequence length (e.g., 4,096 or 8,192 tokens) the instant a request entered the server. This design introduced three catastrophic forms of memory waste:
- Reserved Waste: Memory allocated for tokens that may never be generated. If a user receives a 200-token answer, the remaining 7,992 tokens of allocated space sit empty and unusable by other concurrent requests.
- Internal Fragmentation: Gaps created within memory chunks due to fixed-size hardware alignment boundaries.
- External Fragmentation: Scattered, non-contiguous free memory holes between active requests that cannot be joined to fulfill a new contiguous allocation request.
Virtual Memory Architecture
PagedAttention resolves this crisis by implementing virtual memory paging directly inside GPU kernel space. Instead of demanding contiguous HBM buffers, the system partitions the key-value cache into small, fixed-size blocks (typically 16 or 32 tokens per block).
| Logical Block | Token Range | Physical Block ID | VRAM Physical Address | Allocation Status |
|---|---|---|---|---|
| Logical Block 0 | Tokens 0 – 15 | Physical #412 | 0x7f9a1000 | Full (16/16) |
| Logical Block 1 | Tokens 16 – 31 | Physical #89 | 0x7f8b4000 | Full (16/16) |
| Logical Block 2 | Tokens 32 – 47 | Physical #1044 | 0x7fc02000 | Active (4/16 Allocated) |
Under this architecture, when a new token is generated, the system checks whether the currently active physical block has free slots. If it does, the token’s key and value vectors are written to the next open offset within the block. If the block is full, the memory manager allocates a new arbitrary physical block from anywhere in the GPU’s free memory pool and maps it into the sequence’s private page table.
Because physical blocks do not need to be contiguous, external fragmentation is reduced to absolute zero. Internal fragmentation is strictly bounded to the final unfilled block of a sequence. With a block size of 16 tokens, the average wasted memory per active sequence is only 8 tokens, less than 0.1% of an 8,192-token context window.
Copy-on-Write and Complex Decoding Algorithms
Beyond eliminating memory waste, paged attention memory unlocks radical performance advantages for sophisticated sampling algorithms, such as parallel sampling and beam search. In standard serving engines, generating five candidate completions for a single prompt required cloning the entire prompt’s KV cache five times in memory.
PagedAttention implements the classic operating system primitive of Copy-on-Write (CoW). The initial prompt’s physical blocks are shared across all five candidate paths, with their reference counts incremented to five. During generation, as long as the branches read the shared prompt, no memory is duplicated. Only when an individual branch emits a new, divergent token does the engine allocate a private physical block for that branch. In empirical benchmarks conducted across shared prefix workloads, this mechanism slashes KV cache memory overhead by up to 55%, enabling a 2.2x to 4x expansion in total serving throughput.
Empirical Systems Invariants
- Block sizing dictates hardware efficiency: Smaller blocks (e.g., 8 tokens) minimize internal waste, while larger blocks (e.g., 32 tokens) improve GPU memory bus coalescing and cache line utilization.
- Page tables must live in high-speed GPU memory: Address translation structures must be stored in fast L2 or shared memory to avoid introducing translation lookaside buffer stalls during kernel launches.
- Near-zero waste directly translates to batch expansion: By reclaiming 60-80% of previously wasted VRAM, serving systems can increase batch concurrency by 2x to 4x on identical hardware.
KV Cache Memory Bottleneck: Inside Sub-100ms LLM Serving
Explore the full 10-part curriculum or advance to the next technical stage to master how high-throughput AI serving infrastructure circumvents the GPU memory wall.
KV Cache Memory Bottleneck: Inside Sub-100ms LLM Serving
An empirical exploration through the foundational dynamics, systemic trade-offs, and practical architecture of kv cache memory bottleneck: inside sub-100ms llm serving.