Gen AI

Byte-Pair Encoding

Start from individual characters and repeatedly merge whichever adjacent pair appears most often in the training corpus, building a vocabulary of frequent fragments one merge at a time.

Why Does This Exist?

Tokenization settled on subword units as the practical middle ground between word-level and character-level splitting, but that raises an immediate question: which fragments, exactly, deserve their own token? Nobody sat down and manually decided that ing, token, and the should each get a dedicated vocabulary slot while xqz shouldn't. That would require someone to anticipate every useful fragment across every language and domain a model might ever encounter — an impossible amount of manual specification.

Byte pair encoding sidesteps hand-specification entirely by learning the vocabulary directly from data. Instead of a person deciding what counts as a useful fragment, the algorithm looks at an enormous body of text and lets frequency decide: whatever adjacent pair of symbols shows up together most often gets merged into a new, single symbol. Repeat that process enough times, and the vocabulary that falls out reflects the actual structure of the language it was trained on, not a human's guess at it.

Think of It Like This

Building a shorthand by noticing what you write most

Imagine someone taking notes by hand, and over time inventing their own shorthand: every time they notice they've written the same two-letter sequence in a row unusually often, they invent a single squiggle for it and use the squiggle from then on. Do this repeatedly — first for the most common two-letter sequence, then the next most common combination once the first shorthand is in place — and after a while their notes are full of compact squiggles for whatever they actually write often, while rare sequences stay spelled out letter by letter because they never came up often enough to earn their own squiggle.

Byte pair encoding is that exact process, run automatically over a training corpus instead of over one person's handwriting: merge the most frequent adjacent pair, over and over, and stop after a fixed number of merges.

How It Actually Works

The merge loop

Start with every word in the training corpus broken down into its individual characters (or bytes, in byte-level variants) — the diagram above starts with l, o, w, e as four separate symbols. Count every adjacent pair of symbols across the entire corpus, find the single most frequent pair, and merge every occurrence of it into one new symbol. In the diagram, l and o co-occur often enough to merge first, producing lo. Recount pairs with this new symbol in play, merge the next most frequent pair — lo and w merge into low — and repeat.

Each merge step adds exactly one new entry to the vocabulary. Training stops after a predetermined number of merges, which is really a predetermined target vocabulary size — common choices for real tokenizers run from roughly 30,000 to over 100,000 merges, chosen as a training hyperparameter before the algorithm ever runs.

Why frequency-based merging produces a good vocabulary

The key property is that merges happen in frequency order, so the earliest, most impactful merges get made first. Extremely common patterns — common whole words, common suffixes like -ing or -ed in English — accumulate enough merges early on to become single tokens. Rare combinations never accumulate enough frequency to be worth merging, so they stay broken into smaller, more general pieces. The vocabulary that results isn't designed; it's discovered, directly from how often things actually co-occur in the corpus the tokenizer trained on.

Applying a trained vocabulary to new text

Once training is done, the sequence of merges learned becomes a fixed set of rules applied, in the same order, to any new text. A word the tokenizer has never seen as a whole simply gets broken down using whichever merges do apply to it — if tokenizing was never in the training data as a unit but token and izing were both learned merges, the new word decomposes into those two known pieces rather than failing or falling back to individual characters. This is the direct mechanism behind the out-of-vocabulary fix that motivates subword tokenization in general.

Show Me the Code

A minimal byte pair encoding training loop over a tiny corpus, merging the single most frequent pair at each step.

1from collections import Counter2
3
4def get_pair_counts(corpus: list[list[str]]) -> Counter:5    counts = Counter()6    for word in corpus:7        for a, b in zip(word, word[1:]):8            counts[(a, b)] += 19    return counts10
11
12def merge_pair(corpus: list[list[str]], pair: tuple[str, str]) -> list[list[str]]:13    merged = "".join(pair)14    new_corpus = []15    for word in corpus:16        new_word, i = [], 017        while i < len(word):18            if i < len(word) - 1 and (word[i], word[i + 1]) == pair:19                new_word.append(merged)20                i += 221            else:22                new_word.append(word[i])23                i += 124        new_corpus.append(new_word)25    return new_corpus26
27
28corpus = [list("low"), list("lower"), list("lowest")]     # three words, split into characters29for step in range(2):30    best_pair = get_pair_counts(corpus).most_common(1)[0][0]31    corpus = merge_pair(corpus, best_pair)32    print(f"merge {step + 1}: {best_pair} ->", corpus)33# -> merge 1: ('l', 'o') -> [['lo', 'w'], ['lo', 'w', 'e', 'r'], ['lo', 'w', 'e', 's', 't']]34# -> merge 2: ('lo', 'w') -> [['low'], ['low', 'e', 'r'], ['low', 'e', 's', 't']]

Two merges recover exactly the low symbol the diagram builds by hand — l+o merges first because it's the most frequent pair across all three words, then lo+w merges next for the same reason.

Watch Out For

Assuming merges are linguistically meaningful

Because the resulting fragments often look like recognizable morphemes — prefixes, suffixes, word stems — it's tempting to assume byte pair encoding has learned linguistic structure on purpose. It hasn't; it's purely counting adjacent-symbol frequency, with no notion of grammar, morphology, or meaning at all. Fragments that look linguistically sensible are a byproduct of frequent patterns in real language often being linguistically sensible, not evidence the algorithm understands language. Genuinely odd merges — splitting a word in a linguistically nonsensical place — happen whenever frequency alone points that way.

Retraining a vocabulary without accounting for corpus shift

A byte pair encoding vocabulary reflects whatever corpus it was trained on, and applying it to text from a very different domain or language mix than that training corpus produces measurably worse tokenization efficiency — more fragments, less coverage by common whole-word tokens. Reusing an English-web-trained vocabulary for a code-heavy or multilingual application, without retraining or extending it, is a common source of the token-cost imbalance covered on the tokenization page.

The Quick Version

Byte pair encoding builds a subword vocabulary by repeatedly merging the most frequent adjacent pair of symbols in a training corpus.
Each merge adds exactly one new vocabulary entry; training stops at a target vocabulary size, not a fixed rule count.
Frequent patterns accumulate merges early and become compact tokens; rare patterns stay broken into smaller, more general pieces.
Applying a trained vocabulary to new text reuses the same learned merge rules, decomposing unseen words into known fragments.
The resulting fragments are frequency-driven, not linguistically designed, even when they happen to look like real morphemes.