BPE (Byte Pair Encoding)

Byte pair encoding, or BPE, builds a vocabulary by repeatedly merging frequent adjacent pieces. Training the tokenizer learns the merges. Encoding a new prompt applies the learned rules without retraining them.

A small example you can count

Suppose our entire training set contains low five times and lower twice. Start with characters and keep words separate. For simplicity, this example omits boundary markers.

• The pair l o appears seven times. So does o w.
• Break the tie by choosing l o. Our words become lo w and lo w e r.
• Now lo w appears seven times. Merge it to produce low.
• e r appears twice. A later merge can produce er, leaving low er for the longer word.

Ties can lead to different merge sequences. The point is to count pairs in the current representation, apply one merge, then count again. BPE is learning frequently useful pieces, not looking up grammatical word roots.

What happens to a new word?

At inference time, the tokenizer uses its saved vocabulary and merge priorities. It does not recalculate frequencies from your prompt. If lowest was absent from training, it might still use the learned low piece followed by smaller pieces for the rest. The exact output depends on the remaining vocabulary and rules.

Vocabulary size is one choice, but normalization, word boundaries, special tokens, and the initial alphabet matter too. Character-based BPE and byte-level BPE do not start from the same units. Byte-level approaches can represent text through its bytes, including characters that were not common in the training set.

Why engineers care

Tokenization affects sequence length, which affects context usage and computation. It also explains why small edits to text sometimes change the token count unexpectedly. A merge rule can combine one spelling efficiently while leaving a slightly different spelling in several pieces.

Source: Sennrich, Haddow and Birch on subword units for rare words. For the practical comparison, read token vs word vs character.