Tokenization

Chapter 2 ended with the embedding lookup: integer token IDs in, dense vectors out. Where those integer token IDs come from was a question we deferred.

This chapter answers it. A tokenizer sits between raw text, bytes on disk, characters on a screen, and the integer IDs that Chapter 2’s embedding layer can look up. Every modern language model has one of these somewhere upstream of the embedding table. The bridge looks inconsequential: a few hundred lines of code, a few kilobytes of data on disk, no learnable parameters once trained. It is also where most of the surprising behavior of large language models comes from.

By the end of this chapter, a reader who has been wondering why GPT-4 is bad at long-form arithmetic, why a Korean prompt costs more than the same English content on a per-token API, or what SolidGoldMagikarp was about will have answers. The answers are all the same word: tokenization.

Why tokenize

A neural network reads numerical tensors. Chapter 2 showed how to turn integer token IDs into the dense vectors that the rest of the network actually consumes: the embedding lookup is a row-indexing operation into a learnable matrix $E \in \R^{|V| \times d}$. The chapter started, however, with “given a sequence of token IDs,” and that handwave is the thing this chapter unwinds.

The upstream operation is tokenization. Its job is to take a string of bytes, raw input text, and produce a sequence of integers in $\{0, 1, \ldots, |V|-1\}$, the token IDs the embedding layer indexes. The mapping is deterministic and finite: every input string produces exactly one tokenized output, and the output is a sequence of IDs from a fixed vocabulary $V$.

The tokenizer is trained once on a representative corpus before the model itself is trained, then frozen for the model’s lifetime. It is not a layer that participates in backprop. Its “parameters”, the vocabulary, the merge rules, the regex used to split text, are written once and never updated. Once the model is trained, the tokenizer is part of the model’s contract with the world; you cannot swap it without retraining the model from scratch.

The choice of tokenizer shapes vocab size, sequence length, training cost, inference cost, and a surprising amount of downstream behavior: performance on numbers, asymmetry between languages, the model’s reaction to weird Unicode, and a long tail of edge cases the rest of the chapter walks through. Skipping it the way many tutorials do (treating the tokenizer as a black box that produces “tokens” and moving on) hides much of what makes LLMs feel idiosyncratic.

The two reflexive approaches to tokenization are word-level (one token per whitespace-separated word) and character-level (one token per character). Both fail in different ways, which motivates the subword tokenization that took over from 2015 onward.

Naïve attempts: character-level and word-level

The first reaction to “how do I turn text into integers” is one of two ideas. Both have appeared in real systems, and both have specific failure modes that motivated everything that came later.

Character-level: too long

Map each Unicode character to a unique integer. The vocabulary is the set of characters seen in training, anywhere from 26 (lowercase English letters) to roughly 150,000 (the full Unicode plane), depending on how aggressive you are about coverage.

The case for character-level is real. The vocabulary is small and bounded. Every possible input string is representable, no out-of-vocabulary problem to handle, no special unknown token to design around. Implementation is trivial: a lookup table from ord(char) to a small integer.

The case against is sequence length. Attention compute scales with $\text{seq}^2$ (Chapter 4 makes this precise), so doubling the sequence quadruples the compute. Character-level tokenization gives a sequence that is 4–5 times longer than a competitive subword tokenizer would, which is 16–25× more attention compute for the same content. The numbers are too unfavorable to ignore.

A context window of 4096 tokens, at one token per character, fits about 700 words of English, small enough that the entire chapter you are reading would not fit in one pass. The same 4096-token budget at GPT-4’s tokenizer fits roughly 3000 words. Character-level pays for its simplicity by inflating every sequence the model has to process.

Character-level tokenization still appears in narrow domains where the alphabet is small and structure matters at the character scale: some music generation models, some DNA models, the early ByT5 line. It does not appear in production text LLMs.

Word-level: too brittle

Split text on whitespace and punctuation; each word is a token. Vocabulary is the set of distinct words in the training corpus.

The pros are intuitive. Tokens carry meaning a reader can name. Sequences are short, one token per word is the natural unit. A 2010-era NLP researcher would recognize the representation immediately.

The cons are several, all serious. Vocabulary explosion: every new corpus has new words, so the vocabulary is effectively unbounded. Truncating to a fixed top-$|V|$ words by frequency leaves a long tail of rare words unrepresented. Out-of-vocabulary at inference: any word in the prompt that did not appear during training becomes a special <UNK> token; the model has lost the actual content of that position. Morphological brittleness: a word-level tokenizer trained on English treats walk, walks, walked, walking as four unrelated tokens; it has no representation that lets them share structure. Finnish or Turkish, with hundreds of inflected forms per stem, breaks the scheme entirely. Code and punctuation: where do {, }, def, return, and __init__ go? They are not whitespace-separated words in any natural sense.

The OOV problem is the killer. A model whose prompt contains an <UNK> has lost the relevant content; whatever ability it had to model that word at that position is gone.

The fix that took over from 2015 onward is subword tokenization: split words into pieces. Frequent words become single tokens; rare words become several tokens, ideally along morpheme-like boundaries (unhappiness → un + happi + ness). The vocabulary is fixed at training time but covers an effectively unbounded input space through composition. The dominant algorithm is BPE.

BPE: byte-pair encoding

Byte-pair encoding is the dominant subword tokenization algorithm. It was invented in 1994 by Philip Gage as a compression algorithm, a way to shrink files by replacing the most frequent byte pairs with new codes. Sennrich, Haddow, and Birch (2015, arxiv.org/abs/1508.07909) noticed the same idea works as a tokenizer: instead of compressing bytes for storage, compress them into the vocabulary of a language model. GPT-2, GPT-3, GPT-4, LLaMA, Mistral, and most of the modern open-source landscape use some variant of it.

The merge-greedy idea

Start with a base alphabet, one token per character, or one token per byte, depending on the variant. Look at the corpus. Find the most frequent adjacent pair of tokens. Replace every occurrence of that pair with a new single token; add it to the vocabulary. Look at the corpus again, now slightly different, because some pairs have collapsed. Find the new most-frequent pair. Repeat until the vocabulary reaches the desired size.

The intuition is straightforward. The most frequent pairs are mostly things like t+h, i+n, e+r, building blocks of common English bigrams. After a few merges, you have tokens for th, in, er. After a few hundred, you have the, ing, tion, and. After a few thousand, frequent whole words like the, of, and with are single tokens. Rare words and made-up proper nouns are several tokens each, falling back on subword and ultimately byte-level pieces.

Two implementations matter, both short and both worth seeing.

Training: count, merge, repeat

Given a corpus and a target vocab size $V$, BPE training produces an ordered list of merge operations $[(a_1, b_1) \to c_1, (a_2, b_2) \to c_2, \ldots]$, plus the resulting vocabulary. The loop:

1. Pre-tokenize the corpus into “word-units” (the regex split that section 6 introduces). Within each word-unit, split into base tokens, bytes or characters.
2. Build a frequency table over distinct word-tuples: many copies of the same word in the corpus collapse to one entry with a count, which keeps the inner loop fast.
3. Iterate. Each iteration: count every adjacent pair across all word-tuples (weighted by frequency), find the most-frequent pair, create a new token by concatenating the pair, and rewrite every word-tuple to replace that pair with the new token. Repeat until the vocabulary reaches $V$ tokens.

The merge criterion at each step is

with ties broken by some deterministic rule (lexicographic on the byte representation is the conventional choice). After picking $(a^*, b^*)$, the algorithm creates the new token $c = a^* \mathbin{+\!\!+} b^*$ (string concatenation), adds it to the vocabulary, and rewrites the corpus.

Encoding: greedy by learned order

Encoding takes a new piece of text and the trained merge list and produces a sequence of token IDs:

1. Pre-tokenize the input into word-units with the same regex used at training time.
2. For each word-unit, split into base tokens (bytes or characters).
3. Repeatedly scan for adjacent pairs that match any of the learned merges. Among matching pairs, apply the one with the lowest merge index, the merge learned first during training. Repeat until no learned pair is present.

A toy example

Train BPE on a tiny corpus and watch the first few merges emerge. The corpus is the kind that fits in a tweet, a handful of sentences with repeated tokens, chosen to make the first merges easy to read off.

The runnable block below implements the training loop on a longer toy corpus. It runs in Pyodide in roughly 100 ms; the first few merges show common bigrams collapsing into single tokens.

The first merge on this corpus is t + h, because the appears five times, tying t+h, h+e, and a+t for the most frequent adjacent pair; the code’s deterministic tiebreak (lexicographic on the byte pair) picks t+h first. The second is th + e, collapsing the into a single token. From there, common bigrams in the corpus get pulled together in roughly frequency order. With a larger corpus, the same algorithm produces the vocabularies that ship with GPT-2 and LLaMA, same loop, different scale.

Decoding: bytes back out

The merges list trained above is enough to encode; decoding, going back from token IDs to text, is its mirror image. Look up each ID’s byte string in the vocabulary and concatenate them in the order they occur. The result is a single byte string; UTF-8-decoding it recovers the original text.

Every vocabulary entry, by construction, is itself a concatenation of smaller byte strings all the way down to the base 256 single bytes. Concatenating the vocabulary entries for any sequence of token IDs the encoder could actually produce always yields a valid, complete byte string, so the whole pipeline is lossless: decode(encode(text)) == text for every string in the input space, not just the training corpus. This is the round-trip guarantee that makes tokenization safe to treat as a reversible preprocessing step rather than a lossy one.

The failure at the end of that block is not a bug, it is the reason production decoders never decode token-by-token. A streaming chat completion emits token IDs one at a time; if a multi-byte Unicode character happens to be split across two tokens (café’s é is two bytes, \xc3\xa9, and BPE has no obligation to keep character boundaries intact when it merges bytes), decoding the first of those two tokens in isolation produces an invalid UTF-8 sequence. Real streaming implementations buffer raw bytes across token boundaries and only attempt a UTF-8 decode once they have a complete character, exactly the pattern OpenAI’s and Anthropic’s streaming APIs use under the hood.

There is a problem with the training loop above, independent of decoding. The base alphabet is bytes, which sidesteps an issue character-level BPE has with Unicode.

Byte-level BPE: handling all unicode

Character-level BPE has a subtle but fatal problem at inference time. The base vocabulary contains every character seen during training. If a user prompt contains a character the training corpus never saw (a Korean syllable for an English-trained tokenizer, a Cyrillic letter for a Chinese-trained one, a math symbol for a tokenizer trained on tweets), the encoder has no token for it. The character is genuinely out-of-vocabulary, and the same <UNK> problem that doomed word-level tokenization reappears at the character scale.

Radford et al. (2019, the GPT-2 paper) fixed this with one decision: operate on UTF-8 bytes, not on characters. UTF-8 is a variable-length encoding in which every Unicode character, every emoji, every Hangul syllable, every Arabic letter, every CJK ideograph, is represented as a sequence of one to four bytes. The total alphabet is 256 (every possible byte value), and every string is convertible to bytes losslessly. The base vocabulary of a byte-level BPE is the 256 bytes, with $V - 256$ learned merges on top.

The consequence is immediate: there is no OOV. Any string the user types decomposes into bytes, every byte is in the vocabulary by construction, and BPE merges combine them into whatever tokens the training distribution has provided. A string in a language the tokenizer never saw still encodes; it just encodes inefficiently, with many tokens per character, because no merges learned during training apply.

BPE on bytes is otherwise the same algorithm as BPE on characters. The training loop is identical (count adjacent pairs, merge the most frequent, repeat); the encoder is identical (apply merges in learned order). Only the base alphabet changes. Modern tokenizers (GPT-2, GPT-3, GPT-4, LLaMA, Mistral, Code Llama) all use byte-level BPE in some form.

The trade-off is the asymmetry between languages. UTF-8 represents ASCII characters in one byte each, so English text averages roughly one byte per character before merges. Korean characters take three bytes each in UTF-8; Hindi characters take three; emoji take four. Before any merges learn to combine them, the same number of “characters” produces three or four times as many tokens in those languages.

Merges learned during training partially close the gap. A tokenizer trained on a corpus that contains substantial Korean text will learn merges that combine the common three-byte sequences for high-frequency Korean characters, producing one or two tokens per character instead of three. But the training corpora for the major commercial tokenizers are dominated by English. The merges that do get learned for non-English languages cover only the most frequent character sequences, leaving the long tail of rare words and uncommon characters at full byte-per-character cost.

The structural result: an English prompt and a Korean prompt with the same character count produce very different token counts. English averages roughly 4 characters per token on GPT-4’s tokenizer; Korean averages around 1.5. The same 1000 characters of content becomes 250 tokens of English or 670 tokens of Korean. On per-token pricing, the Korean prompt costs nearly three times as much as the English one for the same information density.

BPE is one algorithm. WordPiece and SentencePiece are the two others that show up in production.

Other tokenizers: WordPiece and Unigram LM

BPE is not the only subword tokenization algorithm in production use. Two others appear in major model families and are worth being able to distinguish.

WordPiece is BPE with a different merge criterion. The algorithm structure is identical, initialize a base alphabet, iteratively merge token pairs, repeat until the vocabulary is full, but the scoring function for picking which pair to merge is different. BPE merges the pair that occurs most frequently in the corpus. WordPiece merges the pair that, when treated as a new token, most increases the corpus’s likelihood under a unigram language model. The pair score is roughly

which rewards pairs whose joint frequency is high relative to the product of their marginals, pairs that “really do” go together, rather than pairs that happen to co-occur because both halves are individually common.

In practice, WordPiece and BPE produce similar tokenizations on most inputs but disagree at the margins. WordPiece was introduced by Schuster and Nakajima (2012, “Japanese and Korean Voice Search”) for speech recognition, then popularized for neural machine translation by Wu et al. (2016, arxiv.org/abs/1609.08144, the GNMT paper), which is where BERT picked it up two years later. WordPiece is used by the BERT family, BERT itself, DistilBERT, MobileBERT, ELECTRA. BERT’s WordPiece tokenizer also uses a different convention for whitespace and word boundaries: subword continuation pieces are prefixed with ## (so tokenization might tokenize as token, ##ization), rather than including a leading space as part of the next token.

Unigram LM is a different algorithm entirely. Kudo (2018, arxiv.org/abs/1804.10959) starts not from a small alphabet that gets merged upward, but from a large candidate vocabulary that gets pruned downward:

1. Build a large initial vocabulary of subword candidates, typically every substring of every word in the corpus, up to a length limit.
2. Score each candidate as a unigram language model: how likely is the corpus under the assumption that each token is drawn independently from a multinomial over the vocabulary?
3. Iteratively remove the candidates whose removal hurts the corpus likelihood least, until the vocabulary reaches the target size.
4. At encoding time, find the segmentation of the input that maximizes the unigram likelihood.

Unigram LM has two useful properties BPE lacks. First, the encoder is probabilistic in a way that admits multiple valid segmentations per input, a feature called subword regularization, used as a form of data augmentation during model training. Second, the algorithm naturally supports byte fallback: if a word cannot be segmented from the learned vocabulary, fall back to its raw bytes, guaranteeing no-OOV in the same way byte-level BPE does. Unigram LM is used by T5, mT5, ALBERT, and XLNet.

Practical map of which model family uses which tokenizer:

• BPE / byte-level BPE: GPT-2, GPT-3, GPT-4, LLaMA, Mistral, Gemma, Code Llama, most open-source models
• WordPiece: BERT, DistilBERT, MobileBERT, ELECTRA
• Unigram LM: T5, mT5, ALBERT, XLNet

The three algorithms produce different segmentations of the same text. The string tokenization becomes ["token", "ization"] under one, ["token", "##ization"] under another, and ["▁token", "ization"] under a third (SentencePiece prefixes whitespace with ▁). Switching between them requires retraining the model from scratch; the embedding table is keyed to specific token IDs, the output projection is sized to a specific vocab, and every position in the training corpus is preprocessed by a specific tokenizer.

The three algorithms share one upstream step: the regex that breaks input text into “word-units” before subword tokenization proper. That step is the topic of the next section.

Pre-tokenization: the regex before the algorithm

The BPE description so far has assumed the input arrives as “a corpus split into words.” What “split into words” means is not obvious. Whitespace? Punctuation? Apostrophes? Newlines? The boundary between what and what’s? The boundary between def and (?

The answer is pre-tokenization: a regex-based step that runs before BPE proper and splits the input text into atomic word-units. BPE operates within each word-unit independently; it never merges across word-unit boundaries. Pre-tokenization is what keeps the and world from collapsing into a single the world token if that sequence happens to be frequent enough.

The GPT-2 paper introduced a specific pre-tokenization regex that has become the de facto standard for the GPT family and many other byte-level BPE tokenizers:

PAT = r"""'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+"""

Six alternatives, in order:

• 's|'t|'re|'ve|'m|'ll|'d, English contraction suffixes, always their own token.
• ?\p{L}+, a sequence of one or more letters, optionally preceded by a single space.
• ?\p{N}+, a sequence of one or more digits, optionally preceded by a single space.
• ?[^\s\p{L}\p{N}]+, a run of punctuation or symbols (anything that is not whitespace, letter, or digit), optionally preceded by a single space.
• \s+(?!\S), a run of whitespace not followed by a non-whitespace character (trailing whitespace at line end).
• \s+, any other run of whitespace.

The most consequential design choice is the optional leading space in the word, number, and punctuation alternatives. The pattern ?\p{L}+ greedily captures the space before a word as part of that word’s word-unit. So the input Hello world produces the word-units ['Hello', ' world'], with the second unit including its leading space. After BPE runs, Hello and world have different token IDs from Hello and world: the leading-space variants are distinct vocabulary entries.

This is the structural reason GPT-style tokenizers list the and the as different tokens. The space-prefix-token convention encodes word position information directly in the token ID: a token starting mid-sentence carries its leading space; a token at the start of a line does not. Models trained on this convention learn the distinction; it carries a small amount of positional information the model can use, without requiring any separate machinery to represent it.

Reading the output shows the leading-space convention in action: ' world', ' not', ' gonna', ' do', ' it', each with its leading space attached. The runs of punctuation and whitespace get their own units; the contractions ('m, 't) split off from their host word.

GPT-4’s tokenizer (the cl100k_base encoding shipped with tiktoken) uses a slightly different regex that keeps short numbers as single units and handles a broader set of Unicode categories. The conceptual structure is the same: split first, BPE second.

Special tokens

The BPE algorithm produces tokens from frequencies in the training corpus. Models need additional tokens for meta-events, boundaries, separators, document markers, that are not naturally words and therefore would not emerge from frequency-based merges. These are added to the vocabulary by hand, typically at the start or end of the ID range.

The common special tokens across modern LMs:

• <|endoftext|> (GPT-2 and GPT-3), marks the end of a document, used as a boundary token when concatenating multiple documents into a single training stream.
• <bos> and <eos> (beginning and end of sequence), start and stop markers used by many models.
• <pad>, padding token used to extend short sequences to a fixed length so they can be batched together. The loss is masked on padding positions so the model never trains to predict them.
• <unk>, unknown token, for tokenizers that can produce OOV. Byte-level BPE eliminates the need for one by construction.
• <|im_start|> and <|im_end|> (the “ChatML” convention used by ChatGPT and adopted by many open-source chat models), message boundaries that mark which turn belongs to which role in a multi-turn conversation.
• [CLS] and [SEP] (BERT), classifier input token and sequence separator, specific to the BERT family.

The model learns what each special token means the same way it learns what the means: by observing it in context during training. A <|im_start|> token has no inherent definition; its meaning comes from millions of training examples in which it preceded a chat turn. A model fine-tuned with a new special token whose ID was randomly initialized has to learn the embedding for that token from scratch, the rest of the model has no prior on what the new ID should mean.

This is the structural reason prompt formatting matters as much as it does. When a user sends a prompt formatted differently from how the model was trained (wrong special tokens, missing system message wrapper, leading-space convention reversed), the model is in a slightly off-distribution state. The behaviors that show up in that state were not directly trained for; they emerge from how the model generalizes. Sometimes the generalization is graceful and the model behaves nearly as well. Sometimes it is brittle and the model behaves erratically. The variance is what makes “exact prompt format matters” a load-bearing rule for production deployments.

The long tail of consequences

Tokenization is an algorithm, but its consequences are empirical, and they show up in places that have nothing to do with tokenization on the surface. Four examples are vivid enough to make the abstract claim “tokenizer choices shape model behavior” feel concrete.

Number tokenization and arithmetic

GPT-2’s BPE tokenizer splits the string " 1234" (a number as it would appear mid-sentence, with its leading space) into the tokens [' 12', '34']. The longer string " 1234567" fragments further, into [' 123', '45', '67']. Short, common numbers fare better: 17 and 432 each survive as a single token. The exact split depends on which digit sequences happened to be frequent in the BPE training corpus, completely arbitrary from the perspective of arithmetic.

A model whose tokenizer fragments numbers this way does not see 1234 as a single quantity. It sees a sequence of two or three tokens whose joint meaning has to be reconstructed by attention. Multiply 432 by 17 becomes a problem in which the model first has to figure out that ' 432' is one token whose “value” is the integer 432, that ' 17' is one token whose “value” is the integer 17, and then perform multiplication, all in a representation that was not designed for it.

The empirical consequence is that GPT-2 and GPT-3 were notably bad at multi-digit arithmetic. GPT-4 improved partly by adopting a tokenizer (cl100k_base) that keeps 1-, 2-, and 3-digit numbers as single tokens; longer numbers still split, but more consistently and along digit-count boundaries. The model still makes arithmetic errors on long numbers, and tokenization is a substantial part of the reason. It is not the only reason; multi-step arithmetic also stresses the model’s ability to track intermediate state. But the tokenizer puts a structural ceiling on how cleanly the model can represent numerical inputs in the first place.

Code tokenization

Source code has a byte distribution nothing like prose: long runs of repeated indentation whitespace, symbols like {, }, ->, ::, __init__, and identifiers in camelCase or snake_case that a natural-language pre-tokenizer was never designed to split sensibly. Recall the GPT-2 pre-tokenization regex from the earlier section on pre-tokenization: it captures at most one leading space per word-unit ( ?\p{L}+), so a run of leading spaces longer than one has to be consumed by the whitespace alternatives before the word starts. On a corpus with little code in it, those whitespace runs get no dedicated merges, and every extra space in a Python indent costs its own token.

That is exactly what happens to GPT-2. Its BPE training corpus, WebText, was scraped from Reddit-linked web pages and contains very little code, so it never learned a merge for “four spaces” or “eight spaces” as a unit. Encoding a short, doubly-indented Python function with the real GPT-2 tokenizer gives one token per space of indentation:

def foo(x):
    return x + 1

def bar(y):
        return y * 2

GPT-2 tokenizes this snippet into 32 tokens, ten of which are the single-space token ' ' (id 220), one per indentation space beyond the space that attaches to return. cl100k_base, GPT-4’s tokenizer, tokenizes the same snippet into 21 tokens: the four-space indent collapses into one token (' ', three spaces, the fourth folded into the following word-unit as ' return') and the eight-space indent collapses into a second single token (' ', seven spaces). cl100k_base’s training mixture included far more source code (OpenAI’s Codex line of models was trained specifically on code, and cl100k_base inherited a vocabulary shaped by that mixture), so it learned dedicated tokens for the whitespace runs that Python indentation actually produces.

The gap is not really about whitespace specifically; it is the general pattern from the rest of this chapter. BPE has no notion of “this is code” or “this is an indentation level,” only frequency statistics over byte sequences. A tokenizer trained on prose-heavy data mishandles code the same way an English-heavy tokenizer mishandles Korean: not because the algorithm is wrong, but because the training corpus never gave it the merges the domain needs. Both problems have the same fix, more representative training data, and the same practical consequence, more tokens and thus more compute for underrepresented content.

Language asymmetry

The byte-level BPE asymmetry from section 4 has a direct economic consequence. English content averages around 4 characters per token under cl100k_base. Korean averages around 1.5. Hindi averages around 1.7. Arabic averages around 1.8. The same content in Korean costs roughly 2.7× more per character than the same content in English on per-token API pricing.

The asymmetry exists because BPE training corpora are dominated by English and other high-resource European languages. The tokenizer learns efficient merges for the bigrams that dominate those corpora; the merges for other languages are sparser, so non-English text bottoms out closer to the raw-byte representation. Petrov et al. (2023, arxiv.org/abs/2305.15425) measured this across 17 tokenizers and confirmed the pattern across nearly every language other than English.

The downstream effects are several. Non-English users pay more per character of input on commercial APIs. Their effective context window, measured in characters of content, is shorter. Their inference latency is higher (more tokens to attend over). And the model’s quality on those languages tends to lag, because the same character of training data produced more tokens of supervision in English but fewer elsewhere.

Glitch tokens

SolidGoldMagikarp was a Reddit username that appeared frequently in the corpus used to train GPT-2’s tokenizer. BPE assigned it a dedicated token ID. By the time GPT-2 itself was trained, on a different, more curated corpus, the username had been filtered out. The embedding row for that token ID existed in the model’s embedding table but was never updated by training. It remained near its random initialization for the model’s entire lifetime.

When prompts containing SolidGoldMagikarp reached GPT-2 and GPT-3, the model’s response was unpredictable, sometimes garbled, sometimes confidently wrong, sometimes a topic shift to gold or Pokémon. Rumbelow and Watkins (2023, the original LessWrong post) catalogued hundreds of similar “glitch tokens” in GPT-2 and GPT-3, orphaned vocabulary entries from rare Reddit usernames, gaming jargon, and other artifacts of the BPE training corpus that did not survive the model training corpus.

Modern tokenizers are more careful about this. The cl100k_base vocabulary used by GPT-4 has substantially fewer glitch tokens, partly because the BPE training corpus was filtered with more care and partly because the model training corpus was less aggressively divergent. But the class of problem is structural: BPE assigns tokens based on frequency in its own training data; the model assigns meaning based on frequency in its training data; when the two diverge, orphaned tokens remain.

The widget below shows the same input text tokenized under different tokenizers, with the token boundaries colored. The contrast between English, Korean, and code under GPT-2 and GPT-4’s tokenizers is the easiest way to see the consequences for yourself.

The comparison above is deliberately limited to three tokenizer families; WordPiece’s likelihood-based merge criterion is illustrated instead in Exercise 4 below.

The runnable block below uses a fresh BPE training on a number-heavy corpus to demonstrate the number-tokenization pattern. The exact split depends on the training corpus and the vocabulary size; the point is that BPE has no notion of numbers as a special category. They are just byte sequences whose tokenization is governed by frequency.

The numbers that appeared in the corpus tokenize cleanly. The numbers that did not appear fragment into multiple tokens whose split is determined by which byte pairs the BPE training happened to merge. 12345 is not “the number twelve thousand three hundred forty-five” to the model; it is some sequence of token IDs whose joint meaning has to be reconstructed by everything downstream.

Exercises

The exercises build on the chapter. Each is a self-contained problem with a starting template. Hints are collapsed by default; try the problem first.

Exercise 1 (easy): Examine BPE merges on a custom corpus

Train BPE on a small corpus of your choice (5–10 sentences) and examine the first 10 merges learned. Confirm that high-frequency character pairs in the corpus appear in the first few merges.

from collections import Counter, defaultdict

def train_bpe(words, vocab_size=270):
    word_freq = Counter(tuple(bytes([b]) for b in w.encode('utf-8')) for w in words)
    vocab = {bytes([i]) for i in range(256)}
    merges = []
    while len(vocab) < vocab_size:
        pair_counts = defaultdict(int)
        for word, count in word_freq.items():
            for i in range(len(word) - 1):
                pair_counts[(word[i], word[i+1])] += count
        if not pair_counts:
            break
        best = max(pair_counts, key=lambda p: (pair_counts[p], p))
        new_token = best[0] + best[1]
        vocab.add(new_token)
        merges.append((best, new_token))
        new_freq = {}
        for word, count in word_freq.items():
            new_word, i = [], 0
            while i < len(word):
                if i < len(word) - 1 and (word[i], word[i+1]) == best:
                    new_word.append(new_token); i += 2
                else:
                    new_word.append(word[i]); i += 1
            new_freq[tuple(new_word)] = count
        word_freq = new_freq
    return merges, vocab

my_corpus = [
    "the quick brown fox jumps over the lazy dog",
    "the dog barks at the fox",
    "a quick fox runs through the forest",
    "the forest is quiet and the dog is tired",
    "foxes and dogs rarely get along",
    "the lazy dog sleeps all day",
]
words = []
for sentence in my_corpus:
    words.extend(sentence.split())

merges, vocab = train_bpe(words, vocab_size=280)
for i, ((a, b), merged) in enumerate(merges[:10]):
    print(f"Merge {i+1}: {a!r} + {b!r} -> {merged!r}")

Merge 1: b't' + b'h' -> b'th'
Merge 2: b'th' + b'e' -> b'the'
Merge 3: b'f' + b'o' -> b'fo'
Merge 4: b'o' + b'g' -> b'og'
Merge 5: b'd' + b'og' -> b'dog'
Merge 6: b'r' + b'e' -> b're'
Merge 7: b'fo' + b'x' -> b'fox'
Merge 8: b'u' + b'i' -> b'ui'
Merge 9: b'q' + b'ui' -> b'qui'
Merge 10: b'z' + b'y' -> b'zy'

Exercise 2 (medium): Implement BPE encoding

After training BPE (exercise 1), implement the encoding function: given a new string, apply the learned merges in priority order to produce a sequence of tokens.

def encode_bpe(word, merges):
    tokens = [bytes([b]) for b in word.encode('utf-8')]
    merge_priority = {pair: i for i, (pair, merged) in enumerate(merges)}
    merge_map = dict(merges)

    while True:
        best_pair, best_priority = None, None
        for i in range(len(tokens) - 1):
            pair = (tokens[i], tokens[i+1])
            if pair in merge_priority:
                p = merge_priority[pair]
                if best_priority is None or p < best_priority:
                    best_priority, best_pair = p, pair
        if best_pair is None:
            break
        merged = merge_map[best_pair]
        new_tokens, i = [], 0
        while i < len(tokens):
            if i < len(tokens) - 1 and (tokens[i], tokens[i+1]) == best_pair:
                new_tokens.append(merged); i += 2
            else:
                new_tokens.append(tokens[i]); i += 1
        tokens = new_tokens
    return tokens

corpus = "the cat sat on the mat the dog sat on the rug the cat purred".split()
merges, vocab = train_bpe(corpus, vocab_size=270)

print(encode_bpe("hello", merges))  # [b'h', b'e', b'l', b'l', b'o']
print(encode_bpe("the", merges))    # [b'the']

Exercise 3 (medium): Quantify language asymmetry

Take the same BPE tokenizer (trained on English text in exercise 1) and tokenize three short sentences: one in English, one in Korean (use Google Translate if needed), and one in Russian. Report bytes-per-token for each. Comment on the result.

corpus = "the cat sat on the mat the dog sat on the rug the cat purred".split()
merges, vocab = train_bpe(corpus, vocab_size=270)

sentences = {
    'English': "the cat sat on the mat",
    'Korean':  "고양이가 매트 위에 앉았다",
    'Russian': "Кошка сидит на коврике",
}

for lang, text in sentences.items():
    n_bytes = len(text.encode('utf-8'))
    tokens = []
    for word in text.split():
        tokens.extend(encode_bpe(word, merges))
    n_tokens = len(tokens)
    print(f"{lang:8s} {n_bytes:3d} bytes, {n_tokens:3d} tokens, {n_bytes/n_tokens:.2f} bytes/token")

English   22 bytes,   7 tokens, 3.14 bytes/token
Korean    36 bytes,  33 tokens, 1.09 bytes/token
Russian   41 bytes,  38 tokens, 1.08 bytes/token

Exercise 4 (hard): Implement WordPiece

WordPiece is BPE’s likelihood-based cousin (used by BERT). Instead of merging the most frequent pair, WordPiece merges the pair that most increases the unigram language model’s likelihood. Implement a simple version: at each step, score each candidate pair by count(a, b) / (count(a) * count(b)) and merge the highest-scoring pair.

def train_wordpiece(words, vocab_size=270):
    word_freq = Counter(tuple(bytes([b]) for b in w.encode('utf-8')) for w in words)
    vocab = {bytes([i]) for i in range(256)}
    merges = []

    while len(vocab) < vocab_size:
        pair_counts = defaultdict(int)
        token_counts = defaultdict(int)
        for word, count in word_freq.items():
            for i in range(len(word)):
                token_counts[word[i]] += count
            for i in range(len(word) - 1):
                pair_counts[(word[i], word[i+1])] += count
        if not pair_counts:
            break

        def score(pair):
            a, b = pair
            return pair_counts[pair] / (token_counts[a] * token_counts[b])

        best = max(pair_counts, key=lambda p: (score(p), p))
        new_token = best[0] + best[1]
        vocab.add(new_token)
        merges.append((best, new_token))

        new_freq = {}
        for word, count in word_freq.items():
            new_word, i = [], 0
            while i < len(word):
                if i < len(word) - 1 and (word[i], word[i+1]) == best:
                    new_word.append(new_token); i += 2
                else:
                    new_word.append(word[i]); i += 1
            new_freq[tuple(new_word)] = count
        word_freq = new_freq

    return merges, vocab

corpus = "the cat sat on the mat the dog sat on the rug the cat purred".split()
bpe_merges, _ = train_bpe(corpus, vocab_size=270)
wp_merges, _ = train_wordpiece(corpus, vocab_size=270)

From tokens to attention

The pipeline is now complete. Text comes in; the tokenizer splits it into byte sequences using its pre-tokenization regex, runs BPE merges in learned order, and emits a sequence of integer token IDs. The embedding layer from Chapter 2 looks up the rows of $E$ corresponding to those IDs. The output is a sequence of dense vectors in $\R^{T \times d}$, ready for whatever the rest of the model wants to do with them.

What the rest of the model does, in every modern LLM, is attention. Each transformer layer takes the sequence of vectors from the layer below, lets every position look at every other position, and refines each vector based on what it sees. After twelve such layers (or seventy, or two hundred), the vector at position $t$ has absorbed information from every other position, the static input embedding has been turned into a context-dependent representation of “what the token at position $t$ means here.”

Sequence length is the dimension along which attention happens. The longer the sequence, the more positions each position has to attend to, and the more compute the attention step requires (it scales with $\text{seq}^2$, as Chapter 4 derives). Tokenization sets the sequence length for any given amount of text. A more efficient tokenizer, fewer tokens per character of content, means shorter sequences, which means cheaper attention. This is one reason an English-optimized tokenizer makes the model feel faster on English than on Korean: there is genuinely less compute per character of input.

Chapter 4 takes that sequence of embedded tokens as its starting point. The pre-tokenizer regex, the BPE merge table, the byte-level vocabulary, all the machinery from this chapter, disappears behind the words “given a sequence of token embeddings.” That handwave is the thing this chapter unwound. The next chapter does the same for attention.