KV Cache: The Engine of 1M-Token LLM Inference

What Is a KV Cache — and Why Does It Matter?

The Problem: Quadratic Attention Cost

In a standard transformer, every token attends to every previous token. Without caching, generating token N requires recomputing attention over all N-1 prior tokens — that's O(n²) work per step. For a 1M-token conversation, the compute becomes astronomical.

# Without KV Cache: quadratic horror
for step in range(num_tokens):
    K, V = compute_kv(all_tokens[:step])    # Recompute EVERYTHING
    attention = softmax(Q @ K^T / sqrt(d)) @ V # O(step²)
    next_token = feed_forward(attention)

# With KV Cache: linear amortized
K_cache, V_cache = [], []
for step in range(num_tokens):
    k, v = compute_kv(token[step])           # Only new token
    K_cache.append(k); V_cache.append(v)      # Store for reuse
    attention = softmax(Q @ K_cache^T / sqrt(d)) @ V_cache
    next_token = feed_forward(attention)
      

Step 0 of 8

Watch how the KV cache grows as each token is processed — enabling fast, O(n) inference

O(n²) → O(n)

Compute complexity reduction

~655 GB

Raw KV cache @ 1M tokens (FP16, 40 layers)

60–80%

Memory wasted without PagedAttention

2–4×

Throughput gain with PagedAttention

The Economics of Cache Hits: Why ~10× Cheaper

The single most important number in LLM inference economics — and why providers desperately want you to structure your prompts for cacheability.

Every Request Has Two Radically Different Phases

Prefill is compute-bound (GPU math). Decode is memory-bandwidth-bound (GPU HBM reads). Cache hits eliminate the expensive one.

Interactive: See Where the Money Goes

Adjust the prompt composition below. The real-time chart shows cache hit vs cache miss token costs.

📋 Cached Prefix 8,000 tokens

✏️ New Prompt 2,000 tokens

📤 Output Tokens 500 tokens

🔧 Model Size

87%+

vLLM prefix cache hit rate in production RAG workloads

O(n²)

Prefill attention complexity — the part cache hits eliminate

~94%

Attention FLOPs avoided on an 8K prefix cache hit

60-90%

Typical prompt tokens that are cacheable (system prompts, tools, examples)

Why Providers Offer This Discount

🧮

Fewer GPU FLOPs

Every cache hit skips the quadratic prefill attention. Same GPU serves more requests per second.

⚡

Lower Latency

Prefill is the slowest part. Skipping it makes responses feel instant — better user experience.

📈

Higher Throughput

More requests per GPU = better unit economics. The 10× discount is a nudge, not charity.

Step-by-Step: How KV Cache Works

Step 1: Token Embedding

The input text "The cat sat on the" is tokenized into individual tokens. Each token is converted into a dense vector (embedding) of dimension d_model (e.g., 4096 for DeepSeek V4, 7168 for GLM 5.2). Positional encodings (RoPE) are added so the model knows token order.

Step 2: Q, K, V Projection

Each token embedding is projected through three learned weight matrices to produce Query (Q), Key (K), and Value (V) vectors. Q asks "what am I looking for?", K encodes "what information do I contain?", and V holds the actual content to be retrieved.

Step 3: Cache the K and V Tensors

Here's the key insight: K and V for past tokens never change. Instead of recomputing them, we store them in the KV cache — a large tensor in GPU memory (HBM). Each new token only computes its own K and V, then appends to the cache.

Step 4: Attention with Cached Keys & Values

The new token's Q attends to ALL cached K entries. Attention scores are computed: softmax(Q·K^T / √d). These scores weight the cached V entries to produce the attention output. Only O(n) work instead of O(n²).

Step 5: Feed-Forward → Output → Append → Repeat

The attention output passes through a feed-forward network (MLP) to produce the next token prediction. The new token's K and V are appended to the cache. The process repeats — each new token costs O(n) instead of O(n²), making autoregressive generation practical.

How Frontier Models Tame the 1M-Context Beast

Three radically different approaches to the same problem: fitting a million tokens of KV cache into GPU memory without losing retrieval quality.

DeepSeek V4 Pro — Hybrid Compressed Attention

Key Innovation: Compression along the sequence-length dimension, not just the head dimension

9.62 GiB

KV Cache @ 1M tokens (bf16)

8.7×

Smaller than V3.2 equivalent

128×

Max compression (HCA)

4×

CSA compression ratio

Three-Branch Architecture

Input Tokens
1M context

↙ ↓ ↘

Sliding Window
128 tokens, uncompressed

CSA
4× compression, sparse top-k

HCA
128× compression, dense

↓ ↓ ↓

Concatenate & Attend
Mixed precision: BF16 RoPE + FP8 cache + FP4 indexer

Key Mechanisms

CSA (Compressed Sparse Attention): Every 4 tokens become 1 compressed entry via learned compression pools. Lightning Indexer scores blocks and selects top-k for sparse attention — efficient for mid-to-long range retrieval.
HCA (Heavily Compressed Attention): 128× compression, dense attention over the ultra-short compressed sequence — acts as a "global table of contents."
Shared KV + Inverse RoPE: Keys and values share the same vector (2× memory reduction), with inverse RoPE applied to attention output to restore translation invariance.
Hybrid Layer Stack: First 2 layers use HCA, subsequent layers alternate CSA/HCA, final block uses sliding-window MTP.
FP4 Lightning Indexer: The CSA indexer uses 4-bit precision — ultra-lightweight scoring for block selection.

GLM 5.2 — Index Share Sparse Attention

Key Innovation: Share sparse position indices across head groups + Multi-Token Prediction

~20×

KV cache reduction at 1M tokens

2.9×

Compute reduction vs independent sparse

k=4

Multi-token prediction depth

8:1

GQA head sharing ratio

Three-Pronged KV Cache Solution

GQA (8:1)
8 query heads share 1 KV head

Sparse Eviction
Drop non-indexed positions

INT8 Quantization
Per-head scale factors

~20× KV Cache Reduction
Deployable on commodity hardware

Key Mechanisms

Index Share Sparse Attention: 32 attention heads grouped into 4 clusters of 8 — each cluster shares one sparse index set. Reduces index computation overhead by factor of g (group size).
Triple Index Strategy: Each group maintains local indices (sliding window of recent tokens), global indices (content-adaptive routing based on attention scores), and fixed landmark indices (periodic structural anchors).
Multi-Token Prediction (MTP, k=4): Predicts 4 future tokens simultaneously from a single hidden state. At inference, enables speculative decoding with 1.5–2.5× throughput gains.
Adaptive Full Attention: Below ~32K tokens, switches to standard full attention — sparse overhead isn't worth it at shorter contexts.
DP-Aware Routing: Dynamic programming routing maximizes KV cache reuse during long-context inference in MoE layers.

MiniMax M3 — MiniMax Sparse Attention (MSA)

Key Innovation: Linear-scaling sparse attention with "KV outer gather Q" operator optimization

1/20×

Per-token compute vs prev gen

>9×

Faster prefilling

>15×

Faster decoding

>4×

Faster than Flash-Sparse-Attn

MSA Architecture

Full KV Cache
All 1M token KVs

↓ Block Partitioning

Block 0

Block 1

Block 2

...

Block N

↓ KV Outer Gather Q (contiguous memory)

Sparse Attention
Only top-k blocks processed
>4× faster than Flash-Sparse-Attn / flash-moba

Key Mechanisms

MSA (MiniMax Sparse Attention): Partitions KV into blocks more precisely than DSA/MoBA, achieving higher effective context coverage with linear scaling. Matches full attention on nearly all capabilities.
KV Outer Gather Q: Operator-level optimization where KV blocks form the outer loop with contiguous memory access patterns — >4× faster than Flash-Sparse-Attention and flash-moba.
Native Multimodality from Step 0: Trained with interleaved text + image + video data from the start — KV cache handles mixed modalities natively.
Long-Horizon Agentic Optimization: MSA's long-context allocation specifically optimized for dense, structured histories of repeated tool calls — 1,959 tool calls over 24 hours in CUDA kernel optimization tasks.
No Multi-Token Prediction: Unlike DeepSeek V4 and GLM 5.2, M3 focuses purely on attention sparsity rather than speculative decoding for throughput gains.

Head-to-Head: KV Cache Strategy Comparison

Dimension	DeepSeek V4 Pro	GLM 5.2	MiniMax M3
Core Mechanism	Hybrid CSA + HCA + Sliding Window	Index Share Sparse + GQA + MTP	MiniMax Sparse Attention (MSA)
Compression Axis	Sequence-length dimension (token aggregation)	Head dimension (GQA) + sequence sparsity	Sequence sparsity (block partitioning)
Max Compression	128× (HCA)	~20× (combined)	N/A (sparse, not compressed)
KV Cache @ 1M (bf16)	9.62 GiB	~33 GiB (est.)	~42 GiB (est.)
vs Traditional GQA	~2% (50× smaller)	~5% (20× smaller)	~6% (17× smaller)
Quantization	FP8 cache + FP4 indexer + BF16 RoPE dims	INT8 with per-head scale factors	FP8 (standard)
Sparsity Pattern	Top-k sparse (CSA) + Dense (HCA)	Triple index: local + global + landmark	Block-wise top-k with contiguous gather
Short Context Fallback	Sliding window always active	Full attention < 32K tokens	MSA applied uniformly
Speculative Decoding	MTP (Multi-Token Prediction)	MTP (k=4) with 1.5–2.5× throughput	None
Multimodal KV Cache	Text-only	Text-only	Native image + video from Step 0
Memory Management	vLLM unified page pools (3 bucket sizes)	PagedAttention + DP-aware routing	PagedAttention + contiguous gather

The KV Cache Engine
Powering 1M-Token LLMs

What Is a KV Cache — and Why Does It Matter?

The Problem: Quadratic Attention Cost

The Economics of Cache Hits: Why ~10× Cheaper

Every Request Has Two Radically Different Phases

Interactive: See Where the Money Goes

Why Providers Offer This Discount

Step-by-Step: How KV Cache Works

Step 1: Token Embedding

Step 2: Q, K, V Projection

Step 3: Cache the K and V Tensors

Step 4: Attention with Cached Keys & Values

Step 5: Feed-Forward → Output → Append → Repeat

How Frontier Models Tame the 1M-Context Beast

DeepSeek V4 Pro — Hybrid Compressed Attention

Three-Branch Architecture

Key Mechanisms

GLM 5.2 — Index Share Sparse Attention

Three-Pronged KV Cache Solution

Key Mechanisms

MiniMax M3 — MiniMax Sparse Attention (MSA)

MSA Architecture

Key Mechanisms

Head-to-Head: KV Cache Strategy Comparison

PagedAttention: The Memory Manager

Virtual Memory for KV Caches

Interactive KV Cache Memory Calculator