Back to series
· 10 min read

How KV Cache Works: How Large Language Models Cache Past Computation Results


1. Why Do Large Models Need KV Cache?

Large language models typically generate text in an autoregressive manner.

Each time a new Token is generated, the next Token must be predicted based on the preceding context.

Suppose the model needs to generate:

Input: Explain how Transformer works.
Output: Transformer is a neural network architecture...

The generation process of the model can be simplified as:

flowchart TB
    A["Input Prompt"] --> B["Model processes context"]
    B --> C["Predict next Token"]
    C --> D["Add Token to context"]
    D --> E{"Stop condition reached?"}
    E -->|"No"| B
    E -->|"Yes"| F["Output complete text"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style F fill:#E5F0E9,stroke:#83A995,color:#315D49

There is an obvious problem here:

Each time a Token is generated, the model needs to use the preceding context for computation. If the Key and Value of all historical Tokens are recalculated from scratch every time, a large amount of duplicate computation will occur.

For example:

Generation Step Current Context New Token
Step 1 A B C D E
Step 2 A B C D E F
Step 3 A B C D E F G
Step 4 A B C D E F G H

Without KV Cache:

  • Step 1 computes the K and V of A, B, C, and D.
  • Step 2 recomputes the K and V of A, B, C, D, and E.
  • Step 3 recomputes the K and V of A, B, C, D, E, and F.
  • Step 4 recomputes the K and V of A, B, C, D, E, F, and G.

As the context grows longer, the duplicate computation increases.

The core idea of KV Cache: historical K and V that have already been computed are not recalculated; they are saved and reused directly.

2. What Does KV Cache Cache?

To understand KV Cache, we first need to understand Q, K, and V in Self-Attention.

1. Computation of Q, K, and V

For the input hidden state X, the Attention layer computes through three different linear projection matrices:

Q=XW_Q
K=XW_K
V=XW_V

Where:

  • Q: Query, representing what information the current Token wants to query.
  • K: Key, representing what matching information each Token provides.
  • V: Value, representing the content representation that each Token actually provides.
  • W_Q,W_K,W_V: learnable linear projection matrices.

Standard Scaled Dot-Product Attention:

Attention(Q,K,V) = Softmax\left(\frac{QK^T}{\sqrt{d_k}}\right)V

Where:

  • QK^T: computes the matching score between Query and Key.
  • \sqrt{d_k}: scaling factor.
  • Softmax: converts scores into attention weights.
  • V: performs weighted aggregation according to the attention weights.

2. Why cache only K and V, and not Q?

This is the most critical design of KV Cache.

During autoregressive generation:

  • The K and V of historical Tokens have already been computed.
  • When a new Token arrives, only the Q, K, and V of the new Token need to be computed.
  • The Query of the current Token needs to match all historical Keys.
  • Historical Values can directly participate in weighted aggregation.

The Query of historical Tokens does not need to be reused in subsequent generation.

Therefore, during inference, K and V are usually cached, while Q is not.

Note that caching K and V does not mean Attention is no longer computed. For each newly generated Token, its Query still needs to be used with the historical Keys to compute attention scores, and a weighted aggregation still needs to be performed over the historical Values.

3. Storage Structure of KV Cache

KV Cache does not just store a single global copy of K and V.

In a Transformer, each layer has its own Attention module, so each layer produces its own independent K and V.

Suppose the model has 4 Transformer layers:

flowchart TB
    A["Input Token"] --> B["Transformer Layer 1"]
    B --> C["Transformer Layer 2"]
    C --> D["Transformer Layer 3"]
    D --> E["Transformer Layer 4"]

    B --> F["Layer 1 KV Cache"]
    C --> G["Layer 2 KV Cache"]
    D --> H["Layer 3 KV Cache"]
    E --> I["Layer 4 KV Cache"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#EAF3EC,stroke:#83A995,color:#315D49
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#EAF3EC,stroke:#83A995,color:#315D49
    style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style I fill:#DCEFE5,stroke:#4F8B70,color:#24563F

The KV Cache of each layer keeps growing throughout the generation process.

Logically, it can be represented as:

KVCache= \left\{ (K_1,V_1), (K_2,V_2), \ldots, (K_L,V_L) \right\}

Where:

  • L: number of Transformer layers.
  • K_l: Key cache of layer l.
  • V_l: Value cache of layer l.

This means that the GPU memory usage of KV Cache is closely related to factors such as the number of model layers, context length, number of KV Heads, and data precision.

III. The Complete Execution Mechanism of KV Cache

The lifecycle of KV Cache is mainly divided into two stages: Prefill and Decode.

1. Prefill: Building the KV Cache

The Prefill stage processes the full Prompt.

Suppose the input contains 5 Tokens:

Token 1: What
Token 2: is
Token 3: KV
Token 4: Cache
Token 5: ?

The model performs a forward pass over the entire input sequence.

In each layer:

  1. Compute Q, K, and V for all input Tokens.
  2. Perform Self-Attention with a causal mask.
  3. Complete the subsequent computations for that layer.
  4. Save the K and V for all input positions in this layer to the cache.

After Prefill is complete, each layer already has the K and V corresponding to these 5 Tokens.

flowchart TB
    A["Input complete Prompt"] --> B["Tokenizer"]
    B --> C["Embedding"]
    C --> D["Enter Transformer"]
    D --> E["Compute Q, K, V for all Tokens in current layer"]
    E --> F["Execute Causal Self-Attention"]
    F --> G["Save current layer K, V"]
    G --> H["Continue to subsequent Transformer layers"]
    H --> I["KV Cache for all layers established"]
    I --> J["LM Head predicts first output Token"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style C fill:#EAF3EC,stroke:#83A995,color:#315D49
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style H fill:#EAF3EC,stroke:#83A995,color:#315D49
    style I fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style J fill:#E5F0E9,stroke:#83A995,color:#315D49

Note: Although Prefill's causal attention restricts each position to accessing only itself and previous positions, all input positions can still be computed in parallel via matrix operations.

2. Decode: Read and append KV Cache

After Prefill is complete, the model starts generating output.

Suppose Prefill has processed 5 Tokens and established the corresponding cache.

The model first predicts the first output Token based on the hidden state of the last input position, for example works.

Then, the model uses the Token ID corresponding to works as the input for the next Decode round.

Execution process of the Decode stage:

  1. Input the current new Token.
  2. Compute Q, K, V for the current Token.
  3. Read the historical KV Cache of each layer.
  4. Compute attention scores using the current Q and historical K.
  5. Use attention weights to perform weighted aggregation of historical V.
  6. Append the current Token's K, V to the cache of the corresponding layer.
  7. Continue through subsequent layers to obtain the current hidden state.
  8. Predict the next Token through the LM Head.
flowchart TB
    A["Existing historical KV Cache"] --> B["Input current Token"]
    B --> C["Compute Q, K, V for current Token"]
    C --> D["Read historical K, V"]
    D --> E["Compute attention with current Q and historical K"]
    E --> F["Softmax-weighted aggregation of historical V"]
    F --> G["Append current K, V to cache"]
    G --> H["Complete Transformer forward computation"]
    H --> I["LM Head predicts next Token"]
    I --> J["Enter next Decode round"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style C fill:#EAF3EC,stroke:#83A995,color:#315D49
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style I fill:#EAF3EC,stroke:#83A995,color:#315D49
    style J fill:#E5F0E9,stroke:#83A995,color:#315D49

Pay special attention to the execution order here:

The current Token's K, V must participate in the attention computation for the current Token, and must also be written to the cache for use by subsequent Tokens.

In actual implementations, cache reading, concatenation or appending of the current K/V, and attention computation can be fused into efficient kernels; a separate memory concatenation operation is not necessarily performed.

3. A complete cache growth example

Suppose the Prompt has 4 Tokens:

Prompt: A B C D

After Prefill is complete:

KV Cache: A B C D

First generation:

Predicted Token: E

After E is selected and enters the next Decode round, the cache becomes:

KV Cache: A B C D E

Second generation:

Predicted Token: F

After F enters the next Decode round, the cache becomes:

KV Cache: A B C D E F

Cache growth process:

flowchart TB
    A["Prefill: A B C D"] --> B["KV Cache: A B C D"]
    B --> C["Generate E"]
    C --> D["KV Cache: A B C D E"]
    D --> E["Generate F"]
    E --> F["KV Cache: A B C D E F"]
    F --> G["Generate G"]
    G --> H["KV Cache: A B C D E F G"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style H fill:#E5F0E9,stroke:#83A995,color:#315D49

Strictly speaking, the Decode round that generates E uses the hidden state of the last input position from Prefill. E's K and V are usually computed and written to the cache only when E serves as the input for the next round.

Therefore, there is an execution-timing relationship between generating a token and writing the K and V corresponding to that token into the cache; it cannot be simply understood that once a token is sampled, its K and V computation has already been completed.

4. How Is the GPU Memory Usage of KV Cache Calculated?

KV Cache is a very important source of GPU memory overhead in large model inference.

Especially in long-context and high-concurrency scenarios, KV Cache may occupy a large amount of GPU memory.

1. KV Cache GPU Memory Calculation Formula

Define the following parameters:

  • L: Number of Transformer layers.
  • B: Batch Size.
  • T: Number of cached tokens.
  • H_{kv}: Number of KV Heads.
  • D: Dimension of each KV Head.
  • P: Number of bytes occupied by each element.

Key and Value each require one cache, so:

M_{KV}=2LBT H_{kv}DP

where the coefficient 2 represents the K and V parts.

If FP16 or BF16 is used:

P=2\ Bytes

If FP32 is used:

P=4\ Bytes

If an 8-bit cache format is used:

P\approx1\ Byte

Actual quantized caches may also include scaling factors, zero points, and alignment overhead, so the final GPU memory cannot be estimated based only on data element size.

2. Concrete Calculation Example

Suppose a model has the following configuration:

Parameter Value
Number of Transformer layers 32
Batch Size 1
Context length 8192
Number of KV Heads 32
Head Dimension 128
Data type FP16
Size per element 2 Bytes

Substitute into the formula:

M_{KV} = 2\times32\times1\times8192\times32\times128\times2
M_{KV}=4,294,967,296\ Bytes

Conversion:

M_{KV}=4\ GiB

In other words, a single request with a context length of 8192 tokens already requires about 4 GiB of KV Cache GPU memory.

If the batch size increases to 8:

M_{KV}=4\times8=32\ GiB

And this does not yet account for model weights, activations, temporary workspaces, and other runtime overhead.

3. What factors affect KV Cache size?

KV Cache memory usage scales approximately linearly with the following factors:

Factor Impact on memory usage
Number of Transformer layers More layers, larger cache
Batch size More requests, larger cache
Context length More tokens, larger cache
Number of KV heads More KV heads, larger cache
Head dimension Larger dimension, larger cache
Data precision More bytes per element, larger cache

Therefore, KV Cache optimization usually centers on three directions:

  • Reducing the number of elements that must be cached.
  • Lowering the storage precision of each element.
  • Improving the efficiency of cache space allocation and reuse.

V. How MHA, GQA, and MQA Affect the KV Cache

Different attention architectures directly affect the size of the KV Cache.

1. MHA: Multi-Head Attention

In standard multi-head attention, Query, Key, and Value usually have the same number of heads.

For example:

  • Query heads: 32
  • Key heads: 32
  • Value heads: 32

Therefore:

H_{kv}=32

Each layer needs to store 32 sets of Keys and 32 sets of Values.

2. MQA: Multi-Query Attention

MQA is characterized by:

  • Query has multiple heads.
  • All Query heads share a single set of Keys.
  • All Query heads share a single set of Values.

For example:

  • Query heads: 32
  • Key heads: 1
  • Value heads: 1

Therefore:

H_{kv}=1

Compared with standard MHA, the KV Cache size can be reduced significantly.

3. GQA: Grouped-Query Attention

GQA sits between MHA and MQA.

Multiple Query heads share one set of KV heads.

For example:

  • Query heads: 32
  • KV heads: 8
  • Every 4 Query heads share one set of KV heads.

Therefore:

H_{kv}=8

4. Comparison of cache size across the three architectures

Assuming all other parameters are identical:

Architecture Query Head KV Head Relative KV Cache size
MHA 32 32 100%
GQA 32 8 25%
MQA 32 1 3.125%

This is because the size of the KV Cache is proportional to the number of KV heads.

flowchart TB
    A["Attention Architecture"] --> B["MHA"]
    A --> C["GQA"]
    A --> D["MQA"]

    B --> E["32 KV Head groups"]
    C --> F["8 KV Head groups"]
    D --> G["1 KV Head group"]

    E --> H["Larger KV Cache"]
    F --> I["Smaller KV Cache"]
    G --> J["Smallest KV Cache"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#EAF3EC,stroke:#83A995,color:#315D49
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style G fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style H fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
    style I fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style J fill:#E5F0E9,stroke:#83A995,color:#315D49

Note that MHA, GQA, and MQA differ not only in cache structure; they also change the model's attention projection structure and training method. You cannot directly use an already-trained standard MHA model as a GQA or MQA model without changing the model architecture.

6. Why Can KV Cache Improve Inference Speed?

1. Without KV Cache

Suppose the current context length is T.

When generating the next token, the model needs to reprocess the entire context and compute K, V for all historical positions.

In the next round, the context length becomes T+1, and K, V at historical positions are recomputed again.

If generating N tokens starting from a prompt of length S, then from the perspective of K, V projection computation alone, the number of repeatedly processed token positions is approximately:

S+(S+1)+\cdots+(S+N-1)

Expanding:

NS+\frac{N(N-1)}{2}

As the generation length increases, the repeated computation overhead becomes increasingly large.

2. With KV Cache

After enabling KV Cache:

  • Prefill computes the K, V of the prompt in one pass.
  • Decode computes only the K, V of the newly added token each time.
  • Historical K, V are read directly from the cache.

Therefore, K, V projection only needs to process:

S+N

token positions, instead of repeatedly processing the entire growing context.

This does not mean that the total Attention computation also becomes linear or constant.

Each new token still needs to compute attention with historical Keys and read historical Values.

For generating N tokens starting from length S, the incremental attention computation of standard full attention is still of the same order as:

O\left(Ld\left(NS+\frac{N(N+1)}{2}\right)\right)

The core benefit of KV Cache is avoiding recomputation of historical K, V, not eliminating the attention computation of new tokens over the historical context.

3. Comparison of the Two Modes

Comparison Dimension Without KV Cache With KV Cache
Historical K, V Recomputed every round Read directly
Q, K, V of the current Token Need computation Need computation
Historical Attention Reprocess the entire context Current Query reads historical K, V
Memory usage Lower cache requirements Requires additional cache memory
Computational redundancy Higher Significantly reduced
Long-text generation Higher computational overhead Usually more efficient

KV Cache trades additional memory for reduced repeated computation.

This is a typical space-for-time optimization.

7. Engineering Implementation and Management of KV Cache