Definition
Byte-pair encoding (BPE) is a subword tokenization algorithm. It starts from a base vocabulary of single symbols (characters, or the 256 byte values) and learns an ordered list of merges: at each step it counts every adjacent pair of symbols in the training corpus, weighted by word frequency, and replaces the most frequent pair with a new symbol. After merges the vocabulary has entries. To encode new text, it splits each word into base symbols and replays the learned merges in the order they were learned. The idea is Philip Gage's compression algorithm ("A New Algorithm for Data Compression", 1994). Rico Sennrich, Barry Haddow and Alexandra Birch adapted it to word segmentation in "Neural Machine Translation of Rare Words with Subword Units" (ACL 2016). Radford et al. made it byte-level for GPT-2 (2019).
Tokenization algorithms laid out the problem. A word vocabulary cannot cover rare words, names and typos, and characters make sequences long. Before 2016, neural translation systems kept a fixed list of 30k–80k words and mapped everything else to an unknown token. They then patched the output with a back-off dictionary that copied or translated the rare source word. Sennrich et al. argued that many rare words can be translated piece by piece. Names can be copied or transliterated by character, compounds split into parts (German Abwasserbehandlungsanlage), and cognates and loanwords follow regular sound rules. A fixed-size vocabulary of variable-length pieces makes this possible. Frequent words stay whole and rare ones break into known parts.
Gage's original algorithm compressed data. It replaced the most common pair of bytes with a byte value that did not occur in the data, and repeated until no pair occurred more than once or no unused bytes were left. Sennrich et al. kept the greedy pair-merging but changed two things. They do not merge across word boundaries, and they stop after a chosen number of merges, which sets the vocabulary size. Their results on WMT 2015 English→German and English→Russian improved over the back-off dictionary baseline by up to 1.1 and 1.3 BLEU.
Learning the merges
- the distinct pre-tokenized words of the corpus and their counts; BPE works on this word-count table, not on the raw text
- the current segmentation of into symbols; initially characters (plus an end-of-word marker) or bytes
- the most frequent adjacent pair, replaced by one new symbol in every word where it occurs
- vocabulary after merges: . the final vocabulary size is the initial vocabulary plus the number of merges, which is the only hyperparameter
The procedure is greedy and deterministic. It never revisits a merge, and the order of the merge list is part of the model. Sennrich et al. append an end-of-word symbol, written </w> or , before counting. A piece then knows whether it ends a word: est</w> in newest and widest is a different token from est in estimate. Without the marker you cannot tell where words end in the output. Byte-level BPE moves the boundary to the front instead, attaching the leading space to the word.
Encoding: replaying merges by rank
Encoding new text does not count pairs again. Each word is split into base symbols. Then, among the adjacent pairs of the word, find the one that was learned earliest (lowest rank), merge it, and repeat until no pair is in the table. This gives the same segmentation that the training corpus would have had if the word had been in it. A word that never appeared still gets a segmentation, made from pieces that did.
- the learned merge table; rank 1 is the first merge learned
- replace every non-overlapping occurrence of the pair, left to right
- naive cost per word of symbols; production encoders cache per word and use heaps or linked lists
Learning and encoding differ in one important way. Learning picks the pair that is most frequent now, given the current segmentation. Encoding applies merges in the fixed learned order, whatever the new word's own pair counts are. Sennrich's toy corpus shows the effect. The vocabulary ends up with lower</w> as one token because lower was in the corpus. But e r was never merged on its own, since the er in lower was absorbed by the merges low e and lowe r. A new word like newer therefore encodes as new e r </w>, four tokens.
Byte-level BPE (GPT-2)
A character base vocabulary has a gap. Unicode has about 150,000 assigned characters, and any character missing from the base becomes <unk>. Byte-level BPE runs on the UTF-8 bytes instead, so the base vocabulary is exactly 256 symbols and every string is encodable. The é in café is two bytes, C3 A9. If the merges never joined them, it costs two tokens, but it is never unknown. GPT-2 used 50,000 merges on this base, plus one special <|endoftext|> token, for entries.
Two engineering details matter. First, pure byte-level BPE wastes merges on variants like dog., dog! and dog?. GPT-2 therefore pre-tokenizes with a regex that splits text into runs of letters, runs of digits, runs of other symbols, and whitespace. English contractions ('s, 't, 're, 've, 'm, 'll, 'd) are split off, and a single leading space is kept with the following word. Merges never cross these splits. Second, the merge files store tokens as text, so GPT-2 maps each of the 256 bytes to a printable Unicode character. The space byte 0x20 is shown as Ġ, which is why GPT-2 vocabularies are full of tokens like Ġthe.
BPE vocabularies in real models
- Sennrich et al. 2016
- character BPE with
</w>, trained on the source and target separately or jointly ("joint BPE", which keeps transliterations consistent); WMT15 En→De and En→Ru - GPT-2 / GPT-3
- byte-level BPE, 50,257 tokens ( bytes merges
<|endoftext|>), regex pre-tokenization; GPT-3 reused the same tokenizer - RoBERTa
- GPT-2's byte-level BPE with 50K units, replacing BERT's 30K WordPiece vocabulary
- GPT-3.5 / GPT-4
cl100k_basein OpenAI's tiktoken library, about 100k tokens; GPT-4o'so200k_basehas about 200k- Llama 1 / Llama 2
- BPE trained with SentencePiece, 32,000 tokens, digits split into single characters, and byte fallback for unknown UTF-8 characters
- Llama 3
- a tiktoken-based BPE with 128K tokens (128,256 including special tokens)
Worked example: Sennrich's corpus by hand
Take the word counts from the paper's Algorithm 1: low 5, lower 2, newest 6, widest 3. Split them into characters plus </w> (written ). The base vocabulary is , 11 symbols, and the corpus is tokens.
| rank | pair | count | where it comes from | corpus tokens after |
|---|---|---|---|---|
| 1 | e + s | 9 | newest 6 + widest 3 | 86 |
| 2 | es + t | 9 | newest 6 + widest 3 | 77 |
| 3 | est + · | 9 | newest 6 + widest 3 | 68 |
| 4 | l + o | 7 | low 5 + lower 2 | 61 |
| 5 | lo + w | 7 | low 5 + lower 2 | 54 |
| 6 | n + e | 6 | newest 6 | 48 |
| 7 | ne + w | 6 | newest 6 | 42 |
| 8 | new + est· | 6 | newest 6 | 36 |
| 9 | low + · | 5 | low 5 | 31 |
Learning, then encoding new words
- 1Step 1 has a three-way tie at 9: , and each occur once in newest (6) and once in widest (3). scores , from newest and lower. The tie goes to , the first of the three seen in corpus order. Each merge removes one token per occurrence: .
- 2After 3 merges,
est·is one token, the superlative ending shared by newest and widest. Merges 4–5 buildlow, which serves low and lower. These are the morpheme-like pieces BPE finds without being told about morphology. - 3Encode lowest, which is not in the corpus, with the first 5 merges. Start from (7 symbols). Rank 1 gives , rank 2 gives , rank 3 gives , rank 4 gives , and rank 5 gives . That is 2 tokens.
- 4Continue to all 15 merges (rank 10 is , 11 is , 12 is , then , and ). Every corpus word is now one token, 16 tokens in total, and the vocabulary has symbols. wider encodes as and newer as : 4 tokens each.
- 5Compression ratio for the corpus: characters (including ) per token at 15 merges, and at 9 merges. Real tokenizers on English land near 4 characters per token at 50k–100k vocabularies, because real corpora have long tails that no affordable vocabulary covers.
1import re2from collections import Counter34# GPT-2's pre-tokenizer splits on letter/number/punctuation runs; a stdlib-only approximation:5PAT = re.compile(r"'(?:s|t|re|ve|m|ll|d)| ?[^\W\d_]+| ?\d+| ?[^\s\w]+|\s+(?!\S)|\s+")67def train_bpe(text, n_merges):8 """Byte-level BPE: base vocab = 256 bytes; returns the ordered merge list."""9 words = Counter(tuple(bytes([b]) for b in w.encode("utf-8")) for w in PAT.findall(text))10 merges = []11 for _ in range(n_merges):12 pairs = Counter()13 for w, f in words.items():14 for a, b in zip(w, w[1:]):15 pairs[a, b] += f16 if not pairs:17 break18 (a, b), n = pairs.most_common(1)[0] # ties: first seen wins19 if n < 2:20 break21 merges.append((a, b))22 new = Counter()23 for w, f in words.items(): # merge (a, b) everywhere24 out, i = [], 025 while i < len(w):26 if i + 1 < len(w) and w[i] == a and w[i + 1] == b:27 out.append(a + b); i += 228 else:29 out.append(w[i]); i += 130 new[tuple(out)] += f31 words = new32 return merges3334def encode(text, merges):35 rank = {p: i for i, p in enumerate(merges)}36 vocab = [bytes([i]) for i in range(256)] + [a + b for a, b in merges]37 ids = {tok: i for i, tok in enumerate(vocab)}38 out = []39 for w in PAT.findall(text):40 sym = [bytes([b]) for b in w.encode("utf-8")]41 while len(sym) > 1: # lowest-ranked pair first42 r, i = min((rank.get(p, 1 << 30), i) for i, p in enumerate(zip(sym, sym[1:])))43 if r == 1 << 30:44 break45 a, b = sym[i], sym[i + 1]46 j, nxt = 0, []47 while j < len(sym):48 if j + 1 < len(sym) and sym[j] == a and sym[j + 1] == b:49 nxt.append(a + b); j += 250 else:51 nxt.append(sym[j]); j += 152 sym = nxt53 out += [ids[s] for s in sym]54 return out, vocab5556corpus = "the cat sat on the mat the fat cat ate the rat that sat on the hat"57merges = train_bpe(corpus, 20)58print(len(merges), [(a + b).decode() for a, b in merges])59# 10 ['at', 'th', 'the', ' the', ' c', ' cat', ' s', ' sat', ' o', ' on']60ids, vocab = encode("the cats sat on a café mat", merges)61print(len(ids), [vocab[i] for i in ids])62# 15 [b'the', b' cat', b's', b' sat', b' on', b' ', b'a', b' c', b'a', b'f', b'\xc3', b'\xa9', b' ', b'm', b'at']63print(b"".join(vocab[i] for i in ids).decode("utf-8")) # the cats sat on a café matUse when
- +Simple, fast and deterministic: counting and merging, with no probabilistic model
- +Vocabulary size is an exact knob: base + number of merges
- +Byte-level BPE encodes any string with no unknown token and decodes losslessly
- +Finds frequent words and morpheme-like affixes (est·, low) without linguistic rules
Avoid when
- −Greedy: an early merge can block a better segmentation later (newer → new|e|r|·)
- −Segmentation reflects the training mix, so under-represented languages and code need more tokens per word
- −Byte-level tokens can split a multi-byte character, so a single token may not be valid UTF-8
- −Training cost grows with corpus size times merges unless pair counts are updated incrementally
Check yourself
After learning merges on low×5, lower×2, newest×6, widest×3, why does the new word 'lowest' encode as low|est· rather than character by character?
Check yourself
Why does GPT-2's byte-level BPE never need an <unk> token?
Remember
- ✓Learning: repeatedly merge the most frequent adjacent pair, ; vocabulary after merges.
- ✓Encoding: split into base symbols, then repeatedly apply the lowest-ranked learned merge present; the merge order is part of the tokenizer.
- ✓Sennrich, Haddow, Birch (ACL 2016) brought Gage's 1994 compression algorithm to NMT; GPT-2 made it byte-level: tokens.
- ✓Byte-level BPE has no unknown tokens; regex pre-tokenization keeps merges within words, digit runs and punctuation runs.
- ✓Each merge of a count-n pair shortens the corpus by n tokens: BPE is a greedy compressor, so frequent languages and domains get shorter encodings.