Byte-Pair Encoding Explained by Building One

Byte-pair encoding was a data compression algorithm published by Philip Gage in 1994 and repurposed for neural machine translation by Sennrich, Haddow and Birch at ACL 2016. It is simple enough to implement over a coffee, and implementing it is the fastest way to stop finding tokenizer behaviour mysterious.

The algorithm, in one sentence

Start with every text represented as a sequence of single characters, repeatedly find the adjacent pair that occurs most often across the whole corpus, and replace every occurrence of that pair with a new single symbol. Record the merges in order. That ordered list is the tokenizer.

Everything else — vocabulary size, compression ratio, which languages are cheap — is a consequence of what corpus you counted pairs in and how many merges you stopped after.

Two things about that are worth holding on to before the code. The algorithm has no notion of meaning, morphology or language; it is counting adjacent symbol pairs and nothing else. And it is greedy at training time as well as at encoding time — it takes the most frequent pair now rather than the pair that would lead to the best vocabulary eventually, which is why BPE vocabularies contain a certain amount of visible junk alongside the sensible prefixes and suffixes.

A trainer you can run

The corpus below is the toy one from the Sennrich paper, which is useful because you can verify the first merges by eye:

from collections import Counter

def pair_counts(words):
    """words: {tuple_of_symbols: frequency}"""
    pairs = Counter()
    for syms, freq in words.items():
        for i in range(len(syms) - 1):
            pairs[(syms[i], syms[i + 1])] += freq
    return pairs

def apply_merge(words, pair):
    a, b = pair
    out = {}
    for syms, freq in words.items():
        merged, i = [], 0
        while i < len(syms):
            if i < len(syms) - 1 and syms[i] == a and syms[i + 1] == b:
                merged.append(a + b)
                i += 2
            else:
                merged.append(syms[i])
                i += 1
        out[tuple(merged)] = out.get(tuple(merged), 0) + freq
    return out

corpus = ("low " * 5 + "lower " * 2 + "newest " * 6 + "widest " * 3).split()
words = Counter(tuple(w) + ("</w>",) for w in corpus)

merges = []
for step in range(10):
    stats = pair_counts(words)
    if not stats:
        break
    best = max(stats, key=stats.get)
    merges.append(best)
    words = apply_merge(words, best)
    print(f"{step:2d}  {best!s:20s} count={stats[best]}")

print("vocab:", sorted({s for syms in words for s in syms}))

The </w> marker is there so the algorithm can tell a word ending from a word interior — without it, est at the end of newest and est in the middle of estimate would be the same symbol and the merges would be worse. Run it and you will watch e + s become es, then es + t become est, then est + </w> become a suffix token. That is morphology being discovered by counting, with no linguistics in the code at all.

Encoding with the merges

Training produced an ordered list. Encoding replays it: split the input into characters, then repeatedly apply the earliest-learned merge that still matches, until none do.

rank = {pair: i for i, pair in enumerate(merges)}

def encode_word(word):
    syms = list(word) + ["</w>"]
    while True:
        cands = [(rank[(syms[i], syms[i+1])], i)
                 for i in range(len(syms) - 1)
                 if (syms[i], syms[i+1]) in rank]
        if not cands:
            return syms
        _, i = min(cands)
        syms[i:i+2] = [syms[i] + syms[i+1]]

Two properties of real tokenizers are visible here. Encoding is greedy and order-dependent, so it is deterministic but not optimal — there are shorter valid segmentations that BPE will not find. And it is local: a merge is chosen without looking at the rest of the sentence, which is why inserting one character can change the tokenization of the word around it and, occasionally, why a prompt behaves differently after a trivial edit.

What production tokenizers add

• A byte-level alphabet. GPT-2 introduced BPE over the 256 possible bytes rather than over Unicode characters. Because every byte is in the base vocabulary, nothing is ever out-of-vocabulary — an unseen emoji or a corrupt file encodes to several byte tokens instead of failing. Most current families inherit this.
• A pre-tokenizer. Before any merging, the input is split by a regex into word-ish chunks, and merges are never allowed to cross those boundaries. This is why tokens carry a leading space rather than a trailing one, and why no token ever spans two words.
• Special tokens. Sequence starts, turn markers, padding and end-of-turn symbols are added to the vocabulary directly, not learned. They are the subject of a whole class of bug — see chat templates.
• Digit and whitespace rules. Several families explicitly pre-split runs of digits, and some collapse or specially encode long runs of spaces so that indented code does not explode.

The one parameter you choose is where to stop. Merge count plus base alphabet is the vocabulary size, and it is a trade rather than a maximisation: more merges means fewer tokens per document, which is cheaper to serve and fits more into a window, but it also means a larger embedding matrix and a larger output projection, both of which scale linearly with the vocabulary. For a 1B-parameter model a 256,000-entry vocabulary is a substantial fraction of the whole model; for a frontier model it is a rounding error. That asymmetry, not linguistics, is why small models still ship small vocabularies.

The other family: unigram

Not everything is BPE. SentencePiece, introduced by Kudo and Richardson (EMNLP 2018 system demonstrations), supports a unigram language model tokenizer that works the other way round: start from a large candidate vocabulary and prune it, keeping the pieces that maximise the likelihood of the corpus. It operates on the raw byte stream with no pre-tokenization step, marking spaces explicitly, which makes it clean for languages that do not use spaces at all.

Practically, the difference matters in two places: unigram can produce multiple valid segmentations of the same string and expose that as regularisation during training, and SentencePiece-based vocabularies handle CJK and other space-free scripts more gracefully than English-regex pre-tokenization does. Both families end at the same place, though — an ordered set of pieces, an integer per piece, and a count you are billed on.

A last observation that the toy trainer makes concrete. Nothing in the algorithm has any concept of a word, a morpheme or a language; it discovered est as a unit purely because those three characters co-occurred. That is simultaneously why BPE transfers to code, to protein sequences and to languages nobody planned for, and why its coverage is a direct photograph of its training corpus with all of that corpus’s imbalances baked in and frozen. Every downstream property in this cluster — the language tax, the count mismatches, the differences between families — traces back to that one loop.