Curriculum

Week 5. Tokenization

Phase 2. The modern transformer · week 5 of 24

Learn in the app: tutor, coding problems →

Core: BPE from scratch, byte-level, tokenization metrics and pain points · Depth: WordPiece and Unigram, embeddings in detail, combinatorics (track D) · ≈ 11 h core / 21 h total

If tokenization is your area, interviewers will dig deep into it.

The model never sees text, only token ids. Anything the tokenizer glued together or split badly, the model later has to learn around: this is where the problems with arithmetic, code and Russian come from. The vocabulary size goes straight into the parameter count (week 9) and into how much text fits in the context.

Step 1. Granularity: the trade-off between length and vocabulary

In plain terms. A vocabulary is a set of stamps. If you only have stamps for whole words, there is nothing to print a new word like "untokenizable" with. If you only have stamps for letters, you can print anything, but every word turns into a dozen impressions. A subword vocabulary makes stamps for frequent pieces: "un", "token", "izable". Byte-level adds a guarantee: the set always contains 256 stamps for individual bytes, so any text can be printed, byte by byte in the worst case.

• Levels: characters / bytes / words / subwords. The trade-off between sequence length and vocabulary size
• Word-level: a vocabulary of hundreds of thousands, an unknown word becomes <unk> (the "unknown" token), word forms do not share statistics. Bytes: a tiny vocabulary, but the sequence is several times longer. Attention pays for length quadratically
• The cost of byte-level for Russian: Cyrillic in UTF-8 takes 2 bytes per letter. «привет, мир» ("hello, world" in Russian) weighs 20 bytes, "hello, world" 12. Russian starts from a longer sequence before any merges happen

Step 2. BPE: greedy compression

In plain terms. Corpus: "cop" ×4, "coda" ×3, "cod" ×5. Count adjacent letter pairs, weighted by frequency: "c"+"o" occurs 4 + 3 + 5 = 12 times, more than any other pair. It becomes a new token "co". Recount: now "co"+"d" occurs 3 + 5 = 8 times: that is the next token, "cod". Two steps, and the frequent word has become a single token, while the rarer "coda" is two: "cod" + "a".

• BPE: training (merging the most frequent pair), encoding, byte-level BPE, byte fallback (an unknown character is broken down into bytes instead of <unk>)
• Training: count pairs of neighbors across all chunks, merge the most frequent one into a new id, repeat V − 256 times
• Encoding is not "longest match" but replaying the merges in training order. At each step the pair with the lowest merge index is merged. Otherwise you get a segmentation the model has never seen
• The pre-tokenization regex (GPT-2/GPT-4 patterns) and why it matters more than it seems. It splits the text into chunks before BPE. Without it, merges cross word boundaries, and the vocabulary is wasted on pieces like " the end of"

• WordPiece, Unigram / SentencePiece: how the merge criterion differs. WordPiece picks the pair with the largest count(ab) / (count(a)·count(b)), that is, the likelihood gain rather than frequency. Unigram goes top-down: it removes the tokens whose removal hurts the corpus likelihood the least
• Metrics: fertility (tokens per word), compression rate (bytes per token). Models with different tokenizers cannot be compared by loss per token, only in bits per byte
• Pain points: numbers (why arithmetic breaks), code and indentation, multilinguality (the tax on non-English languages), the space before a word, glitch tokens (SolidGoldMagikarp): the token is in the vocabulary but almost never appeared in the model's training data, so its embedding stayed untrained
• How the vocabulary affects the embedding matrix and the softmax head: V·D parameters in each and 2·D·V FLOPs (floating-point operations: each multiply and each add counts as one; details in week 9) per token in the head. The larger V, the shorter the sequences, but each token appears less often in training (D2)

Step 3. From id to vector: embeddings

In plain terms. Three words on a plane: "cat" (1, 0.2), "dog" (0.9, 0.3), "airplane" (0.1, 1). The cosine of the angle between "cat" and "dog" is 0.96 / (1.020 · 0.949) ≈ 0.99, between "cat" and "airplane" 0.3 / (1.020 · 1.005) ≈ 0.29. The length of a vector does not matter here, the angle does: that is why similarity is measured by cosine.

• Embedding: a row of the V × D matrix, and the token id selects the row. In one-hot (a vector with a one at the id's position) all words are equally far from each other; a dense vector of size D lets similar words end up close
• The distributional hypothesis (a word's meaning is set by its neighbors). word2vec trains vectors so that a word predicts the words in its window. Skip-gram with negative sampling (negative examples: random words that were not neighbors) reduces this to logistic regression σ(u_cᵀ v_w): real pairs move closer, random ones move apart. GloVe arrives at similar vectors by factorizing the co-occurrence matrix
• Cosine similarity cos(a, b) = aᵀb / (‖a‖·‖b‖), from −1 to 1, independent of length. Frequent words usually get long vectors, and the dot product would make them neighbors of everything
• Analogies by vector arithmetic: "king − man + woman ≈ queen". You look for the vector closest by cosine to b − a + c, excluding a, b, c themselves (otherwise the answer is often b). It works for some relations (capital, gender, verb tense) and fails on many others: an illustration, not a law
• A static embedding gives a word one vector for all its senses ("bank" of a river and "bank" with money). The transformer takes the same kind of vector as input, and attention makes it contextual (weeks 6–8). The same cosines drive dense retrieval (week 21)

Common mistakes

• Decoding each token into a string separately: a token can cut a multi-byte character in half. First concatenate the bytes, then decode. Caught by test_bytes_are_always_encodable and test_roundtrip (emoji)
• Encoding with greedy longest match instead of merge order. All the test_tokenizer.py tests stay green: decoding is correct for any segmentation. Only comparing ids against the reference nanolm.tokenizer on the same corpus catches it. Roundtrip is necessary but not sufficient
• Passing special tokens through the regex and merges: <|endoftext|> falls apart into pieces, caught by test_special_tokens_are_atomic. Stripping the leading space: caught by test_leading_space_matters

Code → nanolm/tokenizer.py: a BPE trainer and encoder/decoder from scratch. BPETokenizer: train (GPT2_SPLIT_PATTERN, _get_pair_counts, _merge), _encode_chunk, encode, decode, add_special_tokens, fertility, compression_ratio. Exercise: exercises_en/tokenizer.py, check: NANOLM_IMPL=exercises_en pytest tests/test_tokenizer.py -v. Train it on a small corpus and compare fertility with tiktoken (test_fertility_shows_language_tax sees the tax even on a toy).

Math (track D): D1: entropy as a lower bound on the average code length (why BPE compression hits a wall at the entropy of the text); D2: how many vocabulary tokens will never appear in the corpus.

Interview question of the week: "Why does an LLM make arithmetic mistakes and fail to count the letters in a word?" A 3-minute structure: the model sees ids, not characters → the letters inside a token are available only through the learned embedding → numbers are split unevenly, digit positions are not aligned → fixes: one digit per token (Llama 1–2), groups of up to 3 digits (GPT-4 regex), right-to-left alignment, a calculator → the price: length.

Sources: Sennrich et al., Subword Units (2016); Radford et al., GPT-2 (2019), byte-level BPE; Kudo, Subword Regularization (2018), Unigram; Kudo & Richardson, SentencePiece (2018).

Week outcomes

• I can implement a BPE trainer, encoder and decoder from scratch, with an exact round trip on arbitrary bytes.
• I can compute the fertility and compression rate of my tokenizer and of tiktoken on Russian and English.
• I can explain in 3 minutes how number tokenization gets in the way of arithmetic.
• I can explain why byte-level BPE never has unknown tokens.
• I can explain why a green roundtrip test does not prove that encoding is correct.

Self-check

1. How does the merge criterion differ in BPE, WordPiece and Unigram?
2. Why is the pre-tokenization regex needed, and what goes wrong without it?
3. How does vocabulary size affect the parameter count and the sequence length, and where does the "tax" on non-English languages come from?
4. Why is embedding similarity measured by cosine rather than the dot product, and why exclude the query words in the analogy task?