NEURONS ALL THE WAY DOWN · CHAPTER 07

Tokenization

The net never sees characters. It sees integer ids. Byte-level BPE is how modern models pick those ids: start from UTF-8 bytes, merge frequent pairs, and apply the merges in rank order.

~16 min read1 interactiveTested Python

What you'll learn

  • Why word-level and character-level tokenizers both fail, in opposite ways
  • How BPE trains (max frequency) and how it encodes (min merge rank)
  • Why “must appear in two words” and “pick the shortest split” are both wrong
  • What “byte-level” adds: UTF-8, no UNK, and why café is five bytes

Before you start

A dictionary that grows its own words

Imagine packing a ship’s library. If you store one card per English word, you run out of cards the first time someone writes bookish or a name you have never seen. If you store one card per letter, every sentence becomes a long ribbon, and the model has to relearn that b-o-o-k is a unit.

BPE starts with the letters (or the bytes) and, each time it sees a pair that keeps showing up, it prints a new card for that pair. Frequent whole words get their own card. Rare words stay split. The library stays finite, and almost nothing is “unknown.”

A tokenizer is a vocabulary plus a procedure. The vocabulary is a list of ids. The procedure is how a string is chopped into those ids, and how the ids are glued back into a string. The model only ever sees the ids.

Words, characters, subwords

Word-level

One id per whitespace word. New names, typos, and compounds become UNK. Morphology (“book” / “books”) is invisible.

Character-level

No UNK. Sequences are long. Attention is \(O(T^2)\), so a 4× longer ribbon is a 16× attention bill. Unicode has over 100,000 code points.

Subword (BPE)

Frequent chunks stay whole. Rare chunks split. The vocab is a chosen size — GPT-2 uses 50,257 — and the embedding table stays that tall.

Two informal rules of a good subword vocab: a common word should be one token, and a rare word should fall back to pieces the model has actually seen. BPE is a compression algorithm from 1994 that happens to do both, if you train it on enough text.

Always merge the most frequent pair

Our corpus, with counts: book×8, books×3, boot×4, boots×2, brook×1. Start with characters. Count every adjacent pair, weighted by the word’s count:

PairCountWhy
o o18every word has “oo” once, 8+3+4+2+1
b o17all but brook
o k12book, books, brook
o t6boot, boots

Merge oo into a new id 256. Then recount. The new leader is b+256 (17 times). That becomes 257. Then 257+k (11 times) becomes 258 — that id is the word “book”. Then 257+t (6 times) becomes 259 — “boot”.

After those four merges the five words look like:

Word× Symbols
book8258
books3258 · s
boot4259
boots2259 · s
brook1b · r · 256 · k

There is no extra rule that a pair “must appear in two different words.” Frequency is the only vote. A corpus of zzzz×9 has the pair zz 27 times inside a single word type, and that pair still merges first.

Interactive · Merge trainer

Which pair is most frequent right now, and what does the corpus look like after you merge it?

Current words

Top pairs

Apply merges by rank, not by shortness

Training recorded a list: merge 0 is oo→256, merge 1 is b+256→257, … Encoding a new string walks that list from the top. Each merge is applied left to right, wherever the pair currently sits. “book” becomes [258]. “brook” becomes ['b', 'r', 256, 'k'] — the oo merged, the later “book” merge did not fire, because the b was no longer next to 256.

That is not “choose the shortest token list.” A shortest-segmentation rule would need a search. BPE is greedy in merge order. Two tokenizers with the same vocab and different ranks can split the same word differently.

Train: repeatedly merge the pair that is most frequent now. Encode: replay those merges in the order they were learned. Confusing the two is the most common BPE mistake.

oo→256 · … · →258  ·  book → [258]  ·  brook → b r 256 k  ·  rank ≠ shortest

MANIM Apply merges by rank, not by shortness. Use the beat buttons to jump.

Start from UTF-8, not from letters

Unicode code points and UTF-8 bytes are different. The string café is four characters. In UTF-8 it is five bytes: c=99, a=97, f=102, and é is the pair 195, 169 (C3 A9). Languages that use more bytes per character get longer token ribbons for the same meaning. That is a fairness issue, not a bug in BPE, and it is why people publish multilingual tokenizers carefully.

café · 4 chars  →  5 UTF-8 bytes  →  é = C3 A9

MANIM café is 4 chars, 5 UTF-8 bytes. Use the beat buttons to jump.

GPT-2-style BPE takes those bytes as the base vocab of 256, then learns merges starting at id 256. Nothing is ever UNK: every Unicode string has a byte encoding, and every byte is in the vocab. Decoding a broken id uses errors="replace" and emits \(\mathrm{U+FFFD}\).

Before the merges run, a regex splits the text into pieces so that dog. and dog! and dog? do not invent three copies of “dog + punctuation” in the vocab. The merges never cross those splits. Spaces usually stick to the next word, which is why “ dog” and “dog” are different tokens and why a leading space can change a completion.

Special tokens such as GPT-2’s <|endoftext|> (id 50,256) sit outside the merges. In tiktoken, encode on a string that contains one raises unless you pass allowed_special. That is a safety default: a prompt that smuggles the end token should not silently become one. And when GPT-2 packs several documents into one context, it does attend across that token. Isolation is a packing / masking choice, not a property of the id.

bpe.pybook → [258], café → 5 UTF-8 bytes, zz still merges
"""Byte-pair encoding on a tiny “book / boot / brook” corpus.

Training picks the most frequent adjacent pair, again and again.
Encoding applies those merges in *rank order* (earliest merge first).
That is not the same as “pick the shortest segmentation.”

The corpus is a made-up shelf of “book / boot / brook” counts.
It is not taken from a source-video demo.
"""
from collections import Counter

# (word, count). Counts make the first few merges unique, so the
# walkthrough on the page has one obvious pair at each step.
CORPUS = [
    ("book", 8),
    ("books", 3),
    ("boot", 4),
    ("boots", 2),
    ("brook", 1),
]


def word_to_symbols(word):
    """Start state: one symbol per character. No end-of-word marker."""
    return tuple(word)


def pair_counts(words):
    """words is a list of (tuple_of_symbols, count)."""
    stats = Counter()
    for symbols, n in words:
        for a, b in zip(symbols, symbols[1:]):
            stats[(a, b)] += n
    return stats


def merge_pair(symbols, pair, new_id):
    """Replace every adjacent `pair` in one word with `new_id`."""
    out = []
    i = 0
    while i < len(symbols):
        if i < len(symbols) - 1 and (symbols[i], symbols[i + 1]) == pair:
            out.append(new_id)
            i += 2
        else:
            out.append(symbols[i])
            i += 1
    return tuple(out)


def pick_pair(stats):
    """Highest count wins. Ties break lexicographically on (a, b)."""
    return min(stats.items(), key=lambda kv: (-kv[1], kv[0]))[0]


def train_bpe(corpus=CORPUS, n_merges=6, first_id=256):
    """Learn `n_merges` merges. Base symbols are the characters themselves.

    first_id=256 matches byte-level BPE: ids 0..255 stay as raw bytes,
    and learned merges start at 256.
    """
    words = [(word_to_symbols(w), n) for w, n in corpus]
    merges = []  # list of (pair, new_id), in the order they were learned
    for i in range(n_merges):
        stats = pair_counts(words)
        if not stats:
            break
        pair = pick_pair(stats)
        new_id = first_id + i
        merges.append((pair, new_id, stats[pair]))
        words = [(merge_pair(sym, pair, new_id), n) for sym, n in words]
    return merges, words


def encode(text, merges):
    """Apply learned merges by rank: earliest merge first, left to right.

    This is the GPT-2 / tiktoken rule. It is *not* “choose the
    segmentation with the fewest tokens.”
    """
    symbols = list(text)
    for pair, new_id, _count in merges:
        symbols = list(merge_pair(tuple(symbols), pair, new_id))
    return symbols


def decode(ids, merges):
    """Invert the merges, then join. Unknown bytes become a replacement."""
    inv = {new_id: pair for pair, new_id, _ in merges}

    def expand(tok):
        if tok in inv:
            a, b = inv[tok]
            return expand(a) + expand(b)
        if isinstance(tok, str):
            return tok
        return "\ufffd"  # replacement character, like bytes.decode(errors='replace')

    return "".join(expand(t) for t in ids)


# --- Byte-level helpers. GPT-2 starts from UTF-8 bytes, not Unicode chars. ---

def utf8_bytes(text):
    """List of integers in 0..255."""
    return list(text.encode("utf-8"))


def train_byte_bpe(texts, n_merges=6):
    """texts is a list of strings (each count=1). Base vocab is 0..255."""
    words = [(tuple(utf8_bytes(t)), 1) for t in texts]
    merges = []
    for i in range(n_merges):
        stats = pair_counts(words)
        if not stats:
            break
        pair = pick_pair(stats)
        new_id = 256 + i
        merges.append((pair, new_id, stats[pair]))
        words = [(merge_pair(sym, pair, new_id), n) for sym, n in words]
    return merges


# --- Numbers quoted on the page. ---

MERGES, AFTER = train_bpe(n_merges=4)
FIRST_PAIR, FIRST_ID, FIRST_COUNT = MERGES[0]          # ('o','o'), 256, 18
SECOND_PAIR, SECOND_ID, SECOND_COUNT = MERGES[1]        # ('b', 256), 257, 17
BOOK_ENCODED = encode("book", MERGES)
BROOK_ENCODED = encode("brook", MERGES)
ROUNDTRIP = decode(BOOK_ENCODED, MERGES)

# “café” in UTF-8: c a f + the two-byte encoding of é.
CAFE_BYTES = utf8_bytes("café")                        # [99, 97, 102, 195, 169]

# A pair that appears in only one word type still merges if it is frequent
# enough. “oo” in this corpus is in four types; the rule is frequency, not
# “must appear in two different words.”
SINGLE_TYPE_CORPUS = [("zzzz", 9), ("xy", 1)]
SINGLE_MERGES, _ = train_bpe(SINGLE_TYPE_CORPUS, n_merges=1)
# “zz” appears 27 times inside one word type (3 pairs × 9). It still merges.

Mistakes learners make

“BPE only merges pairs that appear in two different words.” No. Frequency is the only rule. A pair that lives in one frequent word type still wins.

“At inference, pick the shortest tokenization.” No. Apply the learned merges in rank order. Shortest-search is a different algorithm.

Comparing perplexity across tokenizers. A 50k vocab and a 100k vocab are not guessing from the same set. Compare bits per byte if you must.

Encoding a special token without allowing it. tiktoken raises. Passing allowed_special="all" on user text is how a prompt-injection becomes an actual special id.

What to remember

  • Subword BPE sits between words and characters. The vocab size is a knob (GPT-2: 50,257).
  • Train: merge the most frequent pair. Encode: replay merges by rank.
  • Byte-level BPE starts from the 256 UTF-8 bytes. café is five bytes. There is no UNK.
  • Regex pre-splits so punctuation does not duplicate “dog”. Special tokens are a separate, dangerous channel.

Check yourself

1. On this corpus, what is the first merge, and how many times does it fire?

oo → 256, 18 times. Every word contains “oo” once.

2. After four merges, how is “book” encoded? How is “brook” encoded?

“book” is [258]. “brook” is b, r, 256, k.

3. Why is encode-by-rank not the same as “shortest split”?

Rank order is a greedy replay of the training merges. A shortest split would search over segmentations. They can disagree.

4. How many UTF-8 bytes is “café”, and what are the last two?

Five bytes. é is 195, 169 (C3 A9).

5. Does GPT-2 refuse to attend across <|endoftext|>?

No. Packed training sequences attend across it. A special id is not a mask.

Go to the source

Keep going