11_Sliding Window Attention

Implement Sliding Window Attention — used in Longformer, Mistral, etc. for efficient long-context processing.

Each position ii can only attend to positions jj where |i−j|≤w|i-j|\le w (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 V
  • window_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 ϕ\phi:

\text{LinearAttn}(Q,K,V) = \frac{\phi(Q) \left(\phi(K)^T V\right)}{\phi(Q) \cdot \sum \phi(K)}

Feature map

Use ϕ(x)=elu(x)+1\phi(x) = \text{elu}(x) + 1 (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 S×SS \times S attention matrix, compute ϕ(K)TV\phi(K)^T V first (a Dk×DvD_k \times D_v matrix), then multiply by ϕ(Q)\phi(Q).

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) 能拆 ⟺ 存在特征映射 φ,使得:

k(a,b)=ϕ(a)⋅ϕ(b)=∑mϕm(a)ϕm(b)k(a,b)=\phi(a)\cdot \phi(b) = \sum_m \phi_m(a)\phi_m(b)

也就是先单独提取特征再直接点积比对,就叫可拆

对于softmax,我们的权重是一个eQiKje^{Q_iK_j},在数学上不能拆成两个函数的点积

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.Linear for attention
  • self.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 x

14_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.Linear projections
  • When cache=None (prefill): apply causal mask, return all K/V as cache
  • When cache provided (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.silu or implement as x * 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_entropy or nn.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 by 1/(1-p)
  • During eval: return input unchanged (identity)
  • Do NOT use nn.Dropout or F.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 x

18_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.Parameter of 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} dt

erf是标准正态分布在[−x,x][-x,x] 区间的面积

Signature

def my_gelu(x: Tensor) -> Tensor: ...

Rules

  • Do NOT use F.gelu, nn.GELU, or torch.nn.functional.gelu
  • Use torch.erf for the exact version
import torch
import math

# ✏️ YOUR IMPLEMENTATION HERE

def my_gelu(x):
    return (torch.erf(x/math.sqrt(2)) + 1) /2 * x

20_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)

Related Posts