Subword Tokenization (BPE and WordPiece)

The previous page ended on an unavoidable trade: a 10,000-word vocabulary discards 5.5% of the text, and a 20,000-word one doubles the embedding matrix to get that down to 2.4%. Both numbers are bad, and both are consequences of insisting that the unit of text is a word.

Subword tokenization removes the choice. Build a vocabulary of pieces — frequent words stay whole, rare words split into parts, and anything unseen is spelled out of characters. Measured on 39,563 IMDB word types:

Tokenization	Vocabulary	Tokens per review	OOV rate
character	83	1,211.3	0.0000
BPE (2,000 merges)	2,070	324.7	0.0000
word	39,563	226.0	0.0293 at 20,000 words

A 2,070-piece vocabulary — 5% the size of the word vocabulary — represents every word ever written, for 1.44× the sequence length.

What you’ll learn

The BPE algorithm in full, and why it is about forty lines.
What the first merges actually learn: 'e' + '</w>', then 's' + '</w>', then 't' + 'h'.
How the vocabulary/length trade moves with merges: 5.2155 pieces per word at 1 merge, 1.4651 at 2,000.
Why the OOV rate is exactly zero rather than merely small.
How BPE splits words it has never seen — including antidisestablishmentarianism.
The difference between BPE, WordPiece, Unigram and SentencePiece.
The implementation trap that made the first version of this page time out.

The algorithm

Split every word into characters, plus an end-of-word marker </w>.
Count every adjacent pair of pieces across the corpus, weighted by word frequency.
Merge the most frequent pair everywhere; that merged symbol joins the vocabulary.
Repeat for as many merges as you want vocabulary entries.

Byte-pair encoding, the whole idea

splits = {word: tuple(list(word) + ["</w>"]) for word in counts}
for step in range(merges):
    pairs = Counter()
    for word, pieces in splits.items():
        for pair in zip(pieces, pieces[1:]):
            pairs[pair] += counts[word]          # weight by word frequency
    pair, frequency = pairs.most_common(1)[0]
    if frequency < 2:
        break
    splits = {word: apply(pieces, pair) for word, pieces in splits.items()}

The end-of-word marker matters more than it looks. Without it, est in establish and est in fastest are the same piece, and the tokenizer cannot tell a prefix from a suffix.

Learned on this corpus, the first fifteen merges are:

#	Merge	#	Merge	#	Merge
1	`e` + `</w>`	6	`i` + `n`	11	`o` + `n`
2	`s` + `</w>`	7	`r` + `</w>`	12	`e` + `n`
3	`t` + `h`	8	`a` + `n`	13	`o` + `</w>`
4	`t` + `</w>`	9	`y` + `</w>`	14	`e` + `r`
5	`d` + `</w>`	10	`th` + `e</w>`	15	`i` + `s</w>`

BPE has discovered, in order: English words end in e and s; th is the most common digraph; and by merge 10 it has built the word the. Nobody told it any of that — it is counting.

Vocabulary against sequence length

Two panels. Left: pieces in use against merges learned, rising almost linearly from 84 at one merge to 2,070 at two thousand. Right: average pieces per word falling from 5.2155 at one merge to 2.4994 at 200, 2.0020 at 500, 1.7026 at 1,000 and 1.4651 at 2,000, approaching but not reaching a dashed line at 1.0. — The left panel is nearly a straight line — one merge, one new symbol — which is what makes the vocabulary size a dial you turn rather than a property of the corpus. The right panel is the payoff, and it has diminishing returns: the first 200 merges cut pieces per word from 5.22 to 2.50, the next 1,800 only get to 1.47. Real tokenizers use 30,000-50,000 merges to push that close to 1 for common text.

Merges	Pieces in use	Pieces per word	Words kept whole
1	84	5.2155	60
200	279	2.4994	1,284
500	579	2.0020	2,878
1,000	1,078	1.7026	5,043
2,000	2,070	1.4651	8,367

“Pieces per word” is token-weighted, so it answers the question you actually care about: how much longer does my sequence get? At 2,000 merges the answer is 1.47× — and 8,367 of the 39,563 word types are single pieces, which will be the common ones.

The measurement that settles it

Two panels. Left: out-of-vocabulary rate on test tokens against word vocabulary size — the word-level line falls from 0.2276 at 1,000 words to 0.0293 at 20,000, while the subword line sits flat on zero. Right: a monospace listing showing rare and unseen words split into pieces, such as tokenization becoming 'to k en i z ation'. — The word-level curve never reaches zero, and it cannot: Heaps' law guarantees the test set contains words the training set did not. The subword line is exactly zero at a vocabulary of 2,070 — twenty times smaller than the 20,000-word vocabulary it is beating. That is not a better trade-off along the same curve; it is a different curve.

Word vocabulary	Word-level OOV	BPE OOV
1,000	0.2276	0.0000
5,000	0.0944	0.0000
10,000	0.0550	0.0000
20,000	0.0293	0.0000

The zero is exact, not rounded, and the reason is structural: the vocabulary contains every character in the corpus, so the worst case for any word is that it is spelled out.

Words BPE has never seen as a whole

                tokenization -> to k en i z ation</w>
             unbelievability -> un believ ab ility</w>
        supercalifragilistic -> super c ali f ra g ili stic</w>
antidisestablishmentarianism -> an ti di se st ab li sh m ent ari an ism</w>

Read those splits carefully, because they show both the strength and the limit:

un believ ab ility is close to a morphological analysis, and it was learned from frequency counts alone.
to k en i z ation is not. BPE is greedy and frequency-driven, not linguistic; it found ation but mangled the stem.
antidisestablishmentarianism becomes 13 pieces. A word the tokenizer has never seen costs sequence length, which is the price of never failing.

The length trade

Three bars of average tokens per review: character tokenization at 1,211.3 tokens with an 83-symbol vocabulary, BPE at 324.7 tokens with 2,070 pieces, and word at 226.0 tokens with 39,563 words. — Characters need no vocabulary at all and pay 5.36x the sequence length — fatal for attention, whose cost grows with the square of the token count. Words are the shortest and cannot handle anything new. BPE sits between them at 1.44x the word length with 5% of the vocabulary, which is why every modern model is somewhere on that middle ground.

For a transformer this trade is sharper than it looks, because attention cost grows with the square of the token count. Character tokenization at 5.36× the length is 28.73× the attention cost; BPE at 1.44× is 2.06×. Exercise 5 works the whole table, including the embedding matrices: 21,248 parameters for characters against 10,128,128 for words at 256 dimensions.

diagram Diagram mermaid

  flowchart LR
  A["word level"] -->|"OOV never reaches 0
huge embedding matrix"| D["subword"]
  B["character level"] -->|"5.36x length
28x attention cost"| D
  D --> E["BPE
merge most frequent pair"]
  D --> F["WordPiece
merge highest likelihood gain"]
  D --> G["Unigram
start big, prune"]
  E --> H["vocabulary 2,070
1.44x length
0% OOV"]
  F --> H
  G --> H

The four you will meet

Algorithm	Merge/keep criterion	Used by
BPE	most frequent adjacent pair	GPT-2, RoBERTa, most LLMs
WordPiece	pair maximising $\frac{P(xy)}{P(x)P(y)}$ — likelihood gain, not raw count	BERT, DistilBERT
Unigram	start with a large vocabulary, prune the pieces that cost least likelihood	T5, ALBERT
SentencePiece	not an algorithm — a wrapper that treats the input as raw bytes, so no pre-tokenizer is needed	multilingual models

The difference between BPE and WordPiece is one line of the algorithm. BPE takes the pair that occurs most; WordPiece takes the pair whose merger most increases the corpus likelihood, which favours pairs that are common together relative to how common they are apart. In practice their outputs are similar, and the marker convention differs more visibly: BPE typically marks word ends (ation</w>), WordPiece marks continuations (##ation).

The implementation trap

The obvious BPE implementation recounts every pair after every merge. That is quadratic, and on this corpus — 39,563 words, 2,000 merges — it never finished; the module timed out at ten minutes.

Only the words containing the merged pair can change, so keeping a pair → words index and updating locally turns it into 5.1 seconds for 200 merges. The second trap is at encoding time: replaying all 2,000 merges for each of ~100,000 tokens is another 2×10⁸ operations, when training has already computed the final split for every word in the corpus. Look it up; only genuinely unseen words need the replay.

sketch Learn BPE merges by hand p5.js

Click 'merge' to apply the most frequent adjacent pair to this tiny corpus, and watch the vocabulary grow as the sequences shorten.

sketch The measured table, ranked p5.js

Click a column to rank every row by it. The bars are that column's values and the highest and lowest are computed from the numbers, not written in.

Pitfalls

Forgetting the end-of-word marker. Without it the tokenizer cannot distinguish a suffix from a prefix, and est in fastest merges with est in establish.
Recounting all pairs after every merge. Quadratic; it did not finish on 39,563 words. Keep a pair → words index.
Replaying every merge to encode a known word. Training already produced its split.
Assuming subword splits are morphemes. un believ ab ility looks linguistic; to k en i z ation shows it is frequency, not grammar.
Ignoring the sequence-length cost. 1.44× the tokens is 2.1× the attention cost, and character level’s 5.36× is 28×.
Training the tokenizer on the test set. It is a model fitted to a corpus, with the same leakage rules as any other.
Comparing models across different tokenizers. Perplexity per token is not comparable when the tokens are different sizes — a point the evaluation page returns to.

Recap

BPE: split into characters, repeatedly merge the most frequent adjacent pair. About forty lines.
The first merges learned on this corpus were e</w>, s</w>, th, and by merge 10 the word the.
2,000 merges gave 2,070 pieces, 1.4651 pieces per word, and 8,367 of 39,563 word types kept whole.
OOV rate on 458,707 test tokens: 0.0000 for BPE at 2,070 pieces, against 0.0293 for a 20,000-word vocabulary.
Sequence length per review: character 1,211.3, BPE 324.7, word 226.0.
BPE merges by frequency, WordPiece by likelihood gain, Unigram prunes downward, SentencePiece removes the pre-tokenizer.

With a tokenization that never fails, the question becomes how to turn those tokens into features. The oldest answer still beats a lot of neural models: Bag of Words (BoW) & TF-IDF.

pch.quizTag pch.quizDefaultTitle

A BPE vocabulary of 2,070 pieces had an OOV rate of exactly 0.0000, while a 20,000-word vocabulary had 0.0293. Why is the zero exact rather than merely small?

pch.quizShowAnswer

B — Because the vocabulary contains every character in the corpus, so the worst case for an unknown word is that it is spelled out piece by piece — It is a structural guarantee, not a lucky measurement — which is why subword tokenization replaced word-level tokenization everywhere.
The first merges learned were 'e'+'</w>', then 's'+'</w>', then 't'+'h'. What does that show?

pch.quizShowAnswer

B — Nothing was taught — BPE counts adjacent pairs, and English word endings and the 'th' digraph are simply the most frequent pairs in the corpus — By merge 10 it had assembled 'the'. The structure it finds is statistical, which is also why 'tokenization' splits as 'to k en i z ation'.
Character tokenization needs only 83 symbols and never has an OOV. Why is it not the obvious choice for a transformer?

pch.quizShowAnswer

B — It produced 5.36x the sequence length, and attention cost grows with the square of the token count — about 28x the attention compute — BPE's 1.44x length is only 2.1x attention cost, which is why the middle ground won.
What is the difference between BPE and WordPiece?

pch.quizShowAnswer

B — The merge criterion: BPE takes the most frequent adjacent pair, WordPiece takes the pair whose merger most increases corpus likelihood — One line of the algorithm. The visible difference is usually the marker convention: 'ation</w>' against '##ation'.
The first implementation of this page's BPE timed out after ten minutes. What was wrong?

pch.quizShowAnswer

B — It recounted every pair in the corpus after every merge — but only the words containing the merged pair can change, so a pair-to-words index makes it fast — With the index it runs 200 merges in 5.1 seconds. The second trap is encoding: reuse the splits training already computed rather than replaying all merges per token.

🧪 Try It Yourself

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading