The KV Cache: Why Long Chats Get Slow and Expensive

In Part 1, we followed a user request from "Enter" through tokenization, prompt prefill, and the first decoded token streaming back. Now we're looking at the piece of infrastructure that makes every subsequent decode step efficient: the KV (key-value) cache. It stores the attention keys and values for every token the model has seen, across every layer and head. Without it, every new word would mean re-running the model over the entire conversation so far.

The KV cache changes how the cost of each new token grows. Without it, the attention work for a new token grows with the square of the conversation length; with it, that work grows in step with the length. That's the good news. The bad news is that the cache's memory footprint grows linearly with conversation length, the number of layers, the number and size of the KV heads, and the number of conversations served at once. For long chats and busy servers, the cache becomes the largest user of GPU (graphics processing unit) memory after the model's weights, a growing share of the memory read at every decode step, and the hard limit on how many users you can serve.

How does the KV cache eliminate redundant work?

Think of a long meeting. Someone says something halfway through and you want to reply. You could replay the entire audio recording from the start to recall what was said earlier. Or you could keep a running transcript and glance at earlier lines. The transcript is your KV cache, and reading it costs much less than recomputing everything.

Inside a Transformer layer, self-attention computes three projections for each token position: a query (Q), a key (K), and a value (V). In plain words, the query is what this token is looking for, the key is what each token offers to be matched against, and the value is the information a token passes on when it matches. During training, the model processes the whole sequence in parallel. At inference, though, we generate one token at a time, conditioning on all previous tokens. Naively, for each new token the model would recompute Q, K, and V for every past token and run a full attention pass over the entire history. To produce token number $t$, that means attention work that grows like $t^2$ (each of the $t$ positions attends to up to $t$ others), plus the projections and feed-forward layers for all $t$ tokens.

The KV cache avoids this by storing the K and V tensors for every token after the first time they are computed. When generating a new token, the model only computes a new Q, K, and V for the current position, appends that single K and V row to the cache, and then attends from the new query across all cached keys. No past recomputation. Producing token $t$ now costs one query against $t$ cached keys, so the attention work grows like $t$, and the projections and feed-forward layers run for one token instead of $t$.

In the usual shorthand, $O(t)$ means work that grows in proportion to $t$ and $O(t^2)$ work that grows with its square. Over a whole reply of $T$ tokens the total attention work is still about $T^2$ with the cache (and $T^3$ without it), so the cache does not make long replies free. It removes the repeated work.

Autoregressive Decoding With vs Without KV Cache

Without KV cache

• Recompute K and V for every past token at each step
• Attention work per new token grows with the square of the length
• Projections and feed-forward run on every token, every step

With KV cache

• Compute K and V only for the new token
• Attention work per new token grows in step with the length
• Projections and feed-forward run on the new token only

In the prefill phase (when the prompt first arrives), the model computes K and V for the entire prompt in one forward pass and writes them into the cache. The decode loop from then on reads the cache and appends a single row per step, which is what turns each decode step's attention cost from $O(t^2)$ to $O(t)$, where $t$ is the current sequence length. Hugging Face's guide Optimizing your LLM in production puts the practical advice simply: always use the cache, because it gives identical results and a significant speed-up for longer inputs.

There's no cache for queries. A query vector is computed from the current token and used exactly once; it's never needed again. Keys and values, by contrast, must be available for every future attention step. So the KV cache stores two vectors per KV head per token in every layer: the key and the value.

Why does the cache become so large as conversations grow?

The memory scaling is easy to derive, and the numbers are worth working through once by hand. For a decoder-only model with $L$ layers, $H_{\text{KV}}$ key-value heads per layer (with grouped-query attention this is fewer than the query heads), head size $d_h$, and a sequence length $S$ covering prompt plus generated tokens, the cache for one sequence holds:

• Keys: $L \times H_{\text{KV}} \times S \times d_h$ numbers
• Values: $L \times H_{\text{KV}} \times S \times d_h$ numbers

Stored in 16-bit precision (BF16 or FP16, 2 bytes per number), the cache for one sequence takes:

$$\text{KV bytes} = 2 \times L \times H_{\text{KV}} \times d_h \times S \times 2$$

You may see this written with the model's hidden size, as $L \times d_{\text{model}} \times S \times 4$. That shortcut holds only for plain multi-head attention (MHA), where every query head has its own KV head and so $H_{\text{KV}} \times d_h = d_{\text{model}}$. Under grouped-query attention it overstates the cache by the ratio of query heads to KV heads.

Take a real model. Llama 3.1 8B has 32 layers and a hidden size of 4,096, split into 32 query heads of size 128, but only 8 KV heads (The Llama 3 Herd of Models, Table 3). One token's cache, across all layers, is:

$$\begin{aligned} 2 \times 32 \times 8 \times 128 \times 2 &= 131{,}072 \text{ bytes} \\ &= 128 \text{ KiB} \end{aligned}$$

For a 4,096-token prompt plus a 4,096-token reply, $S = 8{,}192$:

$$\begin{aligned} 131{,}072 \times 8{,}192 &= 1{,}073{,}741{,}824 \text{ bytes} \\ &= 1 \text{ GiB} \approx 1.07 \text{ GB} \end{aligned}$$

A GiB is $2^{30}$ bytes, slightly more than a billion. If the same model used full multi-head attention, with 32 KV heads, the cache would be four times larger: 4 GiB. That factor of four is exactly what GQA saves.

Now a bigger model. Llama 3.1 70B has 80 layers and also 8 KV heads of size 128 (shared by its 64 query heads), and it accepts up to 128K tokens. Per token:

$$\begin{aligned} 2 \times 80 \times 8 \times 128 \times 2 &= 327{,}680 \text{ bytes} \\ &= 320 \text{ KiB} \end{aligned}$$

At 32,768 tokens that's $327{,}680 \times 32{,}768 = 10{,}737{,}418{,}240$ bytes, exactly 10 GiB, for a single conversation. Without GQA (64 KV heads) it would be eight times larger, 80 GiB, more than an entire 80 GB GPU holds.

Batching multiplies these numbers, because every conversation in flight carries its own cache. Llama 3.1 8B's weights take about 16 GB in BF16 (8 billion parameters at 2 bytes each), and sixteen conversations of 8,192 tokens need 16 GiB of cache, about as much as the model itself. The vLLM paper's example of a 13B model on one A100 GPU gives about 65% of memory to the weights and close to 30% to the KV cache (Efficient Memory Management for Large Language Model Serving with PagedAttention); with longer contexts and bigger batches, the cache can rival or pass the weights.

For comparison, older models without GQA pay much more per token. The Llama 2: Open Foundation and Fine-Tuned Chat Models paper uses GQA only at 34B and 70B, so Llama 2 7B keeps all 32 KV heads: $2 \times 32 \times 32 \times 128 \times 2 = 524{,}288$ bytes (512 KiB) per token, or 2 GiB at its full 4,096-token context. The chart sets the three side by side, computed from the configurations in that paper and in The Llama 3 Herd of Models.

KV Cache Memory Footprint

1 GiB

Llama 3.1 8B (GQA, 8 KV heads) at 8,192 tokens

2 GiB

Llama 2 7B (no GQA, 32 KV heads) at its full 4,096 tokens

10 GiB

Llama 3.1 70B (GQA, 8 KV heads) at 32,768 tokens

The problem isn't just capacity. Every decode step reads the model's weights once (Part 1 explained why) and each sequence's whole cache once. For a single user on Llama 3.1 8B, the cache read only catches up with the 16 GB weight read at about 122,000 tokens (16 GB divided by 128 KiB per token). But a server batches many users into each step: the weights are read once for all of them, while every user's cache is read separately. With sixteen users at 8,192 tokens each, the cache reads already match the weight reads. As conversations lengthen, per-token latency rises with them, which is why a 100,000-token conversation feels sluggish even when the model can technically handle it.

How does the cache interact with the decode loop in a serving stack?

Let's follow our running request through the system. In Part 1, the scheduler received the user prompt, tokenized it, ran the prefill pass, and emitted the first token. Now the decode loop kicks in to produce the rest.

At each decode step:

1. The current token's embedding enters the first layer.
2. For each attention head, the layer computes a new query $q$, and for each KV head a new key $k$ and value $v$.
3. It appends $k$ and $v$ to the per-layer cache for this sequence.
4. It multiplies $q$ against all cached keys, scales, applies softmax with causal masking, and computes the attention output as a weighted sum of cached values.
5. The output passes through the feed-forward network, and the next layer does the same.
6. After the last layer, the model turns the final vector into one score per vocabulary token (the logits) and samples the next token.

This loop runs for every generated token. Notice that the attention step is the only part that touches the entire history. The projections, the feed-forward network and the normalization layers operate only on the current token, so their cost per step stays constant, while attention's cost grows with the history. At short lengths, reading the weights dominates each step; as the history grows, reading the cache takes a larger share.

Diagram loading

Two implications matter for serving systems:

• Latency grows with conversation length. Each new token takes longer to produce because the query-key multiplication reads more and more cache. Even with optimized kernels like FlashAttention, which tile the attention computation to cut reads and writes to the GPU's main memory (FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness), the cache itself must still be read, so the linear growth in read volume eventually dominates.
• Memory pressure limits concurrency. The scheduler must find cache space for every running sequence. When the user sends a new message in a long conversation, the prefill must recompute the entire prefix if its cache was evicted or the server keeps nothing between requests. Serving engines such as vLLM store the cache in small fixed-size blocks to avoid fragmentation and to share prefixes; Part 3 covers how.

The tension is plain: the KV cache is essential for speed, but as conversations lengthen it turns into the dominant cost driver.

What tricks reduce the KV cache footprint?

Engineers have built a toolbox to shrink the cache without sacrificing too much quality:

Grouped-Query Attention (GQA) and Multi-Query Attention (MQA). Instead of a separate K and V head for every query head, GQA shares a smaller number of KV heads across groups of query heads. Llama 3.1 8B uses 8 KV heads for 32 query heads, a cache four times smaller than full multi-head attention would need, and the GQA paper found quality close to multi-head attention at nearly the speed of MQA (GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints). MQA goes all the way to one KV head (Fast Transformer Decoding: One Write-Head is All You Need); it shrinks the cache further but can cost quality.

KV cache quantization. Keys and values can be stored in 8-bit formats (in production usually FP8) or even 4-bit ones instead of 16-bit. Going from 16 to 8 bits halves the cache, so the same memory holds twice as many tokens. vLLM, for example, turns on an FP8 cache with --kv-cache-dtype fp8 and recommends calibrated scaling factors for the best accuracy (Quantized KV Cache). At 8 bits the quality change is usually small: vLLM's own tests found at most 1 to 2 points of accuracy lost on short-context tasks, with hybrid models that use small sliding-window layers as the main exception (The State of FP8 KV-Cache and Attention Quantization in vLLM). Below that it depends on the method: KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache keeps quality close to the original at 2 bits by quantizing keys per channel and values per token. Test any low-bit cache on your own long-context tasks.

Paged blocks. Engines like vLLM split the cache into small fixed-size blocks instead of one big reserved buffer per request, which nearly removes wasted memory and lets requests share identical prefix blocks. Part 3 covers how.

Prefix caching. When a user sends a new message that carries forward the entire conversation history, the prefill for the earlier tokens is identical to what was computed before. The cache can be reused, either in whole or by sharing blocks across requests, skipping recomputation for the repeated portion.

Token eviction. Some methods drop the tokens that matter least. H2O keeps a balance of recent tokens and the few "heavy hitter" tokens that receive most of the attention (H₂O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models). StreamingLLM keeps the first few tokens, which act as "attention sinks", plus a window of recent ones (Efficient Streaming Language Models with Attention Sinks). Both trade the ability to recall the dropped tokens for a cache of fixed size.

Offloading. The KV cache can spill to CPU (central processing unit) memory or even NVMe storage (fast solid-state drives), with on-demand prefetching when a specific block is needed. This trades latency for capacity.

No single trick solves everything. Production serving stacks typically combine several.

What happens when the KV cache runs out of memory?

The scheduler's nightmare: a request needs room for its next token's keys and values, the cache pool is full, and there's no free block. Without a management strategy, the server either throws an out-of-memory (OOM) error or the generation stalls.

vLLM handles this by preemption. Its paper describes an all-or-nothing policy: the scheduler picks whole requests, the latest arrivals first, and frees every block they hold; when memory frees up, the paused requests come back (Efficient Memory Management for Large Language Model Serving with PagedAttention). Current vLLM restores them by recomputing their cache, re-running prefill over the prompt plus everything generated so far (vLLM's tuning guide); the paper also describes copying the blocks to CPU memory instead. Either way, the paused user sees a latency spike.

Least recently used (LRU) eviction applies to a different pool: cached prefix blocks that no running request is using, which vLLM evicts oldest first when it needs space (vLLM's prefix caching design notes). Other systems refuse new requests when cache pressure crosses a threshold, which limits concurrency instead.

For long chats specifically, a naive implementation that allocates a contiguous buffer for the maximum context length wastes huge amounts of memory when conversations are short. With paged memory, only the blocks actually used for a conversation consume physical memory, but the pool is still finite. As a user's chat lengthens, they occupy more and more blocks, slowly crowding out other users.

This is the real meaning of "expensive." It's not just GPU rental cost; it's the degraded throughput and latency that long conversations impose on everyone sharing the serving infrastructure.

Quick Reference

Property	Value / Formula
Cache contents per token	One key and one value vector per KV head, in every layer
Per-sequence KV size (bytes)	$2 \times L \times H_{\text{KV}} \times d_h \times S \times b$ (b = bytes per number)
Shortcut, MHA only	$2 \times L \times d_{\text{model}} \times S \times b$ (overstates the cache under GQA)
BF16 or FP16 bytes per number	2
Llama 3.1 8B, BF16	128 KiB per token, 1 GiB at 8,192 tokens
Llama 3.1 70B, BF16	320 KiB per token, 10 GiB at 32,768 tokens
Latency impact of long context	Per-token decode time grows linearly with sequence length
Common mitigations	GQA, FP8 KV cache, paged blocks, prefix caching
Out of memory (vLLM)	Preempt whole requests, latest first; recompute their cache later
LRU eviction	Only for cached prefix blocks that no running request uses

Frequently Asked Questions

Q: Why can't you just recompute the cache on the fly when memory is tight? You can, and vLLM does exactly that when it preempts a request: it frees all of the request's blocks and later re-runs prefill over the whole sequence, prompt plus the tokens generated so far. Prefill processes tokens in parallel, so this costs far less than generating them did, but it still adds a latency spike for that user and spends GPU time other users could have had. That's why schedulers try to avoid it on latency-sensitive paths.

Q: Does the KV cache affect only long chats, or short ones too? Short conversations benefit because the cache removes repeated work. For a 100-token prompt the prefill fills a small cache and subsequent decode steps are cheap. The pain grows with the total cache size. For a single user on Llama 3.1 8B, reading the cache only matches reading the weights at about 122,000 tokens. On a busy server, sixteen users at 8,192 tokens each already reach that point, because each user's cache is read separately while the weights are read once per step for everyone.

Q: Can I put the KV cache on CPU memory to save GPU RAM (random-access memory)? Yes, but attention reads would then cross PCIe (the bus between the CPU and the GPU), which is far slower than the GPU's own memory and can slow generation to a crawl. That's why offloading is usually combined with selective prefetching or used only for "cold" blocks that are not needed right now. NVMe offloading is slower still but can hold enormous contexts at the cost of latency spikes.

Q: What's the difference between multi-head attention (MHA) and grouped-query attention (GQA) for cache size? In MHA, every query head has its own K and V head, so $H_{\text{KV}} = H_{\text{Q}}$. In GQA, a few KV heads are shared across query heads, so $H_{\text{KV}} < H_{\text{Q}}$. The KV cache size scales directly with $H_{\text{KV}}$, so GQA shrinks the cache by the ratio $H_{\text{Q}} / H_{\text{KV}}$: four times for Llama 3.1 8B (32 query heads, 8 KV heads) and eight times for Llama 3.1 70B (64 and 8). The GQA paper found quality close to multi-head attention.

Q: Does FlashAttention eliminate the KV cache bottleneck? No. FlashAttention makes the attention computation faster by tiling it, so fewer intermediate results travel to and from HBM (high-bandwidth memory, the GPU's main memory), but it still must read the entire cache from HBM. It reduces the constant factor but does not change the $O(S)$ growth of cache reads per token. The cache size itself remains unchanged.

Test yourself

Scenario: You serve Llama 3.1 70B (80 layers, GQA with 8 KV heads of size 128) in BF16. After the weights, about 15 GB of GPU memory is left for the KV cache pool. One user's conversation grows to 30,000 tokens of history. Soon other users see a longer time to first token and lower throughput, and the scheduler logs show preemptions. Roughly how much of the pool does that one user hold, and what would you change first?

Answer: One token costs $2 \times 80 \times 8 \times 128 \times 2 = 327{,}680$ bytes, so 30,000 tokens take about 9.8 GB, two thirds of the 15 GB pool. Everyone else shares the last third, so the scheduler keeps preempting their requests and recomputing them later: that is the slow first tokens and the lost throughput. The first change is an FP8 KV cache (in vLLM, --kv-cache-dtype fp8). It halves every sequence's cache, not just this user's: the long chat drops to about 4.9 GB and the pool holds twice as many tokens for everyone, usually with a small quality loss that you should test. Next, cap the context length per request (--max-model-len) so one conversation cannot take most of the pool, keep prefix caching on so shared system prompts are stored once, and if load stays high, add GPUs or move the weights to FP8 to free more memory for the cache.

Next: Batching and PagedAttention: How vLLM Serves Hundreds at Once. It shows how vLLM stores this cache in small blocks and keeps one GPU busy with many requests at once.

If you want this kind of breakdown every week, how real systems actually work under the hood, subscribe to Internals Decoded at internalsdecoded.com.

Sources

• Attention Is All You Need (Vaswani et al. 2017), the original Transformer
• Optimizing your LLM in production (Hugging Face, September 2023)
• Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al. 2023)
• The Llama 3 Herd of Models (Meta 2024), Table 3 for the layer and head counts
• Llama 2: Open Foundation and Fine-Tuned Chat Models (Touvron et al. 2023)
• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (Dao et al. 2022)
• GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints (Ainslie et al. 2023)
• Fast Transformer Decoding: One Write-Head is All You Need (Shazeer 2019)
• KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache (Liu et al. 2024)
• H₂O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models (Zhang et al. 2023)
• Efficient Streaming Language Models with Attention Sinks (Xiao et al. 2023)
• Quantized KV Cache (vLLM documentation)
• The State of FP8 KV-Cache and Attention Quantization in vLLM (vLLM blog, April 2026)
• Optimization and Tuning (vLLM documentation)
• Automatic Prefix Caching design (vLLM documentation)