Subword Tokenization

The core learning algorithm is driven by corpus statistics. The tokenizer iteratively scans the training data to find the most frequent adjacent pair of tokens (or characters) and merges them into a single new token. This process repeats until a target vocabulary size is reached. In Byte-Pair Encoding (BPE), this is purely frequency-driven, while WordPiece uses a likelihood maximization objective to select merges that most improve the language model's probability.

The defining advantage is the elimination of out-of-vocabulary (OOV) tokens. Any unseen word, misspelling, or novel compound is recursively segmented into known subword units present in the vocabulary. For example, the unknown word 'hyperparameterization' might be tokenized as ['hyper', 'parameter', 'ization']. This guarantees the model always receives a valid sequence of token IDs, preventing information loss at the input layer.

Subword tokenization implicitly performs a form of morphological analysis without explicit linguistic rules. The merge algorithm naturally captures common prefixes, suffixes, and stems. For instance, the tokens 'un', 'believ', and 'able' can be combined to represent 'unbelievable'. This shared representation allows the model to transfer semantic knowledge across related words, understanding that 'readable' and 'doable' share a functional suffix.

The vocabulary size is a critical hyperparameter that directly controls the granularity of the tokenization. A smaller vocabulary (e.g., 8k tokens) results in more aggressive segmentation into shorter, more frequent subwords, increasing sequence length. A larger vocabulary (e.g., 50k tokens) preserves more whole words, reducing sequence length but increasing the model's embedding matrix size. The optimal size balances encoding efficiency against computational cost.

Once trained, the merge rules are applied in a strictly greedy and deterministic order. For a given input text, the tokenizer will always produce the exact same sequence of token IDs. This is achieved by applying the learned merges in the order they were created during training. This determinism is crucial for reproducibility in model inference and ensures that the same prompt always maps to the same numerical input.

Tokenizers like SentencePiece guarantee lossless tokenization by treating the input as a raw Unicode sequence and managing whitespace as a special meta-symbol (often '▁'). This means the original input text can be perfectly reconstructed from the token sequence without any ambiguity. This property is essential for tasks like text generation and translation, where the exact original formatting must be recoverable after decoding.

The foundational data compression algorithm repurposed for tokenization. BPE starts with a base vocabulary of characters and iteratively merges the most frequent adjacent pair of tokens until a target vocabulary size is reached.

• Mechanism: Frequency-based bottom-up merging.
• Origin: Adapted from a 1994 compression algorithm by Philip Gage.
• Key Benefit: Automatically discovers common subwords like 'ing' or 'tion' without linguistic knowledge.
• Example: Low-frequency 'low' + 'er' merge to 'lower', preventing an OOV crisis.

A subword segmentation algorithm developed for BERT that selects merge rules based on maximizing the likelihood of the training data rather than raw frequency.

• Mechanism: Greedy likelihood maximization.
• Difference from BPE: Evaluates the mutual information between subwords; it asks 'which merge makes the corpus most probable?' rather than 'which pair is most common?'.
• Identifier: Uses ## prefix to denote continuation tokens (e.g., 'token' and '##ization').

A probabilistic tokenization method that works in reverse. It starts with a large seed vocabulary and iteratively removes tokens that least increase the overall likelihood of the corpus.

• Mechanism: Top-down pruning based on a unigram language model loss.
• Key Advantage: Provides a probability distribution over multiple possible segmentations, enabling subword regularization.
• Implementation: Often used within the SentencePiece framework for models like T5 and Llama.

A language-independent tokenization framework that treats the input text as a raw Unicode sequence, eliminating the need for language-specific pre-tokenization.

• Core Innovation: Lossless and reversible tokenization; the original text can be perfectly reconstructed from the tokens.
• Whitespace Handling: Escapes whitespace as a meta-symbol '▁' (U+2581), allowing the model to process languages without explicit word boundaries.
• Algorithms: Implements both BPE and Unigram models.

A variant of BPE that operates on a raw byte sequence rather than Unicode characters. The base vocabulary is strictly 256 tokens (one per byte).

• Guarantee: Completely eliminates the concept of an unknown token; any Unicode sequence can be represented.
• Trade-off: May require more tokens to encode a single character, but provides universal coverage.
• Usage: Employed by GPT-2 and later models to handle diverse, noisy internet text.

A training technique that stochastically samples different segmentations for the same word, improving model robustness to tokenization variance.

• Implementation: Often achieved via BPE-Dropout, which randomly skips certain merge rules during training.
• Benefit: Exposes the model to multiple valid tokenizations (e.g., 'unbelievable' vs 'un-believable'), acting as data augmentation.
• Result: Better handling of misspellings and rare morphological variants at inference time.