Chapter 5Subword Tokenisation

The vocabulary problem

Chapter 3 left us with an uncomfortable fact. The vocabulary of a natural language never closes.

Heaps’ law guarantees it. However much text a system has seen, the next document can hold a word it has not. For a word level system, every such word is a small crisis.

The classical remedy is to map everything unknown to a single <unk> symbol, as in Chapter 10. That is honest bookkeeping and terrible epistemology. It declares unfathomable, Vaccination and iPhone17 to be the same word. All identity is lost at exactly the moment identity matters most.

The opposite extreme is available, and instructive. Work at the character level and the vocabulary problem vanishes. A few dozen symbols cover everything anyone will ever type.

The price is that every regularity we care about is now smeared across long sequences. The model has to rediscover, character by character, that t-h-e is a unit, before it can start learning what the does. Sequences get roughly five times longer. A dependency that spanned three words now spans fifteen symbols.

So neither words nor characters will do. The resolution sounds like a compromise but is really a synthesis. Let the data decide what the units are.

Frequent words should survive as single tokens, because statistically they have earned it. Rare words should break into pieces that are themselves frequent. Unfathomable becomes something like un + fathom + able. A novel surname becomes pronounceable fragments. In the worst case, anything at all becomes single characters.

A vocabulary of such subword units can be closed, modest in size, and still able to represent every string. Every large language model you have used is built on this idea.

Byte pair encoding

The dominant algorithm is byte pair encoding, or BPE. It is almost embarrassingly simple. It was borrowed from a 1994 data compression technique and repurposed for translation by Sennrich, Haddow and Birch in 2016.

It learns a vocabulary by merging, greedily and repeatedly:

1. Split every word in the training corpus into characters. Append an end of word marker </w> to each word. The starting vocabulary is the character set.

2. Count every adjacent pair of current symbols, across the whole corpus. Each occurrence counts with its word’s frequency.

3. Merge the most frequent pair into one new symbol. Add that symbol to the vocabulary and record the merge as a rule.

4. Repeat from step 2, for a fixed number of merges. That number is the algorithm’s only real hyperparameter.

One bookkeeping rule matters enough to state precisely. Without it, two correct implementations will disagree. When several pairs tie for the highest count, merge the lexicographically smallest pair.

Ties are not rare. In small corpora they are the norm. And the tie break decides every merge that follows. This is the convention the course autograder enforces. State it, and BPE becomes exactly reproducible.

A worked run, step by step

Take the classic micro corpus. Four words, each with a frequency:

We will run five merges. At every step we do the same three things. Count all adjacent pairs. Pick the winner, breaking ties lexicographically. Rewrite the corpus with that pair joined.

Every count below is weighted by the word’s frequency. A pair inside newest contributes 6, not 1. That weighting is the single most common mistake in a hand simulation.

Step 0: split into characters.

Every word becomes its characters plus the end of word marker.

Step 1: merge e s.

Count every adjacent pair. The seven highest are:

Seven more pairs exist and all score below 5.

Three pairs tie at 9. The tie break earns its keep at the very first step. Sorted as tuples, $\texttt{(e,s)} < \texttt{(s,t)} < \texttt{(t,</w>)}$, so e s wins.

Step 2: merge es t.

Recount. The merge changed which pairs exist, so e s and s t are both gone, replaced by es t.

Now only two pairs tie at 9: es t and t </w>. Since $\texttt{(es,t)} < \texttt{(t,</w>)}$, the winner is es t.

Step 3: merge est </w>.

Recount again. This time there is no tie. est </w> stands alone at 9, ahead of l o and o w at 7.

This is the interesting moment. The suffix est</w> completed in three merges, before the algorithm touched the stem of low at all. Nothing told it that -est is an English suffix. It won because it was frequent.

Step 4: merge l o.

With the 9s exhausted, the top count drops to 7, and we get a second tie. Both l o and o w score $5+2=7$. Sorted, $\texttt{(l,o)} < \texttt{(o,w)}$, so l o wins.

Step 5: merge lo w.

The merge just made lo w available, and it inherits the same count of 7. No tie this time.

The result.

Five merges, in order. This ordered list is the tokeniser.

Three of the five steps involved a tie. That is why the tie break rule is not a footnote. Without it, three of these five merges are undefined, and every merge after the first bad one is wrong too.

The words now tokenise like this:

The algorithm found a productive English suffix, est</w>, and a whole common word, low. And lower, which is rarer, still decomposes into a known stem plus leftovers.

Nobody supplied a single linguistic fact. -est simply paid for itself in compression. That is the entire theory of BPE in one sentence.

Using the tokeniser.

Applying a trained tokeniser to new text replays the same logic. Split the word into characters. Then apply the recorded merge rules in the order they were learned, wherever they match.

Try lowest, a word the training corpus never contained. Apply the five rules in order and watch it assemble.

An unseen word came out as two meaningful pieces. A stem, low, and a suffix, est</w>. That is the whole point of subwords.

Try it yourself. The script behind every table in this run is code/worked_examples/bpe.py. Running it with --no-tiebreak takes the lexicographically last tied pair instead of the first. All five merges come out different, and so does the tokenisation of every word. That is the clearest demonstration of why the rule matters.

Run it in ColabNotebookSource

The rules must be applied in learned order. Rule 2 can only fire because rule 1 has already produced es. Apply them in a different order and you get a different, wrong answer.

Fertility: measuring a tokeniser

How do we judge a tokeniser? The workhorse diagnostic is fertility, the average number of tokens produced per word:

$$\begin{equation} \text{fertility} \;=\; \frac{\#\text{tokens}}{\#\text{words}}. \label{eq:fertility} \quad\text{(5.1)} \end{equation}$$

A fertility of $1.0$ means every word survived whole. A fertility of $2.0$ means words are being cut in half on average. Character level tokenisation of English runs near $5$.

Fertility is a compression gauge. Like all compression, it reflects the fit between training data and use. A BPE vocabulary learned on news text has low fertility on news. On medical abstracts, legal boilerplate or another language, its fertility climbs. The merges it learned are the wrong merges for that text.

So rising fertility is often the first measurable symptom of domain shift. It is cheaper to compute than any accuracy number.

Fertility is also, bluntly, money. Modern LLM APIs price by the token, and context windows are budgeted in tokens. Text that tokenises at fertility $1.8$ costs $50\%$ more than the same content at $1.2$, and fits $33\%$ less into the window.

Multilingual users often notice that their language costs more per sentence than English on the same model. What they are measuring is the fertility of a tokeniser whose training data under-represented their language. Tokenisation looks like invisible plumbing. It has an equity dimension.

Three practical notes round out the picture.

First, modern systems usually run BPE over bytes rather than Unicode characters. This is byte level BPE, as in GPT-2 and its descendants. All 256 bytes sit in the base vocabulary. So no string in any script can ever be out of vocabulary, and <unk> disappears from the system entirely.

Second, BPE has siblings. WordPiece uses likelihood driven merges and is used by BERT. The unigram language model tokeniser prunes a large vocabulary instead of growing a small one, and reaches you through SentencePiece. They differ in the selection criterion and share the subword philosophy.

Third, tokenisation is where some of a model’s oddest behaviour is born. Think of a model that cannot reverse a word, count its letters, or do digit arithmetic. Often the cause is the tokeniser. It welded those characters into opaque units before the model ever saw them. So when an LLM’s behaviour on a string puzzles you, the first thing to inspect is the string as the model sees it, in tokens.

Where this leaves us

Subword tokenisation closes the vocabulary problem that Chapter 3 opened. We get a fixed, modest vocabulary that can still spell anything, with frequent units kept whole so downstream statistics have something solid to bind to.

From here on, every model in this book operates on tokens. The n-gram models of Chapter 10, the embeddings of Part II, the transformers of Part IV. Every perplexity, similarity and attention weight we compute is a statement about token sequences.

Remember that when you compare numbers across systems. Two models with different tokenisers are answering subtly different questions about the same text.

Further reading.

is the paper that made BPE standard for neural machine translation. present SentencePiece and the unigram alternative. situate tokenisation in the broader text normalisation pipeline, in Chapter 2 of the third edition draft.