BPE & WordPiece

This cover anchors BPE in its surprising origin: it was published in 1994 as a general-purpose data compression scheme, repurposed for tokenization decades later. The lineage matters because it explains the algorithm's character — it is mechanical and frequency-driven, with no linguistic knowledge baked in. Its power comes entirely from iterating one trivial operation many thousands of times.

The post walks the full training loop for BPE, contrasts WordPiece's merge criterion, and then shows how a trained tokenizer encodes new text. By the end the 'magic' of subword splitting should feel like plain bookkeeping.

This cycle captures the entire BPE training algorithm in four repeating steps. Count every adjacent pair of symbols across the corpus. Pick the single most frequent pair. Merge it into one new symbol and record the merge. Repeat until the vocabulary reaches its target size.

The elegance is that nothing in this loop understands language. It is pure frequency bookkeeping, yet running it tens of thousands of times produces a vocabulary that captures common words whole and rare words as sensible-looking fragments. Keep this four-step cycle in mind as the spine of everything that follows.

Training begins by pre-tokenizing the corpus into words (usually on whitespace) and then splitting each word into its individual characters, often with a special end-of-word marker so the algorithm can tell where words end. At this starting point the vocabulary is nothing more than the set of distinct characters that appear in the data.

Nothing has been merged yet. Every word is a sequence of single-character symbols. This atomic starting state is what guarantees the no-unknown-token property: since the base vocabulary contains all characters, any word can always be represented, even before a single merge happens.

This trace walks a textbook corpus through the first couple of merges so you can watch the vocabulary grow. Starting from characters, the algorithm counts adjacent pairs and finds (e, s) is the most frequent. It merges them into the new symbol 'es' and rewrites the corpus. On the next pass (es, t) becomes the top pair and merges into 'est'.

Following the symbols change line by line makes the loop concrete: each iteration adds exactly one new piece to the vocabulary and shortens the affected words by one symbol. Scale this from a handful of words to a billion-word corpus and tens of thousands of iterations, and you have a real tokenizer.

This step details the heart of the loop. After every merge, you re-scan the entire corpus and recount all adjacent symbol pairs, because a merge changes which pairs are adjacent. The most frequent pair is merged into a new symbol, that symbol is added to the vocabulary, and the merge itself is appended to an ordered list of merge rules.

That ordered merge list is the crucial output, not just the vocabulary. Because merges were learned in a specific sequence, they must be replayed in that same sequence to tokenize new text correctly — a point that becomes important when we reach encoding.

WordPiece keeps the exact same iterative structure but swaps the selection rule, and the change is subtle but meaningful. Rather than merging the most frequent pair, it merges the pair that most increases the likelihood of the training corpus under a unigram language model. In practice this is approximated by a score: the frequency of the pair divided by the product of the frequencies of its two parts.

Dividing by the parts' frequencies penalizes merges where the pieces are already individually common, and rewards merges where the pieces appear together far more than chance would predict. The effect is that WordPiece favors merges that are genuinely informative rather than merely frequent, which is why its splits often look slightly more meaningful than raw BPE's.

This side-by-side isolates the one real algorithmic difference between the two methods. BPE maximizes raw frequency: merge whatever pair occurs most, full stop — simple, fast, and effective. WordPiece maximizes data likelihood, using the score of pair-count divided by the product of part-counts, a probability-flavored criterion.

Everything else — starting from characters, the merge-and-repeat loop, the target vocabulary size — is shared. When people ask 'what's the actual difference between BPE and WordPiece', this comparison is the precise answer: it is the merge criterion, plus surface conventions like the '##' marker.

Encoding new text uses what training produced, and the two algorithms diverge here too. BPE replays its ordered list of merge rules: start from characters, then apply each learned merge in order wherever it matches, until no more rules apply. The result is determined entirely by the merge sequence.

WordPiece instead does greedy longest-match. Starting at the beginning of each word, it finds the longest piece in the vocabulary that matches, emits it, marks any continuation with '##', and repeats on the remainder of the word. If no piece matches, it falls back to the unknown token. Both approaches are fast and deterministic, but they can split the same word slightly differently.

This snippet implements BPE encoding from scratch so the mechanism is undeniable. The function takes a word as a list of characters and a list of merges in their learned order. For each merge rule, it scans the token list and fuses any adjacent occurrence of that exact pair into a single token, then moves to the next rule.

Applying the rules in learned order is the load-bearing detail — it is why 'es' must be formed before 'est' can be. Running this on 'newest' with the merges from the worked example reproduces the same step-by-step fusion shown earlier, proving the trace and the code describe one and the same process.

Two practical refinements separate textbook BPE from what ships in real models. First, GPT-style models use byte-level BPE: instead of starting from characters, they start from the 256 byte values. This means the base vocabulary can represent any possible input — every Unicode character, emoji, and control byte — so an unknown token is literally impossible.

Second, WordPiece uses the '##' prefix convention to encode word boundaries into the pieces themselves. 'playing' becomes 'play' followed by '##ing', where the '##' signals 'this continues the previous piece rather than starting a new word'. This lets the model and the decoder reconstruct the original spacing unambiguously. These two details account for most of the visible differences when you inspect real tokenizer output.

This recap distills the algorithm into five recallable steps: start from characters (or bytes), count adjacent pairs, merge the best pair and repeat, where BPE's 'best' means most frequent and WordPiece's means highest likelihood, and finally encode new text by applying the learned merges in order.

Those five lines are the complete operating model of subword training. Everything fancier — byte-level fallback, '##' markers, target vocabulary sizes — is detail layered on top of this skeleton.

Theory is most convincing when you can run it. Post 4 turns this algorithm into working code: you will train a real BPE tokenizer on a tiny corpus with Hugging Face's tokenizers library, inspect the vocabulary and merges, then train a WordPiece tokenizer and compare how the two split the same words.

You will also pull in tiktoken to see the actual GPT-4 tokenizer in action. After post 4 the loop described here will not be abstract — you will have built it yourself.