Tokenisation: words, characters, subwords

The previous lesson, on the problem of representing language, ended with a loose thread: there we wrote the vocabulary $V$ as if its elements came ready-made. They don't. That list has to be built, and building it forces an earlier decision: where one unit of text ends and the next begins. Nobody makes that decision for you, and the language does not come with it settled. This is called tokenisation, and each unit it produces is a token.

Tokenising is choosing where to cut, and there are three natural answers. Cut by words, which is how you read. Cut by characters, which is how the file is stored. Or cut by word-pieces, by subwords: a middle path that can look unintuitive at first but that most modern language models use today. The explorable below cuts one sentence all three ways and shows, next to each cut, how many tokens that same text takes. Write a sentence of your own and compare the three numbers.

Each cut produces a different vocabulary, and sequences of very different lengths. Hold on to that before going on: there is no true tokenisation waiting to be discovered.

The trade-off between vocabulary size and sequence length

Fix the alphabet $\Sigma$ first: the set of characters that can appear. For English that is the letters, the digits, the punctuation and the space, plus the accented letters that ride in on borrowed words like naïve and café.

That set has a trap worth disarming before counting anything. Unicode allows two spellings for the same accented letter: the ï in naïve can be a single character, or an i followed by a diaeresis drawn over the one before it. On screen they look the same; to $\Sigma$ they are different things, and one of the two takes two positions instead of one. So the text is normalised before tokenising, to the form in which each accented letter is a single character: its Normalization Form C (NFC). Without that step, two texts identical to the eye produce different tokenisations, and the vocabulary ends up holding stray diacritics.

A text isn't one character but a run of them, and to talk about all the strings that can be written over a set of symbols there is a standard notation, which we will use from here on. It is written with an asterisk: $\Sigma^{*}$ is the set of all finite strings made of characters from $\Sigma$, the empty string included. naïve, tokenisation and The naïve boy plays. are all elements of $\Sigma^{*}$; the asterisk says nothing about length, only that it is finite. When the empty string gets in the way we write $\Sigma^{+}$, which is the same thing without it. And the asterisk works for any set, not only the alphabet: $V^{*}$ is the set of finite sequences of tokens from $V$.

With that, a text is an element of $\Sigma^{*}$ and a tokeniser is a function that turns it into a sequence of vocabulary elements:

Each token is therefore a non-empty string of characters, and the vocabulary $V$ is not declared by hand: $\tau$ induces it by running over a corpus, the collection of texts gathered in advance to build it.

From that comes something the rest of the block takes for granted. Each entry of $V$ is a token, and what it is depends on $\tau$: with a word tokeniser the entries are whole words, and with a subword one they are word-pieces, so that unhappiness can span three. A vocabulary entry is therefore not the same thing as a word.

We ask two things of $\tau$. Determinism, for the same reason as in the previous lesson, on representing language: if $\tau$ cut differently today than yesterday, what the model learned would stop matching what it receives. And reconstruction: concatenating the tokens has to give back the original text, save whatever convention was adopted for the spaces. That is what separates cutting from cleaning. A tokeniser that also lowercases everything, or strips the accents, no longer divides the text but alters it: after that résumé and resume are the same unit, and the distinction was lost before the model ever saw it. Everything $\tau$ discards, the model will never see again.

Now the trade-off itself, which falls out of counting characters. Take a corpus with $C$ characters in all, summed over its documents, and apply a tokenisation $\tau$ that breaks it into $T$ tokens $u_1, \dots, u_T$. Write $\lvert u \rvert$ for the length, in characters, of the token $u$. The tokens are pieces of the text itself, so if $\tau$ keeps every character (the reconstruction condition with no conventions), their lengths sum to the whole text:

If it discards the spaces, the sum falls a little short of $C$, and you will see that in the cell.

Write $\bar{\ell}$ for the mean length of a token:

The sum there is the one we set equal to $C$ a moment ago, so

This identity sums up the first half of the trade-off. The text fixes $C$, so $T$ and $\bar{\ell}$ cannot vary independently. Choose shorter tokens and $\bar{\ell}$ drops while the sequence holds more tokens; choose longer ones and the opposite happens. With a character tokeniser, $\bar{\ell} = 1$ and $T = C$. With a word tokeniser, $\bar{\ell}$ runs to around four or five characters, so the sequence comes out roughly that many times shorter.

And the other end of the trade-off, the size of $V$? If we fix a length $\ell$, the number of distinct strings that can be formed over an alphabet $\Sigma$ is

That is, the pool of candidates for the vocabulary grows exponentially with the length of the units. The language uses only a small fraction of those combinations (the vast majority of five-letter strings are not English words), but the tendency is the same: the longer the chosen units, the larger the space the vocabulary is drawn from, and so the larger it tends to be.

Fixing the vocabulary and letting the algorithm choose the units

The answer to this trade-off is the middle row of the table, the subwords, and its $\lvert V \rvert$ cell says what it amounts to: chosen in advance. Instead of letting the vocabulary size fall out of the tokenisation, you fix it ahead of time (say, 30,000 tokens) and let an algorithm decide which units will fill it. The most widespread is byte-pair encoding (BPE): it starts by treating each character as a unit and repeatedly merges the most frequent adjacent pair in the corpus, until it reaches the fixed size. Frequent sequences end up fused into a single piece, and rare ones stay split into pieces that are themselves frequent. That is why a word the algorithm never saw still has a representation: it is written with known pieces. The details of BPE are out of scope here; the explorable above shows its result, which is what matters here.

Two tokenisers in Python, over the same corpus

The identity $T = C/\bar{\ell}$ is worth seeing as numbers rather than algebra. The cell tokenises a short English corpus both extreme ways, by words and by characters, and for each prints $T$, the vocabulary size and the mean length. Look at three things: that $T \cdot \bar{\ell}$ reproduces $C$, that the vocabulary sizes run opposite to $T$, and the last two lines. Run it as it stands, then swap the corpus for a text of your own.

With characters, $T \cdot \bar{\ell}$ gives $C$ exactly. With words it falls short, and the difference is the spaces: the tokeniser threw them away, so the text can no longer be reconstructed from the tokens. That is the reconstruction condition broken for the sake of convenience, and it is why subword tokenisers mark, in one way or another, where the spaces were. The ## you see in the explorable marks that a piece continues the word before it (the absence of a space), and with that the space is recovered.

The second-to-last line cuts a sentence full of contractions and possessives: Don't comes out as three tokens (Don, an apostrophe, t), and the possessive 's is torn off teacher the same way. The tokeniser cuts at every character that is not a letter; it has no notion that an apostrophe can bind a contraction or a possessive, and it does not need one, as long as it always cuts the same way. The last line is more uncomfortable: of the five tokens of a new and perfectly ordinary sentence, three are not in $V$.

Test your intuition

Four questions on what you have seen: the trade-off between vocabulary and length, what cutting below the word buys you, the trap Unicode has in store for a character tokeniser, and one count by hand.

With the tokenisation settled, the vocabulary stops being an abstraction and becomes a concrete list of tokens. That list is always finite, because it is built from a corpus somebody gathered at some point. And here the demand for totality from the lesson on the problem of representing languageBlock 1 · Lesson 1The problem of representing languageA network operates only on real numbers. Text does not. This is the precise statement of the problem the whole block lives on. comes back: $r$ had to be defined for any word that arrives. The last line of the cell shows the hole with nothing to soften it: cryptocurrency is not in $V$, and on it $r$ is worth nothing, because it is not even defined.

That leaves three linked questions, and they are the three of the next lesson. How many distinct tokens really appear in a corpus, and how often? The answer has a very characteristic shape that decides everything else. Which of them make it into $V$: keeping them all is expensive, because each needs its own representation $r(w)$, but every token you leave out is text the model can no longer read. And what to do when one of the tokens left out arrives. That is the lesson on vocabulary, frequency and the problem of out-of-vocabulary words (OOV).