AdversariaLLM
All About LLMs, from AI to Z· Lesson 70 of 80

Infrastructure, Hardware & Production Deployment · 7 min

KV-Cache Management and PagedAttention

The KV cache, not raw compute, is the real constraint on how many users you can serve at once. Paging it like operating-system virtual memory is what made high-throughput LLM serving practical.

A single 13-billion-parameter model in fp16 weighs about 26 GB. Load it onto an 80 GB A100 and you have roughly 54 GB left. It's tempting to treat that leftover as spare capacity for serving lots of users. It isn't. Almost all of it gets eaten by one thing: the KV cache. Understanding how that cache is stored, reused, and reclaimed is the difference between serving a handful of concurrent requests and serving hundreds.

Why the cache exists, and why it's so hungry

When a transformer generates text, every new token attends to every previous token. Recomputing the keys and values for the whole sequence on each step would be quadratic and absurdly slow, so you cache them. For each token, at each layer, you store one key vector and one value vector per attention head. That's the KV cache, and it grows linearly with sequence length.

The size is easy to compute and worth memorizing:

kv_bytes = 2 (K and V)
         * num_layers
         * num_kv_heads * head_dim   (= model hidden size, roughly)
         * seq_len
         * dtype_bytes
         * batch_size

For a 13B model (40 layers, hidden size 5120) in fp16, one token of context costs about 2 * 40 * 5120 * 2 = 819 KB. A single 2,000-token conversation is ~1.6 GB. Sixteen of them and you've burned 26 GB — as much as the weights. This is why long context is expensive and why concurrency is capped by memory, not compute.

One more thing the formula tells you: decode is memory-bound. Each new token requires reading the whole cache back out of HBM to compute attention, so once weights and cache are resident, generation speed is gated by memory bandwidth, not arithmetic. That flips the usual intuition. You can't buy your way out of a KV problem with more FLOPs, only with a smaller or better-managed cache. The GPU is rarely the bottleneck during generation; the cache is.

The waste nobody talks about: fragmentation

Here's the problem that made pre-2023 serving so inefficient. A request doesn't know in advance how long its output will be. The naive fix is to reserve a contiguous slab of memory for each request, sized to the maximum possible length — say 2,048 tokens — even if the reply turns out to be 30 tokens.

The vLLM authors measured this and found that in existing systems only 20–40% of KV cache memory held actual token state. The rest was lost three ways. There's internal fragmentation: you reserved 2,048 slots and used 30. There's reservation waste: slots held for future tokens that don't exist yet. And there's external fragmentation: because every request grabs a different-sized contiguous block, the allocator leaves unusable gaps between them, the same way a disk fragments.

If 60–80% of your most precious resource is dead space, you're serving a fraction of the users your hardware could handle. That's not a tuning problem. It's the memory layout itself.

PagedAttention: treat the cache like virtual memory

The insight in Kwon et al.'s 2023 PagedAttention paper is borrowed straight from operating systems. An OS doesn't demand that a process's memory be one contiguous run of physical RAM. It splits memory into fixed-size pages and keeps a page table mapping the process's contiguous logical view onto scattered physical frames. Fragmentation nearly vanishes because any free page fits any need.

PagedAttention does the same thing to the KV cache. The cache for a sequence is split into fixed-size blocks, each holding the keys and values for a fixed number of tokens (16 is a common block size). The blocks for one sequence do not need to be adjacent in GPU memory. A per-sequence block table maps logical block numbers to physical block locations, and the attention kernel is rewritten to gather K and V through that indirection.

Logical blocks (sequence)      Block table        Physical KV blocks (GPU)
[ tok 0..15  ] -> logical 0 -> phys 7      ...   [phys 3][phys 7][phys 9]...
[ tok 16..31 ] -> logical 1 -> phys 3
[ tok 32..40 ] -> logical 2 -> phys 9  (partial, 9/16 used)

The only waste left is inside the last, partially filled block of each sequence — at most 15 tokens. Internal fragmentation drops from "up to 2,000 tokens per request" to "under one block." External fragmentation disappears entirely because all blocks are the same size and interchangeable. In the paper's evaluation this pushed KV memory utilization above 96% and raised serving throughput by 2–4x over the best prior systems at the same latency.

What paging unlocks downstream

Fixing fragmentation isn't the whole prize. Once the cache is paged, a set of serving techniques that were awkward before become natural.

Continuous batching. Static batching makes fast requests wait for the slowest one in the batch to finish before any new request can start. Orca (Yu et al., OSDI 2022) introduced iteration-level scheduling: the batch is re-formed every decoding step, so a finished sequence is evicted and a waiting one slotted in immediately. Paging is what makes this cheap — admitting a new sequence just means handing it some free blocks, with no contiguous slab to find.

Prefix sharing. Suppose 50 requests all begin with the same 800-token system prompt. Their KV state for that prefix is identical. Because blocks are addressable and shareable, PagedAttention lets those requests point their block tables at the same physical blocks for the shared prefix, computing it once and storing it once. This is the basis of prefix caching (vLLM's automatic prefix caching, SGLang's RadixAttention). Concretely, 50 requests times 800 tokens is 40,000 tokens of prefill and cache that collapse to a single stored copy. For a chatbot with a fat system prompt, or few-shot prompts reused across a batch, the savings in both memory and prefill compute are large. Copy-on-write handles the moment sequences diverge: when one needs to modify a shared block, it gets its own copy, exactly like fork() in an OS.

Preemption and eviction. When memory fills, the scheduler can pause a running request and reclaim its blocks for a higher-priority one. Two strategies exist: swap the evicted blocks out to CPU RAM and back, or recompute them later from the tokens (often cheaper than it sounds, since prefill is compute-bound and parallel). Either way, paging gives the scheduler blocks as the unit of accounting, so it can make these decisions per-block instead of per-request.

Planning capacity when context gets long

Put this to work. To size a deployment, budget memory explicitly:

kv_budget   = gpu_mem - weights - activations_overhead
tokens_max  = kv_budget / kv_bytes_per_token
concurrency = tokens_max / avg_tokens_per_request

On an 80 GB card with that 13B model: ~54 GB for KV at ~819 KB/token gives room for roughly 66,000 tokens of live cache. If your average session is 2,000 tokens, that's about 33 concurrent sequences — before prefix sharing. Push average context to 8,000 tokens and concurrency falls to ~8. This is the capacity-planning reality of long context: doubling the context window doesn't just slow each request, it halves how many users you can hold at once.

Levers to pull when the number is too low: use grouped-query or multi-query attention models (fewer KV heads means a smaller num_kv_heads * head_dim term — a 4x GQA ratio cuts KV memory roughly 4x), quantize the KV cache to fp8 or int8 to halve dtype_bytes, lean on prefix caching when prompts share structure, and cap max_model_len to what you actually serve rather than the model's theoretical maximum. Each of these directly changes a term in the equations above, which is why the math is worth keeping in your head.

The through-line: on modern serving stacks the KV cache, not FLOPs, sets your concurrency ceiling, and PagedAttention is what turned that ceiling from a third of your memory into nearly all of it. Once you see the cache as paged memory, continuous batching, prefix sharing, and preemption stop looking like separate features and start looking like what they are: the same virtual-memory trick, applied to the one resource that was silently capping your throughput.

Sources