Byte-Pair Encoding

Why Does This Exist?

A model reads numbers, not letters, so text has to be chopped into pieces first. That chopping is tokenization: each distinct piece gets an entry in a vocabulary, and each entry gets its own ID.

Word-level chopping breaks on the first unfamiliar word. Names, typos, code, and other languages keep producing words no fixed word list contains, and every one of them lands outside the vocabulary. Character-level chopping never gets stuck, since the character set is small and closed. But it turns ten words into fifty pieces, and every extra piece costs compute downstream. Subword chopping is the middle path: frequent stretches stay whole, and rare ones split apart.

That leaves one question you can't answer by hand: which stretches deserve their own entry? Nobody can list every useful fragment of every language in advance. Byte-pair encoding refuses to guess. It counts pairs in a real corpus and lets frequency decide, most frequent first.

This page covers the counting and merging algorithm itself. The granularity trade-off lives on the tokenization page, and the quirks the merges leave behind live on tokenization artifacts.

Think of It Like This

How It Actually Works

Training starts from single characters. Byte-level variants start from the 256 raw bytes instead, which guarantees every input can be covered. Call the set of pieces the vocabulary $V$. For every adjacent pair of symbols $(a, b)$ in the corpus, count its occurrences $c(a, b)$, weighting each word by how often it appears. Find the pair with the largest count, fuse every occurrence of it into a new symbol $ab$, and add that symbol to $V$. That is one merge. Recount with the new symbol in play and repeat, always merging the current winner, until you have performed a fixed number of merges chosen up front. Each merge adds exactly one entry, so the merge count sets the vocabulary size.

Worked example with real counts

Take a tiny corpus with frequencies attached:

• "low" appears 3 times
• "look" appears 2 times

Start from single characters and weight every pair by its word's frequency. From the three copies of "low" come $(l, o)$ three times and $(o, w)$ three times. From the two copies of "look" come $(l, o)$ twice more, plus $(o, o)$ and $(o, k)$ twice each. The totals are $c(l, o) = 5$, $c(o, w) = 3$, $c(o, o) = 2$, $c(o, k) = 2$. The winner is $(l, o)$, so merge 1 fuses it into a new symbol $lo$, and the vocabulary gains one entry.

Recount with $lo$ in play. The corpus now reads $[lo, w]$ three times and $[lo, o, k]$ twice. The pairs are $c(lo, w) = 3$, $c(lo, o) = 2$, $c(o, k) = 2$. The winner is $(lo, w)$, so merge 2 fuses it into $low$. This is the same picture as the diagram above: $lo$ forms before $low$ because the pair counts say so, and each merge added exactly one entry.

Encoding new text with the learned merges

To encode text the training corpus never contained, start from its characters and apply the learned merges in the order they were learned, skipping any that do not match, until none apply. Hand the trained merges the unseen word "lows": start from $[l, o, w, s]$, apply merge 1 where it matches to get $[lo, w, s]$, then apply merge 2 to get $[low, s]$. Two tokens, no retraining, no unknown-word failure. That decomposition is the whole payoff, and its output is what the next-token prediction objective consumes: IDs, not letters.

What it costs and when to skip it

Every merge shortens frequent text but grows the embedding table by one row, since each vocabulary entry needs its own vector (see embeddings). So the merge count trades sequence length against table size and data hunger: rare entries get updated rarely, which starves them of training signal. Set it with eyes open.

The method assumes your text looks like the counting corpus. Feed it something far away, another language or dense code, and familiar words shatter into tiny pieces while sequences balloon, so latency and cost follow token count instead of word count. When your data differs from the vocabulary's training mix, do not reuse the vocabulary blindly. Count tokens per word on your own sample first, then retrain or pick a vocabulary whose training mix matches yours.

Code

The point of this snippet is a check: run the two merges from the worked example and confirm the winners and counts match the hand computation.

1from collections import Counter2corpus: list[list[str]] = [list("low")] * 3 + [list("look")] * 23for step in range(2):4    counts: Counter[tuple[str, str]] = Counter()5    for w in corpus:6        for a, b in zip(w, w[1:]):7            counts[(a, b)] += 18    (a, b), n = counts.most_common(1)[0]9    out: list[list[str]] = []10    for w in corpus:11        new, i = [], 012        while i < len(w):13            hit = tuple(w[i:i + 2]) == (a, b)14            new.append((a + b) if hit else w[i])15            i += 2 if hit else 116        out.append(new)17    corpus = out18    print(step + 1, (a, b), n, corpus[0], corpus[3])19    # -> 1 ('l', 'o') 5 ['lo', 'w'] ['lo', 'o', 'k']20    # -> 2 ('lo', 'w') 3 ['low'] ['lo', 'o', 'k']

Both prints agree with the hand counts above: $(l, o)$ wins at 5, then $(lo, w)$ wins at 3. This loop counts pairs inside words only. Real implementations add an end-of-word marker for the same reason, so merges never fuse the end of one word to the start of the next.

Watch Out For

The Quick Version

• Byte-pair encoding learns a tokenizer vocabulary by merging the most frequent adjacent pair, one merge at a time.
• Each merge adds exactly one vocabulary entry, so the merge count you choose up front sets the vocabulary size.
• Frequent stretches fuse early into single tokens, while rare text stays split into small reusable pieces.
• New words are encoded by replaying the learned merges in order, so unseen words become known pieces instead of failures.
• The pieces carry frequency, not meaning: never read them as words, and never reuse a vocabulary far from the text it counted.

What to Read Next

• Tokenization Artifacts
• Embeddings
• Next-Token Prediction