PagedAttention: Mathematical Foundations, Virtual Memory Block Allocation, Non-Contiguous KV-Cache Management, and Prefix Sharing Dynamics

PagedAttention is an attention algorithm and memory management architecture designed to eliminate memory waste and fragmentation in autoregressive Large Language Model (LLM) serving. Introduced by researchers at UC Berkeley and published at SOSP 2023 alongside the vLLM serving engine, PagedAttention adapts the classic operating system principles of virtual memory, paging, and copy-on-write to the management of dynamic Key-Value (KV) caches in GPU High Bandwidth Memory (HBM).

During autoregressive inference, generating each new token requires retaining the intermediate Key and Value activation vectors of all preceding tokens to compute multi-head attention. In traditional inference serving architectures, this KV cache was allocated as contiguous memory buffers sized to the maximum possible sequence length. Because sequence lengths cannot be predicted in advance and vary widely across requests, traditional frameworks wasted between 60% and 80% of total GPU KV memory due to internal fragmentation, external fragmentation, and premature reservation. PagedAttention resolves this bottleneck by partitioning the KV cache into fixed-size physical memory blocks and managing them through dynamic page tables, reducing memory waste to below 4% and enabling 2x to 4x higher serving throughput.

The KV Cache Memory Bottleneck

In standard autoregressive Transformer decoding, generating token $t+1$ given context tokens $1, \dots, t$ requires computing attention between the query vector $q_{t+1}$ and all historical key vectors $k_1, \dots, k_t$, followed by multiplying the resulting attention weights by value vectors $v_1, \dots, v_t$.

To avoid recomputing keys and values for all preceding tokens at every generation step, inference engines cache these tensors in GPU memory. For a Transformer model with $L$ layers, $N_{heads}$ attention heads per layer, head dimension $d_{head}$, and 16-bit floating-point precision (2 bytes per element), the KV cache memory footprint $M_{KV}$ for a sequence of length $S$ is calculated as:

$$M_{KV} = 2 \times 2 \times L \times N_{heads} \times d_{head} \times S \text{ bytes}$$

The factor of 2 accounts for storing both Key and Value matrices, and the second factor of 2 accounts for the 16-bit precision. For a 13-billion parameter model with 40 layers, 40 heads, and a hidden dimension of 5120 ($d_{head} = 128$), each token consumes 320 KB of KV cache memory across all layers. A sequence reaching a context length of 2,048 tokens requires 655 MB of GPU memory for its KV cache alone, while an 8,192-token sequence requires over 2.6 GB.

Before PagedAttention, serving systems faced three structural forms of memory waste:

1. Over-allocation (Internal Fragmentation): Because the engine cannot predict the final output length of a request, it reserved a contiguous memory buffer sized to the maximum sequence length (such as 2,048 or 4,096 tokens). If the model generated only 100 tokens, the remaining 95% of the reserved buffer sat allocated but unused.
2. External Fragmentation: Dynamic memory allocators allocating variable-length contiguous buffers created memory holes across GPU memory over time. Even if total free memory was sufficient, requests could not be admitted if no single contiguous chunk matched the required size.
3. Reservation Waste: Memory for future generation steps was allocated prior to token generation, locking out other requests from using available GPU memory.

Together, these inefficiencies constrained the batch sizes that GPU serving systems could sustain, leaving high-bandwidth tensor cores underutilized.

Mathematical Formulation of PagedAttention

PagedAttention breaks the continuous sequence-length dimension of the KV cache into fixed-size blocks containing a fixed number of tokens $B$ (commonly set to $B = 16$ or $B = 32$).

Block Partitioning

Let a sequence have length $S$. The sequence is divided into $\lceil S / B \rceil$ logical KV blocks. For a given attention head with query dimension $d_{head}$, the keys and values are grouped into logical blocks:

$$K_j = \begin{bmatrix} k_{(j-1)B + 1}^T \\ k_{(j-1)B + 2}^T \\ \vdots \\ k_{\min(jB, S)}^T \end{bmatrix} \in \mathbb{R}^{B \times d_{head}}, \quad V_j = \begin{bmatrix} v_{(j-1)B + 1}^T \\ v_{(j-1)B + 2}^T \\ \vdots \\ v_{\min(jB, S)}^T \end{bmatrix} \in \mathbb{R}^{B \times d_{head}}$$

where $j \in \{1, 2, \dots, \lceil S / B \rceil\}$ denotes the logical block index.

Block-Wise Attention Computation

When decoding the $i$-th token with query vector $q_i \in \mathbb{R}^{1 \times d_{head}}$, the attention score vector for logical block $j$ is computed as:

$$A_{i,j} = \frac{q_i K_j^T}{\sqrt{d_{head}}} \in \mathbb{R}^{1 \times B}$$

The elements of $A_{i,j}$ represent the unnormalized attention logits between the query token $i$ and all tokens stored in block $j$:

$$A_{i,j,m} = \frac{q_i \cdot k_{(j-1)B + m}}{\sqrt{d_{head}}}, \quad m \in \{1, \dots, B\}$$

The softmax normalization is then computed globally across all blocks up to the current sequence position:

$$P_{i,j,m} = \frac{\exp(A_{i,j,m})}{\sum_{t=1}^{\lceil i / B \rceil} \sum_{n=1}^{\min(B, i - (t-1)B)} \exp(A_{i,t,n})}$$

The output attention context vector $o_i \in \mathbb{R}^{1 \times d_{head}}$ is obtained by taking the weighted sum of the value blocks:

$$o_i = \sum_{j=1}^{\lceil i / B \rceil} P_{i,j} V_j$$

where $P_{i,j} = [P_{i,j,1}, P_{i,j,2}, \dots, P_{i,j,B}]$ denotes the normalized attention probability row vector for block $j$.

Kernel Implementation and Online Softmax

In standard GPU attention kernels, the entire key and value tensors must reside in contiguous memory to enable stride-based memory indexing. In PagedAttention, the GPU kernel is written to accept an array of physical block pointers.

The execution model operates as follows:

• Threads within a GPU thread block fetch physical block addresses from a lookup table.
• Each thread block loads key vectors from non-contiguous physical blocks into shared memory (SRAM), computes intermediate dot products $q_i K_j^T$, and tracks the running maximum logit $m_i$ and normalizer sum $l_i$ using the online softmax formulation.
• The thread block scales previous partial accumulators, multiplies normalized weights by value blocks $V_j$, and produces the final context vector $o_i$ without ever materializing an intermediate $S \times S$ attention matrix in GPU HBM.

Virtual Memory Architecture and Block Tables

PagedAttention treats GPU High Bandwidth Memory as a pool of fixed-size physical page frames, directly mirroring the virtual memory management architecture of modern operating systems.

Address Translation via Block Tables

The system divides the memory management into two distinct layers:

1. Logical KV Blocks: A contiguous view of the sequence KV cache exposed to the model logic, indexed from 0 to $\lceil S / B \rceil - 1$.
2. Physical KV Blocks: Fixed-size memory buffers allocated across arbitrary, non-contiguous physical memory locations in GPU HBM.

For each active sequence, the serving engine maintains a Block Table data structure. When accessing token index $t$ within a sequence:

• The logical block index is determined by integer division: $LBI = \lfloor t / B \rfloor$.
• The intra-block offset is determined by the modulo operation: $Offset = t \pmod B$.
• The physical block address is retrieved by indexing into the sequence block table: $PBI = \text{BlockTable}[LBI]$.
• The physical memory address for the token key or value vector is computed as:

$$\text{Address}(t) = \text{Base}(PBI) + Offset \times \text{SizeOfTokenKV}$$

Fragmentation Bounding

By enforcing uniform block sizes, PagedAttention completely eliminates external fragmentation. Any free physical block in GPU memory can be allocated to satisfy any block request from any sequence, regardless of location.

Internal fragmentation is strictly bounded to the final, partially filled block of each active sequence. For a block size $B$, the maximum memory wasted per sequence is at most $(B - 1)$ token slots. Across an active serving batch of $N$ sequences, the average total memory wasted is:

$$\mathbb{E}[\text{Waste}] = N \times \frac{B - 1}{2} \times \text{SizeOfTokenKV}$$

For a default block size of $B = 16$, the average waste is approximately 8 token slots per sequence (roughly 2.5 MB for a 13B model), reducing overall KV cache memory waste to below 4%.

Advanced Memory Sharing Patterns

Because logical blocks are decoupled from physical memory allocations via block tables, PagedAttention enables zero-copy memory sharing across multiple sequences using reference counting and Copy-on-Write (CoW).

Parallel Sampling

In workloads requiring multiple completions for a single prompt (such as generating $N$ candidate responses, self-consistency loops, or tree-of-thought exploration), traditional systems duplicated the prompt KV cache $N$ times.

In PagedAttention:

• The prompt is processed once, allocating physical blocks $p_0, p_1, \dots, p_k$.
• All $N$ output sequences initialize their block tables pointing to the exact same physical prompt blocks.
• The reference count for each shared physical block is set to $N$.
• As each output stream generates new tokens, it writes into its own dedicated physical block once the shared prompt block boundaries are passed.

Beam Search

During beam search decoding, multiple candidate candidate hypotheses are tracked and dynamically pruned. When a candidate branch branches into new candidates:

• New candidates share preceding block references with parent candidates.
• Discarded beams have their block table entries unmapped, decrementing the physical block reference counts.
• When a reference count reaches zero, the physical block is immediately returned to the engine free list.

Shared Prefix Caching (Prompt Caching)

In multi-turn chat applications, few-shot prompting, and retrieval-augmented generation (RAG), multiple requests share long static prefixes (such as system instructions or retrieved background documents).

PagedAttention caches pre-computed physical blocks for standard prefixes. When a new request arrives containing a known prefix:

• The serving engine maps the initial logical blocks of the request directly to the pre-existing physical blocks in GPU memory.
• The prompt prefill computation for the shared tokens is skipped entirely, reducing time-to-first-token (TTFT) and eliminating redundant memory consumption.

Copy-on-Write Mechanics

If an execution path requires modifying an existing shared block (for instance, when multiple output branches diverge within the boundary of a single partially filled block):

1. The engine checks the reference count of the target physical block.
2. If the reference count is greater than 1, the engine allocates a fresh physical block from the free list.
3. The contents of the shared block up to the divergence point are copied to the new block.
4. The requesting sequence updates its block table to point to the new physical block, and the reference count of the original block is decremented by 1.

Preemption, Swapping, and Distributed Serving

When memory demand exceeds physical GPU capacity during request bursts, PagedAttention implements coordinated scheduling policies:

Preemption via Swapping vs. Recomputation

When all physical blocks in GPU HBM are exhausted:

• Swapping: The engine evicts physical blocks of selected low-priority requests across PCIe/NVLink to host CPU DRAM. When GPU memory becomes available, blocks are paged back into GPU HBM without losing generated progress.
• Recomputation: For low-prefill-latency workloads, the engine can discard KV blocks of preempted requests entirely, storing only the original prompt and generated token IDs, then recomputing the KV cache when rescheduling.

Tensor Parallelism Integration

In distributed serving configurations where a large model is partitioned across multiple GPUs using tensor parallelism (Megatron-LM style):

• Linear projections for Key and Value transformations are partitioned column-wise, distributing attention heads across $P$ GPUs.
• Each GPU maintains its own physical block storage containing $N_{heads} / P$ heads per block.
• A centralized scheduler maintains a single synchronized Block Table across all worker GPUs, ensuring that identical physical block indices are addressed in parallel without requiring inter-GPU block address communication during attention execution.

Serving Performance and Architectural Impact

By transforming KV cache management from static pre-allocation to dynamic paging, PagedAttention eliminates the primary memory bottleneck in LLM inference servers.

Key performance outcomes documented in the SOSP 2023 evaluation include:

• Memory Waste Reduction: Decreasing KV cache memory overhead from 60%-80% down to under 4%.
• Batch Size Expansion: Enabling 2x to 4x larger concurrent batch sizes within identical GPU memory constraints.
• Serving Throughput: Achieving 2x to 4x higher throughput compared to prior serving baselines such as Hugging Face Text Generation Inference (TGI) and FasterTransformer under identical latency Service Level Objectives (SLOs).

PagedAttention has since become the standard memory management primitive across production LLM inference engines, including vLLM, SGLang, TensorRT-LLM, and TGI.

Sources

• Kwon, W., Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J. E., Zhang, H., & Stoica, I. (2023). Efficient Memory Management for Large Language Model Serving with PagedAttention. Proceedings of the 29th ACM Symposium on Operating Systems Principles (SOSP '23), 611-626. arXiv:2309.06180.
• vLLM Project. (2023). vLLM: Easy, Fast, and Cheap LLM Serving with PagedAttention. vLLM Blog. https://vllm.ai/blog/2023-06-20-vllm.
• Dao, T., Fu, D. Y., Ermon, S., Rudra, A., & Ré, C. (2022). FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness. Advances in Neural Information Processing Systems (NeurIPS 2022), 35, 16344-16359. arXiv:2205.14135.
• Zheng, L., Yin, L., Xie, Z., Huang, J., Sun, C., Yu, C. H., Cao, S., Wang, C., Sheng, Y., Lian, H., Stoica, I., Gonzalez, J. E., & Zhang, H. (2024). SGLang: Efficient Execution of Structured Language Model Programs. arXiv:2312.07104.