Byte-Pair Encoding (BPE)

BPE constructs its vocabulary from the bottom up through a deterministic, iterative process. Starting with a base vocabulary of individual characters, the algorithm scans the training corpus to find the most frequently adjacent pair of symbols. It then creates a new symbol by merging that pair and replaces all its occurrences in the corpus. This process repeats for a predefined number of merge operations, with each iteration adding one new subword unit to the vocabulary. The final vocabulary size is a hyperparameter that directly controls the granularity of tokenization.

A core strength of BPE is its ability to encode any unseen word by decomposing it into known subword units. Since the base vocabulary contains all individual characters, even a completely novel word can be represented as a sequence of characters or known subword fragments. This eliminates the need for a fallback <UNK> token that discards information. For example, a model trained on 'low' and 'lower' can tokenize the unseen word 'lowest' as ['low', 'est'] if those subword merges were learned, preserving morphological relationships.

BPE's merge priority is strictly governed by frequency counts in the training data. This statistical grounding ensures that the most common character sequences—which often correspond to morphemes, root words, and common affixes—are merged early and receive dedicated tokens. Rare or idiosyncratic spellings remain segmented into smaller pieces. This dynamic adaptation to corpus statistics makes BPE inherently language-agnostic. It requires no linguistic knowledge, morphological rules, or pre-built dictionaries, allowing it to work effectively across hundreds of languages and even code.

The BPE tokenization process is fully reversible. A tokenized sequence of subword units can be deterministically reconstructed back into the original surface text string without any loss of information. This is because the merge rules are applied as direct string concatenations, and the decoder simply joins the tokens. This lossless property is critical for generative tasks like machine translation and text summarization, where the model's subword output must be detokenized into clean, readable text for the end user.

The primary hyperparameter governing BPE is the total number of merge operations, which directly determines the final vocabulary size. A smaller number of merges results in a more granular, character-heavy segmentation, increasing sequence length but reducing vocabulary size. A larger number of merges creates a coarser vocabulary with more whole-word tokens, reducing sequence length but increasing the model's embedding matrix size. Typical vocabulary sizes range from 8k to 50k subword units, balancing the trade-off between sequence length and model parameter count.

A modern adaptation, Byte-Level BPE (BBPE), applies the merge algorithm directly to UTF-8 encoded bytes rather than Unicode characters. This forces the base vocabulary to be exactly 256 tokens, one for each possible byte value. BBPE completely eliminates the concept of an unknown character and provides a universal representation for any language, emoji, or symbol. This variant is used in models like GPT-2 and RoBERTa, enabling robust handling of noisy, multilingual, and code-mixed text without any character-level preprocessing.

The central problem that Byte-Pair Encoding solves. An OOV token is any word or character sequence encountered during inference that was not present in a model's fixed vocabulary. Without subword tokenization, OOV terms are typically mapped to a generic <UNK> token, causing complete information loss. BPE eliminates OOV issues by decomposing any unknown word into known subword units. For example, the unseen word 'hyperparameterization' can be tokenized as ['hyper', 'parameter', 'ization'] if those subwords exist in the vocabulary.

The fundamental NLP task of segmenting a continuous string of text into discrete units called tokens. Tokenization strategies exist on a spectrum:

• Word-level: Splits on whitespace and punctuation, creating large vocabularies with severe OOV problems.
• Character-level: Splits into individual characters, creating tiny vocabularies but losing semantic meaning and requiring very long sequences.
• Subword-level (BPE, WordPiece, Unigram): Strikes a balance by splitting rare words into frequent subword units while keeping common words intact.

BPE is the most widely adopted subword tokenization algorithm, used in GPT, RoBERTa, and many other models.

A subword tokenization algorithm closely related to BPE, developed by Google for the BERT model. While BPE merges the most frequent pair of tokens, WordPiece selects the pair that maximizes the likelihood of the training data when merged. This difference means WordPiece prioritizes merges that improve the language model's probability rather than raw frequency. WordPiece also uses a special ## prefix to mark subword tokens that are continuations of a word, e.g., ['playing'] becomes ['play', '##ing']. This explicit continuation marking is absent in standard BPE.

A probabilistic subword tokenization algorithm used in models like XLNet and ALBERT. Unlike BPE's bottom-up merge approach, Unigram starts with a large vocabulary and iteratively removes tokens that least impact the overall likelihood of the training corpus. For any given word, multiple tokenization candidates exist, and the algorithm selects the one with the highest probability under the unigram model. This provides a probabilistic foundation that BPE lacks, allowing for multiple valid tokenizations of the same word and better handling of ambiguous segmentations.

A language-independent tokenization library developed by Google that treats the input text as a raw sequence of Unicode characters, eliminating the need for language-specific preprocessing. SentencePiece implements both BPE and Unigram algorithms but operates directly on the character stream rather than requiring pre-tokenized words. This is critical for languages like Chinese, Japanese, and Korean that do not use whitespace to separate words. SentencePiece also normalizes text using NFKC Unicode normalization and can be configured to include a byte fallback mechanism, ensuring zero OOV tokens by falling back to raw byte representations.

The comprehensive preprocessing pipeline applied to raw text before tokenization. BPE operates on the output of canonicalization, making the quality of this step critical. A typical canonicalization pipeline includes:

• Unicode Normalization (NFKC): Converts visually identical characters to a single binary representation.
• Case Folding: Converts all text to lowercase to reduce vocabulary size.
• Whitespace Normalization: Collapses multiple spaces and strips leading/trailing whitespace.
• Punctuation Handling: Optionally separates or normalizes punctuation marks.

Inconsistent canonicalization between training and inference can cause BPE to produce entirely different token sequences for semantically identical text.