Byte-Pair Encoding (BPE): Learning a Vocabulary by Merging

Last concept (tokenization) ended with a cliffhanger.

We know the model only eats IDs from a fixed vocabulary — a menu of 30k–256k pieces. We know the menu must contain subwords, because full words break on "quarknetbook" and German law-names, and pure characters make every sentence 4–8x longer.

So the question becomes:

A committee of linguists? Impossible — every language, every dialect, every codebase, forever.

BPE's answer is cheekier:

Give BPE two things — a pile of text (the corpus) and a target vocabulary size — and it derives the menu by counting. No dictionaries, no linguists, no supervision.

This came from an odd place: data compression.

Byte-Pair Encoding was published for NLP in 2015 by Sennrich, Haddow, and Birch ("Neural Machine Translation of Rare Words with Subword Units", arXiv:1508.07909) as a fix for rare words in statistical machine translation. The technique itself dates back to a 1994 compression algorithm.

The compression insight, in one line:

Think of a group chat that invents its own shorthand.

At first you type "people" letter by letter. But the pair of letters you type together most often gets abbreviated first. Frequent chunks get shorter names; rare words stay spelled out in pieces. The message always fits — you can still spell anything, one letter at a time if you must.

That is exactly what BPE does with a corpus:

• Words that appear constantly ("the", "and") merge into one token.
• Rare or brand-new words stay decomposed into a handful of known pieces.
• Coverage becomes compositional: every string is representable, because every base symbol is just a character.

Notice the elegance of the fallback: nothing is ever lost, only expanded.

A frequent word becomes one cheap ticket. A never-before-seen word becomes five or six tickets of known pieces. The machine never says "no such drink" — worst case, it sells you the ingredients.

And this little counting game is the algorithmic backbone of the entire generative lineage: GPT-2, GPT-3, GPT-4/4o, RoBERTa, LLaMA (byte-fallback BPE), Qwen, and DeepSeek all train on BPE-style vocabularies.

Training a BPE tokenizer takes only two inputs: a text corpus and a target vocabulary size (say, 50,000). Then five steps:

1. Pre-tokenize: split text into words and append an end-of-word marker — leopard becomes l e o p a r d </w>. Pre-tokenizer rules protect language boundaries: cl100k_base uses a hand-tuned regex that keeps apostrophes, digits, and CJK characters apart.
2. Initialize: the vocabulary starts as all distinct base symbols (characters) plus the end-of-word marker. Nothing else.
3. Count: tally every adjacent symbol pair across the whole pre-tokenized corpus.
4. Merge: take the single most frequent pair, glue it into one new symbol, add it to the vocabulary.
5. Repeat steps 3–4 until the vocabulary hits the target size.

Why the little </w> marker in step 1? Without it, BPE would happily glue the last letters of one word onto the first letters of the next, because in a raw character stream words touch. The marker puts a wall at every word boundary, so merges stay inside words. (Byte-level tokenizers like GPT-2 handle this differently: the space character itself rides along inside the next token, which is why "Ġis" is one ticket.)

Two things to notice:

Each merge gets a rank. Merge #1 was the most frequent thing in the corpus, #2 next, and so on. The final product is an ordered list of merge rules — the shorthand dictionary, most-useful abbreviation first.

Encoding new text never re-runs the statistics. Split into characters, then apply the learned merges in rank order, most-frequent first. This makes inference fast (linear in text length) and deterministic.

A real run in code, for scale:

from tokenizers import Tokenizer, models, trainers, pre_tokenizers

tokenizer = Tokenizer(models.BPE(unk_token="[UNK]"))
tokenizer.pre_tokenizer = pre_tokenizers.Whitespace()

trainer = trainers.BpeTrainer(vocab_size=5000, special_tokens=["[UNK]", "[CLS]", "[SEP]", "[MASK]"])
tokenizer.train(files=["wiki.txt"], trainer=trainer)

print(tokenizer.encode("tokenization is fascinating").tokens)
# ['token', 'ization', 'Ġis', ...] -> merge list replayed on unseen text

Take a toy corpus of eight words:

low low low lowest newer newest widest widest

Round 0 — write every word as characters with an end-of-word marker, then count all neighboring pairs:

code
Copy
low x3        →  (l,o):3  (o,w):3  (w,</w>):3
lowest        →  (l,o):1  (o,w):1  (w,e):1  (e,s):1  (s,t):1  (t,</w>):1
newer         →  (n,e):1  (e,w):1  (w,e):1  (e,r):1  (r,</w>):1
newest        →  (n,e):1  (e,w):1  (w,e):1  (e,s):1  (s,t):1  (t,</w>):1
widest x2     →  (w,i):2  (i,d):2  (d,e):2  (e,s):2  (s,t):2  (t,</w>):2

Add them up into one ledger:

code
Copy
(l,o):4  (o,w):4  (e,s):4  (s,t):4  (t,</w>):4
(w,</w>):3  (w,e):3  (n,e):2  (e,w):2  (w,i):2
(i,d):2  (d,e):2  (e,r):1  (r,</w>):1

(l,o), (o,w), (e,s), (s,t), (t,) all sit at 4 — a five-way tie for most frequent. (Real implementations break ties deterministically; let us just pick one.)

Round 1 — merge e + s → es. The vocabulary gains es. Re-scan: inside "newest" and "widest", the pair (es, t) now exists — and because "lowest", "newest" and both "widest"s carry it, it shows up 4 times. Almost no other pair changed; that is why BPE is cheap to iterate.

Round 2 — merge es + t → est. The suffix est is now a single token — a real English morpheme, learned from pure counting, with zero linguistic supervision.

Keep going and more useful chunks surface exactly where they recur across words: pairs like (e, r) promote newer as a unit, low and lowest form off the (l,o)/(o,w) chains, and est glues onto "wide" and "new".

Watch what just happened: nobody taught BPE what a suffix is. Frequency alone discovered est, low, and new as reusable building blocks.

Encoding a brand-new word like widestest? Split to characters, replay the merge list in rank order: es → est fires, and you get wide + est + est-style decomposition using only known pieces. Any string works. OOV is dead.

Picture BPE as climbing a ladder, one glue at a time. Each rung is a rank in the merge list:

code
Copy
rank 5:   w  i  d  e  s  t  </w>       ← round 0: raw characters
rank 2:   w  i  d  e  [es] t  </w>     ← e+s glued (most frequent at the time)
rank 3:   w  i  d  [est]   </w>        ← es+t glued
   ...
final:    [wide] [est]                 ← word emerges from merges

And training itself is a simple flywheel:

code
Copy
   corpus → COUNT pairs → MERGE winner (+1 vocab entry)
              ↑                    │
              └──── re-scan ◄──────┘
                     ... until vocab size = target → save ORDERED merge list

Two properties fall out of the picture:

• Early ranks = workhorses. Ġthe, ing, Ġ spaces get slots because they merge first and stay.
• The merge list IS the tokenizer. Ship it next to the checkpoint; encoding is just replaying it.

Why must replay follow the stored order and not "any order that fits"? Because rank order encodes the corpus statistics. Applying rank 1 first reproduces exactly the chunking the vocabulary was built for. Play the merges out of order and the same string can shatter differently — which is a nice way to remember that a BPE tokenizer is nothing more than: base split + ordered merge list. Nothing else. No neural anything. Training finished once the list was written.

One snag remained: classic BPE still needs a character alphabet, and Unicode alphabets are messy — which "letter" counts as one symbol across 150 scripts?

GPT-2 (2019) answered with byte-level BPE: forget characters; the base symbols are simply the 256 UTF-8 bytes.

• Every Unicode string decomposes into bytes, so OOV is mathematically impossible — and no language-specific preprocessing is needed at all.
• Bytes that are not printable get mapped to visual placeholder symbols so vocabularies stay inspectable: the Ġ you see standing in for a space, Ċ for a newline. (That is why GPT token dumps look like Ġis.)
• The cost: rare non-ASCII text pays in token count. One Chinese character or emoji can consume 2–4 byte-level tokens unless the model saw enough of them during merge training. The group chat invented shorthand for English chatter and everyone else still types letters.

Concretely: the character 中 is three UTF-8 bytes (e4 b8 ad). If the merge rounds never promoted those byte triples into fancier symbols, that single character costs three tickets where an English "the" costs one. Same meaning, three times the buttons pressed — the exact mechanism behind "the API is more expensive in Japanese".

OpenAI ships these vocabularies in tiktoken: r50k_base (GPT-2, 50,257 tokens), p50k_base/cl100k_base (GPT-3.5/4, 100,256 tokens), and o200k_base (GPT-4o, about 200k, introduced May 2024 — tuned for code and multilingual text, roughly 30–40% fewer tokens on non-English).

LLaMA-3 (2024) uses tiktoken BPE with byte fallback: any unknown Unicode sequence just encodes as its raw bytes instead of failing.

Why BPE won the generative world:

• Deterministic and cheap encode: replaying the merge list is one linear scan. tiktoken is roughly 3–6x faster than the older HuggingFace BPE implementation.
• Vocabulary size is a knob, not a corpus constraint: ask for 32k or 200k depending on coverage needs (the next concept covers how to choose — short version: bigger vocab = fewer tokens per text but fatter embedding tables).
• Language-agnostic in byte-level mode, at the price of token inflation for low-resource scripts.

Known sharp edges:

• Pre-tokenizer coupling: changing the regex silently changes tokenization for everything. A model trained under one pre-tokenizer must always be served under exactly it — the menu and the glues are welded into the checkpoint.
• Fragmentation of rare words hurts spelling and letter-level tasks. The "how many r's in strawberry" failure is a tokenizer artifact, not just a model defect: BPE never gave the model reliable single-letter tickets to count.
• Round-trip bugs: older byte-level vocabularies historically failed decode(encode(text)) == text on some multibyte sequences. Modern vocabularies (o200k, LLaMA-3) fixed this with strict byte fallback.

The group-chat analogy earns its keep one final time: BPE is lossy shorthand. Everyone in the chat understands "idk" — but if you never coined the abbreviation for a phrase, you are spelling it out letter by letter, and your message takes six times the taps.