# 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.

Source: https://www.mlfoundry.in/learn/byte-pair-encoding-bpe  
Section: Deep Learning › Large Language Models (LLMs)  
Level: core · 14 min read · updated 2026-10-13

**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 $M$ merges the vocabulary has $|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^\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\}
$$

- $\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)$: the current segmentation of $w$ into symbols; initially characters (plus an end-of-word marker) or bytes
- $a^\ast b^\ast$: the most frequent adjacent pair, replaced by one new symbol in every word where it occurs
- $V_m$: vocabulary after $m$ merges: $|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.

> Figure: 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.

$$
\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})
$$

- $\mathcal M$: the learned merge table; rank 1 is the first merge learned
- $\mathrm{merge}$: replace every non-overlapping occurrence of the pair, left to right
- $O(n^2)$: naive cost per word of $n$ 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{,}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 ($256$ bytes $+\,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)

> Figure: 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,\cdot\}$, 11 symbols, and the corpus is $4\cdot5+6\cdot2+7\cdot6+7\cdot3=95$ tokens.

The first nine merges (counts and token totals computed in Python with the paper's tie-breaking)

| 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**

1. Step 1 has a three-way tie at 9: $(e,s)$, $(s,t)$ and $(t,\cdot)$ each occur once in *newest* (6) and once in *widest* (3). $(w,e)$ scores $6+2=8$, from *newest* and *lower*. The tie goes to $(e,s)$, the first of the three seen in corpus order. Each merge removes one token per occurrence: $95-9=86$.
2. After 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. Encode *lowest*, which is not in the corpus, with the first 5 merges. Start from $l\,o\,w\,e\,s\,t\,\cdot$ (7 symbols). Rank 1 gives $l\,o\,w\,es\,t\,\cdot$, rank 2 gives $\ldots est\,\cdot$, rank 3 gives $\ldots est\cdot$, rank 4 gives $lo\,w\,est\cdot$, and rank 5 gives **$low\,|\,est\cdot$**. That is 2 tokens.
4. Continue to all 15 merges (rank 10 is $w+i$, 11 is $wi+d$, 12 is $wid+est\cdot$, then $low+e$, $lowe+r$ and $lower+\cdot$). Every corpus word is now one token, 16 tokens in total, and the vocabulary has $11+15=26$ symbols. *wider* encodes as $wid\,|\,e\,|\,r\,|\,\cdot$ and *newer* as $new\,|\,e\,|\,r\,|\,\cdot$: 4 tokens each.
5. Compression ratio for the corpus: $95/16=5.9$ characters (including $\cdot$) per token at 15 merges, and $95/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
import re
from collections import Counter

# GPT-2's pre-tokenizer splits on letter/number/punctuation runs; a stdlib-only approximation:
PAT = re.compile(r"'(?:s|t|re|ve|m|ll|d)| ?[^\W\d_]+| ?\d+| ?[^\s\w]+|\s+(?!\S)|\s+")

def train_bpe(text, n_merges):
    """Byte-level BPE: base vocab = 256 bytes; returns the ordered merge list."""
    words = Counter(tuple(bytes([b]) for b in w.encode("utf-8")) for w in PAT.findall(text))
    merges = []
    for _ in range(n_merges):
        pairs = Counter()
        for w, f in words.items():
            for a, b in zip(w, w[1:]):
                pairs[a, b] += f
        if not pairs:
            break
        (a, b), n = pairs.most_common(1)[0]          # ties: first seen wins
        if n < 2:
            break
        merges.append((a, b))
        new = Counter()
        for w, f in words.items():                   # merge (a, b) everywhere
            out, i = [], 0
            while i < len(w):
                if i + 1 < len(w) and w[i] == a and w[i + 1] == b:
                    out.append(a + b); i += 2
                else:
                    out.append(w[i]); i += 1
            new[tuple(out)] += f
        words = new
    return merges

def encode(text, merges):
    rank = {p: i for i, p in enumerate(merges)}
    vocab = [bytes([i]) for i in range(256)] + [a + b for a, b in merges]
    ids = {tok: i for i, tok in enumerate(vocab)}
    out = []
    for w in PAT.findall(text):
        sym = [bytes([b]) for b in w.encode("utf-8")]
        while len(sym) > 1:                          # lowest-ranked pair first
            r, i = min((rank.get(p, 1 << 30), i) for i, p in enumerate(zip(sym, sym[1:])))
            if r == 1 << 30:
                break
            a, b = sym[i], sym[i + 1]
            j, nxt = 0, []
            while j < len(sym):
                if j + 1 < len(sym) and sym[j] == a and sym[j + 1] == b:
                    nxt.append(a + b); j += 2
                else:
                    nxt.append(sym[j]); j += 1
            sym = nxt
        out += [ids[s] for s in sym]
    return out, vocab

corpus = "the cat sat on the mat the fat cat ate the rat that sat on the hat"
merges = train_bpe(corpus, 20)
print(len(merges), [(a + b).decode() for a, b in merges])
# 10 ['at', 'th', 'the', ' the', ' c', ' cat', ' s', ' sat', ' o', ' on']
ids, vocab = encode("the cats sat on a café mat", merges)
print(len(ids), [vocab[i] for i in ids])
# 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']
print(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)

> **Merge order is part of the model:** A BPE tokenizer is the vocabulary **and** the ordered merge list. If you rebuild it from the vocabulary alone, for example by greedy longest-match as in **WordPiece**, some words will segment differently from training and the model sees token sequences it was never trained on. The same applies to pre-tokenization, normalization and the leading-space convention: `"the"` and `" the"` are different tokens in GPT-2. A prompt that ends with a trailing space produces a token the model rarely saw in that position.

> **Frequency is a proxy for compression:** Each merge of a pair with count $n$ shortens the training corpus by exactly $n$ tokens. Greedy BPE is therefore a greedy compressor: every step makes the largest possible one-step reduction in corpus length. That is why its vocabularies favour frequent words and common affixes, and why it serves languages and domains that are rare in the training mix poorly. Their text gets few merges, so it needs more tokens per word.

> **BPE is deterministic; BPE-dropout is not:** Standard BPE gives one segmentation per word. Provilkov, Emelianenko and Voita ("BPE-Dropout", ACL 2020) randomly skip merges during training-time encoding, so the model sees several segmentations of the same word and becomes more robust to rare words and typos. At test time they encode normally. The same idea in **Unigram tokenization** is subword regularization (Kudo, 2018).

**Strengths**

- 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

**Limitations**

- 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

**Question:** 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?

- A. BPE looks up 'lowest' in a dictionary of known words
- B. Encoding replays the learned merges in rank order, and e+s, es+t, est+·, l+o, lo+w all apply to the new word
- C. Encoding re-counts pairs inside 'lowest' and merges its most frequent pair
- D. The end-of-word marker forces a split before 'est'

**Answer:** B. Encoding replays the learned merges in rank order, and e+s, es+t, est+·, l+o, lo+w all apply to the new word — Encoding never counts pairs. It applies the learned merges by rank. The first five merges all match pairs inside *lowest*, so after them it is `low` + `est·`, two tokens built from pieces learned on *low*, *lower*, *newest* and *widest*.

**Question:** Why does GPT-2's byte-level BPE never need an <unk> token?

- A. Its 50,000 merges cover every Unicode character
- B. Its base vocabulary is the 256 byte values, and every string is a sequence of UTF-8 bytes
- C. It maps unknown characters to the nearest known one
- D. It falls back to WordPiece for rare words

**Answer:** B. Its base vocabulary is the 256 byte values, and every string is a sequence of UTF-8 bytes — Any text is a byte sequence, and every byte is a base token. A rare character costs one token per byte if no merge joined its bytes (two for é, three for a CJK ideograph), but it is always representable. Llama 1 and 2 get a similar guarantee from SentencePiece's byte fallback on top of a character-level vocabulary.

**Key points**

- Learning: repeatedly merge the most frequent adjacent pair, $\arg\max_{(a,b)}\sum_w c(w)\,\#(a,b\in w)$; vocabulary $=|B|+M$ after $M$ 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{,}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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
