Fix a Buggy Transformer, Then Add a KV Cache
Problem statement
A teammate wrote a small decoder-only language model in numpy. It runs, every shape is right, and it returns logits, but the training loss behaves strangely and its samples are poor. Five bugs were planted in the code below. None of them raises an error.
import numpy as np
def layer_norm(x, g, b, eps=1e-5):
mu = x.mean(axis=0, keepdims=True)
var = x.var(axis=0, keepdims=True)
return g * (x - mu) / np.sqrt(var + eps) + b
def self_attention(x, L, n_heads):
T, d = x.shape
dh = d // n_heads
q = (x @ L["Wq"]).reshape(T, n_heads, dh).transpose(1, 0, 2) # (H, T, dh)
k = (x @ L["Wk"]).reshape(T, n_heads, dh).transpose(1, 0, 2)
v = (x @ L["Wv"]).reshape(T, n_heads, dh).transpose(1, 0, 2)
s = q @ k.transpose(0, 2, 1) / dh # (H, T, T)
future = np.triu(np.ones((T, T)), k=2)
s = np.where(future == 1, -np.inf, s)
s = s - s.max(axis=-1, keepdims=True)
w = np.exp(s)
w = w / w.sum(axis=1, keepdims=True)
out = (w @ v).transpose(1, 0, 2).reshape(T, d)
return out @ L["Wo"]
def forward(params, tokens):
E = np.asarray(params["tok_emb"])
P = np.asarray(params["pos_emb"])
tokens = np.asarray(tokens)
x = E[tokens] + P[tokens]
for L in params["layers"]:
L = {key: np.asarray(val) for key, val in L.items()}
x = x + self_attention(layer_norm(x, L["ln1_g"], L["ln1_b"]), L, params["n_heads"])
h = layer_norm(x, L["ln2_g"], L["ln2_b"])
x = x + np.maximum(0.0, h @ L["W1"] + L["b1"]) @ L["W2"] + L["b2"]
x = layer_norm(x, np.asarray(params["lnf_g"]), np.asarray(params["lnf_b"]))
return x @ np.asarray(params["W_out"]) # (T, vocab)
Intended model. Token embedding plus learned absolute position embedding (row $t$ of pos_emb for position $t$, starting at 0). Then for each layer a pre-LayerNorm block: x = x + attn(LN1(x)), then x = x + W2 relu(LN2(x) W1 + b1) + b2. LayerNorm normalizes each position's feature vector ($\epsilon = 10^{-5}$, population variance). Attention is causal multi-head self-attention: head $h$ uses columns $h \cdot d_h$ to $(h+1) d_h - 1$ of the projections, $d_h = d / n_{heads}$, scores are scaled by $1/\sqrt{d_h}$, and position $i$ may attend to positions $0..i$ only. A final LayerNorm and W_out (shape $d \times V$) give the logits. params is a dict of nested lists: n_heads, tok_emb ($V \times d$), pos_emb ($P \times d$), layers (each with ln1_g, ln1_b, Wq, Wk, Wv, Wo, ln2_g, ln2_b, W1, b1, W2, b2, weights used as x @ W), lnf_g, lnf_b, W_out.
Part 1. Find and fix the five bugs, and say which small test would expose each one even though no shape is wrong.
Part 2. Recomputing the whole sequence for every generated token is wasteful. Implement greedy generation with a key/value cache written from scratch: run the prompt through the model once, keeping each layer's keys and values, then feed exactly one new token per step, appending its keys and values to the cache. Cached generation must produce the same logits as a full forward pass of the corrected model over the same tokens.
def generate(params: dict, prompt: list, n_new: int) -> list:
# returns [tokens, logits]
...
tokens: then_newgenerated ids; each is the argmax of the current next-token logits (lowest id on ties).logits[i]: the list of $V$ next-token logits from whichtokens[i]was chosen (sologits[0]comes from the prompt alone).
Constraints
- $d \in \{4, 6, 8\}$, $n_{heads}$ divides $d$, 2-3 layers, $5 \le V \le 10$, $P = 12$ positions.
- $1 \le$
len(prompt)$\le 6$, $1 \le$n_new$\le 6$, andlen(prompt) + n_new - 1$\le P$. - Logits are compared with an absolute and relative tolerance of $10^{-6}$; numpy is available.
Example
For any valid params, generate(params, prompt, 1) must return [[t], [row]] where row is the last row of the corrected forward(params, prompt) and t is its argmax. For n_new = 3, logits[2] must equal the last row of the corrected forward(params, prompt + tokens[:2]).
Show hint
Which properties must a correct causal language model satisfy that you can check without knowing the right logits?
Relevant roles: ML Engineer, LLM Engineer, AI Engineer and Deep Learning Engineer.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium