Byte pair encoding, implemented
BPE starts with single characters and repeatedly glues together the commonest neighbouring pair. Fifty lines of Python gives you the algorithm behind GPT's tokeniser.
- 12 min read
- 3 reading levels
- Updated
Read these first
On this page 6
One lesson, three depths. Pick the one that fits you today — you can switch any time.
Beginner — No maths. Plain English.
Byte pair encoding builds a vocabulary by repeatedly gluing together the two pieces that appear side by side most often.
Think of learning to read Hindi or Tamil as an adult. At first you sound out every letter. After a while, common letter groups start arriving as single chunks, and you stop assembling them one at a time.
Nobody handed you a list of chunks. You noticed which combinations kept turning up and started treating them as units.
BPE does that, deliberately and countably. It scans text, finds the pair of neighbours that appears most, and glues it into one piece. Then it repeats, thousands of times.
Why a model needs this at all
A model has to turn text into numbers, and it needs a fixed list of things it recognises.
One entry per word breaks fast. English has hundreds of thousands of words, plus names, typos and made-up brand names. Anything missing becomes an unknown, and the model is blind to it.
One entry per letter never breaks, and it makes every sentence enormously long. Reading "understanding" as thirteen separate steps wastes the model's attention on spelling.
BPE lands between them. Common words become single pieces. Rare words break into a handful of familiar chunks. Nothing is ever completely unknown.
How the training works
Start by splitting every word into individual characters. Then loop:
- Count every neighbouring pair across the whole text.
- Find the pair that appears most often.
- Glue that pair into one new piece, everywhere it occurs.
- Write the merge down in a list, in order.
start: l o w l o w e r n e w e s t
pair "w e" appears most -> glue it
l o w l o we r n e we s t
pair "s t" appears most -> glue it
l o w l o we r n e we st
...and so on, a few thousand timesThe list of merges, in the order they were learned, is the tokeniser. Applying it to new text means replaying those merges in the same order.
The property that makes it useful
The tokeniser learns from your text, so it fits your text. Train it on English and "ing" becomes a piece. Train it on Python code and "def " becomes a piece.
And nothing is ever unreadable. A word the trainer never saw falls back to smaller chunks, and past that to single characters.
Where you have seen this
- GPT-2, GPT-3 and GPT-4 all use a byte-level variant of BPE.
- Llama, Mistral and most open-weight models.
- Any time a model splits an unusual name into odd-looking pieces.
- The reason your token count for a paragraph is not the same as its word count.
Remember this
- Start from characters, repeatedly glue the commonest neighbouring pair.
- The ordered list of merges is the tokeniser.
- Common words become one piece; rare words become a few pieces; nothing is lost.
What to learn next
- WordPiece — the same bottom-up idea with a different scoring rule.
- Byte-level BPE — how GPT models make unknown tokens impossible.
- Tokenization — the wider picture this fits into.
Developer — Code and libraries.
Setup
python3 --versionNo libraries. BPE is short enough to write from scratch, and writing it once removes all the mystery.
Training and encoding, complete
from collections import Counter
CORPUS = ("low low low low low lower lower newest newest newest "
"newest newest newest widest widest widest new new newer")
def get_word_counts(text):
"""Every word becomes a tuple of characters, with a marker for the word end."""
return Counter(tuple(w) + ("</w>",) for w in text.split())
def count_pairs(words):
pairs = Counter()
for word, n in words.items():
for a, b in zip(word, word[1:]):
pairs[(a, b)] += n # weighted by how often the word appears
return pairs
def merge(words, pair):
a, b = pair
out = Counter()
for word, n in words.items():
new, i = [], 0
while i < len(word):
if i < len(word) - 1 and word[i] == a and word[i + 1] == b:
new.append(a + b); i += 2
else:
new.append(word[i]); i += 1
out[tuple(new)] += n
return out
words = get_word_counts(CORPUS)
print("starting words (as character tuples):")
for w, n in words.items():
print(f" {n:>2} x {' '.join(w)}")
merges = []
for step in range(10):
pairs = count_pairs(words)
if not pairs:
break
best, freq = max(pairs.items(), key=lambda kv: (kv[1], kv[0])) # ties broken by name
merges.append(best)
words = merge(words, best)
print(f"merge {step + 1:>2}: {best[0]!r} + {best[1]!r} -> {best[0] + best[1]!r}"
f" (seen {freq} times)")
print("\nwords after all merges:")
for w, n in words.items():
print(f" {n:>2} x {' '.join(w)}")
def encode(word, merges):
"""Apply the learned merges in the order they were learned. Order is the algorithm."""
parts = list(word) + ["</w>"]
for a, b in merges:
i = 0
while i < len(parts) - 1:
if parts[i] == a and parts[i + 1] == b:
parts[i:i + 2] = [a + b]
else:
i += 1
return parts
print("\nencoding words the trainer never saw:")
for w in ["lowest", "newer", "wider", "slow"]:
print(f" {w:>7} -> {encode(w, merges)}")starting words (as character tuples):
5 x l o w </w>
2 x l o w e r </w>
6 x n e w e s t </w>
3 x w i d e s t </w>
2 x n e w </w>
1 x n e w e r </w>
merge 1: 'w' + 'e' -> 'we' (seen 9 times)
merge 2: 't' + '</w>' -> 't</w>' (seen 9 times)
merge 3: 's' + 't</w>' -> 'st</w>' (seen 9 times)
merge 4: 'n' + 'e' -> 'ne' (seen 9 times)
merge 5: 'w' + '</w>' -> 'w</w>' (seen 7 times)
merge 6: 'ne' + 'we' -> 'newe' (seen 7 times)
merge 7: 'l' + 'o' -> 'lo' (seen 7 times)
merge 8: 'newe' + 'st</w>' -> 'newest</w>' (seen 6 times)
merge 9: 'lo' + 'w</w>' -> 'low</w>' (seen 5 times)
merge 10: 'w' + 'i' -> 'wi' (seen 3 times)
words after all merges:
5 x low</w>
2 x lo we r </w>
6 x newest</w>
3 x wi d e st</w>
2 x ne w</w>
1 x newe r </w>
encoding words the trainer never saw:
lowest -> ['lo', 'we', 'st</w>']
newer -> ['newe', 'r', '</w>']
wider -> ['wi', 'd', 'e', 'r', '</w>']
slow -> ['s', 'low</w>']Reading that output
Merges build on merges. Step 1 makes we. Step 4 makes ne. Step 6 combines those two into newe. Step 8 combines newe with st</w> to make the whole word. BPE grows pieces hierarchically, and the merge list encodes that hierarchy.
</w> is doing real work. Without it, the tokeniser could not tell low at the end of a word from low inside lower. Look at merge 5, which produces w</w>: that is "w, and the word stops here". Modern tokenisers mark the start of a word with a leading space instead, which is the same idea flipped.
Frequency, not length, decides. wi was merged at count 3 while single characters with higher counts sat unmerged, because merging is about pairs, not about individual pieces.
Ties are broken deterministically. Four pairs tied at 9 occurrences. The key (count, pair) breaks ties by the pair's name, so the same corpus always produces the same tokeniser. Without that, two training runs would produce different vocabularies and your outputs would not reproduce.
Now look at the four unseen words. lowest becomes lo we st</w> — three familiar chunks from a word never in the corpus. slow becomes s low</w>, reusing a whole learned word as a suffix. This is the generalisation that makes BPE worth the trouble.
wider needed five pieces, because the corpus only ever showed wid inside widest. Coverage of a word form depends entirely on what the training text contained.
The cost of encoding
The encode function above loops over every merge for every word. With 50,000 merges that is slow. Real implementations use a priority queue over merge ranks, applying the lowest-ranked applicable merge each time:
def encode_ranked(word, merges):
"""Apply the earliest-learned applicable merge, repeatedly. Same result, less work."""
rank = {pair: i for i, pair in enumerate(merges)}
parts = list(word) + ["</w>"]
while len(parts) > 1:
pairs = [(rank.get((a, b), float("inf")), i)
for i, (a, b) in enumerate(zip(parts, parts[1:]))]
best_rank, i = min(pairs)
if best_rank == float("inf"):
break # no learned merge applies
parts[i:i + 2] = [parts[i] + parts[i + 1]]
return parts
merges_demo = [("w", "e"), ("t", "</w>"), ("s", "t</w>"), ("n", "e"), ("w", "</w>"),
("ne", "we"), ("l", "o"), ("newe", "st</w>"), ("lo", "w</w>"), ("w", "i")]
for w in ["lowest", "newer", "wider", "slow"]:
print(f"{w:>7} -> {encode_ranked(w, merges_demo)}")lowest -> ['lo', 'we', 'st</w>'] newer -> ['newe', 'r', '</w>'] wider -> ['wi', 'd', 'e', 'r', '</w>'] slow -> ['s', 'low</w>']
Identical results, and the work now scales with the length of the word rather than with the size of the merge table.
Common mistakes
Applying merges in the wrong order. The merge list is ordered and the order is the algorithm. Sorting it, or applying merges by frequency at encode time, gives different tokens for the same text. A model fed those tokens produces nonsense.
Forgetting the word boundary marker. Without </w> or an equivalent, est at the end of newest and est inside establish become the same token, and the model cannot tell a suffix from a prefix.
Training the tokeniser on different text from the model. The tokeniser should be trained on a sample of the same corpus. Train it on English and pretrain on code, and your token counts and fertility will both be poor.
Assuming BPE is greedy longest-match. It is not. WordPiece is. BPE replays a fixed merge sequence, and that can produce a longer segmentation than a longest-match encoder would.
Try it yourself
Add "lowest lowest lowest" to the corpus and rerun. Watch which merge appears and at which step. Then raise the merge count from 10 to 20 and find the point where every corpus word has collapsed into a single token — that is the moment more merges stop helping, and it is the vocabulary-size question in miniature.
What to learn next
- WordPiece — the same bottom-up idea with a different scoring rule.
- Byte-level BPE — how GPT models make unknown tokens impossible.
- Tokenization — the wider picture this fits into.
Researcher — Mathematics and papers.
Origin
Byte pair encoding is a data compression algorithm from Gage (1994), which replaces the most frequent byte pair with an unused byte and records the substitution. Sennrich, Haddow and Birch (2016) adapted it for open-vocabulary neural machine translation, replacing bytes with characters and stopping after a chosen number of merges rather than compressing to exhaustion.
The adaptation flips the objective. Compression wants the shortest output. Subword tokenisation wants a fixed-size vocabulary in which rare words decompose into meaningful, reusable units.
Algorithm
Given corpus $C$ as a multiset of words with counts, and a target of $k$ merges:
- Initialise the vocabulary as the character set of $C$ plus a boundary marker.
- Represent each word as a sequence of vocabulary symbols.
- For $t = 1 \dots k$: compute $\arg\max_{(a,b)} \mathrm{count}(ab)$ over adjacent symbol pairs, weighted by word frequency; add $ab$ to the vocabulary; replace all occurrences.
- Emit the ordered merge list.
Final vocabulary size is $|\Sigma| + k$ where $\Sigma$ is the base alphabet.
Complexity
Naive retraining costs $O(k \cdot N)$ where $N$ is the total token count, since each merge rescans the corpus. The standard implementation maintains an index from pairs to their occurrence positions and a max-heap over pair counts, giving $O(N + k \log N)$ in practice. huggingface/tokenizers implements this in Rust with parallel counting.
Encoding a word of length $m$ with a rank table is $O(m^2)$ naively (scan all adjacent pairs, apply the best, repeat) and $O(m \log m)$ with a heap. Because the pre-tokeniser bounds $m$ at a word, this is effectively constant per word, which is why encoding is fast despite a 100k-entry merge table.
The greedy objective and its suboptimality
BPE's merge selection is greedy on immediate frequency, with no lookahead. It optimises no global objective. This has two consequences.
Segmentation is deterministic but not minimal. Replaying the merge sequence can yield more pieces than the shortest segmentation available in the same vocabulary. Unigram tokenisers, which score whole segmentations, do not have this property.
No probability is defined. A BPE tokeniser assigns exactly one segmentation to a string and no distribution over alternatives. Provilkov et al. (2020), BPE-Dropout, add stochasticity by randomly skipping merges during training, producing multiple segmentations of the same word and acting as a regulariser. They report BLEU gains on translation, especially in low-resource settings.
The pre-tokenisation constraint
Merges are computed within pre-token boundaries, normally whitespace-delimited words plus punctuation rules. This is not incidental: it bounds the pair-counting cost, prevents merges spanning arbitrary text, and encodes a linguistic prior that words are units.
Liu et al. (2025), SuperBPE, question the prior. They add a curriculum: phase one restricts merges within pre-tokens as usual, phase two lifts the restriction so merges may bridge whitespace, producing "superword" tokens. At 200k vocabulary they report up to 33 percent fewer tokens for the same text, an average +4.0 points across 30 downstream tasks with +8.2 on MMLU, and 27 percent less inference compute. The result is evidence that the whitespace boundary was a cost, not only a constraint.
Where BPE sits among the alternatives
| BPE | WordPiece | Unigram | |
|---|---|---|---|
| Direction | bottom-up merging | bottom-up merging | top-down pruning |
| Selection criterion | pair frequency | likelihood gain of the pair | likelihood loss from removal |
| Encoding | replay merges in order | greedy longest match | Viterbi over piece probabilities |
| Multiple segmentations | only with dropout | no | yes, natively |
Papers
- Gage, A New Algorithm for Data Compression, C Users Journal, 1994
- Sennrich, Haddow and Birch, Neural Machine Translation of Rare Words with Subword Units, ACL 2016 — arxiv.org/abs/1508.07909
- Provilkov, Emelianenko and Voita, BPE-Dropout: Simple and Effective Subword Regularization, ACL 2020 — arxiv.org/abs/1910.13267
- Liu et al., SuperBPE: Space Travel for Language Models, COLM 2025 — arxiv.org/abs/2503.13423
What to learn next
- WordPiece — the same bottom-up idea with a different scoring rule.
- Byte-level BPE — how GPT models make unknown tokens impossible.
- Tokenization — the wider picture this fits into.