NLP #3: Byte-Pair Encoding

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:

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:

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

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

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:

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$:

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

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.

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