Tokenization: BPE & Friends
How text becomes tokens, and why it matters.
In the tokenizer you are about to use, "The children are reading a story." costs 7 tokens, its Russian translation 29, and the number 6912 splits as 6 | 9 | 12. Tokenization is the one stage of a language model that is usually not learned end to end, and its choices leak into cost, fairness, arithmetic and spelling. This lesson treats tokenizers as compression algorithms, with the dynamic programs, approximation theorems and open problems that come with that view.
What you’ll learn
- Specify a tokenizer formally (normalization, pre-tokenization, vocabulary, encoder, decoder) and measure it by compression.
- Prove that minimal-length segmentation over a fixed vocabulary is a shortest-path problem, and explain why BPE's merge-order encoding can be longer.
- State BPE's complexity and its approximation and hardness results, and derive WordPiece's merge criterion and the Unigram LM tokenizer's EM, Viterbi and sampling algorithms.
- Quantify tokenization side effects (multilingual premiums, digit splitting, under-trained tokens) and describe tokenizer-free alternatives.
Tokenizers, precisely
If the base symbols are characters, a character missing from still needs an unknown token, or a byte fallback that spells it out as UTF-8 bytes, as LLaMA's tokenizer does. Byte-level vocabularies (GPT-2; Radford et al., 2019) start from the 256 byte values, so every UTF-8 string is encodable. Many token sequences decode to the same string; the encoder picks one, its canonical encoding, and models are trained only on canonical encodings, although they assign probability to the others too (Cao & Rimell, 2021).
Make positions the nodes of a directed acyclic graph, with an edge whenever . Segmentations are exactly the paths from to , and the number of tokens is the path length. A trie of finds all edges out of in at most steps:
Nodes are already in topological order, so a single left-to-right pass computes the shortest distance to every node; by induction on , is the minimal token count for the prefix . Single symbols guarantee an edge , so is finite:
BPE's encoder does not solve this problem: it replays the merges in the order they were learned, a greedy, local procedure. In the widget's engine, trained on its corpus and default sentence with 200 merges, " younger" encodes as " y" + "oun" + "g" + "er", four tokens, although " you" + "ng" + "er" uses three tokens from the same vocabulary. Shorter is not automatically better for modeling, though: what matters is that the model always sees the same, consistent segmentation. Bostrom and Durrett (2020) found that Unigram LM segmentations track morphology more closely than BPE's and can help downstream tasks.
A BPE tokenizer encodes a word into 4 tokens, yet its own vocabulary admits a 3-token segmentation of the word. Why does it output 4?
- The 3-token segmentation must contain an unknown token
- Its encoder applies the learned merges in training order, and that greedy replay need not minimize the token count
- BPE always maximizes the number of tokens to keep pieces short
- The vocabulary changes depending on the surrounding words
Show the answer
B. Its encoder applies the learned merges in training order, and that greedy replay need not minimize the token count
Encoding replays merges by rank. An early merge can claim symbols that a later, longer token would have used, so the canonical encoding can be longer than the shortest-path segmentation.
BPE and WordPiece: greedy merging
BPE training counts adjacent pairs within pre-token chunks, weighted by chunk frequency, and merges the most frequent pair, times. Rescanning after every merge costs for a corpus of symbols; tracking pair counts incrementally in a priority queue brings it to (Zouhar et al., 2023). Encoding a chunk of symbols with a heap of adjacent pairs keyed by merge rank takes . What does greedy merging achieve?
WordPiece (Schuster & Nakajima, 2012; used in BERT) instead adds the unit that most increases the training likelihood of a unigram model over units. With maximum-likelihood probabilities , the log-likelihood of the tokenized corpus is
Merging the adjacent occurrences of replaces two tokens by one in each. Ignoring the small changes this causes in , and , the gain is the pair count times its pointwise mutual information:
BPE ranks pairs by frequency alone. Widely used open implementations of WordPiece rank by , the association alone, which prefers pairs whose parts rarely occur apart. (The original system's exact criterion is not public.) WordPiece encodes each word greedily, longest match first.
The Unigram LM tokenizer and subword regularization
Kudo (2018) made segmentation probabilistic. A string's probability sums over its segmentations , each a product of token probabilities: . Training alternates EM over with pruning: start from a large vocabulary (for example, frequent substrings), and after each EM run remove the tokens whose removal lowers the likelihood least, say 20% per round, always keeping single characters, until the target size is reached. Encoding is the Viterbi path, the shortest-path program with costs . The SentencePiece library (Kudo & Richardson, 2018) implements both this tokenizer and BPE directly on raw text, treating the space as an ordinary symbol, which makes tokenization reversible and language independent.
The forward variable sums over all segmentations of the prefix ; it costs like the shortest path, with a sum in place of the minimum:
With the analogous backward variable , the E-step's expected count of token sums over its occurrences in the lattice; the M-step sets :
Subword regularization samples a segmentation instead of taking the best one, walking back from and choosing each last token with its posterior probability (forward filtering, backward sampling); Kudo also sharpened or flattened the distribution with an exponent . Training on sampled segmentations is a data augmentation that improves robustness, especially for low-resource translation; BPE-dropout (Provilkov, Emelianenko & Voita, 2020) gets a similar effect by randomly skipping merges.
A Unigram LM tokenizer has , and . Given the string "ab", what is the posterior probability, in percent, of the single-token segmentation [ab]?
Show the answer
71 %
The segmentations are [ab] with probability and [a][b] with , so and the posterior of [ab] is . Viterbi always returns [ab]; subword regularization (with exponent ) samples [a][b] about 29% of the time.
Side effects you can measure
Real tokenizers show the same effects at scale.
- Multilingual premiums. For the same content, Petrov et al. (2023) measured tokenized lengths differing by up to roughly 15× across languages and tokenizers. Speakers of disadvantaged languages pay more per request, wait longer, and fit less text into a fixed context window.
- Numbers. Merges chunk digit strings by frequency, not place value. PaLM and LLaMA split numbers into single digits for this reason, and Singh and Strouse (2024) found that forcing right-to-left three-digit chunks, for example with commas, markedly improved the arithmetic of models whose tokenizers chunk numbers left to right.
- Spelling. A model sees token ids, not letters, so counting or reversing characters requires facts about tokens' spellings that are only indirectly in the training signal.
- Under-trained tokens. Tokens that are frequent in the tokenizer's training data but rare in the model's leave embeddings that barely moved during training, and can trigger erratic outputs; Land and Bartolo (2024) detect them automatically from the embedding matrix.
Key takeaways
- A tokenizer is normalization, pre-tokenization, a vocabulary, an encoder and a decoder; byte-level vocabularies make every string encodable, and models see only canonical encodings.
- Minimal segmentation over a fixed vocabulary is a DAG shortest path (), and the same program with costs is Unigram Viterbi; BPE's merge replay can produce more tokens.
- Choosing optimal merges is APX-complete, yet greedy BPE is a constant-factor approximation; WordPiece ranks pairs by a PMI-like likelihood gain instead of raw frequency.
- The Unigram LM tokenizer learns token probabilities by EM over a segmentation lattice and enables subword regularization by sampling segmentations.
- Tokenization creates multilingual cost premiums, place-value-blind digit chunks, spelling blind spots and under-trained tokens.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Over a fixed vocabulary that contains every single character, with tokens of length at most , what does it cost to find a segmentation of an -character string into the fewest tokens?
- It is NP-hard, like finding optimal merges
- trie steps, by dynamic programming over positions
- , since there are exponentially many segmentations
- with BPE's merge replay, which is always optimal
Show the answer
B. trie steps, by dynamic programming over positions
Segmentations are paths in a DAG on positions with at most edges, and shortest paths in a DAG take one pass. Hardness appears only when the vocabulary itself is being chosen.
Two pairs each occur times. In pair 1 both parts are very common elsewhere; in pair 2 both parts almost always occur together. How do BPE and a WordPiece-style score rank them?
- Both prefer pair 1
- BPE prefers pair 2 and WordPiece pair 1
- BPE treats them as tied, while WordPiece prefers pair 2, whose parts rarely occur apart
- Both prefer pair 2
Show the answer
C. BPE treats them as tied, while WordPiece prefers pair 2, whose parts rarely occur apart
BPE's score is the raw count, equal here. The WordPiece score divides by the parts' counts, which are smaller for pair 2, so it favors the strongly associated pair.
A tokenizer trained mostly on English text encodes a Russian sentence in four times as many tokens as its English translation. Which consequence does not follow?
- Processing the Russian text costs more under per-token pricing
- Less Russian text fits in the same context window
- Generating the Russian text takes more decoding steps
- The model must assign lower probability to the Russian sentence, because it has more tokens
Show the answer
D. The model must assign lower probability to the Russian sentence, because it has more tokens
Probabilities of whole strings are not penalized by token count as such: a model can give a long token sequence high probability if each step is predictable. The other three consequences follow directly from the length.
Further reading
- R. Sennrich, B. Haddow & A. Birch, "Neural machine translation of rare words with subword units," ACL (2016).
- T. Kudo, "Subword regularization: Improving neural network translation models with multiple subword candidates," ACL (2018).
- V. Zouhar, C. Meister, J. L. Gastaldi, L. Du, T. Vieira, M. Sachan & R. Cotterell, "A formal perspective on byte-pair encoding," Findings of ACL (2023).
- A. Petrov, E. La Malfa, P. H. S. Torr & A. Bibi, "Language model tokenizers introduce unfairness between languages," NeurIPS (2023).
- T. Kudo & J. Richardson, "SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing," EMNLP: System Demonstrations (2018).