DL S044 · BPE from Scratch — Byte by Byte

Series: Deep Learning & LLMs From Scratch — 80 sessions · Session 44 / 80 · Module M08 · ~2 hours

The story

You've been feeding your models character-level tokens. That's fine for Tiny Shakespeare, wasteful for anything real. GPT-2, GPT-3, and pre-Llama frontier models all use byte-pair encoding (BPE) — a middle ground between characters (~100 tokens, model has to learn spelling from scratch) and full words (~100k+ tokens, huge embedding table, out-of-vocab problems). BPE gives you a vocab of ~50k subword tokens where common words become single tokens and rare words split into meaningful chunks.

BPE's core algorithm is embarrassingly simple:

1. Start with each byte as its own token.
2. Find the most frequent adjacent pair of tokens in the corpus.
3. Merge that pair into a new token.
4. Repeat until you hit your target vocab size.

The trick is doing it efficiently on billions of tokens, and handling the Unicode / whitespace / punctuation edge cases that will otherwise mangle your model's ability to represent code, emoji, and non-English text. This session we build a working BPE from scratch in ~80 lines, train it on 10 MB of Wikipedia-like text, and understand exactly what's happening when Karpathy says "tokenization is 90% of the pain of building an LLM."

Prerequisites

• S041 — char-level tokenizer, the predecessor.
• Basic Python collections.Counter and dict fluency.

1 · The algorithm in three sentences

BPE training:

1. Represent every text sample as a list of tokens, starting with every byte (or char) being its own token.
2. Count how often each adjacent pair of tokens appears; find the most common pair.
3. Add a new token to the vocab that represents "this pair merged"; replace every occurrence of the pair in the corpus with the new token. Repeat step 2 with the new corpus until vocab size reached.

That's it. The output of training is a vocab (list of tokens) and a merge list (ordered list of pairs that got merged, needed to encode new text later).

2 · Toy example — hand-trace

Corpus: "low low low low low lower lower newest newest widest widest widest" (Sennrich's original example, character-level for clarity).

Start with every char as its own token. Word boundaries matter, so we put </w> at the end of each word:

l o w </w>       (×5)
l o w e r </w>   (×2)
n e w e s t </w> (×2)
w i d e s t </w> (×3)

Count adjacent pairs across all copies. The most common pair: ('e', 's') — appears in every "newest" (×2) and every "widest" (×3) = 5 times.

Merge: create new token es, replace e s with es everywhere:

l o w </w>          (×5)
l o w e r </w>      (×2)
n e w es t </w>     (×2)
w i d es t </w>     (×3)

Next iteration. New pair counts: ('es', 't') = 5, ('l', 'o') = 7. Winner: ('l', 'o') → merge:

lo w </w>            (×5)
lo w e r </w>        (×2)
n e w es t </w>      (×2)
w i d es t </w>      (×3)

Next: ('lo', 'w') = 7. Merge:

low </w>             (×5)
low e r </w>         (×2)
n e w es t </w>      (×2)
w i d es t </w>      (×3)

After a few more iterations, low</w>, lower</w>, newest</w>, widest</w> all become single tokens. The vocab has learned the common words as atomic units while keeping the ability to build up rare words from smaller pieces.

That is BPE. Byte-level GPT-style BPE just does the same thing starting from raw bytes instead of characters — critical for handling arbitrary Unicode.

3 · Training BPE in ~50 lines

from collections import Counter, defaultdict
 
def get_pair_counts(word_freqs):
    """Given {word_tuple: freq}, count all adjacent pairs."""
    pairs = Counter()
    for word, freq in word_freqs.items():
        for i in range(len(word) - 1):
            pairs[(word[i], word[i+1])] += freq
    return pairs
 
def merge_pair(pair, word_freqs):
    """Return new word_freqs with 'pair' merged into a single token."""
    new_word_freqs = {}
    a, b = pair
    merged = a + b
    for word, freq in word_freqs.items():
        new_word = []
        i = 0
        while i < len(word):
            if i < len(word) - 1 and word[i] == a and word[i+1] == b:
                new_word.append(merged)
                i += 2
            else:
                new_word.append(word[i])
                i += 1
        new_word_freqs[tuple(new_word)] = freq
    return new_word_freqs
 
def train_bpe(corpus_text, vocab_size, verbose=False):
    # 1. Split into words, count freqs, split each word into chars
    word_freqs = Counter(corpus_text.split())
    word_freqs = {tuple(w) + ('</w>',): c for w, c in word_freqs.items()}
 
    vocab = set(ch for word in word_freqs for ch in word)
    merges = []
 
    while len(vocab) < vocab_size:
        pair_counts = get_pair_counts(word_freqs)
        if not pair_counts:
            break
        best_pair = max(pair_counts, key=pair_counts.get)
        word_freqs = merge_pair(best_pair, word_freqs)
        merges.append(best_pair)
        vocab.add(''.join(best_pair))
        if verbose:
            print(f"merge {len(merges)}: {best_pair} (count={pair_counts[best_pair]})")
    return vocab, merges

Run it on our toy corpus:

Fifty lines. That's a working (if slow) BPE trainer.

4 · Byte-level BPE — the GPT-2 way

Character-level BPE has a Unicode problem. What's the vocab? All possible characters? Chinese has 20k+ common chars, emoji is unbounded, private-use planes exist. You'd need a huge base vocab or drop out-of-vocab chars entirely.

GPT-2's fix: BPE at the BYTE level. Every Unicode character encodes as 1–4 UTF-8 bytes; work at the byte level and your base vocab is exactly 256 (bytes 0–255). Merges happen between bytes and byte-sequences. Every string can be tokenized; no OOV.

Twist: printable-ASCII bytes are used directly, but non-printable bytes (control chars, high UTF-8 bytes) get remapped to visually-representable Unicode code points via a bijective function (see bytes_to_unicode() in OpenAI's encoder.py). This is purely aesthetic — makes the vocab file human-readable when it contains characters like Ġ (which stands for the space character).

def bytes_to_unicode():
    """OpenAI's byte-to-visible-unicode mapping."""
    bs = list(range(ord("!"), ord("~")+1)) + list(range(ord("¡"), ord("¬")+1)) + list(range(ord("®"), ord("ÿ")+1))
    cs = bs[:]
    n = 0
    for b in range(2**8):
        if b not in bs:
            bs.append(b)
            cs.append(2**8 + n)
            n += 1
    return dict(zip(bs, [chr(c) for c in cs]))

If you see Ġthe in a GPT-2 vocab, that's the (leading-space + "the") after the byte-to-unicode remap. Not a special character. Just readability.

5 · Encoding with a trained BPE

Encoding a new string requires applying merges IN THE ORDER they were learned:

def encode(text, merges):
    tokens = list(text) + ['</w>']
    for pair in merges:
        i = 0
        while i < len(tokens) - 1:
            if tokens[i] == pair[0] and tokens[i+1] == pair[1]:
                tokens[i] = pair[0] + pair[1]
                del tokens[i+1]
            else:
                i += 1
    return tokens

Each merge in the merge list is applied greedily to the current token sequence. Order matters — merging ('e', 's') first (an early learned pair) enables the later merge ('es', 't').

Real BPE encoders speed this up with a priority queue keyed by merge index. Our simple version is O(vocab_size · text_len) per encode, fine for teaching, too slow for production.

with open('input.txt') as f: text = f.read()
vocab, merges = train_bpe(text, num_merges=500)
 
print("First 30 merges (in order they were learned):")
for i, (a, b) in enumerate(merges[:30]):
    print(f"  {i:3d}: {a!r} + {b!r}  ->  {(a+b)!r}")

6 · The four classic BPE pathologies

7 · How big should your vocab be?

8 · Pitfalls of BPE training

# A corpus where a meaningless pair is very frequent and a real
# morpheme boundary is rare.
corpus = ['qx ' * 500, 'unhappiness ']          # 'qx' beats 'un|happi|ness'

vocab = train_bpe(corpus, num_merges=50)
print([m for m in vocab.merges[:10]])
# 'q'+'x' merges first. No morpheme in sight.

# On a real tokenizer, check the frequency story on numbers:
for n in ('1', '12', '123', '1234', '12345'):
    print(n, tok.encode(n))
# Segmentation is inconsistent across lengths because it follows
# corpus frequency of digit strings, not place value -- which is
# why digit arithmetic is unreasonably hard for these models.

Retention scaffold

Recall questions

The 2025 tokenizer landscape (what changed since GPT-2)

BPE hasn't gone away — but 2024–2025 pushed vocab sizes, byte-fallback strategies, and pre-tokenization regex to places GPT-2 never imagined. A quick tour, so you know what you're competing with when you ship a tokenizer in 2026:

• Llama 3 (Meta, 2024) — 128k-token BPE vocab (4× Llama 2's 32k), trained on a much more multilingual + code-heavy corpus. Result: ~15% fewer tokens per document on average vs Llama 2, which directly translates to ~15% cheaper inference and ~15% more usable context. Dubey et al. (2024), The Llama 3 Herd of Models, arxiv 2407.21783.
• DeepSeek-V3 (Dec 2024) — 129k BPE vocab, aggressive Chinese-character coverage; tokenizer alone is ~30% cheaper on Chinese than GPT-4's cl100k_base. Whole-model tech report: arxiv 2412.19437.
• Gemma 3 (Google, 2025) — 256k SentencePiece unigram vocab, the biggest widely-deployed vocab today. The multilingual gains are real; the embedding table is 256k × 2048 = 500M parameters on the 1B model — nearly half the model is the token table. There's a scaling-law twist here (see S047).
• Tekken (Mistral Nemo, 2024) — Mistral's byte-level BPE trained on 100+ languages plus Python/JS/C++. Reported ~30% better compression on non-English + code vs Llama 3's tokenizer at similar vocab size.
• tokenmonster (Alasdair Forsythe, 2023–2024) — an alternative training algorithm that optimizes vocab against a language-model-like objective (rather than greedy pair-count). On matched vocab sizes it typically gives 5–15% better compression than BPE. Not yet used by a frontier model, but the open-source community loves it. https://github.com/alasdairforsythe/tokenmonster

The rule of thumb for 2026 is: larger vocab ≈ better compression ≈ cheaper inference, but embedding table starts eating your parameter budget. A 1B model with a 256k vocab has ~half its params locked in the token table, which is bad for capacity per FLOP. Karpathy's 2024 rant on this — search his X for "tokenization is at the heart of much weirdness in LLMs" — is required reading.

Stretch prompt

Train BPE with vocab_size = 5000 on the first 10 MB of Wikipedia (grab from en.wikipedia.org/wiki/Special:Export). Compare token counts of a paragraph tokenized with your vocab vs GPT-2's tokenizer (from transformers import GPT2Tokenizer). You should be within ~10% — differences will be in how you handle unusual chars, punctuation, and byte remapping.

In your own words

"If a friend asked why tokenization matters — why we don't just feed characters or words to the model — what would I say?"

Spaced review

• S041 — char-level tokenizer we're now generalizing.

Next-session teaser

S045 compares BPE to SentencePiece unigram, the tokenizer scheme used by Llama, T5, and many modern models. Same goal (subword tokens), different training algorithm, subtly different tradeoffs.

Bring back tomorrow

• BPE: greedy pair merging until vocab size reached.
• Byte-level > char-level for universal Unicode support.
• Encoding = apply learned merges in order.
• Tokenization pathologies are the #1 cause of "why is my LLM bad at X" questions.

Previous: ← DL S043 · Next: DL S045 →