Build Your Own BPE Tokenizer — Learning Merge Rules, and Getting Punished by Japanese

Write the BPE trainer and encoder yourself. Why the artifact of training is an ordered rulebook rather than a vocabulary, how to stop recounting the corpus on every merge, why the first few thousand merge slots in Japanese are spent assembling characters, and how to run a vocabulary-size sweep that actually means something.

Neural Machine Translation of Rare Words with Subword Units

What Calling the API Never Shows You

Any tokenizer is three lines away: AutoTokenizer.from_pretrained, then encode. Which is exactly why the questions are hard to answer when someone asks them. Why did it split there? Why does the same word get a different ID at the start of a sentence than in the middle?

The conceptual map lives in Tokenizers from Scratch. This article is the sequel, and it puts you on the other side: writing the trainer and the encoder yourself. Two hundred lines gets you something that works. The interesting part is that the moment you write it, nearly every production pitfall shows its face. Garbled streaming output, the accidents that follow adding tokens to a vocabulary — the causes are all in the code below.

An Analogy: A Stenographer Inventing Shorthand

Say you take shorthand for a living. Your only symbols are letters and digits. Sitting through meetings, you notice "thank you very much for your time" appears dozens of times a day, so you invent a new symbol ① for that whole run. The next most common phrase gets ②. The more symbols you invent, the shorter the same transcript becomes.

Two properties matter later. First, new symbols can be built from old ones. Once "thank you" has a symbol, "thank you very much" can be written as ⟨that symbol + very much⟩. Symbols snowball.

Second, the order has to be recorded or nothing reproduces. Hand someone the same symbol table and they will still produce a different transcript if they apply the symbols in a different order. The table alone is not enough. The order is the rule.

BPE training is exactly this, done mechanically over a whole corpus.

The Intuition: Training Produces an Order, Not a Vocabulary

"Training a BPE" sounds like building a list of frequent words. What actually gets built is an ordered sequence of merge rules: line 1 says "glue e to s", line 2 says "glue es to t", and so on. The vocabulary is a by-product of that rulebook.

Why is the order the real artifact? Because when the encoder meets est, the only thing deciding between ⟨e + st⟩ and ⟨es + t⟩ is which rule was learned first. Frequencies are done doing their job the moment training ends; what survives is the sequence.

So a shipped tokenizer is a pair: a vocabulary file (token → ID) and a merges file (the rules in the order they were learned). That is why HuggingFace's tokenizer.json carries both vocab and merges — and why swapping two lines gives you a different tokenizer with an identical vocabulary.

The Mechanism: How Much Does One Merge Buy?

Training is three verbs. Count, pick, glue.

Equation (1) is one sentence written in symbols, which says: of the adjacent pairs you just counted, take the one that occurs most often. $\arg\max$ means "return the argument that maximises this", and $\mathrm{count}(a,b)$ is the number of times $b$ immediately follows $a$. Nothing about meaning, grammar or word boundaries enters into it — the winner is whichever pair the corpus happens to repeat most.

The reason that rule is sensible is that the count is the saving. Replace the pair $(a,b)$ with one new token and every occurrence goes from two tokens to one.

Equation (2), in words: one merge shrinks the corpus token count $L$ by exactly the number of occurrences, and grows the vocabulary size $|V|$ by one. $L$ is how long the whole corpus becomes once tokenised, $|V|$ is how many distinct tokens exist, and the two arrows point in opposite directions on every single merge. Maximise the shortening you can buy for a fixed price of one vocabulary slot — that is the greedy objective, and it is what people mean when they call BPE a compression algorithm in disguise.

One caveat. Applying (a,a) to aaa fires only once when you scan left to right, so the real saving is slightly below equation (2). It sounds like a footnote, but when your homemade BPE disagrees with a reference implementation, the culprit is almost always an edge case of exactly this kind.

Implementation 1: The Naive Version

Turn equation (1) straight into code. Hold the corpus as a dictionary from pre-tokenized chunk to count, with each chunk stored as a sequence of bytes.

from collections import Counter

def train(corpus, n_merges):          # corpus: Counter[tuple[bytes, ...]]
    merges = []
    for _ in range(n_merges):
        pairs = Counter()
        for word, f in corpus.items():
            for p in zip(word, word[1:]):
                pairs[p] += f          # recount every adjacent pair
        if not pairs:
            break
        (a, b), _ = pairs.most_common(1)[0]
        merges.append((a, b))
        corpus = Counter({apply(w, a, b): f for w, f in corpus.items()})
    return merges                      # rules, in the order learned