II · THE IDEA · ARTIFICIAL INTELLIGENCE
Byte Pair Encoding
▶ Listen · narrated
The vocabulary a model uses is not designed by linguists. It is grown by an algorithm that counts pairs and merges them, over and over, until the list is long enough.
At a glance
- Starting vocabulary
- All 256 byte values, each treated as a separate token
- Operation
- Count adjacent pairs, merge the most frequent, add the merged unit to the vocabulary
- Stopping rule
- When vocabulary reaches the target size, typically 30,000 to 100,000 entries
- Output
- An ordered list of merge rules, applied sequentially during tokenisation
Imagine you are organising a large box of loose Lego bricks. You notice that red-blue combinations appear more often than any other pair, so you glue every red-blue pair together into a single unit. Now those units are available to pair with other bricks. You count again and find that red-blue + yellow appears frequently, so you glue those triplets together. You keep going until you have a manageable number of pre-assembled units. Byte Pair Encoding does the same with bytes: it starts with the smallest pieces, counts which pairs appear most often in the training text, merges them into new units, and repeats until the vocabulary reaches the size you chose. Common sequences like "the" or "ing" become single tokens, while rare words stay fragmented.
Byte Pair Encoding initialises the vocabulary with all 256 byte values. It then scans the training corpus, counts every adjacent pair of tokens, and merges the most frequent pair into a new vocabulary entry. The corpus is updated to reflect that merge, pair counts are recalculated, and the process repeats for a fixed number of iterations — typically tens of thousands — until the vocabulary reaches the target size.
The algorithm is greedy and deterministic. At each step, it commits to the single most frequent pair without considering future consequences. If two pairs have identical frequency, the tie is broken by a consistent rule, often lexicographic order, to ensure reproducibility. Once a pair is merged, it is treated as a single token in all subsequent rounds, so later merges can operate on the results of earlier ones. This cascading allows the algorithm to build hierarchical structures: "t"+"h" merges into "th", which later merges with "e" to form "the".
The output is an ordered list of merge rules. During tokenisation, these rules are applied sequentially to any new text, so the same patterns are recognised consistently. The algorithm makes no use of linguistic knowledge, word boundaries, or morphology. It operates purely on byte-level statistics, which makes it language-agnostic but also means the vocabulary is entirely shaped by the training corpus. Rare words, underrepresented languages, and out-of-distribution text will be tokenised less efficiently because the merge operations that would have captured their patterns were never learned.
Look closer
The algorithm is greedy and deterministic
At each step, count every adjacent pair in the corpus, find the single most frequent pair, and merge every occurrence of it into a new token. Add that token to the vocabulary and repeat. There is no backtracking, no optimisation across steps, no look-ahead. The merge that wins at step one stays merged forever, even if a different choice would have led to a better vocabulary overall. This greedy strategy makes the algorithm fast and predictable, but it also means the final vocabulary depends heavily on the corpus and the order in which ties are broken.
Frequency is counted after each merge
Once a pair is merged, the corpus is treated as though it now contains that merged unit, and pair counts are recalculated. If you merge "t" and "h" into "th", the next round counts "th" + "e" as a candidate pair, not "t" + "h" + "e". This cascading means common sequences build up hierarchically: "th" might merge with "e" to form "the", which might later merge with a leading space. The order of merges matters, because early merges change what pairs are available later.
The vocabulary size is chosen in advance
You decide how many tokens you want — say, 50,000 — and the algorithm runs for exactly that many merge operations beyond the initial 256 bytes. A larger vocabulary means fewer tokens per document, which can speed up processing and reduce the fragmentation of rare words, but it also means more embedding parameters to learn and store. A smaller vocabulary keeps the model compact but forces more words to be split into pieces. There is no single correct size; it is a trade-off set before training begins.
The story
Byte Pair Encoding was borrowed from data compression, where it was used to shrink files by replacing repeated byte sequences with shorter codes. Sennrich and colleagues adapted it in 2016 to build subword vocabularies for neural translation models, and it has since become one of the standard ways to turn text into tokens.
The algorithm starts with the smallest possible vocabulary: all 256 byte values, each one a token. Then it looks at the training corpus — which might be gigabytes of web text, books, or code — and counts every pair of adjacent tokens. Whichever pair appears most often is merged into a single new token, and that token is added to the vocabulary. The corpus is updated to reflect the merge, and the process repeats.
Suppose your tiny corpus is "low low low lower lower". Initially, every letter and space is separate. The pair "l" + "o" appears six times, more than any other, so it merges into a new token "lo". Now the corpus is "lo w lo w lo w lo wer lo wer". Next, "lo" + "w" appears five times, so it merges into "low". Then "low" + " " (space) appears three times and merges. Eventually "lower" might become a single token if the corpus were larger and the algorithm ran longer.
Each merge adds one entry to the vocabulary and changes what pairs are available in the next round. The algorithm is greedy: it takes the best option now without considering whether a different choice would lead to a better vocabulary later. This makes it fast but also means the final vocabulary is path-dependent, shaped by early decisions that cannot be undone.
The process stops when the vocabulary reaches the target size. The output is not just the list of tokens but the sequence of merge operations that created them. During tokenisation, those merges are applied in the same order to any new text, so the same patterns are recognised consistently.
Why it mattered then
Sennrich and colleagues were working on neural machine translation systems that struggled with rare and compound words. Traditional word-level vocabularies either grew impractically large or replaced uncommon words with a generic unknown token, losing information. Character-level models avoided that problem but produced long sequences that were slow to process and hard to learn from. Byte Pair Encoding offered a middle path. By learning which character sequences appeared frequently in the training data and merging them into single tokens, the algorithm built a vocabulary that captured common words whole while splitting rarer ones into recognisable pieces. A German compound like "Donaudampfschifffahrt" might become "Donau" + "dampf" + "schiff" + "fahrt", preserving the meaningful components rather than discarding the word entirely. The method was attractive because it required no linguistic knowledge. It worked on any script, any language, even on code or structured data, because it operated on byte sequences and frequency alone. The vocabulary emerged from the data rather than being imposed by a linguist's intuition about morphemes or word boundaries.
Why it matters now
Byte Pair Encoding remains one of the most widely used tokenisation algorithms in large language models. GPT-2, GPT-3 and many other systems use it or close variants. The simplicity and language-independence that made it useful in 2016 still matter when training on multilingual corpora that mix dozens of scripts and informal text that ignores conventional word boundaries. The algorithm's limitations have also become clearer at scale. Because it is greedy and corpus-dependent, the vocabulary it learns reflects the biases and gaps in the training data. Languages that were underrepresented in the corpus end up with fragmented, inefficient tokenisations, which affects both cost and model quality. A sentence in Yoruba might use three times as many tokens as the same sentence in English, not because the language is inherently more complex but because the merge algorithm saw less of it. There are newer methods — SentencePiece, which treats the input as a stream of Unicode characters rather than bytes, and unigram language models that optimise the vocabulary more globally — but Byte Pair Encoding's transparency and simplicity keep it in use. You can watch it build the vocabulary step by step, and the merge rules it produces are human-readable. For a system whose behaviour is otherwise difficult to interpret, that small piece of legibility still has value.
The surprising detail
The algorithm makes no attempt to respect word boundaries, morphemes, or meaning. It will happily merge "e" + "r" into "er" even when the "e" ends one word and the "r" starts the next, because it only sees frequency. The vocabulary it builds can contain fragments that cross linguistic boundaries in ways no linguist would propose, and yet the model learns to use them effectively. A token might be "ing" in one context, part of a URL in another, and a fragment of a variable name in code, and the model's embeddings somehow accommodate all three. The vocabulary is a statistical accident, not a designed system, but it works.
Remember this
The vocabulary is grown by counting pairs and merging the most frequent, over and over. It is learned, not designed.
Test yourself
You run Byte Pair Encoding on two corpora of the same size, one in English and one in a mix of fifty languages. Both produce 50,000-token vocabularies. Which vocabulary will likely tokenise new English text more efficiently, and why?
The English-only vocabulary will be more efficient on English text, because the merge algorithm spent all 50,000 operations learning pairs that appear in English. The multilingual vocabulary divided those operations across fifty languages, so it learned fewer English-specific patterns and more of its budget went to pairs that rarely appear in English documents. When you tokenise new English text with the multilingual vocabulary, more words will be split into smaller fragments because the merges that would have captured common English sequences were never learned or were learned later, after the budget was partly spent elsewhere. Efficiency is a function of how well the training corpus matched the text you tokenise later.
Go deeper
- Neural Machine Translation of Rare Words with Subword Units · arXiv · Rico Sennrich et al. · 2015-08-31
- SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing · arXiv · Taku Kudo et al. · 2018-08-19
Image: Original diagram, The Daily Triptych. Licence: Original work. Source.