Chapter 5Subword Tokenisation

The vocabulary problem

Chapter 3 left us with an uncomfortable fact, which is that the vocabulary of a natural language never closes. Heaps’ law guarantees it, because however much text a system has seen the next document can hold a word it has not, and 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, which is honest bookkeeping and terrible epistemology. It declares unfathomable, Vaccination and iPhone17 to be the same word, so 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 entirely, since 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, because 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, so a dependency that spanned three words now spans fifteen symbols.

Neither words nor characters will do, then, and the resolution sounds like a compromise while being really a synthesis: let the data decide what the units are.

Frequent words should survive as single tokens because statistically they have earned it, while rare words should break into pieces that are themselves frequent, so that unfathomable becomes something like un + fathom + able and 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, and every large language model you have used is built on this idea.

Byte pair encoding

The dominant algorithm is byte pair encoding, or BPE, and it is almost embarrassingly simple. It is one of a family of subword methods, and the siblings that share its idea appear later in this chapter. 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, because without it two otherwise correct implementations will disagree. When several pairs tie for the highest count, merge the lexicographically smallest pair.

Ties are not rare, and in small corpora they are the norm, while the tie break decides every merge that follows. This is the convention the course autograder enforces, and once it is stated 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, and at every step we do the same three things: count all adjacent pairs, pick the winner while breaking ties lexicographically, then rewrite the corpus with that pair joined.

Every count below is weighted by the word’s frequency, so a pair inside newest contributes 6 rather than 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. There are fourteen distinct pairs in all, and the eight highest are these:

Six more pairs exist, and none of them scores above 5. Note that w </w> is one of those six, at 5, coming from low alone.

Three pairs tie at 9, so 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, because the merge changed which pairs exist, so e s and s t are both gone and es t has taken their place.

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

Step 3: merge est </w>.

Recount again, and this time there is no tie, because est </w> stands alone at 9 while the next best, l o and o w, are back at 7.

This is the interesting moment, because the suffix est</w> completed in three merges, before the algorithm had touched the stem of low at all. Nothing told it that -est is an English suffix, and it won purely 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, since 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 previous merge has just made lo w available, and it inherits the same count of 7, with no tie this time.

Five merges, in order, and this ordered list is the tokeniser.

Three of the five steps involved a tie, which 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 as well.

The words now tokenise like this:

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

Nobody supplied a single linguistic fact, and -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, and apply the five rules in order to watch it assemble.

An unseen word came out as two meaningful pieces, a stem low and a suffix est</w>, and 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 the order they were learned, because rule 2 can only fire once rule 1 has already produced es. Apply them in a different order and you get a different and 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 and a fertility of $2.0$ means words are being cut in half on average, while character level tokenisation of English runs near $5$.

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

Rising fertility is therefore often the first measurable symptom of domain shift, and it is cheaper to compute than any accuracy number.

Fertility is also, bluntly, money, because 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, and what they are measuring is the fertility of a tokeniser whose training data under-represented their language. Tokenisation looks like invisible plumbing, and it has an equity dimension.

Three practical notes round out the picture.

First, modern systems usually run BPE over bytes rather than Unicode characters, which is byte level BPE as used 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 the tokeniser behind BERT, while 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, where the cause is often the tokeniser having welded those characters into opaque units before the model ever saw them. 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.

What the tokeniser decides about the model

Fertility is a property of text, whereas the merge count is a property of the model, and it is a larger one than it looks. The number of merges is not a tuning knob that can be turned freely, because it sets the size of the largest single matrix the model carries.

The merge count is the vocabulary

Run BPE over bytes and the base vocabulary is all 256 byte values, after which every merge adds exactly one new symbol. GPT-2 makes the arithmetic visible.

That is the published figure, and it is the merge loop of Section 5.2.1 run fifty thousand times on web text.

Every merge is a row in the embedding matrix

A model stores one vector per vocabulary item, so the embedding matrix is $V \times d$ where $d$ is the model width. GPT-2 small is 768 wide, which means a single merge costs 768 parameters.

Almost a third of that model is the tokeniser’s vocabulary, and where the output projection is not tied to the input embedding it costs the same again.

There is a genuine trade-off here, and it has two sides. More merges give longer subwords and lower fertility, so sequences get shorter, while more merges also give a larger embedding matrix and a wider softmax. Parameters are being traded against sequence length, and the best point depends on the text the model will actually meet, which is the same argument fertility makes.

Fertility becomes compute, and not linearly

Self attention compares every token with every other token, so its cost grows with the square of the sequence length, which means a tokeniser that is somewhat worse per word turns out considerably worse per document. Take a document of 1000 words.

A tokeniser 58 per cent worse per word costs 151 per cent more attention work, and that gap is the strongest practical argument for measuring fertility at all.

Memory during generation

A model generating text keeps a key and a value vector per token per layer, and that store is the KV cache, which is usually what limits how many requests one server can hold at once.

Every token the tokeniser fails to merge costs another 36 KB of cache, and that is for one request on one small model, with the figure far higher on a large one.

The context window is measured in tokens and never in words, so fertility also decides how much of a document fits inside it.

Two readers send the same document to the same model, and one is truncated while the other is not, with the only difference being how well the tokeniser fits their language. Section 5.3 called that an equity dimension, and these are the numbers underneath it.

Where this leaves us

Subword tokenisation closes the vocabulary problem that Chapter 3 opened, giving us a fixed and 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, whether the n-gram models of Chapter 10, the embeddings of Part II or the transformers of Part IV, and every perplexity, similarity and attention weight we compute is a statement about token sequences.

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

Further reading.

Sennrich et al. (2016) is the paper that made BPE standard for neural machine translation. Kudo and Richardson (2018) present SentencePiece and the unigram alternative. Jurafsky and Martin (2025) situate tokenisation in the broader text normalisation pipeline, in Chapter 2 of the third edition draft. The trainer you are asked to write in Problem 2 exists as tokenizers, the library behind most current models, and sentencepiece is the reference implementation of the unigram alternative.

Code for this chapter

Each one reproduces the tables above. Open it in Colab, change an input and watch which numbers move.

• bpe.pyBPE, five merges

  The whole training run with pair counts and ties, then the learned rules applied to words the corpus never held.

  standard library only Run it in Colab Notebook Source

From Natural Language Processing: From Corpus Statistics to Grounded LLMs, by Ramaseshan Ramachandran.