Tokenization (BPE & friends)

The unglamorous layer everyone skips — and then spends a week debugging. A transformer ([[attention-and-transformers]]) does not read text. It reads a sequence of integers, each of which indexes into a learned vector ([[embeddings]]). Tokenization is the lossy, hand-built, non-neural function that turns a Unicode string into those integers. It sits before the model, it is not trained by gradient descent, and a surprising fraction of "the LLM is dumb" moments — can't spell, can't count letters in strawberry, botches arithmetic, randomly melts down on SolidGoldMagikarp — trace straight back to here. Karpathy calls it the "least glamorous and most under-appreciated" stage; this article gives it the respect (and the scrutiny) it deserves.

What it is (intuition first)

A language model works on a fixed vocabulary of, say, 50,000 to 200,000 symbols called tokens. Before any text reaches the network, a tokenizer chops the string into a sequence of these tokens and looks up each one's integer ID. After the model generates token IDs, the same tokenizer maps them back to text. So the contract is just two functions:

encode(str) -> [int]
decode([int]) -> str

The only interesting question is: what should the tokens be? You have three obvious extremes, all bad:

One token per word. Vocabulary explodes (millions of words across languages), and any word you didn't see in training (anti-disestablish..., a typo, a new product name) becomes a single <UNK> "unknown" hole — the model literally cannot represent it.
One token per character. Vocabulary is tiny (~100) and nothing is ever unknown, but sequences become enormously long. Attention cost is quadratic in sequence length ([[attention-and-transformers]], [[flash-attention]]), so per-character text burns context budget and compute, and the model must spend capacity re-learning that t-h-e is a unit.
One token per byte. Same length problem as characters, slightly worse for non-ASCII.

Subword tokenization is the pragmatic middle. Common words (the, dog) get their own single token; rare words get split into reusable pieces (tokeniz + ation, un + believ + able). You get a small, fixed vocabulary, zero out-of-vocabulary failures (worst case, you fall back to single bytes/characters), and reasonably short sequences. The dominant recipe for finding those pieces is Byte-Pair Encoding (BPE), with cousins WordPiece (BERT) and Unigram (T5, many multilingual models).

The mental model to keep: a token is roughly ~4 characters / ~0.75 words of English on average — but that average hides wild variance, and the variance is where the bugs live.

Why it matters

Tokenization is upstream of everything, which makes its decisions sticky and its failures non-obvious:

It sets the sequence length → directly drives compute cost, context-window usage, and latency. A more efficient tokenizer (fewer tokens per document) is a free throughput and cost win. (This is also why YAML tokenizes more efficiently than JSON for LLMs — fewer structural tokens — a real prompt-design lever, per Karpathy.)
It is frozen at pre-training time. The vocabulary and merge rules are baked into the model's input embedding matrix and output head. You cannot change the tokenizer of a trained model without retraining/grafting. Choices made on day one of pre-training haunt the model forever.
It is the silent cause of "stupid" failures. Karpathy's list, almost verbatim: Why can't an LLM spell words? Tokenization. Why can't it reverse a string? Tokenization. Why is it worse at non-English? Tokenization. Why is it bad at simple arithmetic? Tokenization. Why did it halt on `SolidGoldMagikarp`? Tokenization. (fast.ai recap of "Let's Build the GPT Tokenizer").
It taxes some languages more than others. Because vocabularies are trained on mostly-English/code corpora, the same sentence in (say) Burmese or Telugu can cost 5–10× more tokens than its English translation — so non-English users pay more, fit less in context, and the model has effectively shorter memory for them. Tokenization inequality is a real fairness issue, not a rounding error.

The honest one-liner: tokenization is a non-differentiable, hand-engineered bottleneck that the rest of the beautifully-trained network is forced to live with. Understanding it is the difference between "the model is broken" and "the input encoding is biting me."

How it works (the real mechanics)

Byte-Pair Encoding — the core algorithm

BPE was originally a data-compression algorithm (Gage, 1994) and was re-purposed for NLP word segmentation by Sennrich, Haddow & Birch (2015), "Neural Machine Translation of Rare Words with Subword Units" (arXiv:1508.07909). Their result: encoding rare words as sequences of subword units beat dictionary back-off baselines by +1.1 BLEU (En→De) and +1.3 BLEU (En→Ru) on WMT15 — because names transfer by copy/transliteration, compounds by composition, and cognates by morphological pieces, all of which subwords capture and whole-word vocabularies don't.

Training (learning the merges). You start with a base vocabulary and iteratively merge the most frequent adjacent pair:

Base vocab = every individual symbol in the corpus (every character, or — for byte-level BPE — all 256 byte values).
Count pairs. Across the whole corpus, count how often each adjacent pair of current tokens occurs, weighted by word frequency. If the word low appears 5 times and is currently l o w, then the pairs (l,o) and (o,w) each get +5.
Merge the most frequent pair. Take the top pair, mint a new token for it, give it the next free ID (256, 257, 258, …), and record the merge rule (A, B) -> AB. Replace every adjacent A B in the corpus with the new token.
Repeat until you hit the target vocabulary size.

minbpe's toy example makes it concrete: training on the string "aaabdaaabac" with 3 merges allocates the 256 byte tokens, then learns merges that compress the string; "aaabdaaabac" encodes to [258, 100, 258, 97, 99] and decodes back exactly. In a 32,768-token vocab: IDs 0–255 are raw bytes, 256–32,767 are learned merges, and special tokens start at 32,768+.

Encoding (applying the merges). Tokenizing new text is mechanical: split into the base symbols, then apply the learned merge rules in the order they were learned, greedily, until none apply. The merge order is the model — it's a deterministic priority list, not a search. Pseudocode-in-prose:

Represent the word as a list of bytes. Look at all adjacent pairs; among the pairs that have a merge rule, pick the one with the lowest merge-rank (i.e. learned earliest); apply it; repeat until no adjacent pair has a rule.

Decoding is trivial: concatenate each token's stored byte-string and (for byte-level) UTF-8-decode. Note the asymmetry — decode is a lookup, encode is an iterative greedy reduction.

Byte-level BPE (the GPT-2/GPT-4/tiktoken trick)

Naïve character-level BPE has an ugly edge: what's your base vocabulary when the corpus is all of the internet and contains every Unicode code point and emoji? GPT-2's answer (Radford et al., 2019), adopted by GPT-3/4 and tiktoken: run BPE over raw UTF-8 bytes, not Unicode characters.

Base vocabulary is exactly 256 bytes — universal, finite, and you can never hit an unknown character. Any string in any language/script is guaranteed representable (worst case, byte-by-byte).
This is why a single emoji or a rare CJK character can cost several tokens: it's 3–4 UTF-8 bytes, and if those byte-pairs weren't frequent enough to earn a merge, they stay split.

Karpathy considers byte-level "significantly cleaner" than SentencePiece's alternative (BPE over Unicode code points with a byte fallback only for rare chars). minbpe is built byte-level on purpose.

Pre-tokenization: the regex split (and why it exists)

If you ran BPE on raw text with no constraints, it would happily learn a single token for dog. and a different one for dog! and dog?, wasting vocabulary and entangling words with punctuation. So GPT-2 introduced a pre-tokenization regex that first chops text into chunks (letters, numbers, punctuation, whitespace runs) and forbids merges from ever crossing chunk boundaries. BPE then runs within each chunk independently. minbpe's RegexTokenizer replicates this; the split pattern "originated in the GPT-2 paper and remains standard through GPT-4."

GPT-4's pattern (the cl100k_base split) fixed several GPT-2 warts:

Case-insensitive contractions — GPT-2's pattern only matched lowercase 's 't 're, so HOW'S split badly. GPT-4 handles uppercase + Unicode apostrophes.
Numbers capped at runs of 1–3 digits ("numbers require... merging limited") — preventing the tokenizer from minting bespoke tokens for 2017, 8675309, etc., which (a) wastes vocab and (b) gives every long number an arbitrary, inconsistent chunking. This is a deliberate band-aid for the arithmetic problem below.
Better whitespace/newline handling for code.

WordPiece (BERT) — the merge-by-likelihood variant

WordPiece (Schuster & Nakajima 2012; used by BERT) trains almost like BPE but changes the merge-selection criterion. Instead of merging the most frequent pair, it merges the pair that most increases corpus likelihood, scored as:

score(A, B) = freq(AB) / ( freq(A) * freq(B) )

This penalizes merging a pair just because both halves are individually common (a frequent A and frequent B inflate the denominator), and rewards pairs that occur together more than chance would predict. WordPiece also marks intra-word continuations with a ## prefix (token, ##ization) and, at encode time, does greedy longest-match-first from the start of each word (unlike BPE's learned-merge-order replay).

Unigram LM (SentencePiece / T5) — top-down, probabilistic

Unigram (Kudo 2018, "Subword Regularization," arXiv:1804.10959) flips the whole approach. BPE/WordPiece grow a vocab bottom-up; Unigram starts huge and prunes down, and it's genuinely probabilistic.

It assumes a unigram language model over subwords: every token x has a probability p(x), and the probability of a segmentation (x₁,…,x_k) of a word is just the product of token probabilities (each token independent of context):

P(segmentation) = ∏ p(x_i)

The best segmentation of a word is the one maximizing that product — found efficiently with the Viterbi algorithm over a lattice of all possible splits (branch from position a to b if the substring a..b is a vocab token; find the highest-scoring path; backtrack). Training minimizes the negative log-likelihood of the corpus:

Loss = Σ_over_words  −log P(word)
       = Σ_words  −log ( Σ_over_segmentations  ∏ p(x_i) )

(log-space because multiplying many small probabilities underflows). Vocabulary construction:

Seed an oversized candidate vocab (e.g. all frequent substrings).
EM step: fix the vocab, estimate each p(x) (re-estimate token probabilities to fit the corpus).
Prune: for each token, compute how much the total Loss would rise if it were removed; drop the bottom p% (≈10–20%) with the smallest loss increase. Always keep single characters so everything stays tokenizable.
Repeat EM + prune until you reach the target size.

Unigram's signature trick is subword regularization: because it's probabilistic, at training time you can sample different segmentations of the same word (not just the single best one), exposing the model to ["tokeniz","ation"] and ["token","ization"] and making it robust to segmentation noise — a data-augmentation win that deterministic BPE can't do cleanly.

Note on naming: SentencePiece (Kudo & Richardson, 2018) is the library / framework — it implements both a BPE mode and a Unigram mode, treats input as a raw stream (encoding spaces as a visible ▁ marker so detokenization is reversible and language-agnostic), and is what T5, LLaMA, and most multilingual models use. People sloppily say "SentencePiece tokenizer" when they usually mean "SentencePiece in Unigram mode." Don't conflate the algorithm (Unigram/BPE) with the toolkit (SentencePiece) or with the tiktoken library (OpenAI's fast byte-level BPE).

Family cheat-sheet

Algorithm	Direction	Merge/keep criterion	Encode-time	Used by
BPE	bottom-up merge	most frequent adjacent pair	replay merges in learned order	GPT-2/3/4, RoBERTa, tiktoken
WordPiece	bottom-up merge	max `freq(AB)/(freq(A)·freq(B))`	greedy longest-match	BERT, DistilBERT
Unigram	top-down prune	min loss-increase if removed; probabilistic	Viterbi best (or sampled) path	T5, LLaMA, ALBERT (via SentencePiece)

Key ideas & tradeoffs

Vocabulary size is a dial, not a free lunch. Bigger vocab → shorter sequences (cheaper attention, more text per context window) and more whole words get single tokens → but a larger embedding matrix and softmax head (more parameters and compute spent at the input/output), and rarer tokens get fewer gradient updates (under-trained embeddings — see glitch tokens below). Modern frontier models drifted up (GPT-2: 50,257 → GPT-4 cl100k: ~100,256 → o200k: ~200k) as the efficiency win on long/non-English/code text won out.
Greedy ≠ optimal. BPE's encode is greedy merge-replay; it does not guarantee the fewest-tokens segmentation. Unigram's Viterbi is optimal under its own probability model, which is itself an approximation. Nobody is solving the "true" optimal segmentation — these are all heuristics that work well enough.
The whitespace convention is load-bearing. GPT-style tokenizers attach the leading space to a word: " dog" is one token, distinct from "dog". This is why a trailing space in your prompt can wreck generations — you've split off a token the model rarely saw in that position, knocking it "off-distribution."
Multilinguality is a vocab-budget allocation problem. Every token you spend on English merges is a token not spent on Hindi or code. Tokenizer fairness = who you trained the merges on. There is no neutral choice.
Tokenizers are an attack surface & a leakage surface. Special tokens (<|endoftext|>) bypass normal BPE; if user text containing those literal strings is tokenized with allowed_special="all", you get prompt-injection via token smuggling. minbpe's allowed_special ("all"/"none"/explicit set) exists precisely to make you choose deliberately on untrusted input.

Honest caveats & open questions

Why can't LLMs spell / reverse strings / count letters? Because the model sees strawberry as maybe 2–3 opaque tokens, not as a sequence of characters. The letters are inside the token's embedding, not laid out for the model to index. Counting "r"s in strawberry requires un-fusing information the tokenizer fused — which is why even GPT-4 with chain-of-thought still trips on short words (arXiv:2410.19730, "Counting Ability of LLMs and the Impact of Tokenization"). The mismatch is between the unit you want to count (letters) and the unit the model processes (BPE tokens).
Why is arithmetic flaky? If 327 and 4815 tokenize into inconsistent chunks, the model can't reliably align digit places to add them. GPT-4's "numbers ≤ 3 digits" regex is a partial fix; some models (e.g. the Llama line) force per-digit tokenization for exactly this reason. arXiv:2505.14178 ("Tokenization Constraints in LLMs") argues there are tasks provably unsolvable under certain tokenization schemes regardless of how big the model gets — tokenization is a fundamental, not just empirical, limit on symbolic reasoning.
Glitch tokens / `SolidGoldMagikarp`. A token can be frequent in the tokenizer-training corpus but absent from the model-training corpus — e.g. a Reddit username scraped for vocab counts but filtered out of LM training. Its embedding then never gets trained, stays near its random init, and the model behaves erratically when it appears: refusal, topic-drift, hallucination, evasion. (Glitch token — Wikipedia; GlitchMiner, arXiv:2410.15052, even gradient-mines them automatically.) The root cause is a pipeline mismatch: the tokenizer and the model are trained on different data and nobody checks the intersection.
Is tokenization-free the endgame? Maybe. A 2023 line of work (MEGABYTE, ByT5-style, and "hierarchical" byte models) feeds raw bytes into a multi-scale transformer and concludes tokenization-free autoregressive modeling is "viable... at scale." But — honestly — it has not been validated at frontier scale by multiple independent groups, and the byte-sequence-length cost is real. As of mid-2026, classic subword tokenization is still the default everywhere that ships. Treat "tokenizer-free LLMs" as a promising research direction, not a solved problem.
There is no universally "best" tokenizer. BPE vs WordPiece vs Unigram differences are usually small and corpus-dependent; the bigger levers are vocab size, what corpus you trained merges on, and the pre-tokenization regex. Most practitioners just adopt the tokenizer of their base model and never touch it — which is reasonable, because changing it means retraining.

How it connects to OpenAlice

The from-scratch learning ladder. This is the conceptual sibling of the education tracks in the library: [[microgpt-build-an-llm-from-scratch]] and [[llm-from-scratch]] both begin with a tokenizer (the latter's char-level vocab=65 Shakespeare config is the simplest possible case — one token per character, BPE's degenerate limit), and [[neural-network-from-scratch]] sits one rung below. Karpathy's minbpe is the canonical "next step up" — implement real byte-level BPE in clean code — and is the natural lab exercise to bridge char-level toy models to GPT-style tokenization. A good OpenAlice Academy unit: take the char-level tokenizer from `llm-from-scratch`, replace it with a trained minbpe BPE, observe sequence length drop and the embedding matrix grow.
It's the first stage of the model, before everything else we document. Tokenization → [[embeddings]] (each token ID indexes a learned vector) → [[positional-encoding]] → [[attention-and-transformers]]. Sequence length set here is exactly what [[flash-attention]] and the quadratic-cost story care about.
Cost, context budget, and routing. Token counts are the unit of LLM billing and context limits, so they're load-bearing for any cost-aware [[model-routing]] decision and for retrieval pipelines like [[graphrag]] / [[agent-memory-systems]] / [[mempalace]] that must pack knowledge into a finite token budget — a more efficient tokenizer literally buys more memory per turn.
Prompt-injection hygiene. The special-token smuggling caveat above is directly relevant to Alice's connector surface (Telegram, web, embed widgets): user-supplied text must never be tokenized with allowed_special="all". Worth a cross-check against how OpenAlice's provider layer (Codex/OpenAI byte-level BPE) handles untrusted input.
No honest claim beyond that. OpenAlice consumes provider tokenizers (tiktoken via the Codex/OpenAI path); it does not train its own vocabulary today. The value here is understanding the failure modes (counting, spelling, non-English token tax, glitch tokens) so we attribute "Alice got it wrong" correctly — input encoding vs. model vs. prompt.

Tokenization (BPE & friends) — how text becomes the integers an LLM actually sees