Paged Attention › Page-Based Memory Allocation

The solution comes from a technique that operating systems have used for decades: virtual memory with paging. Instead of requiring contiguous physical memory, paging allows data to be stored in fixed-size blocks (pages) scattered anywhere in memory, with a page table tracking where each piece resides. This technique changed operating system design in the 1960s, and it proves equally effective for managing KV caches in modern LLM serving systems.

The paging philosophy separates two views of memory. The logical view is the programmer's (or in our case, the sequence's) idealized picture: a contiguous array of token slots numbered 0 through N. The physical view is the hardware's reality: a collection of fixed-size blocks sitting at various physical addresses. A page table bridges these views by recording, for each logical block, which physical block holds that data. Neither view changes the other; the translation happens transparently at access time.

Think of paging like a library's call number system. Every book has a shelf number (logical address) that tells you how the library has organized its collection. But physically, books can be moved between branches, stored in offsite warehouses, or placed on reserve shelves. The catalog (page table) always knows where each book is, regardless of what call number it carries. You look up the call number, the catalog tells you the physical location, and you retrieve the book. You never need to know that your 600-series science book is physically sitting in a different wing from your neighboring 601-series book.

The key insight is that the fragmentation problem arose precisely because we required the logical and physical layouts to match. By decoupling them, we eliminate that requirement. Physical blocks can come from anywhere in the free pool, and the logical sequence still appears perfectly ordered through the page table. No fragmentation is possible because there is no requirement for contiguity in physical memory.

To understand how paging solves fragmentation, we must distinguish between logical and physical memory organization. A sequence's KV cache appears contiguous from a logical perspective, with tokens numbered 0, 1, 2, and so on. However, the actual physical storage need not mirror this logical arrangement. As long as we maintain a mapping that tells us where each piece of data resides in physical memory, we can store the data anywhere we like.

In the context of KV caches, paging works through four key concepts that build on each other:

• Physical blocks: GPU memory is divided into fixed-size blocks, each capable of holding a small number of KV pairs (typically 16 tokens worth). These blocks represent the actual memory locations where data is stored. All physical blocks are identical in size, which means any sequence can use any block.
• Logical blocks: Each sequence's KV cache is divided into logical blocks of the same size. These represent the abstract, contiguous view of the sequence's cache. Logical block 0 holds the first 16 tokens' KV pairs, logical block 1 holds the next 16, and so on.
• Block table: A mapping from logical block indices to physical block locations. This data structure is the key that enables the translation between the sequence's logical view and the scattered physical reality. Each sequence has its own block table, typically a short array of physical block indices.
• Dynamic allocation: Physical blocks are allocated only when needed, not pre-allocated. This on-demand approach means we never reserve memory for tokens that haven't been generated yet.

This approach decouples how we think about the data (logically contiguous per sequence) from how we store it (potentially scattered across physical memory). Let's implement a simulator to see these concepts in action:

No fragmentation. Request E was allocated using freed blocks from requests A and C, even though those freed blocks are non-contiguous in physical memory.

The key insight is that request E's blocks do not need to be contiguous in physical memory. The block table maintains the logical ordering, while physical blocks can be scattered anywhere. This eliminates external fragmentation entirely. When the simulator freed sequences A and C, their physical blocks returned to the free pool. Request E then claimed blocks from this pool, assembling its logical sequence from whatever physical locations happened to be available. From request E's perspective, it has a perfectly contiguous cache; the block table handles all the translation behind the scenes.

The block table is the data structure that enables this flexibility. For each sequence, it maintains an ordered list of physical block indices. The position in this list corresponds to the logical block number, while the value at that position indicates where in physical memory that block resides.

The address translation happens in two steps. First, given a token position $t$ in a sequence, we compute the logical block number as $\lfloor t / B \rfloor$, where $B$ is the block size in tokens. We also compute the offset within that block as $t \bmod B$. Second, we look up the physical block index by reading position $\lfloor t / B \rfloor$ from the block table. Combining the physical block address with the within-block offset gives us the exact location of the KV pair for token $t$.

$$\text{physical\_addr}(t) = \text{block\_table}\!\left[\left\lfloor \frac{t}{B} \right\rfloor\right] \cdot B + (t \bmod B)$$

where:

• $t$: the token index within the sequence (0-indexed)
• $B$: the block size in tokens (e.g., 16)
• $\text{block\_table}[\cdot]$: the array mapping logical block index to physical block index
• $\lfloor t / B \rfloor$: the logical block number for token $t$
• $t \bmod B$: the position of token $t$ within its logical block

This formula looks like pointer arithmetic, but the intuition is simple: divide the token index by the block size to find which block it belongs to, look up that block's physical location in the table, and then add the remainder to find the slot within the block. The formula applies identically regardless of how scattered the physical blocks are.

To visualize this concept, consider a sequence whose KV cache spans three logical blocks. The block table might contain the entries [7, 2, 15], showing that logical block 0 is stored in physical block 7, logical block 1 is stored in physical block 2, and logical block 2 is stored in physical block 15. When the attention mechanism needs to access the key for token 20 (which falls in logical block 1, since each block holds 16 tokens), it consults the block table, finds that logical block 1 maps to physical block 2, and reads the data from that location. The physical blocks are numbered 7, 2, and 15, which is a completely non-sequential arrangement, but the lookup is just an array index operation and takes constant time.