Inference Systems Infrastructure Notes (9): The KV Cache Landscape — Why It Decides Your Throughput, Latency and Concurrency

0. The One-Line Thread

KV Cache is space traded for time: it pays once to compute the repeated work in autoregressive generation and caches the result, at the cost of GPU memory growing linearly with batch times sequence length, which eventually throttles your concurrency. This post covers three things — why it can be cached at all, how big it actually gets, and which directions the industry is cutting it from.

1. Meet the Enemy: Without KV Cache, What Are We Recomputing?

LLM inference is autoregressive: generating token n requires information from all previous n−1 tokens. Naively, every new token re-runs the whole history through the forward pass:

Module	Where the redundancy lives
Embedding	Historical token embeddings regenerated every step
K / V generation	K and V for historical tokens recomputed every step
QKᵀ	The attention score matrix recomputed, growing quadratically with sequence length
Softmax × V	The weighted sum recomputed

Total cost for N tokens lands around O(N²) — the longer the sequence, the worse it gets, and it gets ugly fast.

Figure 1: prefill builds the KV Cache for the whole prompt in one shot; decode adds one token per step, and attention reads the entire history.

2. Why Caching Is Legal: Module by Module

Caching rests on two properties: causal masking and position independence.

Attention: causal masking freezes the past

At inference, the query at position i only attends to 1..i — it never sees the future. Under unidirectional attention, the k₂ computed at i=3 is identical to the k₂ computed at i=4.
Put simply, K/V for historical tokens are already final. There is no reason to recompute them. Each step only needs K/V for the newest token, appended to the cache.

FFN / LayerNorm / Linear: positions do not interact

FFN: features at different positions do not mix, so output i depends only on input i (Y₁ depends only on X₁).
LayerNorm: statistics run along d_model, so the output depends only on the current row of hidden states.
Linear (lm_head): by the nature of matrix multiplication, the last row of logits depends only on the last row of hidden states.
Softmax: keeping prior results lets you merge with the new one.

The one-line mathematical backing

Matrix multiplication is block-separable: split A into [:s] and [s:], multiply each by B, concatenate — identical to multiplying A by B whole. Attention and FFN are both matrix multiplications, so caching [:s] and computing only the new [s:] is exactly equivalent. This is a lossless optimization.

3. Prefill vs Decode: Two Stages, Opposite Personalities

Stage	What it does	Compute profile	Key metric
prefill	Processes the whole prompt, builds the KV Cache, emits the first token	Compute-bound (large GEMMs, high parallelism)	TTFT
decode	Emits one token at a time, reading the full history each step	Memory-bandwidth-bound (little compute, lots of KV traffic)	TPOT

This split — one wants FLOPs, the other wants bandwidth — is the entire reason PD disaggregation exists (see sys8).

4. How Big Does It Actually Get

The formula for standard MHA/GQA:

KV Cache = 2 (K and V) x layers x batch x seq_len x kv_dim x dtype_bytes

where kv_dim = num_kv_heads x head_size.

Measured case (Qwen3-32B):

64 layers, GQA with effective KV dimension 1024, BF16
At batch=4, seq=32768: 2 x 64 x 4 x 32768 x 1024 x 2B = 32 GiB
Raise batch to 8 → 64 GiB, already comparable to the model weights themselves (roughly 64 GB in BF16)

Takeaway: KV Cache grows linearly with batch and sequence length. Under high concurrency and long contexts, it — not the weights — is what caps your serving concurrency.

5. How It Eats Performance: Three Metrics, Three Memory Regions

Metric	Meaning	Driven by
TTFT	Time to first token	Mostly prefill cost; prefix cache hits cut it sharply
TPOT	Time per output token	Per-step decode cost; rises as KV grows (more traffic)
Throughput	Output tokens per second (the cost metric)	Larger batches help, until memory runs out

Memory view:

peak memory = model weights (fixed) + KV Cache (grows with batch x seq) + activations
total latency = TTFT + TPOT x number of generated tokens

So shrinking KV Cache pays twice: more concurrency on the same card (memory saved) and faster requests (bandwidth saved).

6. The Optimization Landscape: Three Layers

The survey A Survey on Large Language Model Acceleration based on KV Cache Management organizes the field into three layers.

6.1 Token-level (no model change, no parallelism change)

Selecting, organizing, and compressing at token granularity:

Direction	Approach	Examples
Selection	Keep only the most important tokens	H2O (heavy hitters), Keyformer, SnapKV, Quest
Budget allocation	Distribute cache budget across layers / heads	PyramidKV, PyramidInfer, AdaKV, DuoAttention
Merging	Merge similar or overlapping KV pairs	Intra / inter-layer merging, Prompt Cache
Quantization	Lower storage precision (FP16 to INT8 / INT4 / FP8)	KV cache quantization, see op2
Low-rank decomposition	Compress KV matrices into lower-dimensional form	LoRA-style compression, one of the ideas behind MLA

6.2 Model-level (architectural changes)

Attention grouping and sharing: MQA (one shared KV head), GQA (grouped sharing)
Architecture redesign: MLA (low-rank latent compression, see op1), YOCO, CLA, MLKV, NSA
Non-Transformer architectures: linear attention, RWKV, Mamba — no KV Cache to speak of

6.3 System-level (scheduling and memory management)

Memory management: PagedAttention (paging), virtual-memory adaptation, prefix sharing (RadixAttention)
Scheduling: prefix-aware scheduling to raise hit rate, preemptive context switching
Hardware-aware design: GPU / CPU / SSD tiered offloading (HiCache, AttentionStore, LMCache)

7. Five Knobs: Turning “Shrink the KV Cache” Into Quantifiable Actions

Going back to the formula, KV Cache size is a product of five factors, and each factor is an independent entry point:

Knob	How to turn it	Cost
Sequence length	Sparsity (static window / dynamic eviction), prefix reuse	May drop critical tokens; long-range tasks degrade
Head count	MQA / GQA (fewer KV heads)	Slight expressiveness loss, now a mainstream default
key_bits	Quantize to INT8 / INT4 / FP8	Accuracy loss, needs calibration (see op2)
Head dimension	MLA compresses KV into a low-rank latent; Double Sparsity exploits channel sparsity	Large structural change
Layers	Cache only some layers (YOCO / CLA / MLKV / LayerSkip)	Needs training support or accepts approximation

How to read this: the knobs are not exclusive. Production stacks stack them — for example, “GQA (heads) + FP8 KV (bits) + prefix reuse (length) + PagedAttention (system)” is the most common combination today.

8. Links to the Rest of the Series

This post is fundamentals and taxonomy: what KV Cache is, why it works, and how it can be cut.
sys5 covers the evolution thread of compression directions (MHA to MSA to HCA) — how the routes changed over time.
sys6 (HiSparse), sys7 (DCP), and sys1 (HiCache) are three concrete system-level deployments.
op1 (MLA) and op2 (quantization) map to the model-level and quantization knobs.
sys10, the next post, moves from principles to engineering implementation: SGLang’s two-level memory pool, vLLM’s block management, and Baidu’s AttentionStore measurements on Kunlunxin hardware.