KV Cache Explained: How LLM Inference Caches Keys and Values

What to say (≈90 sec): “I’d frame it around arithmetic intensity — FLOPs per byte read. In a single-token decode step, each token’s matrix-vector multiply reuses each weight exactly once, so at batch size one the intensity is roughly one FLOP per byte — the roofline model says you’re memory-bound. Every step streams two things: the full weight matrix — a 70B model in fp16 is about 140GB crossing HBM on every token — and the KV cache, which grows linearly with context length and batch size. Batching raises intensity because one weight stream serves many tokens, but the KV read scales with the batch, so at long contexts even batched decoding is cache-bandwidth-bound. That’s why GQA and paged attention show up here: they shrink the KV bytes per token, which is exactly the bottleneck.”

Likely follow-up: “So why doesn’t batching fully fix it?” → Because weights are shared across the batch but each request’s KV cache is its own bytes. As the batch grows, the KV read — which scales with batch × context — overtakes the weight read, and the bottleneck just moves from the model stream to the cache stream.

The answer that sinks you: “Because decoding does so much compute.” Why it fails: decoding is tiny compute — one token’s matvec per step. The GPU mostly idles waiting on memory, which is why utilization sits near 10%.

What to say (≈90 sec): “I’d design it as four guardrails. First, the cache key must bind the prefix hash to the authorization context — the tenant ID and the permission set used to fetch any retrieved documents. Same bytes, different authorization, different key — that kills cross-tenant leakage at the key level. Second, scope: partition caches by tenant namespace, and for RAG-heavy prefixes expire entries aggressively or encrypt them with a tenant-scoped key, because a cached prefix can leak the documents behind it. Third, reuse accounting: measure hit rates on hashed keys only and never log the raw prefix text, so the metric itself can’t leak content. Fourth, treat cached prefixes as retained data under the tenant’s retention policy — expire them when the tenant’s data expires and invalidate on permission changes. The core principle: a cache is a copy of someone else’s data, and it must inherit every boundary the original had.”

Likely follow-up: “What breaks when a user’s permissions change mid-conversation?” → Their cached prefix may reference documents they can no longer see. Tie cache keys to a permission-set version and bump it on any revocation, so stale entries miss instead of serving unauthorized content.

The answer that sinks you: “Just share the cache across tenants for efficiency — hits only depend on the prompt text.” Why it fails: prompt caching is exact-prefix matching, so a shared cache lets tenant B observe a hit and learn tenant A’s prefix existed — that’s a cross-tenant information channel and a real privacy breach.

What to say (≈90 sec): “Cache bytes scale linearly with the number of KV heads. Standard multi-head attention keeps one key-value pair per query head, per token. Multi-query attention keeps one KV pair for all query heads — a factor-H shrink in cache size and in the bytes streamed per decode step — but squeezing every query head through a single KV bottleneck can cost quality on long-range reasoning. Grouped-query attention is the middle ground: G groups of query heads share one KV pair each, cutting cache by H/G — Llama 2 70B uses 8 KV heads for 64 query heads, an 8x shrink — with quality close to MHA. The knob is KV heads: fewer heads means proportionally less memory and bandwidth per token, traded against representational capacity in the keys and values. As a rule of thumb I’d quote: KV cache per token is 2 × layers × KV heads × head dim × dtype bytes.”

Likely follow-up: “When would you still ship MHA?” → For short contexts and small batches, where cache bytes are small next to the weights — the quality margin of MHA costs nothing practical there. MQA and GQA only pay off when KV bytes dominate, which is long contexts and large batches.

The answer that sinks you: “MQA is always better because it uses less memory.” Why it fails: it optimizes one axis and ignores quality — on short-context workloads the MQA quality hit is real while the savings are irrelevant, so the trade-off flips.

What to say (≈90 sec): “I’d start from the allocation problem. In naive serving you reserve a contiguous block for each request’s maximum possible context — prompt plus max tokens. Variable-length requests mean most of that reservation is empty, and when the gaps don’t line up you get external fragmentation: memory is free but no contiguous chunk fits the next request, so you OOM with capacity sitting idle. Paged attention slices the KV cache into fixed-size blocks — vLLM’s PagedAttention uses 16-token blocks — and a block table maps each request’s logical positions to physical blocks, so one request’s cache can be scattered non-contiguously. Two wins: first, memory is allocated block by block as tokens arrive, so waste drops to at most one partial block per request; second, blocks are shareable — parallel samples from one prompt share the prompt’s blocks by reference, so beam search or n-sample decoding costs one copy of the prefix instead of n.”

Likely follow-up: “What’s the cost of that indirection?” → Every attention lookup goes through the block table, and a partially filled last block wastes up to block-size-minus-one slots per request. It pays for itself the moment utilization is the bottleneck — which at fleet scale it always is.

The answer that sinks you: “It makes attention faster.” Why it fails: it doesn’t change the attention math at all — it’s a memory-utilization trick, and the throughput gain is indirect, through bigger batches and fewer OOMs.

What to say (≈90 sec): “I’d walk through it in five steps. First, estimate worst-case memory before admitting: KV bytes per token — 2 × layers × KV heads × head dim × dtype — times prompt length plus max new tokens, plus model and scratch overhead. Second, reserve in block units, not raw bytes — since the cache is paged, admit only if free blocks cover the worst case, otherwise queue. Third, cap each request’s share so one 100k-context request can’t lock the pool and starve fifty small ones — that’s the noisy-neighbor guard. Fourth, schedule by SLO: interactive traffic with tight time-to-first-token targets gets reserved headroom over batch and offline jobs. Fifth, make rejection a first-class path: return a clean 429 with a Retry-After estimate instead of admitting into an OOM, and log the dropped request’s estimate so capacity planning sees the real demand signal. And I’d close with validation: load tests with adversarial mixes — all-long-context bursts — plus a dashboard on free blocks and queue depth, because the controller is only as good as its estimates.”

Likely follow-up: “What if requests exceed their estimated max tokens?” → Cap with max tokens as a hard preemption point and never admit against 100% of free blocks — keep headroom. If a request exhausts its estimate mid-flight, preempt and recompute or re-queue rather than let one overrun crash the whole batch.

The answer that sinks you: “Admit everything and let the scheduler sort it out.” Why it fails: an OOM mid-decode kills every request sharing the GPU, not just the offender — admission control exists precisely because recovery isn’t free.

What to say (≈90 sec): “The constraint set is different on device: a fixed RAM budget shared with the OS, thermal throttling under sustained load, and private data that must never leave. So I’d layer four policies. First, bound the context with a rolling window and a hard cap — when it fills, evict the oldest tokens or, better, compress them into a rolling summary so long conversations degrade gracefully instead of forgetting abruptly. Second, shrink bytes per token: quantize the KV cache — int8 or int4 K and V is standard — and run a GQA model so there are fewer KV heads to store. Third, respect the device: watch memory pressure and temperature, and shed load — shorter max tokens, smaller batches — before the OS kills the process. Fourth, the privacy one: every cache entry is derived from user data, so it’s encrypted at rest on device, never uploaded, and wiped on logout. The metric I’d watch is p99 time-per-token under thermal throttle, because a policy that looks fine on a cool phone falls apart on a hot one.”

Likely follow-up: “Why not just spill the cache to flash?” → Flash is orders of magnitude slower than the bandwidth decode needs, the read amplification would drain the battery, and the privacy surface grows. If the cache doesn’t fit in RAM, the right answer is to shrink it, not page it.

The answer that sinks you: “Keep the full context and let the OS handle memory pressure.” Why it fails: the OS handles pressure by killing your process — there’s no graceful degradation, and the whole session state goes with it.