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:

1. Count every pair of neighboring tokens inside the words.
2. 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 = \sum_{j=1}^{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

$$\text{count}(a, b) = \sum_{j=1}^{m} c_j \, n_j(a, b).$$

We count each different word once and multiply by its count. For our review,
$\text{count}(\texttt{a}, \texttt{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) = \operatorname*{arg\,max}_{(a, b)} \ \text{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_{\text{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_{\text{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, \qquad L_i = L_{i-1} - \text{count}(t_L, t_R).$$

The second equation assumes $t_L \ne 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, toks in corpus.items():
            for pair in zip(toks, toks[1:]):
                pairs[pair] += freq[w]
        a, b = pairs.most_common(1)[0][0]  # ties: the pair seen first
        merges.append((a, b))
        corpus = {w: merge(t, a, b) for w, t in corpus.items()}
    return merges

def encode(text, merges):
    out = []
    for w in words_of(text):
        toks = list(w)
        for a, b in merges:
            toks = merge(toks, a, b)
        out += toks
    return out

merges = train("the café baker bakes cakes, the café bakes soufflé", 5)
print(encode("the maker baked cakes", merges))
# ['t', 'h', 'e', ' ', 'm', 'ake', 'r', ' bake', 'd', ' c', 'ake', 's']

Byte-level BPE

Definition 5 (Byte-level BPE). Byte-level BPE runs the same algorithm with
$V_0 = {0, 1, \dots, 255}$ , on the UTF-8 bytes of the corpus. Every merged
token is a sequence of bytes, so

$$|V_k| = 256 + k.$$

All 256 bytes are in $V_0$ , so the encoder never meets an unknown token, and a
text of $B$ bytes becomes at most $B$ tokens. A vocabulary of about 200,000
tokens means about $200{,}000 - 256$ merges.

The widget's byte mode counts only the bytes our review uses, so $|V_0|$ shows 17,
not 256. $L_0$ shows 53, since each of the three é takes 2 bytes.

What you can do now

• Train a BPE tokenizer by hand: start from characters or bytes, merge the most frequent pair of neighboring tokens, and repeat $k$ times.
• Encode a new word by replaying the merges in order: baked becomes ·bake d.
• Predict the sizes: each merge adds one token to the vocabulary and removes $\text{count}(t_L, t_R)$ tokens from the text.
• Explain why a byte-level tokenizer never meets an unknown token.

Exercises

Each question has one correct answer. Pick your answer, then read the explanation. Questions 6–10 use the definitions and equations above.

1. (Intuition) A tokenizer's vocabulary holds only whole words, including bake, bakes and baker. What happens when a new text contains "baked"?

• A. It splits "baked" into bake and d.

• B. It uses the closest word it knows, bake.

• C. It has no token for "baked", so the word is unknown.

• D. It adds "baked" to the vocabulary and carries on.

Answer

C. With whole words only, a word that's missing from the list has no token. That's the unknown word problem, and subwords exist to solve it.

• A is wrong: this vocabulary has no d, because it holds only whole words.
• B is wrong: nothing in a vocabulary measures how close two words are.
• D is wrong: the vocabulary is fixed after training.

2. (Intuition) Characters never cause unknown words. Why not stop there and use them as the tokens?

• A. They are too small: a single letter means little, and texts become much longer.

• B. A computer can't store every character of every language.

• C. A list of characters is longer than a list of words.

• D. New words would still contain unknown letter pairs.

Answer

A. Characters solve the unknown word problem but give long sequences of units that carry little meaning. Subwords keep the safety of characters and add larger pieces.

• B is wrong: post 2 showed that Unicode and UTF-8 handle every character.
• C is wrong: English has far fewer characters than words.
• D is wrong: a character tokenizer never looks at pairs of letters.

3. (Intuition) After training on our review, the encoder gets a text in which z is followed by q a thousand times. What does it do with those pairs?

• A. It merges them, since they're the most frequent pair in this text.

• B. It merges them after finishing the learned merges.

• C. It reports an error, because zq was never seen.

• D. It leaves them as separate tokens, since no learned merge joins them.

Answer

D. The encoder only replays the merges learned in training. Counts in new text play no part, so z and q stay apart.

• A and B are wrong: counting and creating new tokens happen only in training.
• C is wrong: the encoder doesn't need a merge for every pair. Unmerged units stay as they are.

4. (Intuition) In the real tokenizer, ·baker is one token but unbakeable takes four. Why?

• A. Short words are always kept whole.

• B. Frequent strings earn merges early, and the rare ones run out of merges.

• C. The tokenizer knows that "un" and "able" are English morphemes.

• D. Words with a prefix are always split by a rule.

Answer

B. Each merge goes to the most frequent pair at that moment, and the number of merges is limited. ·baker occurs often enough to be built up completely. unbakeable is rare, so it stays in pieces.

• A is wrong: ·bakes is short, and it's split into ·b and akes.
• C is wrong: the algorithm only counts. It has no idea what a morpheme is.
• D is wrong: BPE has no rules about prefixes. Its only data are pair counts.

5. (Intuition, widget) In the widget, switch on "start from UTF-8 bytes", leave the review as it is, and click Next merge. Which merge joins C3 and A9 into é?

• A. Merge 1

• B. Merge 3

• C. Merge 4

• D. It never happens in this text.

Answer

C. The pair occurs 3 times: twice in ·café and once in ·soufflé. Merges 1 and 2 have count 4. At count 3, the pair · + c is seen first and takes merge 3, so C3 + A9 gets merge 4.

• A is wrong: merge 1 is a + k, with count 4.
• B is wrong: · + c also has count 3, and it comes earlier in the text.
• D is wrong: the widget shows it happening, and the merged token displays as é.

6. (Math · Definition 2) A corpus has hop (count 5), hops (count 2), shop (count 3) and shops (count 1), split into letters. What is $\text{count}(\texttt{p}, \texttt{s})$ ?

• A. 3

• B. 2

• C. 4

• D. 11

Answer

A. p is followed by s once in hops and once in shops, so the count is $2\cdot 1+1\cdot 1=3$ .

• B is wrong: 2 is the number of different words that contain the pair, ignoring their frequencies.
• C is wrong: 4 is $\text{count}(\text{s},\text{h})$ , from shop and shops.
• D is wrong: 11 is $\text{count}(\text{o},\text{p})$ , which occurs in all four words.

7. (Math · Sizes after a merge) The same corpus has $|V_0| = 4$ and $L_0 = 40$ . The first merge has count 11. What are $|V_1|$ and $L_1$ ?

• A. $|V_1| = 4$ , $L_1 = 29$

• B. $|V_1| = 5$ , $L_1 = 39$

• C. $|V_1| = 15$ , $L_1 = 29$

• D. $|V_1| = 5$ , $L_1 = 29$

Answer

D. One merge adds one token, so ∣V1​∣=4+1=5 . Each of the 11 replacements turns two tokens into one, so L1​=40−11=29 .

• A is wrong: the old tokens stay in the vocabulary, and the new one is added.
• B is wrong: the corpus shrinks by the pair's count, not by 1.
• C is wrong: the vocabulary grows by one per merge, not by the pair's count.

8. (Math · Definition 3) The first two merges on that corpus are h + o and ho + p. The corpus is now hop, hop s, s hop and s hop s, with the same counts. What is the third merge?

• A. hop + s, with count 3

• B. s + hop, with count 4

• C. s + h, with count 4

• D. o + p, with count 11

Answer

B. Only two pairs are left. $\text{count}(\text{s},\text{hop})=3+1=4$ and $\text{count}(\text{hop},\text{s})=2+1=3$ , so s + hop wins.

• A is wrong: that pair exists, but it's less frequent.
• C and D are wrong: after the merges, h, o and p no longer appear on their own in the corpus, so these pairs have count 0.

9. (Math · Definition 4) The merges, in order, are h + o, ho + p, s + hop, hop + s. How does the encoder split shops?

• A. s hops

• B. shops

• C. shop s

• D. s h o p s

Answer

C. The first two merges give s hop s. The third, s + hop, gives shop s. The fourth needs hop as a token, but it's now inside shop, so nothing changes.

• A is wrong: it applies hop + s before s + hop, against the learned order.
• B is wrong: no merge joins shop and s.
• D is wrong: it applies no merges at all.

10. (Math · Definition 5) A byte-level tokenizer made its 1,000 merges on English text only. It now meets "שלום", which takes 8 bytes in UTF-8. What is the most tokens it can produce?

• A. 8

• B. 4

• C. 1

• D. It can't encode the word.

Answer

A. All 256 bytes are in V0​ , so the worst case is one token per byte: 8 tokens.

• B is wrong: 4 is the number of characters. Each Hebrew letter takes 2 bytes, and gets a single token only if the merge joining its two bytes was learned.
• C is wrong: 1 is the fewest it could produce, not the most.
• D is wrong: starting from bytes means every text can be encoded.

Next: N-gram language models, which predict the next word from the few words
before it (chapter 3, section 3.1).

Co-authored with AI.