Paper: Byte Pair Encoding — LLMs Part 4

Sennrich, Haddow & Birch, “Neural Machine Translation of Rare Words with Subword Units” (2015)

The Problem

A model with a fixed vocabulary (Part 3) can’t handle a word it has never seen — a made-up word, a rare name, a typo. Before this paper, tokenizers often replaced that word with a generic “unknown” token, throwing the information away.

The Core Idea

Instead of a vocabulary of whole words, build one out of frequently occurring pieces, so any word — seen before or not — can be spelled using pieces the model does know.

Characters alone would already solve that problem — every possible piece already exists, nothing is ever truly unseen. The real cost is length: a model reads and predicts one token at a time, so spelling ordinary text out one character at a time multiplies how many steps that takes, for text that’s already easy to say more compactly (Part 3). Merging trades some of that flexibility back for efficiency: common sequences collapse into single tokens, so ordinary text stays short, while anything the training data never saw still falls back to individual characters instead of breaking entirely.

The paper adapted byte pair encoding (BPE), an older data-compression algorithm, to build this piece vocabulary. BPE starts with every individual character as its own token, then repeatedly finds the most frequent adjacent pair of tokens in the training text and merges that pair into one new token, built entirely from data instead of a hand-written word list.

The algorithm has exactly one real setting: how many merges to run. More merges builds a larger vocabulary of longer, more specific pieces; fewer merges builds a smaller vocabulary of shorter, more general ones. The final vocabulary size is the starting character count plus however many merges were run — a direct knob on the tradeoff Part 3 described between vocabulary size and how finely words get split.

That number isn’t something the algorithm works out on its own — like a model’s size, it’s chosen ahead of time by whoever trains the tokenizer, then fixed for that vocabulary’s whole lifetime. The paper itself tested merge counts in the tens of thousands (59,500 for a single-language vocabulary, 89,500 for a shared vocabulary across two languages) and kept whichever produced the best translation quality on held-out data. In practice today, a new project is more likely to start from an existing model’s vocabulary size, like GPT-2’s 50,000, than to re-run that search from scratch.

One more detail matters for correctness. The algorithm marks where each word ends (commonly written </w>) before counting pairs, so a piece like “est” at the end of a word (“widest”) is tracked separately from the same two letters appearing mid-word (“establish”) — without that marker, the algorithm would wrongly treat both as the same recurring pair and merge them together.

Learning the Vocabulary

Training repeats one simple loop until the vocabulary reaches its target size:

flowchart LR
    A["count every adjacent<br/>pair across the training text"] --> B["merge the single<br/>most frequent pair<br/>into one new token"]
    B --> C["↺ repeat, using the<br/>updated text, until<br/>target vocab size is reached"]

    accTitle: The byte pair encoding training loop
    accDescr: Count every adjacent pair in the training text, merge the single most frequent pair into one new token, then repeat using the updated text until the vocabulary reaches its target size.

Each merge adds exactly one new token to the vocabulary, so the number of merges run is a direct, chosen input to training — not something the algorithm discovers on its own.

Worked Example

Starting vocabulary: individual letters. Training text (as characters): l o w, l o w, l o w e r, n e w, n e w e r.

Step 1: most frequent adjacent pair is (l, o) -> merge into "lo"
Step 2: most frequent remaining pair is (lo, w) -> merge into "low"
Step 3: most frequent remaining pair is (n, e) -> merge into "ne"
... repeat until the vocabulary reaches its target size

Common chunks like low become single tokens quickly. Rare combinations stay split into smaller pieces — an unseen word gets spelled out of the pieces the model does have, character by character if it has to.

Applying It to New Text

The merges learned during training don’t just build the vocabulary — they double as the rulebook a tokenizer applies to brand-new text (Part 3), in the exact order they were learned:

flowchart LR
    W["new word, split<br/>into individual characters"] --> M["apply the learned<br/>merges, in the order<br/>they were learned"]
    M --> T["a sequence of<br/>vocabulary tokens"]

    accTitle: Applying learned BPE merges to new text
    accDescr: A new word is split into individual characters, the learned merges are applied in the order they were learned, and the result is a sequence of vocabulary tokens.

A word the algorithm merged early and often, like low, collapses into one token almost immediately. A word that shares none of its structure with anything in the training text never matches an available merge, and stays split into individual characters — exactly the worst-case, one-piece-at-a-time behavior Part 3 described for unrecognized input, without ever falling back to a generic “unknown” token.

Why This Paper Matters

This is the algorithm behind the vocabularies described in Part 3. GPT-2’s entire 50,257-token vocabulary, for example, is built exactly this way, by its own paper’s account: 256 starting bytes (a byte-level variant of the character-level version above), 50,000 learned merges, plus one special end-of-sequence token — a real, count-for-count example of the training loop above, running at production scale.

It’s also the actual mechanism behind two things Part 3 only stated as facts: why a rare word costs more tokens than a common one, and why non-English text often costs more too. A piece only becomes its own single token if it was frequent enough in the training data to earn a merge. Rare words, and words from languages the training data had less of, earn fewer merges, so they stay split into more, smaller pieces — while common words and phrases, trained on far more data, collapse into single tokens almost immediately.

---

Next: Embeddings — how a token’s number becomes a representation of meaning. (Coming soon.)