Xinsong Feng (冯欣淞)

Blog / May 15, 2024

Some Thoughts on Attention Mechanisms and the KV-Cache

Some notes on attention mechanisms.

LLM / Notes

1 Fundamentals of the Attention Mechanism and KV-Cache

1.1 Self-Attention vs. Cross-Attention

  • Self-Attention: The Query QQ, Key KK, and Value VV matrices are all derived from the same input sequence. This structure enables each token to observe and integrate information from all other tokens within the sequence, effectively capturing internal semantic dependencies.
  • Cross-Attention: The QQ matrix originates from one sequence (typically the Decoder), while the KK and VV matrices originate from another (typically the Encoder). This mechanism allows a target sequence to “query” information from a source sequence. A classic example is machine translation: when generating a target word (acting as QQ), the model queries the source sentence (acting as KK and VV) to identify the most relevant context.

1.2 The Roles of QQ, KK, and VV

The interaction within the attention mechanism can be intuitively understood as an information retrieval process from an “archive”:

  • Key KK and Value VV - The Archive: These represent the deterministic, historical context. Specifically, KK acts as the label/index (determining who is important), while VV contains the actual content (determining what information to extract).
  • Query QQ - The Search Request: QQ encodes the current step’s intent. It matches against all available KK matrices to compute attention weights, subsequently retrieving the most relevant combination of VV matrices.

1.3 Autoregressive Generation and the KV-Cache

During inference, standard Transformers operate autoregressively. Generating the tt-th token requires computing its attention relationship with all preceding tt tokens. Without caching, the Attention computation is formulated as:

Attention(Qt,K1:t,V1:t)=softmax(QtK1:tTdk)V1:t\mathrm{Attention}(Q_t, K_{1:t}, V_{1:t}) = \mathrm{softmax}\left(\frac{Q_t K_{1:t}^T}{\sqrt{d_k}}\right) V_{1:t}

In this naive approach, to compute the output at position tt, the model must redundantly recompute the keys K1:t−1K_{1:t-1} and values V1:t−1V_{1:t-1} for all historical positions.

Since QQ drives the active generation while KK and VV provide static historical information, models store historical keys and values in the ​KV-Cache. Consequently, the memory capacity allocated for the KV-Cache directly dictates the maximum context window the model can retain.

1.4 Semantic Compression via Hidden States hth_t

Throughout the sequential generation pipeline:

  • The query QtQ_t used to predict the tt-th token is intrinsically derived from the output embedding of the (t−1)(t-1)-th token.
  • As the representation processes through the Transformer layers, the final layer’s output, hth_t, serves as the semantic compression (or summarization) of all sequential information spanning from position 11 to position tt.

‍

2 An Example to Understand the Generation Process

Suppose we have a simplified one-layer Transformer. Our target is to make the model autoregressively generate the sequence: “To be or not to be.”

Let us define the key notations and their corresponding dimensions. Let dd denote the model’s hidden dimension, and ∣V∣|V| denote the vocabulary size:

  • Input Representation xt∈R1×dx_t \in \mathbb{R}^{1 \times d}: The input vector at step tt, which is the sum of the current token embedding and the positional embedding.
  • Qt,Kt,Vt∈R1×dQ_t, K_t, V_t \in \mathbb{R}^{1 \times d}: Obtained by multiplying xtx_t with three respective weight matrices (WQ,WK,WV∈Rd×dW^Q, W^K, W^V \in \mathbb{R}^{d \times d}). Here, QtQ_t acts as the query, while KtK_t and VtV_t are the keys and values to be stored in the KV-Cache.
  • Context Vector zt∈R1×dz_t \in \mathbb{R}^{1 \times d}: The output of the Attention layer. It is a weighted sum of the historical values (V1:t∈Rt×dV_{1:t} \in \mathbb{R}^{t \times d}) and represents the features incorporating context information.
  • Hidden State ht∈R1×dh_t \in \mathbb{R}^{1 \times d}: The final output of the Transformer layer after passing ztz_t through a FFN/MLP. It represents the accumulated semantic information up to step tt.

Now, let’s examine how the model generates this sequence step-by-step.

Step 1: Initialization (Input: [BOS] →\rightarrow Predict: "To")

We feed a special token [BOS] (Begin of Sequence) to prompt the model to start generating.

  • Input Layer: Compute the token embedding for [BOS], add the positional encoding, and obtain x1∈R1×dx_1 \in \mathbb{R}^{1 \times d}.
  • Generate Q,K,VQ, K, V: Apply linear projections to x1x_1 to obtain Q1,K1,V1∈R1×dQ_1, K_1, V_1 \in \mathbb{R}^{1 \times d}.
  • Update KV-Cache: Store K1K_1 and V1V_1 into the cache. The current cache size for both K and V is 1×d1 \times d.
  • Attention z1z_1: Since there is no prior context, Q1Q_1 only attends to K1K_1 (the attention weight is trivially 11). Thus, z1=V1∈R1×dz_1 = V_1 \in \mathbb{R}^{1 \times d}.
  • Hidden State & Prediction: Pass z1z_1 through the MLP to obtain h1∈R1×dh_1 \in \mathbb{R}^{1 \times d}. Finally, h1h_1 is projected by the Language Modeling (LM) head (using a weight matrix WLM∈Rd×∣V∣W_{LM} \in \mathbb{R}^{d \times |V|}) to yield a logits vector ∈R1×∣V∣\in \mathbb{R}^{1 \times |V|}, predicting the highest-probability next token: "To".

Step 2: Incorporating Context (Input: "To" →\rightarrow Predict: "be")

In the autoregressive setting, the token predicted in the previous step ("To") becomes the input for the current step.

  • Input Layer: Compute the token embedding for "To", add the positional encoding for position 2, and obtain x2∈R1×dx_2 \in \mathbb{R}^{1 \times d}.
  • Generate Q,K,VQ, K, V: Apply the linear projections to x2x_2 to generate Q2,K2,V2∈R1×dQ_2, K_2, V_2 \in \mathbb{R}^{1 \times d}. Here, Q2Q_2 encodes the semantic query: “Given the context so far, what should follow the word ‘To’?”
  • Update KV-Cache: Append the newly computed (K2,V2)(K_2, V_2) row vectors to the existing KV-Cache. The cache now holds the accumulated history matrices K1:2,V1:2∈R2×dK_{1:2}, V_{1:2} \in \mathbb{R}^{2 \times d}.
  • Attention z2z_2: The query Q2∈R1×dQ_2 \in \mathbb{R}^{1 \times d} attends to all available keys in the cache K1:2∈R2×dK_{1:2} \in \mathbb{R}^{2 \times d} via dot-product, resulting in attention scores ∈R1×2\in \mathbb{R}^{1 \times 2}. After applying the softmax function to these scores, the resulting attention weights are used to compute a weighted sum of V1:2V_{1:2}. The output, z2∈R1×dz_2 \in \mathbb{R}^{1 \times d}, is no longer the isolated representation of "To"; it is now a context-aware feature vector.
  • Hidden State & Prediction: The context vector z2z_2 is processed by the MLP to yield the hidden state h2∈R1×dh_2 \in \mathbb{R}^{1 \times d}. Finally, the LM head maps h2h_2 to the vocabulary distribution ∈R1×∣V∣\in \mathbb{R}^{1 \times |V|}, predicting the highest-probability next token: "be".

The subsequent steps follow the exact same autoregressive pattern, appending new KK and VV matrices to the cache and generating the next sequence token until a termination condition is met.

If you have any thoughts you'd like to discuss, feel free to reach out: xsfeng@gatech.edu