Byte-Pair Encoding, Step by Step
Lesson 2 of 4 in Tokenization: Text Becomes Tokens.
Byte-pair encoding began life as a 1990s data-compression trick: repeatedly replace the most frequent pair of adjacent symbols with a new symbol. Sennrich, Haddow and Birch (2016) adapted it to build subword vocabularies for machine translation, and the idea stuck — variants of it tokenize many of the best-known LLMs today.
The training algorithm fits in one breath: start from characters, and repeatedly merge the most frequent adjacent pair into a new symbol until the vocabulary is as big as you want. Everything else is bookkeeping.
BPE vocabulary training
- Corpus as characters
Split every word into single characters, with a marker for word endings, and count how often each word occurs.
- Count adjacent pairs
Tally every pair of neighboring symbols across the corpus, weighted by word frequency.
- Merge the most frequent pair
Replace every occurrence of the winning pair with a single new symbol, e.g.
e+s→es. - Record the merge rule
The new symbol joins the vocabulary, and the merge is appended to an ordered rule list.
- Vocabulary budget reached?
The target vocabulary size is a design choice made before training — the number of merges is roughly that budget.
- Tokenizer = base symbols + ordered merge list
To tokenize new text, apply the same merges, in the same order, wherever they fit.
Watch it run on a toy corpus — four words with counts, in the spirit of the original paper’s example: low ×5, lower ×2, newest ×6, widest ×3. Every word starts as characters plus an end-of-word marker ·, so newest is n e w e s t ·. Now count neighboring pairs across the whole corpus: the pair e s appears in newest (6 times) and widest (3 times) — 9 occurrences, the most frequent. Merge it everywhere, record the rule, and repeat.
| Round | Most frequent pair | New symbol | Corpus afterwards |
|---|---|---|---|
1 |
|
|
|
2 |
|
|
|
3 |
|
| The suffix now knows it ends words |
4 |
|
|
|
5 |
|
|
|
Five merges in, the corpus’s statistics are already visible in the vocabulary: est· exists because two words shared a frequent suffix, and low exists because one word was frequent enough to earn its own symbol. Run tens of thousands of merges over a real corpus and the same logic yields whole common words, productive prefixes and suffixes, and character fragments for everything else.
Training produces two artifacts: the Vocabulary and the ordered merge list. Tokenizing new text replays those merges in the order they were learned — which is why the process is deterministic, fast, and frozen. The tokenizer is trained once, before the model, on some corpus; the model then spends its entire life reading the world through those merge decisions. A corpus rich in English and code produces a tokenizer generous to English and code — remember that when we reach multilingual costs in lesson four.
The mechanics under the merge loop
The objective is greedy compression, not linguistics. Each merge is the single substitution that most reduces the number of symbols in the corpus at that moment — there is no lookahead and no notion of morphemes. BPE derives from a compression scheme (replacing frequent byte pairs with unused byte values), which is why its splits sometimes look linguistic (est) and sometimes just look statistical.
Encoding applies merges by rank. Each learned merge gets a priority equal to its training order. To tokenize a new word, split it to base symbols, then repeatedly apply the highest-priority merge present anywhere in the word until none applies. Given the same merge list, the same string always tokenizes the same way.
The base alphabet is a real design decision. If the base symbols are Unicode characters, any character absent from training data is unrepresentable without an unknown token. Byte-level BPE (lesson three) fixes this by starting from the 256 possible bytes: every string is bytes, so coverage is total by construction — at the price of splitting unfamiliar scripts into many tiny pieces.
Vocabulary size ≈ base alphabet + number of merges (plus special tokens like end-of-text). That one dial sets the trade-off you will see next lesson: more merges mean longer, more word-like tokens and shorter sequences, but a bigger embedding table to store and score.
Interactive checkpoint quiz (1 questions) — open this page in a browser to take it.