Build a BPE Tokenizer: Why Your Model Can't Count the R's

There are two obvious ways to feed text to a network and both fail for reasons worth understanding, because the failure defines the shape of the solution.

Words. Split on spaces, assign each word a number. English has hundreds of thousands of word forms and the model needs an embedding row for each, so the vocabulary — and the output layer, which must produce a score for every entry — becomes enormous. Worse is what happens at inference: a word the model never saw in training has no number. That is the out-of-vocabulary problem, and the usual patch is to map everything unknown to a single <UNK> token, which throws the information away. Also "word" is not a well-defined concept: Chinese and Japanese do not put spaces between words, and German compounds one noun onto another indefinitely.

Characters. No out-of-vocabulary problem, and a vocabulary of a hundred-odd symbols. But the sequences become very long, and Chapter 9 will show that attention cost grows quadratically with sequence length. A 1000-word document is around 5000 characters — a sequence four to five times longer than it needs to be, for a quadratic price. And each character carries almost no meaning on its own, so the first few layers get spent reassembling words the tokenizer could have handed over intact.

The answer is between them: subwords. Common words become one token, rare words split into pieces, and nothing is ever unknown because the pieces bottom out at individual bytes. The interesting part is that nobody designs the split. The tokenizer is trained, on the same kind of data as the model, and it learns which byte sequences are worth their own number by counting how often they occur together.

The algorithm is from 1994, and it was a compression algorithm. Philip Gage published it in the C Users Journal as a way to shrink files by repeatedly replacing the most frequent pair of adjacent bytes with a byte that does not occur in the data.¹ It sat there for twenty-two years until Sennrich, Haddow and Birch repurposed it for machine translation in 2016 to solve the out-of-vocabulary problem.² It is now how essentially every large language model reads.

The training loop is four steps repeated:

Here is the entire trainer:

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


def merge(ids, pair, idx):
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
            out.append(idx)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out


class BPE:
    def __init__(self):
        self.merges = {}
        self.vocab = {i: bytes([i]) for i in range(256)}

    def train(self, text, vocab_size):
        ids = list(text.encode("utf-8"))
        for i in range(vocab_size - 256):
            stats = get_stats(ids)
            if not stats:
                break
            pair = max(stats, key=stats.get)      
            idx = 256 + i                         
            ids = merge(ids, pair, idx)           
            self.merges[pair] = idx               
            self.vocab[idx] = self.vocab[pair[0]] + self.vocab[pair[1]]
        return ids

Run it on 151,191 bytes of English prose and print the first twelve merges as they happen. This is the part worth reading slowly, because nobody told the algorithm anything about English:

merge   1: b'e' + b' '   -> b'e '     (occurred 4433 times)
merge   2: b' ' + b't'   -> b' t'     (occurred 3302 times)
merge   3: b'\xe2' + b'\x80' -> b'\xe2\x80'  (occurred 3247 times)
merge   4: b' ' + b'a'   -> b' a'     (occurred 2335 times)
merge   5: b' t' + b'h'  -> b' th'    (occurred 2253 times)
merge   6: b'i' + b'n'   -> b'in'     (occurred 2011 times)
merge   7: b't' + b' '   -> b't '     (occurred 1904 times)
merge   8: b'e' + b'r'   -> b'er'     (occurred 1813 times)
merge   9: b'd' + b' '   -> b'd '     (occurred 1703 times)
merge  10: b'o' + b'u'   -> b'ou'     (occurred 1554 times)
merge  11: b' ' + b's'   -> b' s'     (occurred 1467 times)
merge  12: b' th' + b'e '-> b' the '  (occurred 1270 times)

Three things in that list are worth pointing at.

Merge 12 is the word "the" — with the space before it and the space after it, as a single unit, discovered on the twelfth iteration of a loop that counts pairs. Nobody supplied a dictionary. It is there because those five bytes co-occur more than any other five in English.

Merge 3 is not text at all. \xe2\x80 is the first two bytes of the UTF-8 encoding of typographic punctuation — the em dash, the curly quotes. The algorithm has no idea UTF-8 exists, and it has just rediscovered a piece of its structure, because multi-byte encodings are by construction sequences of bytes that always appear together.

Most of the early merges involve a space, and the space is usually on the left. That is the origin of one of the most confusing behaviours in practice, which we come back to shortly.

Every merge makes the sequence shorter and the vocabulary bigger. How far to push it is a real decision, and it can be measured — here on the same 151,191 bytes:

Diminishing returns, visibly. Doubling from 512 to 1024 buys 0.78 bytes per token; doubling from 2048 to 4096 buys 1.07 — better here only because this corpus is small enough that longer merges keep paying off. On a real corpus the curve flattens hard.

And the cost of a larger vocabulary is not just memory. Every token needs an embedding row, and — more expensively — the model's output layer has to produce a score for every entry in the vocabulary at every step, so the final matrix multiply scales with vocabulary size. Real models sit between 32,000 and 200,000: GPT-2 used 50,257, GPT-4's cl100k uses 100,277, GPT-4o's o200k roughly doubles that. The trend is upward, and the reason is in the next section.

Here is the same paragraph, translated, measured with the real tokenizers that OpenAI ships:

The same content, the same meaning, and with cl100k the Russian version consumes two and a half times the tokens. Since APIs bill per token and context windows are measured in tokens, that is not a linguistic curiosity — it is a line in a budget, a shorter effective context window, and a slower response, all three at once, for everyone who does not work in English.

The mechanism is the training data. A tokenizer trained mostly on English spends its merge budget on English byte sequences. Spanish shares the Latin alphabet so it still gets some benefit; Russian gets almost none, because Cyrillic characters take two bytes in UTF-8 and few of those pairs were common enough in the training corpus to earn a merge. Japanese is worse still: three bytes per character, and 72 characters become 79 tokens — more tokens than characters.

The o200k column shows this is a solvable problem and that it is being solved. Doubling the vocabulary and rebalancing the training data cuts the Spanish overhead from +39 % to +16 %, and Russian from +152 % to +39 %. That is the real reason vocabularies keep growing: not compression for its own sake, but the fact that the previous generation was quietly charging a large fraction of the world extra.

Training produced an ordered list of merges. Encoding new text replays it — and it must replay it in the same order, because merge 12 combines the results of merges 5 and 1. Apply them in a different order and you get a different, wrong tokenization that will not match anything the model saw in training.

    def encode(self, text):
        ids = list(text.encode("utf-8"))
        while len(ids) >= 2:
            stats = get_stats(ids)
            # the pair whose merge came FIRST during training wins   
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))   
            if pair not in self.merges:
                break
            ids = merge(ids, pair, self.merges[pair])
        return ids

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

Decoding is trivial by comparison: look up each id's bytes, concatenate, decode as UTF-8. Note the errors="replace": a model can emit a token sequence that ends mid-character, and that is not a hypothetical — it is what happens when a streaming response is cut off in the middle of an emoji, which is why streaming APIs buffer partial bytes rather than decoding token by token.

Round-tripping works on anything, which is the promise of byte-level BPE:

'strawberry'                            -> 6 tokens, decode == original: True
'Alice was beginning to get very tired' -> 14 tokens, decode == original: True
'café — naïve — 日本語'                   -> 23 tokens, decode == original: True

Once the mechanism is clear, a set of unrelated-looking complaints turn out to be the same complaint.

Arithmetic. Numbers are not split in any consistent way:

1234     -> 2 tokens  ['123', '4']
12345    -> 2 tokens  ['123', '45']
1000000  -> 3 tokens  ['100', '000', '0']
3.14159  -> 4 tokens  ['3', '.', '141', '59']
2024     -> 2 tokens  ['202', '4']

To add 1234 and 12345 the model must first work out that ['123','4'] and ['123','45'] are numbers whose digits align in a particular way — and the alignment differs for every pair of numbers. The digits of a number are not in the same places from one number to the next. Some newer tokenizers force digits to split into consistent groups of three precisely to remove this obstacle, and models trained with those are measurably better at arithmetic.

Python indentation.

'    x = 1'      -> 5 tokens  ['   ', ' x', ' =', ' ', '1']
'        x = 1'  -> 5 tokens  ['       ', ' x', ' =', ' ', '1']
'\tx = 1'        -> 4 tokens  ['\tx', ' =', ' ', '1']

Four spaces and eight spaces are different single tokens, and a tab is fused with the character after it. Indentation, which in Python is syntax, is represented inconsistently — which is a large part of why models used to produce Python with subtly wrong indentation, and why code-focused tokenizers add explicit tokens for common indentation runs.

Spelling and reversing. Same cause as counting the r's: asking a model to reverse strawberry is asking it to reorder letters inside three opaque ids. Models do it by having memorised spellings during training rather than by looking, which is why they do it well for common words and badly for rare ones.

Glitch tokens. The most striking case is SolidGoldMagikarp and a set of similar strings that made GPT-2 and GPT-3 behave bizarrely — refusing to repeat them, producing unrelated output, sometimes insulting the user. The explanation is mundane and follows directly from the fact that the tokenizer is trained separately from the model: those strings were frequent in the tokenizer's training corpus (they were Reddit usernames), so they earned their own token, but were rare or absent in the model's training corpus. The result is an embedding row that was initialised randomly and almost never updated. The model has a symbol it has essentially never seen, and its behaviour there is whatever the random initialisation happened to be.

A tokenizer is a lossy interface between text and numbers, and every strange behaviour in this chapter is the interface showing through. It is worth being clear that the trade is deliberate: byte-level BPE means no input is ever unrepresentable, sequences are four to five times shorter than characters would be, and common words arrive intact.

The price is that the model's atoms are not our atoms. It reasons about text it cannot spell, in units chosen by a frequency count over a corpus it did not see, with a per-language cost that nobody negotiated.

You now have a sequence of integers. That is the input format for everything in the rest of Part II.

What you do not have is any reason for one integer to follow another. The next chapter introduces the objective that every language model is trained on, and it is startlingly simple: given the tokens so far, predict the next one. That single objective — no labels, no annotation, just text with its own future as the target — is what turns the entire internet into training data, and it is where the model's first genuine representations come from.

It also requires the chain rule of probability from Chapter 2 to be exactly right, because the claim that predicting one token at a time is the same as modelling whole documents is a factorisation, not a metaphor.

Chapter 8 is the autoregressive objective, embeddings, and the first place a model learns something nobody put there.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) introduces the Unigram model; Kudo and Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) is the implementation most multilingual models use; Schuster and Nakajima, Japanese and Korean Voice Search (ICASSP 2012) is the origin of WordPiece. Andrej Karpathy's Let's build the GPT Tokenizer and the accompanying karpathy/minbpe repository are the direct ancestors of the code in this chapter and go considerably further, including the GPT-4 regex and special-token handling. Chapter 6 of the Hugging Face LLM Course covers the three algorithms side by side with worked examples.