Tokenization II: BPE, step by step

1

Concept

Byte-pair encoding began as a compression idea and became a family of subword-tokenizer procedures. Its central move is simple: find a frequent adjacent pair of current units, replace that pair with a new combined unit, then repeat. The resulting vocabulary preserves small fallback pieces while allocating single tokens to strings that occur often enough to justify them.

Take a toy corpus containing low, lower, and lowest. Begin with characters plus an end-of-word marker: l o w </w>, l o w e r </w>, and l o w e s t </w>. Count adjacent pairs over their corpus frequencies. If (l,o) wins, create lo and replace every eligible occurrence. The sequences become lo w .... Counts must then be recomputed because old neighbors vanished and new pairs such as (lo,w) appeared.

Suppose (lo,w) wins next. The vocabulary gains low. A later merge might combine (e,r) or (low,</w>). Each decision is greedy: it selects the best pair under the current segmentation, not a globally optimal final vocabulary. Tie-breaking, word-boundary representation, normalization, and initial units are implementation choices, so two tools both called “BPE” need not produce identical tokenizers.

Training the tokenizer and using it are distinct. Training learns a vocabulary and ordered merge rules from a corpus. Encoding a prompt applies those fixed rules. A common implementation begins with base pieces and repeatedly applies the highest-priority available merge. It does not update pair frequencies from the user’s prompt. If tokenization changed online, the same ID could cease to match the embedding row learned during model training.

Frequency creates both efficiency and bias. Common words or fragments become single tokens and consume fewer sequence positions. Rare names, specialized terms, or strings from underrepresented languages may remain long chains. Capitalization, whitespace, and normalization can alter available pairs. The algorithm has no linguistic notion of a morpheme: it may discover meaningful pieces, but only because those strings are statistically reusable.

BPE avoids a hard unknown-word problem as long as its base alphabet covers the input. Character-based variants need a policy for unseen characters. Byte-level variants start from bytes, so any encoded input can be represented, at the cost of potentially awkward pieces and longer sequences. Special tokens for boundaries, padding, or control need protected handling so ordinary merges cannot accidentally manufacture their semantics.

Vocabulary size creates a trade-off. More merges shorten common sequences but enlarge the embedding and output matrices. Fewer merges reduce vocabulary storage but lengthen sequences, increasing attention and decoding work. The best choice depends on languages, domains, model size, and the relative cost of vocabulary parameters versus sequence positions. There is no universal token-to-word ratio.

To debug BPE, retain the training corpus policy, normalization, base alphabet, merge list, special-token definitions, and exact encoder implementation. Inspect actual segmentations rather than relying on the algorithm name. The durable mental model is a ladder of reusable chunks: start with units that can spell everything, then promote frequent adjacent combinations one rung at a time. The ladder compresses surface patterns; the neural model still has to learn how those pieces behave in context.