Building BPE from scratch

A word-level tokenizer has two problems that no amount of data fixes: the vocabulary is huge, and any word it never saw collapses to <|unk|> (the previous post, Why word-level tokenizers break, shows both). Byte-Pair Encoding solves both by refusing to work with whole words at all.

The algorithm is surprisingly small:

• Start from single characters. The base vocabulary is the 256 single-byte characters (production BPE uses raw UTF-8 bytes instead — see caveats). Every in-range string is expressible in them, so nothing is ever out-of-vocabulary.
• Merge the most frequent adjacent pair. Count every neighbouring pair of tokens across the corpus, merge the most common one into a single new token, record that merge, and repeat until the vocabulary reaches the target vocabulary size.

Why merge the most frequent pair? Because the most common character sequences usually represent meaningful language patterns-common words, prefixes like un, or suffixes like ing. Each merge turns a frequently repeated sequence into a single token, reducing the number of tokens needed for typical text. Rare or unseen words can still be represented by falling back to smaller subword pieces.

Training produces an ordered list of merges. Encoding replays them. That ordering is the whole trick, and it falls straight out of the code.

Strip away the bookkeeping and training is eight lines: count pairs, merge the winner, record it, repeat.

for new_id in range(len(self.id_to_token), vocab_size):
    counts = self._count_pairs(words)          # count adjacent pairs
    if not counts:
        break
    pair, freq = counts.most_common(1)[0]      # pick the most frequent
    if freq < 2:
        break
    words = [self._merge(word, pair, new_id) for word in words]
    self.merges[pair] = new_id                 # record rank via insertion order
    self._add_token(self.id_to_token[pair[0]] + self.id_to_token[pair[1]], new_id)

(Recounting every pair each iteration is O(corpus × vocab) - fine here; real implementations count unique words with their frequencies instead.)

One detail makes this work: merges are stored in a dictionary, whose insertion order defines their rank. During encoding, the earliest learned merge is applied first, via min(..., key=self.merges.get), ensuring the same merge order used during training.

Encoding is training's mirror image: instead of learning merges, it replays them - always applying the earliest-learned merge available.

def _encode_word(self, word):
    ids = [self.token_to_id[c] for c in word]
    while len(ids) >= 2:
        # earliest-learned applicable merge wins
        pair = min(zip(ids, ids[1:]), key=lambda p: self.merges.get(p, float("inf")))
        if pair not in self.merges:
            break
        ids = self._merge(ids, pair, self.merges[pair])
    return ids

Everything else is plumbing - splitting text into words, counting pairs, and the space marker. The space marker is worth one note: following GPT-2, the space before each word is marked with Ġ, so spaces survive the round-trip.

Here's the complete class:

This is a first-iteration implementation built for clarity, not a production tokenizer - the honest caveats are collected at the end.

Same sentence, both tokenizers

Here is the exact sentence from the previous post, run through both tokenizers. Each chip is one token; color encodes token length (pale yellow for a single character up to deep orange for a long piece), and · marks a space that belongs to the token.

Loading comparison…

The word-level row has dropped the capital S and the punctuation entirely. The BPE row keeps everything - case, comma, question mark, and the spaces - by splitting into shorter subword pieces. Hover a chip to see where the same piece is reused.

Watching the merges form

Training is easier to understand when you can watch it happen. The loop below replays BPE training on a tiny corpus - the cat sat the cat sat - building the vocabulary from the ground up. It starts with individual characters, then repeatedly merges the most frequent adjacent pair; the caption names that pair and how often it appears before the two fuse into one token. Each merge appears on its own line, so over five steps you can watch at (shared by both cat and sat), then the, then Ġcat emerge. Hover over any token to see its token id and merge rank, with the merge order reflecting the tokenizer's training history.

Loading merge steps…

Turn the vocabulary size into a dial

This is the payoff. Type any text below and watch it run through a real trained BPE tokenizer.

Move the merges slider to see how the tokenizer evolves-from single-byte tokens to longer subwords as more learned merges are applied. Turn on show ids to see the token sequence shrink as the vocabulary grows.

Notice there is no <|unk|>, even for a made-up word or your own name - every in-range character is already a token, so BPE can always fall back to single characters.

A few simplifications remain. The tokenizer only supports the first 256 characters, so on emoji and most non-Latin scripts the Python _encode_word raises a KeyError; the playground above catches that and flags them out of range rather than inventing an encoding. Production byte-level BPE instead works on raw UTF-8 bytes, which avoids this limitation.

It also treats the first word differently (the vs Ġthe), matching GPT-2, and doesn't special-case tokens like <|endoftext|> during encoding—they're split into subwords instead.¹