Byte-Pair Encoding (BPE)

BPE starts with a base vocabulary of individual characters or bytes. It then scans the training corpus to find the most frequent adjacent pair of tokens and merges them into a single new token. This process repeats for a pre-defined number of merge operations.

• Initial Vocabulary: All unique characters in the corpus.
• Merge Rule: Selects the pair (A, B) that maximizes frequency.
• Termination: Stops after N merges, where N is a hyperparameter controlling the final vocabulary size.

A defining advantage of BPE is its ability to encode any unseen word by decomposing it into known subword units. A word like 'unfriendliness' can be segmented into ['un', 'friend', 'li', 'ness'] if those subwords exist in the vocabulary.

• No OOV Tokens: Eliminates the need for a dedicated unknown token for rare words.
• Morphological Awareness: Learns common prefixes, suffixes, and stems.
• Graceful Degradation: Falls back to individual characters for completely novel sequences.

The final vocabulary size is a critical hyperparameter chosen before training. It directly controls the granularity of the segmentation and the model's embedding matrix size.

• Small Vocab (e.g., 8k): Results in shorter sequences but more aggressive segmentation, often splitting words into characters.
• Large Vocab (e.g., 50k): Encodes most common words as single tokens, reducing sequence length but increasing the embedding layer's memory footprint.
• Trade-off: Balances encoding efficiency against model parameter count.

A variant of BPE that operates on a raw byte sequence (UTF-8) rather than Unicode characters. This guarantees a base vocabulary of exactly 256 tokens and completely eliminates the concept of an unknown token.

• Universal Encoding: Can tokenize any text in any language without special handling.
• Robust to Noise: Handles typos, emojis, and rare symbols gracefully by falling back to byte-level segmentation.
• GPT-2 & GPT-3: This approach was popularized by OpenAI's GPT series.

During inference, BPE tokenization is a deterministic, greedy process. The algorithm applies the learned merge rules in the exact order they were created during training.

• Reproducibility: The same input text always produces the identical token sequence.
• No Probabilistic Choice: Unlike Unigram LM, BPE does not sample from a probability distribution during standard encoding.
• Subword Regularization: A technique called BPE-Dropout can be applied during training to stochastically skip merges, improving robustness.

The resulting subword vocabulary is entirely dependent on the training corpus. A model trained on English Wikipedia will learn different merges than one trained on a multilingual code repository.

• Domain Adaptation: A BPE tokenizer trained on medical text will learn merges like '##oma' and '##itis'.
• Language Bias: A corpus with 90% English text will produce a vocabulary optimized for English morphology, potentially segmenting other languages less efficiently.
• Pre-tokenization: Often combined with a regex-based pre-tokenizer to prevent merges across word boundaries.

A critical hyperparameter defining the total number of unique tokens a model recognizes. This represents a fundamental trade-off:

• Larger vocabularies (50k-100k): shorter sequences, faster inference, but larger embedding matrices consuming more GPU memory
• Smaller vocabularies (8k-32k): more compact models, but longer token sequences requiring more compute per example
• Typical BPE vocabularies range from 30,000 to 50,000 tokens for English-dominant models