KV Cache Memory: Sizing LLM Inference

KV caching makes generation linear, not quadratic, but every cached token costs memory. The per-token sizing formula, the code, and what quantisation buys.

Cover Image for KV Cache Memory: Sizing LLM Inference

You're running a language model locally, and a short prompt fits comfortably in memory. A much longer conversation may slow generation or exhaust the memory available, even though the model itself has not changed. The KV cache grows with that conversation because it keeps information from earlier tokens for reuse. Understanding its size helps explain why fitting the weights is only part of the memory calculation.

Reusing tokens saves computation at a memory cost. At 400 tokens, GPT-2 generation is 2.5x faster with caching. We build a NumPy cache. At 128K context, Llama-3.1 8B's BF16 cache needs 15.6 GB, comparable to its weights. That arithmetic motivates KV cache compression.

By the end you will understand exactly why your GPU runs out of memory before your model runs out of things to say, and where quantisation fits in as the solution.

Let's Build It

Click the badge to open the interactive notebook:

Open In Colab

The cache fills one token at a time. Each new token adds a row of key and value vectors; every previous token's K and V are retrieved instantly from memory rather than recomputed.

Animated table showing a 3-layer KV cache filling token by token. The blue cell (NEW) marks the freshly computed key-value pair; green cells (KV) show entries retrieved from the cache rather than recomputed.

Here is the timing experiment in full. It runs GPT-2 small in two modes: naive (recompute every token's attention from scratch) and cached (use past_key_values).

import time
import numpy as np
import torch
from transformers import GPT2LMHeadModel, GPT2Tokenizer

device = "cuda" if torch.cuda.is_available() else "cpu"
tokenizer = GPT2Tokenizer.from_pretrained("gpt2")
model = GPT2LMHeadModel.from_pretrained("gpt2").to(device)
model.eval()

prompt = "The history of artificial intelligence is a story of"
input_ids = tokenizer.encode(prompt, return_tensors="pt").to(device)

def generate_naive(input_ids, n_tokens):
    """Recompute full attention at every step — O(n²) cost."""
    ids = input_ids.clone()
    with torch.no_grad():
        for _ in range(n_tokens):
            out = model(ids, use_cache=False)
            next_tok = out.logits[:, -1, :].argmax(dim=-1, keepdim=True)
            ids = torch.cat([ids, next_tok], dim=1)
    return ids

def generate_cached(input_ids, n_tokens):
    """Use past_key_values — O(n) cost per new token."""
    ids = input_ids.clone()
    past = None
    with torch.no_grad():
        for _ in range(n_tokens):
            out = model(
                ids if past is None else ids[:, -1:],
                past_key_values=past,
                use_cache=True,
            )
            past = out.past_key_values
            next_tok = out.logits[:, -1, :].argmax(dim=-1, keepdim=True)
            ids = torch.cat([ids, next_tok], dim=1)
    return ids

# Time both approaches across sequence lengths
seq_lengths = [50, 100, 200, 400]
for n in seq_lengths:
    t0 = time.perf_counter()
    generate_naive(input_ids, n)
    naive_t = time.perf_counter() - t0

    t0 = time.perf_counter()
    generate_cached(input_ids, n)
    cached_t = time.perf_counter() - t0

    print(f"{n:4d} tokens | naive {naive_t:.2f}s | cached {cached_t:.2f}s | {naive_t/cached_t:.1f}× faster")
  50 tokens | naive 0.70s | cached 0.48s |  1.5× faster
 100 tokens | naive 0.89s | cached 0.88s |  1.0× faster
 200 tokens | naive 2.41s | cached 1.51s |  1.6× faster
 400 tokens | naive 7.81s | cached 3.12s |  2.5× faster

The gap widens exactly as theory predicts. Naive generation scales quadratically with sequence length; cached generation scales linearly.

Line chart comparing GPT-2 naive vs KV cache generation time across 50, 100, 200, and 400 tokens. The red naive curve bends upward steeply while the blue cached curve stays near-linear.

What Just Happened?

The O(n²) problem in autoregressive generation

Transformer generation is autoregressive: you produce one token at a time, then feed the entire sequence (prompt plus everything generated so far) back into the model to predict the next token.

Attention is the bottleneck. For a sequence of nn tokens, computing attention requires comparing every token with every other token, a cost proportional to n2n^2. Produce 400 tokens and you run 1+2+3+…+400=80,2001 + 2 + 3 + \ldots + 400 = 80,200 individual attention comparisons across all layers. Double the sequence length and the computation quadruples.

Formally, the attention score between query qi\mathbf{q}_i and key kj\mathbf{k}_j is:

Attention(Q,K,V)=softmax ⁣(QK⊤dk)V\text{Attention}(\mathbf{Q}, \mathbf{K}, \mathbf{V}) = \text{softmax}\!\left(\frac{\mathbf{Q}\mathbf{K}^\top}{\sqrt{d_k}}\right)\mathbf{V}

For a single new token at position nn, the query vector is new, but the key and value vectors for positions 11 through n−1n-1 are identical to what you computed in the previous step. You are throwing away that work and recomputing it.

What the KV cache does

The key observation is that key and value vectors for a given token never change once that token is in context. The model is not recalculating what "The" means relative to everything else each time you generate a new word. Its key and value vectors are fixed by the weights applied to that token embedding.

So we store them. After computing keys and values for token ii, we write them into a cache. When generating token n+1n+1, we only need to compute the query, key, and value for the new token, then retrieve all previous keys and values from the cache to compute attention.

The per-step cost drops from O(n2)O(n^2) to O(n)O(n) (one full attention pass for the new token against all cached keys). Across the whole sequence, the total cost becomes O(n2)O(n^2) again, but the constant is dramatically smaller because each new token's computation is cheap.

Q, K, V: a quick intuition

Each token is projected into three vectors through learned weight matrices:

Diagram showing three tokens (I, love, cats) each producing Query, Key, and Value vectors. The KV cache boundary (dashed orange box) shows that only K and V vectors need to be stored and retrieved.

  • Query (Q\mathbf{Q}): "What am I looking for?" The current token's question to the sequence.
  • Key (K\mathbf{K}): "What do I advertise?" Each past token's index card.
  • Value (V\mathbf{V}): "What do I actually contain?" The information to extract if a query matches.

The attention mechanism computes dot products between the current query and all past keys to form a relevance score, then uses those scores to take a weighted sum of the values.

Only K\mathbf{K} and V\mathbf{V} need to be cached. The query for a past token is never needed again once we have moved past it.

Going Deeper

A NumPy mini-transformer with KV caching

To see the cache mechanics without framework abstractions, here is a minimal multi-head attention implementation with a use_cache flag:

import numpy as np

def softmax(x, axis=-1):
    e = np.exp(x - x.max(axis=axis, keepdims=True))
    return e / e.sum(axis=axis, keepdims=True)

class MultiHeadAttention:
    """Minimal MHA for d_model=64, n_heads=4."""
    def __init__(self, d_model=64, n_heads=4, seed=0):
        rng = np.random.default_rng(seed)
        d = d_model
        self.n_heads = n_heads
        self.d_head = d // n_heads
        # Learned projections (normally these come from training)
        self.W_q = rng.standard_normal((d, d)) * 0.02
        self.W_k = rng.standard_normal((d, d)) * 0.02
        self.W_v = rng.standard_normal((d, d)) * 0.02
        self.W_o = rng.standard_normal((d, d)) * 0.02
        # Cache storage: list of (K, V) per head
        self.cache_k = [[] for _ in range(n_heads)]
        self.cache_v = [[] for _ in range(n_heads)]

    def forward(self, x, use_cache=True):
        """
        x: (seq_len, d_model) — either full sequence or single token
        Returns: (seq_len, d_model) output
        """
        seq_len, d = x.shape
        n_heads, d_head = self.n_heads, self.d_head

        Q = (x @ self.W_q).reshape(seq_len, n_heads, d_head)
        K = (x @ self.W_k).reshape(seq_len, n_heads, d_head)
        V = (x @ self.W_v).reshape(seq_len, n_heads, d_head)

        out_heads = []
        for h in range(n_heads):
            q = Q[:, h, :]       # (seq_len, d_head)
            k_new = K[:, h, :]   # (seq_len, d_head)
            v_new = V[:, h, :]

            if use_cache and len(self.cache_k[h]) > 0:
                # Retrieve previous K and V from cache
                k_all = np.vstack(self.cache_k[h] + [k_new])
                v_all = np.vstack(self.cache_v[h] + [v_new])
            else:
                k_all = k_new
                v_all = v_new

            if use_cache:
                # Append the new token's K and V to the cache
                self.cache_k[h].append(k_new)
                self.cache_v[h].append(v_new)

            # Scaled dot-product attention
            scores = q @ k_all.T / np.sqrt(d_head)
            weights = softmax(scores)
            head_out = weights @ v_all
            out_heads.append(head_out)

        out = np.concatenate(out_heads, axis=-1) @ self.W_o
        return out

# Simulate token-by-token generation with cache
mha = MultiHeadAttention(d_model=64, n_heads=4)
rng = np.random.default_rng(42)
tokens = rng.standard_normal((10, 64))  # 10 token embeddings

print("Token-by-token generation with KV cache:")
for step in range(10):
    token = tokens[step:step+1]     # single token
    out = mha.forward(token, use_cache=True)
    total_cached = sum(len(mha.cache_k[h]) for h in range(mha.n_heads))
    print(f"  Step {step+1}: output shape {out.shape}, "
          f"total KV pairs cached = {total_cached}")
Token-by-token generation with KV cache:
  Step 1:  output shape (1, 64), total KV pairs cached = 4
  Step 2:  output shape (1, 64), total KV pairs cached = 8
  Step 3:  output shape (1, 64), total KV pairs cached = 12
  ...
  Step 10: output shape (1, 64), total KV pairs cached = 40

Each step appends 4 new K and V vectors (one per head). The attention for the new token correctly attends over all previously cached positions.

The O(n²) proof by counting

Let LL be the number of layers. For a sequence of nn tokens:

  • Naive generation: Step tt computes attention over tt tokens across LL layers. Total: L∑t=1nt=L⋅n(n+1)2=O(n2)L \sum_{t=1}^{n} t = L \cdot \frac{n(n+1)}{2} = O(n^2).
  • Cached generation: Step tt only computes the new token's projections and one dot product per cached K. Total: L⋅n⋅n=L⋅n2L \cdot n \cdot n = L \cdot n^2 operations on average... wait, is the cache really cheaper?

The distinction is subtle but important. With the cache, each step costs O(t⋅d)O(t \cdot d) for the attention (dot product of the query with all tt cached keys, each of dimension dd). Total across all steps is still O(n2d)O(n^2 d). The cache does not reduce the asymptotic complexity of the full generation.

What it eliminates is the expensive O(n2d)O(n^2 d) matrix multiply for the full context at each step. In naive generation, step tt recomputes the full t×tt \times t attention matrix and all tt key-value projections. With the cache, step tt only computes one new projection and one row of the attention matrix. The practical constant factor is far smaller.

At 400 tokens with GPT-2's 12 layers, the cache provides a 2.5x real-world speedup. At 4,000 tokens (common for document processing), the gap would be far larger.

Causal masking and the cache

One subtle point: the transformer uses causal (lower-triangular) masking so that token tt can only attend to positions 1,2,…,t1, 2, \ldots, t, not future positions. With the full sequence, you enforce this by masking the attention matrix.

With the cache, the masking is implicit: you only ever store keys and values for tokens that have already been generated. The current token's query is always at the last position, so it naturally can only attend to what is already in the cache.

This is why the cache only works for autoregressive (left-to-right) generation, not for bidirectional models like BERT. Those models need full context at every layer during inference, so there is nothing to cache.

The optimisers analogy

Batch normalisation during training and KV caching during inference both fall into the same category: engineering tricks that keep the forward pass tractable. Batch norm avoids pathological gradient scaling; the KV cache avoids redundant computation. Both create side effects that need managing (batch norm needs momentum statistics; the cache needs memory).

Act 3: You Swapped One Problem for Another

Faster generation sounds like a pure win. It is not. The KV cache stores key and value vectors for every token, every layer, every attention head. That memory adds up quickly.

The memory formula

The KV cache size in bytes is:

Cache memory=2×L×HKV×dhead×ntokens×bytes per element\text{Cache memory} = 2 \times L \times H_{\text{KV}} \times d_{\text{head}} \times n_{\text{tokens}} \times \text{bytes per element}

Where:

  • The factor of 22 is for keys and values
  • LL is the number of layers
  • HKVH_{\text{KV}} is the number of KV heads (may differ from attention heads with grouped-query attention)
  • dheadd_{\text{head}} is the dimension per head
  • bytes per element\text{bytes per element} is 2 for BF16/FP16, 4 for FP32

Llama-3.1 8B at scale

Llama-3.1 8B uses grouped-query attention with 32 KV heads... wait, let me be precise. The architecture has 32 transformer layers, 8 KV heads (grouped-query attention reduces from 32 attention heads to 8 KV heads), and head dimension 128. In BF16:

def kv_cache_gb(layers, kv_heads, head_dim, seq_len, bytes_per=2):
    """Calculate KV cache memory in GB."""
    total_bytes = 2 * layers * kv_heads * head_dim * seq_len * bytes_per
    return total_bytes / (1024 ** 3)

# Llama-3.1 8B parameters
L, H_kv, d_head = 32, 8, 128

configs = [
    ("4K context (typical chat)", 4_096),
    ("32K context (document)", 32_768),
    ("128K context (full window)", 131_072),
]

model_weights_gb = 16.0  # Llama-3.1 8B in BF16

for label, seq_len in configs:
    cache = kv_cache_gb(L, H_kv, d_head, seq_len)
    print(f"{label}: {cache:.1f} GB cache  ({cache/model_weights_gb*100:.0f}% of model weights)")
4K context (typical chat):   0.5 GB cache   (3% of model weights)
32K context (document):      3.9 GB cache  (24% of model weights)
128K context (full window):  15.6 GB cache (98% of model weights)

At 128K tokens, the KV cache is almost as large as the model itself. On an 80 GB A100, running a single BF16 Llama-3.1 8B at 128K context (16 GB weights + 15.6 GB cache) leaves only 48 GB for the rest of inference. With batching, the cache multiplies by batch size. Ten concurrent users each at 128K context would require 156 GB of cache alone.

To run these numbers for your own model, context length and hardware, the KV cache calculator applies the same formula across a set of published architectures and reports what fits on a given GPU.

Two-panel chart. Left: bar chart of KV cache size at 1K, 4K, 16K, 32K, 64K, 128K context lengths compared to the 16 GB model weights line. Right: continuous memory growth curve showing BF16 cache vs 4-bit and 3-bit quantised cache, with the region where cache exceeds model weights shaded red.

The crossover point is around 100K tokens: beyond that, the cache exceeds model weight memory. For production systems running many concurrent requests, the cache is often the dominant memory consumer well before that.

Where collaborative filtering and embedding tables fit in

If you have worked with embedding-based models, the KV cache feels familiar: it is a lookup table that grows at runtime. The difference is that the KV cache is dense (every position gets an entry) and unbounded (it grows with every token), whereas embedding tables have a fixed vocabulary.

The growth is the problem. A traditional embedding table for 50,000 vocabulary items at 768 dimensions is 150 MB. A KV cache at 128K context for Llama-3.1 8B is 15.6 GB. Same concept, radically different scale.

Act 4: Quantisation as the Escape Hatch

The pattern is now clear:

  1. Autoregressive attention is O(n²). The KV cache fixes this.
  2. The KV cache costs O(n) memory. This becomes the new constraint.
  3. The escape hatch is compressing the cached vectors.

If you can store each cached key and value in 3 bits instead of 16, you use roughly 5x less memory. At 128K context, that takes the Llama-3.1 8B cache from 15.6 GB down to about 3 GB.

bits_choices = [16, 8, 4, 3]
for bits in bits_choices:
    cache = kv_cache_gb(L, H_kv, d_head, 131_072, bytes_per=bits/8)
    print(f"  {bits:2d}-bit: {cache:.1f} GB")
16-bit: 15.6 GB
 8-bit:  7.8 GB
 4-bit:  3.9 GB
 3-bit:  2.9 GB

The challenge is doing this compression without destroying the information that attention depends on. Naive quantisation of transformer activations fails because of outliers: a handful of coordinates carry most of the vector's magnitude, and snapping them to a coarse grid collapses the angular information that dot products depend on.

The TurboQuant post covers the solution in detail. The key idea is to randomly rotate each vector before quantising, which spreads the energy evenly across all coordinates and makes every quantisation bit count. At 3-4 bits, TurboQuant achieves quality-neutral compression compared to full-precision inference on needle-in-a-haystack benchmarks.

The connection to transfer learning is worth noting: the reason KV cache compression is hard is the same reason fine-tuning pre-trained models requires care. The representations in deep layers are not uniformly distributed. They concentrate information in specific directions that the model learned during training. Any compression scheme has to respect that structure.

Where This Comes From

The KV cache is not a novel invention with a single founding paper. It is an obvious engineering optimisation that any implementation of autoregressive attention would adopt. The key papers are on the attention mechanism itself and on managing the memory implications.

Vaswani et al. (2017), "Attention Is All You Need" introduced the scaled dot-product attention mechanism. The original Transformer was designed for encoder-decoder sequence-to-sequence tasks, but the architecture generalised to decoder-only autoregressive models (GPT) where the KV cache is essential.

Grouped-query attention (Ainslie et al. 2023, "GQA: Training Generalised Multi-Query Transformer Models for Faster Inference") is the architectural change behind Llama-3.1's 8 KV heads. Instead of one set of K and V per attention head (so 32 sets for a 32-head model), GQA groups multiple query heads to share a single K and V. This directly reduces the KV cache size by the grouping factor (4x for Llama-3.1 8B, from 32 to 8 KV heads).

PagedAttention (Kwon et al. 2023, "Efficient Memory Management for Large Language Model Serving with PagedAttention") introduced the idea of managing KV cache memory like an operating system manages virtual memory: allocating it in pages, allowing different requests to share pages, and avoiding fragmentation. This is the technique behind vLLM.

The memory formula in Act 3 comes directly from counting bytes: 2 (K and V) × layers × KV heads × head dim × sequence length × bytes per element. There is no trick to it, just arithmetic that becomes alarming at scale.

Further Reading

Interactive Tools

  • Attention Visualizer: What the cache is holding. Walk through query, key and value on a sentence you type, and see why only K and V are worth keeping between steps
  • KV Cache Calculator: Run the arithmetic in this post against any model, context length, batch size and precision, and see what fits on an A100, H100 or 4090
  • LLM Cost Calculator: Compare live pricing across 300+ APIs; the per-token cost reflects the inference infrastructure costs that KV caching directly reduces
  • Normal Distribution Calculator: Visualise the Gaussian distribution that quantised KV cache coordinates follow after random rotation

Stay in the loop

Get notified when new tutorials and deep-dives are published. No spam, unsubscribe anytime.

Related Posts

Frequently Asked Questions