Skip to content
intai
Search lessonsCtrl K

Module 02 · Chapter 5

PagedAttention: Virtual Memory for the KV Cache

Map logical KV positions to physical blocks, trace copy-on-write sharing, and calculate capacity and tail waste without assuming memory savings guarantee throughput.

Advanced35 min readUpdated Nov 3, 2026

Learning objectives

  • Diagnose over-reservation, internal, and external fragmentation within contiguous KV cache allocation pools.
  • Trace logical-to-physical block translation through block tables and calculate exact internal fragmentation bounds.
  • Track physical block reference counts across parallel sampling forks, unaligned prompt tails, and Copy-on-Write steps.
  • Derive block memory capacity and evaluate kernel memory-access tradeoffs between block sizes without guessing.

Before you start

  • Read Where Inference Time and Memory Go for KV cache sizing per layer and head.
  • Read Batching and Throughput for memory-bandwidth limits and concurrency tradeoffs.
  • Understanding of basic virtual memory, page tables, and tensor memory strides.

We consider dense, full-context causal attention with GPU-resident KV storage. Sliding-window attention and offloading have different retention rules.

During autoregressive language model inference, the key-value (KV) cache grows incrementally with every generated token. Because attention mechanisms attend to all prior tokens in a sequence, previously computed keys and values must remain accessible in high-bandwidth memory (HBM). Managing this dynamically expanding cache efficiently is the primary prerequisite for high-throughput language model serving.

This guide analyzes how PagedAttention resolves memory fragmentation through application-level virtual memory mapping, examines the tradeoffs governing block size selection, and details copy-on-write sharing for branching workloads.

1. The memory bottleneck in key-value serving

Section titled “1. The memory bottleneck in key-value serving”

In transformer decoding, the attention operation requires key and value tensors for every previous context position. For an active sequence of length S, generating the next token requires computing:

Attention(q, K, V) = softmax((q * K^T) / sqrt(d_head)) * V

Here, q represents the query vector for the single token currently being processed, while K and V contain representations for all S cached positions across all preceding prompt and generated tokens.

Memory footprint of the KV cache

Section titled “Memory footprint of the KV cache”

Consider a representative open-weights model configuration using Grouped-Query Attention (GQA):

  • Model parameters: nominal 8B configuration
  • Transformer layers (L): 32
  • Key-value attention heads (H_kv): 8
  • Head dimension (d_head): 128
  • Storage precision: 16-bit floating point (FP16 or BF16, 2 bytes per element)

For each cached token position, the model stores one key vector and one value vector across all layers:

bytes_per_token = 2 (keys and values) * L * H_kv * d_head * sizeof(dtype)
                = 2 * 32 * 8 * 128 * 2 bytes
                = 131,072 bytes
                = 128 KiB per token

At a sequence length of S = 4,096 tokens, a single active request requires:

sequence_kv_bytes = 4,096 tokens * 128 KiB/token
                  = 524,288 KiB
                  = 512 MiB

2. Static GPU memory partitioning

Section titled “2. Static GPU memory partitioning”

GPU high-bandwidth memory is not entirely available for dynamically generated KV pairs. At engine startup, total HBM is partitioned into distinct allocations:

+-----------------------------------------------------------------------+
| Model Weights | Runtime Workspace | KV Cache Pool Buffer | OS Reserve |
+-----------------------------------------------------------------------+
  1. Model weights: Fixed parameter footprint (for example, nominal 8B parameters in FP16 require 16 GB, which equals approximately 14.90 GiB).
  2. Runtime workspace: Pre-allocated scratch buffers for activation memory, communication buffers (NCCL / tensor-parallel collectives), and CUDA graph execution pools.
  3. OS and driver reserve: Driver headroom and runtime allocations retained to avoid cudaErrorMemoryAllocation failures.
  4. Configured KV cache pool: The remaining memory pool explicitly configured by the serving engine (for example, via engine-specific configuration flags such as setting a target GPU memory utilization fraction to 0.90 in vLLM configuration examples; this is a configurable ratio rather than an architectural default).

The KV cache pool is not an unbounded heap. Engines allocate dedicated memory buffers (which may be allocated as a single pool or partitioned into separate pools per layer or per key/value layout) managed directly by the engine’s runtime.

3. Allocation waste in contiguous serving baselines

Section titled “3. Allocation waste in contiguous serving baselines”

Early serving implementations allocated contiguous memory buffers for each request’s KV cache. Under dynamic workloads where requests arrive with varying prompt lengths and produce unpredictable output lengths, contiguous allocation suffers from three distinct structural sources of memory waste (categorized by Kwon et al., SOSP 2023):

Contiguous Reservation Waste Model:
+-------------------------------------------------------------------+
|   Valid Context   |   Reserved Headroom   |      Unused Space     |
+-------------------------------------------------------------------+
|<-- Actual Tokens ->|<-- Future Decode --->|<-- Internal/External ->|
  1. Over-allocation waste: In static reservation allocators, the engine reserves a contiguous buffer sized for the maximum possible sequence length (S_max, e.g., 2,048 or 4,096 tokens) upon request arrival. If an incoming sequence terminates after generating only 200 tokens, the remaining pre-allocated memory sits idle and inaccessible to other requests for the entire request duration. (Note that modern frameworks do not all reserve S_max, but dynamic contiguous reallocation introduces GPU memory movement overhead).
  2. Internal fragmentation: When an allocator provides chunks in fixed or power-of-two increments (e.g., 256, 512, 1,024 slots), any unused slots between the actual sequence length and the chunk boundary remain unusable by other requests.
  3. External fragmentation: As requests of varying durations complete and release contiguous buffers of differing sizes, physical HBM becomes fragmented into non-contiguous free segments.

4. Non-compacting external fragmentation

Section titled “4. Non-compacting external fragmentation”

Consider a non-compacting contiguous memory pool with 320 MiB of total free memory distributed across three discontinuous segments:

Segment 0: [ 128 MiB Free ] -> Segment 1: [ In Use ] -> Segment 2: [ 128 MiB Free ] -> Segment 3: [ 64 MiB Free ]

When a new request arrives requiring a contiguous 256 MiB buffer, the allocator cannot satisfy the request despite having 320 MiB of total available free space.

In an engine without online memory compaction, this allocation fails. However, a failed contiguous allocation does not require terminating the process with an unrecoverable CUDA out-of-memory crash. Robust serving engines handle allocation exhaustion through operational policy: deferring request scheduling, holding the request in an arrival queue, evicting optional caches, or returning an HTTP 429/503 rate-limit response.

Kwon et al. (2023) demonstrated that static contiguous reservation baselines incurred substantial memory waste across over-allocation, internal fragmentation, and external fragmentation on their evaluated serving traces. The paper reported workload-dependent serving throughput gains from eliminating fragmentation rather than a universal efficiency percentage across all hardware.

5. Application-level block mapping

Section titled “5. Application-level block mapping”

PagedAttention addresses these allocation inefficiencies by applying the principles of virtual memory operating systems to the KV cache. Instead of demanding contiguous physical memory for each sequence, the engine organizes KV cache storage into fixed-size, non-contiguous physical memory blocks.

Application-level block mapping

Contiguous logical tokens map through a per-request block table to non-contiguous physical GPU blocks.
Read this diagram as text

Application-level block mapping shows contiguous logical sequence tokens grouped into logical blocks and mapped through a per-request block table (engine metadata, integer pointers) to non-contiguous physical GPU KV cache blocks. Panel 1 shows the logical sequence split into Logical Block 0 (tokens 0–15) and Logical Block 1 (tokens 16–31). Panel 2 is the per-request block table, runtime metadata that maps Logical Block 0 to Physical Block 42 and Logical Block 1 to Physical Block 105; it is integer pointers, not physical tensor storage. Panel 3 shows the physical GPU KV cache buffer as a non-contiguous HBM block pool containing Phys Block 42 and Phys Block 105 separated by free slots. A legend identifies the three roles: logical tokens (input), block table (metadata/process), and physical storage (output).

6. Architectural boundary

Section titled “6. Architectural boundary”

PagedAttention is an application-level memory management technique implemented inside the inference engine runtime (host scheduler and GPU execution kernels). Its block table is software metadata, separate from OS page tables and hardware TLB translation. Ordinary GPU allocations still use the platform’s memory system; this technique does not implement hardware page faults or replace the MMU.

The serving engine manages physical block storage in GPU HBM (which may be allocated as a single pool or separated into distinct pools per layer or tensor layout). Inside its custom attention kernels, the engine passes a block_table—an integer array mapping logical block indices to physical block identifiers within the allocated pool.

7. Address translation arithmetic

Section titled “7. Address translation arithmetic”

For any token at zero-based index i within an active sequence:

logical_block_index = floor(i / block_size)
block_offset        = i % block_size
physical_block_id   = block_table[request_id][logical_block_index]

For example, given block_size = 16 and token index i = 35:

logical_block_index = floor(35 / 16) = 2
block_offset        = 35 % 16 = 3
physical_block_id   = block_table[request_id][2]

8. Fragmentation boundaries under paging

Section titled “8. Fragmentation boundaries under paging”
  1. External fragmentation: Within the homogeneous fixed-size block pool, external fragmentation is exactly zero. Because all blocks share identical dimensions, any free physical block can satisfy any request’s need for a new block.
  2. Internal fragmentation (tail waste): Internal fragmentation is strictly confined to the final, partially filled block of a sequence (in an unshared-last-block configuration).
  3. Tail waste upper bound: For a sequence with total cached length S (representing all prompt tokens plus accumulated generated tokens), the number of allocated blocks is ceil(S / block_size). The number of unused slots in the final block is:
tail_waste_slots = ceil(S / block_size) * block_size - S

At most, a sequence wastes block_size - 1 token slots. Because this tail waste is bounded by the block size rather than the sequence length, memory waste remains small across long contexts.

Block table metadata footprint

Section titled “Block table metadata footprint”

Maintaining block tables requires tracking physical block pointers for active sequences. Using our nominal 8B GQA configuration:

  • Sequence length: S = 4,096 tokens
  • Block size: B = 16 tokens per block
  • Allocated blocks: 4,096 / 16 = 256 blocks
  • KV cache payload: 4,096 tokens * 128 KiB/token = 512 MiB

Storing the block table as an array of 32-bit integers (int32, 4 bytes per entry) requires:

index_array_bytes = 256 blocks * 4 bytes = 1,024 bytes = 1 KiB

The ratio of the block table index array to the KV payload it maps is:

index_array_ratio = 1 KiB / 512 MiB
                  = 1,024 / (512 * 1,024 * 1,024)
                  = 1 / 524,288
                  ≈ 0.0001907%

This calculation accounts specifically for the block table index array. Host-side engine metadata (such as sequence state structures, reference counts, and free-list pointers) adds small auxiliary overhead, but the indexing metadata directly involved in kernel dispatch remains negligible relative to the tensor payload.

9. Block size tradeoffs and conditional capacity planning

Section titled “9. Block size tradeoffs and conditional capacity planning”

Selecting the block size B involves balancing memory packing efficiency against kernel dispatch efficiency and hardware memory coalescing.

  • Small block sizes (B = 8 or B = 16):
    • Advantages: Minimizes tail waste (at most 7 or 15 unused token slots per sequence). Maximizes packing efficiency when sequence lengths are non-uniform or short.
    • Disadvantages: Increases the number of blocks per sequence, expanding host-side metadata and requiring more iterations in kernel block loops.
  • Large block sizes (B = 32 or B = 64):
    • Advantages: Reduces the length of the block table array. Enables longer contiguous memory loops inside GPU kernels, easing vectorized memory loads.
    • Disadvantages: Increases tail waste (up to 31 or 63 unused slots per sequence). For short requests, tail waste can consume a substantial fraction of allocated memory.

10. Worked capacity decision under memory constraints

Section titled “10. Worked capacity decision under memory constraints”

Assume an inference engine operates with a strictly configured 16 MiB KV payload pool for our nominal 8B model (128 KiB per cached token slot):

total_pool_slots = 16 MiB / 128 KiB/token = 128 token slots

The scheduler must admit four concurrent active sequences with total cached token counts (prompt tokens plus generated tokens) of [17, 31, 32, 33]. The total number of useful context tokens is:

useful_tokens = 17 + 31 + 32 + 33 = 113 tokens

We evaluate whether this batch fits into the 16 MiB pool under block sizes B = 8, B = 16, and B = 32.

Evaluation with B = 8

Section titled “Evaluation with B = 8”
  • Req A (17 tokens): ceil(17 / 8) = 3 blocks -> 24 slots (tail waste: 7 slots)
  • Req B (31 tokens): ceil(31 / 8) = 4 blocks -> 32 slots (tail waste: 1 slot)
  • Req C (32 tokens): ceil(32 / 8) = 4 blocks -> 32 slots (tail waste: 0 slots)
  • Req D (33 tokens): ceil(33 / 8) = 5 blocks -> 40 slots (tail waste: 7 slots)
total_slots_B8  = 24 + 32 + 32 + 40 = 128 slots
total_memory_B8 = 128 slots * 128 KiB/token = 16 MiB
total_waste_B8  = 7 + 1 + 0 + 7 = 15 slots (11.72% tail waste)

Status: Fits exactly within the 16 MiB pool (128 slots allocated, 0 free slots remaining).

Evaluation with B = 16

Section titled “Evaluation with B = 16”
  • Req A (17 tokens): ceil(17 / 16) = 2 blocks -> 32 slots (tail waste: 15 slots)
  • Req B (31 tokens): ceil(31 / 16) = 2 blocks -> 32 slots (tail waste: 1 slot)
  • Req C (32 tokens): ceil(32 / 16) = 2 blocks -> 32 slots (tail waste: 0 slots)
  • Req D (33 tokens): ceil(33 / 16) = 3 blocks -> 48 slots (tail waste: 15 slots)
total_slots_B16  = 32 + 32 + 32 + 48 = 144 slots
total_memory_B16 = 144 slots * 128 KiB/token = 18 MiB
total_waste_B16  = 15 + 1 + 0 + 15 = 31 slots (21.53% tail waste)

Status: Exceeds pool capacity by 16 slots (2 MiB deficit). Cannot schedule all four requests concurrently.

Evaluation with B = 32

Section titled “Evaluation with B = 32”
  • Req A (17 tokens): ceil(17 / 32) = 1 block -> 32 slots (tail waste: 15 slots)
  • Req B (31 tokens): ceil(31 / 32) = 1 block -> 32 slots (tail waste: 1 slot)
  • Req C (32 tokens): ceil(32 / 32) = 1 block -> 32 slots (tail waste: 0 slots)
  • Req D (33 tokens): ceil(33 / 32) = 2 blocks -> 64 slots (tail waste: 31 slots)
total_slots_B32  = 32 + 32 + 32 + 64 = 160 slots
total_memory_B32 = 160 slots * 128 KiB/token = 20 MiB
total_waste_B32  = 15 + 1 + 0 + 31 = 47 slots (29.38% tail waste)

Status: Exceeds pool capacity by 32 slots (4 MiB deficit). Cannot schedule all four requests concurrently.

11. Tradeoff analysis

Section titled “11. Tradeoff analysis”

In this capacity-constrained scenario, only B = 8 allows scheduling all four requests concurrently. However, selecting B = 8 does not imply universally superior performance.

Block table indexing overhead increases by approximately 1.78x from B = 16 to B = 8 (16 block entries across requests versus 9 entries). Furthermore, smaller block sizes shorten the inner contiguous dimension in GPU kernels, which may reduce memory load efficiency depending on GPU vectorization capabilities. System operators must balance memory utilization against hardware execution throughput for their specific serving configurations.

12. Physical tensor layouts and fused GPU kernels

Section titled “12. Physical tensor layouts and fused GPU kernels”

In contiguous memory layouts, key and value tensors are structured as four-dimensional tensors: [batch_size, num_heads, max_seq_len, head_dim]. In PagedAttention, keys and values are stored across independent physical memory blocks.

Tensor layout in physical memory

Section titled “Tensor layout in physical memory”

To maximize vectorization efficiency on GPU hardware, serving runtimes customize physical tensor shapes inside each block. For example, vLLM’s CUDA implementation stores key blocks using a 5D layout:

K[num_blocks, num_kv_heads, head_dim / x, block_size, x]

In this layout, x counts the number of consecutive elements packed for 16-byte vectorized memory loads in one particular legacy vLLM CUDA kernel implementation (such as 16-byte load instructions on NVIDIA hardware):

x = 16 bytes / sizeof(dtype)

For 16-bit floating-point types (FP16 or BF16, 2 bytes per element), x = 16 / 2 = 8 elements. For head_dim = 128, the head dimension is divided into 128 / 8 = 16 chunks of 8 elements each.

The value tensor layout may differ from the key tensor layout. In vLLM, values are typically stored as:

V[num_blocks, num_kv_heads, head_dim, block_size]

This arrangement optimizes memory coalescing along the sequence dimension when accumulating weighted value vectors.

Hardware distinction: The vector load width (e.g., 16 bytes per instruction in this specific CUDA kernel path) and the GPU DRAM memory transaction sector (typically 32 bytes on modern GPU memory subsystems) are distinct architectural quantities. Furthermore, this vectorization scheme is specific to certain kernel implementations rather than a universal requirement of all serving engines.

Different serving libraries structure blocks according to their kernel specializations; this specific 5D layout is an implementation choice rather than an industry-wide specification.

13. Integration with fused attention

Section titled “13. Integration with fused attention”

Fused attention algorithms compute softmax activations online using running maximums and normalizers, avoiding the materialization of the intermediate O(S) attention score matrix in HBM.

Paged layouts and fused attention mechanisms operate compatibly:

  1. Custom kernels (such as those in FlashInfer or vLLM) accept a block_table index array alongside the query vector.
  2. The GPU thread block loops across the sequence’s allocated physical blocks: b = 0 to ceil(S / block_size) - 1.
  3. Keys and values from each block are loaded into on-chip memory (staging through shared memory or accumulated directly in registers depending on the kernel implementation), where dot products and online softmax reductions update running accumulation statistics.
  4. In the final block (b = ceil(S / block_size) - 1), unused tail positions beyond the valid context length S are masked out (e.g., initialized to negative infinity) to prevent unallocated slots from corrupting the softmax normalizer.

Not all paged attention kernels produce final outputs without auxiliary memory. In split-K implementations used for long contexts during decode, multiple thread blocks process different segments of the sequence’s blocks concurrently. These kernels write intermediate partial sums and reduction statistics to a global memory scratchpad buffer before a secondary reduction kernel computes the final output vector.

14. Copy-on-write sharing and branch isolation

Section titled “14. Copy-on-write sharing and branch isolation”

Parallel sampling (e.g., generating multiple candidate responses for one prompt) and shared system prompts introduce opportunities to share KV blocks across distinct logical requests.

Copy-on-write sharing and branch isolation

Before and after copy-on-write isolation when two sequences share a prompt tail.
Read this diagram as text

Copy-on-write sharing and branch isolation is shown as an illustrative worked trace with block size 16. Before the fork, Sequence A and Sequence B share physical blocks 10, 11 and 12, each with reference count 2; block 12 is the shared tail holding valid positions 32–34. When Sequence A appends KV position 35, block 12 is shared so it cannot be written in place. The engine allocates physical block 13, copies the 3 valid KV positions (32–34) from block 12 into block 13, writes position 35 into block 13 at offset 3, decrements block 12's reference count to 1, and assigns block 13 to Sequence A (reference count 1, private). Sequence B keeps block 12 (now reference count 1, private to B) and appends its own position 35 directly. Full prefix blocks 10 and 11 remain shared with reference count 2. The diagram distinguishes the 3 valid KV positions copied from the 16-slot block capacity and makes no claims about bytes copied by any particular runtime.

Quick Check

Section titled “Quick Check”

Question: When Sequence A appends at position 35, how many existing KV positions are copied, and how many stay shared in the full prefix blocks?

Answer: Three valid KV positions (positions 32–34) are copied from Block 12 into Block 13, and 32 positions remain shared in full prefix Blocks 10 and 11.

15. Immutable shared blocks and tail cloning

Section titled “15. Immutable shared blocks and tail cloning”
  1. Full shared blocks: Any block that contains block_size tokens and has a reference count greater than 1 (ref_count > 1) is completely immutable. After KV writes complete and visibility is established, requests can read the immutable payload concurrently. Reference-count updates and reclamation still require coordinated lifetime management.
  2. Copy-on-write for shared tail blocks: When a sequence consumes a token in a forward pass and appends that input position’s key-value representations:
    • If the sequence’s tail block is shared (ref_count > 1), the engine cannot append to it in place without corrupting the sibling sequence.
    • The engine allocates a new physical block from the free list, copies the valid cached tokens from the shared tail block into the new block, decrements the reference count of the original block, and updates the sequence’s block table to point to the new block (ref_count = 1).
    • If the sequence’s tail block is already private (ref_count == 1) and contains empty slots, the engine appends the new KV representations directly into the existing block without allocating new memory.

16. Worked trace: 35-token prompt fork

Section titled “16. Worked trace: 35-token prompt fork”

Consider a request with a 35-token prompt using block_size = 16:

  1. Prompt setup:
    • ceil(35 / 16) = 3 blocks.
    • Block 10: tokens 0..15 (16 tokens, full, ref_count = 1)
    • Block 11: tokens 16..31 (16 tokens, full, ref_count = 1)
    • Block 12: tokens 32..34 (3 tokens, 13 unused slots, ref_count = 1)
  2. Branch fork:
    • A parallel branch (Sequence B) forks from Sequence A.
    • Sequence B duplicates Sequence A’s block table: [10, 11, 12].
    • The engine increments the reference count for each block: ref_counts = {10: 2, 11: 2, 12: 2}.
  3. Subsequent forward execution (append KV position 35):
    • The initial prefill of prompt tokens 0..34 produced the first sampled output token. When that token is consumed as input during the next forward decode pass, its key and value representations materialize and are appended at zero-based KV position 35 (the 36th cached token).
    • Sequence A performs this forward step. It examines its tail block (Block 12). Because ref_count == 2, writing in place is forbidden.
    • CoW triggers: the engine allocates Block 13, copies tokens 32..34 from Block 12 into Block 13, decrements Block 12’s reference count to 1, and assigns Block 13 to Sequence A (block_table[A][2] = 13, ref_count = 1).
    • Sequence A appends KV position 35 into Block 13 at offset 3 (now holding tokens 32..35).
    • Sequence B executes its forward step. It examines its tail block (Block 12). Block 12 now has ref_count == 1 because Sequence A detached from it.
    • Sequence B writes its KV position 35 directly into Block 12 at offset 3 without triggering a copy or allocating a new block.

17. Slot accounting and release invariants

Section titled “17. Slot accounting and release invariants”

At the end of this step:

  • Full shared blocks: Blocks 10 and 11 provide 32 slots storing 32 common prompt tokens.
  • Private tail blocks: Block 12 holds 4 tokens for Sequence B (12 unused slots). Block 13 holds 4 tokens for Sequence A (12 unused slots).
  • Physical blocks in use: 4 blocks (64 total slots).
  • Useful tokens stored: 40 tokens (32 + 4 + 4).
  • Tail waste: 24 slots (12 + 12).
  • Contiguous equivalent: Storing both sequences without sharing would require 6 blocks (96 slots). CoW sharing saves 32 slots (2 full blocks).

When Sequence A finishes execution, the engine decrements reference counts along its block table:

  • Block 10: ref_count decrements from 2 to 1 (retained by Sequence B).
  • Block 11: ref_count decrements from 2 to 1 (retained by Sequence B).
  • Block 13: ref_count decrements from 1 to 0 (recyclable after any in-flight GPU reads/writes complete).

18. Automatic prefix caching vs. immediate freeing

Section titled “18. Automatic prefix caching vs. immediate freeing”

In a simple allocator, any block whose reference count drops to 0 is immediately recycled to the free list.

In modern engines supporting Automatic Prefix Caching (APC), blocks with active reference count 0 are not immediately destroyed. Instead, they are retained in an LRU eviction structure indexed by both their token content and their parent block identity (using hash chaining or radix tree prefixes). This ensures blocks with identical token text are only matched if their preceding prefix context is also identical. If a future request arrives with an identical prefix chain, the engine reclaims the existing physical block and increments its reference count from 0 back to 1, bypassing prefill computation. Cached blocks in an APC-enabled engine remain reusable even when their active reference count is 0.

19. Memory exhaustion and scheduling policies

Section titled “19. Memory exhaustion and scheduling policies”

PagedAttention eliminates external memory fragmentation within the block pool, but it does not eliminate the physical capacity limits of GPU HBM. When aggregate batch concurrency and sequence lengths consume all available physical blocks, the engine faces memory exhaustion.

Paged memory does not dictate a single preemption policy. When no free blocks remain to satisfy a decode step, an engine may select from several scheduling policies:

Pool Exhaustion Handling Options:
1. Admission Deferral: Pause scheduling new requests until active sequences finish.
2. Cache Eviction: Recycle unreferenced (ref_count == 0) prefix-cached blocks.
3. Preemption via Recompute: Free a sequence's private blocks; re-run prefill later.
4. Preemption via Swapping: Transfer physical blocks to CPU host memory over PCIe.
5. Error Rejection: Terminate requests gracefully with HTTP 429/503 status codes.
  1. Admission control: The engine schedules incoming requests into the running batch, but initial admission cannot guarantee that unpredictable future generation steps will not exhaust memory. Engines must perform per-step scheduling and capacity checks before each decode iteration.
  2. Reclaiming unreferenced cache: An engine can prefer reclaiming unreferenced cached blocks before preempting active requests; the selection order is runtime policy, not a property of paged addressing.
  3. Preemption via recomputation: The engine selects an active request (often using a last-arrived priority rule), frees its private physical blocks back to the pool, and returns the request to the waiting queue. When memory becomes available, the request’s KV cache is recomputed across its entire consumed history, including prompt tokens and previously generated output tokens. In modern architectures (such as vLLM v1), recomputation is often preferred over PCIe swapping because high GPU tensor core throughput makes recalculating activations faster than transferring gigabytes over bandwidth-constrained PCIe buses.
  4. Preemption via swapping: As designed in Kwon et al. (2023), physical blocks can be swapped out to host CPU memory over PCIe and swapped back in when GPU blocks are released.
  5. Request cancellation: Under extreme overload, the engine can reject incoming requests with explicit error codes rather than crashing the serving process.

PagedAttention does not guarantee arbitrary increases in concurrent serving capacity. Concurrency gains depend directly on the sequence length distribution, prefix sharing characteristics, and whether the workload is memory-bandwidth bound or compute-bound.

20. Executable Python 3 verification

Section titled “20. Executable Python 3 verification”

The following standalone script is a single-head scalar CPU teaching model that demonstrates application-level fixed-size block paging, physical K/V payload storage, and copy-on-write semantics using pure Python standard library. It is designed to illustrate mapping and isolation principles, not GPU kernel execution or GQA tensor operations.

import math
from typing import Dict, List, Tuple




class PagedScalarAllocator:
    """
    Single-head scalar CPU teaching model demonstrating application-level
    fixed-size block paging, physical K/V payload storage, and copy-on-write semantics.
    Not a GPU or GQA kernel.
    """
    def __init__(self, num_blocks: int, block_size: int):
        if num_blocks <= 0 or block_size <= 0:
            raise ValueError("Pool size and block size must be positive.")
        self.num_blocks = num_blocks
        self.block_size = block_size
        self.free_blocks: List[int] = list(reversed(range(num_blocks)))
        self.ref_counts: Dict[int, int] = {i: 0 for i in range(num_blocks)}
        self.block_tables: Dict[str, List[int]] = {}
        self.seq_lengths: Dict[str, int] = {}
        # Physical storage: scalar (K, V) tuple per slot in each block
        self.storage: List[List[Tuple[float, float]]] = [
            [(0.0, 0.0) for _ in range(block_size)] for _ in range(num_blocks)
        ]


    def allocate_sequence(self, seq_id: str, prompt_kvs: List[Tuple[float, float]]) -> bool:
        if seq_id in self.block_tables:
            raise ValueError(f"Sequence {seq_id} already exists.")
        prompt_length = len(prompt_kvs)
        if prompt_length <= 0:
            raise ValueError("Prompt must be non-empty.")


        needed = math.ceil(prompt_length / self.block_size)
        if len(self.free_blocks) < needed:
            return False


        assigned = []
        for _ in range(needed):
            b = self.free_blocks.pop()
            self.ref_counts[b] = 1
            assigned.append(b)


        self.block_tables[seq_id] = assigned
        self.seq_lengths[seq_id] = prompt_length


        for idx, (k, v) in enumerate(prompt_kvs):
            b_idx = assigned[idx // self.block_size]
            offset = idx % self.block_size
            self.storage[b_idx][offset] = (k, v)
        return True


    def fork_sequence(self, parent_id: str, child_id: str) -> bool:
        if parent_id not in self.block_tables or child_id in self.block_tables:
            return False
        parent_blocks = self.block_tables[parent_id]
        for b in parent_blocks:
            self.ref_counts[b] += 1
        self.block_tables[child_id] = list(parent_blocks)
        self.seq_lengths[child_id] = self.seq_lengths[parent_id]
        return True


    def append_token(self, seq_id: str, k_val: float, v_val: float) -> bool:
        """Appends one scalar (K, V) position. Transactional on pool exhaustion."""
        if seq_id not in self.block_tables:
            return False
        curr_len = self.seq_lengths[seq_id]
        tail_offset = curr_len % self.block_size


        if tail_offset != 0:
            tail_block = self.block_tables[seq_id][-1]
            if self.ref_counts[tail_block] > 1:
                if not self.free_blocks:
                    return False
                new_block = self.free_blocks.pop()
                self.ref_counts[new_block] = 1
                self.ref_counts[tail_block] -= 1
                # Copy existing valid payloads into the cloned private block
                for i in range(tail_offset):
                    self.storage[new_block][i] = self.storage[tail_block][i]
                self.block_tables[seq_id][-1] = new_block
                self.storage[new_block][tail_offset] = (k_val, v_val)
            else:
                self.storage[tail_block][tail_offset] = (k_val, v_val)
        else:
            if not self.free_blocks:
                return False
            new_block = self.free_blocks.pop()
            self.ref_counts[new_block] = 1
            self.block_tables[seq_id].append(new_block)
            self.storage[new_block][0] = (k_val, v_val)


        self.seq_lengths[seq_id] = curr_len + 1
        return True


    def free_sequence(self, seq_id: str) -> None:
        if seq_id not in self.block_tables:
            return
        for b in self.block_tables[seq_id]:
            self.ref_counts[b] -= 1
            if self.ref_counts[b] == 0:
                self.free_blocks.append(b)
        del self.block_tables[seq_id]
        del self.seq_lengths[seq_id]




def paged_attention_scalar(
    query: float, allocator: PagedScalarAllocator, seq_id: str, scale: float = 1.0
) -> float:
    """CPU scalar reference attention with stable softmax over paged blocks."""
    block_table = allocator.block_tables[seq_id]
    seq_len = allocator.seq_lengths[seq_id]
    b_size = allocator.block_size
    num_blocks = math.ceil(seq_len / b_size)


    keys, vals = [], []
    for b_idx in range(num_blocks):
        phys_id = block_table[b_idx]
        valid_len = b_size if b_idx < num_blocks - 1 else seq_len - b_idx * b_size
        for slot in range(valid_len):
            k, v = allocator.storage[phys_id][slot]
            keys.append(k)
            vals.append(v)


    scores = [query * k * scale for k in keys]
    max_score = max(scores)
    exp_scores = [math.exp(s - max_score) for s in scores]
    sum_exp = sum(exp_scores)
    weights = [e / sum_exp for e in exp_scores]
    return sum(w * v for w, v in zip(weights, vals))




def run_tests():
    print("=" * 60)
    print("Running PagedAttention Reference Verification Suite")
    print("=" * 60)


    # Test 1: Capacity and tail waste on unaligned requests (B8, pool=16 blocks=128 slots)
    alloc = PagedScalarAllocator(num_blocks=16, block_size=8)
    requests = [("req_A", 17), ("req_B", 31), ("req_C", 32), ("req_D", 33)]
    for req_id, length in requests:
        dummy_payload = [(float(i), float(i)) for i in range(length)]
        assert alloc.allocate_sequence(req_id, dummy_payload)
    total_slots = sum(len(alloc.block_tables[r]) * alloc.block_size for r, _ in requests)
    tail_waste = total_slots - sum(l for _, l in requests)
    assert total_slots == 128 and tail_waste == 15
    print("Test 1 Passed: 4 unaligned requests fit 128 slots with 15 waste slots.")


    # Test 2: Copy-on-write isolation with distinct payload appended
    cow_alloc = PagedScalarAllocator(num_blocks=6, block_size=4)
    prompt = [(float(i), float(i * 10)) for i in range(6)]
    assert cow_alloc.allocate_sequence("A", prompt)
    assert cow_alloc.fork_sequence("A", "B")
    assert cow_alloc.append_token("A", 99.0, 990.0)
    assert cow_alloc.append_token("B", 88.0, 880.0)
    tail_A = cow_alloc.block_tables["A"][1]
    tail_B = cow_alloc.block_tables["B"][1]
    assert tail_A != tail_B, "CoW must allocate distinct physical tail block"
    assert cow_alloc.storage[tail_A][2] == (99.0, 990.0) and cow_alloc.storage[tail_B][2] == (88.0, 880.0)
    assert cow_alloc.storage[tail_A][0] == prompt[4]
    print("Test 2 Passed: CoW payload copy and branch isolation verified.")


    # Test 3: Mathematical equivalence (paged vs unpaged dense softmax)
    paged_sys = PagedScalarAllocator(num_blocks=4, block_size=4)
    # Non-identity, non-contiguous physical order catches direct-index mistakes.
    paged_sys.free_blocks = [1, 3, 0, 2]
    test_kv = [(0.5, 1.2), (1.1, -0.4), (-0.8, 2.0), (0.9, 0.5), (1.4, -1.1), (-0.2, 0.8)]
    assert paged_sys.allocate_sequence("eval_seq", test_kv)
    assert paged_sys.block_tables["eval_seq"] == [2, 0]
    tail_phys = paged_sys.block_tables["eval_seq"][1]
    paged_sys.storage[tail_phys][2] = (999.0, -999.0)  # Tail junk masked
    paged_sys.storage[tail_phys][3] = (888.0, -888.0)  # Tail junk masked


    q = 1.3
    paged_out = paged_attention_scalar(q, paged_sys, "eval_seq", scale=0.5)


    dense_scores = [q * k * 0.5 for k, _ in test_kv]
    dense_max = max(dense_scores)
    dense_exp = [math.exp(s - dense_max) for s in dense_scores]
    dense_weights = [e / sum(dense_exp) for e in dense_exp]
    dense_out = sum(w * v for w, (_, v) in zip(dense_weights, test_kv))


    assert math.isclose(paged_out, dense_out, rel_tol=1e-6), "Paged output must match dense output"
    print("Test 3 Passed: Paged vs dense attention exact within tolerance.")


    # Test 4: Transactional failure on allocation exhaustion leaves state unchanged
    tiny = PagedScalarAllocator(num_blocks=1, block_size=4)
    assert tiny.allocate_sequence("seq", [(1.0, 1.0)] * 4)
    assert not tiny.append_token("seq", 2.0, 2.0)
    assert tiny.seq_lengths["seq"] == 4 and len(tiny.block_tables["seq"]) == 1
    print("Test 4 Passed: Exhaustion append fails transactionally without state mutation.")


    # Test 5: Release all references frees entire pool
    cow_alloc.free_sequence("A")
    cow_alloc.free_sequence("B")
    assert len(cow_alloc.free_blocks) == cow_alloc.num_blocks
    assert all(r == 0 for r in cow_alloc.ref_counts.values())
    print("Test 5 Passed: Sequence releases reclaim all pool blocks.")


    print("=" * 60)
    print("All reference verification tests passed successfully!")
    print("=" * 60)




if __name__ == "__main__":
    run_tests()

Execute the verification script with:

Terminal window
python3 test_paged_attention.py

Expected terminal output

Section titled “Expected terminal output”
============================================================
Running PagedAttention Reference Verification Suite
============================================================
Test 1 Passed: 4 unaligned requests fit 128 slots with 15 waste slots.
Test 2 Passed: CoW payload copy and branch isolation verified.
Test 3 Passed: Paged vs dense attention exact within tolerance.
Test 4 Passed: Exhaustion append fails transactionally without state mutation.
Test 5 Passed: Sequence releases reclaim all pool blocks.
============================================================
All reference verification tests passed successfully!
============================================================

21. Empirical evaluation and primary references

Section titled “21. Empirical evaluation and primary references”

In the paper introducing PagedAttention (Efficient Memory Management for Large Language Model Serving with PagedAttention, Kwon et al., SOSP 2023), the authors evaluated memory efficiency and serving throughput across conversation and parallel sampling workloads. The paper demonstrated that contiguous reservation baselines incurred severe memory waste from over-allocation and fragmentation, and reported workload-dependent serving throughput improvements when switching to paged block allocation.

Actual throughput gains depend heavily on sequence length distributions, hardware memory bandwidth, and batch concurrency. System designers should consult the primary research and implementation documentation:

22. Checkable engineering exercises

Section titled “22. Checkable engineering exercises”

Exercise 1: Block size capacity planning

Section titled “Exercise 1: Block size capacity planning”

An inference cluster serves a model where each cached token across all layers requires 256 KiB of memory. The engine administrator allocates an 8 MiB KV payload buffer (32 token slots).

Three requests arrive with total cached lengths of [7, 11, 10] tokens (total: 28 useful tokens).

  1. Compute the total number of blocks, total allocated slots, and tail waste slots if the engine uses block_size = 4.
  2. Compute the total number of blocks, total allocated slots, and tail waste slots if the engine uses block_size = 8.
  3. Which block size configuration can schedule all three requests simultaneously within the 8 MiB pool?
  4. What is the internal fragmentation percentage (tail waste / total allocated slots) for the fitting configuration?

Exercise 2: Copy-on-write reference tracing

Section titled “Exercise 2: Copy-on-write reference tracing”

A sequence Seq_A has 22 cached tokens. The engine uses block_size = 8.

  1. How many blocks are initially allocated to Seq_A?
  2. A parallel branch Seq_B forks from Seq_A. What are the reference counts of all blocks in the pool?
  3. Seq_A appends 10 new KV positions across subsequent generation steps, while Seq_B generates no new tokens.
    • Describe each block allocation or CoW event during this generation process.
    • What are the final block tables for Seq_A and Seq_B?
    • What are the final reference counts of all allocated blocks?
    • How many total physical slots are allocated, and how many are tail waste?

Solutions

Section titled “Solutions”

23. Solution to exercise 1

Section titled “23. Solution to exercise 1”
  1. For block_size = 4:
    • Req 1 (7 tokens): ceil(7 / 4) = 2 blocks -> 8 slots (tail waste: 1 slot)
    • Req 2 (11 tokens): ceil(11 / 4) = 3 blocks -> 12 slots (tail waste: 1 slot)
    • Req 3 (10 tokens): ceil(10 / 4) = 3 blocks -> 12 slots (tail waste: 2 slots)
    • Total blocks = 2 + 3 + 3 = 8 blocks.
    • Total slots = 8 + 12 + 12 = 32 slots.
    • Total memory = 32 slots * 256 KiB/token = 8 MiB.
    • Total tail waste = 1 + 1 + 2 = 4 slots.
  2. For block_size = 8:
    • Req 1 (7 tokens): ceil(7 / 8) = 1 block -> 8 slots (tail waste: 1 slot)
    • Req 2 (11 tokens): ceil(11 / 8) = 2 blocks -> 16 slots (tail waste: 5 slots)
    • Req 3 (10 tokens): ceil(10 / 8) = 2 blocks -> 16 slots (tail waste: 6 slots)
    • Total blocks = 1 + 2 + 2 = 5 blocks.
    • Total slots = 8 + 16 + 16 = 40 slots.
    • Total memory = 40 slots * 256 KiB/token = 10 MiB.
    • Total tail waste = 1 + 5 + 6 = 12 slots.
  3. Fitting configuration: Only block_size = 4 fits within the 8 MiB pool (requires exactly 32 slots). block_size = 8 requires 40 slots (10 MiB) and exceeds pool capacity.
  4. Internal fragmentation percentage:
    • Tail waste ratio = 4 / 32 = 0.125 = 12.5%.

24. Solution to exercise 2

Section titled “24. Solution to exercise 2”
  1. Initial allocation:
    • ceil(22 / 8) = 3 blocks:
      • Block 0: tokens 0..7 (full, 8 tokens)
      • Block 1: tokens 8..15 (full, 8 tokens)
      • Block 2: tokens 16..21 (6 tokens, 2 empty slots)
  2. Fork state:
    • block_table[Seq_A] = [Block 0, Block 1, Block 2]
    • block_table[Seq_B] = [Block 0, Block 1, Block 2]
    • Reference counts: {Block 0: 2, Block 1: 2, Block 2: 2}
  3. Appending 10 tokens to Seq_A:
    • Token 22: Tail Block 2 is shared (ref_count == 2). CoW triggers. The engine allocates Block 3, copies tokens 16..21 into Block 3, decrements Block 2’s reference count to 1, sets Block 3’s reference count to 1, and assigns Block 3 to Seq_A. Token 22 is appended at offset 6 in Block 3. (Seq_A length = 23).
    • Token 23: Block 3 is private (ref_count == 1) and has 1 empty slot at offset 7. Token 23 is written in place without allocation. (Seq_A length = 24, Block 3 is now full).
    • Token 24: Block 3 is full. The engine allocates a new block (Block 4, ref_count = 1). Token 24 is written at offset 0. (Seq_A length = 25).
    • Tokens 25 through 31 (7 tokens): Block 4 is private and has space for remaining offsets 1 through 7. Tokens are written directly in place. (Seq_A length = 32, Block 4 is now full).
    • Final block tables:
      • Seq_A: [Block 0, Block 1, Block 3, Block 4] (32 tokens)
      • Seq_B: [Block 0, Block 1, Block 2] (22 tokens)
    • Final reference counts:
      • Block 0: 2 (shared)
      • Block 1: 2 (shared)
      • Block 2: 1 (private to Seq_B)
      • Block 3: 1 (private to Seq_A)
      • Block 4: 1 (private to Seq_A)
    • Total slots and tail waste:
      • Total physical blocks in use: 5 blocks = 40 slots.
      • Cached payload copies stored across active sequences: 38 token positions (16 shared prefix tokens in Blocks 0 and 1 counted once, plus 6 private tokens in Block 2 and 16 private tokens in Blocks 3 and 4, which includes duplicated tail context from the fork).
      • Total tail waste: 2 slots (the 2 unused slots in Block 2).

24. Sources and implementation scope

Section titled “24. Sources and implementation scope”

The vLLM stable documentation is a moving reference, accessed 2026-11-03. Pin a release and selected attention backend before relying on a layout or policy in production. The CPU examples are original teaching models, not GPU benchmarks.