PagedAttention

Technical Overview of PagedAttention

PagedAttention is a memory management algorithm designed to optimize the storage of Key-Value (KV) caches in LLM serving engines.

In autoregressive generation, KV caches grow dynamically, requiring memory allocation for maximum sequence lengths upfront. This causes physical memory fragmentation and limits serving capacity. PagedAttention addresses this by partitioning the KV cache into fixed-size virtual pages, allowing non-contiguous storage in physical memory.

Key Architecture & Implementation

Inspired by virtual memory paging in operating systems, PagedAttention manages the KV cache as follows:

• Logical Blocks: The KV cache of a request is partitioned into logical blocks, each containing attention keys and values for a fixed number of tokens (e.g., 16 tokens).
• Physical Page Table: Maps virtual blocks to non-contiguous physical pages allocated on-demand in GPU VRAM.
• Block Sharing: Concurrent requests (e.g., parallel decoding paths in speculative decoding or multi-agent loops) share identical prompt prefix blocks, reducing VRAM usage.

Virtual Blocks:   [ Block 0 ] --> [ Block 1 ] --> [ Block 2 ]
                   |               |               |
Page Table:        |               |               |
                   v               v               v
Physical Pages:   [ Page 23 ]     [ Page 104 ]    [ Page 8 ]

Core Parameters

• Memory Wastage: Reduces KV cache memory wastage from over-allocation to near 0%.
• Throughput: Increases inference engine serving capacity by up to 2-4x.

Real-world Applications

• The core engine of vLLM, which has been adopted across production serving platforms.

Why It Was Necessary

Before PagedAttention, most inference serving frameworks allocated KV cache memory in large, contiguous blocks sized for a request’s maximum possible sequence length, even when the actual generated sequence turned out much shorter — wasting a large fraction of GPU memory to fragmentation and over-allocation, sometimes over 60-80% by some measurements in the original vLLM paper. PagedAttention borrows the classic operating-systems idea of virtual memory paging: it divides the KV cache into small fixed-size blocks that can be allocated non-contiguously and mapped through a page table, similar to how an OS manages physical RAM pages for multiple processes. This lets a serving system allocate memory to a request incrementally as it actually generates tokens, rather than reserving a large block upfront, and lets multiple requests share identical prefix blocks (like a common system prompt) without duplicating that memory. The result, demonstrated in the vLLM serving engine, is dramatically higher achievable batch sizes and throughput for the same GPU memory budget — the single biggest lever most production LLM serving systems have for cost efficiency.