2.1 PagedAttention

The KV Cache memory ledger in the last chapter left one problem open: traditional contiguous GPU-memory allocation wastes a lot through “reserve means waste,” and real utilization can sit at only 20–30% (the vLLM paper measured that only 20.4%–38.2% of KV Cache memory in then-current systems actually held Token state). vLLM fixes this with PagedAttention by moving OS-style memory paging onto GPU memory. This section covers four things: what idea it borrows, how the Block Table works, why it kills fragmentation, and the prefix-sharing ability paging also unlocks.

⏰ Freshness: Paging, the block table, and CoW follow the PagedAttention paper; default parameters and the V1 source walkthrough are based on vLLM v0.32.0 (released 2026-10-18).

📑 Contents

• 1. Problem recap: the two sins of contiguous allocation
• 2. Core idea: borrow OS virtual-memory paging
• 3. Block Table: mapping logical blocks to physical blocks
• 4. How paging kills fragmentation
• 5. Kernel view: how scattered physical blocks are read
• 6. Bonus: memory sharing and Copy-on-Write
• 7. Preemption and recovery: what if GPU memory runs out
• 8. Practice: tuning PagedAttention in vLLM
• 9. Source walkthrough: KV Cache management in vLLM V1
• 10. Costs and trade-offs
• Summary
• Self-check list
• References

---

1. Problem recap: the two sins of contiguous allocation

Before the fix, nail the problem. Traditional inference frameworks (before PagedAttention) gave each request’s KV Cache one contiguous GPU slab, reserved for “the longest this request might generate.” That creates two sins:

• Internal Fragmentation: If a request might generate up to 2048 Tokens, you reserve 2048 Tokens of space, but it may stop at EOS after only 100. The remaining 1948 Token slots are “locked” by this request and unused; other requests cannot enter.
• External Fragmentation: Large reserved slabs leave uneven gaps between them. The scraps may add up to a lot, but no single gap fits a full new request, so they are all wasted.

Analogy: a restaurant reserves a 10-person table for every party “in case 10 show up.” Most tables seat two or three people; lots of chairs sit empty. A new party of 4 still queues at the door because no whole empty table is free — even though the empty seats added up would fit them easily.

📌 Key point: Fragmentation comes from stacking contiguous + reserved. Drop “must be contiguous” and “must reserve for max length,” and fragmentation goes away. PagedAttention starts right there.

---

2. Core idea: borrow OS virtual-memory paging

Operating systems hit the same problem decades ago: processes want a contiguous address space, but physical memory is chopped up by every process. The OS answer is virtual-memory paging — the process sees contiguous “virtual addresses,” and the OS maps them through a Page Table onto arbitrary scattered “physical pages.” The process feels like it owns one contiguous slab; physically it is pieced together from here and there.

PagedAttention copies that mechanism onto the KV Cache:

• Split the KV Cache into fixed-size KV Blocks; each block holds Keys and Values for a fixed number of Tokens (that count is block_size; in vLLM a common value is 16).
• One request’s KV Cache is a contiguous sequence of “logical blocks” logically, but physically may sit anywhere in GPU memory.
• A Block Table records “which logical block of this request maps to which physical block in GPU memory.”

🔑 Core idea: PagedAttention = virtual-memory paging for the KV Cache. The Token sequence is cut into blocks, allocated on demand, and mapped through a block table. From then on GPU memory need not be contiguous, and you no longer reserve ahead for max length.

💡 Tip: The vLLM docs stress that a KV Block here is vLLM’s own GPU-memory unit, completely different from a CUDA “thread block.” Do not mix them up.

---

3. Block Table: mapping logical blocks to physical blocks

The Block Table is the hub of the mechanism. Here is a worked example.

Assume block_size = 4 (each block holds KV for 4 Tokens; real workloads often use 16; we use 4 so the picture is easy). A request Prefills 9 Tokens, so it needs $\lceil 9/4 \rceil = 3$ logical blocks:

• Logical block 0: Tokens 0~3
• Logical block 1: Tokens 4~7
• Logical block 2: Token 8 (only 1 slot used, 3 left)

vLLM allocates 3 physical blocks from the free pool — physical IDs need not be contiguous, for example #7, #2, #5. The Block Table looks like:

The figure puts that table back into GPU memory: left is the request’s 3 contiguous logical blocks, middle is the Block Table, right is the physical pool. Solid red/yellow/green cells are KV already written for logical blocks 0, 1, 2; green hatched cells are allocated-but-empty slots in #5; purple and pink hatched blocks belong to other requests; white cells are free.

In Decode, each new Token fills the next empty slot in the current logical block. Logical block 2 still has 3 slots, so it can take 3 more Tokens; once full (at Token 12), vLLM on demand asks for a new physical block and hangs it on logical block 3 — allocate what you use, never reserve ahead.

During Attention, the CUDA Kernel uses the Block Table to get each logical position’s physical_block_number and physical_block_offset, then reads the full history of KV from the scattered physical blocks.

---

4. How paging kills fragmentation

Back to the two sins in section 1, and how paging breaks each one:

• Kill internal fragmentation: No more reserve-for-max-length; allocate one block at a time and ask for the next only when full. Waste is capped at “the unfilled part of the last block,” at most under one block (for example at most 15 Token slots when block_size=16). Against the old habit of wasting thousands of Token slots, that is negligible.
• Kill external fragmentation: Every physical block is exactly the same size, so any free block can serve any request. There is no “enough space but the wrong shape”; every block in the free pool is equivalent and reusable.

The figure compares both allocators on the same 64 Token slots. Solid cells are written Tokens (red/blue/green for requests A/B/C); same-color hatched cells are reserved-but-unused slots (internal fragmentation); gray dashed cells are scattered holes between reserved regions (external fragmentation); white cells are free. On the left, free slots add up enough for new request C, but no contiguous stretch is long enough; on the right C takes two non-adjacent free blocks.

📌 Key point: Higher memory utilization means the same card can hold more concurrent requests. The last chapter showed Decode is Memory Bound; packing more requests into one Batch raises system throughput a lot, so the memory PagedAttention saves turns into throughput.

---

5. Kernel view: how scattered physical blocks are read

So far the story was logical mapping. Once KV is scattered across GPU memory, how does the Attention Kernel still gather it efficiently? This section looks inside the Kernel. Understanding it shows PagedAttention is not only a memory trick; it is co-design of the operator and the memory layout.

Traditional Attention assumes one sequence’s K and V are laid out contiguously; the Kernel walks them with a base address plus offset. PagedAttention breaks contiguity, so the Kernel must consult the block table first and translate “logical position” into “physical address.” Two quantities matter:

• physical_block_number: Which physical block to read; multiply by the block stride to get the block base.
• physical_block_offset: Which slot inside that block holds this Token.

In vLLM’s official Kernel docs, Key pointer address math looks roughly like this (simplified sketch, not a verbatim copy):

// From physical block number + head offset + in-block offset, get this token's Key start address
const scalar_t* k_ptr = k_cache
                      + physical_block_number * kv_block_stride   // locate the physical block
                      + kv_head_idx           * kv_head_stride    // locate the KV head
                      + physical_block_offset * x;                // locate the token inside the block

A Warp (32 threads) advances block by block in the outer loop: each iteration jumps to the next physical block by block number, and k_ptr points at Keys in a different block. So storage that is physically scattered is accessed as one logically contiguous context. The cost of the indirection sits in recomputing addresses each iteration; section 10 (“Costs and trade-offs”) covers that overhead.

⚠️ Note: That official Kernel walkthrough is marked as “historical documentation based on the original paper; it no longer reflects current vLLM code.” Treat the pointer formula above as a principle sketch, not current source. For the real implementation, look at the V1 engine’s Attention backends (section 2.5 covers how FlashAttention/FlashInfer and others take over this layer).

---

6. Bonus: memory sharing and Copy-on-Write

Paging also unlocks something contiguous allocation cannot do: multiple requests sharing the same physical block.

Because KV is referenced indirectly by blocks through the block table, several requests’ tables can point at the same physical block. Typical cases:

• Cross-request prefix sharing: A batch of requests shares the same System Prompt, so their prefix KV is identical — no need to store it N times. Point every Block Table at the same physical blocks. This sharing is read-only: each request only reads those prefix blocks and writes new content into its own blocks. That is the physical basis for the next section (2.3 Prefix Cache).
• Forks inside one request: When you sample multiple answers from one Prompt in parallel (n > 1) or run Beam Search, candidates share the Prompt KV but start to diverge inside a block — that is when CoW below is needed.

What if two sequences sharing a block later diverge? The PagedAttention paper (and vLLM V0) answers with another classic OS mechanism — Copy-on-Write (CoW):

• While shared read-only, everyone points at the same block; a reference count (ref_cnt) tracks how many requests use it.
• When a request must write into a shared block, copy that block into a private copy first, write on the copy, then retarget its Block Table. Other requests are untouched.

The figure shows read-only sharing on the left and CoW when B writes on the right. Blue is Prompt KV shared by both requests; red and yellow are Tokens A and B write themselves; white cells are empty slots.

💡 Tip: “Reference count + Copy-on-Write” is the same idea as parent and child processes sharing pages after Linux fork(). If you already know OS paging and CoW, almost nothing in PagedAttention is new — that is part of why the design feels clean.

---

7. Preemption and recovery: what if GPU memory runs out

Paging fixes “how to store efficiently,” but there is still a practical problem: too many concurrent requests drain the physical block pool, and a new Decode step cannot get a block. You cannot just crash the request. vLLM’s answer is Preemption: like an OS scheduling processes, temporarily “pause” some requests, give their resources to others, and resume when space returns.

The trigger is direct: a Decode step needs new blocks for some requests, but free physical blocks are not enough. The scheduler picks some requests to “kick out” and frees their physical blocks. For a kicked request’s already-computed KV Cache there are two options:

Analogy: swapping is putting papers you do not need right now into a drawer (CPU memory) and taking them out later; recomputation is throwing the draft away and re-deriving from memory (the Tokens already generated). Which wins depends on “is the drawer big enough / is the transfer fast enough” versus “how expensive is re-deriving.”

💡 Tip: The table above is the paper and V0 story. vLLM V1 preemption only recomputes: a preempted request frees all blocks, zeroes num_computed_tokens, and goes back to the head of the waiting queue; resume means Prefill again. The official tuning docs say recompute is cheaper under the V1 architecture. With Prefix Cache on, full blocks that were freed but not yet evicted can still hit on resume, so less work is recomputed.

📌 Key point: Preemption is vLLM’s safety net under memory pressure so you do not OOM and requests do not fail. If logs keep warning about preemption, concurrency is too high — lower concurrency, raise gpu_memory_utilization to give the KV Cache more room, or add GPUs. It is a signal that “the system is bracing,” not the steady state.

---

8. Practice: tuning PagedAttention in vLLM

As a user you can steer PagedAttention with these engine parameters (defaults from vLLM v0.32.0; check vllm serve --help when you change versions).

from vllm import LLM

llm = LLM(
    model="meta-llama/Llama-3.1-8B-Instruct",
    # Max fraction of total GPU memory this vLLM instance may use; after weights
    # and activation peaks, the rest goes to the KV Cache block pool. Default 0.92 in v0.32.0.
    gpu_memory_utilization=0.92,
    # How many tokens of KV each KV Block holds. The basic paging grain.
    block_size=16,
    # Turn on prefix caching so requests with the same prefix reuse physical blocks (see §2.3).
    enable_prefix_caching=True,
    # Max sequences processed together in one batch.
    max_num_seqs=256,
)

How each parameter relates to PagedAttention:

• gpu_memory_utilization: Default in v0.32.0 is 0.92 (earlier versions used 0.9), so the instance may use up to 92% of GPU memory; whatever is left after weights and activations becomes the KV Cache block pool. Higher means more concurrency and fewer preemptions, but less headroom for activations and other overhead; too aggressive and you OOM.
• block_size: Paging grain — Tokens per block, as above. Docs call it “contiguous cache block size in Tokens.” Trade off “Block Table length / management cost” against “internal fragmentation in the tail block.”
• enable_prefix_caching: When on, requests that share a prefix (for example a shared System Prompt) reuse already-cached physical blocks and skip repeated Prefill. This is the config switch for the memory-sharing ability in section 6.
• max_num_seqs: Max sequences per iteration; together with Continuous Batching in the next section it sets the concurrency ceiling.

💡 Tip: In most cases you do not need to change block_size by hand — the default is already tuned on most models. The knobs you actually turn are gpu_memory_utilization (squeeze memory) and enable_prefix_caching (turn on when prefixes are shared).

---

9. Source walkthrough: KV Cache management in vLLM V1

This section shows how vLLM turns “block table + free pool + reference counts” into code. It is based on the vLLM V1 engine under vllm/v1/core/ (code keeps moving; treat method signatures as version-dependent, and treat this as the stable design skeleton).

⚠️ Note: The Kernel doc cited in section 5 is a V0-era historical document. The V1 engine rewrote scheduling and KV Cache management and concentrates the logic in two core classes, KVCacheManager and BlockPool. What follows is the V1 implementation.

9.1 How the two core classes split work

V1 draws a clean line:

• KVCacheManager (kv_cache_manager.py): Manager from the request’s view. Every scheduler step goes through it to allocate and free blocks for requests. Core methods map one-to-one onto the concepts above:
  • get_computed_blocks: Prefix-cache lookup; returns already-computed blocks this request can hit, and how many Tokens hit. Entry point for “shared prefix” in section 6.
  • allocate_slots: Ask for slots/blocks for new Tokens on a request, free blocks no longer needed, and check whether free blocks are enough; if not, return None (scheduler then preempts). This is “allocate block by block on demand” from section 3.
  • free: When a request ends, free its blocks in reverse order — reclaim the tail first, because head blocks are more likely to be reused by the prefix cache and should live longer.
• BlockPool (block_pool.py): Global physical-block warehouse. It does not care which request owns what; it only tracks “which blocks are free, which are cached.”

9.2 Why free blocks use a doubly linked list

An easy-to-miss detail: BlockPool keeps every block in an ordinary list self.blocks: list[KVCacheBlock] (indexed by block id), but free blocks are managed by a separate FreeKVCacheBlockQueue — internally a doubly linked list, not a plain stack or deque.

Free blocks need two operations at once:

• On allocate, take N quickly from the head (popleft_n);
• On a prefix-cache hit, a block that is “free but still holds reusable content” must be reactivated — plucked from an arbitrary middle position in the list (remove).

An ordinary queue cannot delete from the middle in $O(1)$; a doubly linked list can. Prefix caching needs “a free block may still carry reusable cache,” so vLLM chose a doubly linked list.

9.3 Reference counts and free order

ref_cnt is the spine of memory sharing. Behavior in code matches the “read-only sharing” part of section 6:

# Pseudocode: restore BlockPool's key logic (not verbatim source)
def get_new_blocks(self, num_blocks):
    if num_blocks > self.get_num_free_blocks():
        raise ValueError("not enough free blocks")   # trigger upper-layer preemption
    blocks = self.free_block_queue.popleft_n(num_blocks)
    for blk in blocks:
        assert blk.ref_cnt == 0                 # a freshly allocated block must have no refs
        blk.ref_cnt += 1
    return blocks

def free_blocks(self, ordered_blocks):
    for blk in ordered_blocks:
        blk.ref_cnt -= 1
    to_free = [b for b in ordered_blocks if b.ref_cnt == 0]   # only reclaim when nobody uses it
    no_hash = [b for b in to_free if b.block_hash is None]
    has_hash = [b for b in to_free if b.block_hash is not None]
    self.free_block_queue.prepend_n(no_hash)    # no cache value: list head, reused first
    self.free_block_queue.append_n(has_hash)    # hashed: list tail, evicted last

def touch(self, blocks):                        # called on a prefix-cache hit
    for blk in blocks:
        if blk.ref_cnt == 0:                    # "rescue" it from the free list
            self.free_block_queue.remove(blk)
        blk.ref_cnt += 1

Two designs worth remembering:

1. Free does not mean clear: A block whose ref_cnt hits zero only returns to the free list; content stays. If a later request’s prefix hash hits it, touch() revives and reuses it. That is the low-level mechanism behind Automatic Prefix Caching skipping repeated Prefill.
2. Hashed blocks live longer: On free, vLLM puts “no-cache-value blocks” at the list head (reallocated and overwritten first; source comments say that also lets just-freed blocks be reused immediately for better GPU locality) and “hashed, reusable blocks” at the list tail (evicted later). Allocation always takes from the head, so hashed blocks are evicted in free order — effectively LRU.

⚠️ Note: V1’s BlockPool has no CoW. The three functions above only bump ref_cnt and splice the free list; there is no “copy a block” path. V1 can skip CoW for two design reasons:

• Only share full blocks: Prefix caching hashes and shares only blocks that are already full; the unfilled tail block is never shared. Newly generated Tokens always append into the request’s own new blocks. Cross-request prefix sharing is therefore always read-only; there is never a “write into a shared block” moment.
• n > 1 becomes independent child requests: V1 splits parallel sampling into n child requests with n = 1 each (see ParentRequest in vllm/v1/engine/parallel_sampling.py). Children share the Prompt’s full blocks through the prefix cache and no longer need in-block forks.

So the CoW in section 6 is a paper and V0 mechanism (V0’s cow_block_if_not_appendable left with V0). Understanding it helps grasp the design; you will not find matching code on the V1 KV Cache path.

📌 Key point: When reading the source, hold this main line — KVCacheManager owns requests, BlockPool owns physical blocks, ref_cnt owns sharing, FreeKVCacheBlockQueue owns eviction. Together they implement the paging, read-only sharing, and preemption from sections 3–7.

---

10. Costs and trade-offs

PagedAttention has costs; engineering needs the trade-offs clear:

• ✅ Gains: Near-optimal memory utilization, prefix sharing, and recovery via preemption when memory runs out (paper and V0 support swap and recompute; V1 only recomputes) instead of failing outright.
• ❌ Costs: The Attention Kernel needs an extra block-table lookup and indirection (the pointer recomputation in section 5); more complex than naive contiguous Attention. The Block Table itself also costs a bit of management overhead.

On block_size: too small and the Block Table grows and management cost rises; too large and internal fragmentation returns (more waste in the last block). vLLM’s common default of 16 sits in the middle between management cost and fragmentation.

⚠️ Note: The “paging + block table + reference counts” stressed throughout this article is vLLM’s stable design foundation (CoW exists only in the paper and V0; see §9.3). Concrete data structures in the V1 engine (for example the KV Cache Manager) have been rewritten several times. Learn the unchanging core idea; treat the latest source as authoritative for code details.

---

📝 Summary

• PagedAttention moves OS virtual-memory paging onto the KV Cache: cut into blocks, allocate on demand, map through a block table.
• The Block Table maps the contiguous logical blocks a request sees onto physically scattered physical blocks, so memory need not be contiguous and need not be reserved for max length.
• On the Kernel side, physical_block_number + physical_block_offset look up addresses and read scattered physical blocks as a logically contiguous context — co-design of the operator and the memory layout.
• It kills both internal fragmentation (no over-reservation) and external fragmentation (uniform block size), pushes utilization near optimal, and turns that into higher concurrency and throughput.
• Paging naturally supports memory sharing + Copy-on-Write, which lays the ground for prefix reuse (Prefix Cache).
• When memory is drained, preemption is the safety net (paper and V0 can swap to CPU or recompute; V1 defaults to and only uses recompute) so requests fail soft instead of OOMing.
• In practice the knobs you turn are gpu_memory_utilization and enable_prefix_caching; block_size trades management cost against fragmentation (vLLM commonly uses 16).
• In source, the V1 engine lands this with KVCacheManager (requests) + BlockPool (physical blocks) + ref_cnt (sharing) + FreeKVCacheBlockQueue (eviction).

🎯 Self-check list

• Explain what causes internal vs external fragmentation under contiguous allocation
• Explain the Block Table via a “logical block → physical block” map
• Draw a request’s Block Table after Prefill and describe how blocks grow on demand in Decode
• Explain how the Attention Kernel reads scattered KV via physical block number and in-block offset
• Explain why PagedAttention can remove both internal and external fragmentation
• Explain how read-only sharing supports prefix reuse, how Copy-on-Write supports parallel sampling, and why V1 no longer needs CoW
• Distinguish the two preemption recovery modes (swap vs recompute) and their costs
• State what gpu_memory_utilization, block_size, and enable_prefix_caching each affect
• State the split of duties between KVCacheManager and BlockPool in vLLM V1
• Explain why free blocks use a doubly linked list instead of an ordinary queue
• Analyze what goes wrong if block_size is too large or too small
• Connect “save memory” to “raise throughput” through the Memory Bound conclusion

📚 References

• Efficient Memory Management for Large Language Model Serving with PagedAttention (vLLM paper)
• vLLM blog: Easy, Fast, and Cheap LLM Serving with PagedAttention
• vLLM Design — PagedAttention Kernel
• vLLM Design — Automatic Prefix Caching
• vLLM — Engine Arguments
• vLLM — Optimization and Tuning (preemption and V1 recompute)
• vLLM V1 source — vllm/v1/core (KVCacheManager, BlockPool)