PagedAttention

Traditional KV cache allocation reserves contiguous memory blocks for each request's maximum possible sequence length, leading to significant internal fragmentation as most sequences are shorter than the maximum. PagedAttention divides the KV cache into fixed-size blocks (analogous to memory pages). These blocks are allocated non-contiguously only as needed for the actual sequence, virtually eliminating wasted memory. This allows more concurrent requests to fit into GPU VRAM, directly increasing throughput.

PagedAttention's block-based management is the foundation for high-efficiency continuous batching (also known as in-flight batching). Because sequences are composed of independent blocks, the scheduler can:

• Dynamically add new requests to a running batch.
• Evict and store blocks of completed sequences to CPU RAM.
• Swap blocks back in to GPU memory if a paused sequence (e.g., in chatbot turn-based dialogue) needs to resume generation. This maximizes GPU utilization by keeping the computational pipeline saturated, even with highly variable request arrival times and sequence lengths.

The algorithm enables shared memory blocks across different sequences or within a single sequence. This is critical for two optimizations:

• Shared Prompt Prefixes: In multi-user scenarios where requests share a common system prompt or context, PagedAttention allows a single physical block of KV cache for the shared prefix to be referenced by all relevant sequences, providing dramatic memory savings.
• Parallel Sampling: When generating multiple output candidates (e.g., beam search or top-k sampling) from the same input, the shared context's KV cache is not duplicated. This reduces memory pressure during advanced decoding strategies.

By packing KV cache blocks densely and sharing memory, PagedAttention drastically reduces the incidence of out-of-memory (OOM) errors during high-concurrency serving. The efficient memory use also makes it feasible to serve models with very long context windows (e.g., 128K or 1M tokens) without requiring prohibitive amounts of GPU VRAM per request. This allows practical deployment of models capable of processing large documents, lengthy conversations, or complex codebases.

PagedAttention introduces a level of indirection between the logical sequence of tokens and their physical storage in memory. A block table (similar to a page table) maps the logical positions of tokens to their actual physical block addresses. This decoupling is what enables all other features:

• Non-contiguous allocation prevents fragmentation.
• Easy sharing of physical blocks across logical sequences.
• Efficient swapping of blocks between GPU and CPU memory. This design mirrors operating system principles, applying proven systems techniques to the specific problem of attention cache management.

Also known as dynamic batching, this is an inference optimization technique where new requests are dynamically added to a running batch on the GPU as previous requests finish generation. This maximizes GPU utilization and throughput by eliminating idle time, contrasting with static batching where the entire batch must finish before a new one starts. It is a foundational technique used in conjunction with PagedAttention in engines like vLLM.

A memory structure used during the autoregressive decoding of Transformer models. It stores the computed keys and values for previously generated tokens, allowing the model to attend to its own output without recomputing these tensors for every new token. The KV cache is the primary source of memory fragmentation and waste that PagedAttention was designed to solve, as its size grows dynamically with sequence length.

A condition where free memory is broken into small, non-contiguous blocks, preventing the allocation of larger contiguous blocks even if total free memory is sufficient. In LLM inference, this occurs because variable-length sequences cause the KV cache for each request to be allocated and freed at different times. PagedAttention eliminates this by using a virtual memory paging approach, allowing non-contiguous physical memory blocks to serve a logically contiguous cache.

An inference acceleration technique that reduces the number of slow, sequential autoregressive steps from a large target model. A small, fast draft model (or a simpler heuristic) proposes a short sequence of candidate tokens. The large target model then verifies this sequence in a single, parallel forward pass, accepting correct tokens and rejecting incorrect ones. This technique improves Time Per Output Token (TPOT) and is often used alongside memory optimizations like PagedAttention.

A compiler-level inference optimization that combines multiple sequential neural network operations into a single GPU kernel. For example, a pattern like Linear -> Bias Add -> Activation can be fused. This reduces GPU kernel launch overhead and intermediate memory reads/writes, lowering latency. While PagedAttention optimizes memory management, operator fusion (used in engines like TensorRT) optimizes the computation graph itself.