Upgrade lesson

From words to subwords

The word-level model in the previous lesson worked โ€” readable output, real grammar โ€” but it had a hard ceiling: any word outside the top 2,000 became <unk>, and punctuation glued itself to words. This lesson fixes both by replacing whitespace splitting with Byte Pair Encoding. The Transformer, the optimizer, and the autograd engine don't change. Only the tokenizer does โ€” and it's the tokenizer every real language model actually uses.

What stays

All the internals

Autograd, attention, LayerNorm, GELU, Adam, iterative backward(), the save format, the sampling loop. Zero model code changes.

What changes

Just the tokenizer

Whitespace split โ†’ learned merges. Words become sequences of subword pieces. <unk> disappears entirely.

What it costs

One extra training pass

The merge table has to be learned once (a few minutes). After that, tokenization is fast. Slightly slower per step because words are longer sequences.

"the" โ†’ [t, h, e] โ†’ [th, e] โ†’ ["the"] frequent pairs are merged repeatedly; rare words stay as multiple subwords, common words become single tokens
Begin โ†“

Why subwords โ€” the word model's two problems

The word-level model from the previous lesson made text generation readable, but it had two structural limitations that no amount of training could fix:

  • Unknown words collapse to <unk>. About one token in six on the reference corpus was outside the top 2,000. That means the model could never produce an uncommon word โ€” a name, a technical term, a number, a typo โ€” no matter how much context it had. Every rare word became the same generic token.
  • Punctuation is baked into tokens. "the," and "the" are different vocabulary entries. The embedding table spent 2,000 slots learning that a comma makes a word different, which wasted capacity and reduced coverage.

Subword tokenization solves both at once. Instead of choosing between "one token per character" and "one token per word," it finds a middle ground: common words become single tokens, and rare words break into frequent fragments.

Character (lesson 1)Word (lesson 2)Subword (this lesson)
Tokenone characterone whitespace wordone BPE piece
Vocab size~105~2,001~2,000 merges + 256 bytes
Unknown tokensimpossible~16% of textimpossible (byte fallback)
Handles typosyesnoyes (splits into known pieces)
Punctuationnativeglued to wordsseparate tokens
Output readabilityfragmentsreal wordsreal words + fragments when needed
Context (tokens)321632
Context (text)โ‰ˆ6 wordsโ‰ˆ16 wordsโ‰ˆ23 words
This is what GPT-2, Llama, and everything in between actually use

BPE was adapted from a compression algorithm for neural models by Sennrich et al. (2016) in machine translation, and GPT-2 made its byte-level variant the default. GPT-2 uses 50,257 BPE tokens; Llama 2 uses 32,000 SentencePiece pieces; GPT-4 uses ~100,000. The exact algorithm varies, but the principle โ€” frequent sequences become single tokens, everything else is built from pieces โ€” is universal. Implementing it from scratch here means you understand every real tokenizer.

The BPE idea, step by step

Byte Pair Encoding is a compression algorithm adapted for tokenization. The training procedure is almost embarrassingly simple:

  1. Start by splitting the text into chunks (a word with its leading space, a number, a run of punctuation) and writing each chunk as individual bytes โ€” bytes rather than characters, for full Unicode safety. Merges never cross chunk borders, and spaces are kept, so decoding gives back the exact original text.
  2. Count every adjacent pair of tokens across the whole corpus.
  3. Find the most frequent pair and merge it into a new token.
  4. Repeat steps 2โ€“3 until you have enough merges (we'll use 2,000).

After the merges are learned, encoding new text is just applying the same merges in order. Here's a concrete trace on the words "the", "then", "there":

Start: the then: then there: there
Merge "th" (most frequent pair): the then there
Merge "the": the then there
After more merges: the then there

Notice what happened: "the" became a single token because it appeared often enough, "then" became two tokens, and "there" became two tokens. The vocabulary learned the structure of the language without being told anything about English morphology.

merge table = [('t', 'h') โ†’ 'th', ('th', 'e') โ†’ 'the', ('r', 'e') โ†’ 're', ...]
encode(word) = repeatedly apply the earliest-learned merge that matches
decode(tokens) = ''.join(tokens) then decode bytes โ†’ UTF-8

Try it: train BPE in your browser

Edit the corpus, slide the number of merges, and watch how a sentence is split. With 0 merges every token is a single byte; with more merges, frequent chunks fuse into one token. (Same algorithm as tokenizer.py.)

Why bytes instead of characters?

A character-level BPE needs a special <unk> for any character not in the initial vocabulary. A byte-level BPE starts with all 256 possible bytes, and every Unicode string is representable as bytes, so there is no such thing as an unknown token. GPT-2 introduced this "byte-level BPE" and it's now standard. The trade-off: a non-ASCII character (รฉ, ไฝ , emoji) becomes 2โ€“4 bytes, so it's tokenized into 2โ€“4 pieces. That's a minor cost for complete coverage.

tokenizer.py โ€” the new module

This is the main new file. It contains the BPE trainer, encoder, and decoder. Everything else in the project stays the same. Read it top to bottom โ€” it's about 70 lines of actual logic.

tokenizer.py
"""
tokenizer.py - byte-level BPE, learned from a corpus.

Token ids 0-255 are raw bytes. Merge number k creates id 256 + k.
Text is first split into chunks (a word with its leading space, a number,
a punctuation run, or whitespace) and merges never cross chunk borders.
Because whitespace is kept, decode(encode(text)) == text exactly.

No external dependencies. Pure Python.
"""
import json
import re
from collections import Counter

# GPT-2 style pre-tokenizer: every character lands in exactly one chunk.
PRETOKEN = re.compile(r" ?[^\W\d]+| ?\d+| ?[^\s\w]+|\s+(?!\S)|\s+")


def pretokenize(text):
    return PRETOKEN.findall(text)


def merge_ids(ids, pair, new_id):
    """Replace every adjacent occurrence of `pair` in `ids` with `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


def train_bpe(text, n_merges=2000):
    """Learn a merge table from raw text. Returns a list of (id, id) pairs."""
    chunks = pretokenize(text)
    if not chunks:
        raise ValueError("empty corpus")

    # each distinct chunk is a tuple of byte ids, weighted by how often it occurs
    freq = Counter(tuple(c.encode("utf-8")) for c in chunks)

    merges = []
    for _ in range(n_merges):
        pairs = Counter()
        for word, count in freq.items():
            for pair in zip(word, word[1:]):
                pairs[pair] += count
        if not pairs:
            break
        best = max(pairs, key=pairs.get)           # most frequent adjacent pair
        if pairs[best] < 2:                        # nothing repeats any more
            break
        new_id = 256 + len(merges)
        merges.append(best)

        new_freq = Counter()
        for word, count in freq.items():
            new_freq[tuple(merge_ids(word, best, new_id))] += count
        freq = new_freq

    return merges


class BPETokenizer:
    """A byte-level BPE tokenizer."""

    def __init__(self, merges):
        self.merges = [tuple(p) for p in merges]
        self.ranks = {p: i for i, p in enumerate(self.merges)}
        # id -> bytes: 256 raw bytes, then one entry per merge
        self.itos = {i: bytes([i]) for i in range(256)}
        for i, (a, b) in enumerate(self.merges):
            self.itos[256 + i] = self.itos[a] + self.itos[b]
        self.vocab_size = len(self.itos)
        self._cache = {}

    def _encode_chunk(self, chunk):
        if chunk in self._cache:
            return self._cache[chunk]
        ids = list(chunk.encode("utf-8"))
        while len(ids) > 1:
            # merge the pair that was learned earliest (lowest rank)
            best = min(zip(ids, ids[1:]), key=lambda p: self.ranks.get(p, float("inf")))
            if best not in self.ranks:
                break
            ids = merge_ids(ids, best, 256 + self.ranks[best])
        self._cache[chunk] = ids
        return ids

    def encode(self, text):
        """Text -> list of token ids. No <unk> is ever needed."""
        ids = []
        for chunk in pretokenize(text):
            ids.extend(self._encode_chunk(chunk))
        return ids

    def decode(self, ids):
        """Token ids -> text. Concatenate bytes, then decode UTF-8."""
        raw = b"".join(self.itos[i] for i in ids)
        return raw.decode("utf-8", errors="replace")

    def save(self, path):
        with open(path, "w", encoding="utf-8") as f:
            json.dump(self.merges, f)

    @classmethod
    def load(cls, path):
        with open(path, encoding="utf-8") as f:
            return cls(json.load(f))

pretokenize splits text into chunks with a regex (the same idea as GPT-2). A word keeps its leading space (" the"), numbers and punctuation get their own chunks, and every character lands in exactly one chunk. That is what makes decode(encode(text)) == text hold, and it is why punctuation is now separate from words.

train_bpe does what Step 2 described: count pairs, merge the most frequent one, repeat. Token ids 0โ€“255 are raw bytes and merge k creates id 256 + k, so a merge is just a pair of ids. The freq table counts each distinct chunk once, weighted by how often it appears, so a round never rescans the whole corpus. Training stops early if no pair occurs at least twice.

BPETokenizer.encode applies merges greedily: at each step it merges the pair learned earliest (lowest rank). This is the standard BPE encoding used by GPT-2 and friends. A per-chunk cache makes repeated words free.

The vocabulary is 256 byte tokens plus one per merge, so vocab_size = 256 + len(merges) (2,256 with 2,000 merges). Every byte has an id, so encoding never fails. itos maps ids back to bytes for decoding, and save/load write the merge list to JSON, which is all you need to rebuild the tokenizer.

What you don't see: encoding one chunk costs roughly O(nยฒ) in the chunk's length (each round rescans its pairs), which is tiny for words. Production tokenizers use priority queues and compiled code, but the algorithm is the same.

Test it in isolation before training the model

Run python -c "from tokenizer import *; t = BPETokenizer(train_bpe(open('corpus.txt', encoding='utf-8').read(), 500)); s = 'The quick brown fox, cafรฉ ๐Ÿ˜€'; assert t.decode(t.encode(s)) == s; print('ok', t.encode(s))". If it prints ok, the text round-trips exactly. Do this before starting a 30-minute training run โ€” it is much faster to debug here.

What changes in the model โ€” almost nothing

The model architecture is identical to the previous lesson. Only one constant changes: CTX_LEN goes from 16 (words) to 32 (subword tokens). D_MODEL, N_LAYERS, N_HEADS, D_FF โ€” all unchanged.

model.py โ€” the diff from the word version
# word version (lesson 2)
CTX_LEN = 16     # 16 words โ‰ˆ one sentence

# subword version (this lesson)
CTX_LEN = 32     # 32 subword tokens โ‰ˆ 20โ€“24 words, depending on the text

# everything else unchanged
D_MODEL  = 32
N_LAYERS = 2
N_HEADS  = 2
D_FF     = 128

Why 32 tokens for 20โ€“24 words? Because BPE is a compression algorithm: common words become one token, rare words become several. On the reference corpus, the average English word takes ~1.4 BPE tokens with a 2,000-merge vocabulary. So 32 tokens covers roughly 23 words โ€” longer effective context than the word model's 16.

Parameter count

Vocabulary size = 256 bytes + 2,000 merges = 2,256 tokens. The embedding table and output head are 2 ร— 32 ร— 2256 = 144,384 parameters, versus 128,064 for the 2,001-word model. Total parameter count rises from ~153K to ~170K โ€” a ~11% increase, entirely in the embedding table. The Transformer blocks are untouched.

One caveat, now fixed in the listing: the parameter count train.py prints comes from len(list(all_params(params))). That only matches the numbers above if all_params yields individual scalars. Yielding rows (as a plain yield from over a matrix does) counts each row as one parameter and, worse, feeds lists into the optimizer's gradient loop โ€” which crashes with 'list' object has no attribute 'grad'. The full model.py listing below flattens matrices via _flatten, so Params reports the true ~170K and the optimizer sees only Values.

Training โ€” same loop, different data

The training loop is identical to the previous lesson, with one addition: before the loop, you train the BPE merges. This takes a few minutes on a 500K-character corpus and is a one-time cost โ€” you save the merges alongside the model weights.

train.py โ€” the new first lines
from tokenizer import train_bpe, BPETokenizer

# ... existing imports and constants ...
N_MERGES = 2000

def main():
    text = corpus_path.read_text(encoding="utf-8")

    # 1. learn the BPE merges (one-time, ~2โ€“3 minutes)
    print("Training BPE merges...")
    merges = train_bpe(text, N_MERGES)
    tok = BPETokenizer(merges)
    print(f"Vocabulary: {tok.vocab_size} tokens ({len(merges)} merges + 256 bytes)")

    # 2. tokenize the corpus with the new tokenizer
    data = tok.encode(text)
    if len(data) <= CTX_LEN + 1:
        raise SystemExit(f"Corpus too short: {len(data)} tokens")

    # ... rest of training loop is identical to lesson 2 ...

train_bpe(text, N_MERGES) returns the merge table. BPETokenizer(merges) wraps it into an object with encode and decode. The vocabulary size is 256 + len(merges) โ€” there's no <unk> token because every byte is in the vocabulary from the start.

The tokenized corpus will have noticeably more tokens than the word corpus โ€” roughly 1.3โ€“1.5ร— as many, since common words stay one token while rare words become several (and punctuation is now its own token). Measure yours: len(tok.encode(text)) versus len(text.split()).

The loss numbers will be different again. Random-guess baseline is now ln(2256) โ‰ˆ 7.72. Expect it to fall steadily from ~7.7; the end value depends on your corpus. The numbers are not comparable to the word model because the tokenization is different, but the shape of the curve โ€” steep initial drop, then slow improvement โ€” should look familiar.

What to expect in the log

Vocabulary: 2256 tokens (2000 merges + 256 bytes)
Tokens: ~95,000 (โ‰ˆ1.4ร— the word model's 68,827; yours depends on the corpus)
Params: ~170,000
Training time: roughly 2ร— slower per step than the word model, because each sequence is 32 tokens instead of 16.

If you see Params: 5,760 instead, your all_params is yielding matrix rows instead of scalars โ€” use the full model.py listing below, which flattens matrices. The training loop will otherwise crash on the first optimizer step with 'list' object has no attribute 'grad'.

Generation โ€” the tokenizer handles everything

The generation loop is unchanged. The only difference is that the prompt is encoded with tok.encode() and the output is decoded with tok.decode(). No manual splitting or joining โ€” the tokenizer owns the text โ†” tokens mapping.

infer.py โ€” the two changed lines
from tokenizer import BPETokenizer

# ... load the model ...
tok = BPETokenizer.load("model.tok.json")   # written by train.py

# tokenize the prompt
tokens = tok.encode(prompt)

# ... generation loop identical ...

# detokenize the output
return tok.decode(tokens)

That's the entire diff. The tokenizer handles punctuation correctly, handles unknown words by breaking them into subword pieces, and handles Unicode by working on bytes. The model doesn't need to know any of this โ€” it just sees integer token ids.

What the output looks like

After a full 300-step training run you should see output like the following. These samples are illustrative of the kind of text a model this small produces, not captured logs โ€” yours will differ:

infer.py โ€” sample session
> :t 0.5
> :k 10
> The
The code is a of the can be used to the code is a string that is a of the code is a
> The tokenizer
The tokenizer is a of the code and the code is a string that can be used to the

The output is still not coherent English โ€” this is a ~170K-parameter model trained for 300 steps on a single CPU core. But it no longer has the word model's <unk> failure mode, so no capacity is spent on it. And critically, if the prompt contains a rare word, it doesn't fail:

infer.py โ€” rare word test
> The defenestration
The defenestration of the code is a of the can be a the

"defenestration" is almost certainly not in the top 2,000 words, so the word model would have collapsed it to <unk> and produced garbage. The subword model splits it into several learned pieces (the exact split depends on your merges; print tok.encode("defenestration") to see it), and continues normally. That's the whole point.

Experiments to try

Compare to the word model: prompt both with the same rare word. The word model outputs <unk>; the subword model keeps going.

Look at a tokenization: add a debug line print(tok.encode("your prompt here")) and compare to prompt.split(). Common words โ†’ one id; rare words โ†’ several ids.

Vary N_MERGES: try 500 merges (coarser, smaller vocab) and 4,000 (finer, larger vocab). Watch how the average tokens-per-word changes.

Try non-ASCII text: prompt with cafรฉ or an emoji. The byte-level tokenizer handles it; the word model would have produced <unk>.

The trade-offs, made explicit

Subword tokenization is not strictly better than words or characters โ€” it's a different set of trade-offs. Here's the full three-way comparison:

PropertyCharacterWordSubword (BPE)
Vocabulary size~105~2,001~2,256
Unknown tokensimpossible~16% of textimpossible
Handles typosyesnoyes
Handles non-ASCIIyes (each char)often <unk>yes (bytes)
Punctuationseparate charsglued to wordsseparate pieces
Output readabilityspelling fragmentsreal wordsreal words + rare fragments
Tokens per word~5โ€“61~1.4
Context length (tokens)321632
Effective context (words)~6~16~23
Parameters~33K~153K~170K
Training speedfastestmediummedium (slightly slower)
Extra training stepnonenoneBPE merge table
Used by real modelsearly modelsrarelyalmost everything

When to pick which

  • Character only if you're building a teaching tool or a model for an extremely constrained alphabet (e.g., DNA sequences). Real text models moved past characters because the per-token cost is too high.
  • Word if you have a closed vocabulary and a specific, narrow domain where every word is known. In practice, this is rare โ€” any real-world text contains unknown words.
  • Subword in every other case. It's the default for a reason: no unknowns, reasonable vocabulary size, readable output, and it compresses text so each token carries ~1.4 words of information on average.
The real lesson: tokenization is compression

BPE is a compression algorithm. It finds repeated patterns and replaces them with single symbols. The vocabulary is a codebook, and the merge table is the list of common patterns. This is exactly what tokenization is: a learned code that maps text to integers. The model never sees characters โ€” it sees the output of this code. Getting the code right means the model spends its capacity on language, not on spelling or vocabulary gaps.

Every real language model's tokenizer is a variant of this idea. GPT-2's byte-level BPE, SentencePiece's unigram model, WordPiece (BERT) โ€” they all learn a vocabulary of frequent subword pieces and represent everything else as sequences of those pieces. You now understand the algorithm behind all of them.

Where this leads

The subword tokenizer is the final tokenization upgrade in this series. From here, every further change is architectural or scale, not tokenization. The path from here to something that writes coherent paragraphs is a matter of more parameters, more data, and more compute โ€” the same model, scaled.

StageTokenizerVocabContextParams
Character (lesson 1)per-character~10532 chars~33K
Word (lesson 2)whitespace split~2,00116 words~153K
Subword (this lesson)byte-level BPE~2,25632 subwords~170K
GPT-2 smallBPE50,2571024 subwords124M

The gap between this model and GPT-2 small is 700ร— in parameters and 32ร— in context length โ€” but the tokenizer is the same idea, and the architecture is the same block stacked more times. If you understand this lesson, you understand the tokenization layer of every model above it.

Natural next steps from here: more layers (2 โ†’ 12), wider model (32 โ†’ 768), longer context (32 โ†’ 1024), and much more data. None of those require a new concept. The concepts are done; the rest is scale.

The source files

To run it

Requires: Python 3.9+. No pip install needed. No dependencies beyond the standard library.

Layout: six files in one folder, plus a corpus.txt. Every file is listed in full below โ€” build_corpus.py, tokenizer.py, micrograd.py, model.py, train.py, and infer.py. train.py writes model.bin and model.tok.json (the merges); infer.py loads both.

mkdir docs && cp some_text.md docs/
python build_corpus.py ./docs corpus.txt
python train.py corpus.txt model.bin
python infer.py

Expected: ~170K parameters when all 2,000 merges are learned (a very small corpus runs out of repeated pairs and learns fewer). BPE training takes ~2โ€“3 minutes, then 300 training steps take ~25โ€“30 minutes on a single core. Peak memory ~1.6 GB.

build_corpus.py โ€” complete

build_corpus.py
#!/usr/bin/env python3
"""build_corpus.py โ€” concatenate text files into one corpus.txt.

Usage: python build_corpus.py <input_dir> <output.txt>
"""
import sys
from pathlib import Path

TEXT_EXTS = {".txt", ".md", ".rst", ".py", ".c", ".h", ".js", ".css", ".html", ".json", ".csv"}

def main():
    if len(sys.argv) < 3:
        print("usage: build_corpus.py <input_dir> <output.txt>", file=sys.stderr)
        sys.exit(1)
    src = Path(sys.argv[1])
    out = Path(sys.argv[2])
    if not src.exists():
        raise SystemExit(f"input dir not found: {src}")

    files = sorted(p for p in src.rglob("*") if p.is_file() and p.suffix.lower() in TEXT_EXTS)
    if not files:
        raise SystemExit(f"no text files found under {src}")

    total = 0
    with out.open("w", encoding="utf-8") as f:
        for p in files:
            try:
                text = p.read_text(encoding="utf-8")
            except UnicodeDecodeError:
                try:
                    text = p.read_text(encoding="latin-1")
                except Exception as e:
                    print(f"skip {p}: {e}", file=sys.stderr)
                    continue
            text = text.strip()
            if not text:
                continue
            f.write(text)
            f.write("\n\n")
            total += len(text)
    print(f"wrote {out} ({total:,} chars from {len(files)} files)")

if __name__ == "__main__":
    main()

tokenizer.py โ€” complete

tokenizer.py
"""
tokenizer.py - byte-level BPE, learned from a corpus.

Token ids 0-255 are raw bytes. Merge number k creates id 256 + k.
Text is first split into chunks (a word with its leading space, a number,
a punctuation run, or whitespace) and merges never cross chunk borders.
Because whitespace is kept, decode(encode(text)) == text exactly.

No external dependencies. Pure Python.
"""
import json
import re
from collections import Counter

# GPT-2 style pre-tokenizer: every character lands in exactly one chunk.
PRETOKEN = re.compile(r" ?[^\W\d]+| ?\d+| ?[^\s\w]+|\s+(?!\S)|\s+")


def pretokenize(text):
    return PRETOKEN.findall(text)


def merge_ids(ids, pair, new_id):
    """Replace every adjacent occurrence of `pair` in `ids` with `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


def train_bpe(text, n_merges=2000):
    """Learn a merge table from raw text. Returns a list of (id, id) pairs."""
    chunks = pretokenize(text)
    if not chunks:
        raise ValueError("empty corpus")

    # each distinct chunk is a tuple of byte ids, weighted by how often it occurs
    freq = Counter(tuple(c.encode("utf-8")) for c in chunks)

    merges = []
    for _ in range(n_merges):
        pairs = Counter()
        for word, count in freq.items():
            for pair in zip(word, word[1:]):
                pairs[pair] += count
        if not pairs:
            break
        best = max(pairs, key=pairs.get)           # most frequent adjacent pair
        if pairs[best] < 2:                        # nothing repeats any more
            break
        new_id = 256 + len(merges)
        merges.append(best)

        new_freq = Counter()
        for word, count in freq.items():
            new_freq[tuple(merge_ids(word, best, new_id))] += count
        freq = new_freq

    return merges


class BPETokenizer:
    """A byte-level BPE tokenizer."""

    def __init__(self, merges):
        self.merges = [tuple(p) for p in merges]
        self.ranks = {p: i for i, p in enumerate(self.merges)}
        # id -> bytes: 256 raw bytes, then one entry per merge
        self.itos = {i: bytes([i]) for i in range(256)}
        for i, (a, b) in enumerate(self.merges):
            self.itos[256 + i] = self.itos[a] + self.itos[b]
        self.vocab_size = len(self.itos)
        self._cache = {}

    def _encode_chunk(self, chunk):
        if chunk in self._cache:
            return self._cache[chunk]
        ids = list(chunk.encode("utf-8"))
        while len(ids) > 1:
            # merge the pair that was learned earliest (lowest rank)
            best = min(zip(ids, ids[1:]), key=lambda p: self.ranks.get(p, float("inf")))
            if best not in self.ranks:
                break
            ids = merge_ids(ids, best, 256 + self.ranks[best])
        self._cache[chunk] = ids
        return ids

    def encode(self, text):
        """Text -> list of token ids. No <unk> is ever needed."""
        ids = []
        for chunk in pretokenize(text):
            ids.extend(self._encode_chunk(chunk))
        return ids

    def decode(self, ids):
        """Token ids -> text. Concatenate bytes, then decode UTF-8."""
        raw = b"".join(self.itos[i] for i in ids)
        return raw.decode("utf-8", errors="replace")

    def save(self, path):
        with open(path, "w", encoding="utf-8") as f:
            json.dump(self.merges, f)

    @classmethod
    def load(cls, path):
        with open(path, encoding="utf-8") as f:
            return cls(json.load(f))

micrograd.py โ€” complete

micrograd.py
"""
micrograd.py โ€” a tiny autograd engine.
Same as the word-level lesson. The only notable detail is that
backward() is iterative, which matters because a 2,256-way softmax
makes the graph deep enough to hit Python's recursion limit.
"""
import math

class Value:
    def __init__(self, data, children=(), op=""):
        self.data      = data
        self.grad      = 0.0
        self._prev     = children
        self._op       = op
        self._backward = lambda: None

    def __add__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data + other.data, (self, other), "+")
        def _backward():
            self.grad  += out.grad
            other.grad += out.grad
        out._backward = _backward
        return out

    def __mul__(self, other):
        other = other if isinstance(other, Value) else Value(other)
        out = Value(self.data * other.data, (self, other), "*")
        def _backward():
            self.grad  += other.data * out.grad
            other.grad += self.data  * out.grad
        out._backward = _backward
        return out

    def __pow__(self, n):
        out = Value(self.data ** n, (self,), f"**{n}")
        def _backward():
            self.grad += n * (self.data ** (n - 1)) * out.grad
        out._backward = _backward
        return out

    def exp(self):
        out = Value(math.exp(self.data), (self,), "exp")
        def _backward():
            self.grad += out.data * out.grad
        out._backward = _backward
        return out

    def log(self):
        x = max(self.data, 1e-30)
        out = Value(math.log(x), (self,), "log")
        def _backward():
            self.grad += (1.0 / x) * out.grad
        out._backward = _backward
        return out

    def tanh(self):
        out = Value(math.tanh(self.data), (self,), "tanh")
        def _backward():
            self.grad += (1.0 - out.data ** 2) * out.grad
        out._backward = _backward
        return out

    def backward(self):
        topo, visited = [], set()
        stack = [(self, False)]
        while stack:
            v, expanded = stack.pop()
            if expanded:
                topo.append(v)
                continue
            if v in visited:
                continue
            visited.add(v)
            stack.append((v, True))
            for child in v._prev:
                if child not in visited:
                    stack.append((child, False))
        self.grad = 1.0
        for v in reversed(topo):
            v._backward()
            v._backward = lambda: None
            v._prev = ()
        topo.clear(); visited.clear()

def __radd__(self, other): return self + other
def __rmul__(self, other): return self * other
def __neg__(self): return self * -1
def __sub__(self, other): return self + (-other)
def __truediv__(self, other):
    other = other if isinstance(other, Value) else Value(other)
    return self * (other ** -1)
def __rsub__(self, other): return (-self) + other
def __rtruediv__(self, other): return Value(other) * (self ** -1)
Value.__rsub__    = __rsub__
Value.__rtruediv__ = __rtruediv__
Value.__radd__    = __radd__
Value.__rmul__    = __rmul__
Value.__neg__     = __neg__
Value.__sub__     = __sub__
Value.__truediv__ = __truediv__

def dot(xs, ws):
    out = Value(sum(x.data * w.data for x, w in zip(xs, ws)),
                tuple(xs) + tuple(ws), "dot")
    def _backward():
        g = out.grad
        for x, w in zip(xs, ws):
            x.grad += w.data * g
            w.grad += x.data * g
    out._backward = _backward
    return out

model.py โ€” complete

model.py
"""
model.py โ€” the tiny Transformer. Identical to the word-level lesson
except CTX_LEN = 32 (subword tokens) and the vocab is now 256 + n_merges.

all_params() FLATTENS every matrix into individual Value objects. This
matters for two reasons:
  * len(list(all_params(p))) must equal the true scalar count (~170K),
    otherwise the "Params:" log line lies (it printed 5,760 before the fix);
  * train.py's optimizer loop iterates all_params() and calls .grad on
    every element โ€” if a matrix row (a list) slips through, it crashes
    with "'list' object has no attribute 'grad'".
"""
import math, random, struct
from micrograd import Value, dot

CTX_LEN  = 32
D_MODEL  = 32
N_LAYERS = 2
N_HEADS  = 2
D_FF     = 128
HEAD_DIM = D_MODEL // N_HEADS

# ---------- parameter init ----------

def init_matrix(rows, cols, scale=0.08):
    return [[Value(random.gauss(0, scale)) for _ in range(cols)] for _ in range(rows)]

def init_vector(n, scale=0.08):
    return [Value(random.gauss(0, scale)) for _ in range(n)]

def init_model(vocab_size):
    p = {}
    p["tok_emb"]  = init_matrix(vocab_size, D_MODEL)
    p["pos_emb"]  = init_matrix(CTX_LEN, D_MODEL)
    p["blocks"]   = []
    for _ in range(N_LAYERS):
        b = {}
        b["ln1_g"] = init_vector(D_MODEL, 0.0)
        b["ln1_b"] = init_vector(D_MODEL, 0.0)
        b["wq"] = init_matrix(D_MODEL, D_MODEL)
        b["wk"] = init_matrix(D_MODEL, D_MODEL)
        b["wv"] = init_matrix(D_MODEL, D_MODEL)
        b["wo"] = init_matrix(D_MODEL, D_MODEL)
        b["ln2_g"] = init_vector(D_MODEL, 0.0)
        b["ln2_b"] = init_vector(D_MODEL, 0.0)
        b["w1"] = init_matrix(D_FF, D_MODEL)
        b["b1"] = init_vector(D_FF, 0.0)
        b["w2"] = init_matrix(D_MODEL, D_FF)
        b["b2"] = init_vector(D_MODEL, 0.0)
        p["blocks"].append(b)
    p["lnf_g"] = init_vector(D_MODEL, 0.0)
    p["lnf_b"] = init_vector(D_MODEL, 0.0)
    p["head"]  = init_matrix(vocab_size, D_MODEL)
    return p

# ---------- flatten & iterate parameters ----------
# A parameter container is either a Value, a list of Values, or a list
# of lists of Values (a matrix). _flatten recursively yields the scalars.

def _flatten(obj):
    if isinstance(obj, Value):
        yield obj
    else:
        for x in obj:
            yield from _flatten(x)

def all_params(p):
    for key in ("tok_emb", "pos_emb"):
        yield from _flatten(p[key])
    for b in p["blocks"]:
        for key in ("ln1_g","ln1_b","wq","wk","wv","wo","ln2_g","ln2_b","w1","b1","w2","b2"):
            yield from _flatten(b[key])
    yield from _flatten(p["lnf_g"])
    yield from _flatten(p["lnf_b"])
    yield from _flatten(p["head"])

# ---------- math helpers ----------

def matmul(x, W):
    # x: list of Value (len = rows of W = len(W[0])); W: list of rows
    return [dot(x, row) for row in W]

def add_rows(a, b):
    return [x + y for x, y in zip(a, b)]

def softmax(logits):
    m = max(v.data for v in logits)
    e = [(v - m).exp() for v in logits]
    s = sum(v.data for v in e)
    return [v / s for v in e]

def layernorm(x, g, b, eps=1e-5):
    n = len(x)
    mean = sum(v.data for v in x) / n
    var  = sum((v.data - mean) ** 2 for v in x) / n
    inv  = 1.0 / math.sqrt(var + eps)
    out = []
    for i, v in enumerate(x):
        out.append((v - mean) * inv * g[i] + b[i])
    return out

def gelu_approx(x):
    # tanh approximation
    return 0.5 * x * (1.0 + (math.sqrt(2.0 / math.pi) * (x + 0.044715 * (x ** 3))).tanh())

# ---------- transformer block ----------

def attention(x, b):
    # x: list of CTX_LEN vectors, each length D_MODEL
    Q = [matmul(t, b["wq"]) for t in x]
    K = [matmul(t, b["wk"]) for t in x]
    V = [matmul(t, b["wv"]) for t in x]

    out = []
    for i in range(CTX_LEN):
        heads_out = []
        for h in range(N_HEADS):
            off = h * HEAD_DIM
            scores = []
            for j in range(i + 1):  # causal
                s = sum(Q[i][off + d] * K[j][off + d] for d in range(HEAD_DIM))
                scores.append(s / math.sqrt(HEAD_DIM))
            probs = softmax(scores)
            head = [Value(0.0) for _ in range(HEAD_DIM)]
            for j in range(i + 1):
                for d in range(HEAD_DIM):
                    head[d] = head[d] + probs[j] * V[j][off + d]
            heads_out.extend(head)
        out.append(matmul(heads_out, b["wo"]))
    return out

def block(x, b):
    # pre-LN
    a = [layernorm(t, b["ln1_g"], b["ln1_b"]) for t in x]
    a = attention(a, b)
    x = [add_rows(xi, ai) for xi, ai in zip(x, a)]
    a = [layernorm(t, b["ln2_g"], b["ln2_b"]) for t in x]
    ff = []
    for t in a:
        h = matmul(t, b["w1"])
        h = [h[k] + b["b1"][k] for k in range(D_FF)]
        h = [gelu_approx(v) for v in h]
        o = matmul(h, b["w2"])
        o = [o[k] + b["b2"][k] for k in range(D_MODEL)]
        ff.append(o)
    return [add_rows(xi, fi) for xi, fi in zip(x, ff)]

# ---------- forward ----------

def forward(tokens, p):
    x = [add_rows(p["tok_emb"][t], p["pos_emb"][i]) for i, t in enumerate(tokens)]
    for b in p["blocks"]:
        x = block(x, b)
    x = [layernorm(t, p["lnf_g"], p["lnf_b"]) for t in x]
    logits = [matmul(t, p["head"]) for t in x]
    return logits

# ---------- save / load ----------
# save/load consume all_params(), which is already flat, so the byte
# layout is: 12-byte header (steps, vocab_size, n_params), 4-byte loss,
# then n_params float32 scalars in all_params() order.

def save_model(path, p, itos, steps, loss):
    with open(path, "wb") as f:
        f.write(struct.pack("<III", steps, len(itos), len(list(all_params(p)))))
        f.write(struct.pack("<f", loss))
        for v in all_params(p):
            f.write(struct.pack("<f", v.data))

def load_model(path):
    with open(path, "rb") as f:
        steps, vocab_size, n_params = struct.unpack("<III", f.read(12))
        loss, = struct.unpack("<f", f.read(4))
        params = []
        for _ in range(n_params):
            params.append(Value(struct.unpack("<f", f.read(4))[0]))
    return steps, vocab_size, loss, params

train.py โ€” complete

train.py
#!/usr/bin/env python3
"""train.py โ€” train the subword model."""
import sys, time, random, gc
from pathlib import Path
from tokenizer import train_bpe, BPETokenizer
from micrograd import Value
from model import CTX_LEN, init_model, all_params, forward, softmax, save_model

BATCH_SIZE = 4
STEPS      = 300
LR         = 3e-3
N_MERGES   = 2000

def compute_loss(logits, targets):
    total = Value(0.0)
    for t in range(len(logits)):
        probs = softmax(logits[t])
        total = total - probs[targets[t]].log()
    return total / len(logits)

def main():
    random.seed(0)
    gc.disable()
    corpus_path = Path(sys.argv[1] if len(sys.argv) > 1 else "corpus.txt")
    out_path    = Path(sys.argv[2] if len(sys.argv) > 2 else "model.bin")

    text = corpus_path.read_text(encoding="utf-8")

    print("Training BPE merges...")
    merges = train_bpe(text, N_MERGES)
    tok = BPETokenizer(merges)
    print(f"Vocabulary: {tok.vocab_size} tokens")

    data = tok.encode(text)
    if len(data) <= CTX_LEN + 1:
        raise SystemExit(f"Corpus too short: {len(data)} tokens")

    vocab_size = tok.vocab_size
    params = init_model(vocab_size)
    plist  = list(all_params(params))
    print(f"Tokens: {len(data):,}")
    print(f"Params: {len(plist):,}")

    m = [0.0] * len(plist)
    v = [0.0] * len(plist)
    b1, b2, eps = 0.9, 0.999, 1e-8
    t0, recent = time.time(), []

    print(f"Training for {STEPS} steps...")
    for step in range(1, STEPS + 1):
        loss = Value(0.0)
        for _ in range(BATCH_SIZE):
            j = random.randint(0, len(data) - CTX_LEN - 1)
            x = data[j : j + CTX_LEN]
            y = data[j + 1 : j + CTX_LEN + 1]
            loss = loss + compute_loss(forward(x, params), y)
        loss = loss / BATCH_SIZE
        loss.backward()
        for i, p in enumerate(plist):
            m[i] = b1 * m[i] + (1 - b1) * p.grad
            v[i] = b2 * v[i] + (1 - b2) * p.grad ** 2
            m_hat = m[i] / (1 - b1 ** step)
            v_hat = v[i] / (1 - b2 ** step)
            p.data -= LR * m_hat / (v_hat ** 0.5 + eps)
            p.grad  = 0.0
        recent.append(loss.data)
        if step == 1 or step % 50 == 0:
            avg = sum(recent[-50:]) / len(recent[-50:])
            print(f"step {step:4d}  loss {avg:.4f}")

    final = sum(recent[-50:]) / len(recent[-50:])
    save_model(out_path, params, tok.itos, STEPS, final)
    tok.save(out_path.with_suffix(".tok.json"))   # merges, needed by infer.py
    print(f"Saved: {out_path}  (avg loss: {final:.4f})")
    print(f"Done in {time.time() - t0:.1f}s")

if __name__ == "__main__":
    main()

infer.py โ€” complete

infer.py
#!/usr/bin/env python3
"""infer.py โ€” sample from the subword model."""
import sys, struct, math, random
from pathlib import Path
from tokenizer import BPETokenizer
from micrograd import Value
from model import (
    CTX_LEN, D_MODEL, N_LAYERS, N_HEADS, D_FF,
    init_model, all_params, forward, softmax,
)

def load_weights_into(model, flat):
    it = iter(flat)
    for v in all_params(model):
        v.data = next(it)

def load_model_bin(path):
    with open(path, "rb") as f:
        steps, vocab_size, n_params = struct.unpack("<III", f.read(12))
        loss, = struct.unpack("<f", f.read(4))
        flat = [struct.unpack("<f", f.read(4))[0] for _ in range(n_params)]
    model = init_model(vocab_size)
    load_weights_into(model, flat)
    return model, steps, vocab_size, loss

def sample(logits, temperature=1.0, top_k=None):
    if temperature <= 0:
        return max(range(len(logits)), key=lambda i: logits[i].data)
    scaled = [v / temperature for v in logits]
    probs = softmax(scaled)
    if top_k:
        idx = sorted(range(len(probs)), key=lambda i: probs[i].data, reverse=True)[:top_k]
        keep = {i: probs[i].data for i in idx}
        z = sum(keep.values())
        r = random.random() * z
        acc = 0.0
        for i, p in keep.items():
            acc += p
            if r <= acc:
                return i
        return idx[-1]
    r = random.random()
    acc = 0.0
    for i, p in enumerate(probs):
        acc += p.data
        if r <= acc:
            return i
    return len(probs) - 1

def _pad_to_ctx(tokens):
    """Left-pad with the space byte (32) so attention has exactly CTX_LEN slots."""
    if len(tokens) >= CTX_LEN:
        return tokens[-CTX_LEN:]
    return [32] * (CTX_LEN - len(tokens)) + tokens

def generate(model, tok, prompt, n_tokens=60, temperature=1.0, top_k=None):
    tokens = tok.encode(prompt)
    if not tokens:
        tokens = [32]  # space fallback
    for _ in range(n_tokens):
        ctx = _pad_to_ctx(tokens)
        logits = forward(ctx, model)
        next_id = sample(logits[-1], temperature, top_k)
        tokens.append(next_id)
    return tok.decode(tokens)

def main():
    random.seed(0)
    model_bin = Path(sys.argv[1] if len(sys.argv) > 1 else "model.bin")
    tok_json  = Path(sys.argv[2] if len(sys.argv) > 2 else "model.tok.json")

    if not model_bin.exists():
        raise SystemExit(f"missing {model_bin}; run train.py first")
    if not tok_json.exists():
        raise SystemExit(f"missing {tok_json}; run train.py first")

    model, steps, vocab_size, loss = load_model_bin(model_bin)
    tok = BPETokenizer.load(tok_json)
    if tok.vocab_size != vocab_size:
        raise SystemExit(f"vocab mismatch: model={vocab_size} tokenizer={tok.vocab_size}")

    print(f"Loaded: {steps} steps, vocab {vocab_size}, avg loss {loss:.4f}")
    print("Commands: :t <temp>  :k <top_k>  :q  (or type a prompt)")
    temp, topk = 1.0, None

    while True:
        try:
            line = input("> ").strip()
        except (EOFError, KeyboardInterrupt):
            print()
            break
        if not line:
            continue
        if line == ":q":
            break
        if line.startswith(":t "):
            temp = float(line[3:]); print(f"temperature = {temp}"); continue
        if line.startswith(":k "):
            topk = int(line[3:]); print(f"top_k = {topk}"); continue
        out = generate(model, tok, line, n_tokens=60, temperature=temp, top_k=topk)
        print(out)

if __name__ == "__main__":
    main()
Troubleshooting

Smoke test first โ†’ set STEPS = 5 and N_MERGES = 100. Everything should complete in under a minute.

Tokenization is slow โ†’ it's pure Python BPE on a full corpus. For a smoke test, use a smaller corpus or fewer merges.

Encoding / decoding mismatch โ†’ test tok.decode(tok.encode(text)) == text before training. If it fails, check the merge application logic.

'list' object has no attribute 'grad' โ†’ all_params is yielding matrix rows instead of scalars. Use the full model.py listing above, which flattens via _flatten. Symptom: Params: prints a suspiciously small number (e.g. 5,760) just before the crash.

Out of memory โ†’ peak is ~1.6 GB. Lower BATCH_SIZE to 2.

Most tokens are single bytes โ†’ you trained too few merges. Increase N_MERGES.

Vocab mismatch in infer.py โ†’ make sure model.tok.json is the one written by the same train.py run as model.bin.

What you just learned

Three takeaways

1. BPE is compression. It learns frequent byte pairs and merges them into single tokens. Common words become one token; rare words become a sequence of frequent fragments. The model never sees raw text โ€” it sees the output of this learned code.

2. No more unknowns. Starting from all 256 bytes means every Unicode string is representable. Typos, names, emoji, mixed languages โ€” all tokenize without a special <unk> case. This is why every real model uses subword tokenization.

3. The model doesn't change. Same Transformer block, same optimizer, same autograd engine. The tokenizer is a preprocessing layer: it takes text in and produces integers out. Swapping it out is the entire upgrade.

You now have three working language models built from the same ~500 lines of pure Python: a character model, a word model, and a subword model. The architecture is identical across all three. What changed each time was the tokenizer โ€” and that's the lesson: in language modeling, the tokenizer is the first and most consequential design decision. The model learns whatever the tokenizer shows it. Show it bytes, and it learns spelling. Show it words, and it learns grammar but hits an unknown-word ceiling. Show it subwords, and it gets both โ€” which is why every real system uses them.