KV Caching in LLMs | Vivek Khatri

1 Why KV Cache Exists

Analogy
Think of a chef cooking a multi-course meal. Without KV caching, the chef re-reads the entire recipe before every single dish. With KV caching, the chef keeps a running summary of what's been done — and only reads the new step.

When an LLM generates text one token at a time (autoregressive decoding), it computes attention at every step. Attention uses three vectors per token:

Attention(Q, K, V) = softmax(Q · K^T / √d) · V

Every token produces its own Query, Key, and Value. The Query asks "what am I looking for?", the Key says "what do I contain?", and the Value says "what do I pass on?".

The problem: at step N, the model needs the K and V of every previous token to compute attention. Without caching, it recomputes all of them from scratch — every single time.

Without cache vs. With cache — for a 5-token sequence

✗ Without Cache

Step 1: compute K,V for [The]

Step 2: recompute K,V for [The, quick]

Step 3: recompute K,V for [The, quick, brown]

Total: 15 K,V computations (1+2+3+4+5)

✓ With KV Cache

Step 1: compute K,V for [The] → store

Step 2: fetch cached K,V, compute only for [quick]

Step 3: fetch cached K,V, compute only for [brown]

Total: 5 K,V computations (1+1+1+1+1)

Without Cache

O(n²) — 15 ops

With Cache

O(n) — 5 ops

That's the core idea: store K and V from past tokens so you never recompute them. The rest of this page explains the details and the techniques built on top of this idea.

2 How It Works — Step by Step

Let's walk through it with the sentence "The quick brown fox jumps". Click each step to watch the KV cache build up. Only the new token's K and V are computed — everything else comes from cache.

Notice how each step only computes one new K,V pair. The cached tokens (shown in green) are fetched from memory — no math needed. This is why KV caching turns O(n²) work into O(n) work.

3 The Memory Problem

KV caching solves the speed problem — but creates a memory problem. Every attention head stores its own K and V cache. More heads = more memory.

8 attention heads — each maintaining independent K and V caches

Cache per token = 2 × num_heads × head_dim

Real numbers
LLaMA-2 70B has 64 attention heads. For a single 4,000-token sequence, the KV cache alone can consume ~40 GB of GPU memory. That's more than the model weights themselves in some configurations.

This memory pressure is what drove researchers to develop KV sharing techniques — ways to reduce the number of independent KV caches without losing quality.

4 KV Sharing — MHA vs GQA vs MQA

The idea is simple: share KV caches between query heads. Fewer KV caches means less memory. The question is how aggressively to share.

MHA

Multi-Head Attention

32 Q heads, 32 KV heads

Each head has its own Q, K, V. Maximum quality, maximum memory. The baseline.

GQA

Grouped Query Attention

32 Q heads, 8 KV heads

Groups of 4 query heads share one KV head. Best balance of quality and memory.

MQA

Multi-Query Attention

32 Q heads, 1 KV head

All query heads share a single KV head. Maximum memory savings.

KV cache memory comparison (32 query heads)

MHA

32 KV heads — 100%

GQA

8 KV heads — 25%

MQA

1 KV head — 3%

Click to see how query heads map to KV heads

GQA is the sweet spot — it's what LLaMA-2, Mistral, and most modern LLMs use. You get most of MHA's quality with a fraction of the memory.

5 Beyond the Basics

Two more techniques tackle different aspects of the KV cache problem: memory layout and cache size.

PagedAttention — Memory Without Waste

Traditional KV cache allocates one contiguous block of GPU memory per sequence. This wastes memory when sequences are different lengths (like in a serving system handling many requests). PagedAttention (from vLLM) splits the cache into small fixed-size pages, like an operating system's virtual memory. Pages can be allocated on demand and freed when done — no wasted space.

Paged memory — allocate and free pages interactively

H2O — Not All Tokens Matter Equally

In natural language, some tokens get much more attention than others. Function words like "the" or "is" rarely matter — content words like "Python" or "transformer" do. H2O (Heavy-Hitter Oracle) exploits this: it tracks accumulated attention scores and evicts low-attention tokens when the cache is full, keeping only the "heavy hitters."

Score(t) = Σ attention received across all steps
Evict min(Score) when full → keep heavy hitters, drop light hitters

H2O simulation — tokens enter, scores accumulate, low-scorers get evicted

Cache budget: 5 tokens

Cache contents:

eviction threshold — tokens below are candidates

Event log:

6 Summary

All techniques at a glance

Technique	KV Heads	Memory per Token	Used In
MHA	h (all)	2 × h × d	GPT-3, BERT
GQA	g (grouped)	2 × g × d	LLaMA-2, Mistral
MQA	1 (shared)	2 × d	PaLM, Falcon
PagedAttention	Any	Pages (4-16 tok)	vLLM, SGLang
H2O	Dynamic	Budget B tokens	Research

TL;DR
KV Cache = store past K,V → avoid recomputation → O(n) instead of O(n²)
GQA = share KV across query groups → 75% less memory
PagedAttention = OS-style pages → zero memory waste
H2O = evict low-attention tokens → smaller cache, same quality