AIM-03-001-P · Primer — Tokenization

The idea in one sentence

Tokenization converts a raw string into a sequence of integer ids by greedily matching pieces of a fixed subword vocabulary — it's the step that turns text into the only kind of input a neural network can actually consume.

Why it exists

A neural network has no native notion of "the English language"; it needs a finite, fixed-size list of symbols it can look up in an embedding table, the way an old printer's typecase holds only so many pre-cast letter blocks to compose a page. If you tokenized whole words, that typecase would need a block for every word ever written or that ever will be — including typos, invented names, and words in languages the model never trained on — effectively an infinite typecase, and any word missing from it becomes an unrecoverable "unknown token" hole in the text. If instead you tokenized single characters or raw bytes, the typecase shrinks to a few hundred blocks, but every sentence becomes a much longer sequence of pieces, burning far more of the model's limited context window and compute just to re-discover that "c-a-t" spells a common animal instead of seeing it as one unit. Subword tokenization is the engineered compromise: build a vocabulary of common whole words plus reusable fragments for everything else, so the typecase stays a manageable size (tens of thousands of entries) while sequences stay short, and no input can ever produce a symbol the model has never seen, because in the worst case it always falls back to individual bytes or characters, which are guaranteed to be in the vocabulary.

How it works

The dominant training mechanism is byte-pair encoding (BPE). Training starts from a base alphabet — for byte-level BPE, all 256 possible byte values — and then repeatedly scans the training corpus counting how often every adjacent pair of symbols occurs. The single most frequent pair is merged into one new symbol and added to the vocabulary, using the update rule \[(a^*, b^*) = \arg\max_{(a,b)} \; \text{count}(a, b)\] where \(\text{count}(a,b)\) is the number of times symbols \(a\) and \(b\) appear adjacent to each other anywhere in the corpus. This merge-and-recount loop repeats for a fixed number of rounds — 50,000 merges for GPT-2, taking its vocabulary from 256 bytes to 50,257 tokens (256 bytes + 50,000 merges + 1 special end-of-text token).

Work through two merge rounds on a tiny toy corpus to see the arithmetic: suppose the training text contains "low" 5 times, "lowest" 2 times, and "newer" 6 times, each word split into characters plus an end-of-word marker _ (so "low" → l o w _). Counting adjacent character pairs weighted by word frequency: (w,e) occurs 2 times inside "lowest" plus 6 times inside "newer" for a total count of 8 — the highest count of any pair (the next-highest, (l,o) and (o,w), each occur 5+2=7 times). So round one merges w+e into a new symbol we, giving updated sequences l o w _ (unchanged), l o we s t _, and n e we r _. Recounting pairs on these updated sequences, (l,o) now occurs 5+2=7 times — the new maximum (the next contenders, like (n,e) and (e,we), sit at 6) — so round two merges l+o into lo. After enough rounds like this, common English words such as "low" and "lower" collapse into single tokens while rare or novel words stay fragmented into several pieces.

Encoding new text at inference time does not re-run frequency counting; it applies the merges the training phase already learned, in the priority order they were learned, which is equivalent to greedily taking the longest known vocabulary piece at each position — exactly what this lab's encode function implements directly against a finished vocabulary. The resulting vocabulary size directly sets the size of the model's token-embedding table, \(E \in \mathbb{R}^{V \times d}\): GPT-2's \(V = 50{,}257\) vocabulary entries at \(d = 768\) dimensions is a 50,257 × 768 matrix, about 38.6 million parameters, before the model has processed a single token of context.

See it — BPE learns merges offline by counting pairs; encoding new text just applies those merges greedily, longest match first.

flowchart TD
    A["Training corpus"] --> B["Start vocab:<br/>256 byte values"]
    B --> C["Count all<br/>adjacent pairs"]
    C --> D{"Most frequent<br/>pair found?"}
    D -->|"Yes, merge it"| E["Add merged symbol<br/>to vocab"]
    E --> C
    D -->|"Target vocab<br/>size reached"| F["Final vocab +<br/>merge rules"]
    F --> G["New text: match<br/>longest piece first"]
    G --> H["Token ids,<br/>e.g. [1279, 2003]"]

The one gotcha

"Token" means neither "word" nor "character" — a common English word is often one token while a rare word, a typo, or an emoji can split into three or more, and non-English scripts routinely cost two to four times as many tokens as the "equivalent" English sentence, so token counts (and token-based pricing or context limits) don't track word counts or reading time the way people intuitively expect.

The one-line takeaway

Subword vocabularies trade sequence length for vocabulary size.

Where you'll meet it

Hugging Face tokenizers / AutoTokenizer (BPE, WordPiece); OpenAI's tiktoken library (cl100k_base, o200k_base encodings) and the token counts shown in the OpenAI and Anthropic API dashboards; Google's sentencepiece (used by T5, Llama, Gemini), which tokenizes raw text without assuming whitespace-separated words — important for Chinese, Japanese, and Thai.

Named concepts: tokenization