D4Hard★ Core Essential · Industrial BedrockPart D · Attention Mechanisms & Transformer Blocks
KV Cache Autoregressive Generation Loop
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?
💡
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
### Avoiding Quadratic Recomputation via Incremental Caching
Recomputing full attention from tokens at every decoding step wastes 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 in parallel, populating and ;
2. Decode: Process only the newest token () to compute , append to the cache, and attend against in per step instead of .
Recomputing full attention from tokens at every decoding step wastes 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 in parallel, populating and ;
2. Decode: Process only the newest token () to compute , append to the cache, and attend against in per step instead of .
🔄 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.