Skip to content

BPE

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
text = "hello"
initial_tokens = ['h', 'e', 'l', 'l', 'o']

# Byte-Level BPE
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

Alternative to BPE: Statistical approach

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](/01-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
# (approximate; exact IDs depend on the encoding version)
# "Hello"=15339 ","=11 " world"=1917 "!"=0 " 你好"=242,25180,234
# Note

# 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

-