Tokenization II: BPE, step by step

01 · Concept

Concept

Lesson 1.2 asserted that subword pieces are learned from a corpus and left the learning unexplained. This lesson does it by hand, with a corpus small enough to count on paper, because the algorithm is genuinely simple and the interesting part is what happens between the merges.

Take a corpus containing three words with these frequencies: low five times, lower twice, and lowest three times. Split every word into characters and append an end-of-word marker, written here as an underscore so that a piece ending a word is distinguishable from the same piece in the middle of one. The corpus is now l o w _ at count 5, l o w e r _ at count 2, and l o w e s t _ at count 3.

Count every adjacent pair, weighting by word frequency. The pair l o appears in all three words, giving $5 + 2 + 3 = 10$. The pair o w likewise gives 10. The pair w _ appears only in low, giving 5. The pair w e appears in lower and lowest, giving 5. Then e r gives 2, r _ gives 2, e s gives 3, s t gives 3, and t _ gives 3. Two pairs are tied at the top, so the implementation’s tie-breaking rule decides; take l o.

Merge it everywhere. The corpus becomes lo w _ at 5, lo w e r _ at 2, and lo w e s t _ at 3. Here is the step people skip: the counts must be recomputed. The pair l o no longer exists anywhere, and a new unit lo has appeared with new neighbours. Recounting gives lo w at 10, which now wins outright. Merge it, and the corpus becomes low _ at 5, low e r _ at 2, low e s t _ at 3, with the vocabulary having gained the piece low.

Recount again. Now low _ occurs 5 times and low e occurs $2 + 3 = 5$ times, tied, with e s, s t, and t _ at 3 apiece and e r, r _ at 2. Suppose the tie-break takes low _, producing a single unit for the standalone word low. The fourth merge then takes low e, giving the shared stem of lower and lowest. Four merges in, the algorithm has independently discovered something that looks like a morpheme, and it discovered it for a purely statistical reason: that string kept being adjacent to itself.

Every decision above is greedy. The algorithm selects the best pair under the current segmentation, never reconsidering, and never planning toward a globally optimal vocabulary. Tie-breaking, the representation of word boundaries, the normalization applied beforehand, and the choice of base units are all implementation decisions, which is why two tools that both say BPE need not produce identical tokenizers.

Now the distinction that matters in production. Training learns a vocabulary and an ordered list of merge rules. Encoding applies that fixed list. A common misreading is that encoding works by scanning the vocabulary for the longest entry that matches, the way a dictionary lookup would. It does not, and the difference is observable. Encoding applies merges in learned rank order: split into base units, then repeatedly apply the highest-ranked merge that is currently applicable. A long piece can sit in the vocabulary and still never be produced for a given input, because the merge sequence that would build it is not reachable from that input’s intermediate state. Ship a model with only the vocabulary and no merge ranks and its tokenizer becomes unreproducible, even though every piece is present.

Encoding also never recounts anything from your prompt. If it did, the same word could tokenize differently on Tuesday, and every id addresses an embedding row that learned its value under one specific mapping. The merge list is part of the model contract, exactly as lesson 1.2 argued for the vocabulary.

Frequency creates efficiency and bias in the same motion. Strings common in the training corpus become single tokens and consume one position; strings rare there remain long chains, however ordinary they are to their speakers. Capitalization, whitespace, and normalization all change which pairs were available to merge. The algorithm has no concept of a morpheme. It sometimes finds them, purely because a meaningful unit tends to be a reusable one.

Vocabulary size is the governing trade. More merges shorten common sequences but enlarge the embedding table and the output projection, which for Qwen3.8-27B means 5120 numbers per row, twice over, since its input and output matrices are separate. Fewer merges shrink those matrices and lengthen every sequence, raising attention and decoding work. Lesson 5.3 revisits the choice from the training side; there is no universal token-to-word ratio to appeal to.

The durable image is a ladder of reusable chunks. Start with units that can spell any valid normalized Unicode string, promote the most frequent adjacent combination one rung at a time, and keep a numbered log of the promotions so the climb can be repeated exactly. The ladder compresses surface patterns. What those pieces mean is still entirely the neural network’s problem.