# Module 9: Tokenization

> How tokenizers turn text into integers: byte-pair encoding by hand, WordPiece and SentencePiece, vocabulary-size trade-offs, and the quirks tokens cause.

- Part III: Building an LLM · core track · Intermediate · 3 hours
- By the end you can run BPE by hand and predict how the tokenizer changes cost and behaviour.
- Builds on: [Module 8: Three Families: Encoder, Encoder-Decoder, Decoder](https://transformers-and-math.drmhse.com/md/08-three-families.md)
- Web page (interactive figures, labs and equation explainers): https://transformers-and-math.drmhse.com/modules/09-tokenization
- From *Transformers & Math* by Mike Chumba: https://transformers-and-math.drmhse.com

A model reads integers, not text. The *tokenizer* decides how text becomes integers, once, before training, and the choice is frozen into everything the model learns. It sets sequence length, embedding-table size, the cost of each language, and even which simple-looking questions the model finds oddly hard.

## 9.1 Words, Characters, or Subwords

One token per word needs an enormous vocabulary and still meets unseen words. One token per character keeps the vocabulary small but makes sequences very long. **Subword** tokenization sits between: common words get one token, and rare words split into a few common pieces.

## 9.2 Byte-Pair Encoding

GPT-2 uses **byte-level Byte-Pair Encoding (BPE)**. Its vocabulary has $50{,}257$ tokens: the 256 possible byte values, 50,000 learned merges, and one special end-of-text token.

```mermaid
graph TD
    Raw["Training words: 'lower', 'lowest', 'newer', 'wider'"] --> Base["Start: 256 base tokens, one per byte value 0 to 255"]
    Base --> Count["Count every adjacent pair of tokens in the corpus"]
    Count --> Merge1["Merge the most frequent pair: 'e' + 'r' becomes 'er'"]
    Merge1 --> Merge2["Recount, merge again: 'l' + 'o' becomes 'lo'"]
    Merge2 --> Merge3["Again: 'lo' + 'w' becomes 'low'"]
    Merge3 --> Vocab["Stop at the target size: 50,257 tokens for GPT-2"]
```

> **In words.** Start from single bytes and repeatedly merge the most frequent adjacent pair into a new token. Frequent words end up as one token; rare words stay in pieces.

> **Interactive figure** `bpe-stepper`, on the web page: https://transformers-and-math.drmhse.com/modules/09-tokenization#figure-bpe-stepper
>
> **Try:** The starting corpus repeats *low*, *lower*, *newest* and *widest*. Before stepping, predict which pair of symbols will be merged first, and which whole word will become a single token soonest.
>
> **What happens:** The first merge is the most frequent adjacent pair in the whole corpus, and in this corpus that is one of the pairs shared by *newest* and *widest* (`e` + `s`, then `es` + `t`), because they repeat often. Frequent words collapse into single tokens within a few merges; a word that appears once stays split into pieces long after.

> **In words.** A small corpus split into symbols, a table of adjacent-pair counts, and the merges learned so far. Each step merges the most frequent pair everywhere. A test sentence below is retokenized after each merge, and its token count falls.

### The BPE Merge Algorithm
1. Split the training text into words, and write each word as a sequence of base symbols (characters, or bytes in GPT-2).
2. Count how often each pair of adjacent symbols occurs across the whole corpus.
3. Take the most frequent pair $(A, B)$ and replace every occurrence with a single new symbol $AB$.
4. Add $AB$ to the vocabulary and record the merge.
5. Repeat steps 2 to 4 until the vocabulary reaches the target size.

New text is tokenized by applying the recorded merges in order. The original BPE paper (Sennrich et al., 2016) marks word ends with `</w>`; GPT-2 instead keeps the leading space as part of the token, so `" lower"` and `"lower"` are different tokens.

Since any text is a sequence of UTF-8 bytes, a byte-level vocabulary can tokenize every input and never needs an `<UNK>` ("unknown") token.

## 9.3 Other Subword Tokenizers

- **WordPiece** (Schuster & Nakajima, 2012), used by BERT with 30,522 tokens, merges the pair that most increases the training text's likelihood rather than the most frequent.
- **Unigram** (Kudo, 2018) starts from many candidate pieces and removes those whose loss hurts least, keeping a probability per piece so a word can split more than one way.
- **SentencePiece** (Kudo & Richardson, 2018) is a library that runs BPE or Unigram on raw text, treating the space as a symbol (`▁`), so it needs no language-specific word splitting. LLaMA 1 and 2 use it with 32,000 BPE tokens; LLaMA 3 switched to 128,256 tokens built with OpenAI's `tiktoken`.

The algorithm matters less than the vocabulary size and the text it was built from.

## 9.4 Choosing a Vocabulary Size

- **Bigger vocabularies make sequences shorter**, which is cheaper (attention cost grows with length, section 6.6) and fits more text in a fixed context window.
- **Bigger vocabularies make the model's ends bigger.** The embedding table and output layer each hold $|V| \times d_{\text{model}}$ numbers, and the softmax runs over all $|V|$ at every position. At $d_{\text{model}} = 4096$, going from 32,000 to 128,000 tokens adds about 393 million parameters to each.
- **Rare tokens are poorly trained.** A token seen a handful of times gets a handful of updates, and its embedding stays near random.

Vocabularies have grown with models, since the end matrices become a smaller share while the length savings apply to every token: GPT-2 used 50,257, LLaMA 2 32,000, LLaMA 3 128,256, and Gemma 256,000.

The text the tokenizer was built from matters as much. One built mostly from English learns few merges for other languages, so the same sentence can cost two to five times as many tokens in a language it saw little of: less text per context window and a higher price per request.

> **Browser lab** `bpe-compression`: an experiment that runs in the reader's browser on the web page: https://transformers-and-math.drmhse.com/modules/09-tokenization#lab-bpe-compression

## 9.5 Quirks That Tokens Cause

The model sees token ids, never letters, and several apparent failures of reasoning are really tokenization:

- **Spelling and counting letters.** `strawberry` may be one or two tokens, and the model has no direct view of the letters inside, so "how many r's are in strawberry?" is harder than it looks.
- **Arithmetic.** `1234` might be one token and `12345` two (`123`, `45`), so digits do not line up in consistent columns and carrying is hard to learn. Some tokenizers, LLaMA's among them, split numbers into single digits for this reason.
- **Leading spaces.** A prompt ending in a trailing space forces the next word to start without its usual leading-space token, a pattern rarely seen in training, and output often degrades.
- **Under-trained tokens.** A token merged from text later filtered out of the training data stays near random, and prompting with it can produce erratic output. Such "glitch tokens" exist in several released models.

When a model fails a simple-looking task, check how the input was tokenized first.

## 9.6 What the Reference Implementation Tokenizes

The reference implementation uses a **character** vocabulary of 67 tokens: `<PAD>` (padding), `<UNK>` (unknown), and every distinct character in the training text, sorted.

```python
# src/infra/tokenizer.py
self.stoi = {self.PAD_TOKEN: 0, self.UNK_TOKEN: 1}
for character in sorted(set(text)):
    self.stoi[character] = len(self.stoi)
```

This keeps the tokenizer out of the results, so the labs' parameter counts and losses reflect the architecture. A 50,257-token vocabulary would not fit anyway: at width 64, its embedding table alone would be about 3.2 million numbers, nearly 30 times the whole 112k-parameter model.

Its costs are exactly what BPE fixes:

- **Unseen characters fail.** The Shakespeare text has no accented letters, so `"café"` gives `c`, `a`, `f`, `<UNK>`.
- **Sequences are longer.** An English word is five to six characters with its space, against about 1.3 BPE tokens, so text takes roughly four times the context.
- **It does not transfer** to any other text.

> **Measured** (lab 1a). The vocabulary has 67 tokens, and its embedding table holds 4,288 of the model's 112,323 parameters, under $4\%$. At that size the vocabulary is a design choice, not a cost worth worrying about.

## Exercises

**Exercise (check).** Why does a byte-level BPE tokenizer never need an `<UNK>` token?

*Solution:* Every piece of text, in any language, is stored as a sequence of UTF-8 bytes, and the tokenizer's base vocabulary contains all 256 byte values. Any input can therefore be written with base tokens at worst, so nothing is ever unknown.

**Exercise (apply).** The corpus is `aaab aab ab` (three words). Run BPE by hand: what are the first two merges?

*Solution:* Count adjacent pairs within words: `aaab` has `aa` twice and `ab` once; `aab` has `aa` once and `ab` once; `ab` has `ab` once. So `aa` and `ab` are tied at 3 each; break the tie by taking the first found, `aa`. After merging, the words are `aa a b`, `aa b`, `a b`; the pairs are `(aa, a)` 1, `(a, b)` 2, `(aa, b)` 1, so the second merge is `ab`.

**Exercise (apply).** With a character vocabulary, how many tokens does `café` cost if `é` was never seen in training? How many does a byte-level tokenizer with no merges need?

*Answer:* 5 (within 0)

*Solution:* The character vocabulary gives 4 tokens, `c`, `a`, `f`, `<UNK>`, and loses the `é`. A byte-level tokenizer with no merges needs one token per UTF-8 byte: `é` is two bytes, so 5 tokens, and nothing is lost.

**Exercise (apply).** How many parameters does a 256,000-entry embedding table take at $d_{\text{model}} = 3584$, in millions?

*Answer:* 917.5 (within 1)

*Solution:* $256{,}000 \times 3{,}584 = 917{,}504{,}000$, about 918 million. Gemma ties its output layer to this table, so it pays the cost once rather than twice.

**Exercise (extend).** Why might a model answer "what is 4831 + 2967?" less reliably than "what is 4831 plus 2967, digit by digit?" Relate your answer to tokenization.

*Solution:* With a merging tokenizer, `4831` and `2967` may be split into pieces of different lengths that do not correspond to digit positions, so the model cannot reliably line up thousands, hundreds, tens and units, and carrying is hard to learn. Asking it to work digit by digit makes it write the digits out separately, often as single-digit tokens, which line up consistently. (Section 22.1 discusses another reason writing out intermediate steps helps.)

### Core Academic References
- **Sennrich, Haddow & Birch (2016)**: *Neural Machine Translation of Rare Words with Subword Units* (BPE). ACL 2016. [arXiv:1508.07909](https://arxiv.org/abs/1508.07909)
- **Schuster & Nakajima (2012)**: *Japanese and Korean Voice Search* (WordPiece). ICASSP 2012.
- **Kudo (2018)**: *Subword Regularization* (Unigram). ACL 2018. [arXiv:1804.10959](https://arxiv.org/abs/1804.10959)
- **Kudo & Richardson (2018)**: *SentencePiece*. EMNLP 2018. [arXiv:1808.06226](https://arxiv.org/abs/1808.06226)
- **Petrov et al. (2023)**: *Language Model Tokenizers Introduce Unfairness Between Languages*. NeurIPS 2023. [arXiv:2305.15425](https://arxiv.org/abs/2305.15425)
- **Land & Bartolo (2024)**: *Fishing for Magikarp: Automatically Detecting Under-trained Tokens in Large Language Models*. [arXiv:2405.05417](https://arxiv.org/abs/2405.05417)