The "Spatial Magic" of Modern AI Inference: A Deep Dive into PagedAttention

In production environments for Large Language Models (LLMs), memory management is the core bottleneck determining throughput and cost. If you have followed high-performance inference frameworks like vLLM, you have undoubtedly encountered a key concept: PagedAttention.

Simply put, PagedAttention solves an extremely inefficient problem in LLM inference: memory fragmentation of the KV Cache.

Why Is PagedAttention Needed?

During generative AI inference, to avoid recalculating previously generated tokens, the system stores the Key and Value vectors for each token in memory. This is known as the KV Cache.

Traditional KV Cache management relies on "contiguous storage." This means the system must pre-allocate a contiguous block of memory for each request. However, this approach suffers from two critical issues:

1. Internal Fragmentation: Since it is impossible to predict exactly how many tokens a model will generate, systems typically pre-allocate space based on the maximum sequence length (Max Sequence Length). If a model generates only 10 tokens but 2048 were pre-allocated, the vast majority of the memory is wasted.
2. External Fragmentation: As requests dynamically start and finish, numerous small, non-contiguous gaps appear in memory. This makes it impossible to allocate large contiguous blocks for new requests.

This inefficiency leads to extremely low GPU memory utilization, limiting the number of concurrent requests (Batch Size).

The Core Logic of PagedAttention: Borrowing from Virtual Memory

PagedAttention draws direct inspiration from Virtual Memory and Paging mechanisms in operating systems.

Instead of requiring the KV Cache to be stored contiguously in physical memory, PagedAttention divides it into fixed-size "blocks."

• Logical Blocks $\rightarrow$ Physical Blocks: Each request has a logical sequence of KV Cache entries, but these sequences are mapped to non-contiguous physical memory blocks.
• Block Table: The system maintains a mapping table that records the correspondence between logical page indices and physical page addresses. When the model needs to access previous KV Cache data, it quickly locates the physical address via the block table.

What Are the Practical Benefits?

1. Near-Zero Waste: Except for the last block, which may not be fully filled, all physical blocks are fully utilized. GPU memory utilization increases from ~60% to over ~96%.
2. Dynamic Expansion: When the current block is full, the system simply allocates a new physical block dynamically and adds it to the block table. There is no need to move existing data or reallocate large contiguous spaces.
3. Efficient Sharing (Copy-on-Write): During parallel sampling or Beam Search, multiple output sequences can share the same physical blocks for the prefix (Prompt). Only when a specific sequence generates a new token requiring modification is "Copy-on-Write" executed, significantly reducing the memory overhead of multi-path generation.

Impact on Engineering Practice

The introduction of PagedAttention allows frameworks like vLLM to increase Batch Size by several times without increasing hardware costs. For developers, this means:

• Higher Throughput: More requests can be processed per unit of time.
• Lower Latency: Increased concurrency reduces queue waiting times.
• More Flexible Deployment: Larger-scale concurrent tasks can run on smaller GPUs.

Conclusion

If Continuous Batching solved scheduling waste along the "time axis," then PagedAttention solves storage waste along the "space axis." Together, they form the foundation of modern high-performance LLM inference engines, pushing AI from "expensive laboratory toys" toward "high-efficiency industrial-grade products."