Tokenization

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 EncodingRun this section

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.

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.

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 SizeRun this section

• 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.

9.5 Quirks That Tokens CauseRun this section

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.

# 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

Core Academic References

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