Byte-pair encoding (BPE)

BPE (Sennrich, Haddow, Birch, ACL 2016) builds a subword vocabulary by repeatedly merging the most frequent adjacent symbol pair; encoding replays the merges in rank order. GPT-2's byte-level variant starts from 256 bytes, so it never emits <unk>: 256 + 50,000 merges + 1 = 50,257 tokens.

14 min read1354 wordscore0 viewsupdated 2026-10-13

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 MM merges the vocabulary has ∣B∣+M|B|+M 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

(a∗,b∗)=arg⁡max⁡(a,b) ∑w∈Dc(w)⋅#{i:si(w)=a, si+1(w)=b},Vm=Vm−1∪{a∗b∗}(a^\ast,b^\ast)=\arg\max_{(a,b)}\ \sum_{w\in\mathcal D}c(w)\cdot\#\{i: s_i(w)=a,\ s_{i+1}(w)=b\},\qquad V_{m}=V_{m-1}\cup\{a^\ast b^\ast\}
D, c(w)\mathcal D,\ c(w)
the distinct pre-tokenized words of the corpus and their counts; BPE works on this word-count table, not on the raw text
s(w)s(w)
the current segmentation of ww into symbols; initially characters (plus an end-of-word marker) or bytes
a∗b∗a^\ast b^\ast
the most frequent adjacent pair, replaced by one new symbol in every word where it occurs
VmV_m
vocabulary after mm merges: ∣Vm∣=∣B∣+m|V_m|=|B|+m. 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 ⋅\cdot, 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.

LEARN merges (once, on a corpus)ENCODE text (every input)corpus → word countspre-tokenized: low×5, lower×2, …split into base symbolschars + </w>, or 256 bytescount adjacent pairsweighted by word frequencymerge the top pair everywheree + s (9) → es; one new token|V| = target size?e.g. 32k, 50k, 100k, 200knoyesordered merge table + vocabulary: 1 e s · 2 es t · 3 est </w> · 4 l o · 5 lo w · …GPT-2: 256 byte tokens + 50,000 merges + <|endoftext|> = 50,257 ids (merges.txt + vocab.json)raw text"the lowest"pre-tokenize (regex)"the" | " lowest"split into bytest h e | Ġ l o w e s tapply merges by ranklowest-ranked pair first, repeatlook up idstokens → integers, 1 per pieceranksused inorder
fig.BPE has two separate phases. Learning (left) runs once on a corpus. It turns word counts into an ordered merge table by repeatedly merging the most frequent adjacent pair until the vocabulary reaches its target size. Encoding (right) runs on every input: pre-tokenize, split each piece into bytes, and replay the merges, always applying the lowest-ranked pair present. The merge table, with GPT-2's 50,000 merges on 256 byte tokens, is the only thing the two phases share.

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.

encode(w):s←base(w);while ∃ i: (si,si+1)∈M:  i∗=arg⁡min⁡i rank(si,si+1),  s←merge(s,si∗,si∗+1)\text{encode}(w):\quad s\leftarrow \mathrm{base}(w);\quad \textbf{while}\ \exists\,i:\ (s_i,s_{i+1})\in\mathcal M:\ \ i^\ast=\arg\min_i\ \mathrm{rank}(s_i,s_{i+1}),\ \ s\leftarrow\mathrm{merge}(s,s_{i^\ast},s_{i^\ast+1})
M\mathcal M
the learned merge table; rank 1 is the first merge learned
merge\mathrm{merge}
replace every non-overlapping occurrence of the pair, left to right
O(n2)O(n^2)
naive cost per word of nn 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 256+50,000+1=50,257256+50{,}000+1=50{,}257 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 (256256 bytes + 50,000+\,50{,}000 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_base in OpenAI's tiktoken library, about 100k tokens; GPT-4o's o200k_base has 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)
Sennrich et al. 2016, Algorithm 1 · characters + end-of-word </w> (shown ·)after 4 of 15 merges · vocab = 11 + 4 = 15 · corpus = 61 tokens (from 95)corpus: frequency × current symbols5×low·2×lower·6×newest·3×widest·pair counts → next mergelo + w7n + e6e + w6w + est·6w + ·5w + i3merge table (rank: pair → token) 1: e + s → es (9) 2: es + t → est (9) 3: est + · → est· (9) 4: l + o → lo (7)encode "lowest" with merges 1–4: apply the lowest-ranked pair present, repeatstartlowest·#1 e+slowest·#2 es+tlowest·#3 est+·lowest·#4 l+olowest·result: 3 tokens from 7 symbols (4 merges applied)
corpus
encode
fig.BPE learning and encoding, run live. The default is Sennrich et al.'s toy corpus, low×5, lower×2, newest×6 and widest×3, with an end-of-word marker shown as ·. Before any merge the corpus is 95 tokens over an 11-symbol base vocabulary. The first three merges are e+s, es+t and est+·, each with count 9. Ties go to the pair seen first, as in the paper's Python code. At the default 4 merges (l+o, count 7, is the fourth), the vocabulary has 15 symbols, the corpus is 61 tokens, and the next merge is lo+w (7). The new word lowest encodes as lo|w|est· with ranks 1–4. One more merge gives low|est·: two tokens for a word never seen in training. All 15 merges leave one token per word, 16 tokens for 16 word occurrences. Yet newer still encodes as new|e|r|·, because e+r was never learned on its own. The hug/pug/pun corpus starts at 113 tokens and stops after 7 merges at 36. There, mug has an m outside the base vocabulary and becomes <unk>. The byte-level corpus has 256 base symbols and stops after 10 merges, when no pair occurs twice. café becomes Ġc|a|f|<C3>|<A9>: é costs two byte tokens, but nothing is unknown. Note that ␣that encodes as Ġ|th|at, because the corpus merged Ġ+the directly and never learned Ġ+th.

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 ⋅\cdot). The base vocabulary is {d,e,i,l,n,o,r,s,t,w,⋅}\{d,e,i,l,n,o,r,s,t,w,\cdot\}, 11 symbols, and the corpus is 4⋅5+6⋅2+7⋅6+7⋅3=954\cdot5+6\cdot2+7\cdot6+7\cdot3=95 tokens.

rankpaircountwhere it comes fromcorpus tokens after
1e + s9newest 6 + widest 386
2es + t9newest 6 + widest 377
3est + ·9newest 6 + widest 368
4l + o7low 5 + lower 261
5lo + w7low 5 + lower 254
6n + e6newest 648
7ne + w6newest 642
8new + est·6newest 636
9low + ·5low 531
The first nine merges (counts and token totals computed in Python with the paper's tie-breaking)

Learning, then encoding new words

  1. 1Step 1 has a three-way tie at 9: (e,s)(e,s), (s,t)(s,t) and (t,⋅)(t,\cdot) each occur once in newest (6) and once in widest (3). (w,e)(w,e) scores 6+2=86+2=8, from newest and lower. The tie goes to (e,s)(e,s), the first of the three seen in corpus order. Each merge removes one token per occurrence: 95−9=8695-9=86.
  2. 2After 3 merges, est· is one token, the superlative ending shared by newest and widest. Merges 4–5 build low, which serves low and lower. These are the morpheme-like pieces BPE finds without being told about morphology.
  3. 3Encode lowest, which is not in the corpus, with the first 5 merges. Start from l o w e s t ⋅l\,o\,w\,e\,s\,t\,\cdot (7 symbols). Rank 1 gives l o w es t ⋅l\,o\,w\,es\,t\,\cdot, rank 2 gives …est ⋅\ldots est\,\cdot, rank 3 gives …est⋅\ldots est\cdot, rank 4 gives lo w est⋅lo\,w\,est\cdot, and rank 5 gives low ∣ est⋅low\,|\,est\cdot. That is 2 tokens.
  4. 4Continue to all 15 merges (rank 10 is w+iw+i, 11 is wi+dwi+d, 12 is wid+est⋅wid+est\cdot, then low+elow+e, lowe+rlowe+r and lower+⋅lower+\cdot). Every corpus word is now one token, 16 tokens in total, and the vocabulary has 11+15=2611+15=26 symbols. wider encodes as wid ∣ e ∣ r ∣ ⋅wid\,|\,e\,|\,r\,|\,\cdot and newer as new ∣ e ∣ r ∣ ⋅new\,|\,e\,|\,r\,|\,\cdot: 4 tokens each.
  5. 5Compression ratio for the corpus: 95/16=5.995/16=5.9 characters (including ⋅\cdot) per token at 15 merges, and 95/31=3.195/31=3.1 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.
python
1import re
2from collections import Counter
3
4# 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+")
6
7def 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] += f
16 if not pairs:
17 break
18 (a, b), n = pairs.most_common(1)[0] # ties: first seen wins
19 if n < 2:
20 break
21 merges.append((a, b))
22 new = Counter()
23 for w, f in words.items(): # merge (a, b) everywhere
24 out, i = [], 0
25 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 += 2
28 else:
29 out.append(w[i]); i += 1
30 new[tuple(out)] += f
31 words = new
32 return merges
33
34def 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 first
42 r, i = min((rank.get(p, 1 << 30), i) for i, p in enumerate(zip(sym, sym[1:])))
43 if r == 1 << 30:
44 break
45 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 += 2
50 else:
51 nxt.append(sym[j]); j += 1
52 sym = nxt
53 out += [ids[s] for s in sym]
54 return out, vocab
55
56corpus = "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é mat
Byte-level BPE from scratch: learn merges on a toy corpus and encode new text losslessly (pure Python; run with CPython 3.10, outputs as printed)

Use 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, arg⁡max⁡(a,b)∑wc(w) #(a,b∈w)\arg\max_{(a,b)}\sum_w c(w)\,\#(a,b\in w); vocabulary =∣B∣+M=|B|+M after MM 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: 256+50,000+1=50,257256+50{,}000+1=50{,}257 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.
← back to Deep Learning roadmap