PagedAttention in vLLM: scattered memory, exact attention

Memory fragmentation is what happens when free space exists, but the pieces are awkward to use. Before we talk about vLLM, imagine trying to seat six friends together in a room with eight empty chairs scattered across different tables. Enough chairs; no table with six adjacent seats.

LLM serving has the same kind of problem. Each conversation grows as tokens arrive, and its attention history needs memory. PagedAttention lets that history occupy scattered blocks while the model still attends to the correct sequence. To see why this preserves the mathematics, we first need the operating-system idea it borrows: virtual memory.

1. Free memory can still be unusable

External fragmentation means gaps between live allocations. Suppose a memory pool has free regions of 3 MB, 2 MB, and 3 MB, separated by data that is still in use. An allocator demanding one contiguous 6 MB region cannot satisfy the request from that pool, even though 8 MB is free in total.

Internal fragmentation means unused space inside an allocation. Reserve room for 100 tokens, then finish after 30: 70 token slots were reserved without useful data. Reserving the maximum possible conversation length for every request also strands capacity that other conversations could have used.

Fixed-size pages let us assemble a large logical allocation from smaller free pieces. They reduce the need for one huge gap. They do not make waste literally disappear: the last partly filled page can still have unused slots.

Eight MB are free, but the largest gap is only three MB. A six MB contiguous allocation fails; six one MB pages fit the scattered space. Cell sizes are illustrative.

2. Virtual memory gives an application an address space

A program uses virtual addresses: addresses in its own view of memory. Physical RAM is divided into equal-size frames; the virtual address space is divided into pages of the same size. A page table maps a virtual page number to a physical frame number. Consecutive virtual pages can map to frames far apart in RAM.

For a toy page size of 4,096 bytes, virtual address 5,000 lies in page 1 with an offset of 904 bytes. If the page table maps page 1 to physical frame 9, the physical address is 9 × 4,096 + 904 = 37,768. The offset stays the same; only the page’s location changes.

virtual page = floor(virtual address / page size)
offset       = virtual address mod page size
physical address = frame[virtual page] × page size + offset

Here, floor means round down to a whole number, and mod means the remainder after division. The application can walk through a contiguous virtual array while address translation follows different physical frames. Its entire address space need not be one allocated array; the continuity applies to the particular mapped range it is using.

Further reading: Operating Systems: Three Easy Pieces — Paging.

3. The MMU translates; the page table stores mappings

The memory management unit, or MMU, is hardware that translates addresses. The operating system maintains page tables in RAM; the MMU does not contain every page or all the program’s data. A small hardware cache called the translation lookaside buffer, or TLB, remembers recent translations. On a TLB miss, a page-table walk looks up the mapping.

If a page is not present, or the access violates permissions, a page fault transfers control to the operating system. The OS can establish a valid mapping, fetch data when appropriate, or reject the access. A TLB miss alone is not a page fault. This separation lets software use simple addresses while the OS manages physical placement and access rights.

Further reading: Operating Systems: Three Easy Pieces — TLBs.

4. An LLM’s growing memory is its KV cache

A token is a small piece of text. In each attention layer, the model turns token representations into queries, keys, and values. A query asks what information matters now. A key helps score a stored token’s relevance. A value carries the information that gets mixed into the attention output. These are vectors: ordered lists of numbers.

During prefill, the model processes the prompt and stores its keys and values. During decode, it generates another token, adds new KV entries, and reuses previous entries. Causal attention ensures earlier tokens cannot depend on future tokens, so their cached entries remain valid as the conversation grows.

Weights are the learned parameters, normally reused across requests. KV cache is the per-sequence state that grows with context. PagedAttention’s contribution is how that changing state is allocated and read. Modern vLLM also handles model loading, quantization, scheduling, and distributed serving, but paging itself does not change the learned weights.

KV bytes ≈ 2 × L × T × Hkv × D × b

This estimate assumes ordinary dense-attention KV with equal key and value dimensions: 2 for keys plus values, L layers, T cached tokens, Hkv key/value heads, D numbers per head, and b bytes per number. It omits padding, metadata, and workspace. With 32 layers, 4,096 tokens, 8 KV heads, 128 numbers per head, and 2-byte numbers, one sequence needs 536,870,912 bytes: 512 MiB.

Further reading: The original PagedAttention paper.

5. PagedAttention adds a block table

vLLM divides a sequence’s KV cache into blocks holding a fixed number of token positions. Each request has a block table mapping logical block numbers to physical cache blocks. The kernel uses that table to read the right keys and values, even when neighboring logical blocks live in distant parts of GPU memory.

This is an analogy to OS paging, implemented explicitly by the serving engine and attention kernels. vLLM does not ask the CPU’s MMU to remap every KV block into a contiguous array. Logical token order and positional information remain intact; physical adjacency is unnecessary.

Logical block 0tokens 0–3 → physical block 9

Logical block 1tokens 4–7 → physical block 2

Logical block 2tokens 8–9 → physical block 14

One ordered sequence, three scattered cache blocks. The final block has two unused slots. This toy example uses four tokens per block.

For token position t and block size B, the logical block is floor(t / B) and the slot is t mod B. In the example, token 6 is in logical block 1, slot 2. The table sends the kernel to physical block 2. Real layouts also index the layer, KV head, and vector dimension.

Blocks are assigned as a sequence grows rather than reserving its maximum output length. Within a uniform block pool, any free block can serve the next allocation. For one unshared sequence, unused tail capacity is at most B − 1 token slots per KV layout. Pool sizing, backend padding, and mixed attention layouts still have their own costs.

Further reading: vLLM’s paged-attention kernel design.

The block table maps logical blocks 0, 1, 2 to physical KV blocks 9, 2, 14. Reads preserve token order 0 through 9. This example uses four tokens per block; the final two slots are unused.

6. Prefix caching reuses work; eviction reclaims space

Imagine two requests begin with the same eight token IDs and then ask different questions. With four tokens per block, both can reuse the first two full KV blocks. Their suffixes get separate blocks. Matching text later in a different conversation is insufficient: a token’s KV state depends on its entire preceding context.

vLLM identifies full reusable blocks using hashes that include the block’s tokens and the preceding prefix, plus relevant context such as adapter identity or multimodal inputs. Reference counts track which requests still use a block. Shared cached content must remain unchanged; diverging writable state needs private storage, with copy-on-write where shared partial blocks are supported.

When a request finishes, its blocks can become available for allocation while reusable prefix data remains cached. Under pressure, the documented V1 cache manager reclaims eligible zero-reference blocks through an LRU-style free queue. Blocks still referenced by active requests are not casually overwritten. Evicting an idle prefix means a future miss recomputes it; it does not delete context from a running request.

Paging tackles allocation waste. Prefix sharing tackles duplicated state and repeated prefill. Eviction decides which idle entries survive memory pressure. If active requests themselves cannot fit, scheduling can preempt a request and later recompute its state. These mechanisms improve capacity without treating required attention history as disposable.

Further reading: vLLM prefix-cache design and eviction.

Prefix caching mainly saves prompt computation. A new decoded token must still attend to the required cached history. Continuous batching lets completed requests leave and new requests join between steps; better KV utilization makes room for more useful work in those batches.

Further reading: vLLM automatic prefix caching.

Requests A and B share two full prefix blocks. When A finishes, B keeps its active references. Only A’s now-idle suffix block is reclaimed for a new allocation. This is a schematic ownership example, not a particular LRU queue trace.

7. Different attention types change what a block stores

Multi-head attention, or MHA, gives each query head its own key and value head. Grouped-query attention, or GQA, lets several query heads share a KV head. Multi-query attention, or MQA, shares one KV head across all query heads. For otherwise equal dimensions, fewer KV heads mean fewer cached numbers.

A toy model with 32 query heads might use 32 KV heads for MHA, 8 for GQA, or 1 for MQA. Relative KV sizes are then 32:8:1. Paging can organize any of these supported layouts; it does not turn an MHA checkpoint into a GQA checkpoint. The trained architecture defines the head relationships.

8. Smaller KV cache does not automatically mean linear attention

Let n be sequence length. Dense prefill compares n queries with up to n keys, giving O(n²) attention work for fixed head dimensions. Doubling n roughly quadruples the pairwise work. A single dense decode step has only one new query against n stored keys, giving O(n); generating many steps adds those growing costs together.

A sparse attention stage that reads at most k selected entries per query costs O(nk) during prefill and O(k) per decode query, with fixed dimensions. If k stays fixed, that stage scales linearly with n. But selection can still scan growing history, and compressed or windowed branches have their own costs. This is a stage-level calculation, not proof that every DeepSeek model’s entire inference is linear.

Paging itself preserves the chosen attention rule and its asymptotic arithmetic. It changes allocation and access. Sparse attention changes which positions participate; latent compression changes representation; quantization changes precision. Exactness from rearranging blocks should be evaluated against the same model, attention mask, and numeric precision.

In V3.2’s reference implementation, the indexer scores queries against the preceding key history before choosing top-k positions. At fixed index dimensions, that retains an O(n²) score-selection component over a full prompt. This is a complexity inference from the code, not a latency benchmark; sparse main attention still reduces the more expensive work.

Further reading: DeepSeek-V3.2 reference indexer.

9. Matrix multiplication, one row at a time

A matrix is a rectangular table of numbers. To multiply matrices A and B, take one row from A and one column from B, multiply matching entries, and add them. A’s column count must equal B’s row count. Entry Cᵢⱼ uses row i and column j; the index r runs over the shared dimension.

C = A × B
Cᵢⱼ = Σᵣ Aᵢᵣ Bᵣⱼ

             [3  4]
[1  2]   ×   [5  6]   = [13  16]

first output  = 1 × 3 + 2 × 5 = 13
second output = 1 × 4 + 2 × 6 = 16

The symbol Σ means “add all these terms.” The same multiplication can be split across two blocks: [1] × [3, 4] + [2] × [5, 6] = [3, 4] + [10, 12] = [13, 16]. Splitting the storage does not omit a multiplication or a contribution.

10. Exact attention across two scattered pages

For one query row q, stack the cached keys as rows of K and the values as rows of V. Kᵀ means transpose: turn K’s rows into columns. The query-key multiplication gives one score per token. Divide by √d, the square root of the key dimension d, then use softmax to turn scores into positive weights summing to one. Finally multiply those weights by V.

s = q Kᵀ / √d
aᵢ = exp(sᵢ) / Σⱼ exp(sⱼ)
o = a V = Σᵢ aᵢ vᵢ

Here s is the score row, a is the attention-weight row, and o is the output row. exp(x), also written eˣ, raises the constant e ≈ 2.71828 to x. ln is its inverse, so exp(ln 3) = 3. We choose logarithms below to make the weights easy to check. All four positions are visible to this query; a causal kernel would mask any future or unfilled positions.

Further reading: Attention Is All You Need.

d = 2                 q = [√2, 0]

    [0      1]             [1  0]
K = [ln 2   0]         V = [0  2]
    [ln 3   1]             [3  1]
    [ln 4  −1]             [2  4]

q Kᵀ / √2 = [0, ln 2, ln 3, ln 4]
exp(scores) = [1, 2, 3, 4]
a = [1, 2, 3, 4] / 10

For example, the third dot product is √2 × ln 3 + 0 × 1. Dividing by √2 leaves ln 3. Softmax’s denominator is 1 + 2 + 3 + 4 = 10. The final multiplication takes the weighted sum of the four value rows:

o = (1×[1,0] + 2×[0,2] + 3×[3,1] + 4×[2,4]) / 10
  = ([1,0] + [0,4] + [9,3] + [8,16]) / 10
  = [18,23] / 10
  = [1.8,2.3]

For this separate worked example, use two tokens per page. Store the first two KV rows in physical page 9 and the last two in physical page 2. The block table preserves their logical positions. Each page can calculate its unnormalized value sum N and its weight sum Z independently. We then add the sums before dividing. This can be processed in tiles or split across parallel workers; it need not be a separate kernel call for every page.

page A: Zₐ = 1 + 2 = 3
        Nₐ = 1×[1,0] + 2×[0,2] = [1,4]

page B: Zᵦ = 3 + 4 = 7
        Nᵦ = 3×[3,1] + 4×[2,4] = [17,19]

o = (Nₐ + Nᵦ) / (Zₐ + Zᵦ)
  = [18,23] / 10
  = [1.8,2.3]

There is no approximation here: the split calculation includes the same terms as the contiguous calculation. Physical location is absent from the equation. The example computes one head’s attention output; the model’s remaining layers and output projection turn that result into next-token logits and probabilities.

Each value row is multiplied by its unnormalized attention weight. Page sums [1,4] and [17,19] combine into [18,23]; dividing once by the global weight sum 10 gives [1.8,2.3], exactly as in the contiguous calculation. This separate example uses two tokens per page.

11. Stable block merging keeps the same normalization

Real scores can be large enough that exp overflows. Subtracting one common maximum m from every score prevents this without changing softmax: the factor exp(−m) cancels between numerator and denominator. A block can store its maximum mᵦ, shifted weight sum zᵦ, and shifted weighted-value sum uᵦ. These summaries can be merged exactly in real arithmetic.

For each block b:
  mᵦ = max of its scores
  zᵦ = Σᵢ exp(sᵢ − mᵦ)
  uᵦ = Σᵢ exp(sᵢ − mᵦ) vᵢ

Merge blocks:
  m = maxᵦ mᵦ
  z = Σᵦ exp(mᵦ − m) zᵦ
  u = Σᵦ exp(mᵦ − m) uᵦ
  o = u / z

The subscript b names a block; i runs over tokens inside it. max chooses the largest number. In our example, page A has mₐ = ln 2, zₐ = 1.5, and uₐ = [0.5, 2]. Page B has mᵦ = ln 4, zᵦ = 1.75, and uᵦ = [4.25, 4.75]. At the shared maximum ln 4, rescale A by 1/2 and B by 1.

z = 0.5 × 1.5 + 1 × 1.75 = 2.5
u = 0.5 × [0.5,2] + [4.25,4.75] = [4.5,5.75]
o = [4.5,5.75] / 2.5 = [1.8,2.3]

This proves that partitioning KV into blocks does not require dropping tokens or estimating attention. It does not promise bit-for-bit equality between arbitrary GPU executions. Floating-point sums can round differently when kernels, batch sizes, or reduction orders change. Quantized KV introduces a separate precision tradeoff, and sampling can select different tokens even from the same probabilities.

The precise claim is that paging adds no approximation to the model’s specified attention. Compare the same model, mask, KV precision, and decoding settings. For repeatable outputs, also control backend behavior and scheduling; vLLM documents batch-invariance support and its limits.

12. The useful distinction

Fragmentation is about unusable gaps or unused reserved capacity. Paging makes small allocations easier to place.
Virtual memory separates logical addresses from physical storage. An MMU translates using page-table mappings and cached TLB entries.
PagedAttention preserves logical token order while KV blocks occupy scattered locations. It changes storage access, not the attention definition.
Prefix caching shares already computed state. Eviction reclaims eligible idle blocks; it does not silently discard required active context.
MHA, GQA, MLA, and sparse or compressed attention define different state and computation. Model-compatible backends must respect those definitions.
Blocked matrix multiplication and globally normalized softmax reproduce the same mathematical attention result. Paging adds no approximation.

Sources checked on October 3, 2026. The worked numbers and diagrams are illustrative; block sizes, supported backends, and cache policies depend on the installed vLLM version.

More engineering notes