The KV Cache: Why Long Chats Get Slow and Expensive
The memory trick that makes generation fast, and the bill it quietly runs up.
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, generating a thousand-word reply would be as computationally expensive as training on that entire conversation from scratch.
The KV cache turns autoregressive decoding from an algorithm that grows quadratically in sequence length into one that’s nearly linear per step. That’s the good news. The bad news is that the cache’s memory footprint grows linearly with conversation length, model depth, embedding size, and batch concurrency. For long chats, the cache becomes the primary memory sink on the GPU (graphics processing unit), the main driver of per-token latency, 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). 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. Over (T) generated tokens that would cost O((T^2)) attention operations, making even short conversations absurdly expensive.
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.
- Recompute K and V for all past tokens each step
- Quadratic attention cost per token
- O(n^2) time complexity
- Compute K and V only for the new token
- Linear attention cost per token
- O(n) time complexity
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 only reads the cache and appends a single row per step. This is what turns each decode step’s attention cost from O((t^2)) to O((t)), where (t) is the current sequence length. The practical speedup is dramatic: a 7-8× increase in tokens per second on CPU-bound setups after enabling KV caching source.
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 head per token: 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 jarring. For a decoder-only model with (L) layers, (H) KV-heads (if grouped-query attention is used, this may be fewer than query heads), head dimension (d_h), and a sequence length (S) spanning prompt plus generated tokens, each cache entry per sequence is:
- Keys: (L \times H \times S \times d_h) elements
- Values: (L \times H \times S \times d_h) elements
Storing both in 16-bit (BF16/FP16) gives:
[ \text{KV bytes per sequence} = 2 \times L \times H \times S \times d_h \times 2 ]
Using (d_{\text{model}} = H \cdot d_h), that simplifies to:
[ \text{KV bytes per sequence} = L \times d_{\text{model}} \times S \times 4 ]
Take a real model. Llama 3.1 8B has 32 layers, hidden size 4096, and 8 KV-heads per layer with head dimension 128 (grouped-query with 32 query heads). For a prompt of 4,096 tokens and a generated 4,096-token reply, (S = 8192). The cache for that one conversation needs:
[ 32 \times 4096 \times 8192 \times 4 \text{ bytes} \approx 4 \text{ GB} ]
That’s a single conversation. A 70B model with hidden size 8192 and 80 layers can demand 20-30 GB per sequence at 32k context. Meanwhile, batching multiple conversations multiplies that cost linearly. In many serving deployments, the KV cache consumes more GPU memory than the model parameters source.
The problem isn’t just capacity. The decode step must read the entire cache for every new token’s attention computation. As cache grows, the memory bandwidth needed for those reads increases, and per-token latency rises directly with sequence length. This is why a 100k-token conversation feels sluggish even if 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:
- The current token’s embedding enters the first layer.
- For each attention head, the layer computes a new query (q), a new key (k), and a new value (v).
- It appends (k) and (v) to the per-layer cache for this sequence.
- 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.
- The output passes through the feed-forward network, and the next layer does the same.
This loop runs for every generated token. Notice that the attention step is the only part that touches the entire history. The feed-forward network and normalization layers operate only on the current token, so their cost per step is constant. The bottleneck is the memory-bound attention operation that reads the entire cache.
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 fuse attention operations to reduce memory roundtrips source, the linear growth in read volume eventually dominates.
- Memory pressure limits concurrency. The scheduler must allocate a KV cache block for every active and pending sequence. When the user sends a new message in a long conversation, the prefill must recompute the entire prefix if the cache was evicted or the model is stateless between requests. Many serving frameworks now use paged memory (PagedAttention) to manage the cache in fixed-size blocks, avoiding fragmentation and enabling prefix sharing source.
The core tension: 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 having separate K and V heads for every query head, GQA uses a smaller number of KV heads shared across query groups. Llama 3.1 8B uses 8 KV-heads with 32 query heads, reducing the KV cache by 4× compared to a full multi-head setup. MQA (1 KV-head) reduces it further but can hurt model quality source.
KV cache quantization. Keys and values can be stored in 8-bit or even 4-bit integers instead of FP16. Because the attention computation is performed with higher precision (e.g., dequantizing on the fly), the memory footprint drops by 2-4× with minimal accuracy loss source.
PagedAttention and virtual memory. The vLLM framework treats the KV cache like virtual memory: store it in non-contiguous blocks, map them logically, and evict cold blocks under memory pressure. This allows serving many sequences with a fraction of the peak memory and enables prefix caching when multiple requests share the same prompt prefix source.
Prefix caching. When a user sends a new message that carries forward the entire conversation history, the prompt prefill for the earlier tokens is identical to what was computed before. The cache can be reused, either in whole or by sharing a prefix tree across requests, dodging recomputation entirely for the repeated portion.
Token-axis compression. Some methods drop or merge tokens from the cache that are deemed less important using heuristics or learned selection, effectively shortening the effective context for attention while keeping important windows source.
Offloading. The KV cache can spill to CPU (central processing unit) memory or even NVMe storage, with on-demand prefetching when a specific cache 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 comes in, the cache pool is full, and there’s no free block to append the next token’s KV entries. Without a management strategy, the model either throws an out-of-memory error or the generation stalls.
PagedAttention-based schedulers handle this by evicting blocks from the least recently used or lowest priority sequences, possibly recomputing them later if needed. This eviction may force a full prefill of the prefix on the next interaction, causing latency spikes. Some systems preemptively compress or quantize older KV blocks to make room. Others refuse new requests when cache pressure crosses a threshold, effectively limiting concurrency.
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 scheduler still must bound the total physical page count. 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 scope per token | 2 vectors (K, V) per head per layer |
| Per-sequence KV size (bytes) | (2 \times L \times H \times S \times d_h \times b) (b = bytes per element) |
| Simplified form | (L \times d_{\text{model}} \times S \times 2 \times b) |
| FP16 bytes per element | 2 |
| Latency impact of long context | Per-token decode grows linearly with sequence length |
| Common mitigation | GQA, KV quantization (8-bit), PagedAttention, prefix caching |
| Framework example | vLLM uses block-wise page table for KV cache source |
| Eviction policy | LRU per block, sometimes with priority (preemptible vs. pinned) |
Frequently Asked Questions
Q: Why can’t you just recompute the cache on the fly when memory is tight? The entire point of the KV cache is avoiding recomputation. If you drop an old block, generating the next token would need a full recomputation of that block plus everything after it, which is a huge latency spike. In practice, serving systems do recompute selectively when a block is evicted and then demanded again, but they try very hard to avoid that in latency-sensitive paths.
Q: Does the KV cache affect only long chats, or short ones too? Short conversations benefit because the cache eliminates overhead. For a 100-token prompt the prefill fills a small cache and subsequent decode steps are cheap. The pain starts when the cache grows beyond the point where per-token read bandwidth dominates, usually around 4-8k tokens for large models without optimization.
Q: Can I put the KV cache on CPU memory to save GPU RAM (random-access memory)? Yes, but attention reads will then pay the PCIe bandwidth penalty, which can slow generation to a crawl. That’s why offloading is usually combined with selective prefetching or only used for less frequently accessed “cold” blocks. NVMe offloading is even slower but can support enormous context windows 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 can reduce cache memory by 2-8× with negligible quality loss for many models.
Q: Does FlashAttention eliminate the KV cache bottleneck? No. FlashAttention makes the attention computation faster by fusing operations and reducing memory writes during the attention step, but it still must read the entire cache from HBM. It reduces the latency constant factor but does not change the O((S)) scaling of memory reads. The cache size itself remains unchanged.
Test yourself
Scenario: You’re running a serving deployment of a 70B model with GQA (8 KV heads) and 32k context window. A single user starts a conversation that gradually reaches 30k tokens of history. Suddenly, other users see increased time-to-first-token and lower throughput. Your GPU utilization drops, and you notice OOM evictions in the scheduler logs. What is likely happening, and what change would you make first to restore service?
Answer: The user’s KV cache has grown to roughly 20-30 GB (depending on head dimensions), consuming a large fraction of the GPU’s KV page pool. The scheduler is evicting pages from other users to make room, causing those sequences to require recomputation on their next prompt, and possibly refusing new requests. Your first move would likely be to enable quantized KV storage (e.g., 8-bit), which would shrink that user’s cache by ~50% without quality degradation. If that alone doesn’t restore acceptable concurrency, you’d lower the maximum sequence length for that deployment or switch to dynamic batching with preemptive flushing of old pages. For long-conversation resilience, you’d also deploy prefix caching so that repeated message-history preambles are shared rather than duplicated.
If you want this kind of breakdown every week, how real serving stacks actually work under the hood, subscribe to Internals Decoded at internalsdecoded.com. We don’t cover the hype. We cover the memory layouts.
Sources
- Attention Is All You Need, original Transformer with encoder-decoder, but self-attention in decoders laid groundwork for KV caching.
- Optimize LLM (large language model) Inference, Hugging Face post showing 7-8× speedup from KV caching on CPU.
- PagedAttention: vLLM, introduces block-wise virtual memory for KV cache, eviction policies.
- FlashAttention: Fast and Memory-Efficient Exact Attention, reduces HBM reads but cache reads still scale linearly.
- GQA: Training Generalized Multi-Query Transformers, reduced KV heads.
- TensorRT-LLM, includes KV cache quantization.
- A Length-Extrapolated Transformers Approach, token dropping as compression (example of token-axis methods).
- internalsdecoded.com