Tokenization

It is August 2015. Neural machine translation systems can only handle the words they saw during training — everything else collapses into a single unknown-word symbol. A short paper from Edinburgh proposes borrowing a merge trick from data compression, and in doing so quietly fixes the input layer of every large language model that follows. This chapter covers the layer almost nobody sees: how raw text becomes the integer sequences a transformer actually reads.

Where We Were

Every neural language model needs a vocabulary: a fixed, finite list of symbols it can read and emit. Through 2015 there were two obvious choices, and both were bad.

The first was word-level vocabularies. Models like word2vec assigned one vector per word (chapter 2), and the encoder–decoder translation systems of 2014 (chapter 3) inherited the same design: pick the 30,000–80,000 most frequent words, map everything else to a single <unk> token. This failed in predictable ways. Natural language has a long tail — names, numbers, typos, new coinages, and the rich inflection systems of languages like German, Russian, Turkish, or Finnish, where a single stem can surface in dozens of forms. A word-level system that had seen Regierung (government) still treated Regierungsverantwortung (governmental responsibility) as an unknown word. Translation systems papered over this with back-off dictionaries and copy mechanisms, but the core problem remained: the model’s world was closed, and language is open.

The second choice was character-level modeling: give the model an alphabet of individual characters and let it learn everything else. This eliminates unknown words by construction — any string decomposes into characters — but at a steep price. Sequences become several times longer, recurrent networks of the era struggled to carry information across the resulting distances, and compute per sentence grows with sequence length. Characters are also a semantically impoverished unit: the model must relearn from scratch that c-a-t forms a meaningful whole.

What the field needed was the middle ground: a unit larger than a character, smaller than a word, chosen so that common strings stay whole while rare strings decompose gracefully. Between 2015 and 2019 that middle ground was found, standardized, and pushed all the way down to raw bytes.

The tokenizer is trained separately from the model it feeds, on its own corpus, with its own objective; the last two cards are that seam showing. PNG ↓

The Breakthrough

Byte Pair Encoding for text, introduced in “Neural Machine Translation of Rare Words with Subword Units” (Sennrich et al., 2015), adapted a byte-level data-compression algorithm into a vocabulary learner. The idea is disarmingly simple. Start with a vocabulary of individual characters. Scan the training corpus and count every pair of adjacent symbols. Merge the most frequent pair into a single new symbol, add it to the vocabulary, and repeat. Each merge is recorded as a rule; after a few thousand iterations the vocabulary contains characters, common fragments like ing and tion, and eventually whole frequent words. The number of merges is the tokenizer’s only real hyperparameter — it directly sets the vocabulary size.

Every merge is greedy and local, but the recorded order is what lets the same procedure be replayed deterministically on text the trainer never saw. PNG ↓

At inference time the learned merge list is replayed deterministically on new text: split the input into characters, then apply the merges in the order they were learned. Any word the model has never seen decomposes into known subwords — in the worst case, into individual characters. The vocabulary is finite, but the set of representable strings is open. Sennrich et al. showed this was not just elegant but effective: on the WMT 15 translation tasks, subword models improved over a back-off dictionary baseline by 1.1 BLEU on English–German and 1.3 BLEU on English–Russian.

Google arrived at a closely related scheme independently. Its production translation system, GNMT (Wu et al., 2016), divided words “into a limited set of common sub-word units” — wordpieces — for both input and output, demonstrating in September 2016 that subword vocabularies worked at production scale, not just in research benchmarks. Wordpieces later became the tokenizer of BERT and its descendants (chapter 6).

The next conceptual step treated segmentation as a probabilistic modeling problem rather than a greedy procedure. Subword regularization (Kudo, 2018), from April 2018, observed that any given sentence admits many valid segmentations, and that committing to exactly one throws information away. Kudo proposed a segmentation algorithm based on a unigram language model: the vocabulary carries a probability for each token, a sentence’s segmentation score is the product of its token probabilities, and during training the model sees multiple segmentations sampled in proportion to their probability. The sampling acts as a regularizer — the same word arrives split differently across epochs, making the model robust to segmentation noise, with the largest gains in low-resource and out-of-domain settings.

Four months later came the tooling consolidation. SentencePiece (Kudo & Richardson, 2018) packaged both BPE and the unigram model into an open-source C++ and Python library with one decisive design change: it trains directly on raw sentences, with no language-specific pre-tokenization step. Earlier pipelines assumed text arrived pre-split into words — an assumption that quietly breaks for Japanese, Chinese, and Thai, which do not delimit words with spaces. SentencePiece instead treats the input as a raw character stream and escapes whitespace itself with the meta-symbol ▁ (U+2581), making tokenization fully lossless: detokenization is a simple string join followed by replacing ▁ with spaces, with no ambiguity about where spaces were. Kudo and Richardson validated the end-to-end approach on English–Japanese translation, showing accuracy comparable to pipelines that used a dedicated pre-tokenizer.

The final move went below characters entirely. GPT-2 (Radford et al., 2019), released in February 2019 (chapter 7), ran BPE over bytes rather than Unicode characters. A byte-level base alphabet has exactly 256 symbols and covers every possible input — every emoji, every script, every corrupted encoding — so an unknown token becomes structurally impossible. GPT-2’s vocabulary of 50,257 tokens (256 byte symbols, plus learned merges, plus one end-of-text token) became one of the most widely reused artifacts in the field, and byte-level BPE became the default recipe for the GPT lineage.

The transformer itself never sees text; tokenizer defects are invisible in the architecture diagram because they live entirely in the three steps before it. PNG ↓

The transformer itself (chapter 5) never sees text. It sees a sequence of integers, each mapped to a learned embedding vector. Everything in this chapter happens before the first attention layer — which is precisely why tokenizer defects are invisible in the architecture diagram and yet surface everywhere in model behavior.

The Mathematics

BPE’s training loop is a greedy frequency maximization. At each step, the algorithm selects the pair of adjacent symbols to merge:

(x^{*}, y^{*}) = \arg\max_{(x, y)} \ \mathrm{count}(x, y)

The unigram language model of Kudo (2018) replaces greedy merging with an explicit probabilistic model. A segmentation of a sentence is scored as the product of its token probabilities, and decoding picks the best segmentation:

P(\mathbf{x}) = \prod_{i=1}^{M} p(x_i), \qquad \mathbf{x}^{*} = \arg\max_{\mathbf{x} \in \mathcal{S}(X)} P(\mathbf{x})

A sentence $X$ can be chopped into subwords in many ways; $\mathcal{S}(X)$ is the set of all of them. One candidate segmentation $\mathbf{x} = (x_1, \ldots, x_M)$ is scored by multiplying together the probability $p(x_i)$ of each token it uses — tokens are assumed independent, which is what “unigram” means. The best segmentation $\mathbf{x}^{*}$ is the highest-scoring one, found efficiently with dynamic programming. What this buys you over BPE: because every segmentation has a probability, you can sample alternative segmentations during training (subword regularization) instead of always feeding the model the same split, and you can prune the vocabulary by deleting tokens that contribute least to total corpus likelihood.

Symbol	Meaning
$X$	The raw input sentence
$\mathcal{S}(X)$	The set of all valid segmentations of $X$
$\mathbf{x} = (x_1, \ldots, x_M)$	One candidate segmentation, a sequence of $M$ subword tokens
$p(x_i)$	Learned unigram probability of token $x_i$
$P(\mathbf{x})$	Score of the whole segmentation — product of its token probabilities
$\mathbf{x}^{*}$	The maximum-likelihood segmentation actually used

Finally, vocabulary size is not free. Every token in the vocabulary owns a row in the model’s embedding matrix (and, tied or not, in the output projection):

N_{\mathrm{embed}} = |V| \cdot d_{\mathrm{model}}

The efficiency of a tokenizer on a given text is usually summarized as its fertility — average tokens produced per word — or its compression rate in bytes per token. Two models with identical architectures but different fertility on your language are not paying the same price per sentence, a fact that resurfaces below.

What It Enabled

Subword tokenization removed the open-vocabulary problem as a blocker, and everything in Part II is downstream of that. The pretrain-then-finetune wave (chapter 6) trained on web-scale corpora (chapter 11) precisely because no string in those corpora could crash the input layer. The GPT lineage (chapter 7) standardized on byte-level BPE. And the idea of a learned discrete vocabulary escaped text entirely: VQ-VAE codebooks give images their own “tokens” (image-generation chapter 5), the foundation of the multimodal models covered in chapter 18.

	Word-level (pre-2015)	Character-level	Subword (2015–)
Unknown words	Collapse to `<unk>`	Impossible by construction	Impossible by construction
Typical vocabulary	30k–80k words per language	Dozens to hundreds of symbols	30k–250k shared units
Sequence length	Short	Very long	Moderate
Morphology and rare words	Lost	Learnable but slow	Decompose into meaningful parts
Multilingual sharing	Poor — separate vocabularies	Good	Good — shared subwords across languages

The individual algorithms settled into stable niches:

Scheme	Year	Selection criterion	Notable adopters
BPE (Sennrich et al., 2015)	2015	Greedy pair frequency	NMT systems; most GPT-family models
WordPiece (Wu et al., 2016)	2016	Corpus-likelihood-driven merges	GNMT, BERT family
Unigram LM (Kudo, 2018)	2018	Probabilistic segmentation, vocabulary pruning	Models trained with subword regularization
SentencePiece (Kudo & Richardson, 2018)	2018	Framework — implements BPE and unigram on raw text	Standard open-source tokenizer tooling
Byte-level BPE (Radford et al., 2019)	2019	BPE over a 256-byte base alphabet	GPT-2 and successors

The failure modes

The chapter’s subtitle promise — why tokenizers cause weird failures — comes down to one structural fact: the tokenizer is trained separately from the model, on its own corpus, with its own objective. The seams show.

Glitch tokens. If a string is frequent in the tokenizer’s training corpus but rare or absent in the model’s, the vocabulary contains a token whose embedding is essentially untrained — a reserved seat nobody ever sat in. Prompting a model with such a token produces unpredictable behavior, because the model is being asked to interpret a vector it never learned. The best-known specimen is the token SolidGoldMagikarp, a Reddit username that survived into GPT-2’s vocabulary; the phenomenon was later studied systematically in “Fishing for Magikarp” (Land & Bartolo, 2024), which showed such under-trained tokens exist across essentially all major model families and developed automated methods — inspecting tokenizer behavior and model embedding weights — to detect them before users do.

Character blindness. A model that reads strawberry as one or two opaque tokens has no direct access to its letters, which is why letter-counting, spelling, rhyming, and arithmetic on long digit strings fail in ways that seem bizarre for systems that write fluent prose. The cleanest evidence is comparative: ByT5 (Xue et al., 2021), a token-free byte-to-byte model from May 2021, showed byte-level models are “significantly more robust to noise and perform better on tasks that are sensitive to spelling and pronunciation” — at the cost of much longer sequences, traded against parameter count, training FLOPs, and inference speed. Tokenization, in other words, is a compression choice, and what it compresses away is exactly what character-level tasks need.

Language inequity. Because merge rules are learned from a corpus, the tokenizer is fluent in whatever that corpus over-represents — overwhelmingly English. “Language Model Tokenizers Introduce Unfairness Between Languages” (Petrov et al., 2023) measured the damage in May 2023: the same text translated into different languages can differ in tokenized length by up to 15×, and even character- and byte-level models show over 4× differences for some language pairs. Since commercial APIs bill per token, generate token by token, and cap context windows in tokens (chapter 16), a speaker of a poorly tokenized language pays more, waits longer, and fits less into the same model — for identical content.

Key Papers

Paper	Authors	Year	Link	Why it matters
Neural Machine Translation of Rare Words with Subword Units	Sennrich et al.	2015	arXiv:1508.07909	Adapted BPE from compression to text; solved open-vocabulary NMT with a 3-step merge loop
Google’s Neural Machine Translation System	Wu et al.	2016	arXiv:1609.08144	Wordpieces at production scale; the tokenizer lineage BERT inherited
Subword Regularization	Kudo	2018	arXiv:1804.10959	Unigram LM segmentation; sampling multiple segmentations as a regularizer
SentencePiece	Kudo & Richardson	2018	arXiv:1808.06226	Language-independent, lossless tokenization from raw text; the field’s standard tooling
Language Models are Unsupervised Multitask Learners	Radford et al.	2019	OpenAI report	Byte-level BPE with the 50,257-token vocabulary reused across the GPT lineage
ByT5: Towards a token-free future	Xue et al.	2021	arXiv:2105.13626	Byte-to-byte models; quantified the spelling-robustness cost of tokenization
Language Model Tokenizers Introduce Unfairness Between Languages	Petrov et al.	2023	arXiv:2305.15425	Measured up to 15× tokenization-length gaps across languages — cost, latency, and context inequity
Fishing for Magikarp	Land & Bartolo	2024	arXiv:2405.05417	Systematic detection of under-trained glitch tokens across model families

PM Lens

I treat the tokenizer as a pricing document. Every LLM API I have evaluated bills per token, not per word or per character — so the tokenizer, not the list price, decides what a feature actually costs. When I scoped a multilingual assistant, the Petrov et al. finding was the number that mattered: identical content can tokenize at up to 15× the length across languages, which means my cost model and latency budget for Hindi or Thai users could be multiples of the English case on the same model. Now I benchmark fertility on our own production text — support tickets, product names, code snippets — before committing to a provider, because vocabulary fit varies more than quality benchmarks suggest. Two practical checks I run: paste representative non-English and code-heavy samples into the provider’s token counter and compare counts across candidate models; and confirm the advertised context window in my language, not English. And when a model behaves bizarrely on a specific string — a username, a SKU, a rare Unicode sequence — I check the tokenizer before filing a model bug. It is usually the tokenizer.

Search