Byte-Pair Encoding (BPE)

BPE starts with a base vocabulary of individual characters and iteratively merges the most frequent adjacent pair of symbols. This process builds a vocabulary of subword units, where common words remain intact and rare words are decomposed into meaningful fragments.

• Initialization: Vocabulary contains every unique character in the corpus.
• Merge Step: The pair (A, B) with the highest co-occurrence count is merged into a new token AB.
• Termination: The process stops after a predefined number of merges or when a target vocabulary size is reached.

A core strength of BPE is its ability to encode any unseen word by decomposing it into known subword units. This eliminates the problem of out-of-vocabulary (OOV) tokens that plague word-level models.

• A novel word like 'unfriendliness' can be segmented into ['un', 'friend', 'li', 'ness'] if those subwords exist in the vocabulary.
• This is critical for handling morphologically rich languages, technical jargon, and user-generated content with typos.

BPE naturally learns a vocabulary that reflects the statistical structure of the training corpus. High-frequency words and morphemes are preserved as single tokens, while rare sequences are broken down.

• Efficiency: Common words like 'the' or 'ing' become single tokens, maximizing the information per token.
• Granularity: Rare or complex words are split into smaller, reusable parts, preventing vocabulary explosion.
• This balances the context window length with the need for granular semantic representation.

The BPE tokenization process is fully deterministic and reversible. Given the merge rules learned during training, a tokenized sequence can be perfectly reconstructed back into the original text.

• Encoding: Apply the learned merge operations greedily to split a word into subword tokens.
• Decoding: Simply concatenate all tokens and replace the special whitespace character to recover the original string.
• This lossless property ensures no information is discarded during the preprocessing step.

BPE is one of several subword tokenization algorithms, each with distinct optimization criteria.

• BPE: Merges the most frequent pair. A deterministic, bottom-up approach.
• WordPiece: Merges the pair that maximizes the likelihood of the training data. Used by BERT.
• Unigram LM: Starts with a large vocabulary and iteratively prunes tokens that least impact the overall likelihood. A probabilistic, top-down approach used by T5 and Llama.
• All three achieve open-vocabulary encoding but differ in their training objectives and resulting vocabulary composition.