Subword Tokenization

Byte-Pair Encoding (BPE) is a data compression algorithm adapted for tokenization. It starts with a base vocabulary of individual characters and iteratively merges the most frequent adjacent pair of symbols (bytes or characters) to create new subword units.

• Process: Begins with character-level tokens, then performs merge(‘A’, ‘B’) -> ‘AB’ for the most frequent pair (A, B) in the corpus. This repeats until a target vocabulary size is reached.
• Key Use Case: Originally used in GPT-2 and many early transformer models. It effectively balances vocabulary size and sequence length.
• Example: The word "unhappiness" might be tokenized as ["un", "happ", "iness"] if "un", "happ", and "iness" are learned subwords.

WordPiece is a subword tokenization algorithm used by models like BERT. It is similar to BPE but uses a different, likelihood-based merging criterion.

• Process: Starts with a base vocabulary of characters. Instead of merging the most frequent pair, it merges the pair that maximizes the likelihood of the training data when added to the vocabulary. This is often implemented by scoring pairs with the formula: score = (freq_of_pair) / (freq_of_first * freq_of_second).
• Key Use Case: The default tokenizer for BERT and its derivatives. It often produces linguistically intuitive subwords.
• Example: The word "playing" might be split into ["play", "##ing"], where ## indicates a subword suffix.

The Unigram Language Model tokenization algorithm starts with a large seed vocabulary and iteratively prunes it down, in contrast to BPE/WordPiece's bottom-up merging.

• Process:
  1. Initialize with a large vocabulary (e.g., all words and common substrings).
  2. Train a unigram language model to estimate the probability of each subword.
  3. Iteratively remove the subwords that cause the smallest increase in the overall loss (perplexity) of the corpus.
• Key Advantage: Provides a probability score for each tokenization, allowing for multiple segmentation possibilities. This is useful for uncertainty modeling.
• Key Use Case: Used in SentencePiece (with the --model_type=unigram flag) and models like ALBERT.

Byte-level BPE is a variant used by OpenAI's GPT models (from GPT-2 onward). It applies BPE not on Unicode characters but on bytes, creating a truly universal base vocabulary.

• Process: The input text is first encoded into UTF-8 bytes. The BPE merging algorithm is then run on this sequence of 256 possible byte values.
• Key Advantage: The vocabulary is small (256 base bytes + merges), guaranteeing that any string can be tokenized without an <UNK> token. It elegantly handles any language, emoji, or special formatting.
• Consideration: Sequences become longer (as many bytes per character), but this is offset by the transformer's ability to handle long contexts. It is the foundation of tokenizers like OpenAI's tiktoken and Hugging Face's GPT2Tokenizer.

Choosing an algorithm involves key engineering trade-offs between vocabulary coverage, sequence length, and linguistic intuition.

• Vocabulary Size vs. Sequence Length: A larger subword vocabulary leads to shorter, more efficient sequences but risks overfitting. A smaller vocabulary (e.g., byte-level) leads to longer sequences but perfect coverage.
• Merging Strategy: BPE (frequency-based) is simple and fast. WordPiece (likelihood-based) can yield more meaningful merges. Unigram (pruning-based) is more computationally intensive but provides probabilistic segmentations.
• Pre-tokenization: Most algorithms (BPE, WordPiece) require a pre-tokenization step (splitting on whitespace/punctuation). SentencePiece and Byte-level BPE avoid this, offering greater flexibility for multilingual and noisy text.
• Implementation: For production, robust libraries like Hugging Face Tokenizers (which supports all major algorithms) or SentencePiece are essential.

Advanced implementations go beyond deterministic tokenization. Subword Regularization (e.g., as implemented in SentencePiece's Unigram mode) introduces noise during training to improve model robustness.

• Method: Instead of always using the single best segmentation, the model randomly samples from possible subword segmentations based on their probability.
• Benefit: This acts as a powerful data augmentation technique, exposing the model to multiple segmentations of the same word and improving generalization, especially for morphologically rich languages or noisy text.
• Use Case: Prominently used in training models like T5 and multilingual BERT variants.

Byte-Pair Encoding (BPE) is the foundational, data-driven algorithm behind most modern subword tokenizers. It starts with a base vocabulary of individual characters and iteratively merges the most frequently occurring pair of symbols in the training corpus to create new subword units.

• Key Mechanism: The algorithm runs for a pre-defined number of merge operations, building a vocabulary that balances character-level flexibility with word-level efficiency.
• Real-World Use: BPE is the core of tokenizers for models like GPT (OpenAI) and RoBERTa (Meta), enabling them to handle complex morphology and out-of-vocabulary words effectively.

WordPiece is a subword tokenization algorithm similar to BPE but with a different merging criterion. Instead of merging the most frequent pair, it merges the pair that maximizes the likelihood of the training data when added to the vocabulary.

• Key Difference: This likelihood-based approach can lead to a vocabulary that is more optimized for the language model's training objective.
• Primary Application: WordPiece is famously used in BERT and its derivatives. Tokens often start with ## to indicate they are a subword continuation (e.g., ##ing).

SentencePiece is a language-agnostic tokenization toolkit that implements subword units (using BPE or unigram language models) directly on raw text, treating whitespace as just another character.

• Key Advantage: It does not require pre-tokenization (splitting by whitespace/punctuation), making it highly effective for languages without clear word boundaries (e.g., Japanese, Chinese) or for processing code and noisy text.
• Widespread Use: It is the tokenizer of choice for models like T5 (Google) and LLaMA (Meta), providing robust performance across many languages.

The Unigram Language Model approach is a probabilistic method for subword tokenization. It starts with a large seed vocabulary (e.g., all words plus subwords) and iteratively prunes it down by removing the units that least affect the overall likelihood of the corpus.

• Key Mechanism: It evaluates the contribution of each subword unit, allowing for the creation of a vocabulary of a precise target size.
• Use Case: This method is particularly useful when a specific vocabulary size is a hard constraint. It's an option within the SentencePiece toolkit and is used in models like ALBERT.

Data Tokenization is the overarching process of breaking down any raw data stream into discrete, processable units (tokens). While subword tokenization is specific to text, the concept generalizes across modalities.

• Cross-Modal Examples:
  • Audio: Converting a waveform into frames or mel-spectrogram patches.
  • Video: Dividing a video into frames or spatiotemporal patches.
  • Code: Splitting source code into lexical tokens (keywords, operators, identifiers).
• Unified Principle: All tokenization aims to create a finite vocabulary of atomic units from which a model can learn patterns and generate coherent outputs.

A Chunking Strategy is a systematic method for segmenting long, continuous data into coherent blocks that fit within a model's finite context window. It works in concert with tokenization.

• Relationship to Tokenization: First, text is tokenized into subwords. Then, a chunking strategy (e.g., sliding window, semantic boundary detection) groups these tokens into sequences of appropriate length.
• Critical for Long Context: Effective chunking is essential for processing long documents, audio recordings, or video with models like transformers, ensuring that related information stays together within a single processing window.