BPE by hand

A language model never sees text. It sees integers. The tokenizer is the part that decides which integers, and a surprising number of "model" failures (bad arithmetic, spelling, odd behaviour on code or on non-English text) start there.

Byte-pair encoding (BPE) is the algorithm behind GPT-2, GPT-4 and Llama's tokenizers. The idea fits in one sentence: start with single bytes, then repeatedly merge the most frequent adjacent pair into a new symbol. Frequent strings become one token, rare strings stay in pieces, and nothing is ever out of vocabulary because any text is bytes.

Why bytes

Unicode has well over a hundred thousand characters. A byte-level vocabulary starts with exactly 256 entries and can encode any string through UTF-8. An ASCII letter is one byte, é is two (0xC3 0xA9), a typical emoji is four. GPT-2's vocabulary is 256 byte symbols plus 50,000 merges plus one special token: 50,257 in total.

A worked example

Pre-split the corpus into words with counts: low ×5, lower ×2, newest ×6, widest ×3. Start from characters. That is 79 symbols in total (3×5 + 5×2 + 6×6 + 6×3).

Count adjacent pairs. The winners are e s and s t with 9 each (they occur in both newest and widest). Ties are broken by first occurrence, so the first merge is e s → es. Recount: now es t has 9 and nothing beats it, so the second merge is es t → est. Third, l o and o w tie at 7, and l o → lo wins by order. Fourth, lo w has 7: lo w → low.

After four merges:

wordtokenscount
lowlow5
lowerlow e r2
newestn e w est6
widestw i d est3

The corpus shrank from 79 symbols to 5 + 6 + 24 + 12 = 47. That is the whole point: compression of the sequence at the cost of a bigger vocabulary. Here the vocabulary grew from 10 to 14 symbols.

Encoding a new word replays the merges in the order they were learned. lowest becomes l o w e s t, then es, est, lo, low, ending as low est. Two tokens, although the model never saw lowest. newer matches none of the merges and stays five tokens. Words made of familiar pieces are cheap, unfamiliar ones fall apart into near-bytes.

The trade-off behind vocab size

A bigger vocabulary shortens sequences, so attention, which costs $O(T^2)$, has less to do and the context window holds more text. It also makes the embedding and output matrices bigger: at width 768, a 50,257-token vocabulary is $50{,}257 \times 768 \approx 38.6$M parameters in the embedding alone. Rare tokens get few training examples, so their embeddings stay poor. Pick the vocabulary for your data and your budget; there is no universal best.

Code

from collections import Counter


def train(data: bytes, vocab_size: int) -> dict[tuple[int, int], int]:
    ids = list(data)
    merges = {}
    for new_id in range(256, vocab_size):
        counts = Counter(zip(ids, ids[1:]))
        if not counts:
            break
        pair = max(counts, key=counts.get)
        merges[pair] = new_id
        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
        ids = out
    return merges


def encode(text: str, merges) -> list[int]:
    ids = list(text.encode("utf-8"))
    while len(ids) >= 2:
        pair = min(zip(ids, ids[1:]), key=lambda p: merges.get(p, float("inf")))
        if pair not in merges:
            break
        new_id, out, i = merges[pair], [], 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
        ids = out
    return ids


def decode(ids, merges) -> str:
    vocab = {i: bytes([i]) for i in range(256)}
    for (a, b), new_id in merges.items():
        vocab[new_id] = vocab[a] + vocab[b]
    return b"".join(vocab[i] for i in ids).decode("utf-8", errors="replace")

Two details matter. Merge order is rank: encode always applies the earliest-learned merge available, which is why the new ids can double as ranks. And decode never needs the text; it only concatenates bytes.

What real tokenizers add

  • A pre-tokenization regex. GPT-2 first splits text into chunks (a word with its leading space, a run of digits, punctuation) and merges only inside chunks. Without it you get tokens like dog. and dog! that glue words to punctuation.
  • Special tokens such as end-of-text, handled outside the merge loop so user text can never create them by accident.
  • Speed. The loop above is quadratic-ish. Production versions use priority queues or Rust. Your version only has to be correct.

Common mistakes

  • Merging across pre-token boundaries, then wondering why a space sticks to the wrong word.
  • Breaking ties non-deterministically, so two training runs give different tokenizers.
  • Decoding with errors="strict" and crashing on a partial UTF-8 sequence. Models can emit a token boundary in the middle of a character.
  • Training the tokenizer on a corpus that looks nothing like the model's data (English-only text, then a multilingual product).
  • Forgetting that the tokenizer is part of the model. Change it and every checkpoint is invalid.

Check yourself

  • Why does a byte-level vocabulary never produce an unknown token?
  • Starting from the corpus above, what is the fifth merge, and what is the tie? (Count the pairs.)
  • Why does the embedding table grow when the vocabulary grows, but the transformer blocks do not?
  • Why do models stumble on questions about letters in a word?
  • You change the merge list after training the model. What breaks, and why?