Byte Pair Encoding (BPE) is a subword tokenization algorithm that breaks text into smaller units combining characters and frequently co-occurring sequences. Originally developed for data compression, BPE has become one of the most widely adopted tokenization methods in modern natural language processing and large language models due to its ability to balance vocabulary size with compression efficiency.
BPE was initially introduced as a data compression technique by Sennrich et al. in 2016 as a method for neural machine translation systems 1). The algorithm works by iteratively replacing the most frequent pair of consecutive bytes or characters with a new, unused byte or token. Unlike character-level tokenization, which results in long sequences and increased computational costs, and whole-word tokenization, which creates extremely large vocabularies with poor generalization to out-of-vocabulary terms, BPE provides a middle ground.
The core innovation of BPE lies in its greedy merging strategy. The algorithm begins with a vocabulary of individual characters and special tokens. It then repeatedly identifies the most frequently occurring pair of adjacent tokens in the training corpus and merges them into a single new token. This process continues for a predetermined number of iterations (typically 10,000 to 50,000 merges), with each iteration adding one new token to the vocabulary.
The BPE algorithm operates through the following steps:
1. Initialization: The initial vocabulary consists of all unique characters present in the training text, plus special tokens such as end-of-word markers (represented as </w>).
2. Frequency Analysis: For each merge iteration, the algorithm counts all adjacent token pairs throughout the entire training corpus and identifies the pair with the highest frequency.
3. Merging: The most frequent pair is merged into a new token, and all occurrences of that pair in the corpus are replaced with the new merged token.
4. Iteration: Steps 2-3 repeat for a fixed number of iterations, each time adding a new token to the vocabulary.
5. Encoding: Once training completes, new text is tokenized by greedily matching the longest available multi-character sequences against the learned vocabulary.
Modern implementations differ slightly in their specifics. GPT-2 and subsequent transformer models use a variant called byte-level BPE, which operates on raw bytes rather than Unicode characters, providing better handling of multilingual and special character content 2).com/openai/gpt-2/blob/master/src/encoder.py|OpenAI GPT-2 Tokenizer Implementation]])).
BPE has become the dominant tokenization approach for large language models including GPT series, LLaMA, and Mistral architectures. The technique offers several practical advantages:
Vocabulary Efficiency: BPE maintains compact vocabularies (typically 20,000-50,000 tokens) compared to character-level approaches with only ~100 tokens or word-level approaches requiring millions of tokens. This directly reduces memory requirements and computational overhead in model layers.
Handling Out-of-Vocabulary Terms: Unlike word-piece tokenization, BPE gracefully handles rare words, proper nouns, and domain-specific terminology by decomposing them into subword units that frequently appear in training data. This enables models to process novel text without designated “unknown” tokens.
Multilingual Support: Byte-level BPE naturally accommodates multiple writing systems and languages within a single vocabulary, making it suitable for multilingual models like mBERT and XLM-RoBERTa 3).
The efficiency of BPE directly impacts token consumption metrics for commercial APIs. Since billing and context window constraints operate at the token level, BPE's compression properties affect both operational costs and the amount of text that can be processed within fixed context windows.
WordPiece tokenization, used in BERT and other models, differs from BPE by selecting merge operations based on likelihood maximization rather than raw frequency counts. This approach tends to produce slightly different vocabulary distributions 4).
SentencePiece, developed by Google, extends the concept by treating the input as a sequence of Unicode characters and learning both encoding and decoding operations without requiring explicit space markers. This provides cleaner handling of CJK languages and spaces.
The choice between these approaches involves trade-offs between vocabulary size, compression efficiency, and language coverage. BPE's simplicity and strong empirical performance have made it the preferred choice for most contemporary large language models.
Despite its widespread adoption, BPE exhibits certain limitations. The algorithm's greedy merging approach is not globally optimal—it produces locally optimal decisions that may not minimize overall sequence length for all possible texts. Additionally, the vocabulary learned during training may not generalize well to significantly different domains or languages not well-represented in the training corpus.
BPE can produce suboptimal tokenization boundaries, particularly for morphologically complex languages where meaningful word boundaries diverge from frequency-based merge patterns. This may impact model performance on linguistic reasoning tasks.
The computational cost of the BPE training process itself, while linear in the corpus size per iteration, can become substantial for very large training datasets when computing pairwise frequencies for each merge operation.