PagedAttention and Virtual Memory Management: Mathematical Foundations of Non-Contiguous KV-Cache Allocation, Dynamic Block Translation, and Copy-on-Write Forking Mechanics

In autoregressive transformer serving, the generation phase is fundamentally constrained by GPU memory capacity and memory bandwidth rather than raw compute throughput. While the initial prefill phase processes the prompt in parallel with high arithmetic intensity, the subsequent token-by-token decoding phase computes attention for only a single new token per sequence at each step. At each decoding step, the model must read all historical Key (K) and Value (V) activation tensors from GPU High Bandwidth Memory (HBM) into on-chip Static Random-Access Memory (SRAM).

Before the introduction of PagedAttention by Kwon et al. (2023), serving runtimes required key-value cache memory to reside in contiguous physical memory buffers. Because request completion lengths cannot be known in advance, systems pre-allocated contiguous memory chunks sized for maximum context limits or expected sequence bounds. This static allocation pattern introduced severe memory fragmentation, causing 60% to 80% of allocated KV-cache HBM to sit idle and restricting maximum serving concurrency.

PagedAttention resolves this bottleneck by adapting classical operating system virtual memory paging to transformer KV caches. By partitioning key and value tensors into fixed-size physical blocks and managing access through per-sequence page tables, PagedAttention eliminates external fragmentation, constrains internal fragmentation to under 4%, and enables zero-copy prefix sharing and parallel sampling via Copy-on-Write (CoW) mechanics.

1. The Mathematical Modeling of KV-Cache Memory Consumption

To understand the memory wall in autoregressive serving, consider a standard decoder-only transformer architecture parameterized by:

• $N_L$: Number of transformer layers
• $N_Q$: Number of query attention heads per layer
• $N_{KV}$: Number of key-value attention heads per layer (where $N_{KV} = N_Q$ in Multi-Head Attention, and $N_{KV} \ll N_Q$ in Grouped-Query Attention)
• $d_h$: Hidden dimension per attention head
• $b$: Byte precision per parameter (e.g., $b = 2$ for FP16/BF16, $b = 1$ for FP8)
• $L$: Sequence length in tokens

At sequence length $L$, the total key-value cache memory $M_{KV}$ consumed by a single request across both key and value projections is defined as:

$$M_{KV}(L) = 2 \times N_L \times N_{KV} \times d_h \times L \times b \quad \text{bytes}$$

For modern frontier and open-weight architectures, this footprint scales rapidly:

• Llama-3-8B ($N_L = 32, N_{KV} = 8, d_h = 128, b = 2$): $M_{KV}(L) = 131,072 \times L \text{ bytes} \approx 0.131 \text{ MB per token}$. A context of 8,192 tokens consumes $\approx 1.07 \text{ GB}$ of HBM per concurrent stream.
• Llama-3-70B ($N_L = 80, N_{KV} = 8, d_h = 128, b = 2$): $M_{KV}(L) = 327,680 \times L \text{ bytes} \approx 0.328 \text{ MB per token}$. A context of 8,192 tokens consumes $\approx 2.68 \text{ GB}$ of HBM per stream.
• Llama-2-70B ($N_L = 80, N_{KV} = 64, d_h = 128, b = 2$ using dense MHA): $M_{KV}(L) = 2,621,440 \times L \text{ bytes} \approx 2.62 \text{ MB per token}$. An 8,192-token context consumes $\approx 21.47 \text{ GB}$ of HBM per stream.

When serving a batch of $N$ concurrent requests with dynamic sequence lengths $L_1, L_2, \dots, L_N$, total memory allocated under contiguous allocation systems is governed by maximum capacity reservations rather than actual consumed tokens.

2. Taxonomy and Formal Proofs of KV-Cache Memory Waste

In traditional serving frameworks like FasterTransformer and early versions of Orca (Yu et al., 2022), memory allocators suffer from three distinct fragmentation mechanisms:

Traditional Contiguous Pre-Allocation:
[ Token 1 .. Token 200 (Active) | Unused Reserved Slots (Waste) -> Max Context (4096) ]
                                 \____________________________________________________/
                                              Internal + Reservation Waste

PagedAttention Dynamic Block Allocation:
Logical Cache:  [ Block 0 (16) ] -> [ Block 1 (16) ] -> [ Block 2 (16) ] ...
Physical Pool:  [ Phys 47 ] ... [ Phys 12 ] ... [ Phys 93 ] (Non-contiguous HBM)
Waste: Only partially filled final block (< 16 tokens).

Internal Fragmentation

Internal fragmentation occurs when memory is allocated in fixed or pre-reserved boundaries that exceed the actual sequence length generated by the model.

If a runtime allocates a contiguous buffer sized for maximum sequence length $L_{\max}$, the internal memory waste $\mathcal{W}_{\text{int}}$ for request $i$ terminating at length $L_i$ is:

$$\mathcal{W}_{\text{int}, i} = (L_{\max} - L_i) \cdot 2 N_L N_{KV} d_h b$$

For a batch of $N$ requests drawn from a sequence length distribution with probability density function $p(L)$, the expected aggregate internal waste is:

$$\mathbb{E}[\mathcal{W}_{\text{int}}] = N \cdot 2 N_L N_{KV} d_h b \int_{0}^{L_{\max}} (L_{\max} - L) p(L) \, dL$$

In enterprise workloads where prompt lengths average 500 to 1,000 tokens and completions average 200 tokens within an 8,192-token limit window, $\mathbb{E}[\mathcal{W}_{\text{int}}]$ routinely exceeds 75% of total allocated cache memory.

Reservation Fragmentation

Even when runtimes implement dynamic memory resizing (reallocating buffers when sequences grow), allocators must reserve memory for future generation steps ahead of time to avoid per-token memory allocation overhead.

If memory is reserved in increments of $\Delta L$, at any arbitrary decoding step $t \in [1, L_i]$, the reserved ungenerated capacity $\mathcal{W}_{\text{res}}(t)$ is:

$$\mathcal{W}_{\text{res}}(t) = (\lceil t / \Delta L \rceil \cdot \Delta L - t) \cdot 2 N_L N_{KV} d_h b$$

External Fragmentation

External fragmentation occurs when memory is dynamically allocated and freed in variable chunk sizes. Over time, physical HBM becomes peppered with non-contiguous free memory segments.

Let GPU HBM contain a set of free disjoint memory segments $\mathcal{M}_{\text{free}} = \{m_1, m_2, \dots, m_k\}$ where each segment $m_j$ has contiguous capacity $c(m_j)$. Total free memory is:

$$C_{\text{total\_free}} = \sum_{j=1}^{k} c(m_j)$$

Under contiguous allocation constraints, an incoming request requiring contiguous capacity $C_{\text{req}}$ will be rejected (or forced to wait) if:

$$\max_{1 \le j \le k} c(m_j) < C_{\text{req}} \le C_{\text{total\_free}}$$

This condition represents complete allocation stalls despite substantial aggregate unallocated memory on the device.

3. The PagedAttention Architecture: Logical-to-Physical Address Translation

PagedAttention solves all three fragmentation modalities by eliminating the requirement for physical contiguity. The key-value cache of each sequence is treated as a sequence of Logical KV Blocks, which are mapped to Physical KV Blocks managed in a unified global GPU memory pool.

Mathematical Formulation of Block Partitioning

Let block size $B$ denote the fixed number of tokens stored in a single physical block (typically $B \in \{8, 16, 32\}$).

For a sequence of length $L$, the logical KV cache is partitioned into $M = \lceil L / B \rceil$ logical blocks:

$$\mathcal{B}_{\text{logical}} = \{B_0, B_1, \dots, B_{M-1}\}$$

For any arbitrary token position $t \in \{0, 1, \dots, L-1\}$ within the sequence:

1. Logical Block Index ($j$):

$$j = \left\lfloor \frac{t}{B} \right\rfloor$$

1. Intra-Block Token Offset ($o$):

$$o = t \bmod B$$

Physical Block Representation

A physical block $p_k$ is a contiguous memory region allocated in GPU HBM sized to hold exactly $B$ token vectors for both key and value tensors across all layers and heads:

$$\text{BlockSizeBytes} = 2 \times N_L \times N_{KV} \times d_h \times B \times b$$

For $B = 16$, $N_{KV} = 8$, $d_h = 128$, $b = 2$, a single physical block occupies exactly:

$$2 \times 8 \times 128 \times 16 \times 2 = 65,536 \text{ bytes per layer} \quad (64 \text{ KB})$$

For an 80-layer model, one physical block across all layers consumes $80 \times 64 \text{ KB} = 5.12 \text{ MB}$.

The Block Table Mapping

Each active sequence $r$ maintains a private Block Table $\mathcal{T}_r$, which acts as an operating system page table:

$$\mathcal{T}_r = [p_{(r, 0)}, p_{(r, 1)}, \dots, p_{(r, M-1)}], \quad p_{(r, j)} \in \{0, 1, \dots, \mathcal{P}_{\max}-1\}$$

where $\mathcal{P}_{\max}$ is the total number of physical blocks available in the global GPU allocator.

Token Index t = 38, Block Size B = 16
1. Logical Block Index:  j = floor(38 / 16) = 2
2. Intra-Block Offset:    o = 38 mod 16 = 6
3. Block Table Lookup:    T_r[2] -> Physical Block 93
4. Physical Address:      BasePtr(Pool) + (93 * BlockSizeBytes) + (6 * TokenBytes)

Minimization of Internal Waste

Because physical blocks are allocated dynamically on demand as tokens are generated, only the final logical block $B_{M-1}$ of a sequence can contain unwritten token slots.

The maximum internal fragmentation per sequence is strictly bounded by:

$$\mathcal{W}_{\text{paged\_int}} \le (B - 1) \cdot 2 N_L N_{KV} d_h b$$

Assuming sequence completion lengths $L \bmod B$ are uniformly distributed over $\{0, 1, \dots, B-1\}$, the expected internal memory waste per sequence is:

$$\mathbb{E}[\mathcal{W}_{\text{paged\_int}}] = \frac{B - 1}{2} \cdot 2 N_L N_{KV} d_h b$$

For $B = 16$, the expected waste is exactly $7.5$ tokens of KV-cache memory per sequence. For a sequence length $L = 500$, the internal fragmentation percentage is:

$$\mathcal{F}_{\text{waste}} = \frac{7.5}{500} = 1.5\%$$

This represents a reduction in memory waste from over 70% in contiguous static allocation systems to under 2% to 4% in PagedAttention.

4. Kernel Execution and Gather-Scatter Attention Mechanics

During autoregressive generation at decoding step $t$, the attention engine receives a new query vector $q_i \in \mathbb{R}^{d_h}$ for head $i \in \{1, \dots, N_Q\}$ and must compute scaled dot-product attention against all previous key vectors $k_{\tau, i}$ and aggregate value vectors $v_{\tau, i}$ for $\tau \in \{0, \dots, t-1\}$.

In standard contiguous attention kernels (e.g. FlashAttention-2 by Dao, 2023), the kernel reads directly from a continuous memory pointer $K \in \mathbb{R}^{L \times d_h}$. In PagedAttention, the kernel performs non-contiguous gather operations via the sequence's block table.

Vectorized Address Computation

Let $\mathcal{T}$ denote the array of physical block identifiers for the current sequence. For token position $\tau \in [0, t-1]$, the physical memory addresses for the key and value vectors at layer $l$ and head $h$ are:

$$\text{Addr}_K(\tau) = \text{PoolPtr}_K + \mathcal{T}\left[\left\lfloor \frac{\tau}{B} \right\rfloor\right] \cdot \text{Stride}_{\text{block}} + (\tau \bmod B) \cdot \text{Stride}_{\text{token}} + h \cdot \text{Stride}_{\text{head}}$$

$$\text{Addr}_V(\tau) = \text{PoolPtr}_V + \mathcal{T}\left[\left\lfloor \frac{\tau}{B} \right\rfloor\right] \cdot \text{Stride}_{\text{block}} + (\tau \bmod B) \cdot \text{Stride}_{\text{token}} + h \cdot \text{Stride}_{\text{head}}$$

Fused PagedAttention Algorithm

# Algorithmic formulation of PagedAttention forward decode pass
def paged_attention_decode(
    query: Tensor,          # Shape: [batch_size, num_heads, head_dim]
    key_pool: Tensor,       # Shape: [num_blocks, num_kv_heads, block_size, head_dim]
    value_pool: Tensor,     # Shape: [num_blocks, num_kv_heads, block_size, head_dim]
    block_tables: Tensor,   # Shape: [batch_size, max_num_blocks_per_seq]
    seq_lens: Tensor,       # Shape: [batch_size]
    scale: float,           # 1.0 / sqrt(head_dim)
    block_size: int         # Tokens per physical block (e.g., 16)
) -> Tensor:
    batch_size, num_heads, head_dim = query.shape
    output = torch.zeros_like(query)

    for b in range(batch_size):
        seq_len = seq_lens[b]
        num_blocks = (seq_len + block_size - 1) // block_size
        q = query[b]  # [num_heads, head_dim]
        
        # Accumulators for online softmax
        m_prev = torch.full((num_heads, 1), -float('inf'))
        l_prev = torch.zeros((num_heads, 1))
        acc = torch.zeros((num_heads, head_dim))
        
        for blk_idx in range(num_blocks):
            phys_block_id = block_tables[b, blk_idx]
            tokens_in_block = min(block_size, seq_len - blk_idx * block_size)
            
            # Gather physical block KV tensors
            k_block = key_pool[phys_block_id, :, :tokens_in_block, :]  # [num_kv_heads, tokens, head_dim]
            v_block = value_pool[phys_block_id, :, :tokens_in_block, :] # [num_kv_heads, tokens, head_dim]
            
            # Compute logits: S = (q * K^T) * scale
            scores = torch.einsum("hd,ktd->hkt", q, k_block) * scale
            
            # Online softmax reduction across blocks
            m_curr = torch.maximum(m_prev, torch.max(scores, dim=-1, keepdim=True)[0])
            p_prev = torch.exp(m_prev - m_curr)
            p_curr = torch.exp(scores - m_curr)
            
            l_curr = p_prev * l_prev + torch.sum(p_curr, dim=-1, keepdim=True)
            acc = acc * p_prev + torch.einsum("hkt,ktd->hd", p_curr, v_block)
            
            m_prev = m_curr
            l_prev = l_curr
            
        output[b] = acc / l_prev
        
    return output

Parallel Partitioning Across GPU Warps

In production CUDA implementations (such as vLLM's vllm/csrc/attention/attention_kernels.cu), executing PagedAttention over long sequences requires partitioning the reduction across thread warps:

1. Intra-Block Parallelism: Thread warps inside a CUDA threadblock are assigned distinct physical blocks. Each thread loads a 128-bit vectorized chunk (8 consecutive FP16 values) from GPU HBM.
2. Intermediate Reduction: Each threadblock computes intermediate maximum values $m_{\text{block}}$, sum of exponentials $l_{\text{block}}$, and partial output vectors $O_{\text{block}}$.
3. Cross-Block Reduction Kernel: A second lightweight reduction kernel combines the intermediate statistics across all assigned physical blocks using online softmax rescaling:

$$O_{\text{final}} = \sum_{k} \frac{l_k \exp(m_k - m_{\text{global}})}{l_{\text{global}}} O_k, \quad m_{\text{global}} = \max_k m_k, \quad l_{\text{global}} = \sum_k l_k \exp(m_k - m_{\text{global}})$$

Because memory accesses inside each physical block are fully contiguous and coalesced, PagedAttention achieves over 95% of the memory bandwidth saturation of monolithic, contiguous attention kernels while operating entirely over non-contiguous physical allocations.

5. Copy-on-Write (CoW) Forking and Complex Decoding Strategies

Modern LLM workflows frequently deploy advanced inference patterns that diverge from simple linear sequence generation:

• Parallel Sampling: Generating $n$ candidate completions from a single shared prompt.
• Beam Search: Maintaining $K$ active candidate paths at each step.
• Tree-Structured Decoding & Speculative Tree Verification: Evaluating multiple speculative token branches concurrently.
• Multi-Turn Agent Interactions: Multiple independent agent steps sharing identical system instructions and tool definitions.

Under contiguous memory allocation architectures, each branch requires a complete, independent physical duplicate of the entire prompt's KV cache.

Reference-Counted Physical Blocks

PagedAttention introduces operating-system-level Copy-on-Write (CoW) mechanics by augmenting every physical block $p \in \mathcal{P}$ in the global block allocator with an atomic reference counter:

$$\mathcal{R}[p] \in \{0, 1, 2, \dots, N_{\text{max}}\}$$

When a block is free, $\mathcal{R}[p] = 0$. When assigned to an active sequence, $\mathcal{R}[p] = 1$.

Parallel Sampling with Copy-on-Write (Prompt Length = 32 tokens, B = 16):
Shared Prompt:   [ Logical 0 (Phys 10, Ref=2) ] -> [ Logical 1 (Phys 14, Ref=2) ]
                                                            /                  \
Branch A (Token 33): Allocates Phys 88 (Ref=1) <-----------+                    +------------> Branch B (Token 33): Allocates Phys 92 (Ref=1)

The Copy-on-Write Forking Protocol

When a request forks from a parent sequence into $k$ child sequences (or when parallel sampling initializes $k$ streams from a single prompt):

1. Page Table Duplication: The system creates $k$ new Block Tables $\mathcal{T}_1, \mathcal{T}_2, \dots, \mathcal{T}_k$, copying the parent's physical block pointers:

$$\mathcal{T}_i[j] \leftarrow \mathcal{T}_{\text{parent}}[j] \quad \forall j \in \{0, \dots, M-1\}, \quad \forall i \in \{1, \dots, k\}$$

1. Reference Increment: For every physical block referenced in the table, its counter is incremented by $k - 1$:

$$\mathcal{R}[p] \leftarrow \mathcal{R}[p] + (k - 1) \quad \forall p \in \mathcal{T}_{\text{parent}}$$

1. Execution Cost: Step 1 and Step 2 operate exclusively on lightweight metadata (integers in host or device control memory). The physical KV tensors in GPU HBM are never copied, executing in $\mathcal{O}(1)$ time with zero memory allocation overhead.

Write Execution and Block Splitting

When child sequence $i$ generates a new token at position $t$:

• Let $j = \lfloor t / B \rfloor$ and $p = \mathcal{T}_i[j]$.
• Case 1: Exclusive Ownership ($\mathcal{R}[p] == 1$):

The child sequence owns the physical block exclusively. The new key and value vectors are written directly into slot $o = t \bmod B$ of physical block $p$.

• Case 2: Shared Block Mutation ($\mathcal{R}[p] > 1$):

The block is shared with other active sequences. Writing directly would corrupt state for the other branches. The memory manager executes Copy-on-Write:

1. Allocates a new physical block $p_{\text{new}}$ from the free pool ($\mathcal{R}[p_{\text{new}}] \leftarrow 1$).
2. Copies the existing $o$ token vectors from $p$ to $p_{\text{new}}$:

$$\text{MemCopy}\left(K[p, :o], K[p_{\text{new}}, :o]\right), \quad \text{MemCopy}\left(V[p, :o], V[p_{\text{new}}, :o]\right)$$

1. Decrements the reference counter of the original block:

$$\mathcal{R}[p] \leftarrow \mathcal{R}[p] - 1$$

1. Updates the child's block table:

$$\mathcal{T}_i[j] \leftarrow p_{\text{new}}$$

1. Writes the new token's key and value vectors into slot $o$ of $p_{\text{new}}$.

In beam search and parallel sampling benchmarks, CoW memory sharing reduces KV-cache memory consumption by up to 55%, directly translating to a 2.2x increase in maximum serving throughput on identical hardware.

6. Memory Exhaustion, Eviction, and Preemption Dynamics

In high-concurrency production serving, the aggregate memory demand of active decoding sequences can exceed total physical GPU HBM capacity ($N \cdot M_{KV}(L) > \text{Capacity}_{\text{HBM}}$).

When the global physical block allocator runs out of free blocks ($\sum_{p} \mathbb{I}(\mathcal{R}[p] > 0) == \mathcal{P}_{\max}$), the scheduler must handle memory exhaustion deterministically without crashing or dropping active requests.

PagedAttention enables two distinct preemption policies:

GPU HBM Saturation Handling:
                   [ All Physical Blocks Allocated ]
                                   |
                +------------------+------------------+
                |                                     |
        [ Swapping Policy ]                  [ Recomputation Policy ]
  Async DMA copy to Host CPU RAM.       Evict physical blocks immediately.
  Free GPU blocks for active jobs.      On resume, re-run prefill forward pass.
  Swap back when memory frees.          Optimal for short contexts & high FLOPS.

1. Swapping (GPU HBM $\leftrightarrow$ Host CPU RAM)

The serving system allocates an auxiliary physical block pool in CPU host memory. Because CPU RAM is significantly larger and cheaper than GPU HBM (e.g., 512 GB to 2 TB CPU RAM vs. 80 GB GPU HBM), the scheduler can evict victim sequences to host memory:

1. The scheduler selects a victim request (typically using First-In-First-Out or Last-In-First-Out priority).
2. It transfers the victim's physical blocks from GPU HBM to Host RAM via asynchronous PCIe DMA transfers.
3. The freed GPU blocks are returned to the active pool.
4. When GPU capacity recovers, the blocks are transferred back to GPU HBM, and generation resumes without losing decoding progress.

2. Recomputation (Discard and Prefill)

In scenarios where PCIe bandwidth is saturated or prompt evaluation is fast, the scheduler can discard the victim's physical KV blocks entirely:

1. The scheduler frees all physical blocks in $\mathcal{T}_{\text{victim}}$, retaining only the original prompt tokens and the sequence of generated token IDs.
2. When GPU memory becomes available, the system resubmits the concatenated tokens $[\text{Prompt}, \text{Generated}]$ as a single prefill request.
3. Because prefill executes at compute-bound arithmetic intensity (saturating GPU tensor cores), recomputing 500 tokens often takes less elapsed time than transferring megabytes of KV tensors across a contended PCIe bus.

7. Architectural Comparison and Systems Evolution

The table below contrasts PagedAttention with historical and subsequent memory management architectures in LLM serving:

| Architecture | Memory Allocation Unit | Internal Fragmentation | External Fragmentation | Zero-Copy Prefix Sharing | CoW Parallel Sampling | Serving Engine | | :--- | :--- | :--- | :--- | :--- | :--- | :--- | | Static Pre-Allocation | Monolithic buffer ($L_{\max}$) | Extreme ($> 70\%$) | Severe | Unsupported | Unsupported | FasterTransformer, TensorRT-LLM (v1) | | Dynamic Resizing (Orca) | Contiguous resized chunks | High ($20\% - 40\%$) | Severe | Unsupported | Unsupported | Orca (Yu et al., 2022) | | PagedAttention | Fixed non-contiguous blocks ($B=16$) | Minimal ($< 4\%$) | Zero | Supported | Supported ($\mathcal{O}(1)$ fork) | vLLM (Kwon et al., 2023) | | RadixAttention | Trie-structured paged blocks | Minimal ($< 4\%$) | Zero | Recursive Radix Tree | Supported with LRU Eviction | SGLang (Zheng et al., 2024) | | vAttention | OS Virtual Memory Remapping | Zero (byte-level) | Low | Supported | Supported | vAttention (Prabhu et al., 2024) |

Subsequent architectures build directly on PagedAttention's foundations. SGLang's RadixAttention extends PagedAttention by retaining physical KV blocks in a radix tree across independent API calls, enabling automatic multi-turn cache hits and prefix reuse. vAttention leverages low-level Linux kernel page table manipulation to provide contiguous virtual memory addresses to standard attention kernels while dynamically mapping physical GPU pages underneath.

By eliminating memory fragmentation and uncoupling logical token positions from physical HBM layout, PagedAttention shifted LLM serving from memory-wasteful static reservations to high-density, multi-tenant execution engines.

Sources

• Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al., SOSP 2023 / arXiv:2309.06180)
• SGLang: Efficient Execution of Structured Language Model Programs (Zheng et al., 2024 / arXiv:2312.07104)
• Orca: A Distributed Serving System for Transformer-Based Generative Models (Yu et al., OSDI 2022)
• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (Dao et al., NeurIPS 2022 / arXiv:2205.14135)
• FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning (Dao, 2023 / arXiv:2307.08691)
• vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention (Prabhu et al., ASPLOS 2024)