Byte-Pair Encoding (BPE)

BPE starts with a base vocabulary of individual characters or bytes and iteratively merges the most frequently co-occurring adjacent pair into a new token. This process repeats for a pre-defined number of merge operations, building a vocabulary of increasingly longer subword units. The final vocabulary size is a hyperparameter that directly controls the granularity of tokenization.

• Start: Character-level vocabulary (e.g., 'l', 'o', 'w')
• Step 1: Merge most frequent pair (e.g., 'l' + 'o' → 'lo')
• Step N: Continue until target vocabulary size is reached
• Result: A mix of characters, subwords, and whole words

BPE eliminates the unknown token problem by design. Since the vocabulary is built from characters upward, any word can be represented as a sequence of known subword units. Rare or unseen words are decomposed into smaller, known pieces rather than being replaced with a generic <UNK> token.

• Example: 'unhappiness' → 'un' + 'happiness' or 'un' + 'hap' + 'pi' + 'ness'
• Morphological transparency: Prefixes and suffixes emerge naturally
• No vocabulary ceiling: Any Unicode sequence can be encoded

The merge priority is determined by corpus frequency, ensuring that common morphemes and word pieces receive dedicated tokens while rare character sequences remain decomposed. This data-driven approach automatically discovers linguistically meaningful units without requiring pre-segmented training data or language-specific rules.

• Common words like 'the' or 'and' become single tokens
• Frequent morphemes like '-ing' or '-tion' emerge as subword units
• Rare names and technical terms remain split into smaller pieces
• Language agnostic: Works identically across all languages

BPE tokenization is fully reversible with no information loss. The original text can be reconstructed exactly by concatenating the tokens and removing the special whitespace markers (often represented as 'Ġ' or '▁') that indicate word boundaries. This deterministic encoding-decoding cycle is critical for text generation tasks.

• Encoding: 'low lower' → ['low', 'Ġlow', 'er']
• Decoding: Concatenate and strip boundary markers → 'low lower'
• Lossless: No characters are dropped or normalized away
• Deterministic: Same input always produces same token sequence

The target vocabulary size is a critical hyperparameter that balances sequence length against embedding matrix size. A smaller vocabulary produces longer token sequences but a more compact model, while a larger vocabulary shortens sequences at the cost of increased memory for the embedding layer.

• Small vocab (8k-16k): Longer sequences, smaller embedding matrix, better for multilingual models
• Medium vocab (30k-50k): Common in GPT-2 and many production models
• Large vocab (100k+): Shorter sequences, larger memory footprint, better for domain-specific corpora
• Trade-off: Sequence length × vocabulary size ≈ constant computational budget

Byte-level BPE operates on raw bytes (0-255) rather than Unicode characters, enabling a base vocabulary of exactly 256 tokens. This variant, used in GPT-2 and subsequent models, can encode any text regardless of pre-processing or character set, including emoji, code, and malformed input.

• Base vocabulary: 256 byte values
• Universal encoding: Handles any input without Unicode normalization
• No pre-tokenization required: Operates directly on UTF-8 bytes
• Example: 'é' is encoded as two bytes (0xC3, 0xA9) which may be merged into a single token if frequent

The broader category of algorithms that Byte-Pair Encoding belongs to. Subword tokenization splits text into units smaller than words but larger than individual characters, enabling models to handle out-of-vocabulary (OOV) words by composing them from known fragments. This approach balances vocabulary size against representational power.

• Morphological awareness: 'unhappiness' becomes 'un', 'happi', 'ness'
• Open-vocabulary: Any word can be represented, even if never seen during training
• Rare word handling: Proper nouns and technical terms decompose into familiar subword units

A subword algorithm developed by Google for BERT and subsequent transformer models. Unlike BPE's frequency-based merging, WordPiece uses a likelihood maximization criterion, selecting merges that most increase the probability of the training corpus under a unigram language model.

• Uses ## prefix to mark continuation tokens (e.g., 'token', '##ization')
• Greedy longest-match-first segmentation at inference time
• Produces slightly different vocabularies than BPE for the same corpus size

A probabilistic subword segmentation method used in SentencePiece and models like XLNet. Instead of building a vocabulary bottom-up through merges, Unigram LM starts with a large seed vocabulary and prunes it by removing tokens whose removal least impacts the corpus likelihood.

• Trains a unigram language model over subword units
• At inference, produces multiple segmentation candidates with probabilities
• Selects the Viterbi path—the most probable tokenization
• Inherently handles ambiguity better than deterministic BPE

A language-independent tokenization library developed by Google that treats the input text as a raw byte stream, eliminating the need for language-specific pre-tokenization. SentencePiece implements both BPE and Unigram LM algorithms and is the tokenizer behind models like LLaMA, T5, and ALBERT.

• Whitespace is treated as a regular symbol (escaped as '▁')
• Directly handles any language without pre-segmentation rules
• Lossless and reversible: detokenization perfectly reconstructs the original text
• Supports BPE and Unigram modes with a unified API

The fundamental engineering decision in subword tokenization. A larger vocabulary captures more common words and morphemes as single tokens, reducing sequence length and improving inference speed. A smaller vocabulary forces more fragmentation but improves generalization to rare and unseen words.

• Typical sizes: 32K (SentencePiece default), 50K (GPT-2), 100K (multilingual models)
• Larger vocabularies increase embedding matrix memory footprint
• Multilingual models require larger vocabularies to cover multiple scripts
• The compression ratio (tokens per word) directly impacts compute cost

A variant introduced by GPT-2 that applies BPE directly to UTF-8 encoded bytes rather than Unicode characters. This completely eliminates the unknown token problem, as every possible input is representable as a sequence of 256 base byte tokens.

• Base vocabulary of exactly 256 byte tokens
• Handles any Unicode character, emoji, or garbled text without <unk> tokens
• Can produce longer token sequences for non-Latin scripts
• Used by GPT-2, GPT-3, RoBERTa, and most modern large language models