BPE: Subword Units for Neural MT

Chapter 2: The BPE Algorithm

Let's walk through BPE step by step on a real vocabulary. This is the training phase — where we learn which character pairs to merge. The input is a corpus of text; the output is an ordered list of merge rules.

Step 1: Initialize

Start by splitting every word in the training corpus into individual characters, with a special end-of-word symbol (we'll use ·). Count word frequencies. Suppose our corpus contains these words with their counts:

training corpus
low:    5   → l o w ·
lower:  2   → l o w e r ·
newest: 6   → n e w e s t ·
widest: 3   → w i d e s t ·

The initial vocabulary is just the set of characters: {l, o, w, e, r, n, s, t, i, d, ·}. Eleven symbols.

Step 2: Count pairs

Count every adjacent character pair across the corpus, weighted by word frequency:

pair frequencies
(e, s): 6 (newest) + 3 (widest) = 9
(s, t): 6 (newest) + 3 (widest) = 9
(t, ·): 6 (newest) + 3 (widest) = 9
(l, o): 5 (low) + 2 (lower) = 7
(o, w): 5 (low) + 2 (lower) = 7
(n, e): 6
(e, w): 6
(w, e): 6
(w, ·): 5
...

Step 3: Merge the most frequent pair

The most frequent pair is (e, s) with count 9. Merge it into a new symbol "es":

after merge #1: (e, s) → es
low:    5   → l o w ·
lower:  2   → l o w e r ·
newest: 6   → n e w es t ·
widest: 3   → w i d es t ·

Vocabulary: {l, o, w, e, r, n, s, t, i, d, ·, es}  — 12 symbols

Step 4: Repeat

Recount pairs. Now (es, t) has frequency 9. Merge it into "est":

after merge #2: (es, t) → est
low:    5   → l o w ·
lower:  2   → l o w e r ·
newest: 6   → n e w est ·
widest: 3   → w i d est ·

Vocabulary: {l, o, w, e, r, n, s, t, i, d, ·, es, est}  — 13 symbols

Continue: (est, ·) freq 9 → merge into "est·". Then (l, o) freq 7 → merge into "lo". Then (lo, w) freq 7 → merge into "low". And so on, until we've done the desired number of merges.

python
import collections

def learn_bpe(corpus, num_merges):
    # Step 1: Initialize — split words into characters
    vocab = {}
    for word, freq in corpus.items():
        # Add end-of-word marker, split into chars
        symbols = list(word) + ['</w>']
        vocab[tuple(symbols)] = freq

    merges = []
    for i in range(num_merges):
        # Step 2: Count all adjacent pairs
        pairs = collections.Counter()
        for symbols, freq in vocab.items():
            for j in range(len(symbols) - 1):
                pairs[(symbols[j], symbols[j+1])] += freq

        if not pairs:
            break

        # Step 3: Find most frequent pair
        best = max(pairs, key=pairs.get)
        merges.append(best)

        # Step 4: Apply merge to vocabulary
        new_vocab = {}
        for symbols, freq in vocab.items():
            new_symbols = []
            j = 0
            while j < len(symbols):
                if j < len(symbols)-1 and (symbols[j], symbols[j+1]) == best:
                    new_symbols.append(symbols[j] + symbols[j+1])
                    j += 2
                else:
                    new_symbols.append(symbols[j])
                    j += 1
            new_vocab[tuple(new_symbols)] = freq
        vocab = new_vocab

    return merges, vocab

Chapter 3: Learning Merge Rules

The number of merge operations is the one hyperparameter that controls BPE. It determines your vocabulary size and the granularity of your subword units. Sennrich et al. explored merge counts from 10,000 to 90,000. The choice creates a direct tradeoff.

The vocabulary size tradeoff

Few merges (small vocabulary, ~10K): Words are split into many small pieces. "unfortunately" becomes ["un", "for", "tun", "ate", "ly"]. Sequences are longer, but every piece is frequent and well-learned. Good for morphologically rich languages where you need to decompose aggressively.

Many merges (large vocabulary, ~90K): Common words stay intact. "unfortunately" stays as one token. Sequences are shorter, but rare subwords may not have enough training examples. Approaches word-level behavior with the same OOV risks.

Joint vs separate vocabularies

For machine translation, you have two languages. Should you learn BPE separately for each, or jointly on the combined corpus?

Sennrich et al. found that joint BPE is better for related language pairs (English-German, English-French) because they share many cognates and named entities. For distant language pairs (English-Chinese), separate vocabularies can be better since they share very few subword units.

The end-of-word marker

BPE uses a special end-of-word symbol (written as · or </w>) appended to the last character of each word before training. This is crucial for reversibility. Without it, you can't tell where words end when reconstructing text from subword tokens.

python
# Without end-of-word marker: ambiguous!
# "low" → ["lo", "w"]
# "lower" → ["lo", "w", "er"]
# How do you know "w" ends "low" vs continues to "er"?

# With end-of-word marker: unambiguous
# "low" → ["lo", "w·"]  (· marks word boundary)
# "lower" → ["lo", "w", "er·"]
# "w·" is a DIFFERENT token from "w" — the · tells you the word ends here

# Reconstruction: join tokens, replace · with space
tokens = ["lo", "w·", "lo", "w", "er·"]
# → "low lower"

Chapter 4: Encoding New Text

Training gives us an ordered list of merge rules. Now we need to apply those rules to new text at inference time. This is the encoding phase — turning an arbitrary string into a sequence of subword tokens.

The encoding algorithm

Given a word and the learned merge rules:

The order matters. You apply merge rules in the exact sequence they were learned during training. Early merges capture frequent patterns (suffixes, prefixes). Later merges build up to common words.

What about truly unknown words?

This is BPE's superpower. Consider "lowest" — even if this exact word never appeared in training, its subword pieces "low" and "est" probably did. Now consider a word from a language you've never trained on, like the Czech word "nejneobvyklejší" (most unusual). BPE handles it by falling back to characters:

python
# If no merge rules apply, characters remain as individual tokens
# "nejneobvyklejší" might tokenize as:
# ['ne', 'j', 'ne', 'ob', 'vy', 'k', 'le', 'j', 'ší', '·']
# Some pieces got merged (ne, ob, le) because they're common
# Others stayed as characters (j, k) because they're rare in context

# The key: NOTHING is ever truly OOV
# Worst case: every character is its own token
# This is equivalent to character-level processing
# for that specific word, while common words stay efficient

Encoding implementation

python
def apply_bpe(word, merges):
    """Encode a word using learned BPE merge rules."""
    # Start with characters
    symbols = list(word) + ['</w>']

    # Apply each merge rule in order
    for (left, right) in merges:
        i = 0
        while i < len(symbols) - 1:
            if symbols[i] == left and symbols[i+1] == right:
                symbols[i:i+2] = [left + right]
                # Don't increment i — check if new symbol merges with next
            else:
                i += 1

    return symbols

# Example usage
merges = [('e','s'), ('es','t'), ('est','</w>'), ('l','o'), ('lo','w')]
print(apply_bpe("lowest", merges))
# ['low', 'est</w>'] — 2 tokens instead of 6 characters

print(apply_bpe("newer", merges))
# ['n', 'e', 'w', 'e', 'r', '</w>'] — falls back to chars where no merges apply

Chapter 5: BPE for Translation

Now let's see how Sennrich et al. actually integrated BPE into a neural machine translation pipeline. The NMT system they used was an attention-based encoder-decoder model — the standard architecture in 2016 (before Transformers).

The pipeline

The @@ notation is a practical detail: during BPE segmentation, every subword except the last in a word gets @@ appended. To reconstruct the original word, you just remove @@ and concatenate.

Why this works for translation

BPE solves three concrete translation problems:

Compound words: German "Abwasserbehandlungsanlage" (wastewater treatment plant) is split into "Ab@@ wasser@@ behandlungs@@ anlage". The model can translate each morpheme because it has seen "wasser" (water) and "Anlage" (facility) in many contexts.

Named entities: "Schwarzenegger" might split into "Sch@@ war@@ zen@@ egger". Even if the model hasn't seen this name, it has learned to copy subword pieces from source to target — names typically stay the same across languages.

Morphological agreement: Russian adjectives agree with nouns in gender, number, and case — producing dozens of forms. BPE learns the common stems and suffixes separately, allowing the model to generalize.

python
# BPE in a translation pipeline
from subword_nmt import learn_bpe, apply_bpe

# 1. Learn BPE on training data
learn_bpe(
    input="train.en-de",    # concatenated EN + DE training text
    output="bpe.codes",     # merge rules file
    num_operations=32000   # vocabulary size
)

# 2. Apply to training data
bpe = apply_bpe.BPE(codes=open("bpe.codes"))
segmented = bpe.process_line("The unbreakable code was discovered")
# → "The un@@ break@@ able code was dis@@ cover@@ ed"

# 3. Train NMT model on segmented data (standard encoder-decoder)
# Model vocabulary: ~32K BPE tokens instead of ~500K words

# 4. At inference: segment input, translate, de-segment output
src = bpe.process_line("Schwarzenegger attended the ceremony")
tgt_bpe = model.translate(src)  # "Sch@@ war@@ zen@@ egger besuchte die Zere@@ monie"
tgt = tgt_bpe.replace("@@ ", "")   # "Schwarzenegger besuchte die Zeremonie"

Chapter 6: Results & Analysis

Sennrich et al. tested BPE on four language pairs from the WMT 2015 translation task. The results demonstrated that BPE consistently improves over word-level baselines, especially for morphologically rich target languages.

BLEU scores

Key findings from the results:

BPE beats the dictionary back-off. The word-level + back-off approach was the previous best method for handling OOV words. BPE surpasses it on all language pairs except one, without needing any external dictionary.

Compound-heavy languages benefit most. EN→DE shows the largest improvement (+1.2 BLEU over back-off) because German has many compound words that BPE decomposes effectively. EN→RU also benefits due to Russian's rich morphology.

The optimal merge count varies. 60K merges works best for EN→RU (more decomposition helps with Russian morphology), while 90K merges works best for EN→DE and DE→EN. This aligns with the tradeoff: more morphologically complex languages benefit from smaller subword units.

Analysis: what BPE learns

The paper includes a qualitative analysis showing that BPE discovers linguistically meaningful subword units without any linguistic knowledge:

BPE-discovered morphemes
# Prefixes:  un- , re- , pre- , über- , aus-
# Suffixes:  -ing , -tion , -ness , -ung , -lich , -keit
# Stems:    break , work , hand , schuh (shoe)

# German compound decomposition:
# Handschuhschneeballwerfer → Hand@@ schuh@@ schnee@@ ball@@ werfer
#                            (glove + snow + ball + thrower)
# Each piece is a real German morpheme!

Rare word translation examples

The paper shows specific examples where BPE enables correct translation of rare words:

The "Charlemagne" example is particularly interesting. BPE didn't just copy the name — it translated it to the German equivalent "Karl der Große" (Charles the Great). This happened because BPE segmented "Charlemagne" into subwords that overlapped with training examples containing this historical figure.

Chapter 7: Connections

Sennrich et al.'s 2016 paper had an impact far beyond machine translation. BPE became the de facto tokenization method for large language models, and its direct descendants power every major model today.

The BPE family tree

Byte-level BPE (used in GPT-2+) is the most important descendant. Instead of operating on Unicode characters, it operates on raw bytes (values 0-255). This means the base vocabulary is just 256 symbols, and BPE can tokenize any byte sequence — any language, any encoding, even binary data. Radford et al. showed this works as well as character-level BPE while being more universal.

SentencePiece (Kudo, 2018) removes BPE's assumption that input is pre-tokenized into words by whitespace. This is crucial for languages like Japanese and Chinese that don't use spaces between words. SentencePiece treats the raw input as a character stream and can use either BPE or Unigram LM as the merging algorithm.

Impact on modern LLMs

Every major language model uses a BPE variant. The vocabulary sizes have grown:

tokenizer vocabulary sizes
GPT-2:      50,257 tokens  (byte-level BPE)
GPT-3:      50,257 tokens  (same tokenizer as GPT-2)
GPT-4:     100,256 tokens  (cl100k_base, byte-level BPE)
LLaMA:      32,000 tokens  (SentencePiece BPE)
LLaMA-3:   128,256 tokens  (tiktoken byte-level BPE)
Mistral:     32,000 tokens  (SentencePiece BPE)

What BPE got right

Looking back from 2026, BPE's key insight — that the right vocabulary emerges from data statistics rather than linguistic rules — proved fundamental. Every subsequent tokenization method builds on this principle. The specific merge heuristic (frequency vs. likelihood) matters less than the architecture: start with atoms, iteratively combine the most useful units, stop at a fixed vocabulary size.

"The most frequent pair captures the most predictable structure. Compression and understanding are the same thing." — adapted from the spirit of Gage (1994)