Byte Pair Encoding › The BPE Algorithm
Language AI HandbookAll chapters Byte Pair Encoding › The BPE AlgorithmOne section · Sections in this chapter3 / 14 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
BPE has two distinct phases: training (learning merge rules from a corpus) and encoding (applying those rules to new text). These phases are conceptually separate and use different procedures. Training reads the entire corpus and learns statistical patterns. Encoding applies those learned patterns to individual strings, one at a time. Let us trace through each carefully.
The full algorithm can be described in a few sentences, but each step has subtleties that matter in practice. Training starts by splitting every word in the corpus into characters, counting how often adjacent character pairs appear, merging the most frequent pair everywhere it occurs, and repeating. Encoding starts with a character-split word and replays the learned merge rules in order. Decoding simply concatenates the tokens back into a string.
Understanding where edge cases arise, particularly around word boundaries, merge ordering, and out-of-vocabulary characters, requires working through concrete examples. We will do that in detail in the worked example section after covering the algorithm itself.
Step 1: Initialize with Characters
Training starts by splitting every word in the corpus into individual characters. A special end-of-word marker (commonly </w>) is appended to each word. This marker serves a critical purpose: it lets BPE distinguish between the substring "est" inside "estimated" and the standalone suffix "est" at the end of "smallest". Without word boundaries, merges can bleed across word edges in ways that corrupt the vocabulary.
The initial vocabulary is the set of all unique characters that appear in the training corpus, plus the </w> symbol. For ASCII English text, this is roughly 60-70 tokens. For Unicode corpora covering hundreds of languages, it may be thousands. Character-level coverage is the foundation of BPE's guarantee that any input can always be tokenized: as long as every character that ever appears in new text appeared at least once in training, the vocabulary can represent it.
def build_initial_vocab(corpus):
"""Split each word into characters and add </w> end-of-word marker."""
word_freqs = {}
for text in corpus:
for word in text.lower().split():
# Represent each word as space-separated characters with </w> at end
char_repr = " ".join(list(word)) + " </w>"
word_freqs[char_repr] = word_freqs.get(char_repr, 0) + 1
return word_freqs
# A small training corpus to trace the algorithm
corpus = [
"low lower lowest",
"new newer newest",
"low new low new",
"the newest lower new low",
]
word_freqs = build_initial_vocab(corpus)Initial character-level representation: ------------------------------------------------------------ l o w </w> freq=4 n e w </w> freq=4 l o w e r </w> freq=2 n e w e s t </w> freq=2 l o w e s t </w> freq=1 n e w e r </w> freq=1 t h e </w> freq=1
Each word is now represented as a sequence of character tokens separated by spaces. The </w> marker appears as a distinct token. Notice that "low" (freq=4) and "new" (freq=4) both appear frequently because they recur across multiple sentences. This frequency weighting is important: every adjacent pair in a word that appears four times contributes four to the pair count. Words that appear more often exert proportionally more influence on which merges happen first.
Step 2: Count Adjacent Pairs
With the corpus represented as character sequences, the algorithm counts how many times each adjacent pair of tokens co-occurs across all word occurrences. If a word appears 4 times in the corpus, each of its adjacent pairs contributes 4 to the count. This weighting by word frequency means the pair counts reflect how often each pattern appears in running text, not just how many word types contain that pattern.
The counting step is the computational heart of BPE training. For large corpora, this step must be performed efficiently because it runs once per merge iteration and there may be tens of thousands of iterations. In practice, optimized implementations maintain a priority queue of pair frequencies rather than recomputing counts from scratch each iteration, updating only the entries affected by the most recent merge.
def count_pairs(word_freqs):
"""Count frequency of all adjacent token pairs, weighted by word frequency."""
pairs = {}
for word, freq in word_freqs.items():
tokens = word.split()
for i in range(len(tokens) - 1):
pair = (tokens[i], tokens[i + 1])
pairs[pair] = pairs.get(pair, 0) + freq
return pairs
pairs = count_pairs(word_freqs)Top 10 adjacent pair frequencies:
---------------------------------------------
w + </w> → 8
l + o → 7
o + w → 7
n + e → 7
e + w → 7
w + e → 6
e + r → 3
r + </w> → 3
e + s → 3
s + t → 3
Best pair to merge: ('w', '</w>') (frequency 8)The pair with the highest count wins the first merge. With our small corpus, you will likely see ('e', 'w') at the top because it appears in every occurrence of "new", "newer", and "newest", accumulating a high count. This is a good example of how BPE discovers morphological structure: "ew" is part of a productive root ("new") that appears across many word forms, so the algorithm merges it early.
Step 3: Merge the Best Pair
The winning pair is merged into a single token everywhere it appears. The merge rule is recorded in an ordered list, which will be replayed later during encoding. This is important: the order matters. If you learned "e w" before "ew s", you must apply those rules in the same sequence when encoding new text. The ordering is not arbitrary but reflects the dependency structure of the merges: later rules often depend on tokens created by earlier rules.
The merge operation itself is a simple string replacement on the space-separated token representation. Every occurrence of the space-delimited bigram "(a) (b)" becomes the single token "ab". The total number of tokens in the corpus decreases by exactly the frequency of the merged pair.
def merge_pair(word_freqs, pair):
"""Replace all occurrences of (pair[0], pair[1]) with a merged token."""
merged = pair[0] + pair[1]
new_word_freqs = {}
for word, freq in word_freqs.items():
# Replace the bigram with the merged token in the space-separated repr
new_word = word.replace(f"{pair[0]} {pair[1]}", merged)
new_word_freqs[new_word] = freq
return new_word_freqs
# Perform the first merge
best_pair = max(pairs.items(), key=lambda x: x[1])[0]
word_freqs_after = merge_pair(word_freqs, best_pair)
merge_rules = [best_pair]Merged pair: w + </w> → w</w> Vocabulary after first merge: ------------------------------------------------------------ l o w</w> freq=4 n e w</w> freq=4 l o w e r </w> freq=2 n e w e s t </w> freq=2 l o w e s t </w> freq=1 n e w e r </w> freq=1 t h e </w> freq=1
After the merge, every occurrence of the old bigram has been replaced by a single token. The total number of tokens in the corpus decreases by one for each occurrence of the merged pair. BPE is a compression algorithm: each merge reduces the total length of the encoded corpus. The merge operation is also why the algorithm is fast to implement: it requires only string operations on the space-separated word representations, not any complex data structure manipulation.
Step 4: Repeat Until Target Vocabulary Size
The algorithm repeats steps 2 and 3 until the vocabulary reaches the desired size. If we start with unique characters and want a vocabulary of size , we perform exactly merges. Each merge adds exactly one new token to the vocabulary (the merged bigram becomes a new type), so the number of merges maps directly to the vocabulary size increase.
The stopping condition is simple but consequential. If you stop too early, with too few merges, the vocabulary will be small and sequences will be long, requiring many tokens to represent each word. If you stop too late, with too many merges, the vocabulary grows large with tokens that appear rarely in training data and may not transfer well to new text. Finding the right stopping point is the primary hyperparameter decision in BPE, and we will discuss it in depth in the vocabulary size section.
def train_bpe(corpus, num_merges):
"""Train BPE and return merge rules and final word representations."""
word_freqs = build_initial_vocab(corpus)
merge_rules = []
for step in range(num_merges):
pairs = count_pairs(word_freqs)
if not pairs:
break
best_pair = max(pairs.items(), key=lambda x: x[1])[0]
merge_rules.append(best_pair)
word_freqs = merge_pair(word_freqs, best_pair)
return merge_rules, word_freqs
merge_rules, final_word_freqs = train_bpe(corpus, num_merges=12)Learned merge rules (in order of discovery): --------------------------------------------- Rule 1: w + </w> → w</w> Rule 2: l + o → lo Rule 3: n + e → ne Rule 4: w + e → we Rule 5: lo + w</w> → low</w> Rule 6: ne + w</w> → new</w> Rule 7: lo + we → lowe Rule 8: r + </w> → r</w> Rule 9: s + t → st Rule 10: st + </w> → st</w> Rule 11: ne + we → newe Rule 12: lowe + r</w> → lower</w> Final vocabulary representation: ------------------------------------------------------------ low</w> freq=4 new</w> freq=4 lower</w> freq=2 newe st</w> freq=2 lowe st</w> freq=1 newe r</w> freq=1 t h e </w> freq=1
The merge rules reveal meaningful linguistic patterns. The algorithm discovers that common character combinations like "ew", "lo", "ow" appear frequently in our small corpus and merges them early. With more training data, it would discover suffixes like "ing", "tion", "er", and "est" as stable patterns. The fact that these linguistically meaningful units emerge without any explicit linguistic knowledge is one of BPE's most elegant properties.
Visualizing Training Dynamics
Two properties of BPE training are worth seeing directly. First, pair frequencies follow a Zipf-like distribution: a few pairs are very common while most are rare. Second, each merge reduces the total token count in the corpus, and the rate of reduction decreases over time as less-frequent pairs are targeted. Both of these properties have practical implications for how you configure BPE training.
The Zipf-like distribution of pair frequencies is important because it tells you that the first merges provide much more compression benefit than later merges. Roughly speaking, doubling the number of merges does not double the compression: early merges capture highly frequent patterns, while later merges target increasingly specialized patterns. This is why small vocabulary sizes, achieved with fewer merges, are surprisingly effective: the first few hundred merges capture the bulk of the linguistic structure in the corpus.
The left chart confirms the Zipf-like shape: the top three pairs (shown in red) are much more frequent than the rest. This is why greedy selection works well in practice. By capturing the most common pattern first, BPE maximizes compression gain at every step.
The right chart shows the compression payoff. The curve is steepest at the start, when high-frequency pairs are being merged, and flattens out as the algorithm moves to less common pairs. This diminishing-returns behavior is typical and helps practitioners decide when to stop training: once the curve flattens significantly, additional merges provide minimal compression benefit and the vocabulary grows with increasingly rare tokens.