🔤 Byte Pair Encoding (BPE) - Deep Dive

Used by: GPT-2, GPT-3, GPT-4, RoBERTa, BART, and most modern LLMs

🎯 Why BPE?

The Problem BPE Solves

Word-level: "unhappiness" → ["unhappiness"] ❌ (unknown word)
Character-level: "unhappiness" → ["u","n","h","a","p","p","i","n","e","s","s"] ❌ (too long)
BPE: "unhappiness" → ["un","happiness"] ✅ (perfect balance)

BPE Advantages

1. No Unknown Tokens - Can represent any text
2. Efficient - Balances vocabulary size and sequence length
3. Language Agnostic - Works for any language
4. Learns from Data - Adapts to your corpus

Infographic takeaway: BPE is really a vocabulary-building process

The BPE infographics make one idea very clear:

• BPE does not start with a smart understanding of words
• BPE starts with tiny units, usually characters or bytes
• then it keeps merging the most frequent neighboring pieces
• over time, a practical vocabulary emerges automatically

That means BPE is doing two jobs:

1. Learning a reusable vocabulary
2. Using that vocabulary to split future text into token pieces

A helpful mental model:

Training time:
characters/bytes → frequent merges → learned subword vocabulary

Runtime:
new text → split using learned merges → token pieces → token IDs

🔬 How BPE Works

Step-by-Step Algorithm

1. Start with character vocabulary: ['a', 'b', 'c', ..., 'z']
2. Count all adjacent character pairs in corpus
3. Merge the most frequent pair
4. Repeat until desired vocabulary size

Visual Example

Corpus: "low low low lower lowest"

Iteration 1:
Pairs: {('l','o'): 5, ('o','w'): 5, ('w','e'): 1, ...}
Most frequent: ('l','o') → merge to 'lo'
Result: "lo w lo w lo w lo wer lo west"

Iteration 2:
Pairs: {('lo','w'): 5, ('w','e'): 1, ...}
Most frequent: ('lo','w') → merge to 'low'
Result: "low low low lower lowest"

Iteration 3:
Pairs: {('low','e'): 2, ...}
Most frequent: ('low','e') → merge to 'lowe'
Result: "low low low lowe r lowe st"

💻 BPE Implementation from Scratch

Complete BPE Tokenizer

from collections import Counter
import re

class SimpleBPETokenizer:
    """
    Simplified BPE tokenizer implementation.
    This is how GPT-2, GPT-3, and many modern models tokenize.
    """
    
    def __init__(self, vocab_size=1000):
        self.vocab_size = vocab_size
        self.vocab = {}
        self.merges = {}
        
    def get_stats(self, words):
        """Count frequency of adjacent token pairs."""
        pairs = Counter()
        for word, freq in words.items():
            symbols = word.split()
            for i in range(len(symbols) - 1):
                pairs[(symbols[i], symbols[i + 1])] += freq
        return pairs
    
    def merge_vocab(self, pair, words):
        """Merge the most frequent pair in vocabulary."""
        new_words = {}
        bigram = ' '.join(pair)
        replacement = ''.join(pair)
        
        for word in words:
            new_word = word.replace(bigram, replacement)
            new_words[new_word] = words[word]
        return new_words
    
    def train(self, text):
        """Train BPE on text corpus."""
        # Start with character-level tokens
        words = {}
        for word in text.split():
            # Add space between characters
            word_tokens = ' '.join(list(word)) + ' </w>'
            words[word_tokens] = words.get(word_tokens, 0) + 1
        
        # Iteratively merge most frequent pairs
        for i in range(self.vocab_size - 256):  # 256 for base characters
            pairs = self.get_stats(words)
            if not pairs:
                break
            
            # Get most frequent pair
            best_pair = max(pairs, key=pairs.get)
            words = self.merge_vocab(best_pair, words)
            self.merges[best_pair] = i
            
            if i % 100 == 0:
                print(f"Merge {i}: {best_pair} (freq: {pairs[best_pair]})")
        
        # Build vocabulary
        self.vocab = set()
        for word in words:
            self.vocab.update(word.split())
        
        print(f"\nTraining complete!")
        print(f"Vocabulary size: {len(self.vocab)}")
        print(f"Number of merges: {len(self.merges)}")
    
    def tokenize(self, text):
        """Tokenize text using learned BPE merges."""
        tokens = []
        for word in text.split():
            # Start with characters
            word_tokens = list(word) + ['</w>']
            
            # Apply merges
            while len(word_tokens) > 1:
                pairs = [(word_tokens[i], word_tokens[i + 1]) 
                        for i in range(len(word_tokens) - 1)]
                
                # Find pair with lowest merge index (earliest merge)
                valid_pairs = [p for p in pairs if p in self.merges]
                if not valid_pairs:
                    break
                
                best_pair = min(valid_pairs, key=lambda p: self.merges[p])
                
                # Merge the pair
                new_tokens = []
                i = 0
                while i < len(word_tokens):
                    if i < len(word_tokens) - 1 and \
                       (word_tokens[i], word_tokens[i + 1]) == best_pair:
                        new_tokens.append(word_tokens[i] + word_tokens[i + 1])
                        i += 2
                    else:
                        new_tokens.append(word_tokens[i])
                        i += 1
                word_tokens = new_tokens
            
            tokens.extend(word_tokens)
        
        return tokens

# Train the tokenizer
corpus = """
The quick brown fox jumps over the lazy dog.
The dog was not amused by the fox's antics.
Quick thinking saved the day.
"""

tokenizer = SimpleBPETokenizer(vocab_size=300)
tokenizer.train(corpus)

# Test tokenization
test_text = "The quick fox"
tokens = tokenizer.tokenize(test_text)
print(f"\nTokenizing: '{test_text}'")
print(f"Tokens: {tokens}")

Output:

Merge 0: ('e', ' ') (freq: 8)
Merge 100: ('t', 'h') (freq: 5)
...
Training complete!
Vocabulary size: 287
Number of merges: 44

Tokenizing: 'The quick fox'
Tokens: ['The</w>', 'qu', 'ick</w>', 'fox</w>']

🎯 BPE in Production

Using HuggingFace's BPE (GPT-2)

from transformers import AutoTokenizer

# Load GPT-2's BPE tokenizer
tokenizer = AutoTokenizer.from_pretrained("gpt2")

text = "Hello, how are you doing today?"

# Tokenize
tokens = tokenizer.tokenize(text)
token_ids = tokenizer.encode(text)

print(f"Text: {text}")
print(f"Tokens: {tokens}")
print(f"Token IDs: {token_ids}")
print(f"Token count: {len(tokens)}")

# Decode back
decoded = tokenizer.decode(token_ids)
print(f"Decoded: {decoded}")

Output:

Text: Hello, how are you doing today?
Tokens: ['Hello', ',', 'Ġhow', 'Ġare', 'Ġyou', 'Ġdoing', 'Ġtoday', '?']
Token IDs: [15496, 11, 703, 389, 345, 1804, 1909, 30]
Token count: 8
Decoded: Hello, how are you doing today?

Note: Ġ represents a space character in GPT-2's tokenizer

What the production infographic is trying to show

When you look at the BPE and numeric-token-ID infographics together, the important sequence is:

text
→ subword pieces
→ vocabulary lookup
→ token IDs
→ model input

So BPE alone is not the full pipeline.

• BPE decides the pieces
• the vocabulary stores those pieces
• the tokenizer converts each piece into a numeric ID
• the model reads IDs, not raw text

Example:

"unbelievable"
→ ["un", "believ", "able"]
→ [451, 9821, 735]

This is why vocabulary design and token IDs are tightly connected in real GPT-style systems.

🔍 BPE Characteristics

Strengths

✅ Handles rare words - Breaks them into subwords ✅ No unknown tokens - Can represent anything ✅ Efficient - Good balance of vocab size and sequence length ✅ Data-driven - Learns from your corpus

Weaknesses

❌ Greedy algorithm - May not find optimal solution ❌ Frequency-based - Ignores linguistic structure ❌ Deterministic - Same input always gives same output ❌ Sensitive to corpus - Quality depends on training data

🎯 When to Use BPE

Use BPE when:

• Building general-purpose language models
• Working with multiple languages
• Need to handle rare/unknown words
• Want proven, battle-tested approach

Consider alternatives when:

• Need probabilistic tokenization (use Unigram)
• Want linguistic awareness (use WordPiece)
• Working with specific languages (use SentencePiece)

🎯 Practice Exercise

Challenge: Modify the BPE implementation to:

1. Handle punctuation separately
2. Add special tokens like [CLS] and [SEP]
3. Implement vocabulary pruning for rare tokens

Next: 01.b WordPiece - Learn how BERT tokenizes differently