Tokenization

Byte-Pair Encoding is a data compression algorithm adapted for NLP that iteratively merges the most frequent pair of bytes or characters in a training corpus to build a subword vocabulary. Starting with individual characters, BPE learns a set of merge rules that define the final tokenizer. For instance, if 't' and 'h' frequently co-occur, they merge into 'th', which may later merge with 'e' to form 'the'. This greedy, frequency-based approach ensures common words remain as single tokens while rare words are decomposed into smaller, known subword units.

SentencePiece treats the input text as a raw sequence of Unicode characters, eliminating the need for language-specific pre-tokenization. It implements the Unigram Language Model algorithm, which starts with a large seed vocabulary and iteratively prunes tokens that least impact the overall likelihood of the training corpus. The final model computes a probability distribution over all possible segmentations of a word, selecting the most probable one during inference. This probabilistic approach is inherently reversible and is the backbone of models like T5 and LLaMA.

A data compression algorithm adapted for NLP that iteratively merges the most frequent pairs of bytes or characters to build a subword vocabulary. BPE starts with characters and repeatedly merges the most common adjacent pairs, creating tokens for frequent words while decomposing rare words into known subword units. This effectively handles out-of-vocabulary words by representing them as sequences of subwords.

• Core algorithm behind GPT models and RoBERTa tokenizers
• Balances vocabulary size against sequence length
• Example: 'tokenization' might be split into ['token', 'ization']

A subword tokenization algorithm developed for BERT that selects subword units based on their likelihood to maximize the probability of a language model. Unlike BPE's frequency-based merging, WordPiece uses a greedy algorithm that picks the pair whose combination yields the greatest increase in training data likelihood.

• Used by BERT, DistilBERT, and Electra
• Uses '##' prefix to denote continuation tokens
• Example: 'playing' becomes ['play', '##ing']

A language-independent subword tokenizer that treats the input text as a raw stream of Unicode characters, including whitespace. SentencePiece implements both BPE and Unigram language model algorithms without requiring pre-tokenization, making it ideal for languages that do not use spaces as word delimiters.

• Used by Llama, Mistral, and T5 models
• Directly handles raw text without language-specific preprocessing
• Example: Spaces are encoded as '▁' (U+2581) metacharacter

A probabilistic subword tokenization approach that starts with a large initial vocabulary and iteratively removes tokens that least impact the overall likelihood of the training corpus. Unigram models assign a probability to each token and select the most probable tokenization for a given word using the Viterbi algorithm.

• Often paired with SentencePiece implementation
• Produces multiple possible tokenizations with associated probabilities
• Example: The word 'hello' could be tokenized as ['he', 'llo'] or ['h', 'e', 'l', 'l', 'o'] with different probabilities

Word-level tokenization splits text on whitespace and punctuation, creating a vocabulary of full words. It is simple but suffers from massive vocabulary sizes and inability to handle unseen words. Character-level tokenization splits text into individual characters, resulting in a tiny vocabulary but very long sequences that dilute semantic meaning.

• Word-level: Vocabulary can exceed millions for large corpora
• Character-level: Vocabulary is typically < 256 tokens
• Subword tokenization (BPE, WordPiece) represents the practical compromise between these extremes

Reserved tokens injected into sequences to provide structural and instructional signals to language models. Special tokens include [CLS] for classification pooling, [SEP] for sequence separation, [MASK] for masked language modeling, [PAD] for batch padding, and [UNK] for unknown tokens.

• Modern models use <|endoftext|>, <|user|>, <|assistant|> for chat formatting
• Control tokens like <|im_start|> define role boundaries in instruction-tuned models
• Proper special token handling is critical for chat template fidelity