Byte Pair Encoding (BPE)

Byte Pair Encoding (BPE) is the dominant subword tokenization algorithm in modern Large Language Models (including GPT-2, GPT-3, GPT-4, LLaMA, Mistral, and Claude). It begins with individual base characters (or raw bytes) and iteratively merges the most frequent adjacent symbol pairs in a training corpus to create a compact, reusable dictionary of subwords.

Before subword tokenization, Natural Language Processing suffered from a severe trade-off between word-level and character-level modeling:

• Word-level tokenization: Requires an entry for every distinct inflected word, slang term, and misspelling. When vocabulary exceeds 50k–100k, embedding matrices consume gigabytes of VRAM. Unseen words collapse into the catastrophic [UNK] (unknown) token.
• Character-level tokenization: Solves out-of-vocabulary words but produces extremely long sequence lengths. A 1,000-word essay becomes 6,000 character tokens, exhausting the quadratic $O(N^2)$ self-attention window and weakening long-range dependencies.
• BPE's Sweet Spot: Common words stay whole ("the" $\rightarrow$ 1 token), rare words decompose into reusable pieces ("tokenization" $\rightarrow$ ["token", "ization"]), and sequences stay short while preventing [UNK] tokens.

Imagine building language with LEGO bricks. Initially, you are given only individual $1\times1$ plastic studs (characters). Every word in your corpus is spelled out stud by stud.

Now, you inspect the floor and ask: "Which two adjacent studs appear together most frequently?" You superglue those two together into a new $1\times2$ brick. You scan the floor again and glue the next most frequent adjacent combo. After thousands of cycles, you have pre-assembled common brick shapes (stems, prefixes, suffixes, and entire words), yet you can always fall back to single studs for rare structures.

Initial state: Every word is segmented into characters + end-of-word marker (_)
  "low"    →  l  o  w  _
  "lower"  →  l  o  w  e  r  _
  "newest" →  n  e  w  e  s  t  _
  "widest" →  w  i  d  e  s  t  _

1. Most frequent pair: ('e', 's') appearing in "newest" and "widest"
   Merge: 'e' + 's' → 'es'

2. Next most frequent: ('es', 't')
   Merge: 'es' + 't' → 'est'

3. Next most frequent: ('l', 'o') and ('lo', 'w')
   Merge: 'l' + 'o' → 'lo' → 'low'

Vocabulary grows organically from individual characters into meaningful subwords!

A frequent beginner misconception is confusing BPE Training with BPE Tokenization (Inference). These are two completely distinct operations:

Phase A: BPE Training (Vocabulary Learning)

• Input: Large training corpus of raw text + target vocabulary budget $V$.
• Initialization: Pre-tokenize text into words, append boundary markers (like _ or Ġ), and split into characters. Base vocabulary $V_0$ consists of all unique characters.
• Iteration: At step $k$, count all adjacent symbol pairs across all words. Find the argmax pair $(a, b)$, create token $ab$, add it to vocabulary $V_k = V_{k-1} \cup \{ab\}$, and record merge rule $a + b \rightarrow ab$.
• Termination: Stops when target merge count $N = V - |V_0|$ is reached or no pairs remain.

Phase B: BPE Tokenization / Inference (Applying Merges)

• Input: A new unseen sentence or prompt.
• Initialization: Split word into individual characters.
• Deterministic Replay: Iterate through the ordered list of learned merge rules exactly in the order they were learned during training. For each rule $(a, b) \rightarrow ab$, if adjacent tokens $a$ and $b$ appear in the word, merge them.
• Output: The resulting sequence of token IDs mapped from the vocabulary table.

Here is the formal algorithmic structure of BPE training in pseudocode:

# BPE Training Loop Pseudocode
def train_bpe(corpus_word_freqs, target_merges):
    # 1. Initialize vocabulary with base characters
    vocab = {char for word in corpus_word_freqs for char in word}
    
    # 2. Represent each word as a tuple of symbols + end marker
    splits = {word: list(word) + ['_'] for word in corpus_word_freqs}
    merge_rules = []
    
    # 3. Iterative merge loop
    for step in range(target_merges):
        pair_counts = Counter()
        for word, symbols in splits.items():
            freq = corpus_word_freqs[word]
            for i in range(len(symbols) - 1):
                pair_counts[(symbols[i], symbols[i+1])] += freq
                
        if not pair_counts:
            break
            
        best_pair = max(pair_counts, key=pair_counts.get)
        new_symbol = best_pair[0] + best_pair[1]
        
        # Apply merge across all words in split table
        for word in splits:
            splits[word] = merge_pair_in_sequence(splits[word], best_pair, new_symbol)
            
        vocab.add(new_symbol)
        merge_rules.append(best_pair)
        
    return vocab, merge_rules

Let's manually execute 3 full merge steps on a controlled toy corpus. Follow every frequency calculation by hand:

The mathematics of BPE governs vocabulary explosion, token compression rates, and lookup computational complexity.

Here is the complete state machine representing BPE training and tokenization cycles:

graph TD
    subgraph "Training Phase"
    A[Raw Training Corpus] --> B[Word Freq Dictionary]
    B --> C[Split Words into Chars]
    C --> D[Count All Adjacent Pairs]
    D --> E[Select Most Frequent Pair a, b]
    E --> F[Create Merged Token ab]
    F --> G[Update Corpus Sequences]
    G --> H{Merge Count < N?}
    H -- Yes --> D
    H -- No --> I[Save Merge Rules & Vocab]
    end

    subgraph "Inference / Tokenization Phase"
    J[New Input Word] --> K[Split into Initial Chars]
    K --> L[Replay Learned Merges in Order]
    L --> M[Output Subword Tokens & IDs]
    end

    I -.-> L

    style A fill:#1e2235,stroke:#3b82f6
    style I fill:#1a1e2e,stroke:#34d399,stroke-width:2px
    style M fill:#1a1e2e,stroke:#38bdf8,stroke-width:2px
          

⚡ Live Interactive BPE Tokenizer Inference

Type any word below (e.g. lowest, newer, widest, tokenize). The visualizer runs an active in-browser BPE engine trained on a live subword corpus (low, lower, lowest, new, newer, newest, widest) and shows every merge step applied.

Here is the full, clean, dependency-free Python implementation of both BPE Training and BPE Tokenization:

from collections import Counter
import re

# ── 1. Corpus Preparation ──
def get_vocab(corpus_dict):
    """Convert word-frequency dictionary into space-delimited character strings."""
    vocab = Counter()
    for word, freq in corpus_dict.items():
        # Represent word as space-separated characters with end-of-word token '_'
        vocab[' '.join(list(word) + ['_'])] += freq
    return vocab

# ── 2. Frequency Counter for Adjacent Pairs ──
def get_pairs(vocab):
    """Scan vocabulary words and accumulate adjacent pair frequencies."""
    pairs = Counter()
    for word, freq in vocab.items():
        symbols = word.split()
        for i in range(len(symbols) - 1):
            pairs[(symbols[i], symbols[i + 1])] += freq
    return pairs

# ── 3. Merge Selected Pair in Vocabulary ──
def merge_vocab(pair, vocab):
    """Replace occurrences of (pair[0], pair[1]) with concatenated token."""
    new_vocab = {}
    bigram = re.escape(' '.join(pair))
    replacement = ''.join(pair)
    pattern = re.compile(r'(?