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"¶

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

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](/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

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

BPE: Byte Pair Encoding - The Most Common Tokenization Method¶

Overview¶

How BPE Works¶

Algorithm (Step-by-Step)¶

Concrete Example: "hello world"¶

Concrete Example: "hello world"¶

BPE Algorithm Implementation¶

Python Implementation¶

Using Hugging Face Tokenizers¶

BPE Variants¶

Byte-Level BPE¶

Token Composition¶

BPE Limitations & Gotchas¶

Limitation 1: Inefficient for Some Languages¶

Limitation 2: Long Subword Sequences¶

Limitation 3: Suboptimal for Code¶

BPE Performance¶

Token Efficiency Comparison¶

Practical BPE Tips¶

Training a Custom BPE Tokenizer¶

Key Takeaways¶

Related Notes in Tokenization Subdirectory¶