Byte-pair encoding

Byte-pair encoding (BPE) builds a vocabulary by greedy merges. Start from a small alphabet, count adjacent pairs in the corpus, and repeatedly fuse the most frequent pair into a new symbol until you hit a target size. Encoding a new string applies those learned merges in order.

The big idea

1. Start with a base alphabet. Byte-level BPE starts from 256 bytes.
2. Count adjacent symbol pairs in the training corpus (after a pre-tokenizer splits on spaces and punctuation).
3. Merge the most frequent pair into a new symbol. Add it to the vocab.
4. Repeat until you hit target size V (for example 50,257 for GPT-2 including specials).

Classic BPE on Unicode characters struggles with large character sets and leftovers. GPT-2 maps raw UTF-8 bytes to 256 base tokens, then learns merges. Any emoji, CJK character or binary-ish junk still encodes. Decoding must reverse bytes carefully (the famous GPT-2 unicode escape mapping in the vocab file).

Walking through a toy corpus

Toy corpus, pretending characters are already base symbols: aaabdaaabac.

• Pair counts: aa appears most → merge aa → A.
• Corpus becomes AabdAabac. Next frequent merge might be ab → B, and so on.
• After a few merges, common chunks are single tokens. Leftovers stay as short pieces.

Real trainers run this on billions of tokens of text. The rule is identical: frequent neighbors coalesce.

After merges are learned, encoding uses an ordered list (a,b) → new_id:

1. UTF-8 encode → bytes → base ids 0…255.
2. Repeatedly find the pair in the current id sequence that appears earliest in the merge list, merge it, until no known pair remains.
3. Map special tokens in a pre-pass so BPE never splits them.

Suppose merges learned ('t','h')→256, then (256,'e')→257 so the is one token. Encoding "the": [t,h,e] → [256,e] → [257]. Encoding "then": [t,h,e,n] → [256,e,n] → [257,n]. Slight spelling changes change token counts non-linearly.

A teaching-scale trainer, same spirit as Karpathy's minbpe:

from collections import Counter

def get_stats(ids: list[int]) -> Counter:
    pairs = Counter()
    for a, b in zip(ids, ids[1:]):
        pairs[(a, b)] += 1
    return pairs

def merge(ids: list[int], pair: tuple[int, int], new_id: int) -> list[int]:
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and (ids[i], ids[i + 1]) == pair:
            out.append(new_id)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out

ids = list(b"aaabdaaabac")
stats = get_stats(ids)
pair = max(stats, key=stats.get)
print(pair, stats[pair])
print(merge(ids, pair, 256))

Output:

(97, 97) 4
[256, 256, 97, 98, 100, 256, 256, 97, 98, 97, 99]

97 is byte a. The most frequent pair aa merged into id 256.

Naive repeated scans are fine for teaching. Production tokenizers (tiktoken, Hugging Face tokenizers) use optimized data structures.

Common mistakes

• Reimplementing encoding with a different merge order. Priority is the merge list, not "merge whatever is frequent in this string."
• Letting BPE split special tokens. Reserve them and pre-split.
• Upgrading a tokenizer under a trained checkpoint. Embedding rows no longer match.

Check yourself

1. Why start from 256 bytes instead of Unicode characters? Answer: Every UTF-8 string is then representable, with no unknown token.
2. Merges learned th→256 then the→257. How does "then" encode? Answer: [257, n] — the merges, trailing n stays separate.

Key takeaways

• BPE greedily merges frequent adjacent pairs until it hits a vocab size.
• Byte-level BPE covers all Unicode from 256 base bytes.
• Encoding applies learned merges in priority order, not by re-counting on the new string.
• Special tokens must be reserved so BPE never splits them.

Further learning

Next: WordPiece and SentencePiece.

Karpathy builds a GPT-2-compatible tokenizer from scratch:

Neural Machine Translation of Rare Words with Subword Units (BPE)Neural machine translation (NMT) models typically operate with a fixed vocabulary, but translation is an open-vocabulary problem. Previous work addresses the translation of out-of-vocabulary words by backing off to a …arXiv.org

minbpe (Karpathy)Minimal, clean code for the Byte Pair Encoding (BPE) algorithm commonly used in LLM tokenization. - karpathy/minbpeGitHub