Simple Algorithm
Artificial Intelligence · Deep Layer · 24 min

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 VV 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).

DerivationProof
  1. edges={(i,j): s[i:j]∈V, 0<j−i≤L},∣edges∣≤nL\text{edges}=\big\{(i,j):\ s[i{:}j]\in V,\ 0<j-i\le L\big\},\qquad\abs{\text{edges}}\le nL

    Make positions 0,…,n0,\dots,n the nodes of a directed acyclic graph, with an edge i→ji\to j whenever s[i:j]∈Vs[i{:}j]\in V. Segmentations are exactly the paths from 00 to nn, and the number of tokens is the path length. A trie of VV finds all edges out of ii in at most LL steps:

  2. f(0)=0,f(j)=min⁡i: s[i:j]∈V(f(i)+1)■f(0)=0,\qquad f(j)=\min_{i:\ s[i{:}j]\in V}\big(f(i)+1\big)\qquad\blacksquare

    Nodes are already in topological order, so a single left-to-right pass computes the shortest distance f(j)f(j) to every node; by induction on jj, f(j)f(j) is the minimal token count for the prefix s[0:j]s[0{:}j]. Single symbols guarantee an edge j−1→jj-1\to j, so f(n)≤nf(n)\le n 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.

Check your understanding

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?

  1. The 3-token segmentation must contain an unknown token
  2. Its encoder applies the learned merges in training order, and that greedy replay need not minimize the token count
  3. BPE always maximizes the number of tokens to keep pieces short
  4. 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, MM times. Rescanning after every merge costs O(NM)\order{NM} for a corpus of NN symbols; tracking pair counts incrementally in a priority queue brings it to O(Nlog⁡M)\order{N\log M} (Zouhar et al., 2023). Encoding a chunk of nn symbols with a heap of adjacent pairs keyed by merge rank takes O(nlog⁡n)\order{n\log n}. What does greedy merging achieve?

DerivationWordPiece: from likelihood gain to a PMI-like score
  1. L=∑tc(t)log⁡c(t)N\mathcal L=\sum_tc(t)\log\frac{c(t)}N

    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 p(t)=c(t)/Np(t)=c(t)/N, the log-likelihood of the tokenized corpus is

  2. ΔL≈c(ab)[log⁡p(ab)−log⁡p(a)−log⁡p(b)]=c(ab)log⁡p(ab)p(a) p(b)\Delta\mathcal L\approx c(ab)\Big[\log p(ab)-\log p(a)-\log p(b)\Big]=c(ab)\log\frac{p(ab)}{p(a)\,p(b)}

    Merging the c(ab)c(ab) adjacent occurrences of a,ba,b replaces two tokens by one in each. Ignoring the small changes this causes in NN, c(a)c(a) and c(b)c(b), the gain is the pair count times its pointwise mutual information:

  3. BPE:  c(ab)WordPiece (open variants):  c(ab)c(a) c(b)\text{BPE: }\ c(ab)\qquad\text{WordPiece (open variants): }\ \frac{c(ab)}{c(a)\,c(b)}

    BPE ranks pairs by frequency c(ab)c(ab) alone. Widely used open implementations of WordPiece rank by c(ab)/(c(a)c(b))c(ab)/\big(c(a)c(b)\big), 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 S(x)S(x), each a product of token probabilities: P(x)=∑s∈S(x)∏ip(si)P(x)=\sum_{\mathbf s\in S(x)}\prod_ip(s_i). Training alternates EM over pp 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 −log⁡p(t)-\log p(t). 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.

DerivationForward–backward over the segmentation lattice
  1. α(0)=1,α(j)=∑i: x[i:j]∈Vα(i) p(x[i:j]),α(n)=P(x)\alpha(0)=1,\qquad\alpha(j)=\sum_{i:\ x[i:j]\in V}\alpha(i)\,p\big(x[i{:}j]\big),\qquad\alpha(n)=P(x)

    The forward variable sums over all segmentations of the prefix x[0:j]x[0{:}j]; it costs O(nL)\order{nL} like the shortest path, with a sum in place of the minimum:

  2. E[ct∣x]=∑(i,j): x[i:j]=tα(i) p(t) β(j)α(n)\E[c_t\mid x]=\sum_{(i,j):\,x[i:j]=t}\frac{\alpha(i)\,p(t)\,\beta(j)}{\alpha(n)}

    With the analogous backward variable β\beta, the E-step's expected count of token tt sums over its occurrences x[i:j]=tx[i{:}j]=t in the lattice; the M-step sets p(t)∝E[ct]p(t)\propto\E[c_t]:

  3. Pr⁡(last token=x[i:j] ∣ prefix x[0:j])=α(i) p(x[i:j])α(j)\Pr\big(\text{last token}=x[i{:}j]\ \big|\ \text{prefix }x[0{:}j]\big)=\frac{\alpha(i)\,p\big(x[i{:}j]\big)}{\alpha(j)}

    Subword regularization samples a segmentation instead of taking the best one, walking back from nn and choosing each last token with its posterior probability (forward filtering, backward sampling); Kudo also sharpened or flattened the distribution with an exponent α\alpha. 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.

Predict before you look

A Unigram LM tokenizer has p(a)=0.2p(\text{a})=0.2, p(b)=0.1p(\text{b})=0.1 and p(ab)=0.05p(\text{ab})=0.05. 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 0.050.05 and [a][b] with 0.2×0.1=0.020.2\times0.1=0.02, so P("ab")=0.07P(\text{"ab"})=0.07 and the posterior of [ab] is 0.05/0.07≈71%0.05/0.07\approx71\%. Viterbi always returns [ab]; subword regularization (with exponent 11) 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 (O(nL)\order{nL}), and the same program with −log⁡p-\log p 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.

Question 1

Over a fixed vocabulary that contains every single character, with tokens of length at most LL, what does it cost to find a segmentation of an nn-character string into the fewest tokens?

  1. It is NP-hard, like finding optimal merges
  2. O(nL)\order{nL} trie steps, by dynamic programming over positions
  3. O(2n)\order{2^n}, since there are exponentially many segmentations
  4. O(n)\order{n} with BPE's merge replay, which is always optimal
Show the answer

B. O(nL)\order{nL} trie steps, by dynamic programming over positions

Segmentations are paths in a DAG on positions 0,…,n0,\dots,n with at most nLnL edges, and shortest paths in a DAG take one pass. Hardness appears only when the vocabulary itself is being chosen.

Question 2

Two pairs each occur 1,0001{,}000 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 c(ab)/(c(a)c(b))c(ab)/\big(c(a)c(b)\big) rank them?

  1. Both prefer pair 1
  2. BPE prefers pair 2 and WordPiece pair 1
  3. BPE treats them as tied, while WordPiece prefers pair 2, whose parts rarely occur apart
  4. 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.

Question 3

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?

  1. Processing the Russian text costs more under per-token pricing
  2. Less Russian text fits in the same context window
  3. Generating the Russian text takes more decoding steps
  4. 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).