Byte-Pair Encoding (BPE)

BPE operates at the subword level, striking a balance between character-level and word-level tokenization. It represents frequent words as single tokens while decomposing rare or unseen words into smaller, known subword units.

• Open Vocabulary: Eliminates out-of-vocabulary (OOV) tokens by ensuring any text can be represented as a sequence of known subwords.
• Morphological Awareness: Automatically captures common prefixes, suffixes, and roots without explicit linguistic knowledge.
• Example: The word 'unhappiness' might be tokenized as ['un', 'happiness'] or ['un', 'happi', 'ness'], depending on the training corpus.

The BPE training process is a deterministic, greedy algorithm that builds the vocabulary from the bottom up through repeated pair frequency analysis.

• Initialization: The vocabulary starts with all unique characters present in the training corpus.
• Merge Step: The algorithm identifies the most frequently occurring adjacent pair of tokens and merges them into a single new token.
• Termination: This process repeats until a predefined vocabulary size is reached or no pair exceeds a frequency threshold.
• Result: The final vocabulary consists of individual characters plus the most common multi-character sequences learned from the data.

Unlike rule-based tokenizers, BPE's vocabulary is learned directly from the statistical properties of the training corpus, making it highly adaptive to specific domains.

• Corpus Sensitivity: A model trained on English text will learn merges like 'th' and 'ing', while one trained on code will learn merges like 'def' and 'import'.
• Language Agnosticism: BPE makes no assumptions about word boundaries or linguistic structure, allowing it to work effectively across hundreds of languages without modification.
• Frequency-Based Efficiency: The most common words and morphemes receive the shortest encodings, providing a form of implicit compression for frequent patterns.

BPE tokenization is a lossless, fully reversible process. The original input text can be perfectly reconstructed from the sequence of token IDs without any ambiguity.

• Deterministic Decoding: By simply concatenating the text of all tokens in order, the original string is recovered exactly.
• No Normalization Loss: Unlike some tokenizers that perform case-folding or unicode normalization, standard BPE preserves the original byte sequence.
• Critical for Generation: This reversibility ensures that a language model's generated token sequence can always be decoded back into valid, intended text for the end user.

A critical adaptation for multilingual models is Byte-Level BPE, which operates on raw bytes rather than Unicode characters, as popularized by GPT-2.

• Universal Coverage: By operating on bytes (0-255), the base vocabulary is fixed at 256 tokens, guaranteeing every possible digital input can be encoded.
• Avoids Unknown Characters: This completely sidesteps the problem of unseen Unicode characters, emojis, or corrupted text that would break a character-level tokenizer.
• Trade-off: Byte-level tokenization can lead to longer token sequences for non-Latin scripts, as multi-byte characters are split into their constituent bytes before merging.

BPE offers a highly favorable compute-to-performance ratio for both training and inference compared to other subword methods.

• Fast Training: The greedy merge algorithm is straightforward to implement and scales efficiently to large corpora using priority queues.
• Linear-Time Tokenization: Once the merge rules are learned, tokenizing new text is a simple linear scan applying the learned merges in order.
• Inference Speed: The resulting vocabulary size (typically 30k-100k tokens) provides a dense representation that minimizes the sequence length processed by the transformer, directly reducing the quadratic cost of self-attention.

The broader category of algorithms to which BPE belongs. Subword tokenization breaks text into units smaller than words but larger than individual characters. This balances vocabulary size against the ability to represent rare and out-of-vocabulary words.

• Morphological richness: Handles prefixes, suffixes, and compound words
• Open vocabulary: Never encounters an unknown token; any word can be reconstructed from subword pieces
• Efficiency: A vocabulary of 32k–50k subwords can represent millions of distinct words

A subword algorithm developed by Google for BERT, closely related to BPE but with a key difference in the merge criterion. Instead of merging the most frequent pair, WordPiece selects the pair that maximizes the likelihood of the training data.

• Training objective: Greedily maximizes the language model probability of the corpus
• Distinctive symbol: Uses ## prefix to mark continuation subwords (e.g., token + ##ization)
• Adoption: Used in BERT, DistilBERT, and Electra models

A probabilistic subword tokenization method used by SentencePiece and T5. Unlike BPE's bottom-up merging, Unigram starts with a large vocabulary and iteratively prunes tokens that least increase the overall likelihood of the corpus.

• Probabilistic foundation: Each token has an independent probability; the model finds the most likely segmentation
• Multiple segmentations: A single word can have several valid tokenizations with different probabilities
• Lossy pruning: Removes 10–20% of tokens per iteration based on their contribution to data likelihood

A language-independent tokenization library developed by Google that treats the input text as a raw sequence of Unicode characters, bypassing the need for language-specific pre-tokenization. It implements both BPE and Unigram algorithms.

• Whitespace as a character: Escapes spaces as a special meta-character _ (U+2581), making decoding lossless and reversible
• Language agnostic: Works identically for English, Japanese, Chinese, and code without custom rules
• Adoption: Used by Llama, Mistral, T5, and XLNet model families

The dense vector representations that each BPE token is mapped to before being processed by a transformer. After tokenization, each subword ID indexes into an embedding matrix of shape [vocab_size, d_model].

• Learned during training: Embeddings are initialized randomly and optimized via backpropagation
• Semantic clustering: Subwords with similar functions (e.g., ##ing, ##ed) develop similar vector representations
• Dimensionality: Typically 512–4096 dimensions, depending on model scale

The primary problem that BPE solves. In traditional word-level tokenization, any word not seen during training is mapped to an <UNK> token, losing all information. BPE eliminates this by decomposing unknown words into known subword units.

• Example: The rare word disestablishmentarianism becomes dis + establish + ment + arian + ism
• Code and URLs: Handles arbitrary strings like https://api.example.com/v2 without failure
• Multilingual robustness: Proper nouns and loanwords from any script are tokenizable