D4Hard★ Core Essential · Industrial BedrockPart D · Attention Mechanisms & Transformer Blocks

KV Cache Autoregressive Generation Loop

⚡Flashcard Drill➔

Cache past Keys and Values so decoding steps attend in O(t) incrementally instead of recomputing O(t^2) history.

⏱️ Time: Decode 单步计算复杂度仅 O(S * D),极大加速生成速度
💾 Space: O(B * H * S * D) 随序列长度线性持久驻留显存
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
class KVCacheManager:
def __init__(self, max_seq_len: int, num_heads: int, head_dim: int):
self.max_seq_len =
self.num_heads = num_heads
self.head_dim = head_dim
self.current_len = 0
# 预分配连续显存 Buffer: (B, H, max_S, D_k)
self.k_cache = None
self.v_cache = None
def step(self, q_t: np.ndarray, k_t: np.ndarray, v_t: np.ndarray) -> np.ndarray:
"""
单步自回归更新。
参数:
q_t: (B, H, 1, D_k) 单个当前 Token 的 Query
k_t: (B, H, 1, D_k) 当前 Token 的 Key
v_t: (B, H, 1, D_k) 当前 Token 的 Value
返回:
out_t: (B, H, 1, D_k)
"""
B = q_t.shape[0]
if self.k_cache is None:
self.k_cache = np.zeros((B, self.num_heads, self.max_seq_len, self.head_dim), dtype=q_t.dtype)
self.v_cache = np.zeros((B, self.num_heads, self.max_seq_len, self.head_dim), dtype=v_t.dtype)
pos = self.current_len
assert pos < self.max_seq_len, "超出最大序列缓存上限"
# 1. 写入当前时间步数据
self.k_cache[:, :, pos:pos+1, :] = k_t
self.v_cache[:, :, pos:pos+1, :] = v_t
self.current_len += 1
# 2. 截取有效历史: (B, H, current_len, D_k)
k_valid = self.k_cache[:, :, :self.current_len, :]
v_valid = self.v_cache[:, :, :self.current_len, :]
# 3. 单步点积注意力: (B, H, 1, D_k) @ (B, H, D_k, current_len) -> (B, H, 1, current_len)
scores = np.matmul(q_t, k_valid.swapaxes(-1, -2)) / np.sqrt(self.head_dim)
# 注意:此处 q_t 为最新 Token,它能看到所有已存在的历史,因此无需再加因果掩码!
scores_max = np.max(scores, axis=-1, keepdims=True)
exp_s = np.exp(scores - scores_max)
attn_probs = exp_s / np.sum(exp_s, axis=-1, keepdims=True)
# 4. 加权聚合: (B, H, 1, current_len) @ (B, H, current_len, D_k) -> (B, H, 1, D_k)
return
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How does PagedAttention solve memory fragmentation in naive KV caching?
Next: Cross-Attention Mechanism →
💡

Core Mental Anchor / Mnemonic

Prefill full prompt once; decode one token per step by appending k_t, v_t and attending to cached history.

📐 Mathematical Derivation & Core Formula

Knew=Concat(Kpast,Kt),Vnew=Concat(Vpast,Vt),Qt∈RB×1×DK_{\text{new}} = \mathrm{Concat}(K_{\text{past}}, K_t), \quad V_{\text{new}} = \mathrm{Concat}(V_{\text{past}}, V_t), \quad Q_t \in \mathbb{R}^{B \times 1 \times D}
### Avoiding Quadratic Recomputation via Incremental Caching
Recomputing full attention from tokens 1…t1 \dots t at every decoding step wastes O(N2)O(N^2) work because keys and values of past tokens never change under causal masking.
KV Cache two-phase flow:
1. Prefill: Process the entire prompt of length SS in parallel, populating KcacheK_{\text{cache}} and VcacheV_{\text{cache}};
2. Decode: Process only the newest token (S=1S=1) to compute qt,kt,vtq_t, k_t, v_t, append kt,vtk_t, v_t to the cache, and attend qtq_t against Kcache,VcacheK_{\text{cache}}, V_{\text{cache}} in O(t)O(t) per step instead of O(t2)O(t^2).

🔄 Tensor Dimensions & Shape Flow

step t: q_t, k_t, v_t (B, H, 1, D_k) -> write cache[pos] -> slice valid [:current_len] -> attend -> out (B, H, 1, D_k)

🛡️ Numerical Stability & Pitfalls Checklist

  • Single-token decode queries only attend to prior cached keys, so an explicit triu mask matrix is unnecessary.
  • Serving engines (like vLLM) pair KV cache with PagedAttention blocks to minimize memory fragmentation.

💻 Reference Code Implementation

import numpy as np

class KVCacheManager:
    def __init__(self, max_seq_len: int, num_heads: int, head_dim: int):
        self.max_seq_len = max_seq_len
        self.num_heads = num_heads
        self.head_dim = head_dim
        self.current_len = 0
        
        # 预分配连续显存 Buffer: (B, H, max_S, D_k)
        self.k_cache = None
        self.v_cache = None
        
    def step(self, q_t: np.ndarray, k_t: np.ndarray, v_t: np.ndarray) -> np.ndarray:
        """
        单步自回归更新。
        参数:
            q_t: (B, H, 1, D_k) 单个当前 Token 的 Query
            k_t: (B, H, 1, D_k) 当前 Token 的 Key
            v_t: (B, H, 1, D_k) 当前 Token 的 Value
        返回:
            out_t: (B, H, 1, D_k)
        """
        B = q_t.shape[0]
        if self.k_cache is None:
            self.k_cache = np.zeros((B, self.num_heads, self.max_seq_len, self.head_dim), dtype=q_t.dtype)
            self.v_cache = np.zeros((B, self.num_heads, self.max_seq_len, self.head_dim), dtype=v_t.dtype)
            
        pos = self.current_len
        assert pos < self.max_seq_len, "超出最大序列缓存上限"
        
        # 1. 写入当前时间步数据
        self.k_cache[:, :, pos:pos+1, :] = k_t
        self.v_cache[:, :, pos:pos+1, :] = v_t
        self.current_len += 1
        
        # 2. 截取有效历史: (B, H, current_len, D_k)
        k_valid = self.k_cache[:, :, :self.current_len, :]
        v_valid = self.v_cache[:, :, :self.current_len, :]
        
        # 3. 单步点积注意力: (B, H, 1, D_k) @ (B, H, D_k, current_len) -> (B, H, 1, current_len)
        scores = np.matmul(q_t, k_valid.swapaxes(-1, -2)) / np.sqrt(self.head_dim)
        
        # 注意:此处 q_t 为最新 Token,它能看到所有已存在的历史,因此无需再加因果掩码!
        scores_max = np.max(scores, axis=-1, keepdims=True)
        exp_s = np.exp(scores - scores_max)
        attn_probs = exp_s / np.sum(exp_s, axis=-1, keepdims=True)
        
        # 4. 加权聚合: (B, H, 1, current_len) @ (B, H, current_len, D_k) -> (B, H, 1, D_k)
        return np.matmul(attn_probs, v_valid)

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

import numpy as np
kv_mgr = KVCacheManager(max_seq_len=10, num_heads=2, head_dim=4)
B = 1
# 模拟自回归生成 3 个 Token
for t in range(3):
    q_t = np.random.randn(B, 2, 1, 4)
    k_t = np.random.randn(B, 2, 1, 4)
    v_t = np.random.randn(B, 2, 1, 4)
    out_t = kv_mgr.step(q_t, k_t, v_t)
    assert out_t.shape == (B, 2, 1, 4)
assert kv_mgr.current_len == 3
print("✓ KV Cache 增量自回归推理自测通过")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:How does PagedAttention solve memory fragmentation in naive KV caching?
Contiguous pre-allocation reserves max sequence length per request, causing severe internal and external fragmentation. PagedAttention splits the KV cache into fixed-size blocks mapped dynamically via a virtual-to-physical block table, reducing wasted KV memory substantially.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Grouped-Query & Multi-Query AttentionBack to Part D & All 105Next: Cross-Attention Mechanism →