PagedAttention and vLLM: Virtual Memory for the KV Cache

Start with the problem, because PagedAttention is unintelligible without it.

12-05 established that a KV cache holds one key and one value entry per token, per layer, per attention head, and that it grows as the sequence grows. A serving system must allocate memory for that cache. The naive approach — and it was the standard approach — is to reserve one contiguous region per request, sized to the maximum sequence length the request could possibly reach, because the attention kernel expects contiguous tensors and you cannot know in advance how many tokens the model will generate before emitting an end-of-sequence token.

That produces three distinct kinds of waste, and naming all three is the point:

All three are consequences of the same design choice — one contiguous, maximum-sized region per request — and all three are exactly the problems operating systems solved for process memory decades ago. The solution there was paging: divide memory into fixed-size pages, let a process's address space be a scattered collection of physical pages, and use a page table to translate logical addresses into physical ones. A process's memory then appears contiguous to the process and is anything but contiguous in reality.

PagedAttention applies that structure to the KV cache. GPU memory reserved for cache is divided into fixed-size KV blocks, each holding the keys and values for a small fixed number of tokens (a block size of 16 tokens is a commonly cited default; the exact value is configuration- and version-dependent). Each sequence has a block table — its page table — mapping logical block indices to physical block numbers. When a sequence needs room for token 17 and its current block is full, the allocator hands it any free block, anywhere in the pool, and appends the mapping to its block table. When the sequence finishes, all its blocks return to the pool immediately.

Two properties follow, and they are the entire value proposition:

1. Internal fragmentation is bounded by one block. A sequence wastes at most block_size − 1 token slots in its final partially-filled block, instead of max_length − actual_length. With a block size of 16, average waste is around 8 token slots per sequence rather than potentially thousands.
2. External fragmentation disappears. All blocks are the same size, so any free block satisfies any request. There is no such thing as a gap too small to use.

And one further property that is not obvious from the OS analogy but turns out to be enormously useful: because sequences reference blocks through a table, two sequences can point at the same physical block. That enables sharing, and sharing enables prefix reuse and cheap parallel sampling, discussed below.

L1 — Intuition: a hotel that assigns rooms, not floors

Contiguous allocation is a hotel that gives every guest an entire floor because the guest might bring twenty friends. Most guests arrive alone. The hotel fills up with empty rooms and turns away paying customers while three-quarters of the building is unoccupied.

Paged allocation is a hotel that assigns rooms one at a time as guests actually arrive, keeps a list of which rooms belong to which party, and does not care whether a party's rooms are adjacent. Occupancy goes from a quarter to nearly full, and nothing about the guests' experience changes — the front desk's list is what makes a scattered set of rooms behave like a suite.

The block table is the front desk's list. The attention kernel consults it instead of assuming adjacency.

L2 — Mechanism: blocks, block tables, and a modified attention kernel

The block pool. At startup the server measures how much GPU memory remains after loading weights and reserving workspace, and carves the remainder into a fixed number of uniform KV blocks. That count is the hard capacity of the system: total tokens of cache that can be resident at once equals num_blocks × block_size, regardless of how those tokens are distributed across sequences. This is a genuinely different capacity model from contiguous allocation, where capacity depended on the shape of the requests as well as their total size.

The block table. Per sequence, an array mapping logical block index → physical block number. A sequence at token 40 with block size 16 occupies three blocks: logical 0 (tokens 0–15), logical 1 (tokens 16–31), and logical 2 (tokens 32–39, partially filled). Its table has three entries pointing at three arbitrary physical blocks.

The allocation lifecycle.

admit sequence      → allocate ceil(prompt_len / block_size) blocks, populate during prefill
each decode step    → write the new token's K,V into the last block
                      if that block is now full, allocate one more block
sequence finishes   → return every block in its table to the free pool
memory pressure     → preempt a sequence: swap its blocks to host memory, or
                      discard them and recompute the prefill when readmitted

The kernel change. This is why PagedAttention is a kernel technique and not merely an allocator. A standard attention kernel is given a contiguous K tensor and strides through it. A paged kernel is given the block table and gathers each block's keys and values from its physical location as it computes the attention scores. The indirection has to be inside the kernel, at the point where memory is read, or the whole scheme collapses back into needing contiguity. That is the reason "just use a smarter allocator" is not a substitute: the attention computation itself must be block-aware.

Copy-on-write sharing. Because blocks are referenced rather than owned, a block can be shared. Each physical block carries a reference count. Two situations exploit this:

• Shared prefixes. Many requests begin with the same long system prompt or the same retrieved document. Those tokens produce identical K and V (a consequence of causal masking, as 12-05 explains), so the blocks holding them can be shared across all those sequences instead of duplicated. This is the memory-side counterpart of prefix caching.
• Parallel sampling and beam search. Generating n candidate completions from one prompt means n sequences sharing an identical prefix and diverging afterwards. Under contiguous allocation you pay n full copies of the prompt's cache. Under paging you pay one copy plus the divergent tails.

When a shared block would be written to — the sequences have diverged and one needs to append a token into a block another is using — the allocator copies that single block, decrements the original's reference count, and lets the writer modify its private copy. That is textbook copy-on-write, and it means sharing costs nothing until divergence and then costs exactly one block.

L3 — vLLM, preemption policy, and the honest limits

vLLM is the open-source LLM inference and serving engine that introduced PagedAttention and built its scheduler around it. Its identity, stated at the level the exam cares about:

• A serving engine for LLM inference: takes a model, exposes an inference API, manages GPU memory and scheduling.
• Built on PagedAttention for cache memory management and continuous batching for scheduling — the two together, because as 12-06 argues, iteration-level scheduling demands fine-grained memory allocation.
• Supports the operational features that follow from block sharing: prefix caching, parallel sampling, and preemption with swap-or-recompute.
• It is open source and vendor-neutral, which is the cleanest way to distinguish it from NVIDIA's stack in a question. NVIDIA's counterparts are TensorRT-LLM (the optimizing compiler and runtime with its own paged attention and in-flight batching), Triton Inference Server (the general multi-model serving layer), and NIM (the packaged microservice). vLLM overlaps functionally with parts of that stack; it is not part of it.

Preemption policy. When the block pool is exhausted and a resident sequence needs another block, something must give. Two strategies:

Whichever is chosen, preemption is all-or-nothing per sequence — you cannot half-evict a sequence, because attention needs the whole history. And victim selection is a policy question with fairness consequences, typically last-arrived-first-preempted so that long-running work is not repeatedly restarted.

The honest limits, because vendor-neutral enthusiasm is not analysis.

• PagedAttention does not reduce the amount of cache a sequence actually needs. The formula in 12-05 still governs. It removes waste, which is a different and bounded quantity. If your working set genuinely needs 40 GB of cache, paging will not make it fit in 24.
• The indirection has a cost: the block table lookup and the gather inside the attention kernel are real work, and a paged kernel is more complex than a contiguous one. The trade is overwhelmingly favourable in practice because the memory savings buy larger batches, but it is a trade.
• Block size is a tuning parameter with a genuine trade-off. Small blocks minimize internal fragmentation and maximize sharing granularity, but multiply block-table size and per-block bookkeeping. Large blocks reduce overhead and waste more.
• Prefix sharing only helps where prefixes actually match, token for token. A system prompt that embeds a timestamp or a user name at the top shares nothing. This is a real design lesson: put the variable parts of a prompt after the invariant parts if you want prefix reuse.
• Paging solves fragmentation. It does not solve bandwidth. Reading the cache every decoding step still costs bandwidth proportional to its size, so a large resident working set still slows decode.

Against the allocation scheme it replaces:

Against its own source of inspiration, which is the analogy worth being able to state out loud:

Against the neighbouring techniques it is confused with:

FlashAttention versus PagedAttention is the most common genuine confusion, because both have "attention" in the name and both are memory-related. The clean split: FlashAttention makes the attention computation move fewer bytes; PagedAttention makes the attention cache waste fewer bytes. One is a compute-kernel optimization, the other a memory-allocation architecture, and production systems use both.

A constructed scenario, all figures derived from stated assumptions. Reuse the model from 12-05: 32 layers, hidden size 4096, BF16 cache, so 512 KB of cache per token. The server has 24 GB of memory available for KV cache after weights and workspace. The API's maximum sequence length is 2,048 tokens.

Traffic: eight concurrent requests whose actual total lengths (prompt + generation) are 180, 220, 260, 310, 400, 520, 1,400 and 1,900 tokens. Total actual = 5,190 tokens.

Scheme A — contiguous allocation, pre-sized to the maximum.

per request reservation = 2,048 tokens × 512 KB = 1,048,576 KB ≈ 1.05 GB
eight requests          = 8 × 1.05 GB           ≈ 8.39 GB reserved
actually used           = 5,190 tokens × 512 KB ≈ 2.66 GB
internal fragmentation  = 8.39 − 2.66           ≈ 5.73 GB wasted (68.3%)

maximum concurrent requests = 24 GB / 1.05 GB   ≈ 22 requests

Twenty-two concurrent requests is your hard ceiling regardless of how short they are, because each reserves a full 2,048-token region on admission. Two-thirds of the cache memory is reserved and untouched.

Scheme B — PagedAttention with a 16-token block size.

block size in bytes = 16 tokens × 512 KB = 8,192 KB = 8 MB per block
total blocks in pool = 24 GB / 8 MB      = 3,072 blocks
total resident token capacity = 3,072 × 16 = 49,152 tokens

Now allocate the same eight requests by blocks needed, ceil(length / 16):

180  → 12 blocks (192 slots, 12 wasted)
220  → 14 blocks (224 slots,  4 wasted)
260  → 17 blocks (272 slots, 12 wasted)
310  → 20 blocks (320 slots, 10 wasted)
400  → 25 blocks (400 slots,  0 wasted)
520  → 33 blocks (528 slots,  8 wasted)
1400 → 88 blocks (1408 slots, 8 wasted)
1900 →119 blocks (1904 slots, 4 wasted)
       ---------
total  328 blocks = 5,248 token slots for 5,190 actual tokens
internal fragmentation = 58 token slots = 1.1%
memory used = 328 × 8 MB = 2.63 GB

Fragmentation fell from 68.3% to 1.1%. And the concurrency ceiling changes character entirely:

blocks free after these eight = 3,072 − 328 = 2,744 blocks
additional requests admissible at ~300 tokens each (19 blocks) ≈ 144 more requests

Where contiguous allocation capped you at 22 concurrent requests of any length, paging admits requests until the actual token total reaches 49,152 — so about 160 requests averaging 300 tokens, or about 24 requests averaging 2,000 tokens. Capacity became a function of real demand rather than declared maximums. That is the single most important consequence, and it is why the technique changed serving economics rather than merely improving a number.

A second calculation: parallel sampling with block sharing. Suppose one request has a 1,000-token prompt and asks for 4 candidate completions of 200 tokens each.

Without sharing:
  4 sequences × (1,000 prompt + 200 generated) = 4,800 tokens of cache
  = 4,800 × 512 KB ≈ 2.46 GB

With block sharing (prompt blocks shared, copy-on-write at divergence):
  prompt: ceil(1000/16) = 63 blocks, shared once
  each completion: ceil(200/16) = 13 blocks × 4 = 52 blocks
  plus up to 4 copied blocks at the divergence boundary   ≈ 4 blocks
  total ≈ 119 blocks = 1,904 token slots ≈ 0.98 GB

saving ≈ 60%

The saving grows with the prompt-to-completion ratio, which is precisely the regime RAG operates in: long retrieved context, short answer. A RAG service generating multiple candidates or serving many users off one large shared document set is where block sharing pays best.

The check that keeps this honest. Paging did not make the 5,190 tokens of genuinely-needed cache any smaller — 2.63 GB paged versus 2.66 GB of real usage in the contiguous scheme is the same data. What it removed was the 5.73 GB of reservation. If your traffic genuinely consisted of eight requests each running to the full 2,048 tokens, contiguous allocation would have wasted almost nothing and paging would have gained almost nothing. PagedAttention's benefit is proportional to the variance and unpredictability of sequence lengths — the same property that makes continuous batching valuable, which is not a coincidence.

The direct hook is a product-identity fact the course index flags as high-value: paged attention appears on the list of LLM-specific capabilities that TensorRT-LLM adds on top of TensorRT, alongside KV cache management, in-flight/continuous batching, and speculative decoding. TensorRT versus TensorRT-LLM is one of the two most-reported confusables on this exam, and the discriminating detail is precisely that list. If you can recite it, you can answer the question in either direction — "which of these is a TensorRT-LLM feature" or "what does TensorRT-LLM add for LLM workloads."

The broader hooks are objectives 4.1 (deployment and evaluation of model scalability, performance, and reliability) and 4.4 (identifying required system, hardware, and software components). Memory management for LLM serving is a capacity-planning topic and belongs to both.

A calibration warning belongs here, because this is the module's deepest lesson. Field reports on this exam are consistent that low-level mechanism — kernel internals, attention math, YAML configuration — did not appear and was described as overkill. So the study posture for this lesson is: memorize the identity and the association, understand the fragmentation story well enough to explain it in two sentences, and do not attempt to memorize block-table internals. The 3,500-plus words here exist to make the mechanism intelligible, not because the exam will interrogate it.

Question phrasings:

• "Which technique manages KV cache memory in non-contiguous fixed-size blocks?" — PagedAttention.
• "Paged attention is a feature of which NVIDIA product?" — TensorRT-LLM (not TensorRT).
• "What problem does PagedAttention primarily solve?" — memory fragmentation and over-reservation in the KV cache, enabling higher batch occupancy.
• "Which open-source inference engine introduced PagedAttention?" — vLLM.
• "PagedAttention is inspired by which computing concept?" — operating-system virtual memory and paging.
• "How does PagedAttention enable efficient parallel sampling?" — blocks holding the shared prompt prefix are referenced by multiple sequences with copy-on-write.

Distractor families:

PagedAttention is a technique for storing an LLM's KV cache in fixed-size blocks that need not be contiguous in GPU memory, using a per-sequence block table to map logical token positions onto physical block addresses. It exists to eliminate the waste produced by the previous standard approach, which reserved one contiguous region per request sized to the maximum sequence length that request might reach. That approach caused internal fragmentation — a request that could generate 2,048 tokens but stops at 180 wastes over 90% of its reservation — plus reservation waste and external fragmentation. With paging, a sequence's cache grows one small block at a time and returns to a shared pool the moment it finishes, so internal fragmentation is bounded by one block and external fragmentation is impossible because every block is interchangeable. The design is a direct transplant of operating-system virtual memory: pages, page tables, and copy-on-write, applied to attention.

The mapping is essentially one to one. A sequence's logical token positions correspond to a process's virtual address space; a KV block corresponds to a page; the block table is the page table; the GPU's pool of blocks is physical memory; and unused slots in a sequence's final partial block are the internal fragmentation any paged system accepts within its last page. The correspondence continues into the advanced features: sharing blocks between sequences with reference counting and copying only on write is exactly the copy-on-write behaviour an operating system uses after fork(), and swapping a sequence's blocks to host memory under pressure is paging to disk. The reason this transplant works is that both systems face the same underlying problem — allocating memory for a set of consumers whose eventual sizes are unknown at allocation time — and paging is the general solution to that problem, discovered in the 1960s and re-applied to attention.

vLLM is an open-source, vendor-neutral LLM inference and serving engine, best known for introducing PagedAttention and for pairing it with continuous batching. TensorRT-LLM is NVIDIA's LLM-specific optimization and runtime layer built on TensorRT, and its feature list — as recorded in the course source material — includes KV cache management, paged attention, in-flight (continuous) batching, and speculative decoding. So the two overlap functionally: both provide paged KV-cache management and iteration-level batching for LLM serving. They differ in provenance and in position within a stack. TensorRT-LLM is part of NVIDIA's stack, compiles models into optimized engines for NVIDIA GPUs, and is what NIM ships prebuilt engines from; vLLM is an independent project you deploy yourself. For exam purposes the discriminator is simple: paged attention as an NVIDIA product feature belongs to TensorRT-LLM, and if a question names vLLM it is naming an open-source engine, not an NVIDIA one.

No — it reduces the waste around the cache, which is a different quantity. The amount of cache a given sequence genuinely requires is fixed by the formula in 12-05: 2 × num_layers × num_kv_heads × head_dim × sequence_length × bytes_per_element. Paging does not alter a single term in that expression. What it removes is the memory reserved but unused: the gap between what a request might need and what it actually needs, plus the unusable gaps left behind by variable-sized allocations. In the constructed example above that gap was 68.3% of reserved memory, so removing it was transformative — but if the working set truly requires 40 GB of cache, paging will not fit it into 24. The techniques that reduce actual cache size are different ones: KV-cache quantization to halve bytes per element, a grouped-query attention model to cut the KV-head count, and shorter enforced contexts to cut sequence length. Production systems combine paging with those, not instead of them.

Because generating several candidate completions from one prompt produces several sequences that share an identical prefix, and under paging an identical prefix can be stored once. The blocks holding the prompt's keys and values are referenced by every candidate's block table with a reference count above one; only the divergent tails get private blocks. When a candidate needs to write into a block another candidate is reading, the allocator copies just that one block — copy-on-write — so the cost of divergence is a single block rather than a full duplicate of the prompt's cache. In the constructed example above, four candidates from a 1,000-token prompt needed about 0.98 GB of cache with sharing against about 2.46 GB without, roughly a 60% saving, and the saving grows as the prompt-to-completion length ratio grows. That ratio is exactly the RAG regime — long retrieved context, short answer — which is why block sharing matters most in retrieval-augmented systems.

No, and they operate at different layers of the same stack. FlashAttention is an IO-aware attention kernel: it restructures the attention computation into tiles that fit in fast on-chip memory so that the large intermediate attention matrix never has to be written to and read back from HBM, which makes attention compute faster and lets longer sequences be processed. PagedAttention is a memory-management architecture for the KV cache: it decides how the already-computed keys and values are laid out in GPU memory and how that memory is allocated, freed, and shared. One reduces the bytes moved while computing attention; the other reduces the bytes wasted while storing attention's cache. They address different bottlenecks, they are not alternatives, and production serving stacks use both together. The confusion is understandable from the names alone, which is exactly why it makes a good distractor.

• PagedAttention stores the KV cache in fixed-size non-contiguous blocks with a per-sequence block table — operating-system paging, applied to attention.
• The problem it solves is fragmentation and over-reservation: contiguous per-request allocation sized to the maximum possible length wastes most of what it reserves.
• Internal fragmentation drops to at most one block per sequence; external fragmentation disappears because all blocks are interchangeable.
• In the constructed example, waste fell from 68.3% to 1.1%, and capacity changed from "22 requests regardless of length" to "49,152 resident tokens however you distribute them."
• Block sharing with reference counting and copy-on-write makes shared prefixes and parallel sampling far cheaper — roughly a 60% saving in the constructed four-candidate case.
• It reduces waste, not need. Actual cache size is still governed by the 12-05 formula; quantization and GQA are what shrink that.
• It does not reduce cache read bandwidth, and it is not an attention-compute optimization — FlashAttention is the compute-side technique, and the two are complementary.
• vLLM is the open-source engine that introduced it, paired with continuous batching. It is not an NVIDIA product.
• Paged attention is on the TensorRT-LLM feature list — with KV cache management, in-flight batching, and speculative decoding — and that list is how you answer the TensorRT-versus-TensorRT-LLM question.
• Study this to identity depth for the exam; the mechanism is here to make the rest of the module coherent, not because kernel internals are tested.

Next: 12-08 resolves the confusable this lesson has been pointing at. ONNX is the framework-neutral exchange format, TensorRT is the general-purpose inference compiler that fuses layers and calibrates precision, and TensorRT-LLM is the LLM-specific layer on top that adds the KV cache, paged attention, in-flight batching, and speculative decoding — three different things that questions routinely present as one.