Tokenization Primer

A model never sees your string. It sees a list of integers, each one a row number in a table, and the tokenizer is the only thing that knows which row. Here is a sentence and the integers it becomes — walk the caret along them:

Notice that the ids are not arbitrary. The first 256 are the byte values, and everything above that is numbered by when it was learned, so ·the at 258 was the third thing the training text asked for. An id is a position in a history, which is why two tokenizers cannot swap tables.

Three answers to what is a row were on the table for years and each broke somewhere. One row per character keeps the table tiny and makes every sequence five times longer — and attention costs the square of that. One row per word keeps sequences short, but the table is unbounded and any word you have not seen is a hole in it. What everyone ships is a dial between them.

Here is the same sentence with the dial at its far left, where every raw byte is a token of its own. Drag the slider and each step fuses the commonest pair in the training text, so the tokens grow from bytes into word-pieces and then into whole words:

Nothing is chosen between the three levels — one loop produces all of them. At zero merges — the frame this opens on — the vocabulary is the 256 byte values and the sentence costs 16 tokens, one per byte. At thirty-two merges it is 288 and the same sentence is 4, because ·the, ·model and ·read have each become one entry. The dot is the space: in every GPT vocabulary a word carries the space in front of it.

Both ends of the dial cost something, and the two costs are the same slider read from opposite sides — the sequence the model must attend over, and the vocabulary rows it must store and score:

Because attention is quadratic in sequence length and the embedding table is linear in vocabulary size, the left end of the dial is expensive per step and the right end is expensive per row. No setting is free; §06 puts real numbers on both.

The word end carries a second cost that is not on that plot. A vocabulary of whole words can only ever return what it has already seen. Walk the slider past the words the training text contained:

Watch what happens at unhappiness: the word vocabulary has no entry and returns <unk> — one id meaning something was here, with the something thrown away — while the byte vocabulary spells it out in 12. That is why every shipped tokenizer keeps the 256 bytes underneath: nothing can be out of vocabulary when the alphabet is the alphabet of the file.

The floor underneath is bytes, though, not characters, and those two are the same thing only in ASCII. Drag the caret along the Latin line and the Japanese line and read the cost of one character:

Every Latin letter is one byte; every Japanese character is three. A tokenizer that has learned no merges for a script therefore pays three tokens per character before it pays for anything else — and §04 is about what happens when the merges that would have fixed that were spent somewhere else.

Count every adjacent pair of symbols in a pile of text, fuse the commonest one into a single new symbol, write that fusion down, and go round again. The vocabulary is whatever the fusions produced. But nothing counts across a word boundary, because the text is cut into pieces before the loop ever runs.

That cut is a plain regular expression, and it is the reason ·the and the are two different entries. Walk the slider along the pieces it produces and read the byte count under each:

Notice where the boundaries fall. A leading space joins the word after it, so a word carries its own space; punctuation stands alone; and Chinese and Japanese, having no spaces at all, get one piece per character. No merge may ever cross one of these lines, which is a stronger guarantee than it looks — it is what stops the vocabulary learning ·the·model as one token.

Now the loop itself, on eleven word forms written in eleven distinct bytes. Every adjacent pair in the whole corpus is counted, weighted by how often its word occurs, and the commonest pair wins:

At the opening pass ·l leads with 21 against es's 16 — the space-plus-l of low, lower, lowest, less and list together. Ties happen constantly on a corpus this small: by the fourteenth pass the leader is a three-way tie at 4. Every implementation needs a rule for them; this one takes the pair its scan met first, so two libraries with different tie rules build different vocabularies from identical text.

Each merge rewrites the whole corpus, and the next pass counts what is left. Press play and watch the raw bytes fuse into pieces the vocabulary keeps:

Watch the shape of it. The first merges buy stems — ·l, ·lo, ·low — then the shared suffix est, then whole words. Fourteen merges take the corpus from 62 symbols to 21, and the scrubber stops there because fourteen is the budget this figure was given. The loop itself has not finished: ten pairs still occur at least twice, and it would run for ten more before the last repeated pair was gone. On real text that point is never reached at all — you always stop at a budget, and choosing it is §04's whole subject.

Every merge is one new row in the table, laid on top of an alphabet that was already complete. Drag the slider and watch the learned entries arrive:

Because the base is fixed and each merge adds exactly one entry, the vocabulary size is arithmetic, not a hyperparameter you tune blind: 256 + merges + specials. GPT-2 is 256 + 50,000 + 1 = 50,257, and the one special is <|endoftext|>. Every number in §04's ladder decomposes the same way.

Encoding is that list replayed on one word. Repeatedly find the pair in the word whose merge has the lowest rank and apply it. Step through it on a word the training text never contained, starting from its raw bytes:

Because the replay follows the learned order, the segmentation it produces is exactly the one the training would have produced for that word. That is the invariant the whole scheme rests on: encoding reproduces training. Order is not an optimisation here — it is the definition.

Both halves are cheap and neither is the bottleneck. Training and encoding cost different things. Training the naive way is O(k · N) — every merge rescans the corpus — and production trainers keep incremental pair counts in a heap to reach about O(N log N). Encoding one word of b bytes is O(b²) naively, O(b log b) with a heap. On real text the pre-tokenizer regex is usually the slowest part.

Which makes the obvious shortcut a bug. Take the longest entry the vocabulary has at each position instead of replaying the merges, and everything still typechecks. Flip the switch and read the two answers for the same word:

Replaying the merges gives ·n est — two tokens. Longest match gives ·ne s t — three ids, every one of them in the vocabulary, in an arrangement the model was never trained on. Nothing raises. The model just gets quietly worse, which is the same failure as shipping a merge file one version out of step with the weights.

BPE asks which pair is commonest. That is a count, and nothing else. WordPiece — BERT's tokenizer, and the ancestor of most encoder models — asks which pair is most surprising: it divides the pair's count by how often its two halves occur apart, which is a likelihood ratio rather than a frequency.

Here is the same corpus scored the second way. The switch flips between them — it opens on the likelihood criterion, and the count criterion is one press away:

Notice which pair likelihood promotes. id occurs 8 times against ·l's 21, but i and d in this corpus occur almost nowhere apart, so their bond is the strongest evidence in the text even though it is not the loudest. Frequency buys you the pairs you see most; likelihood buys you the pairs that mean something.

The criterion is not a detail of the loss curve; it is a different vocabulary. Both tables below open as ten numbered slots — drag the slider and each criterion fills its own row, one merge at a time, so you can compare what count bought against what likelihood bought:

After ten merges each the two tables have exactly one entry in common. That is why a tokenizer is not a component you swap: BERT's vocabulary and GPT-2's are not two spellings of the same thing, they are two different partitions of the same language.

Unigram — the other mode of SentencePiece, and what Llama and T5 use — throws the pair loop away. It starts from a large candidate vocabulary, gives every piece a probability, and asks a different question of a word: not how do I build it but which cut is most likely. Walk the ranking of every legal cut:

There are 13, and the top one is the cut BPE also returns — log-probability −2.64 against the runner-up's −5.20. The rest are still there, and that is the point: a model that can rank alternatives can sample them, which is how subword regularisation trains on several segmentations of one string.

A merge budget is fixed before training starts — 50,000 for GPT-2, 100,000 for cl100k. Every merge spent on a Latin word-piece is a merge not spent on a kanji, and the loop spends them wherever the counts are highest, which is wherever the corpus came from.

Here is one budget of 32 merges shared by two languages. The bar at the top is where they went; the two below are what one sentence costs in English and in Japanese. Drag the corpus:

At the opening frame the corpus is all English, every merge is Latin, and the two sentences cost 4 tokens and 18 — a 4.5× bill for the same amount of text. Push it halfway and the bill is 5 against 15; push it to all Japanese and it inverts exactly: 16 against 6. The asymmetry is not about the scripts. It is about whose text was in the pile.

The same slider, on the Japanese sentence itself. A box that is one bare byte is a third of a character standing in for a whole one:

With no Japanese in the corpus every character is 3 bytes and every byte is its own token — 18 ids for 6 characters, and not one of them is a character. The model can still read it, because byte fallback means nothing is unrepresentable, but it is spending three positions of context, three embedding lookups and three attention rows on a symbol a Japanese reader sees as one.

This is what the vocabulary ladder of the last six years has been buying. Walk the shipped sizes and read the decomposition of the rung under your hand:

Every one of them is 256 + merges + specials — cl100k and o200k also carry a block of ids nothing was ever assigned to, which is most of the gap between their specials and their total — and the growth is almost entirely merges: GPT-2's 50,257 in 2019, cl100k's 100,277 in 2022, o200k's 200,019 in 2024, Gemma's 256,000. Quadrupling the budget in five years is how multilingual and code coverage got bought — and §06 is what it cost to buy it.

Start with arithmetic. The merge loop has no idea what a number is; it fuses digit runs that were frequent in the corpus and leaves the rest alone. Walk the number line and watch the split change under your hand:

380, the frame this opens on, is one token. 381 is two, 38 then 1, and 2024 is one again because years were frequent. Only 108 of the 900 three-digit numbers are a single id here, and which 108 is an accident of frequency. The corpus under this figure is synthetic, so those 108 are ours and not any shipped tokenizer's; the raggedness is not. A model adding two numbers is adding operands of different shapes, which is why Llama 3 forces digits into groups of at most three and Gemma splits every digit on its own.

The same blindness explains the letter-counting failures. Walk the word list and compare what the model gets with the letters underneath:

At the opening frame ·model is one id covering six characters. Asked how many letters it has, the model cannot look: the letters are not in its input, so it has to have memorised that fact about that id. Rare words fare better precisely because they arrive in pieces — the tokenizer that hides spelling from common words exposes it in the ones nobody trained on.

Third, whitespace. A word carries the space in front of it, so moving it changes which entry gets looked up. Step through four arrangements of the same two words:

Watch the token count. The ordinary spacing is 4; a trailing space is 5, because the space is stranded as a token of its own instead of riding the next word. That is the whole explanation for a prompt that ends in a space behaving worse than the same prompt without one: it is not superstition, the model is genuinely off the distribution it was trained on.

And fourth, one word is four entries. Case and leading space are part of the key, so three of these four spellings fall back to raw bytes:

·the is one id; the same word at the start of a line, with no space, is three; capitalised it is four. The model has to learn that these four id sequences mean one word, from data alone. It mostly does — and the cases where it does not are why a prompt rewritten in Title Case can score differently on the same benchmark.

A decoder block is about 12·L·d² parameters — four d×d attention projections and a 4× MLP — and the embedding table is V·d. Drag the vocabulary and watch the two halves of that sum:

At the opening frame — GPT-2 small, d = 768, GPT-2's own vocabulary — the embedding table is 38.6M parameters against 84.9M in the twelve blocks: 31% of the model is the vocabulary. The formula puts the total at 123.5M against a published 124M, and it lands within half a percent on all four GPT-2 sizes — the rest is layer norms and the position table — so the split it reports is the real one.

Now the same split drawn once for each of the four sizes GPT-2 actually shipped. The first slider is still the vocabulary, and the second one — the new one — picks which rung of the width ladder is the subject:

Notice that the embedding band shrinks down the stack untouched — 31.2%, 14.6%, 8.3%, and at d = 1600 just 5.2% — because blocks grow as d² and the table only as d. That is §04's ladder: quadrupling the vocabulary is a rounding error at the top of it and the dominant term at the bottom.

def train(corpus, k):
    seq = [list(w.encode()) for w in corpus]
    merges = []
    for _ in range(k):
        p = top_pair(seq)
        if p is None:
            break
        seq = [fuse(s, p) for s in seq]
        merges.append(p)
    # the order IS the model
    return merges

def encode(word, merges):
    s = list(word.encode())
    rank = {p: i for i, p in enumerate(merges)}
    while (p := best(s, rank)) is not None:
        # lowest rank first, always
        s = fuse(s, p)
    return s

Two lines carry the weight: merges is an ordered list, not a set, and best picks by rank. Which makes the merge file part of the model, not a config beside it. Delete one entry from the list the weights were trained with and read what the model is handed instead:

Notice that nothing raises. Every id in the bottom row is a legal id, the sequence is a legal sequence, and the tokenizer returns it without a warning — the ids after the deleted merge have simply all slid down by one, so the model is being asked about ·model using the integer it learned for something else. Delete the very first merge and almost the whole sentence moves. That is the same failure as the longest-match encoder in §02, arriving by a different route: the only symptom either way is a model that quietly scores worse.