Language Models2016foundational10 min read
Neural Machine Translation of Rare Words with Subword Units
ترجمة الكلمات النادرة آلياً باستخدام وحدات دون الكلمة
Sennrich, R. · Haddow, B. · Birch, A. — ACL
The problem
Neural systems in 2015 operated with a fixed — typically 30,000–50,000 words. Any word not in that list was replaced with an <UNK> , a blank placeholder the model could not translate. Rare words, names, compounds, and morphological variants were all casualties. Back-off dictionaries helped a little, but they broke the end-to-end elegance of NMT and still failed on unsegmented compounds and morphology.
The contribution
Adapt — a 1994 data compression algorithm — as a method for NMT. Instead of merging frequent byte pairs, BPE iteratively merges the most frequent character pairs in the training until a desired is reached. Common words stay whole; rare words are split into known pieces. The result: truly open-vocabulary translation with no <UNK> tokens, no back-off dictionary, and no architecture changes — just a preprocessing step that improved BLEU by +1.1 to +1.5 over strong baselines on English↔German and English↔Russian.
The impact
BPE became the default method for virtually every major language model that followed: GPT-1, GPT-2, GPT-3, GNMT, and most Transformer-based systems. Its variants — (BERT), (T5), and Unigram — form the tokenization backbone of modern NLP. The paper solved the open-vocabulary problem so thoroughly that fixed word-level vocabularies simply disappeared from the field. Every time you type a prompt into a language model, your text is first BPE-tokenized.
Imagine a printing press with only 5,000 movable type blocks — one for each common word. When a rare name or foreign word arrives, the typesetter has no block for it and leaves a blank ▒.
BPE is like a letter-tile workshop beside the press: it looks at which letter pairs appear together most often — "th", "er", "ing" — and casts reusable tiles for those pairs. Now the typesetter can spell any word by snapping together a few familiar tiles, and the blanks disappear forever.
The problem: a vocabulary ceiling that blocks rare words
In 2015, neural machine translation models used a fixed-size vocabulary — typically the 30,000–50,000 most frequent words from the training corpus. Every word outside that list was mapped to a single <UNK> (unknown) token. This created three interlinked problems:
1. Names and numbers vanish. A proper name like "Bundesverteidigungsministerium" (German Federal Ministry of Defence) becomes <UNK> — untranslatable.
2. Morphology explodes the vocabulary. Agglutinative languages like German, Finnish, and Turkish generate compound words combinatorially. No fixed list can cover them all.
3. Back-off dictionaries break end-to-end learning. The workaround in 2015 was a post-processing step that replaced <UNK> with dictionary lookups — but this severed the clean gradient path that makes neural models elegant and was brittle on compounds.
<UNK>. Then toggle BPE to see it split into known pieces.The idea: learn a vocabulary from the data itself
The key insight of the paper is that most rare words are not truly novel — they are composed of familiar building blocks. The German word "Abwasserbehandlungsanlage" (sewage treatment plant) is rare as a whole, but "Abwasser" (sewage), "Behandlung" (treatment), and "Anlage" (plant) are common. If we could segment rare words into these known parts, the model could translate them compositionally.
Sennrich et al. borrowed a tool from data compression: Byte Pair Encoding (BPE), originally proposed by Gage in 1994. The original BPE replaces the most frequent pair of bytes in a file with a single new byte to shrink the data. The authors adapted this principle to text: instead of bytes, merge the most frequent pairs of characters (or character sequences) to build a subword vocabulary.
The algorithm: count, merge, repeat
The BPE algorithm for text segmentation works in two phases — a training phase that learns merge rules, and an application phase that uses them:
Training (learning the merge table): Start with a vocabulary of all individual characters in the training corpus plus a special end-of-word symbol. Then, repeatedly: (1) count every adjacent character pair across the entire corpus, (2) find the most frequent pair, (3) merge it into a single new symbol and add it to the vocabulary, (4) replace all occurrences in the corpus. Repeat until you reach the desired number of merge operations (e.g., 30,000).
Application (segmenting new text): At test time, split each word into characters, then replay the learned merge operations in the exact order they were learned. Early merges fire first (common pairs like "t"+"h" → "th"), gradually building up to full common words. Rare words only get partially merged, remaining as sequences of known subword tokens.
Think of it as building with LEGO bricks. The algorithm starts with the smallest bricks (individual letters). It observes which pairs of bricks are clicked together most often across all the buildings (words) in the training city (corpus), fuses those pairs into a bigger pre-made piece, and adds it to the brick catalog. After thousands of fusions, common buildings can be placed as a single large block, while unusual buildings are still constructible from a mix of medium and small bricks — and nothing is ever missing from the kit.
Formal description of BPE
Before seeing the formula, here is what it captures intuitively: we want to build the best possible vocabulary of a given size by always merging the character pair that will compress the corpus the most — i.e., the one that appears the most.
The algorithm in code
Simplified to show the idea — not the real implementation.
import re, collections
def get_stats(vocab):
"""Count frequency of each adjacent symbol pair across all words."""
pairs = collections.defaultdict(int)
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
def merge_vocab(pair, vocab):
"""Replace every occurrence of pair with a merged symbol."""
out = {}
bigram = re.escape(' '.join(pair))
pattern = re.compile(r'(?<!\S)' + bigram + r'(?!\S)')
for word in vocab:
new_word = pattern.sub(''.join(pair), word)
out[new_word] = vocab[word]
return out
# --- Example usage ---
vocab = {'l o w </w>': 5, 'l o w e r </w>': 2,
'n e w e s t </w>': 6, 'w i d e s t </w>': 3}
num_merges = 10
for i in range(num_merges):
pairs = get_stats(vocab)
if not pairs:
break
best = max(pairs, key=pairs.get) # the greedy choice
vocab = merge_vocab(best, vocab)
print(f"Merge #{i+1}: {best[0]} + {best[1]} → {''.join(best)}")
# After training, "lowest" → "low" + "est</w>" (both known)
# A rare word like "newer" → "new" + "er</w>" (compositional!)Joint vs. separate vocabularies
A crucial design decision is whether to learn BPE separately for each language or jointly on the concatenated source and target corpora:
Separate BPE learns merge rules independently for each language. This is appropriate when source and target use different scripts (e.g., English and Russian).
Joint BPE concatenates both corpora and learns a single shared set of merge rules. This is powerful when languages share an alphabet (e.g., English and German) because cognates and loanwords like "Computer" or "Information" are segmented identically in both, giving the model a natural bridge between languages. The paper found that joint BPE with 90,000 operations produced the best results for English↔German.
The vocabulary size trade-off
The number of BPE merge operations directly controls vocabulary size and segmentation granularity. Think of it as a zoom knob:
Few merges (small vocabulary): words are split into many small pieces — sometimes individual characters. The model sees short, very frequent tokens but needs longer sequences to represent the same text. The vocabulary is compact, but the is long.
Many merges (large vocabulary): common words stay whole and the sequence is short. But the vocabulary grows large, the table consumes more memory, and rare words in the vocabulary are seen too few times to learn good representations.
The paper found that 60,000–90,000 merge operations hit the sweet spot for translation, balancing vocabulary coverage against sequence length.
Results and impact
The paper evaluated BPE on WMT 2015 English↔German and English↔Russian translation tasks. Key findings:
On English→German, BPE with of 90k operations achieved a improvement of +1.1 over the word-level baseline with a back-off dictionary. For rare words specifically, the unigram F1 improved dramatically — the model no longer needed to copy unknown tokens.
On English→Russian (different scripts), separate BPE with 60k operations per language worked best, improving over the baseline while handling Cyrillic morphology gracefully.
Crucially, BPE required zero changes to the NMT architecture. It was a pure preprocessing step — segment the text, train the same model, and post-process by merging subword tokens back (removing the @@ markers). This simplicity is what made adoption universal.
BPE vs. other segmentation methods
The paper also tested character-level bigram segmentation (splitting words into overlapping character pairs) and compared it against BPE. Character bigrams were simpler but produced much longer sequences, slowing training and hurting BLEU.
BPE sits in a sweet spot: it is purely data-driven (no linguistic rules), produces compact sequences (frequent words stay whole), and handles any language. Its later variants refine the core idea:
WordPiece (used in BERT and GNMT) is similar but selects merges by maximizing the language model likelihood rather than raw frequency.
SentencePiece removes the dependency on pre-tokenized whitespace-separated words, treating the raw text as a stream — critical for languages like Japanese and Chinese that don't use spaces.
Unigram LM (Kudo 2018) starts from a large vocabulary and prunes down rather than building up, using a unigram language model to choose which pieces to keep.
Why BPE became the foundation of modern NLP
1994
Original BPE (Gage)
A data compression algorithm that iteratively replaces the most frequent byte pair with a new symbol. Pure compression — no NLP application yet.
2016
BPE for NMT (Sennrich et al.)
This paper. Adapted BPE from byte compression to text segmentation. Solved the open-vocabulary problem and became the standard tokenizer.
2016
GNMT & WordPiece (Google)
Google's Neural Machine Translation adopted WordPiece, a BPE variant that selects merges by likelihood rather than frequency. Powered Google Translate's neural upgrade.
2017
fastText subwords
Facebook's fastText used character n-grams (a simpler subword approach) for word embeddings, enabling embeddings for any word — inspired by the same open-vocabulary insight.
2018
GPT-1 adopts BPE
OpenAI's GPT-1 used BPE tokenization with ~40,000 merges. From this point, every major language model used some form of subword tokenization.
2018
SentencePiece (Kudo)
A language-agnostic tokenizer that operates on raw text without pre-tokenization, combining BPE and Unigram approaches. Used by T5, mBART, and many multilingual models.
BPE is a rare example of a paper whose contribution is not a new architecture or training objective, but a preprocessing step. That a simple data compression trick from 1994, adapted with a single key insight — use character pairs instead of byte pairs — could solve one of NMT's hardest problems speaks to the power of finding the right abstraction. The abstraction here is that the unit of translation is neither the word nor the character, but something in between: the subword. Every modern tokenizer inherits this idea.
CitationSennrich, Haddow, Birch. Neural Machine Translation of Rare Words with Subword Units. ACL, 2016.
Terms in this paper
- Byte Pair Encoding (BPE)ترميز زوج البايت
- Subword Segmentationالتجزئة دون مستوى الكلمة
- Merge Operationعملية الدمج
- Open Vocabularyالقاموس المفتوح
- Joint Vocabularyالقاموس المشترك
- Vocabulary Sizeسعة قاموس المفردات
- Out-of-Vocabulary (OOV)خارج قاموس المفردات
- WordPieceWordPiece
- SentencePieceأداة تجزئة الجمل والكلمات
- Cognateالكلمة المتشابهة بين اللغات