PagedAttention: Mathematical Foundations, Virtual Memory Block Allocation, and Zero-Waste KV Cache Serving

In autoregressive transformer inference, serving throughput is bounded primarily by high-bandwidth memory (HBM) capacity and memory bandwidth rather than raw floating-point operations. As large language models generate tokens sequentially, each newly sampled token requires caching the key and value projection vectors across all preceding tokens in the sequence. In legacy serving engines, this key-value (KV) cache is allocated contiguously for the theoretical maximum sequence length, resulting in severe internal fragmentation, external fragmentation, and redundant memory duplication during complex decoding routines.

Introduced by Kwon et al. from UC Berkeley and formalized in the vLLM serving engine, PagedAttention adapts classic virtual memory and paging principles to the attention operator. By partitioning key and value tensors into fixed-capacity, non-contiguous physical blocks managed via dynamic page tables, PagedAttention reduces KV cache memory waste from over 60% down to under 4%, unlocking 2x to 4x throughput improvements on identical accelerator hardware.

1. The Memory Wall in Autoregressive Serving

Transformer inference operates in two distinct phases with radically different computational profiles:

1. The Prefill (Prompt) Phase: The model processes the full prompt sequence $(x_1, \dots, x_n)$ in parallel. The self-attention matrix multiplication maps efficiently to tensor cores as dense compute-bound GEMM (General Matrix Multiply) operations.
2. The Decode (Generation) Phase: The model generates tokens $x_{n+t}$ sequentially one token at a time. To evaluate the attention output at step $t$, the query vector $q_{n+t}$ must be multiplied by all historical keys and values $(k_1, \dots, k_{n+t})$ and $(v_1, \dots, v_{n+t})$.

Because each decoding step generates only one token per sequence, the matrix-vector multiplications (GEMV) exhibit low arithmetic intensity. GPU compute units spend most of their cycles waiting for weights and KV cache tensors to be loaded from high-bandwidth memory into fast on-chip SRAM.

KV Cache Memory Footprint

For a transformer model with $L$ layers, hidden dimension $d_{\text{model}}$, and $H$ attention heads with head dimension $d = d_{\text{model}} / H$, each token requires storing two vectors (key and value) per layer in half-precision format (16-bit / 2 bytes per parameter). The memory footprint $M_{\text{token}}$ required per token across all layers is:

$$M_{\text{token}} = 2 \times L \times d_{\text{model}} \times 2 \text{ bytes} = 4 L d_{\text{model}} \text{ bytes}$$

For an OPT-13B model ($L = 40, d_{\text{model}} = 5120$), each token consumes:

$$M_{\text{token}} = 4 \times 40 \times 5120 = 819,200 \text{ bytes} \approx 800 \text{ KB}$$

For a sequence of length 2,048 tokens, the KV cache alone demands 1.64 GB of GPU memory. In a single NVIDIA A100 GPU with 40 GB of HBM, the static model weights in FP16 consume 26 GB, leaving only 12 to 14 GB for runtime activations and KV cache. Under this memory ceiling, a server can concurrently host fewer than 10 maximum-length sequences if memory is allocated statically.

2. Memory Inefficiencies in Contiguous Allocation

Prior to PagedAttention, deep learning serving systems such as FasterTransformer and early versions of Orca stored the KV cache for each sequence in contiguous physical GPU memory. Because output sequence lengths are non-deterministic and unknown prior to generation, legacy systems suffered from three major forms of memory waste:

Legacy Contiguous Pre-allocation (Severe Fragmentation):
+-------------------------------------------------------------------------+
| Prompt KV (Used) | Generated KV (Used) | Reserved for Max Length (Wasted) |
+-------------------------------------------------------------------------+
<------------------------ Static Pre-allocated Chunk -------------------->

PagedAttention Dynamic Block Allocation (Zero Waste):
Logical Blocks:   [ Block 0 ] -> [ Block 1 ] -> [ Block 2 (Partial) ]
Physical Pages:   Page #7        Page #1        Page #14 (Allocated on-demand)

1. Reserved Memory Waste: Systems pre-allocate memory buffers based on the requested maximum generation length $L_{\text{max}}$ (e.g., 2,048 or 4,096 tokens). Throughout early generation steps, the majority of the allocated buffer sits idle, preventing the scheduler from admitting new requests.
2. Internal Fragmentation: When a sequence emits an end-of-sequence token (<eos>) well before reaching $L_{\text{max}}$, the unutilized portion of the pre-allocated contiguous chunk is permanently lost for that request lifetime.
3. External Fragmentation: Dynamic memory allocators (such as buddy allocators) create non-contiguous free memory holes between variable-sized contiguous requests, leaving chunks that are too small to satisfy new maximum-length allocations.

Empirical profiling of production workloads by Kwon et al. (2023) showed that legacy contiguous serving frameworks utilized only 20.4% to 38.2% of allocated KV cache memory for actual token states, wasting over 60% to 79% of GPU memory capacity.

3. Mathematical Formulation of PagedAttention

Standard multi-head attention computes output vector $o_i$ at sequence position $i$ via scaled dot-product attention over historical representations:

$$q_i = W_q x_i, \quad k_i = W_k x_i, \quad v_i = W_v x_i$$

$$a_{ij} = \frac{\exp\left(\frac{q_i^\top k_j}{\sqrt{d}}\right)}{\sum_{t=1}^i \exp\left(\frac{q_i^\top k_t}{\sqrt{d}}\right)}, \quad o_i = \sum_{j=1}^i a_{ij} v_j$$

Block-Wise Partitioning

PagedAttention divides the sequence of key vectors $(k_1, \dots, k_i)$ and value vectors $(v_1, \dots, v_i)$ into discrete blocks of fixed token size $B$ (typically $B \in \{8, 16, 32\}$).

Let $K_j$ and $V_j$ represent the $j$-th key block and value block respectively:

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

For a sequence of length $i$, the total number of blocks is $\lceil i / B \rceil$. The attention score calculation is transformed into a block-wise dot product. The row vector of unnormalized attention logits for the $j$-th block is:

$$S_{ij} = \frac{q_i^\top K_j^\top}{\sqrt{d}} \in \mathbb{R}^{1 \times B}$$

The normalized attention weight vector $A_{ij} = (a_{i, (j-1)B+1}, \dots, a_{i, jB})$ across all historical blocks is computed via block-wise softmax normalization:

$$A_{ij} = \frac{\exp(S_{ij})}{\sum_{t=1}^{\lceil i / B \rceil} \sum_{m=1}^{\min(B, i - (t-1)B)} \exp\left(\frac{q_i^\top k_{(t-1)B + m}}{\sqrt{d}}\right)}$$

The final output vector $o_i$ is computed as the sum of matrix products across all physical value blocks:

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

Because $K_j$ and $V_j$ are fetched independently per block index $j$, the physical memory addresses storing $K_j$ and $V_j$ do not need to be contiguous in GPU DRAM.

4. Virtual Memory Architecture and Block Tables

PagedAttention decouples logical sequence representation from physical GPU allocation by mirroring operating system paging architectures:

• Logical KV Blocks: A contiguous virtual index space $(0, 1, 2, \dots)$ representing the sequence tokens.
• Physical KV Blocks: Fixed-size page slots allocated in a pre-reserved pool of GPU DRAM.
• Block Table: A metadata lookup structure maintaining the logical-to-physical mapping, filled token counts, and physical block reference counters.

Request Sequence: "The transformer attention mechanism uses virtual memory paging"
Token Indices:     [0 .. 3]        [4 .. 7]        [8 .. 11]       [12 .. 15]
Logical Blocks:    Block 0         Block 1         Block 2         Block 3 (Unallocated)
                      |               |               |
Block Table:       [ Log 0 -> Phys 12, #filled=4 ]
                   [ Log 1 -> Phys 4,  #filled=4 ]
                   [ Log 2 -> Phys 19, #filled=2 ]
                      |               |               |
Physical DRAM:     Page #4         Page #12        Page #19 (2 slots free)

Allocation Lifecycle

1. Prompt Prefill: When a request arrives with prompt length $N$, the manager computes the required blocks $M = \lceil N / B \rceil$. It pulls $M$ free physical blocks from the free list and assigns them in the block table.
2. Decoding Step: During step $t$, the engine appends the newly computed key $k_t$ and value $v_t$ to the last allocated physical block.
3. Block Overflow: When the last physical block reaches capacity ($\#\text{filled} = B$), the scheduler allocates a single new physical block from the free list and appends a new row to the request block table.
4. Completion: Upon encountering <eos>, all mapped physical blocks decrement their reference counters. Blocks with a reference count of 0 return immediately to the free page pool.

Internal fragmentation is bounded strictly to the final block of each active sequence, creating an average memory waste of less than $B / 2$ tokens per sequence. With $B = 16$, the maximum waste per sequence is 15 token slots (under 12 KB in OPT-13B), eliminating external fragmentation entirely.

5. Advanced Memory Sharing: Branching and Prefix Caching

PagedAttention natively supports fine-grained memory sharing across sequences through block reference counting and copy-on-write (CoW) semantics.

Parallel Sampling

In scenarios where a single prompt generates $K$ independent completion samples (such as code generation or best-of-$N$ verification):

1. The prompt prefill phase executes once, storing the prompt KV cache in shared physical blocks with reference count set to $K$.
2. All $K$ output sequence streams initialize their block tables pointing to the identical prompt physical blocks.
3. During generation, each stream writes new tokens to its own private physical blocks.
4. If a stream needs to write to a partially filled shared block, a CoW kernel copies the shared block into a new physical block, decrements the shared block reference count, and updates the stream block table.

Prompt Blocks: [ Phys 7 (Ref=2) ] -> [ Phys 1 (Ref=2) ]
                                          /          \
Sample 1 (CoW on split):       [ Phys 3 (Ref=1) ]   [ Phys 1 (Ref=1) ] (Sample 2)

Beam Search

Beam search continuously forks candidate hypotheses and prunes low-probability beams at each step. In legacy engines, pruning and branching required massive memory copies across GPU buffers.

In PagedAttention, beam candidate transitions update only block table pointers and reference counts:

• Discarded candidate beams decrement reference counts on their assigned physical blocks.
• Surviving candidate beams share historical prefix blocks without copying data.
• Memory copies occur strictly when branching within a shared block boundary, reducing memory movement overhead by over 90%.

System Prompt Prefix Sharing

For multi-tenant workloads with long invariant system instructions (e.g., 2,000-token enterprise system prompts), PagedAttention allows the system prompt KV blocks to be pre-computed once and pinned in physical memory. Incoming user queries map their initial logical blocks directly to the pinned physical blocks, eliminating redundant prefill computation and saving significant GPU memory across concurrent sessions.

6. Preemption and Memory Recovery Dynamics

When concurrent request demand exceeds physical GPU block capacity, the serving engine must preempt active requests to maintain execution stability without dropping queries. vLLM implements a First-Come-First-Serve (FCFS) gang-scheduling strategy using two recovery mechanisms:

| Strategy | Mechanism | Latency Impact | Bandwidth / Compute Cost | | :--- | :--- | :--- | :--- | | Swapping | Evicts physical blocks across PCIe from GPU HBM to Host CPU RAM. | Minimal TTFT penalty upon resume; bounded by PCIe bandwidth. | Memory bandwidth bounded (e.g., PCIe Gen4/Gen5 transfer rates). | | Recomputation | Discards physical blocks and recalculates KV cache from original prompt and generated tokens. | Recalculates all historical tokens in a single parallel prefill step. | Compute bounded; highly efficient on short-to-medium sequence lengths. |

Because transformer prefill operates at high compute intensity using GEMM operations, recomputing the KV cache for a 500-token sequence often executes faster than reading 400 MB of cache tensors across a congested PCIe bus, making recomputation the preferred default for compute-heavy accelerators.

7. Custom GPU Kernel Optimization

Executing non-contiguous attention requires specialized CUDA kernels to prevent memory access serialization. Standard cuBLAS or cuDNN attention implementations assume contiguous tensor strides $(B, H, S, D)$. PagedAttention introduces three custom kernel fusions:

1. Fused Reshape and Block Write: Instead of writing raw projection tensors and later reshaping them into head-major layouts, the projection write kernel immediately transposes and stores new keys and values directly into their physical block destinations based on block table indices.
2. Warp-Aligned Attention Gathering: During decoding, a GPU thread warp is assigned to iterate across physical block pointers. The kernel fetches key blocks $K_j$, computes partial vector dot-products $q_i^\top K_j^\top$, maintains running softmax normalizers using online softmax reduction, and accumulates value vectors $V_j$ directly in GPU registers.
3. Batched Block Copy-on-Write: Memory duplication operations triggered by branching are batched into a single CUDA kernel launch, avoiding hundreds of tiny asynchronous cudaMemcpyAsync invocations.

Pseudocode for PagedAttention Decoding Kernel:
---------------------------------------------------------------------------------
def paged_attention_decode_kernel(q, block_table, physical_k_cache, physical_v_cache):
    # q: [head_dim], block_table: [num_blocks]
    acc_o = zeros(head_dim)
    running_max = -infinity
    running_sum = 0.0

    for block_idx in block_table:
        # Fetch non-contiguous physical block
        phys_k = physical_k_cache[block_idx]  # [block_size, head_dim]
        phys_v = physical_v_cache[block_idx]  # [block_size, head_dim]

        # Compute block attention scores
        scores = dot_product(q, phys_k.T) / sqrt(head_dim)  # [block_size]
        
        # Online softmax update
        block_max = max(scores)
        new_max = max(running_max, block_max)
        rescale = exp(running_max - new_max)
        
        running_sum = running_sum * rescale + sum(exp(scores - new_max))
        acc_o = acc_o * rescale + dot_product(exp(scores - new_max), phys_v)
        running_max = new_max

    return acc_o / running_sum

8. Empirical Benchmarks and Systems Impact

In empirical evaluations conducted across OPT (13B, 66B, 175B) and LLaMA models on NVIDIA A100 clusters, PagedAttention demonstrated decisive throughput gains over FasterTransformer and Orca:

Serving Throughput Comparison (Requests per Second on A100):
ShareGPT Trace (OPT-13B):
FasterTransformer : [====] 1.0x (Baseline)
Orca (Oracle)     : [======] 1.5x
vLLM (PagedAttn)  : [================] 3.6x

Alpaca Trace (OPT-13B):
FasterTransformer : [====] 1.0x (Baseline)
Orca (Oracle)     : [========] 2.1x
vLLM (PagedAttn)  : [==================] 4.3x

• Memory Efficiency: PagedAttention reduced KV cache memory waste to below 4%, enabling effective batch sizes 2x to 4x larger than legacy contiguous systems.
• Serving Throughput: Across ShareGPT (long prompts, variable outputs) and Alpaca (instruction following) workloads, vLLM achieved 2x to 4.3x higher request throughput while sustaining identical per-token latency.
• Complex Decoding Gains: In parallel sampling ($N=4$) and beam search ($K=4$), memory sharing reduced total KV cache consumption by 55%, yielding up to 4.8x higher throughput compared to unshared execution engines.

9. Architectural Takeaways

PagedAttention fundamentally changed the systems architecture of LLM serving by demonstrating that memory management, rather than raw floating-point computation, is the defining bottleneck of modern inference.

By separating logical sequence dependencies from physical hardware layouts, PagedAttention provides:

• Near-Zero Memory Waste: Predictable, bounded memory overhead that scales linearly with active tokens rather than theoretical maximum lengths.
• Unified Memory Sharing: Frictionless support for prefix caching, speculative decoding trees, multi-sample verification, and multi-agent conversations without redundant tensor allocations.
• Standardized Serving Infrastructure: The foundational memory abstraction powering contemporary high-throughput inference engines across the industry, including vLLM, SGLang, Hugging Face TGI, and TensorRT-LLM.

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). arXiv:2309.06180
• Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., & Polosukhin, I. (2017). Attention Is All You Need. Advances in Neural Information Processing Systems (NeurIPS 2017). arXiv:1706.03762
• Yu, G. I., Jeong, J. S., Kim, G. W., Kim, S., & Chun, B. G. (2022). Orca: A Distributed Serving System for Transformer-Based Generative Models. 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). USENIX OSDI 2022
• 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). arXiv:2205.14135
• Shoeybi, M., Patwary, M., Puri, R., LeGresley, P., Casper, J., & Catanzaro, B. (2019). Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism. arXiv:1909.08053