Operating systems
Part 6 of 6 · Virtual Memory — Paging, Swapping & CachesFrom Pages to KV Cache — Block Tables, Fragmentation, and Prefix Cache
This lesson is the OS lens on LLM KV cache, not a second PagedAttention tutorial. The existing lesson on PagedAttention teaches the block table, the attention kernel, and continuous batching; read it for engine internals. Here we take the vocabulary of the previous lessons and apply it: contiguous per-request KV reservation is segmentation and fails the same way, with internal waste from worst-case sizing and external fragmentation from churn; fixed-size KV blocks with a per-sequence block table are paging; block size is the page-size tradeoff; prefix caching is a page cache keyed by token content with refcounts and LRU; preemption by swapping blocks to CPU or recomputing them is demand paging where the backing store can be computation. We quantify fragmentation, build a prefix block cache that evicts like the kernel does, and work through swap versus recompute and KV offload tiers. The goal is to answer why PagedAttention uses pages, in OS terms, and to know exactly where the analogy breaks.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What OS idea is a max-context KV reservation?
Answer
Segmentation. The length is unknown, so you reserve the worst case, and most of the segment is never written.
L2
What OS idea is a fixed KV block?
Answer
A page. Any free block fits any logical block. External fragmentation disappears. Waste is the tail of the last block.
L3
What is the block table?
Answer
The page table for one sequence. It maps logical blocks to physical blocks. The attention kernel reads it. There is no hardware walker and no TLB.
L4
Why are only full blocks shared?
Answer
The partial last block will be appended by decode. Sharing it would copy on the next token. Full blocks are immutable prefixes.
L5
What does refcount zero mean?
Answer
The block is not mapped by a live request. It stays cached, like a clean page on the inactive list, until a miss needs the frame.
L6
Swap or recompute?
Answer
Compare bytes over the host link, both directions, with prefill time for that length under load. Long contexts and a fast link favor swap. Short sequences favor recompute.
L7
Where does the analogy break?
Answer
No MMU or TLB. The pool is reserved up front. A miss is FLOPs, not a disk read. Prefix keys include every earlier token. The scheduler picks whole sequences.
Failure modes
KV usage near 100 percent and rising preemptions
This is thrashing. Prefill steals compute and blocks from decode. Cap concurrency or context, or the loop continues.
Variable tokens at the front of the prompt
A timestamp or user id in the system prompt changes the chained hash. Later identical text misses.
Prefix cache sized as free memory
Cached blocks and live sequences share one pool. A full cache leaves no room to grow.
Tuned on an empty cache
Admission that fits the empty pool thrashes once real lengths and unique prompts arrive.
Misconceptions
PagedAttention is virtual memory, done.
The allocation geometry matches. The miss path, the reservation, and the lack of an MMU do not.
Any repeated sentence is a prefix hit.
The hash chains from the parent block. A different earlier token makes a different block.
Evicting a prefix is a disk read later.
Unless a CPU or remote tier kept a copy, the next request recomputes those blocks.
Interviewer traps
Teaching the attention kernel or the iteration scheduler from scratch.
Stay on fragmentation, block size, refcounts, and swap versus recompute. Name the engine page and stop.
Promising prefix hits across prompts that differ in the first tokens.
Put stable text first and variable text last. Say that partial blocks are not shared.
Design scenario
Same prompt for every reader.
Requirements
Describe the failure as thrashing. Explain why the system prompt is not hitting. Say how block size and admission change waste and preemption. Do not redesign the attention kernel.
Traffic / scale
Mixed short and long requests, many sharing a prefix, admitted until the pool looks full.
Latency
Re-prefill competes with decode. A swap pays the link twice.
Consistency
A prefix hit must cover the exact token chain, not a fuzzy match.
Availability
Rejecting or queueing a sequence is better than preempting one you just admitted.
Failure assumptions
- The block pool is pre-reserved.
- Plain LRU is the prefix policy.
- Unique prompts arrive in bursts.
Constraints
- Do not claim there is a disk behind every block.
- Do not duplicate the continuous-batching lesson.
Prompt
A serving pool reports KV cache usage near 100 percent, preemptions climbing, and time-to-first-token and inter-token latency both up. Most prompts share a long system prompt, but a request id is prepended. Block size is 128. The concurrency limit was chosen on an empty cache.
API
Which counter is the thrash signal?
Data
Where does the variable token sit in the prompt?
Architecture
What watermark stops admission before preemption?
How to hold KV for a request
Prefer
Fixed blocks, allocated as the sequence grows
Any free block fits any logical block. Waste is less than one block per sequence. Sharing a prefix is a refcount, not a copy.
- External fragmentation is gone.
- Refcount zero stays cached until a miss needs the frame.
- Admission and a watermark beat swap versus recompute.
Alternative
Reserve max context up front
Most requests are shorter than the maximum, so most of the reservation is never written. Exact-fit holes fail the same way segments do.
- Few sequences fit, so the batch is small.
- Decode is bandwidth-bound, so throughput falls with the batch.
- A burst of unique prompts flushes the shared prefix under plain LRU.
Read a KV decision as a paging decision
Stop when the next sentence would be the attention kernel.
- 1
Name the fragmentation
Worst-case reservation is internal waste. Exact contiguous fit is external fragmentation. - 2
Pick a block size like a page size
Tiny blocks waste nothing and hurt gathers. Huge blocks waste the tail and share coarsely. - 3
Cache full blocks by chained hash
A hit increments a refcount. Refcount zero is reclaimable. A different parent hash is a miss. - 4
Preempt only when nothing cached is free
Swap pays the link both ways. Recompute pays FLOPs. Fewer admissions avoid the choice.
The translation table
| OS concept | KV counterpart | Same | Different |
|---|---|---|---|
| Virtual address space | A sequence's logical token positions | Contiguous to the user, scattered physically | Grows one token per decode step, append-only |
| Page, 4 KiB | KV block, for example 16 tokens across layers | Fixed size, the unit of allocation | Byte size depends on layers, KV heads, head dim, and dtype |
| Page table | Block table per sequence | Maps logical to physical | Read by the attention kernel, not by an MMU. No TLB |
| Frame pool | Pre-reserved GPU block pool | A fixed set of physical units | Reserved up front, like hugetlbfs, not demand-allocated |
| Copy-on-write after fork | Shared blocks for beams, parallel samples, prefix hits | Refcount, copy on the first divergent write | Often only the partial last block is written, so copies are rare |
| Page cache keyed by file offset | Prefix cache keyed by a hash of the token prefix | Reuse across requests | Exact prefix match. One early token change invalidates later blocks |
| Swap device | CPU memory or a remote KV store | A slower tier | Optional. Often cheaper to recompute than to transfer |
| Major fault | Re-prefill of evicted blocks | An expensive miss | GPU FLOPs, not I/O |
| Thrashing | Preempt and recompute when too many sequences are admitted | Working sets exceed memory | The fix is scheduler admission, the same load-control lesson |
| OOM killer | Reject or abort when no block can be freed | Last resort | The engine picks victims by policy, for example latest arrival, not only by size |
The kernel that walks the block table, the iteration scheduler, and fork-style sharing of blocks are PagedAttention and continuous batching. The runtime map is LLM inference runtime. This table is the OS reading of those designs.
Why contiguous allocation fails
A naive server reserves max-context slots per request because it does not know the final length. Most requests are shorter, so most of the reservation is never written. If it reserved exact lengths instead, requests finishing in random order would leave holes too small for a new long request. Either way fewer requests fit. Decode is bandwidth-bound and reads the weights once per step, so throughput falls almost linearly with batch size. That bandwidth equation is Prefill vs decode.
ProblemAdmit a fixed seed of request lengths into 32768 token slots. Compare a max-length reservation, exact first-fit, and paged blocks.
ExpectedMax-length admits 8 requests and wastes most of the reservation. Exact fit still fails some admissions while free slots remain. Paged allocation with block 16 admits more than 8, and block 1 wastes nothing.
Edge cases
- Waste for block size 1 is zero on every admitted request.
- A failed exact-fit admission can happen with enough total free space.
- Test: max-length admits pool divided by max context
cont_admitted == 8 - Test: max-length wastes more than it uses
cont_wasted > cont_used - Test: exact fit fails despite free space
exact_fail > 0 - Test: paged block 16 admits more than the reservation
paged16_admitted > cont_admitted - Test: block size 1 has no tail waste
paged1_waste == 0
Press Run. Snippets must be self-contained — no network, files, or native modules.
Max-length reservation admits a handful of requests and wastes most of what it reserved. Exact-size contiguous allocation fails admissions even when the total free space would fit the request. Paged allocation admits several times more, with waste bounded by less than one block per sequence. Tiny blocks waste nothing and explode the table. Huge blocks waste the tail. Sixteen tokens is a common default.
Block size is the page-size tradeoff
| Block size | Internal waste | Table cost | Kernel efficiency | Prefix sharing |
|---|---|---|---|---|
| 1 to 4 tokens | Near zero | Very high, many gathers | Poor memory coalescing | Fine-grained, more hits |
| 16 tokens | Under one block per sequence | Moderate | Good on current GPUs | Good |
| 64 to 256 tokens | Noticeable on short requests | Low | Very good | Coarse. A partial block is not shareable |
The OS parallel is 4 KiB versus 2 MiB pages. Bigger units are cheaper to translate and move. Smaller units waste less and share better. The huge-page stalls and copy amplification are the scaling lesson. Here the analogous cost is a coarse prefix and a fat tail.
Prefix cache as a page cache
Sequence
- 1
Scheduler → Prefix hash index
1 hash each full block, chained with the parent
- 2
Prefix hash index → Scheduler
2a reuse the block and increment refcount
- 3
Scheduler → Block pool
3a allocate a free block
- 4
Block pool → Block pool
4a evict an LRU block with refcount 0
- 5
Block pool → Scheduler
5a preempt - swap or recompute
- 6
Scheduler → GPU prefill
3b compute KV only for missed blocks
- 7
GPU prefill → Prefix hash index
3c register the new hashes
- 8
Scheduler → Block pool
6 request ends - decrement refcounts, keep refcount 0 cached
Lesson map
From Pages to KV Cache — Block Tables, Fragmentation, and Prefix Cache
This lesson is the OS lens on LLM KV cache, not a second PagedAttention tutorial. The existing lesson on PagedAttention teaches the block table, the attention kernel, and continuous batching; read it for engine internals. Here we take the vocabulary of the previous lessons and apply it: contiguous per-request KV reservation is segmentation and fails the same way, with internal waste from worst-case sizing and external fragmentation from churn; fixed-size KV blocks with a per-sequence block table are paging; block size is the page-size tradeoff; prefix caching is a page cache keyed by token content with refcounts and LRU; preemption by swapping blocks to CPU or recomputing them is demand paging where the backing store can be computation. We quantify fragmentation, build a prefix block cache that evicts like the kernel does, and work through swap versus recompute and KV offload tiers. The goal is to answer why PagedAttention uses pages, in OS terms, and to know exactly where the analogy breaks.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB s["Scheduler"] h["Prefix hash index"] p["Block pool"] g["GPU prefill"] s -->|1 hash each full| h h -->|2a reuse the| s s -->|3a allocate a| p p -->|5a preempt -| s s -->|3b compute KV| g g -->|3c register the| h
- Refcount zero is not freed. It is cached, like a clean page on the inactive list.
- Chained hashes enforce an exact prefix. Block k's key includes the hash of blocks 0 through k minus 1. The same text after a different system prompt is a different block. A page cache key of file plus offset does not depend on other pages. This one does.
- Only full blocks are shared. Decode will append to the partial last block. Sharing it would copy on the next token.
- Eviction policy matters. Plain LRU lets a burst of unique prompts flush a shared system prompt. That is the scan problem from the page-cache lesson. Engines pin or prefer hot prefixes. A radix tree of token sequences is a different index over the same idea: SGLang and RadixAttention. Which runtime you pick is vLLM vs SGLang.
ProblemAdmit four prompts that share an eight-token system prompt into a 12-block pool. Release them. Flood the pool with unrelated prompts. Admit the shared prompt again.
ExpectedHits climb while the system prompt is reused. The flood evicts refcount-zero blocks. A later miss recomputes. Nothing here reads a disk.
Edge cases
- A partial tail is not inserted.
- Eviction skips any block with a nonzero refcount.
- Test: shared prompts hit
afterUsers.hits > 0 - Test: the first prompt still misses
afterUsers.misses > 0 - Test: the flood evicts cached blocks
afterFlood.evictions > 0 - Test: eviction never required a live refcount
afterFlood.evictions >= 1 && afterUsers.hits >= 2
Press Run. Snippets must be self-contained — no network, files, or native modules.
Requests that share the system prompt reuse its blocks. After a flood of unrelated prompts, plain LRU can evict that prefix, so the next request recomputes it. Production routing sends the same prefix to the replica that already holds it, the way a CDN sticks a URL to an edge that has the object: CDN cache hierarchy. Stampede protection, deduplicating identical in-flight prefills, is the cache-aside idea on Redis cache-aside. Invalidating a prefix when the system prompt or tool schema changes is the same family of problems as caching for agents.
Preemption: swap or recompute
When the pool is exhausted and nothing cached is evictable, the scheduler takes blocks from a running sequence.
| Option | What happens | Cost | Wins when |
|---|---|---|---|
| Swap to CPU memory | Copy KV over the host link, and copy it back later | Bytes divided by link bandwidth, both directions, plus host RAM | Long contexts where re-prefill is expensive, and the link is fast |
| Recompute | Free the blocks. Later, prefill the prompt plus the generated tokens | GPU FLOPs proportional to length, competing with other work | Short or medium sequences, and spare compute |
| Offload tier | Keep evicted prefix blocks in CPU, disk, or a remote store | Transfer on the hit | Many requests share long prefixes across time |
An 8B grouped-query model at about 128 KiB of KV per token and a 4,000-token sequence holds about 500 MiB of KV. At an effective 25 GB/s host link, swapping it out and back moves about 1 GiB in roughly 40 ms. Re-prefilling 4,000 tokens on a modern GPU is in the same tens of milliseconds, and it competes with every other request. Engines make the choice configurable. As with OS swap, the better answer is to admit fewer sequences so you rarely choose.
KV thrashing
Decisions
- 1
1 Scheduler admits many sequences
- next2 Sequences grow one block every 16 tokens
- 2
2 Sequences grow one block every 16 tokens
- next3 Free blocks left
- ?
3 Free blocks left
- 3a yes2 Sequences grow one block every 16 tokens
- 3b no4 Evict refcount-zero prefix blocks
- 4
4 Evict refcount-zero prefix blocks
- next5 Enough
- ?
5 Enough
- 5a yes2 Sequences grow one block every 16 tokens
- 5b no6 Preempt the newest sequence
- 6
6 Preempt the newest sequence
- next7 That sequence is re-admitted and re-prefilled
- 7
7 That sequence is re-admitted and re-prefilled
- next8 Prefill steals compute and blocks from decode
- 8
8 Prefill steals compute and blocks from decode
- next9 TTFT and inter-token latency spike
- 9
9 TTFT and inter-token latency spike
The fix is the OS load-control fix. Cap concurrent sequences or reserve headroom for growth. Size max context realistically. Watch KV usage and preemption counters as SLO signals. A pinned buffer in a database is a block with refcount above zero. A clock sweep of unpinned pages is LRU over refcount zero. A full scan is a burst of unique prompts. Those database mechanics stay on B-tree internals.
Interview Q&A
Why does PagedAttention use pages or blocks?
Answer
KV cache has the allocation problem virtual memory solved. Many variable, growing allocations finish in arbitrary order. Contiguous reservation wastes memory on the worst case and fragments. Fixed-size blocks through a per-sequence block table remove external fragmentation, bound internal waste to one block per sequence, and make sharing a refcount. More sequences fit, the batch grows, and memory-bound decode throughput rises. The kernel and the batcher are PagedAttention and continuous batching.
Where does the OS analogy break?
Answer
There is no hardware MMU or TLB. The attention kernel reads the block table directly. The pool is pre-reserved, not demand-allocated. There is no file behind a block, so a miss means recompute unless a slower tier kept a copy. Prefix keys must match the entire preceding sequence. Victims are chosen by a batch scheduler per iteration, not only by page-level recency.
How would you size the block?
Answer
Balance tail waste, especially on short requests, against metadata and kernel efficiency, and against prefix granularity, because only full blocks are shared. Start from the engine default, often 16, then measure KV utilization and throughput on your length distribution.
Swap or recompute on preemption?
Answer
Compare bytes over link bandwidth, both directions, with prefill time for that length under the current load. Long contexts and fast links favor swap. Short sequences and spare compute favor recompute. Better, avoid preemption with admission control and a watermark.
KV cache usage is near 100 percent and preemptions are rising. What do you do?
Answer
Treat it as thrashing. Reduce max concurrent sequences or max length. Add replicas or GPUs if tensor parallelism is how you split KV. Quantize KV. Improve prefix caching and prefix-aware routing so duplicate blocks disappear. Tune the GPU memory fraction. Watch time to first token and inter-token latency next to the preemption count. Do not start by rewriting the kernel.
Explain prefix caching to a backend engineer in one sentence.
Answer
It is a page cache for attention state. Full KV blocks are keyed by a hash of the tokens up to and including them, kept with refcounts while in use and on an LRU list when idle, so a new request with the same prefix maps existing blocks instead of recomputing them.
Why can two prompts with the same ending miss?
Answer
The hash is chained from the parent block. A timestamp or a user id at the front of the system prompt changes every later block. Put stable content first and variable content last. The partial last block is not shared even when the prefix matches.
How is this not a second PagedAttention lesson?
Answer
That lesson owns the block-table layout, the attention read, and continuous batching. This lesson owns fragmentation, the page-size tradeoff, the page-cache reading of a prefix, and swap versus recompute. If the question becomes the kernel, open PagedAttention or the runtime map.
Pitfalls
- Describing PagedAttention as virtual memory, finished, without the differences above.
- Expecting prefix hits when prompts differ early.
- Ignoring that prefix-cache capacity competes with live sequences for the same pool.
- Tuning max concurrency on an empty cache and then thrashing on real lengths.
In three sentences: why blocks exist, what a prefix hit requires, and the miss cost that is not a disk read. If you start describing the attention formula, you have left this page.