NLP #3: Byte-Pair Encoding

Originally published on almoghagbi.com, where the figures are interactive.

By the end of this post, you'll be able to train a tiny tokenizer by hand.
You'll also predict how it splits a word it has never seen. Every natural
language processing (NLP) model reads text as tokens,
the units it works with. Section 2.4 of
Speech and Language Processing
shows where models like GPT-4o get theirs: byte-pair encoding (BPE). It starts
from single characters and merges the most frequent pair of neighboring tokens,
again and again.

Intuition

Tokens smaller than words

It's tempting to think of a tokenizer as a dictionary: one token per word. Our
running example, a short review, shows why that fails:

the café baker bakes cakes, the café bakes soufflé

If the vocabulary holds exactly these words, a new review that says "baked"
leaves the model with nothing to work with. This is the unknown word
problem.

Make every character a token instead, and nothing is ever unknown. But the units
are too small: a letter like k means little by itself, and texts get long.

The answer lies between the two: subwords, pieces of any length learned from
data. Common words become single tokens. The tokenizer builds rarer words from
pieces like bake and d, falling back to single characters in the worst case.

Merge the most frequent pair, again and again

A BPE tokenizer has two parts. A trainer learns tokens from training text,
and an encoder uses them to split new text.

The trainer cuts the text into words at spaces and punctuation, keeping each
space on the word after it. We write that space as a dot: ·bakes. It splits
each word into characters, which form the starting vocabulary: our review has 50
characters, 16 of them different. Then it repeats two steps:

Count every pair of neighboring tokens inside the words.
Merge the most frequent pair into one new token, everywhere it occurs.

a k occurs 4 times: once in baker, twice in bakes and once in cakes. No
pair beats that, so ak becomes a token. Ties go to the pair seen first. The
first five merges:

Merge	Pair	Count	New token	Tokens left in the text
1	`a` + `k`	4	`ak`	46
2	`ak` + `e`	4	`ake`	42
3	`·` + `c`	3	`·c`	39
4	`·` + `b`	3	`·b`	36
5	`·b` + `ake`	3	`·bake`	33

Notice what BPE doesn't do. A linguist would split baker into its
morphemes, bake and -er. BPE builds the
meaningless ake first and never makes er, which occurs only once. It follows
counts and nothing else: find the most frequent pair, merge it, repeat. Run it
yourself:

▶ Interactive figure: try it on the original post.

New words split into known pieces

The encoder counts nothing. It splits new text into characters, then replays the
merges in the order they were learned. After five merges, "the maker baked
cakes" becomes:

t h e · m ake r ·bake d ·c ake s

baked and maker never appeared in the review, yet both now use known pieces.

Real tokenizers make tens of thousands of merges. GPT-4o's tokenizer has about
200,000 tokens, and most of our review stays whole in it:

the ·café ·baker ·b akes ·cakes , ·the ·café ·b akes ·souff lé

The made-up unbakeable becomes un b ake able, and ·bakes splits as
·b akes: counts decide, not meaning. Try your own text in the
Tiktokenizer.

Real tokenizers start from bytes

In practice, BPE starts from the
UTF-8 bytes of the text, not characters. A
byte has only 256 possible values, so no input contains an unknown starting
token.

Switch on "start from UTF-8 bytes" in the widget. é now starts as two bytes,
C3 and A9. They occur together 3 times, so merge 4 joins them: BPE
rediscovers é without knowing what UTF-8 is.

Training text matters too. Most of it is English, so English gets the largest
share of the tokens. In one sentence I ran through GPT-4o's tokenizer, 8 English words took 9 tokens,
while my 6-word Hebrew translation took 12.

The math

The corpus

Definition 1 (Corpus and vocabulary). A corpus $C$ is the training text,
cut into words: strings $s_{1}, \dots, s_{m}$ with counts $c_{1}, \dots, c_{m}$ . Each
string is a sequence of tokens from a vocabulary $V$ , which starts as $V_{0}$ ,
the set of all characters (or bytes) in $C$ . The corpus length is

L = j = 1 \sum m c_{j} ∣ s_{j} ∣,

where $∣ s_{j} ∣$ is the number of tokens in $s_{j}$ .

Our review has 8 different strings: the (1), ·café (2), ·baker (1),
·bakes (2), ·cakes (1), , (1), ·the (1) and ·soufflé (1). So
$L = 3 + 10 + 6 + 12 + 6 + 1 + 4 + 8 = 50$ and $∣ V_{0} ∣ = 16$ .

Counting pairs

Definition 2 (Pair count). For tokens $a$ and $b$ , let $n_{j} (a, b)$ be the
number of times $b$ directly follows $a$ in string $s_{j}$ . Then

count (a, b) = j = 1 \sum m c_{j} n_{j} (a, b) .

We count each different word once and multiply by its count. For our review,
$count (a, k) = 1 \cdot 1 + 2 \cdot 1 + 1 \cdot 1 = 4$ ,
from ·baker, ·bakes and ·cakes.

Key equation (Next merge). Training picks the most frequent pair:

(t_{L}, t_{R}) = (a, b) arg max count (a, b) .

It returns the pair, not its count. Ties need a fixed rule: ours takes the pair
seen first.

One merge

Definition 3 (Merge). A merge concatenates the two tokens into
$t_{NEW} = t_{L} t_{R}$ and adds it to $V$ . It then replaces each occurrence of
$t_{L}$ followed by $t_{R}$ in $C$ with $t_{NEW}$ , reading left to right.
Training makes $k$ merges, a number we choose.

Key equation (Sizes after a merge). Each merge adds one token to $V$ ,
and each replacement removes one token from $C$ :

∣ V_{k} ∣ = ∣ V_{0} ∣ + k, L_{i} = L_{i - 1} - count (t_{L}, t_{R}) .

The second equation assumes $t_{L} \neq = t_{R}$ . If they're equal, occurrences can
overlap: a a a has count 2, but only one replacement fits. For our review,
$∣ V_{1} ∣ = 17$ and $L_{1} = 50 - 4 = 46$ ; after five merges, $∣ V_{5} ∣ = 21$ and $L_{5} = 33$ .

Encoding new text

Definition 4 (BPE encoder). Training produces an ordered list of merges
$m_{1}, \dots, m_{k}$ . To encode new text, split it into words and each word into
starting units. Then apply $m_{1}$ everywhere, then $m_{2}$ , and so on through $m_{k}$ .

Counts in the new text play no part, but order does: ake can only form after
merge 1 has made ak. The whole tokenizer in Python:

import re from collections import Counter def words_of(text): return re.findall(r" ?\w+|[^\w\s]", text) def merge(tokens, a, b): # turn each "a b" into "ab", left to right out = [] for t in tokens: if out and out[-1] == a and t == b: out[-1] = a + b else: out.append(t) return out def train(text, k): freq = Counter(words_of(text)) corpus = {w: list(w) for w in freq} merges = [] for _ in range(k): pairs = Counter() for w, t...