ML Implementations
Core ML building blocks written from scratch in NumPy and PyTorch.
Compact from-scratch implementations of the core building blocks of a transformer language model, in PyTorch and NumPy, with the detail that most often goes wrong in each.
Attention
Multi-head attention (MHA) – Each token builds a query , key and value by linear projection. Its output is a weighted average of all values, weighted by how well its query matches each key. With heads, the model dimension is split into independent heads of size . In a causal (left-to-right) model, token may only attend to positions up to .
where the mask is on allowed positions and on future ones.
import math, torch, torch.nn as nn
class MHA(nn.Module):
def __init__(self, d_model, n_heads, bias=False):
super().__init__()
assert d_model % n_heads == 0
self.nh, self.hd = n_heads, d_model // n_heads
self.q = nn.Linear(d_model, d_model, bias=bias)
self.k = nn.Linear(d_model, d_model, bias=bias)
self.v = nn.Linear(d_model, d_model, bias=bias)
self.o = nn.Linear(d_model, d_model, bias=bias)
def forward(self, x, causal=True):
B, T, D = x.shape
def split(t): # (B,T,D) -> (B,nh,T,hd)
return t.view(B, T, self.nh, self.hd).transpose(1, 2)
q, k, v = split(self.q(x)), split(self.k(x)), split(self.v(x))
att = (q @ k.transpose(-2, -1)) / math.sqrt(self.hd) # (B,nh,T,T)
if causal:
mask = torch.triu(torch.ones(T, T, dtype=torch.bool, device=x.device), 1)
att = att.masked_fill(mask, float("-inf"))
att = att.softmax(dim=-1)
y = att @ v # (B,nh,T,hd)
y = y.transpose(1, 2).contiguous().view(B, T, D) # merge heads
return self.o(y)
Fill masked scores with before the softmax, not after. Attention costs time and memory per head for sequence length . Call .contiguous() after transpose and before view. For grouped-query attention (GQA), where several query heads share one key/value head, project and to fewer heads and repeat them along the head axis.
Numerics
Stable softmax and cross-entropy – Softmax turns scores (logits) into probabilities . Cross-entropy is the loss for the correct class . Subtracting the maximum score first leaves the result unchanged but keeps from overflowing. The log-sum-exp form computes directly:
The gradient of the mean loss with respect to the logits is for a batch of .
import numpy as np
def softmax(x, axis=-1):
x = x - np.max(x, axis=axis, keepdims=True) # shift for stability
e = np.exp(x)
return e / np.sum(e, axis=axis, keepdims=True)
def log_softmax(x, axis=-1):
z = x - np.max(x, axis=axis, keepdims=True)
return z - np.log(np.sum(np.exp(z), axis=axis, keepdims=True))
def cross_entropy(logits, targets):
"""logits (N, C) float, targets (N,) int -> mean loss, dL/dlogits."""
ls = log_softmax(logits)
N = logits.shape[0]
loss = -ls[np.arange(N), targets].mean()
grad = np.exp(ls) # softmax probabilities
grad[np.arange(N), targets] -= 1.0
return loss, grad / N
np.log(softmax(x)) can underflow to . log_softmax cannot, because after the shift every exponent is at most .
Normalization
LayerNorm and RMSNorm – Layer normalization rescales each token's vector to mean and variance , then applies a learned scale and shift . RMSNorm skips the mean subtraction and the shift, dividing only by the root mean square. It is cheaper and works as well in practice.
class LayerNorm(nn.Module):
def __init__(self, d, eps=1e-5):
super().__init__()
self.w = nn.Parameter(torch.ones(d))
self.b = nn.Parameter(torch.zeros(d))
self.eps = eps
def forward(self, x):
mu = x.mean(-1, keepdim=True)
var = x.var(-1, keepdim=True, unbiased=False) # divide by N, not N-1
return (x - mu) / torch.sqrt(var + self.eps) * self.w + self.b
class RMSNorm(nn.Module):
def __init__(self, d, eps=1e-6):
super().__init__()
self.w = nn.Parameter(torch.ones(d))
self.eps = eps
def forward(self, x):
rms = x.pow(2).mean(-1, keepdim=True).add(self.eps).rsqrt()
return x * rms * self.w # no mean, no bias
x.var() defaults to dividing by . LayerNorm needs unbiased=False.
LayerNorm backward pass – With and features, the input gradient removes the components along the all-ones direction and along :
def layernorm_backward(dy, x, w, eps=1e-5):
N = x.shape[-1]
mu = x.mean(-1, keepdims=True)
var = x.var(-1, keepdims=True)
inv = 1.0 / np.sqrt(var + eps)
xhat = (x - mu) * inv
dw = (dy * xhat).sum(axis=tuple(range(dy.ndim - 1)))
db = dy.sum(axis=tuple(range(dy.ndim - 1)))
dxhat = dy * w
dx = inv / N * (N * dxhat
- dxhat.sum(-1, keepdims=True)
- xhat * (dxhat * xhat).sum(-1, keepdims=True))
return dx, dw, db
Positional encoding
Rotary position embeddings (RoPE) – Encode position by rotating pairs of query and key coordinates through an angle proportional to the position . Pair rotates at frequency for a base such as . The dot product of a rotated query at position and a rotated key at position then depends only on the offset .
def rope_cache(T, hd, base=10000.0, device="cpu", offset=0):
"""offset = absolute position of the first token. Returns cos, sin: (T, hd/2)."""
assert hd % 2 == 0
inv = 1.0 / (base ** (torch.arange(0, hd, 2, device=device).float() / hd))
pos = torch.arange(offset, offset + T, device=device).float()
ang = torch.outer(pos, inv) # (T, hd/2)
return ang.cos(), ang.sin()
def apply_rope(x, cos, sin):
"""x: (B, nh, T, hd), 'split-half' pairing (x[i], x[i + hd/2])."""
x1, x2 = x.chunk(2, dim=-1)
cos, sin = cos[None, None], sin[None, None]
return torch.cat([x1 * cos - x2 * sin,
x2 * cos + x1 * sin], dim=-1)
Rotate and only, never . The split-half pairing and the interleaved pairing are not interchangeable for the same weights. Pass offset when decoding with a cache. Raising the base extends the usable context length.
Decoding
Temperature, top-k and top-p sampling – To pick the next token, divide the logits by a temperature (below 1 sharpens the distribution, above 1 flattens it). Top- keeps only the most likely tokens. Top-, or nucleus sampling, keeps the smallest set of most-likely tokens whose total probability reaches . Removed tokens get logit , and the rest are renormalized by the softmax.
def filter_logits(logits, top_k=0, top_p=1.0, temperature=1.0):
"""logits (B, V) -> same shape, -inf on removed tokens."""
logits = logits / max(temperature, 1e-8) # temperature first
if top_k and top_k > 0:
k = min(top_k, logits.size(-1))
kth = logits.topk(k, dim=-1).values[..., -1, None]
logits = logits.masked_fill(logits < kth, float("-inf"))
if top_p is not None and top_p < 1.0:
sl, si = torch.sort(logits, descending=True, dim=-1)
probs = sl.softmax(-1)
cum = probs.cumsum(-1)
# keep a token iff the mass strictly before it is below top_p
remove = (cum - probs) >= top_p
sl = sl.masked_fill(remove, float("-inf"))
logits = torch.empty_like(logits).scatter_(-1, si, sl) # undo the sort
return logits
# usage
probs = filter_logits(logits, top_k=50, top_p=0.9, temperature=0.8).softmax(-1)
next_token = torch.multinomial(probs, num_samples=1)
The naive rule cum > top_p drops the token that crosses the threshold, and returns an empty set when top_p is below the largest single probability. Testing cum - probs always keeps at least one token. For example, with probabilities 0.4, 0.3, 0.2, 0.07, 0.03 and , three tokens are kept.
Key–value (KV) cache – Generation runs in two phases. Prefill processes the whole prompt at once. Decode then feeds one new token per step. Keys and values of past tokens never change, so each layer stores them in a cache and appends the new token's and , instead of recomputing the whole prefix every step.
class Block(nn.Module):
def __init__(self, d, nh):
super().__init__()
self.nh, self.hd = nh, d // nh
self.n1, self.n2 = RMSNorm(d), RMSNorm(d)
self.qkv = nn.Linear(d, 3 * d, bias=False)
self.proj = nn.Linear(d, d, bias=False)
self.mlp = nn.Sequential(nn.Linear(d, 4*d, bias=False), nn.GELU(),
nn.Linear(4*d, d, bias=False))
def attn(self, x, cache, pos0):
B, Tq, D = x.shape
q, k, v = self.qkv(x).split(D, dim=-1)
sp = lambda t: t.view(B, Tq, self.nh, self.hd).transpose(1, 2)
q, k, v = sp(q), sp(k), sp(v)
cos, sin = rope_cache(Tq, self.hd, offset=pos0, device=x.device)
q, k = apply_rope(q, cos, sin), apply_rope(k, cos, sin) # rotate, then cache
if cache is not None and cache["k"] is not None: # append
k = torch.cat([cache["k"], k], dim=2)
v = torch.cat([cache["v"], v], dim=2)
if cache is not None:
cache["k"], cache["v"] = k, v
Tk = k.size(2)
att = (q @ k.transpose(-2, -1)) / math.sqrt(self.hd) # (B,nh,Tq,Tk)
# query i sits at absolute position pos0+i and may see keys 0..pos0+i
qp = torch.arange(pos0, pos0 + Tq, device=x.device)[:, None]
kp = torch.arange(Tk, device=x.device)[None, :]
att = att.masked_fill(kp > qp, float("-inf")).softmax(-1)
y = (att @ v).transpose(1, 2).contiguous().view(B, Tq, D)
return self.proj(y)
def forward(self, x, cache=None, pos0=0):
x = x + self.attn(self.n1(x), cache, pos0) # pre-norm
return x + self.mlp(self.n2(x))
class TinyLM(nn.Module):
def __init__(self, V, d=16, nh=4, nl=3):
super().__init__()
self.emb = nn.Embedding(V, d)
self.blocks = nn.ModuleList([Block(d, nh) for _ in range(nl)])
self.nf = RMSNorm(d)
self.head = nn.Linear(d, V, bias=False)
self.nl = nl
def forward(self, idx, caches=None, pos0=0):
x = self.emb(idx)
for i, blk in enumerate(self.blocks):
x = blk(x, None if caches is None else caches[i], pos0)
return self.head(self.nf(x))
def empty_cache(self):
return [{"k": None, "v": None} for _ in range(self.nl)]
@torch.no_grad()
def generate(self, idx, max_new, temperature=1.0, top_k=0, top_p=1.0, greedy=False):
caches = self.empty_cache()
logits = self(idx, caches, pos0=0)[:, -1] # prefill: whole prompt
pos, out = idx.size(1), idx
for _ in range(max_new):
if greedy:
nxt = logits.argmax(-1, keepdim=True)
else:
probs = filter_logits(logits, top_k, top_p, temperature).softmax(-1)
nxt = torch.multinomial(probs, 1)
out = torch.cat([out, nxt], dim=1)
logits = self(nxt, caches, pos0=pos)[:, -1] # decode: one token in
pos += 1
return out
The cache holds . The mask must use absolute positions, and RoPE needs the offset. To test the implementation, check that cached decoding gives the same logits as recomputing from scratch. Prefill is limited by compute; decode is limited by memory bandwidth. Appending with torch.cat reallocates every step, so production code pre-allocates the buffer instead.
Tokenization
Byte-pair encoding (BPE) – Start from the 256 possible byte values as the vocabulary. Training repeatedly finds the most frequent adjacent pair of tokens and merges it into a new token, until the vocabulary reaches the target size. Encoding replays the learned merges in the order they were learned. Decoding concatenates the bytes of each token.
def get_stats(ids, counts=None):
counts = {} if counts is None else counts
for a, b in zip(ids, ids[1:]):
counts[(a, b)] = counts.get((a, b), 0) + 1
return counts
def merge(ids, pair, new_id):
out, i = [], 0
while i < len(ids):
if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
out.append(new_id); i += 2
else:
out.append(ids[i]); i += 1
return out
class BPE:
def __init__(self):
self.merges = {} # (a, b) -> new_id
self.vocab = {i: bytes([i]) for i in range(256)} # byte-level base
def train(self, text, vocab_size):
assert vocab_size >= 256
ids = list(text.encode("utf-8"))
for i in range(vocab_size - 256):
stats = get_stats(ids)
if not stats:
break
pair = max(stats, key=stats.get) # most frequent pair
new_id = 256 + i
ids = merge(ids, pair, new_id)
self.merges[pair] = new_id
self.vocab[new_id] = self.vocab[pair[0]] + self.vocab[pair[1]]
return ids
def encode(self, text):
ids = list(text.encode("utf-8"))
while len(ids) >= 2:
stats = get_stats(ids)
# apply the earliest-learned merge present (replay training order)
pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))
if pair not in self.merges:
break
ids = merge(ids, pair, self.merges[pair])
return ids
def decode(self, ids):
return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")
A byte-level base means no input is ever out of vocabulary, so no unknown token is needed. Encoding greedily by longest match gives different results from replaying the merges. Real tokenizers first split the text with a regular expression so merges never cross word boundaries. errors="replace" matters because a single token can end partway through a multi-byte character.
Optimizers
Adam and AdamW – Adam keeps a running average of the gradient (momentum) and of its square. It divides the step by , so each parameter gets its own scale. At step , the bias corrections and undo the zero initialization. AdamW applies weight decay directly to the weights, separately from the gradient.
class Adam:
def __init__(self, params, lr=1e-3, betas=(0.9, 0.999), eps=1e-8,
weight_decay=0.0, decoupled=False):
self.p = list(params); self.lr = lr
self.b1, self.b2 = betas; self.eps = eps
self.wd, self.decoupled = weight_decay, decoupled
self.m = [torch.zeros_like(p) for p in self.p]
self.v = [torch.zeros_like(p) for p in self.p]
self.t = 0
@torch.no_grad()
def step(self):
self.t += 1 # t starts at 1
bc1 = 1 - self.b1 ** self.t
bc2 = 1 - self.b2 ** self.t
for i, p in enumerate(self.p):
if p.grad is None:
continue
g = p.grad
if self.wd and not self.decoupled:
g = g + self.wd * p # Adam: L2 folded into the gradient
self.m[i].mul_(self.b1).add_(g, alpha=1 - self.b1)
self.v[i].mul_(self.b2).addcmul_(g, g, value=1 - self.b2)
denom = (self.v[i] / bc2).sqrt().add_(self.eps) # eps outside the sqrt
if self.wd and self.decoupled:
p.mul_(1 - self.lr * self.wd) # AdamW: decoupled decay
p.addcdiv_(self.m[i] / bc1, denom, value=-self.lr)
def zero_grad(self):
for p in self.p:
p.grad = None
Three details matter. The step count starts at 1, since without bias correction early steps are too small. is added after the square root. In plain Adam an L2 penalty is rescaled per parameter, while AdamW's decay is not.
Warmup and cosine schedule – The learning rate rises linearly for the first steps, then follows half a cosine down to a floor.
def lr_at(step, base_lr, warmup, total, min_ratio=0.1):
if step < warmup:
return base_lr * (step + 1) / warmup # linear warmup
prog = (step - warmup) / max(1, total - warmup) # in [0, 1]
cos = 0.5 * (1.0 + math.cos(math.pi * prog))
return base_lr * (min_ratio + (1 - min_ratio) * cos)