Byte-Pair Encoding (BPE)Open in Colab

Byte-Pair Encoding (BPE)

BPE, used by GPT and many modern models, builds a subword vocabulary by iteratively merging the most frequent adjacent symbol pair. It solves the out-of-vocabulary problem: common words become single tokens, rare words decompose into known subword pieces — nothing maps to [UNK].

The algorithm, step by step

  1. Split every training word into characters plus a special end-of-word marker </w>: "low" → ["l","o","w","</w>"].
  2. Start with the character vocabulary (every unique character is a token).
  3. Count the frequency of every adjacent pair across all word representations, weighted by word frequency.
  4. Find the most frequent pair (a,b)(a, b).
  5. Merge all occurrences of (a,b)(a, b) into the new symbol abab in every word.
  6. Add abab to the vocabulary.
  7. Repeat steps 3–6 until the vocabulary reaches the target size (e.g. 50 000 tokens).

The learned merge list (the ordered sequence of pairs) is the tokenizer: to tokenize new text, apply the same merges in the same order.

Watch it run

Training corpus: "low"×5, "lower"×2, "newest"×6. Step through four merges being learned, then watch the learned merge list tokenize "lowest" — a word that never appears in the corpus. The code panel highlights the line executing at each step.

BPE — learning the merge list, then tokenizing an unseen word

1/20

Split every training word into characters plus the end-of-word marker </w>. The starting vocabulary is just the distinct characters — no subwords learned yet.

python
1corpus = {"low": 5, "lower": 2, "newest": 6}
2vocab = {tuple(w) + ("</w>",): f for w, f in corpus.items()}
3merges = []
4
5def get_pairs(vocab):
6 pairs = {}
7 for sym, freq in vocab.items():
8 for i in range(len(sym) - 1):
9 pair = (sym[i], sym[i + 1])
10 pairs[pair] = pairs.get(pair, 0) + freq
11 return pairs
12
13for _ in range(NUM_MERGES):
14 pairs = get_pairs(vocab)
15 if not pairs:
16 break
17 # ties broken by first seen
18 best = max(pairs, key=pairs.get)
19 vocab = {merge(sym, best): f
20 for sym, f in vocab.items()}
21 merges.append(best)
22
23def encode(word, merges):
24 sym = list(word) + ["</w>"]
25 for pair in merges: # same order as learned
26 sym = merge(sym, pair)
27 return sym
28
29# a word never seen in training
30encode("lowest", merges)
state
"low" ×5
l
o
w
</w>
"lower" ×2
l
o
w
e
r
</w>
"newest" ×6
n
e
w
e
s
t
</w>
merge list (0)
empty

Step through the two halves of BPE. Training (steps 1–14): count adjacent pairs, merge the most frequent, repeat — the ordered merge list is the whole tokenizer. Inference (steps 15–20): replay those same merges, in the same order, on "lowest" — a word absent from the corpus — and watch it decompose into learned subwords instead of falling back to [UNK].

Three things to notice as you step:

  1. Frequency is the entire selection rule. The first merge is (w, e) with count 8 — not because "we" is meaningful, but because that pair happens to be the commonest. Meaningful subwords emerge as a side effect of frequency.
  2. Words without the winning pair are untouched. "low" sits out merge 1 entirely; each merge only rewrites the words that contain the pair.
  3. The merge list is ordered, and the order is load-bearing. At inference the rules replay in the order they were learned — apply them in a different order and you get different tokens for the same string.

Result: the vocabulary learns reusable subwords. "lowest" was never in the corpus, yet it tokenizes to ["lo", "we", "s", "t", "</w>"] with no [UNK] — the same mechanism that turns "unhappiness" into ["un", "happi", "ness"].

Implementation from scratch

Python
vocab = {" ".join(word) + " </w>": freq
         for word, freq in [("low", 5), ("lower", 2), ("newest", 6)]}

def get_pairs(vocab):
    pairs = {}
    for word, freq in vocab.items():
        symbols = word.split()
        for i in range(len(symbols) - 1):
            pair = (symbols[i], symbols[i+1])
            pairs[pair] = pairs.get(pair, 0) + freq
    return pairs

def merge_vocab(pair, vocab):
    new_vocab = {}
    bigram = " ".join(pair)
    replacement = "".join(pair)
    for word, freq in vocab.items():
        new_word = word.replace(bigram, replacement)
        new_vocab[new_word] = freq
    return new_vocab

num_merges = 10
for _ in range(num_merges):
    pairs = get_pairs(vocab)
    if not pairs:
        break
    best = max(pairs, key=pairs.get)
    vocab = merge_vocab(best, vocab)
    print(f"Merged {best} → {''.join(best)}")

Main variants

WordPiece (used by BERT) is similar but merges based on language-model likelihood improvement rather than raw frequency, producing tokens prefixed with ## for word-continuation: "unhappiness" → ["un", "##happi", "##ness"].

Byte-level BPE (GPT-2 onwards) operates on raw bytes instead of Unicode characters — the base vocabulary is exactly 256 symbols and any string is representable, including emoji and arbitrary Unicode.

Vocabulary size trade-off

Bigger vocabulary → shorter sequences (fewer tokens per sentence) but a larger embedding matrix and rarer token updates. GPT-2 used 50 257 tokens; modern LLMs typically use 32k–128k.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Referenced by
Byte-Pair Encoding (BPE)Text PreprocessingWord Embeddings