Why the KV Cache is Needed: Remembering to Avoid Recomputation

Status: Draft (2026-10-13), partially measured. The toy model measurements (Section 3) were measured directly by the author on a laptop CPU. The GPU server measurements (Sections 4 and 6) re-reference values measured on a single 8GB-class GPU from the "Toss ML/AI Infra Preparation" series on the same site. Model configurations were verified from official configs and paper tables (viewed 2026-10-13), and KV sizes were calculated using those values. Writing rule: Measured data is the default; unmeasured items are marked as "Unmeasured", and unverified items are marked as "Unverified".

Table of Contents

• 1. Models That Generate One Token at a Time
• 2. Without a Cache, Starting from Scratch at Every Step
• 3. Trying It Yourself: numpy Toy Transformer
• 4. The Cost of the Cache: Memory
• 5. Methods to Reduce Size: MHA → GQA → MQA → MLA
• 6. Prefill and Decode: Two Phases with Different Characteristics
• 7. Summary: Questions This Series Will Follow
• References

1. Models That Generate One Token at a Time

A chatbot's response does not appear all at once. The model looks at the text so far (prompt + answers generated so far) to choose a single next token, appends that token to the end of the text, and chooses the next token again. This is called autoregressive decoding.

When choosing a single token, each layer of the transformer computes attention. It creates three vectors for each token:

• Q (Query): "What am I looking for right now?"
• K (Key): An index saying, "I contain this kind of content."
• V (Value): The actual content to be passed along.

The Q of the new token is compared one by one with the Ks of the preceding tokens to score them (how relevant they are), and the Vs are mixed using those scores. Expressed as a formula, it is softmax(q·Kᵀ/√d)·V .

There is an important property here. Language model attention is masked so that it cannot look ahead(causal mask). Because the K and V of the 3rd token are created by looking only at the 1st through 3rd tokens, even if 100 tokens are appended afterwards, they do not change . Therefore, there is no reason to discard the K and V once they are created and make them again. We can store them and retrieve them in the next step. This is the KV cache.

Q is not stored. This is because the Q of a previous token is never used again after it is used once to create that token. The only Q needed for a new step is that of the new token itself.

2. Without a Cache, Starting from Scratch at Every Step

Without a cache, at the t-th step, the K and V of all t tokens are re-created. Since the linear projections (Q, K, V, output) and MLPs performed per layer are proportional to the number of tokens, the cost of a single step is proportional to t, and summing over n steps gives 1+2+…+n ≈ n²/2 . With a cache, only a single new token is projected and fed into the MLP at each step, resulting in n for n steps.

Attention score calculation remains in both methods. Even with a cache, the Q of the new token must be compared against all preceding Ks, costing t per step (summing to n²/2 over n steps). Without a cache, even this costs t² per step, causing the sum to grow to n³/3. As long as the context is not very long, projections and MLPs make up the majority of computation, so the practically felt difference is "t versus 1 per step".

3. Trying It Yourself: numpy Toy Transformer

It is easy to describe but hard to intuitively grasp, so I built a small transformer in numpy with weights filled with random numbers to measure both methods. Since it is not a trained model, the output tokens have no meaning, but the computational shape (projection, attention, MLP, normalization) is identical to the real thing.

• Model: 2 layers, model dimension 128, 8 heads (head dimension 16), MLP 512, vocabulary 512, float32
• Environment: Laptop CPU, Python 3.9, numpy 2.0.2, single process
• Method: Greedy decoding to the end from a random prompt of 32 tokens. Run under the same conditions three times and take the median. The computational workload of matrix multiplications (counting multiplications and additions as 2) was measured directly by the code.
• Code and raw data: Repository docs/experiments/2026-10-13-numpy-kv-cache-toy/(toy_kv_cache.py, result-20261013.txt)

The core of the cached version is just a few lines. The K and V of the current token are written to the end of a pre-allocated array, and attention looks at everything accumulated so far (reshape separating by heads was simplified).

k = mm(h, W["k"])  # 새 K
v = mm(h, W["v"])  # 새 V
n = cache["n"]
cache["k"][:, n:n+T] = k  # 끝에 붙임
cache["v"][:, n:n+T] = v
K = cache["k"][:, :n+T]  # 지난 것 전부
V = cache["v"][:, :n+T]
a = attend(q, K, V)

Result 1. Outputs are identical, but workload and time differ significantly.

Workload (GFLOPs, counted by code):

Time (seconds, median of three runs):

• For all three lengths, the tokens generated by both methods were identical to the end, and the maximum difference in logits was 1.5×10⁻⁶, which is at the level of float32 rounding. The cache is not an approximation; it is simply not recomputing the same calculation.
• Every time the length was doubled, the workload for the uncached version increased by about 4.6 to 4.8 times (n² mixed with a bit of n³ from attention), while the cached version increased by about 2.2 times.
• The reason the time ratio is smaller than the workload ratio is that a single step in the cached version involves very small matrix multiplications, causing Python invocation overhead to play a large role. For length 128, the total time is under 0.1 seconds, so fluctuations are also high (it was 4.5x in a short check run).

Result 2. Without a cache, each step becomes slower in proportion to the context. Looking at the median time per step across 64-token intervals in the 512-token run, the uncached version increased from 1.25 ms to 35.1 ms, while the cached version increased only slightly from 0.43 ms to 0.60 ms. The slight increase even with a cache is due to the attention score calculation mentioned in Section 2 (t per step).

Result 3. The size of the cache array matches the formula down to the byte. After prefilling 1,024 tokens, we added the nbytes .

Query heads are 8 for all three, and the formula value is 2 * layers (2) * KV heads * head dimension (16) * tokens (1,024) * 4 bytes.

For all three methods, the final logit using the cache was identical to the value calculated from scratch without a cache (tolerance 10⁻³).

4. The Cost of the Cache: Memory

The cache trades computation for memory. Since the KV left behind by a single token consists of one set of K and V per layer, it is as follows:

KV Bytes/Token = 2 * Number of Layers * Number of KV Heads * Head Dimension * Datatype Bytes

Whether this formula matches actual servers was verified in another series. For Qwen3-1.7B (28 layers, 8 KV heads, head dimension 128, bf16), the formula yields 114,688 bytes per token, and dividing the KV cache memory in the vLLM server logs (2.36 GiB) by the number of tokens (22,048) gave approximately 114,900 bytes, matching within 0.2% (8GB-class GPU, vLLM 0.31.0, measured). Storing KV in 8-bit (fp8) allowed 41,920 tokens to fit in the same memory, nearly doubling it precisely.

Plugging this into well-known public models yields the following. Layer and head counts were verified from official materials, and sizes were calculated assuming KV is stored in bf16 (2 bytes). The models below all have a head dimension of 128. "32K" is the KV for a single 32,768-token request.

The number of query heads is 12 for Qwen2.5-1.5B, 28 for Qwen2.5-7B, 32 for Llama 3.1 8B, Mistral-7B, and Qwen3-8B, 64 for 70B, and 128 for 405B. Having fewer KV heads than query heads is the GQA discussed in Section 5.

• Llama 3.1 was verified from the model configuration table in the Llama 3 paper (8B, 70B, and 405B all have 8 KV heads) and configuration values in Meta's official repository. Hugging Face's Llama config could not be opened as it required a login, and the head dimension of 128 was calculated as model dimension ÷ number of heads. Qwen and Mistral were verified from public config.json .
• Llama 3.1 supports a 128K context. Filling all 128K tokens in 70B results in 40GiB of KV alone (calculated). Alongside a model whose weights are about 140GB in bf16, just a few long requests quickly consume GPU memory.
• DeepSeek-V2 stores compressed latent vectors (512 elements per layer) and positional keys (64 elements) instead of K and V. The paper counts KV per token as the number of elements (512 + 64) * 60 layers = 34,560. 67.5 KiB is the calculated value obtained by assuming these are stored in bf16. If the same head configuration (128 heads, head dimension 128) were used with MHA, it would be 1,966,080 elements per token, or about 1/57th of that (calculated).

5. Methods to Reduce Size: MHA → GQA → MQA → MLA

What can be reduced in the formula are the number of KV heads (or whatever replaces them) and the bytes. The number of layers and head dimension are directly tied to the model's capabilities and cannot be arbitrarily reduced.

• MHA(Multi-Head Attention): Separate K and V are maintained for each query head. This is the method from the original Transformer (2017).
• MQA(Multi-Query Attention, Shazeer 2019): All query heads share a single set of K and V. In the paper's translation model experiments (approx. 200M parameters, TPUv2), decoder time per output token dropped from 46 µs to 3.8 µs, while BLEU dropped slightly from 27.7 to 27.5 (greedy).
• GQA(Grouped-Query, Ainslie et al., 2023): It is a middle ground between the two. Query heads are grouped into several sets, and each group shares a single set of K and V. It was shown that a model already trained with MHA can be adapted with only 5% of its original training compute, and in the T5-XXL experiments, GQA-8 achieved an average score of 47.1 (MHA 47.2, MQA 46.6) in 0.28 seconds per sample (MHA 1.51s, MQA 0.24s). This is the approach used by the Llama 3 family (8 KV heads).
• MLA(DeepSeek-V2, 2024): Instead of reducing the number of heads, K and V are compressed into small latent vectors for storage and decompressed when needed. The paper reports that compared to DeepSeek 67B, it reduced the KV cache by 93.3% and increased the maximum generation throughput by 5.76x (conditions including a single node with eight H800 GPUs and FP8 weights/approx. 6-bit KV quantization during deployment). The exact calculation basis for the 93.3% figure was not found in the main text (unverified).
• Reducing bytes: Setting KV to 8-bit halves the size. In the vLLM measurements above, fp8 KV increased the token capacity by 1.9x. The impact on quality must be measured separately for each model and task.

Why go to such lengths to reduce it? Section 6 holds the answer.

6. Prefill and Decode: Two Phases with Different Characteristics

A single request goes through two phases.

1. Prefill(prefill): The entire prompt is fed at once to generate K and V for all tokens and write them to the cache. The first token is produced here. This determines the Time to First Token (TTFT).
2. Decode(decode): Tokens are generated one by one thereafter. This determines the Inter-Token Latency (ITL) and Time Per Output Token (TPOT).

Both use the same model, but they manifest differently on hardware.

• Prefill is compute-bound. Weights are read once and applied simultaneously to thousands of prompt tokens. Because there are many computations per byte read, the GPU's compute units are kept busy.
• Decode is memory bandwidth-bound. To generate a single token, the entire set of weights and all KV caches for that request must be read from memory, but the computation performed with them is only for a single token. Since bf16 weights are 2 bytes per parameter and perform about 2 FLOPs per parameter for a single token, decoding a single request involves about 1 FLOP per byte read (calculated). Modern datacenter GPUs can perform hundreds of FLOPs while reading a single byte, so the compute units mostly sit idle.

The difference was also visible in a toy model (with cache, median of three runs).

Total prefill times were 1.16ms for 64 tokens, 8.76ms for 256 tokens, and 146.9ms for 1,024 tokens.

Decoding a single token took 6 to 24 times longer than the per-token prefill time. Because it uses NumPy on CPU, Python call overhead is mixed in, and for the 1,024-token prefill, the quadratic attention term grows larger, increasing the per-token cost. Therefore, rather than the exact multiplier, you should look at the general trend that "batching computations together is far cheaper per token."

On GPUs, this difference is even more pronounced. In actual measurements from a different setup (8GB-class GPU, Qwen3-1.7B, vLLM), the input processing speed was about 8,200 tokens/sec, while decoding a single request yielded an inter-token latency of 15ms (approx. 66 tokens/sec). There is over a 120-fold difference per token.

If decoding is bound by memory, there is only one way to increase throughput: decoding multiple requests together whenever weights are read, which means increasing the batch size. In the same measurements, increasing concurrent requests from 1 to 8 raised throughput from 66 to 383 tokens/sec (5.8x), and to 831 tokens/sec at 32 concurrent requests. However, every request in the batch must have its own KV cache stored in the GPU memory. With an input of 512 + output of 128 tokens, a single request takes 640 tokens, and the GPU's KV capacity (22,048 tokens) can accommodate about 34 of them. When 64 concurrent requests were sent, throughput did not increase, and the time to first token spiked to 5.7 seconds. The upper limit of throughput is determined by the KV memory.

7. Summary: Questions This Series Will Follow

Titty's note. No referee in a table tennis match recounts the score from the very first serve every time. They write it down on the scoreboard and add one point at a time. The KV cache is precisely that scoreboard. However, if there are hundreds of arenas, you start running out of places to put the scoreboards.

References

• Vaswani et al., Attention Is All You Need: https://arxiv.org/abs/1706.03762
• Shazeer, Fast Transformer Decoding: One Write-Head is All You Need (MQA): https://arxiv.org/abs/1911.02150 (Tables 1 and 2)
• Ainslie et al., GQA: https://arxiv.org/abs/2305.13245 (v3, Section 3, Table 1)
• DeepSeek-AI, DeepSeek-V2: https://arxiv.org/abs/2405.04434 (v5, Abstract, Section 2.1 Table 1, Section 3.2.3)
• Llama 3 Paper Model Architecture Table: https://arxiv.org/abs/2407.21783 (Section 3.2 Table 3), Meta Configuration Values: https://github.com/meta-llama/llama-models (models/sku_list.py)
• Public Config: https://huggingface.co/Qwen/Qwen2.5-7B-Instruct/raw/main/config.json, https://huggingface.co/Qwen/Qwen3-8B/raw/main/config.json, https://huggingface.co/mistralai/Mistral-7B-v0.1/raw/main/config.json, https://huggingface.co/Qwen/Qwen2.5-1.5B-Instruct/raw/main/config.json (All accessed on 2026-10-13)
• Toy model code and raw data: Repository docs/experiments/2026-10-13-numpy-kv-cache-toy/
• GPU measurement citations: Same site, "Toss ML/AI Infra Preparation" Part 14 (vLLM load, KV capacity, prefix caching, chunking)