KV Cache & PagedAttention

1. Quick anchor

Attention at decode step t needs the keys and values of every prior token. Recomputing them is O(t) work per token and O(t²) for a sequence, so we cache K and V once and reuse them — that cache is the KV cache, and it is the single largest dynamic consumer of GPU HBM during serving. Its size is brutally simple and brutally large: 2 * layers * kv_heads * head_dim * seq_len * batch * dtype_bytes. Naively, you allocate one contiguous buffer per sequence sized to the maximum possible length, which wastes 40-60% of HBM to internal fragmentation, reservation, and padding — and HBM is exactly what limits your batch size, which is exactly what limits your throughput. PagedAttention (vLLM) fixes this by managing the cache like OS virtual memory: fixed-size blocks, a per-sequence block table, near-zero waste, and free copy-on-write prefix sharing. RadixAttention (SGLang) pushes the sharing idea further with a radix tree that automatically reuses any common prefix across requests.

2. Why interviewers probe this

• IC5 (senior IC): Can you derive the KV-cache formula cold, name every symbol, and explain why memory — not FLOPs — is the throughput ceiling in decode? Do you instinctively reach for batch size when asked "how do I serve more users on the same GPU"? Do you know GQA changes the kv_heads term, not the query-head count?
• IC5: Can you explain fragmentation concretely — internal vs external vs reservation waste — rather than hand-waving "memory gets fragmented"? Can you sketch a block table?
• IC6 (staff): Can you reason about the system: how paging interacts with continuous batching, preemption, and prefix caching; what the indirection costs in kernel complexity and a few percent of bandwidth; when RadixAttention's tree beats vLLM's block hashing and when its bookkeeping is overkill; and how KV-cache quantization and disaggregated serving shift the whole calculus. Staff candidates connect the cache to the business: tokens/dollar.

3. Concept build-up

3.1 Why we cache K and V (and not Q)

Self-attention for a query at position t computes scores against the keys of all positions 1..t, softmaxes them, and weights the corresponding values. The query q_t is needed only at step t and then thrown away — but every key k_i and value v_i for i ≤ t is needed again at step t+1, t+2, and so on. So the asymmetry is structural: Q is ephemeral, K and V are reused. Without a cache, generating token t re-projects K and V for all t prior tokens, making a full sequence O(seq²) in projection FLOPs and re-running the whole prompt every step. With the cache, prefill projects K,V once for the whole prompt (a big matrix-matrix multiply — compute-bound, ~90% GPU utilization), and each decode step appends exactly one token's K,V and does a matrix-vector attention read (memory-bound, 20-40% utilization). We covered that phase split in prefill vs decode; the cache is the object that connects the two phases.

The catch: decode now reads the entire cache from HBM for every token, with essentially zero arithmetic reuse per byte. Arithmetic intensity drops to ~60-80 FLOP/byte and the GPU stalls 10-50x longer on memory reads than on math. This is the memory-bandwidth wall, and it is why "shrink the cache" (GQA, quantization) and "stop wasting cache memory" (paging) are the highest-leverage levers in serving.

3.2 The formula — and the number that ends arguments

Two consequences staff candidates state without prompting. First, the cache scales linearly in sequence length and batch and is independent of the prompt/generation split — a 1k-prompt-7k-generation sequence costs the same as a 7k-prompt-1k-generation one. Second, the term that matters most for serving cost is H_kv, which is why GQA (Grouped-Query Attention) and MQA (Multi-Query Attention) are the cheapest quality-for-memory trade in the stack: they shrink the cache by the grouping ratio while barely touching the FLOP count or accuracy.

3.3 Where the memory actually goes: three kinds of waste

The PagedAttention paper's central empirical claim is that pre-paging systems used 20-40% of KV memory for actual token state — the rest was waste in three flavors:

1. Reservation waste. You don't know the output length in advance, so contiguous allocators reserve the max sequence length up front. A request that generates 200 tokens but reserved 4096 holds ~95% empty-but-unavailable memory for its whole lifetime.
2. Internal fragmentation. Even sized correctly, the last chunk is partially filled — the slack between actual length and the allocation granularity.
3. External fragmentation. Sequences finish at different times, leaving variable-size holes between live allocations. A new 3000-token request can't fit in the sum of a 1000 + 1200 + 900 gap because no single hole is big enough — classic malloc-style fragmentation.

The result, with one contiguous buffer per sequence: 50-60% effective utilization, sometimes worse under skewed length distributions. Half your most expensive resource, idle. And because batch size is gated by free HBM, halving usable cache memory roughly halves throughput. This is the problem PagedAttention was built to kill.

3.4 PagedAttention: the cache as virtual memory

The insight (Kwon et al., 2023; the foundation of vLLM) is a direct lift from operating systems. Don't allocate the cache contiguously. Instead:

• Carve HBM into a pool of fixed-size blocks, each holding a small fixed number of tokens (e.g. 16) worth of K,V for all layers.
• Give each sequence a block table: a list mapping logical token positions to physical block IDs. Logically contiguous tokens can live in physically scattered blocks — exactly like OS pages mapped by a page table.
• Allocate a new block only when the current tail block fills. So a sequence holds at most one partially-filled block of slack — internal fragmentation is capped at block_size - 1 tokens, and external fragmentation vanishes because all blocks are the same size and interchangeable.

Memory utilization jumps from ~50-60% to near 100%, which translates into 2-4x (reported up to 4-24x on favorable workloads) larger batches on the same HBM budget, and throughput scales with batch in the memory-bound decode regime. The cost is real but bounded: the attention kernel must be rewritten to gather K,V from non-contiguous block addresses via the block table (a scattered/gather read), which costs a few percent of bandwidth versus an idealized contiguous read — a trade everyone takes happily. PagedAttention is now the industry default, shipped in vLLM, TGI, TensorRT-LLM, and LMDeploy.

The second gift falls out for free: copy-on-write prefix sharing. If two sequences share a prefix (same system prompt, same few-shot examples), their block tables can point at the same physical blocks, refcounted. No duplication until one of them writes past the shared region, at which point that block is copied. This is the seed of prompt caching.

3.5 RadixAttention: automatic, semantic prefix sharing (SGLang)

PagedAttention shares prefixes when you fork a sequence. RadixAttention (SGLang, 2024) makes prefix reuse automatic and content-addressed across all requests. It stores cached KV in a radix tree where each edge can represent a sequence of tokens (not one token per edge), and on every new request it walks the tree to find the longest cached prefix match and reuses those blocks — no explicit fork, no user signal. Eviction is LRU over leaf nodes under memory pressure.

On high-prefix-reuse workloads — multi-turn chat where every turn re-sends the conversation, agentic loops re-sending a long system prompt and tool schema, batched structured generation — RadixAttention reports up to 5x throughput over vLLM, and it claims zero overhead when there are no cache hits (unlike block-granular approaches that can pay for bookkeeping they don't use). SGLang's tree-based caching powers 400,000+ GPUs in production (xAI, NVIDIA, LinkedIn, AMD). When prefixes are mostly unique (e.g. high-entropy user prompts with no shared scaffolding), the tree's advantage shrinks toward vLLM's, and the simpler block hashing is fine. This is the kind of "it depends on the workload" answer IC6 interviews reward — see continuous batching for how these caches feed the scheduler.

3.6 Continuous batching: why the cache layout enables the scheduler

Blocks aren't just about saving memory — they're what make continuous (iteration-level) batching practical. Static batching waits for the slowest request in a batch to finish before admitting new ones; the cache for finished sequences sits reserved and idle. Continuous batching schedules at token granularity: after every decode iteration, finished sequences free their blocks back to the pool, and waiting requests are admitted into the freed blocks immediately — even mixing a new request's prefill chunk with in-flight decodes in the same iteration ("decode-maximal batching"). That instant block reuse is only cheap because blocks are uniform and the free list is O(1). The combination of paged blocks + continuous batching is the source of vLLM's headline 23x throughput over naive static batching. When the pool does run dry, the scheduler preempts a sequence — either recompute its cache later (cheap to evict, costs prefill to restore) or swap its blocks to CPU (costs PCIe bandwidth). Paging makes both preemption strategies clean.

4. Minimal implementation

The file examples/inference/kv_cache.py does two things every interview touches: the size calculator (section 3.2's formula) and a correct, runnable PagedAttention-style allocator — fixed blocks, a per-sequence block table, a free list, and refcounted copy-on-write prefix sharing. It deliberately implements the bookkeeping, not the CUDA kernel, because the allocator is where the conceptual content lives.

import numpy as np
from dataclasses import dataclass, field
 
def kv_cache_bytes(*, num_layers, num_kv_heads, head_dim, seq_len,
                   batch=1, dtype_bytes=2):
    # 2 = K and V; num_kv_heads is post-GQA, NOT query heads.
    return 2 * num_layers * num_kv_heads * head_dim * seq_len * batch * dtype_bytes
 
@dataclass
class PagedKVCache:
    num_blocks: int; block_size: int
    num_layers: int; num_kv_heads: int; head_dim: int
    def __post_init__(self):
        # [2, blocks, layers, block_size, kv_heads, head_dim] — one big pool.
        self.pool = np.zeros((2, self.num_blocks, self.num_layers,
                              self.block_size, self.num_kv_heads,
                              self.head_dim), dtype=np.float16)
        self.free = list(range(self.num_blocks))
        self.refcount = {}
    def alloc_block(self):
        if not self.free:
            raise MemoryError("KV pool exhausted — preempt/evict a sequence")
        b = self.free.pop(); self.refcount[b] = 1; return b
    def free_block(self, b):
        self.refcount[b] -= 1
        if self.refcount[b] == 0:
            del self.refcount[b]; self.free.append(b)
    def share_block(self, b):           # copy-on-write prefix sharing
        self.refcount[b] += 1; return b
    def utilization(self):
        return 1.0 - len(self.free) / self.num_blocks

The scheduler in the file appends one slot per token and allocates a fresh block only when the tail block fills (if seq.length % block_size == 0) — that single condition is what caps internal fragmentation at one block per sequence. fork() shares whole prefix blocks by bumping refcounts (no copy), modeling prompt caching. Running it prints:

Llama-3-70B, 8k ctx, 1 seq :   2.50 GiB KV
... x 64 concurrent users   : 160.00 GiB KV
... if it had 64 KV heads   :  20.00 GiB KV (8x worse)
after 2 forks (shared)util=5% (no copy — refcounted blocks)

The 160 GiB for 64 users line is the punchline you want on the whiteboard: it exceeds a single H100's entire HBM, so the cache, not the weights, is what forces multi-GPU or aggressive cache compression. The 20 GiB line quantifies GQA's payoff, and the unchanged utilization after forking shows prefix sharing costs zero extra blocks until divergence. Run it with python examples/inference/kv_cache.py (numpy only — no GPU needed).

5. Production tradeoffs

Cost. In the memory-bound decode regime, throughput scales roughly with batch size, and batch size is gated by free HBM after weights. So every GiB of cache you don't waste, and every GiB you compress, converts almost linearly into tokens/second/dollar. That is the entire economic argument for paging.

Latency. Paging adds a small, constant per-token bandwidth overhead (the scattered KV read) — invisible next to the throughput it unlocks. The bigger latency lever is the cache size: long contexts make every decode step read more bytes, so TPOT (time per output token) grows with sequence length even though FLOPs barely do. Prefix caching cuts TTFT (time to first token) dramatically for repeated prompts because prefill over the cached prefix is skipped.

Quality. Paging and continuous batching are mathematically lossless — they change where bytes live, not what they are. The lossy lever is KV-cache quantization: storing K,V in FP8 (Hopper/Blackwell) or INT8 (portable since Pascal) halves cache memory and halves decode memory traffic, with small accuracy cost on most tasks. Recent work (e.g. TurboQuant, ICLR 2026) pushes to K=4-bit / V=2-bit with near-zero reported loss. Quantize the cache before you quantize weights if decode throughput is your bottleneck.

What changes at scale. Past one GPU, the cache forces architectural choices: tensor parallelism shards kv_heads across GPUs (each holds H_kv / TP heads' cache); disaggregated prefill/decode serving puts decode on high-HBM, high-bandwidth parts (H200/B200) precisely because decode is cache-read-bound, while prefill runs on compute-optimized H100s. The cache is also the thing that gets migrated between those clusters, adding <50ms of network transfer. See inference parallelism for the full picture.

6. How it's asked

7. Pitfalls & flashcards

• Counting query heads instead of KV heads. GQA/MQA shrink the cache via H_kv; using the query-head count overstates memory by the grouping ratio (8x for Llama-3-70B). The cache term is the reason GQA exists.
• Thinking the model weights cap concurrency. Weights are static; the cache is what grows per user and per token and saturates HBM first in any non-trivial serving setup.
• Assuming paging is free. The scattered-block read costs a few percent of bandwidth and demands a custom kernel — worth it, but not zero, and a real source of "vLLM is slower than my contiguous baseline at batch=1" surprises.
• Believing prefix caching always helps. With unique, high-entropy prompts there are no shared prefixes to reuse; RadixAttention's tree then adds maintenance for little gain.
• Ignoring eviction. Prefix-cache and paged pools are finite; without LRU eviction or CPU/disk tiering, a busy multi-tenant system thrashes and one tenant evicts another's hot blocks.
• Forgetting cache quantization is the cheap throughput win. FP8/INT8 KV halves both memory and decode memory traffic — often quantize the cache before the weights.

Flashcard. KV cache = 2 · L · H_kv · d · S · B · bytes. Decode is memory-bound, so this number — not the weights — caps batch size, hence throughput; PagedAttention recovers the ~40% lost to fragmentation, RadixAttention deduplicates shared prefixes, and FP8 KV halves what's left.

8. Further reading

• PagedAttention / vLLM paper (Kwon et al., 2023) — the fragmentation analysis and block-table design.
• SGLang & RadixAttention blog (LMSYS, 2024) — the radix-tree prefix cache and its throughput claims.
• vLLM documentation — production knobs: paging, prefix caching, chunked prefill.
• SGLang documentation — structured generation and RadixAttention internals.
• SARATHI: chunked prefills (2023) — how prefill chunking lets the cache feed continuous batching.
• LLM inference serving survey (2024) — taxonomy of cache, batching, and parallelism techniques.

Next: Continuous batching & scheduling — how the block pool you just built becomes the iteration-level scheduler that delivers 23x throughput.