NEURONS ALL THE WAY DOWN · CHAPTER 07
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.
UNK, and why café is five bytesImagine 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.
One id per whitespace word. New names, typos, and compounds become UNK. Morphology (“book” / “books”) is invisible.
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.
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.
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:
| Pair | Count | Why |
|---|---|---|
| o o | 18 | every word has “oo” once, 8+3+4+2+1 |
| b o | 17 | all but brook |
| o k | 12 | book, books, brook |
| o t | 6 | boot, 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 |
|---|---|---|
| book | 8 | 258 |
| books | 3 | 258 · s |
| boot | 4 | 259 |
| boots | 2 | 259 · s |
| brook | 1 | b · 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
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
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
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.
"""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.
“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.
café is five bytes. There is no UNK.oo → 256, 18 times. Every word contains “oo” once.
“book” is [258]. “brook” is b, r, 256, k.
Rank order is a greedy replay of the training merges. A shortest split would search over segmentations. They can disagree.
Five bytes. é is 195, 169 (C3 A9).
<|endoftext|>?No. Packed training sequences attend across it. A special id is not a mask.