BPE: Byte Pair Encoding - The Most Common Tokenization Method¶
Overview¶
Byte Pair Encoding (BPE) iteratively merges the most frequent pair of bytes/characters to build vocabulary. Simple yet powerful, used by GPT models and many others.
- Paper: "Neural Machine Translation of Rare Words with Subword Units" (Sennrich et al., 2016)
- Adoption: GPT-2, GPT-3, GPT-4, and most modern models
- Principle: Build vocabulary bottom-up from bytes/characters
- Result: Efficient subword tokenization without rare words
How BPE Works¶
Algorithm (Step-by-Step)¶
Start: Every character is a token (character-level)
Goal: Merge frequent pairs to build subwords
Example: "hello world" (repeated 3 times in the corpus)
Initial state (character-level):
- Unique chars: h, e, l, o, (space), w, r, d
- Frequency: h:3, e:3, l:9, o:6, (space):3, w:3, r:3, d:3
- Text (one occurrence): "h e l l o (space) w o r l d"
Step 1: Count adjacent pairs across the whole corpus
- In this TINY corpus every pair appears exactly 3 times:
"h e", "e l", "l l", "l o", "o (space)", "(space) w",
"w o", "o r", "r l", "l d" → all tied at 3
- Tie-break (use the order shown): pick "l l" → merge to "ll"
- Text becomes: "h e ll o (space) w o r ll d"
Step 2: Recount pairs, merge the next most frequent
- Ties again (all pairs appear 3 times):
"h e", "e ll", "ll o", "o (space)", "(space) w",
"w o", "o r", "r ll", "ll d" → all 3
- Pick "o (space)" → merge to "o_"
- Text becomes: "h e ll o_ w o r ll d"
- (Note: "o_" marks the space inside a token — real tokenizers
encode spaces as Ġ or ▁ — see the Concrete Example below)
Step 3: Repeat until desired vocab size
- Keep merging most frequent pairs
- Each merge creates a new token
- Stop when vocab size = target (e.g., 50K)
💡 Tiny corpora tie everywhere — a REAL corpus (millions of words)
gives distinct pair frequencies, so the merge order is deterministic.
Final vocabulary:
- Base: all single characters (the alphabet)
- Plus: every merged unit (one new token per merge step)
- Total size = alphabet size + number of merges
Concrete Example: "hello world"¶
Concrete Example: "hello world"¶
Corpus: "hello world" repeated 3 times (every merge below is justified by frequency 3; ties broken in the order shown).
Initial: h e l l o Ġ w o r l d
(Ġ represents the space in tokenization)
Iteration 1: Merge l + l → ll
Result: h e ll o Ġ w o r ll d
Iteration 2: Merge h + e → he
Result: he ll o Ġ w o r ll d
Iteration 3: Merge he + ll → hell
Result: hell o Ġ w o r ll d
Iteration 4: Merge hell + o → hello
Result: hello Ġ w o r ll d
Iteration 5: Merge Ġ + w → Ġw
Result: hello Ġw o r ll d
Iteration 6: Merge Ġw + o → Ġwo
Result: hello Ġwo r ll d
Iteration 7: Merge Ġwo + r → Ġwor
Result: hello Ġwor ll d
Iteration 8: Merge ll + d → lld
Result: hello Ġwor lld
Iteration 9: Merge Ġwor + lld → Ġworld
Result: hello Ġworld
Final tokens: ["hello", "Ġworld"]
Vocabulary: 8 base chars + 9 merges = 17 tokens
💡 Where did the space go? Iteration 5 glued Ġ to the FOLLOWING word (Ġworld), which is why GPT-2-style output shows space prefixes. If iteration 5 had merged hello Ġ instead, you'd get ["helloĠ", "world"]. Real tokenizers decide this by design:
GPT-2 byte-level BPE: add_prefix_space=True → "Ġworld"
SentencePiece: ▁ prefix → "▁world"
Both avoid a standalone "space" token and keep the boundary
information attached to a word.
BPE Algorithm Implementation¶
Python Implementation¶
def bpe(text, vocab_size=50000, num_merges=None):
"""
Implement BPE from scratch
Args:
text: Raw text
vocab_size: Target vocabulary size
num_merges: Number of merge operations (alt to vocab_size)
"""
from collections import defaultdict, Counter
# Step 1: Split into words and count frequencies
words = text.split()
word_freqs = Counter(words)
# Convert each word into "space-separated chars + </w>"
# e.g. "hello" → "h e l l o </w>" (</w> marks the word end)
vocab = {}
for word, freq in word_freqs.items():
vocab[' '.join(word) + ' </w>'] = freq
# Step 2: Get initial alphabet (all characters)
alphabet = set()
for word in vocab.keys():
for char in word:
if char != ' ':
alphabet.add(char)
# Step 3: Iteratively merge most frequent pair
num_merges_to_do = num_merges or vocab_size - len(alphabet)
for i in range(num_merges_to_do):
# Count all adjacent pairs
pairs = defaultdict(int)
for word, freq in vocab.items():
symbols = word.split()
for j in range(len(symbols) - 1):
pair = (symbols[j], symbols[j+1])
pairs[pair] += freq
# Find most frequent pair
if not pairs:
break
best_pair = max(pairs, key=pairs.get)
# Merge best pair in vocabulary
new_word = ''.join(best_pair)
new_vocab = {}
bigram = ' '.join(best_pair)
replacement = new_word
for word in vocab:
new_word_str = word.replace(bigram, replacement)
new_vocab[new_word_str] = vocab[word]
vocab = new_vocab
alphabet.add(new_word)
if (i + 1) % 100 == 0:
print(f"Merge {i+1}: {best_pair} → {new_word} (vocab size: {len(alphabet)})")
return vocab, alphabet
# Usage:
text = "hello world hello" * 3
vocab, alphabet = bpe(text, num_merges=10)
print(f"Vocabulary size: {len(alphabet)}")
print(f"Sample tokens: {sorted(list(alphabet))[:20]}")
Using Hugging Face Tokenizers¶
from tokenizers import Tokenizer, models, pre_tokenizers, trainers
# Create BPE tokenizer
tokenizer = Tokenizer(models.BPE())
# Set pre-tokenizer (split on spaces/punctuation)
tokenizer.pre_tokenizer = pre_tokenizers.ByteLevel(add_prefix_space=True)
# Create trainer
trainer = trainers.BpeTrainer(
vocab_size=50000,
special_tokens=["<|endoftext|>", "<|padding|>"]
)
# Train on files
tokenizer.train(
files=["text_file.txt"],
trainer=trainer
)
# Use tokenizer
encoded = tokenizer.encode("hello world")
print(encoded.tokens) # ['hello', ' world']
print(encoded.ids) # [1234, 5678]
BPE Variants¶
Byte-Level BPE¶
Standard BPE: Character-level (128 ASCII chars)
Byte-Level BPE: Start from bytes (256 possible bytes)
Advantage:
- Can handle any Unicode character
- Doesn't need special handling for languages
- Single representation for all text
- Example: GPT-2, GPT-3 use byte-level BPE
Implementation difference:
```python
# Standard BPE: Characters
text = "hello"
initial_tokens = ['h', 'e', 'l', 'l', 'o']
# Byte-Level BPE: UTF-8 bytes
text = "hello"
utf8_bytes = text.encode('utf-8') # b'hello'
initial_tokens = list(utf8_bytes) # [104, 101, 108, 108, 111]
# Then treat numbers as tokens!
Benefits: - Works for all Unicode - No need for separate character encodings - Same algorithm for all languages - Slightly less efficient (starts with 256 instead of 128)
### Unigram LM
Approach: - Start with vocab_size tokens - Model probability of each token - Remove tokens that don't help (lowest probability) - Iterate until desired vocab size
Vs BPE: - BPE: Greedy merging (bottom-up) - Unigram: Probabilistic (top-down) - Unigram often slightly better quality - But BPE is simpler and widely adopted
Used by: - SentencePiece (can use Unigram or BPE)
> 📌 **WordPiece** (BERT) is the third major family — it merges pairs by
> *likelihood gain* rather than raw frequency, and marks continuations
> with `##`. See [06 Wordpiece](/02-llm-modeling/00-fundamentals/00-tokenization/06-wordpiece/).
---
## BPE Encoding/Decoding
### Encoding (Text → Tokens)
```python
# GPT-2 tokenizer (uses BPE)
import tiktoken
enc = tiktoken.encoding_for_model("gpt-3.5-turbo")
text = "Hello, world! 你好"
tokens = enc.encode(text)
print(tokens)
# Output: [15339, 11, 1917, 0, 242, 25180, 234]
# (approximate; exact IDs depend on the encoding version)
# "Hello"=15339 ","=11 " world"=1917 "!"=0 " 你好"=242,25180,234
# Note: Chinese text takes 3+ tokens in cl100k (see 05-Multilingual)
# Decode back
decoded = enc.decode(tokens)
print(decoded) # "Hello, world! 你好"
Token Composition¶
GPT-3 encoding example:
Text: "hello world"
↓
Tokens: ["hello", " world"]
↓
Token IDs: [15339, 1917]
Text: "The quick brown fox"
↓
Tokens: ["The", " quick", " brown", " fox"]
↓
Token IDs: [464, 2068, 6218, 21831]
Text: "extraordinary"
↓
Tokens: ["extra", "ordinary"] (might be split if "extraordinary" not in vocab)
↓
Token IDs: [12345, 6789]
Text: "🎉"
↓
Tokens: bytes representing emoji
↓
Token IDs: multiple IDs (emoji is multi-token)
BPE Limitations & Gotchas¶
Limitation 1: Inefficient for Some Languages¶
English:
Text: "hello world"
Tokens: ["hello", " world"] - 2 tokens
Efficiency: Good
Chinese:
Text: "你好世界"
Tokens: ["你", "好", "世", "界"] - 4 tokens
Efficiency: Poor (no spaces!)
Arabic (right-to-left):
Text: "مرحبا بالعالم"
Tokens: Multiple bytes
Efficiency: Medium
Lesson: BPE optimal for English, less so for other languages
Limitation 2: Long Subword Sequences¶
Problem: Rare long words split into many tokens
Word: "internationalization"
BPE encoding: ["inter", "nation", "al", "ization"] - 4 tokens
Problem: Lost structure, harder to learn
Word: "pneumonoultramicroscopicsilicovolcanoconiosis"
BPE encoding: 15+ tokens!
Problem: Very inefficient, sequence grows
Solution: Larger vocabulary can help
But: Vocab size is limited (computational trade-off)
Limitation 3: Suboptimal for Code¶
Python code:
def count_elements():
return len(items)
BPE tokenization:
["def", " count", "_", "elements", "():", "\n", " ", "return", " len", "(", "items", ")", "\n"]
Problems:
- "_" is separate token (should be part of name)
- "()" might be merged or separate
- Indentation awkward
- Not great for code!
Better: Code-aware tokenizers
- Understand Python syntax
- Better splitting at meaningful boundaries
- More efficient for code
BPE Performance¶
Token Efficiency Comparison¶
Model Vocab Size Avg Tokens/Word Language
──────────────────────────────────────────────────
GPT-2 (BPE) 50K 1.15 English
GPT-3 (BPE) 50K 1.15 English
BERT 30K 1.25 English
LLaMA 32K 1.20 English
Mistral 32K 1.20 English
Token inflation (tokens per word > 1):
Text Tokens/Word
─────────────────────────────────
Common English 1.10
Technical English 1.20
Code 1.30
Mixed languages 1.50
All Unicode 2.00
Implication:
- 1M word document = 1.2M tokens (typical)
- Training cost ∝ tokens
- Better tokenizer = 10-20% cost savings
Practical BPE Tips¶
Training a Custom BPE Tokenizer¶
from tokenizers import Tokenizer, models, pre_tokenizers, trainers, processors
# Create BPE tokenizer with custom config
tokenizer = Tokenizer(models.BPE())
# Configure
tokenizer.pre_tokenizer = pre_tokenizers.ByteLevel(add_prefix_space=True)
tokenizer.post_processor = processors.ByteLevel(trim_offsets=True)
# Train on your data
trainer = trainers.BpeTrainer(
vocab_size=32000,
min_frequency=2, # Minimum frequency to include
special_tokens=[
"<|begin_of_text|>",
"<|end_of_text|>",
"<|padding|>",
]
)
files = [
"data/train.txt",
"data/validation.txt",
]
tokenizer.train(files=files, trainer=trainer)
# Save for later use
tokenizer.save("my_tokenizer.json")
# Load and use
loaded_tokenizer = Tokenizer.from_file("my_tokenizer.json")
encoded = loaded_tokenizer.encode("hello world")
Key Takeaways¶
🔄 BPE: Iteratively merge most frequent character pairs
📊 Simple yet effective: Character-level → subwords → vocabulary
🌐 Widely adopted: GPT-2, GPT-3, GPT-4 use BPE
💾 Efficient: ~32-50K vocab handles most text
⚠️ Trade-offs: Inefficient for some languages, not optimal for code
Related Notes in Tokenization Subdirectory¶
- 00 Tokenization Fundamentals - Overview
- 02 Sentencepiece - Modern alternative to BPE
- 06 Wordpiece - BERT-style variant (## continuations)
- 03 Token Efficiency & Compression - Improving token count
- 04 Tokenization Best Practices - Tips and tricks