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 symbol pairs into new subword units.

• Process: Begins with characters, counts symbol pair frequencies, and merges the most common pair. Repeats for a set number of merges.
• Key Feature: Creates a vocabulary of variable-length subwords. Common words become single tokens (e.g., "the"), while rare words are split (e.g., "tokenization" → "token", "ization").
• Use Case: The original algorithm behind OpenAI's GPT models and many other early large language models.

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.
• Key Feature: Tends to produce a more linguistically plausible segmentation than pure frequency-based BPE. It uses a ## prefix to denote subwords that are not at the beginning of a word.
• Use Case: The standard tokenizer for the BERT family of models and their derivatives.

The Unigram Language Model tokenization algorithm starts with a large seed vocabulary and iteratively prunes it down, optimizing for overall corpus likelihood.

• Process: Assumes each word's tokenization is independent (a unigram assumption). Begins with a large overcomplete vocabulary (e.g., all frequent substrings) and uses the Expectation-Maximization algorithm to estimate subword probabilities. The vocabulary is shrunk by removing the least impactful subwords.
• Key Feature: Can output multiple possible segmentations with probabilities for a single word, allowing for sampling-based segmentation. It is inherently probabilistic.
• Use Case: Used by the SentencePiece tool and models like ALBERT and T5.

Byte-Level BPE (BBPE) is a variant of BPE that operates directly on UTF-8 encoded bytes, rather than Unicode characters. This creates a truly universal, small vocabulary.

• Process: Text is encoded into a sequence of bytes (256 possible values). The standard BPE merging process is applied to these byte sequences.
• Key Feature: The vocabulary size is capped at 256 + merges, guaranteeing a small, fixed base. It can represent any text without an <UNK> token, as out-of-vocabulary words are simply decomposed into many byte tokens.
• Trade-off: Extremely small vocabulary is efficient, but longer sequences for complex characters or rare words can increase context window usage.
• Use Case: Used by OpenAI's GPT-2 and RoBERTa to handle diverse text and emojis robustly.

Choosing a subword algorithm involves balancing vocabulary size, token sequence length, and linguistic coherence.

• Vocabulary Size vs. Sequence Length: A larger vocabulary leads to shorter, more efficient token sequences but risks overfitting to the training corpus. A tiny vocabulary (like BBPE) guarantees coverage but produces long sequences.
• Linguistic Coherence: BPE/WordPiece merges are greedy and can produce non-intuitive splits. The Unigram model's probabilistic approach can be more flexible.
• TinyML Consideration: For microcontroller deployment, a small, fixed vocabulary is critical. Techniques like vocabulary pruning (removing rare tokens) or using BBPE are essential to shrink the embedding matrix, which is often a model's largest layer.

Byte-Pair Encoding (BPE) is a data compression algorithm adapted for subword tokenization. It starts with a base vocabulary of individual characters and iteratively merges the most frequent adjacent symbol pairs into new subword units.

• Process: Begins with character-level tokens, then performs merge operations based on frequency in the training corpus.
• Key Feature: Creates a vocabulary of variable-length subwords, balancing character-level flexibility with word-level efficiency.
• Usage: The original algorithm behind OpenAI's GPT model tokenizers and a core option in the SentencePiece library.

WordPiece is a subword tokenization algorithm similar to BPE, used prominently in Google's BERT family of models. Instead of merging the most frequent pairs, it merges pairs that maximize the likelihood of the training data when added to the vocabulary.

• Process: Employs a greedy likelihood maximization strategy for merges.
• Distinction: Often produces subwords that are more linguistically plausible prefixes, stems, and suffixes compared to pure frequency-based BPE.
• Handling Unknowns: Uses a [UNK] token for out-of-vocabulary sequences that cannot be broken down.

Unigram Language Model Tokenization is a probabilistic subword method that starts with a large vocabulary and iteratively removes the least valuable subwords to shrink to a target size.

• Process: Begins with all possible substrings (or a large seed vocabulary) and uses a unigram language model to score the likelihood of the corpus under different vocabularies.
• Key Feature: Provides a probability for each subword, allowing for multiple possible tokenizations of a single word, from which the most probable can be selected.
• Advantage: Offers a principled probabilistic framework for vocabulary optimization, as implemented in SentencePiece.

Vocabulary Pruning is a model compression technique that reduces the size of a language model's embedding layer by removing rarely used tokens from its vocabulary.

• Mechanism: Tokens with the lowest frequency in a target domain or task dataset are identified and eliminated.
• Impact: Directly shrinks the model's parameter count (the embedding matrix is often one of the largest components) and memory footprint.
• TinyML Synergy: Often applied after subword tokenization to create an ultra-compact, domain-specific vocabulary for microcontroller deployment, trading broad linguistic coverage for extreme efficiency.

Token Embeddings are dense, continuous vector representations of tokens (words or subwords) learned by a language model. They map discrete token IDs from the vocabulary into a high-dimensional semantic space.

• Function: Form the first layer of a transformer model, converting tokenized input into a numerical format the network can process.
• Subword Connection: Subword tokenization creates a manageable set of tokens, each with its own learned embedding. This allows the model to construct representations for unseen words by combining the embeddings of their constituent subwords.
• Compression Target: The embedding lookup table is a primary target for quantization and pruning in TinyML to reduce its memory and computational cost.