Tokenization units and byte-pair encoding

Take the six-word string that the rest of this part will keep returning to: set new new renew reset renew. Split it at spaces and you have one token per word. Split it into characters, keeping a marker for each space, and you have one token per character. Split it with the subword vocabulary this part will learn and you get something in between.

Same text, three very different values of N and |V|. That is the whole subject of Tokenization in one example. Tokenization converts raw text into a sequence of tokens, the units that a model or a pipeline operates on, and the choice of unit fixes three things at once: the Vocabulary the model must learn embeddings for, the length of every input, and what the model can represent at all. Earlier parts of this lecture treated the unit as given and asked what a word is. This part reverses the question: given that we may pick the unit, what should we optimise for?

The four criteria pull in different directions, which is why no single unit wins. Coverage asks how often new text contains something the vocabulary cannot represent, the out-of-vocabulary problem from the Zipf and Heaps part: with word tokens the answer is always, because Heaps' law says the word vocabulary never closes. Compactness asks how many tokens the model must process; every token costs attention, memory and, in a hosted API, money. Meaningfulness asks whether one token corresponds to one unit of meaning, which makes downstream tasks such as tagging and parsing easier. Cross-lingual applicability asks whether the same scheme works for Chinese, which has no spaces, and for Arabic, whose clitics glue several words into one whitespace token.

There is also a quieter reason to care. Jurafsky and Martin note that a standardised tokenization is essential for replicability: a perplexity or an F1 score only means something if the units are the same, so the tokenizer is part of the experimental protocol, not a preprocessing detail (SLP3, chapter 2).

Take the word renewed. As a word token it is one unit, but only if it appeared in training; if it did not, it is an unknown. As characters it is 7 letters, eight tokens with the leading space marker, none of which means anything alone. With the subword vocabulary learned later in this part it is four tokens, _re new e d, and the model has seen every one of them before even though it has never seen the word. Those three outcomes are the three granularities, and each buys something by paying for something else.

Words: meaningful, but the vocabulary never closes

Word tokens are the natural first choice. They are meaningful, they line up with dictionaries and with the lexicons that rule-based systems consult, and tasks that need explicit word boundaries, such as part-of-speech tagging, syntactic parsing and lexicon-driven pipelines, are built around them. The problems are the ones the first four parts of this lecture already exposed. "Word" is ambiguous across languages: punctuation, contractions, compounds, clitics and scripts without spaces all give different answers. And the vocabulary is enormous and open-ended. Heaps' law says |V| keeps growing with N, so however large the training corpus, test text brings rare and unseen words, and every one of them is an OOV token the model must lump into a single UNK symbol.

Characters: nothing is unknown, but everything is long

Go to the other extreme and tokenize into characters. The vocabulary is tiny, a few dozen letters for Latin script or, at byte level, exactly 256 values. There is no OOV at all, because any string is spelled from the base symbols, and the tokenizer is robust to spelling variants, typos and OCR noise since a damaged word still shares most of its characters with the clean one. The price is paid in sequence length and in meaning. The 6-word string became 29 tokens, roughly five times longer, and attention cost grows with the square of that length. Two words that sit a sentence apart become dozens of positions apart, so a model with a fixed context window sees less of the surrounding text and must learn dependencies across far longer distances. Meaning is spread across many tokens, so the model must spend capacity learning to reassemble words before it can learn anything about them, which makes training slower. Characters are the right call for noisy text, for extremely low-resource languages where no subword vocabulary can be trusted, and for specialised tasks such as transliteration where the character really is the unit.

Subwords: the middle ground modern models use

Subword tokenization keeps a vocabulary smaller than a word vocabulary and produces sequences shorter than a character sequence, and its decisive property is the third row of the table: an unseen word is composed from pieces that were seen. The GPT-2 paper describes byte-pair encoding as a practical middle ground that interpolates between word-level inputs for frequent symbol sequences and character-level inputs for infrequent ones (Radford et al., 2019). Frequent words stay whole, rare words shatter into recognisable parts, and nothing is ever unknown.

There are two ways to decide what the pieces are. The linguistically natural way is to cut at morphemes, since morphemes carry meaning by definition. But the morphology parts of this lecture showed why that is hard: allomorphy changes the shape of a morpheme by context, non-concatenative morphology interleaves an Arabic root with a pattern rather than concatenating anything, and clitics blur the boundary between word and affix. Morpheme segmentation needs a linguist, or a model, per language, and it remains ambiguous even then. It is useful in some applications but it is not the common approach in modern language models. The language-agnostic way is to learn frequent substrings from data with no linguistic knowledge at all. That is what byte-pair encoding does, and Jurafsky and Martin name BPE and unigram language modelling as the two families widely used in modern language models (SLP3, section 2.4). They work across languages, reduce OOV and stay efficient, which is why the rest of this part is about one of them.

Here is the smallest corpus that shows the whole idea, borrowed from Jurafsky and Martin: the ten-character string A B D C A B E C A B with the vocabulary {A, B, C, D, E}. Look for the pair of adjacent symbols that occurs most often. It is A B, three times. Replace every A B with a new symbol AB and add it to the vocabulary. Now look again.

That loop is the entire training algorithm of byte-pair encoding. The slide's pseudocode, which is Figure 2.6 of SLP3 adapted from Bostrom and Durrett (2020), reads as follows. Start with V equal to the set of unique characters (or bytes) in the Corpus C. Then repeat k times: find the most frequent pair of adjacent tokens tL, tR in C, form the new token tNEW = tL + tR by concatenation, add it to V, and replace every occurrence of tL tR in C with tNEW. Return V. One iteration of the loop is a Merge.

Sennrich, Haddow and Birch, who introduced BPE for neural machine translation, state the consequence plainly: the final symbol vocabulary size is equal to the size of the initial vocabulary plus the number of merge operations, and the number of merges is the only hyperparameter of the algorithm (Sennrich et al., 2016). In the toy example k is 2 or 4. In practice Jurafsky and Martin describe tens of thousands of merges on a very large corpus to produce vocabularies of 50,000, 100,000 or even 200,000 tokens, and GPT-2's vocabulary is 50,257 entries (Radford et al., 2019).

Two practical details shape the counting. First, merges never cross word boundaries. Sennrich's implementation says it does not consider pairs that cross word boundaries for efficiency, so the corpus is stored as a table of distinct words with their counts, and a pair inside a word that occurs twice in the corpus is counted twice. That is exactly why the slides list the toy corpus as four rows with counts rather than as running text. Second, the base symbols can be characters or bytes. GPT-2 works on UTF-8 bytes because a Unicode Code point vocabulary would start at over 130,000 entries, whereas byte-level BPE starts at exactly 256 and, since every byte is in the vocabulary, there can never be an unknown token (Radford et al., 2019; SLP3, section 2.4).

Where the algorithm came from, and its two halves

The name is older than NLP. Philip Gage published byte pair encoding in 1994 as a data compression method: find the most frequently occurring pair of adjacent bytes in the data, replace all instances with a byte that was not in the original data, and repeat until no further compression is possible (Gage, 1994). Sennrich and colleagues adapted it for word segmentation, and two things changed. The units became characters rather than bytes, and the stopping rule became a fixed k rather than exhaustion, so the merges are no longer a throwaway table for one file but a reusable vocabulary shared by every text the model will ever see.

That reuse is why BPE has two parts. The trainer runs once, over the training corpus, and produces the vocabulary together with the ordered list of merges it performed. The encoder runs every time new text arrives and applies that list. The two must never be confused, and the last concept of this part is devoted to the encoder. The simulator below is the trainer: step through the merges and watch the pair table decide each one, then encode a word of your own in its lower panel; the encoder concept returns to that panel on its own.

Now run the BPE trainer by hand on the slide Corpus, set new new renew reset renew, for k = 4. This is the same example as the current SLP3 draft (example 2.11 in section 2.4), so the tables here match both the slides and the book symbol for symbol. The slides show the corpus and the Vocabulary after each Merge but never the pair counts that decided it, so those are worked out in full below.

First the setup. Every word except the first carries a leading space marker, drawn as an open box on the slides and written _ here. The first word, set, starts the string, so it has none. Grouping equal words gives four rows with counts: 2 × _ n e w, 2 × _ r e n e w, 1 × s e t and 1 × _ r e s e t. The initial vocabulary is the seven symbols _, e, n, r, s, t, w, and the corpus holds 2 × 4 + 2 × 6 + 3 + 6 = 29 symbols. Pair counts are weighted by row count: a pair that occurs once inside _ n e w counts 2.

Ties: the pseudocode is silent, so state your rule

Two of the four steps were decided by a tie, and the algorithm as written never says how to break one. Real implementations do have a rule, and it is worth knowing which. The minimal listing in the Sennrich paper (Algorithm 1) picks the best pair with Python's max(pairs, key=pairs.get), which in modern Python (3.7 and later, where dictionaries keep insertion order) returns the first pair encountered while scanning. The released subword-nmt implementation instead selects with max(stats, key=lambda x: (stats[x], x)), which prefers the lexicographically largest pair among the tied ones. On this corpus that rule agrees with the slides at merge 1, choosing (n, e) because n sorts after e, but at merge 3 it chooses (r, e) over (_, r). The Hugging Face course states the first-encountered convention explicitly: when there is a choice of the most frequent pair, the first one encountered is selected. The 🤗 Tokenizers library breaks ties by internal token ids, and the simulator's alphabetical option takes the smallest pair.

The simulator lets you switch between first-seen and alphabetical order, and on this corpus the very first merge already differs: alphabetical order picks (e, w) over (n, e), so the vocabulary ends with ew where the slides have ne, even though the corpus rows after four merges are identical. That is exactly why an exam answer must state its rule.

The order of the rows matters too, because "first encountered" depends on it. The slides list the four rows by count, most frequent first, and so does SLP3. Jurafsky and Martin continue the same trace past the slides: merges five to seven are _new, _renew and se, each decided by a tie at count 2, and merge eight, set, is then forced because (se, t) is the only pair left at 2. The simulator reproduces that order exactly when its rows are listed the same way.

What the space marker does to the learned units

The marker is not cosmetic. Because this deck attaches it to the start of a word, the trainer learned _re, a word-initial piece, and that token is different from a re that occurs inside a word, as in _ c a re, which never merges into _re. Jurafsky and Martin put it this way: the system has essentially induced that there is a word-initial prefix re- (SLP3, section 2.4). This leading-marker convention is the one used by GPT-2, whose byte-level tokenizer shows the space as Ġ, and by SentencePiece, which shows it as ▁ (U+2581); in both, the space rides on the following word (Hugging Face tokenizers documentation). It also explains why set in the trace never carries a marker: it is the first word of the string, so no space precedes it, and s e t and _ s e t are different strings to the trainer.

The original paper did it the other way round. Sennrich, Haddow and Birch appended a special end-of-word symbol to every word so that the original tokenization could be restored after translation, and older SLP3 drafts followed them with the corpus low lowest newer wider new (Sennrich's own listing uses low lower newest widest). Under that convention every word gets a marker, the marker sits at the end, and the prefix would be learned as plain re.

Training is over. The merge list ne, new, _r, _re is frozen, and a word arrives that the trainer never saw: renewed, with its leading space. The encoder does not count anything. It writes the word as characters and replays the four merges, first to last.

Try the same replay on words of your own. The panel below starts from the four slide merges; type newest, reset or an Arabic transliteration, tick sentence-initial to drop the marker, and raise k to watch _new and set collapse into single tokens once merges five to eight exist.

The rule behind the trace is short. To tokenize a new string, start from characters or bytes, apply the learned merges in the order they were learned, and output the resulting subword sequence. The slide calls this "greedy": each merge fires on every place it matches as soon as its turn comes, the encoder never goes back, and it never searches for the longest vocabulary entry. Jurafsky and Martin are exact about what the encoder does not do: it just runs on the test data the merges learned from the training data, in the order they were learned, and the frequencies in the test data play no role, only the frequencies in the training data (SLP3, section 2.4). Sennrich describes the same procedure: split words into sequences of characters, then apply the learned operations to merge the characters into larger known symbols. Because the list is fixed, the output is deterministic: the same input always yields the same tokens, which is what lets a model trained on one tokenization be served with it later.

Order is not a convention but a dependency. Merge 2 joins ne and w, and ne only exists if merge 1 has already run; merge 4 needs _r from merge 3 in the same way. Replaying the list out of order would produce segmentations that never occurred during training, so the model would receive token ids it has no experience of, even though every id is technically in the vocabulary. With tens of thousands of merges, most words in ordinary text are covered by a single token and only rare words break into pieces, which is the interpolation between word and character level that the GPT-2 paper describes (Radford et al., 2019).

One last coverage detail depends on the base symbols. A character-level BPE trained on English letters still has a hole: the Hugging Face course shows mug encoding as [UNK] ug because m never appeared in its toy corpus, so it is not in the vocabulary at all. A byte-level tokenizer starts from all 256 byte values, so any UTF-8 string, including Arabic, emoji and typos, is encodable and the UNK special token is never needed (Radford et al., 2019; Hugging Face tokenizers documentation). The next part looks at what this does to non-Latin scripts.