11_Sliding Window Attention
Implement Sliding Window Attention — used in Longformer, Mistral, etc. for efficient long-context processing.
Each position can only attend to positions where (the window size).
Signature
def sliding_window_attention(Q, K, V, window_size):
# Q, K, V: (batch, seq, d) → output: (batch, seq, d_v)
# window_size: int — position i attends to [i-w, i+w]
Rules
- Do NOT use sparse attention libraries
- Mask positions outside the window with
-inf window_size=0: only self — output should equal Vwindow_size >= seq_len: equivalent to full attention
import torch
import math
# ✏️ YOUR IMPLEMENTATION HERE
def sliding_window_attention(Q, K, V, window_size):
b, s, d = Q.shape
score = Q @ K.transpose(-1,-2) / math.sqrt(d)
i = torch.arange(s)[:,None]
j = torch.arange(s)[None,:]
mask = torch.abs(i - j) <= window_size
score = score.masked_fill(~mask, float('-inf'))
return torch.softmax(score, dim = -1) @ V滑动窗口注意力就是在相关性得分矩阵中去除远距离项。mask内容为-inf的原因是后面紧跟着softmax。
但是这么写其实没有节省计算
真正节省计算需要软硬件实现跳块,可以实现S/(2*w+1)的节省比例
12_Linear Self-Attention
Implement Linear Attention — O(S·D²) instead of O(S²·D), enabling efficient long-sequence processing.
Replace softmax with a kernel feature map :
\text{LinearAttn}(Q,K,V) = \frac{\phi(Q) \left(\phi(K)^T V\right)}{\phi(Q) \cdot \sum \phi(K)}Feature map
Use (ensures non-negative features).
Signature¶
def linear_attention(Q, K, V):
# Q: (B, S, D_k), K: (B, S, D_k), V: (B, S, D_v)
# Returns: (B, S, D_v)
Key insight
Instead of computing the attention matrix, compute first (a matrix), then multiply by .
Rules
- Must use a feature map (NOT softmax)
- Must be O(S·D²) — should run fast on long sequences
- You may use
F.elu
# ✏️ YOUR IMPLEMENTATION HERE
def linear_attention(Q, K, V):
def phi(X):
return F.elu(X) + 1
phi_Q = phi(Q) #(B,S,D)
phi_K = phi(K) #(B,S,D)
A = phi_K.transpose(-1,-2) @ V #(B,D,D)
numerator = phi_Q @ A #(B,S,D)
B = torch.sum(phi_K, dim = -2) #(B,D)
denom = phi_Q @ B.unsqueeze(-1) #(B,S,1)
return numerator / (phi_Q @ torch.sum(phi_K, dim = -2).unsqueeze(-1))理解线性注意力我们需要先搞明白softmax的不可拆性质
核 k(a, b) 能拆 ⟺ 存在特征映射 φ,使得:
也就是先单独提取特征再直接点积比对,就叫可拆
对于softmax,我们的权重是一个,在数学上不能拆成两个函数的点积
elu(x) =
\begin{cases}
a(e^x-1), & x \leqslant 0 \\
x, & x >0 \\
\end{cases}a 限制了elu的下探深度,为了保证注意力得分恒正,a需要小于等于1
对于elu(default: a=1),我们的权重是
k(a,b) = \phi(a) \cdot \phi(b)^T = elu(a)elu(b)^T + elu(a)\cdot 1^T + 1\cdot elu(b)^T + 1\cdot 1^T \\
k_{i,j} = \sum_m ELU(a_{i,m})ELU(b_{j,m}) + \sum_m ELU(a_{i,m}) +\sum_m ELU(b_{j,m}) + d所有矩阵形状全是[B,S,S],重点是这满足结合律
对于softmax
O= softmax(Q\cdot K^T) \cdot V
\\
(Q \cdot K^T)_{i,j} = \sum Q_{i,m} K_{j,m} = Q_i K_j
\\
softmax(Q\cdot K^T)_{i,j} = \frac{e^{Q_i K_j}}{\sum_k e^{Q_i K_k}}
\\
O_i= \sum_j \frac{e^{Q_i K_j} }{\sum_k e^{Q_i K_k}}V_j假如说有一个函数满足
e^{Q_i K_j} = \phi(Q_i) \cdot \phi(K_j)则分子
\sum_j e^{Q_i K_j} V_j = \sum_j \phi(Q_i)\phi(K_j) V_j = \sum_j \sum_m \phi(Q_i)_m\phi(K_j)_m V_j\\
=\sum_m \phi(Q_i)_m \sum_j \phi(K_j)_m V_j \\
= \phi(Q_i) \cdot (\phi(K_j) \otimes V_j )可惜没有这样的函数。
13_GPT-2
Implement a full GPT-2 style Transformer block — combining everything you’ve learned.
Architecture (Pre-Norm)
x = x + causal_self_attention(ln1(x))
x = x + mlp(ln2(x))
Signature
class GPT2Block(nn.Module):
def __init__(self, d_model: int, num_heads: int): ...
def forward(self, x: torch.Tensor) -> torch.Tensor: ...
Requirements
- Inherit from
nn.Module self.ln1,self.ln2:nn.LayerNorm(d_model)self.W_q,self.W_k,self.W_v,self.W_o:nn.Linearfor attentionself.mlp:nn.Sequential(Linear(d, 4d), GELU(), Linear(4d, d))- Attention must be causal (mask future positions)
- Pre-norm architecture (LayerNorm before attention and MLP)
- Residual connections around both attention and MLP
import torch
import torch.nn as nn
import math
# ✏️ YOUR IMPLEMENTATION HERE
class GPT2Block(nn.Module):
def __init__(self, d_model, num_heads):
super().__init__()
self.ln1 = nn.LayerNorm(d_model)
self.ln2 = nn.LayerNorm(d_model)
self.num_heads = num_heads
self.W_q = nn.Linear(d_model, d_model)
self.W_k = nn.Linear(d_model, d_model)
self.W_v = nn.Linear(d_model, d_model)
self.W_o = nn.Linear(d_model, d_model)
self.mlp = nn.Sequential(nn.Linear(d_model, 4*d_model), nn.GELU(), nn.Linear(4*d_model, d_model))
def forward(self, x):
B,S,D = x.shape
d_k = D // self.num_heads
h = self.ln1(x)
Q = self.W_q(h).view(B,S, self.num_heads, d_k).transpose(1,2)
K = self.W_k(h).view(B,S, self.num_heads, d_k).transpose(1,2)
V = self.W_v(h).view(B,S, self.num_heads, d_k).transpose(1,2)
score = Q @ K.transpose(-1,-2) / math.sqrt(d_k)
mask = torch.triu(torch.ones_like(score ,dtype = torch.bool), diagonal = 1)
score = score.masked_fill(mask, float('-inf'))
atten = torch.softmax(score, dim=-1) @ V
x = x + self.W_o(atten.transpose(1,2).contiguous().view(B,S,D))
x = x + self.mlp(self.ln2(x))
return x14_KV Cache Attention
Implement multi-head attention with KV caching for efficient autoregressive generation.
During LLM inference, recomputing all key/value projections at every step is wasteful. A KV cache stores previously computed K and V tensors so only the new token(s) need projection.
Signature
class KVCacheAttention(nn.Module):
def __init__(self, d_model: int, num_heads: int): ...
def forward(self, x: torch.Tensor, cache=None) -> tuple[torch.Tensor, tuple]:
# x: (B, S_new, D) — new tokens
# cache: None or (K_past, V_past) each (B, num_heads, S_past, d_k)
# Returns: (output, (K_all, V_all))
Requirements
- Inherit from
nn.Module self.W_q,self.W_k,self.W_v,self.W_o:nn.Linearprojections- When
cache=None(prefill): apply causal mask, return all K/V as cache - When
cacheprovided (decode): concat new K/V with cached, no causal mask needed for single-token decode - Incremental decode must produce identical results to full forward pass
Key Idea
Prefill: [t0 t1 t2 t3] → full causal attention → cache = (K_{0:3}, V_{0:3})
Decode: [t4] → Q=t4, K/V=cache+t4 → cache = (K_{0:4}, V_{0:4})
Decode: [t5] → Q=t5, K/V=cache+t5 → cache = (K_{0:5}, V_{0:5})
import torch
import torch.nn as nn
import math
# ✏️ YOUR IMPLEMENTATION HERE
class KVCacheAttention(nn.Module):
def __init__(self, d_model, num_heads):
super().__init__()
self.d_model = d_model
self.num_heads = num_heads
# Initialize W_q, W_k, W_v, W_o
self.d_k = d_model // num_heads
self.W_q = nn.Linear(d_model, d_model)
self.W_k = nn.Linear(d_model, d_model)
self.W_v = nn.Linear(d_model, d_model)
self.W_o = nn.Linear(d_model, d_model)
def forward(self, x, cache=None):
B, S, D = x.shape
# 2. Reshape to multi-head: (B, num_heads, S, d_k)
# 1. Project Q, K, V from x
Q = self.W_q(x).view(B, S, self.num_heads, self.d_k).transpose(1,2)
K_new = self.W_k(x).view(B, S, self.num_heads, self.d_k).transpose(1,2)
V_new = self.W_v(x).view(B, S, self.num_heads, self.d_k).transpose(1,2)
# 3. If cache exists, concat new K/V with cached K/V
s_cache = 0
if cache is not None:
K_prev, V_prev = cache
_, _, s_cache, _ = K_prev.shape
K_all = torch.cat([K_prev, K_new], dim = 2)
V_all = torch.cat([V_prev, V_new], dim = 2)
else:
K_all, V_all = K_new, V_new
# 4. Compute attention (causal mask needed during prefill)
score = Q @ K_all.transpose(-1,-2) / math.sqrt(self.d_k)
if S > 1:
mask = torch.triu(torch.ones_like(score, dtype = torch.bool ), diagonal = s_cache+1)
score = score.masked_fill(mask, float('-inf'))
# 5. Return (output, (K_all, V_all))
atten = torch.softmax(score, dim = -1) @ V_all
out = self.W_o(atten.transpose(1,2).contiguous().view(B, S, D))
return out, (K_all, V_all)15_SwiGLU MLP
Implement the SwiGLU MLP (feed-forward network) used in modern LLMs like LLaMA.
where
Signature
class SwiGLUMLP(nn.Module):
def __init__(self, d_model: int, d_ff: int): ...
def forward(self, x: torch.Tensor) -> torch.Tensor: ...
Requirements
- Inherit from
nn.Module self.gate_proj:nn.Linear(d_model, d_ff)self.up_proj:nn.Linear(d_model, d_ff)self.down_proj:nn.Linear(d_ff, d_model)- Activation: SiLU (a.k.a. Swish) —
F.siluor implement asx * torch.sigmoid(x)
Why SwiGLU?
Unlike the classic Linear → ReLU/GELU → Linear FFN, SwiGLU uses a gating mechanism: the gate projection controls information flow, while the up projection provides the content. This consistently outperforms standard FFNs in practice (PaLM, LLaMA, Mistral all use it).
import torch
import torch.nn as nn
import torch.nn.functional as F
# ✏️ YOUR IMPLEMENTATION HERE
class SwiGLUMLP(nn.Module):
def __init__(self, d_model, d_ff):
super().__init__()
# Initialize gate_proj, up_proj, down_proj
self.gate_proj = nn.Linear(d_model, d_ff)
self.up_proj = nn.Linear(d_model, d_ff)
self.down_proj = nn.Linear(d_ff, d_model)
def forward(self, x):
# down_proj(silu(gate_proj(x)) * up_proj(x))
return self.down_proj(F.silu(self.gate_proj(x)) * self.up_proj(x))16_Cross-Entropy Loss
Implement cross-entropy loss from scratch.
\text{CE}(x, y) = -\log\frac{e^{x_y}}{\sum_j e^{x_j}}Signature¶
def cross_entropy_loss(logits: Tensor, targets: Tensor) -> Tensor:
# logits: (B, C) float, targets: (B,) long indices
# Returns: scalar loss (mean over batch)
Rules
- Do NOT use
F.cross_entropyornn.CrossEntropyLoss - Must be numerically stable (use logsumexp trick)
import torch
# ✏️ YOUR IMPLEMENTATION HERE
def cross_entropy_loss(logits, targets):
B = logits.shape[0]
m = logits.max(dim = -1, keepdim = True).values
log_probs = logits - m - torch.log(torch.exp(logits - m).sum(dim = -1, keepdim = True))
return -log_probs[torch.arange(B), targets].mean()
log_probs的形状为(B, C), -log_probs[torch.arange(B), targets] 取出了每个batch的独热正确答案的交叉熵
17_Implement Dropout
Implement Dropout regularization from scratch.
Signature
class MyDropout(nn.Module):
def __init__(self, p: float = 0.5): ...
def forward(self, x: Tensor) -> Tensor: ...
Rules
- During training: zero each element with probability
p, scale remaining by1/(1-p) - During eval: return input unchanged (identity)
- Do NOT use
nn.DropoutorF.dropout
import torch
import torch.nn as nn
# ✏️ YOUR IMPLEMENTATION HERE
class MyDropout(nn.Module):
def __init__(self, p=0.5):
super().__init__()
self.p = p
def forward(self, x):
if self.training:
mask = torch.rand_like(x) < self.p
x = x.masked_fill(mask, float(0)) / (1-self.p)
return x18_Embedding Layer
Implement an embedding lookup table from scratch.
Signature
class MyEmbedding(nn.Module):
def __init__(self, num_embeddings: int, embedding_dim: int): ...
def forward(self, indices: Tensor) -> Tensor: ...
Rules
self.weight:nn.Parameterof shape(num_embeddings, embedding_dim)- Forward: index into weight matrix —
weight[indices] - Do NOT use
nn.Embedding
import torch
import torch.nn as nn
# ✏️ YOUR IMPLEMENTATION HERE
class MyEmbedding(nn.Module):
def __init__(self, num_embeddings, embedding_dim):
super().__init__()
self.weight = nn.Parameter(torch.rand(num_embeddings, embedding_dim))
def forward(self, indices):
return self.weight[indices]nn.Parameter是将张量注册到model.parameter中,令optimizer可以识别。
19_GELU Activation
mplement the GELU (Gaussian Error Linear Unit) activation.
\text{GELU}(x) = x \cdot \Phi(x) = x \cdot 0.5 \cdot (1 + \text{erf}(x / \sqrt{2}))erf(x) = \frac{2}{\sqrt{\pi}} \int^x_0 e^{-t^2} dterf是标准正态分布在 区间的面积
Signature
def my_gelu(x: Tensor) -> Tensor: ...
Rules
- Do NOT use
F.gelu,nn.GELU, ortorch.nn.functional.gelu - Use
torch.erffor the exact version
import torch
import math
# ✏️ YOUR IMPLEMENTATION HERE
def my_gelu(x):
return (torch.erf(x/math.sqrt(2)) + 1) /2 * x20_Kaiming Initialization
Implement Kaiming (He) normal initialization for weight tensors.
W \sim \mathcal{N}(0, \text{std}^2) \quad \text{where} \quad \text{std} = \sqrt{\frac{2}{\text{fan\_in}}}Signature
def kaiming_init(weight: Tensor) -> Tensor:
# Initialize weight in-place with Kaiming normal
# fan_in = weight.shape[1]
# Returns the weight tensor
import torch
import math
# ✏️ YOUR IMPLEMENTATION HERE
def kaiming_init(weight):
# fill with normal(0, sqrt(2/fan_in))
fan_in = weight.shape[1]
std = math.sqrt(2/fan_in)
return weight.normal_(0, std)