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.