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.
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.
All the internals
Autograd, attention, LayerNorm, GELU, Adam, iterative backward(), the save format, the sampling loop. Zero model code changes.
Just the tokenizer
Whitespace split โ learned merges. Words become sequences of subword pieces. <unk> disappears entirely.
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.
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) | |
|---|---|---|---|
| Token | one character | one whitespace word | one BPE piece |
| Vocab size | ~105 | ~2,001 | ~2,000 merges + 256 bytes |
| Unknown tokens | impossible | ~16% of text | impossible (byte fallback) |
| Handles typos | yes | no | yes (splits into known pieces) |
| Punctuation | native | glued to words | separate tokens |
| Output readability | fragments | real words | real words + fragments when needed |
| Context (tokens) | 32 | 16 | 32 |
| Context (text) | โ6 words | โ16 words | โ23 words |
The BPE idea, step by step
Byte Pair Encoding is a compression algorithm adapted for tokenization. The training procedure is almost embarrassingly simple:
- 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.
- Count every adjacent pair of tokens across the whole corpus.
- Find the most frequent pair and merge it into a new token.
- 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":
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.
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.)
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 - 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.
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.
# 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.
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.
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.
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.
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:
> :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:
> 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.
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:
| Property | Character | Word | Subword (BPE) |
|---|---|---|---|
| Vocabulary size | ~105 | ~2,001 | ~2,256 |
| Unknown tokens | impossible | ~16% of text | impossible |
| Handles typos | yes | no | yes |
| Handles non-ASCII | yes (each char) | often <unk> | yes (bytes) |
| Punctuation | separate chars | glued to words | separate pieces |
| Output readability | spelling fragments | real words | real words + rare fragments |
| Tokens per word | ~5โ6 | 1 | ~1.4 |
| Context length (tokens) | 32 | 16 | 32 |
| Effective context (words) | ~6 | ~16 | ~23 |
| Parameters | ~33K | ~153K | ~170K |
| Training speed | fastest | medium | medium (slightly slower) |
| Extra training step | none | none | BPE merge table |
| Used by real models | early models | rarely | almost 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.
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.
| Stage | Tokenizer | Vocab | Context | Params |
|---|---|---|---|---|
| Character (lesson 1) | per-character | ~105 | 32 chars | ~33K |
| Word (lesson 2) | whitespace split | ~2,001 | 16 words | ~153K |
| Subword (this lesson) | byte-level BPE | ~2,256 | 32 subwords | ~170K |
| GPT-2 small | BPE | 50,257 | 1024 subwords | 124M |
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
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
#!/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 - 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 โ 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 โ 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
#!/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
#!/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()
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
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.