ML Implementations

Core ML building blocks written from scratch in NumPy and PyTorch.

ML Implementations

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 qq, key kk and value vv by linear projection. Its output is a weighted average of all values, weighted by how well its query matches each key. With hh heads, the model dimension dd is split into hh independent heads of size dh=d/hd_h = d/h. In a causal (left-to-right) model, token tt may only attend to positions up to tt.

Attention⁡(Q,K,V)=softmax⁡(QK⊤dh+M)V\operatorname{Attention}(Q, K, V) = \operatorname{softmax}\Big(\frac{QK^\top}{\sqrt{d_h}} + M\Big)V

where the mask MM is 00 on allowed positions and −∞-\infty 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 −∞-\infty before the softmax, not after. Attention costs O(T2d)O(T^2 d) time and O(T2)O(T^2) memory per head for sequence length TT. Call .contiguous() after transpose and before view. For grouped-query attention (GQA), where several query heads share one key/value head, project KK and VV to fewer heads and repeat them along the head axis.

Numerics

Stable softmax and cross-entropy – Softmax turns scores (logits) zz into probabilities pi=ezi/∑jezjp_i = e^{z_i}/\sum_j e^{z_j}. Cross-entropy is the loss −log⁡py-\log p_y for the correct class yy. Subtracting the maximum score first leaves the result unchanged but keeps eze^{z} from overflowing. The log-sum-exp form computes log⁡p\log p directly:

log⁡py=zy−m−log⁡∑jezj−m,m=max⁡jzj\log p_y = z_y - m - \log\sum_j e^{z_j - m}, \qquad m = \max_j z_j

The gradient of the mean loss with respect to the logits is (p−onehot(y))/N(p - \text{onehot}(y))/N for a batch of NN.

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⁡0=−∞\log 0 = -\infty. log_softmax cannot, because after the shift every exponent is at most e0=1e^0 = 1.

Normalization

LayerNorm and RMSNorm – Layer normalization rescales each token's vector to mean 00 and variance 11, then applies a learned scale ww and shift bb. RMSNorm skips the mean subtraction and the shift, dividing only by the root mean square. It is cheaper and works as well in practice.

LN⁡(x)=x−μσ2+ϵ⊙w+b,RMSNorm⁡(x)=xmean⁡(x2)+ϵ⊙w\operatorname{LN}(x) = \frac{x - \mu}{\sqrt{\sigma^2 + \epsilon}}\odot w + b, \qquad \operatorname{RMSNorm}(x) = \frac{x}{\sqrt{\operatorname{mean}(x^2) + \epsilon}}\odot w
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 N−1N - 1. LayerNorm needs unbiased=False.

LayerNorm backward pass – With x^=(x−μ)/σ2+ϵ\hat x = (x - \mu)/\sqrt{\sigma^2 + \epsilon} and NN features, the input gradient removes the components along the all-ones direction and along x^\hat x:

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 mm. Pair ii rotates at frequency θi=b−2i/dh\theta_i = b^{-2i/d_h} for a base bb such as 1000010000. The dot product of a rotated query at position mm and a rotated key at position nn then depends only on the offset m−nm - n.

(x1′x2′)=(cos⁡mθi−sin⁡mθisin⁡mθicos⁡mθi)(x1x2)\begin{pmatrix}x_1'\\ x_2'\end{pmatrix} = \begin{pmatrix}\cos m\theta_i & -\sin m\theta_i\\ \sin m\theta_i & \cos m\theta_i\end{pmatrix}\begin{pmatrix}x_1\\ x_2\end{pmatrix}
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 QQ and KK only, never VV. The split-half pairing and the interleaved pairing (x0,x1),(x2,x3),…(x_0, x_1), (x_2, x_3), \dots 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 τ\tau (below 1 sharpens the distribution, above 1 flattens it). Top-kk keeps only the kk most likely tokens. Top-pp, or nucleus sampling, keeps the smallest set of most-likely tokens whose total probability reaches pp. Removed tokens get logit −∞-\infty, 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 p=0.8p = 0.8, 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 kk and vv, 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 2×layers×KV heads×dh×sequence length×batch×bytes per number2 \times \text{layers} \times \text{KV heads} \times d_h \times \text{sequence length} \times \text{batch} \times \text{bytes per number}. 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 mm of the gradient (momentum) and vv of its square. It divides the step by v^\sqrt{\hat v}, so each parameter gets its own scale. At step tt, the bias corrections m^=m/(1−β1t)\hat m = m/(1 - \beta_1^t) and v^=v/(1−β2t)\hat v = v/(1 - \beta_2^t) undo the zero initialization. AdamW applies weight decay directly to the weights, separately from the gradient.

θ←θ−η m^v^+ϵ  [− ηλθ for AdamW]\theta \leftarrow \theta - \eta\,\frac{\hat m}{\sqrt{\hat v} + \epsilon} \;\Big[-\, \eta\lambda\theta \text{ for AdamW}\Big]
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. ϵ\epsilon 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)