The Merge Table Is the Tokenizer: Why Tokenize, and BPE from Scratch

Part 23 said a token is something you define, using stoi with one number per character; part 27 said text becomes bytes before it reaches the tokenizer. This part fills in the stretch between: how bytes become tokens.

text  →  UTF-8 bytes (part 27)  →  BPE merges (this part)  →  token IDs  →  model

A model sees nothing but IDs

Parts 23 to 26 tokenized by character: the 65 characters that occur in Shakespeare, one number each, a 65-row embedding table.

"hii there"
   ↓ split by character, look up stoi
[46, 47, 47, 1, 58, 46, 43, 56, 43]     ← 9 tokens
   ↓ each number fetches a row of the embedding table
into the model

A model never sees text, only IDs. The tokenizer is the layer that translates back and forth between the two. Real models do not split by character but by “chunk”: a common word is one chunk, a rarer one breaks into a few. GPT-2’s vocabulary has 50,257 tokens and its context is 1024 — and that 1024 counts tokens, not characters.

The token is the base unit of a large model: context length, training data size and API billing are all counted in tokens.

The split decides what the model sees

Karpathy opens the video with a list of large models’ odd habits, all rooted in tokenization. Four of them:

The last one has a sequel in the video: GPT-4’s tokenizer merges runs of spaces into a single chunk, one of the reasons it writes code better than GPT-2.

Same text, different tokenizer, different IDs

When OpenAI released GPT-4o it published a comparison: its new tokenizer, o200k_base (a vocabulary of about 200k), cut the same text as GPT-4’s cl100k_base (about 100k) into 1.4—1.7× fewer tokens for East Asian languages such as Chinese, Japanese, Korean and Vietnamese, and 2.9—4.4× fewer for Indian languages such as Hindi.

The reason lies in BPE itself: a bigger vocabulary can merge more, and longer, chunks; and the more of a language the tokenizer sees in training, the more readily its fragments merge into whole chunks — the algorithm below shows why.

🔑 Same model family, same text, only the tokenizer changed, and the token count moves by multiples — how many tokens a passage costs is decided by the tokenizer, not the model. Part 23’s “choose Qwen because Chinese costs fewer tokens” rests on exactly this.

A vocabulary cannot grow without limit

Every extra token is one more row in the embedding table and one more column in the output layer. Take the model from experiment D in part 25 (384 dimensions per token):

All 38.6M extra parameters sit in those two layers. Part 23 said “a small model with a large vocabulary is badly proportioned”; this table puts numbers on it. The bigger the vocabulary, the fewer tokens the same text cuts into — but the more parameters the model spends just storing the tokens.

Code points are too many, bytes too long

What the model wants is a string of integers. There are two ready-made ways to turn text into integers, and neither works — which is precisely the problem BPE solves.

Code points as tokens

A Python string is already a sequence of code points:

>>> [ord(c) for c in "你好，世界"]
[20320, 22909, 65292, 19990, 30028]

Two things rule it out: the vocabulary is too big — Unicode holds about 150,000 characters, and the vocabulary would be the whole table; and it is unstable — Unicode adds characters every year, so the vocabulary would change and the model would have to be retrained.

Bytes as tokens

UTF-8 has only 256 byte values, fixed forever, able to represent any text (part 27). UTF-16 and UTF-32 are out of the running: English h is [104, 0] and [104, 0, 0, 0] in them, stuffed with zeros.

The drawback is sequences far too long. Part 27’s Chinese sentence:

分词是大模型许多怪现象的根源。   15 characters
as byte tokens              →  45 tokens

The context holds a third as much; and attention computes a T×T table (part 23’s O(T²)), so three times the length is nine times the work.

BPE: start from 256 bytes, merge what often sits together

🔑 The smaller the vocabulary, the longer the sequence; the bigger the vocabulary, the shorter. The two trade off, and BPE picks a point in between: starting from 256 bytes, it merges a pair that often appears together into a new token, again and again, until the vocabulary reaches the size wanted — keeping “bytes can represent anything” while shortening the sequence.

The video also mentions the other road: skip tokenization and let the model read bytes directly (MEGABYTE, 2023, a Transformer with a hierarchical structure). Karpathy’s verdict was that it had not yet been proven on large models, and for now BPE is still the way.

Training BPE: count adjacent pairs, merge the commonest, repeat

The algorithm has a single rule: find the adjacent pair that occurs most often, replace it with a new symbol, and repeat. The video uses Wikipedia’s example:

aaabdaaabac      the commonest adjacent pair is aa → new symbol Z
ZabdZabac        the commonest is ab                → Y
ZYdZYac          the commonest is ZY                → X
XdXac            no pair occurs twice any more, stop

The sequence shrinks from 11 symbols to 5, the symbol set grows from {a, b, c, d} to {a, b, c, d, Z, Y, X}: each merge makes the sequence a little shorter and the vocabulary one entry larger. The third step merges the two new symbols Z and Y into X — merged symbols can take part in further merges, X = ZY = aa + ab = aaab.

On bytes, the starting point is the 256 values 0—255, and new tokens are numbered from 256.

Only adjacent pairs, overlaps left to right, ties recorded in order

“Replace the commonest pair with a new symbol” replaces the two together, and only where they truly sit side by side:

# merging (101, 32) in "the tree ", i.e. e plus a space → 256
[116, 104, 101, 32, 116, 114, 101, 101, 32]
[116, 104, 256,     116, 114, 101, 256]         # 9 become 7

The first e in “tree” is followed by an e, not a space, so it stays 101. 101 and 32 also stay in the vocabulary — merging only adds, never removes.

Two places where intuition slips:

• Overlaps go left to right, first come first paired: aaa becomes Za, and the third a has no partner and stays. So in the step above aa counts 4 times but is replaced in only 2 places
• A tie can go either way, but the order has to be recorded: in ZabdZabac, Za and ab both occur twice. Wikipedia takes ab; the code below, using max, takes Za, counted first. Both are valid BPE — what matters is that the order merges happen in during training goes into the table exactly as it happened

get_stats and merge

Two functions are the whole algorithm:

tokens = list(text.encode("utf-8"))     # integers 0—255 first

def get_stats(ids):
    counts = {}
    for pair in zip(ids, ids[1:]):      # (ids[0],ids[1]), (ids[1],ids[2]), ...
        counts[pair] = counts.get(pair, 0) + 1
    return counts

def merge(ids, pair, idx):
    newids, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
            newids.append(idx)          # this pair becomes the new ID
            i += 2                      # skip both
        else:
            newids.append(ids[i])
            i += 1
    return newids

merge([5, 6, 6, 7, 9, 1], (6, 7), 99)   # → [5, 6, 99, 9, 1]

• zip(ids, ids[1:]) lines the sequence up against itself shifted by one, giving every adjacent pair at once
• merge scans left to right, emitting the new ID and jumping two on a match, copying and stepping one otherwise — which is where “overlaps go left to right” comes from
• i < len(ids) - 1 guards against running off the end at the last position

On the whole of Shakespeare the top pair is (101, 32), e plus a space, 27,643 times: a great many English words end in e with a space right after.

The training loop: the merge table is the tokenizer

vocab_size = 276                  # the vocabulary size wanted
num_merges = vocab_size - 256     # = 20 merges
ids = list(tokens)                # a copy, leaving the data untouched
merges = {}                       # (p0, p1) -> new ID
for i in range(num_merges):
    stats = get_stats(ids)
    pair = max(stats, key=stats.get)
    idx = 256 + i
    ids = merge(ids, pair, idx)
    merges[pair] = idx

Twenty merges on the whole of Shakespeare:

merge  1: (101, 32)  -> 256   'e '        merge 11: (97, 110)  -> 266   'an'
merge  2: (116, 104) -> 257   'th'        merge 12: (58, 10)   -> 267   ':\n'
merge  3: (116, 32)  -> 258   't '        merge 13: (111, 114) -> 268   'or'
merge  4: (115, 32)  -> 259   's '        merge 14: (111, 32)  -> 269   'o '
merge  5: (100, 32)  -> 260   'd '        merge 15: (101, 110) -> 270   'en'
merge  6: (44, 32)   -> 261   ', '        merge 16: (10, 10)   -> 271   '\n\n'
merge  7: (111, 117) -> 262   'ou'        merge 17: (97, 114)  -> 272   'ar'
merge  8: (101, 114) -> 263   'er'        merge 18: (32, 257)  -> 273   ' th'  ← 257 merged again
merge  9: (105, 110) -> 264   'in'        merge 19: (111, 110) -> 274   'on'
merge 10: (121, 32)  -> 265   'y '        merge 20: (108, 108) -> 275   'll'

bytes 1,115,394 → tokens 882,737, compression 1.26x

• New tokens merge again: merge 18 takes the th made by merge 2 (257) together with the space before it into th; a few more rounds and the appears
• The rules mirror the data: merge 12, :\n, comes from the play’s layout, every speaker’s name followed by a colon and a newline (“First Citizen:”)
• Compression = bytes ÷ tokens: twenty merges compress by 1.26×. More merges, more compression, a bigger vocabulary — the trade-off from the previous section

🔑 What training produces is the merges table: twenty rules in the order learned. A trained tokenizer holds nothing but that table. Vocabulary size = 256 + number of merges: GPT-2’s 50,257 = 256 + 50,000 merges + 1 special token (<|endoftext|>). A real tokenizer does not stop at “no repeats”; it stops after a set number of merges.

A Hanzi’s 3 bytes take two merges

Ten merges on a passage of Chinese (423 characters, 1,227 bytes), a few picked out:

merge  4: (231, 154) -> 259   b'\xe7\x9a'          the first two bytes of 的
merge  5: (259, 132) -> 260   b'\xe7\x9a\x84'  = 的  ← one more merge completes the character
merge  2: (229, 173) -> 257   b'\xe5\xad'
merge  6: (257, 151) -> 261   b'\xe5\xad\x97'  = 字
merge  9: (136, 229) -> 264   b'\x88\xe5'           ← a fragment across two characters

bytes 1,227 → tokens 1,011, compression 1.21x

的 is E7 9A 84 and takes two merges to become one token: first its first two bytes, then that result with the third.

Merge 9 is more interesting still: 88 is the last byte of 合 (E5 90 88), and E5 the first byte of 并 (E5 B9 B6). Of this pair’s 18 occurrences, 15 come from 合并 and 3 from 先合 — two unrelated pairs of characters, counted as one pair because the bytes at the join are the same. BPE sees only bytes and has no idea where a character begins or ends.

“Is it the same pair?” depends only on the IDs

At the start an ID is a byte value; after merging, IDs are still what gets compared, and every new ID stands for a fixed string of bytes — so ultimately it is byte sequences being compared. The tokenizer knows nothing of letters, Hanzi, words, case or meaning. Three consequences:

1. Looks the same, different bytes, counts as different: case (E = 69, e = 101), a leading space or not; several ways of writing one character — é can be the single code point C3 A9 or e plus a combining accent 65 CC 81, identical on screen; full-width ＡＢＣ (EF BC A1 …) against half-width ABC (41 42 43) likewise. Some tokenizers unify these before BPE, which is Unicode normalization (NFC, NFKC); GPT’s tokenizers don’t, sentencepiece does by default
2. Different characters sharing bytes get counted together: 你 E4 BD A0, 住 E4 BD 8F, 位 E4 BD 8D, 体 E4 BD 93, 作 E4 BD 9C, 低 E4 BD 8E all begin with E4 BD. The count for (E4, BD) is theirs added up, more than any one whole character — so it tends to be merged early, and each character’s remaining byte is left over as a separate fragment
3. Fragments spanning two characters: merge 9 above

So a Hanzi’s 3 bytes being cut apart is routine: common characters learned the full merge and are 1 token; less common ones merged only partly; rare ones are three separate bytes. For the model itself this is no error — it only sees IDs, and learns from data that “these two pieces together are such-and-such a character”. The trouble comes when turning output back into text:

b = "你".encode("utf-8")                   # b'\xe4\xbd\xa0'
b[:2].decode("utf-8", errors="replace")   # '�'   with only the first two bytes in
b.decode("utf-8")                         # '你'  once the third has arrived

A model emits tokens piece by piece, and after the first two bytes nothing forms a character yet — streaming output has to hold bytes back until a character is complete before showing it, or part 27’s � flashes on screen.

decode and encode

The tokenizer is a stage of its own

tokenizer training data ──BPE training──→ merges table (fixed from then on)
                                              │
               text ──encode──→ IDs ──→ model (training, generation)
               text ←──decode── IDs ←──┘

• The tokenizer has its own training data, which can differ from the model’s. It is trained once and then fixed
• The model sees nothing but IDs from start to finish: before training, all training data is encoded into one long string of IDs; the model generates IDs, which must be decoded to be read
• The mix of languages in the tokenizer’s training data matters: the more of a language in it, the more merges that language learns and the fewer tokens it cuts into. That is one of the reasons the same Chinese can differ by multiples in token count between tokenizers

decode: build the vocab in training order

def build_vocab(merges):
    vocab = {idx: bytes([idx]) for idx in range(256)}   # 0—255: each ID is one byte
    for (p0, p1), idx in merges.items():                 # in training order
        vocab[idx] = vocab[p0] + vocab[p1]               # new ID = the bytes of two old IDs joined
    return vocab

def decode(ids, vocab):
    b = b"".join(vocab[idx] for idx in ids)              # IDs → bytes, one long string
    return b.decode("utf-8", errors="replace")           # bytes → text

• Why training order is required: a new ID may be built from an earlier new ID — 273 = 32 + 257, so 257 has to exist before 273 can be computed. Python dicts keep insertion order, so iterating merges.items() is exactly the training order
• Why errors="replace": not every string of IDs forms valid text

bytes([128]).decode("utf-8")   # error: can't decode byte 0x80 in position 0: invalid start byte
decode([128], vocab)           # '�'

128 = 10000000, and a byte opening with 10 is a continuation byte that can never start a character (part 27). A model may emit any combination of IDs while generating, including ones like this; with replace the program does not crash, and whatever cannot form a character becomes �.

encode: take the pair learned earliest, every step

def encode(text, merges):
    ids = list(text.encode("utf-8"))                    # text → bytes
    while len(ids) >= 2:
        stats = get_stats(ids)
        pair = min(stats, key=lambda p: merges.get(p, float("inf")))  # the pair learned earliest
        if pair not in merges:                          # none of the remaining pairs are in the table
            break
        ids = merge(ids, pair, merges[pair])
    return ids

The crux is which pair each step picks: not whichever pair is most frequent in this new text, but, among all the current adjacent pairs, the one with the smallest number in the merges table — the one learned earliest in training. Later merges are built on earlier ones, so encoding has to replay them in training order.

• merges.get(p, float("inf")): a pair not in the table counts as infinity and is never chosen; if even the chosen pair is missing from the table, nothing can merge any more
• while len(ids) >= 2: an empty string or a single byte has no adjacent pairs, and without the check min would raise on an empty dict

Encoding the thin with the twenty rules learned from Shakespeare:

start           [116, 104, 101, 32, 116, 104, 105, 110]     t h e ␣ t h i n
merge (101, 32)  → 256   [116, 104, 256, 116, 104, 105, 110] 'e ' is rule 1, merged first
merge (116, 104) → 257   [257, 256, 257, 105, 110]           'th', both places at once
merge (105, 110) → 264   [257, 256, 257, 264]                'in'
nothing left to merge → [257, 256, 257, 264] = 'th' 'e ' 'th' 'in'

❗ ’ th’ is in the table and goes unused

Rule 18, th (273), is in the table, yet cutting the thin never uses it: rule 1, 'e ', first merged the space with the e before it, and the second th no longer has a space of its own in front.

🔑 The order decides the result. The same table applied in a different order gives a different string of IDs — and the model learned from the split made in training, so if the split changes at encode time, what it sees is a string of unfamiliar IDs. Which is why encode has to replay the table strictly in order.

The round trip

decode(encode(s)) == s always holds. The first 5000 characters of Shakespeare give True; so does “Hello, 世界！分词器没见过中文也能处理。👋”, which this tokenizer has never seen — no merges were learned for the Chinese or the emoji, so they stay as raw bytes, and since 256 bytes can represent any text the round trip always works.

encode("the other", merges)   # [257, 256, 111, 257, 263]  'er' uses rule 8
encode("你好", merges)         # [228, 189, 160, 229, 165, 189]  6 raw bytes, not one Chinese merge

That 你好 line is what GPT-2 does with Chinese: rules learned from English find almost nothing to apply to, only on a much smaller scale.

The reverse does not always hold: encode(decode(ids)) need not equal ids — [128] decodes to �, which does not encode back to 128.

The code in this part adds up to a few dozen lines: get_stats counts adjacent pairs, merge replaces a pair, the training loop records the order of merges, decode looks things up, encode replays in order. A merge table in order is the entire tokenizer.

🔮 GPT-2’s real tokenizer has one more step: a regular expression first cuts the text into chunks (words, numbers, punctuation, spaces), and merging happens only inside each chunk, never across. So the 'e ' above would never appear in GPT-2 — it attaches the space to the following word, cutting the egg into the and egg. That rule, OpenAI’s tiktoken and special tokens are the next section (1.3); sentencepiece and a quirk-by-quirk explanation are 1.4.