Part I — Text becomes numbers

Tokenization — from text to integer ids

Lesson 00 said an LLM is one function that eats a sequence of tokens and scores a fixed vocabulary. But we start with a raw string of characters, and a neural net is matrix multiplies that only consume numbers. This lesson builds the translator: a reversible map from text to a sequence of integer ids, backed by a fixed-size subword vocabulary that can never run out of room for a word it has never seen.

1 · Why integers, and why subwords

The network is a stack of matrix multiplications. It cannot multiply the letter h. So the first non-negotiable is that text must become numbers — and specifically a sequence of integer ids, each pointing into a lookup table (the embedding table of lesson 02). The only real design freedom is the unit: what is one token? Three choices present themselves, and two of them fail for concrete reasons.

Hold onto the tension in the table: it is a genuine trade-off between sequence length and vocabulary size. Bigger tokens mean a bigger vocabulary but fewer of them per document; smaller tokens mean a smaller vocabulary but more per document. Subwords do not escape the trade-off — they tune it, and the widget at the end of this lesson lets you slide along the curve one merge at a time.

2 · A naive word tokenizer, and the wall it hits

Before the clever scheme, build the obvious one — it makes the failure that motivates BPE concrete. A word-level tokenizer is three steps: split the text into pieces, collect the distinct pieces into a sorted vocabulary, and map each piece to its index in that vocabulary.

Split, then build the vocabulary

"Split" means more than cutting on spaces: punctuation has to become its own token, or "painted." and "painted" would be two different vocabulary entries and the model would have to learn them separately. So we split on whitespace and peel off punctuation as standalone tokens. We also keep case as-is — The and the stay distinct — because capitalization is a real signal (proper nouns, sentence starts) that lowercasing would silently destroy.

# split on whitespace and punctuation, keeping punctuation as tokens
pieces = split_keeping_punctuation(text)      # "It's the last." -> ["It", "'", "s", "the", "last", "."]

# the vocabulary is the sorted set of distinct pieces
vocab_tokens = sorted(set(pieces))            # deterministic order
str_to_id = { tok: i for i, tok in enumerate(vocab_tokens) }
id_to_str = { i: tok for tok, i in str_to_id.items() }   # the inverse, for decoding

Sorting is not cosmetic: it makes the id assignment deterministic, so the same corpus always yields the same ids. With the two dictionaries in hand, encode maps each piece to its id, and decode looks each id back up and rejoins the pieces (fixing spacing around punctuation). The two are exact inverses — this reversibility is what lets us read the model's numeric output back out as text.

The out-of-vocabulary wall

Now feed the tokenizer a word the story never used — say the encoder was built only from The Verdict and you hand it "Hello". The lookup str_to_id["Hello"] simply is not there. The encoder throws a key error. It cannot produce any id, so it cannot process the text at all. This is the out-of-vocabulary (OOV) wall, and it is fatal: a tokenizer that crashes on unseen words is useless on the open-ended text real users type.

The first patch is special tokens — reserved vocabulary entries that stand for something other than a literal word:

Adding these two entries bumps a 1,130-word vocabulary to 1,132. The <|endoftext|> token is genuinely useful and survives into the real GPT tokenizer. But <|unk|> is an admission of defeat — it says "there was a word here and I have no idea what." Every name, typo, and neologism becomes the same featureless id. That is the wall byte-pair encoding is built to demolish: a good tokenizer should never need an unknown token.

3 · Byte-pair encoding: never out-of-vocabulary, fixed size

Byte-pair encoding (BPE) gets the best of both extremes from §1 by building the subword vocabulary bottom-up from characters. The insight: don't pick words or characters as the unit — start at characters (which can spell anything) and then learn which chunks are worth promoting to single tokens, using nothing but their frequency in the training corpus.

The training algorithm

BPE trains a merge table in a greedy loop. Start with the vocabulary as the set of individual characters (or, in the real GPT-2 tokenizer, the 256 raw bytes — see the cross-reference). Then repeat: scan the whole corpus, count every adjacent pair of current tokens, take the single most frequent pair, and glue it into one new token everywhere it occurs — adding it as a new vocabulary entry. Each pass adds exactly one entry, so you stop the moment the vocabulary reaches the target size.

# train BPE: grow the vocabulary to a target size by greedy pair-merging
vocab  = set of all characters in the corpus       # seed: can spell anything
merges = []                                        # ordered list of learned merges

while len(vocab) < TARGET_V:                        # e.g. TARGET_V = 50257
    pairs = count_adjacent_pairs(corpus_tokens)     # {("l","o"): 42, ("e","r"): 37, ...}
    best  = pair_with_highest_count(pairs)          # greedy: take the most frequent
    corpus_tokens = merge_everywhere(corpus_tokens, best)   # "l","o" -> "lo"
    vocab.add(join(best))                            # new token enters the vocabulary
    merges.append(best)                             # remember the order — it defines encoding

The ordered merges list is the whole trained tokenizer. To encode new text, split it into characters and replay the merges in the same order they were learned; whatever tokens remain after the last applicable merge are the ids. Because the loop terminates at a chosen count, V is fixed by construction — for GPT-2 it is exactly 50,257 (256 byte tokens + 50,000 learned merges + one <|endoftext|>).

Why BPE is never out-of-vocabulary

Here is the payoff that kills the <|unk|> token. Suppose the model meets a word it never saw in training — a surname, someunknownPlace, a fresh piece of slang. The merges that do apply fire, and the parts that never earned a merge simply stay as smaller sub-pieces or, in the worst case, individual characters. A brand-new word does not crash the encoder; it comes out as a short sequence of familiar sub-tokens. Since the seed vocabulary can spell every character, there is no string BPE cannot encode. Frequent words end up as a single token (efficient); rare words decompose into a handful of pieces (still exact). The vocabulary is fixed and complete — the exact combination the naive scheme could not achieve.

4 · Consequences: compression and pathologies

Choosing the subword unit has downstream effects that show up constantly when you actually use an LLM. Two are worth internalizing now.

Compression ratio

Tokenization is a compression step. The useful number is the compression ratio = characters ÷ tokens: how many characters, on average, one token buys you. For English with a GPT-2-style vocabulary it is roughly 4 characters per token. That ratio is why the same context window measured in tokens holds far more English than the token count suggests — and why prices, context limits, and throughput are all quoted per token, not per character or per word. The widget's KPI is exactly this ratio, and you will watch it climb as merges make the sequence shorter.

Pathologies you inherit

Because the model only ever sees tokens, quirks of the tokenizer become quirks of the model's apparent "reasoning":

5 · Watch a vocabulary grow, one merge at a time

The widget below runs the BPE training loop from §3 on a fixed toy corpus with lots of repeated structure: low low lower lowest newer newest wider widest. It starts with every word split into individual characters (a small vocabulary that can spell anything, but a long sequence). Each Merge finds the single most frequent adjacent pair — highlighted before it fires — glues it into one token everywhere, and adds it to the vocabulary. Watch the two numbers move in opposite directions: the token count falls while the vocabulary size rises. That is the §1 trade-off happening in front of you, and the compression ratio (characters per token) is the score. Merges never cross the word gaps, exactly as real BPE trains within word boundaries.

Failure modes & checklist

Checkpoint

Where this points next

You can now turn any string into a sequence of integer ids and back — reversibly, with a vocabulary that is fixed at 50,257 and yet never stumped by a new word. But look hard at what those ids are: arbitrary labels. The token " the" might be id 262 and " a" id 257, but 262 is not "5 more" than 257 in any meaningful sense, and id 5 is no nearer id 6 than id 5000. If we fed these integers to the network directly, it would read their magnitudes as meaning and invent a fake ordering that isn't there. The ids are pointers, not quantities. Lesson 02, Embeddings & positions, replaces each id with a learnable vector — so that "meaning" is something gradient descent can shape, and so that similar tokens can drift close together in a space where distance actually means something.

Interview prompts

• Why not tokenize by whole words? (§1 — the vocabulary is unbounded and you still hit out-of-vocabulary on the first unseen name, typo, or new word; a fixed V and open-ended word list are incompatible.)
• Why not tokenize by characters? (§1 — the vocabulary is tiny and never OOV, but sequences become very long and quadratic attention wastes compute spelling common words letter by letter.)
• How does BPE build its vocabulary? (§3 — start from characters/bytes, then greedily merge the most frequent adjacent pair into a new token, repeating until the vocabulary hits a target size; the ordered merge list is the tokenizer.)
• Why does a BPE tokenizer never need an <|unk|> token? (§3 — the seed vocabulary contains all characters, so any unseen word decomposes into sub-pieces or characters it already has; every string encodes.)
• Why is the BPE vocabulary a fixed size? (§3 — each pass adds exactly one entry and the loop stops at the target count, so V is fixed by construction — 50,257 for GPT-2.)
• What does <|endoftext|> do, and why keep it when you drop <|unk|>? (§2 — it marks boundaries between concatenated documents and pads batches; unlike <|unk|> it encodes real structure, so GPT keeps it.)
• Why does an LLM struggle to count the letters in "strawberry"? (§4 — it receives the word as a couple of subword tokens, not seven separate characters, so it never sees the letters as countable units; the failure is in tokenization, not reasoning.)

Companion reads: cs336 · 01 Tokenization goes deeper on byte-level BPE, the 256-byte seed, and glitch tokens; the compression trade-off there is framed against a fixed compute budget.