Demystifying Byte Pair Encoding (BPE)

1. Introduction

In modern Natural Language Processing (NLP), one of the earliest hurdles is how to represent text as input to machine learning models. Traditional methods, like splitting text on spaces, often lead to the dreaded <unk> token for any unseen words. On the other hand, a purely character-level approach yields extremely long input sequences, slowing down training and possibly hurting performance if the model can’t effectively learn higher-level patterns.

Enter Byte Pair Encoding (BPE): a subword tokenization strategy that strikes a balance between word-level and character-level tokenization. BPE was originally introduced as a data compression technique, but it was later adapted for NLP by Sennrich, Haddow, and Birch (2016). The method incrementally merges common character sequences (bigrams) into subword tokens, which can dramatically reduce sequence lengths while still avoiding out-of-vocabulary issues.

In this article, we’ll:

1. Explain the theory and premise of BPE, including why it was groundbreaking.
    
2. Show hands-on code that trains a BPE tokenizer from scratch on WikiText-2.
    
3. Demonstrate how BPE fares on out-of-distribution data (e.g., different languages).
    
4. Discuss pitfalls, alternatives, and best practices for subword tokenization.
    

By the end, you’ll see that training and applying a BPE tokenizer isn’t just about compressing text—it’s also about making strategic trade-offs in vocabulary selection, domain adaptation, and language coverage.

2. Core Concepts of Byte Pair Encoding

2.1 The Premise of BPE

BPE originated as a data compression algorithm. The idea is simple:

1. Start with all text encoded at the byte level (each character is a separate token).
    
2. Iteratively merge the most frequent pair of tokens (bigrams) into a single token, effectively building a subword.
    
3. Repeat until you’ve added as many new tokens as your vocabulary budget allows.

In NLP, BPE ensures that frequently occurring word fragments (e.g., “tion”, “ing”, “pre-”) become stable subwords in the vocabulary, while rare words are decomposed into smaller chunks rather than being replaced by an <unk> token.

2.2 Why BPE Was Game-Changing

• Fewer Unseen Tokens: Because every byte sequence is represented in the vocabulary, BPE drastically reduces or eliminates the usage of <unk> tokens.
   
• Efficient Representation: Subwords allow models to process shorter sequences than character-level approaches while retaining flexibility for out-of-vocabulary (OOV) words.
   
• Adaptable to Domains: If you train BPE on medical text, it will learn to treat “neuro” or “cardio” as high-frequency subwords, capturing domain-specific language more effectively than a naive tokenizer would.

BPE’s popularity soared with the advent of deep learning architectures like RNN-based and Transformer-based models, making it a standard choice in frameworks such as SentencePiece and in major NLP toolkits.

3. A Simple Example

Let’s illustrate BPE with a toy sentence: “We named our son nwonkun.”

• Word-level tokenization might handle this well, except for “nwonkun,” which might become <unk>.
   
• Character-level tokenization yields many tokens (including spaces, punctuation, etc.).

BPE starts by treating each character as a token:

[W, e,  , n, a, m, e, d,  , o, u, r,  , s, o, n,  , n, w, o, n, k, u, n, .]

• Then it merges the most common bigrams—like n (space + n) or on—into single tokens. After several merges, the sequence length shrinks without losing the ability to represent “nwonkun.”

In practice, BPE merges are learned from a larger corpus. That’s where training a BPE tokenizer comes into play.

For this example, here are the results after 1, 2, 5 merges. Do you get the same results? If not, you might still be right!

• After 1 merge:
  [W, e, _n, a, m, e, d, _, o, u, r, _, s, o, n, _n, w, o, n, k, u, n, .]
   
• After 2 merges:
  [W, e, _n, a, m, e, d, _, o, u, r, _, s, on, _n, w, on, k, u, n, .]
   
• After 5 merges:
  [W, e, _n, a, m, e, d, _o, u, r, _s, on, _n, _nw, on, k, u, n, .]

4. Notebook Walk-Through: Training and Using a BPE Tokenizer

Below, we explore an interactive Jupyter notebook approach. You’ll see how to:

1. Initialize a BPE tokenizer.
    
2. Train it on WikiText-2.
    
3. Compare compression rates on training vs. test data.
    
4. Test on out-of-distribution languages.

4.1 Data Setup

We use the WikiText dataset from Hugging Face:

from datasets import load_dataset
dataset = load_dataset(“wikitext”, “wikitext-2-raw-v1”)
train_text = ” “.join(dataset[“train”][“text”])[:10**6]
test_text = ” “.join(dataset[“test”][“text”])[:10**6]

• We limit each to 1 million characters for demonstration.
   
• train_text and test_text are just large strings.

4.2 Defining the Tokenizer Class

The core logic:

from itertools import chain, pairwise
from collections import Counter
from tqdm import tqdm

class Tokenizer:
    …

1. Initial Vocab: 256 single-byte tokens.
    
2. Training: We find the most frequent pair of tokens in the training text, merge them, append the merged token to self.vocab, then replace every occurrence in the byte sequence.
    
3. Tokenizing: A greedy approach ensures we always match the longest token in the vocab for each substring.
    
4. Detokenizing: We reverse the process by expanding token IDs into their byte tuples and decoding.

(See the full code snippet in the notebook for details.)

4.3 Training with a Small Subset

train_data = train_text[:10000]
tokenizer = Tokenizer(train_data, vocab_size=500)

• We use 10,000 characters and a vocab_size of 500. In real scenarios, you might use far more merges.

After training, we can inspect the new subword tokens:

for token in tokenizer.vocab[-10:]:
    print(repr(bytes(token).decode(“utf-8”)))

You might see merges like ” on”, “ing”, ” th”, reflecting frequent bigrams in the training text.

4.4 Measuring Compression

train_bytes_len = len(bytes(train_data, “utf-8”))
train_token_len = len(tokenizer.tokenize(train_data))
train_ratio = (train_token_len / train_bytes_len) * 100

test_data = test_text[:10000]
test_bytes_len = len(bytes(test_data, “utf-8”))
test_token_len = len(tokenizer.tokenize(test_data))
test_ratio = (test_token_len / test_bytes_len) * 100

print(f”Train compression: {train_ratio:.2f}%”)
print(f”Test compression: {test_ratio:.2f}%”)

• Train data often shows better compression because it matches the BPE merges learned.
• Test data may have different phrasing or style, resulting in slightly worse compression.

4.5 Out-of-Distribution Languages

We also compare how this English-trained tokenizer fares on other languages:

languages = [“en”, “fr”, “es”, “de”, “zh”, “ar”]
# Code snippet to fetch samples from OSCAR dataset
# then tokenize with ‘tokenizer’
# compute ratio of tokens to bytes
# Plot bar chart of compression ratio for each language

As expected, English and languages with Latin scripts might compress better than, say, Chinese (zh) or Arabic (ar). This underscores that a monolingual BPE tokenizer is not universal—if your corpus or user base is multilingual, you need a joint or multilingual strategy to avoid inefficiencies and biases.

Observations and Limitations

1. BPE Reduces <unk> Tokens
   • Thanks to the byte-level fallback, BPE can handle rare words by breaking them into smaller subwords instead of a single unknown token.
      
2. Domain & Distribution
   • If your text is from a drastically different domain (e.g., legal documents vs. Wikipedia articles), BPE merges learned from Wikipedia might not capture your domain’s subwords well, resulting in longer token sequences.
      
3. Retokenization Paradox
   • A known pitfall: Detokenizing and then re-tokenizing might produce a different set of token IDs. This happens because merges can overlap or apply in different orders.
      
4. Multilingual Challenges
   • As shown by our OSCAR dataset test, an English-focused BPE doesn’t do well on scripts like Chinese. Large multilingual models (e.g., mBERT, XLM-R) typically train on data that covers multiple writing systems to mitigate this gap.
      
5. Subword Tokenization & Fluent Generation
   • You might wonder: Does splitting words into subwords harm the fluency of generated text? In practice, no. Language models (like GPT-2, GPT-3) learn how these smaller pieces recombine into coherent words and sentences. They do this via:
     • Contextual Embeddings: Even if “con” and “vers” are separate tokens, the model’s training on massive text corpora teaches it which subword sequences form valid words.
     • Auto-Regressive Predictions: Predicting each subword token in sequence, the model sees a wide range of language patterns, ensuring final output is linguistically coherent.
     • Large-Scale Data: Extensive training examples let it pick up common subword combinations (like “con” + “vers” + “ation”).
        
   • A great resource for understanding this is Radford et al. (2019), “Language Models are Unsupervised Multitask Learners,” which explains how subword-based models can still generate highly fluent and contextually appropriate text.

6. Pitfalls and Alternatives to BPE

6.1 Pitfalls

• Greedy Merging: BPE merges can be suboptimal if the corpus is small or domain-specific merges overshadow more general merges you might want.
• Missing Tokens During LM Training: Some merges might never appear in your language model training, causing potential mismatch between the tokenizer and the LM.
• Retokenization Inconsistency: As mentioned, merging can create tokens that are not guaranteed to reconstruct identically across multiple tokenization rounds.
   

6.2 Alternatives

1. Unigram Language Model
   • Proposed by Kudo (2018). Instead of iteratively adding merges, it starts with a big vocabulary and discards subwords that don’t fit well.
2. SentencePiece
   • A popular toolkit that supports BPE and Unigram. It can handle raw text without requiring explicit preprocessing and handles multi-lingual scenarios more gracefully.
3. Character-Based
   • Some researchers advocate going back to a character or byte approach, especially for languages with complex morphology. While this can solve OOV issues definitively, it may bloat sequence lengths.
4. Continuous Representations
   • A new frontier in NLP suggests eschewing discrete tokenization altogether, but these methods are still experimental.
      

7. Conclusion and Best Practices

Byte Pair Encoding remains one of the most influential subword tokenization techniques in NLP, balancing vocabulary size with flexibility. Here’s what you should keep in mind:

1. Data Matters: BPE “learns” merges from the training distribution. If you drastically switch domains, consider retraining or fine-tuning your tokenizer.
    
2. Beware of Bias: An English-trained BPE might struggle with non-Latin scripts, as shown by higher token counts for Chinese, Arabic, and other languages.
    
3. Watch for Pitfalls: The retokenize(detokenize(x)) ≠ x phenomenon can be surprising, so always test your pipeline carefully.
    
4. Stay Updated: Alternatives like Unigram LM, or even brand-new methods, may outperform classic BPE in certain multilingual or domain-specific contexts.
    

Next Steps for You

• Try adjusting the vocab_size in our notebook to see how it affects compression.
   
• Conduct your own domain adaptation experiment (e.g., training on legal text).
   
• Experiment with SentencePiece or Unigram to see if it better fits your data or language variety.
   

Video Explanation

• The video from Hugging Face walks through Byte Pair Encoding, explaining its subword tokenization algorithm, how to train it, and how tokenization of the text is done with the algorithm. (Runtime: 6 mins)

• The following video by DataMListic on Youtube compares three tokenizers, one of which is Byte Pair Encoding (Runtime 0:00 – 2:15). It proivides a clear explanation with visuals and examples. (Runtime: ~2 mins for Byte Pair Encoding)

References and Further Reading

1. Sennrich, R., Haddow, B., & Birch, A. (2016). “Neural Machine Translation of Rare Words with Subword Units.” ACL.
2. Kudo, T. (2018). “Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates.” ACL.
3. Petrov, P. et al. (2023). “Tokenization and Fairness Across Languages.” arXiv preprint arXiv:2305.15425.
4. Byte-Pair Encoding (Wikipedia)
5. He, Junxian, et al. (2020). “A unified view of parameterization in NLP.” NAACL.
6. Radford, A. et al. (2019). “Language Models are Unsupervised Multitask Learners.

Link to the Notebook

Related Articles

1. What is Natural Language Processing (NLP)? List the different types of NLP tasks
2. What are some of the most common practical, real world applications of NLP?
3. What is tokenization?