Tokenization at Scale

A tokenizer maps a string of raw text into a sequence of integers, each indexing an entry in a fixed vocabulary learned from training data. The naive choices sit at two extremes. A word-level vocabulary treats each whitespace-delimited word as one token; this keeps sequences short but forces an enormous vocabulary (English alone has hundreds of thousands of inflected forms), and any word not seen during vocabulary construction becomes an unrecoverable out-of-vocabulary (OOV) token, typically mapped to a generic `` symbol with total loss of information. A character-level vocabulary solves OOV entirely — every string is composed of a small, closed set of characters — but produces sequences several times longer than word-level ones, which is expensive because the Full Transformer Architecture's self-attention costs grow quadratically in sequence length.

Subword tokenization is the compromise that all modern LLMs use. The vocabulary contains a mixture of common whole words (`the`, `ing`), frequent word fragments (`##ing`, `un`, `▁the`), and, critically, every individual byte or character as a fallback. This guarantees two properties simultaneously: no OOV tokens (any string can be decomposed down to guaranteed-present atomic symbols) and short sequences in practice (because frequent strings are represented by single large tokens learned from the data distribution). The vocabulary is not hand-designed; it is learned by an algorithm that scans a large corpus and decides which character sequences are common enough to deserve their own token. Three families dominate practice. Byte-Pair Encoding (BPE), adapted from a 1994 data-compression algorithm, iteratively merges the most frequent adjacent pair of symbols. WordPiece, developed at Google for machine translation and later used in BERT, is algorithmically similar to BPE but chooses merges using a likelihood-based score rather than raw frequency. SentencePiece is not a separate merge algorithm but an implementation framework: it treats the input as a raw stream of Unicode code points (or bytes), explicitly encodes whitespace as a visible symbol (conventionally `▁`, U+2581), and offers both a BPE backend and a probabilistic unigram language model tokenizer as pluggable segmentation strategies. This design makes tokenization fully reversible and language-agnostic, since it never assumes whitespace-delimited words exist (a property essential for Chinese, Japanese, Thai, and other languages without word-boundary spaces).

Byte-Pair Encoding (BPE)

BPE training operates on a corpus that has first been pre-tokenized into words (via whitespace/punctuation splitting), each word represented as a sequence of characters with a special end-of-word marker. Training proceeds greedily: at each step, count every adjacent symbol pair across the entire corpus, merge the single most frequent pair into a new symbol, and repeat for a fixed number of merges. The sequence of merges is the model — it defines a deterministic, ordered vocabulary. ``` ALGORITHM: BPE-Train INPUT: corpus (list of words with frequencies), num_merges K OUTPUT: ordered list of merge rules, final vocabulary 1. vocab_word ← map each word w to a sequence of symbols: the characters of w, each followed by "" appended only to the LAST character (marks word boundary) 2. merges ← empty ordered list 3. symbol_set ← set of all individual characters appearing (initial vocab) 4. for step in 1..K: 5. pair_counts ← empty map (pair -> count) 6. for each (word, freq) in vocab_word: 7. symbols ← current symbol sequence for word 8. for i in 0..len(symbols)-2: 9. pair ← (symbols[i], symbols[i+1]) 10. pair_counts[pair] += freq 11. if pair_counts is empty: 12. break // no more pairs to merge 13. best_pair ← argmax over pair_counts by count 14. new_symbol ← concat(best_pair[0], best_pair[1]) 15. merges.append(best_pair -> new_symbol) 16. symbol_set.add(new_symbol) 17. // apply this merge everywhere it occurs, left to right 18. for each (word, freq) in vocab_word: 19. vocab_word[word] ← replace all occurrences of best_pair in symbols with new_symbol 20. return merges, symbol_set ``` ``` ALGORITHM: BPE-Encode (apply learned merges to new text) INPUT: word (string), ordered merges (from training) OUTPUT: list of subword tokens 1. symbols ← characters of word, with "" on the last one 2. loop: 3. candidate_pairs ← all adjacent pairs currently in symbols 4. if candidate_pairs is empty: break 5. // find the pair that appears EARLIEST in the merge order 6. applicable ← {p in candidate_pairs : p in merges} 7. if applicable is empty: break 8. best ← the pair in applicable with the SMALLEST merge rank (i.e., learned earliest during training) 9. merge best into a single symbol, everywhere it occurs 10. return symbols ``` The encoder never recomputes frequencies at inference time — it replays the training merge order on new text, always applying whichever learnable merge occurs earliest in that order. This is what makes tokenization deterministic and identical between training and serving.

WordPiece

WordPiece (used in BERT and its descendants) trains almost identically to BPE, but changes the scoring function for choosing which pair to merge. Instead of raw co-occurrence count, it scores a candidate merge of symbols `x` and `y` by an approximation of the mutual-information gain from treating `xy` as one unit:

This down-weights merges where `x` or `y` is individually extremely common (like a single vowel), preferring merges that are surprising given the base rates — closer to a pointwise mutual information criterion than a raw frequency count. Everything else about training (iterative merges, fixed target vocabulary size) mirrors BPE. WordPiece's encoding procedure at inference time is also distinct: rather than replaying merges, it uses greedy longest-match-first segmentation over the fixed learned vocabulary. ``` ALGORITHM: WordPiece-Encode INPUT: word (string), vocabulary V (set of known tokens, continuation tokens prefixed with "##") OUTPUT: list of tokens, or [UNK] if unsegmentable 1. tokens ← empty list 2. start ← 0 3. n ← length(word) 4. while start < n: 5. end ← n 6. cur_token ← null 7. while end > start: 8. substr ← word[start:end] 9. if start > 0: substr ← "##" + substr 10. if substr in V: 11. cur_token ← substr 12. break 13. end ← end - 1 14. if cur_token is null: 15. return [UNK] // word cannot be tokenized 16. tokens.append(cur_token) 17. start ← end 18. return tokens ``` This is a greedy longest-prefix match, re-run from each successive starting position, with the `##` prefix marking "this piece continues the previous one" (so `unbelievable` becomes `un`, `##believ`, `##able` rather than three ambiguous free-standing pieces).

SentencePiece

SentencePiece is best understood as a preprocessing and interface layer, not a competing scoring rule. Its key design decisions: 1. No language-specific pre-tokenization. Raw input (including whitespace) is treated as one long Unicode sequence. Spaces are replaced with the visible meta-symbol `▁` before training, so tokenization and detokenization become a pure, lossless string operation: `decode(encode(x)) == x` exactly, byte-for-byte. 2. Pluggable model: SentencePiece can run BPE (as above) or a unigram language model tokenizer. The unigram model works in the opposite direction from BPE/WordPiece: it starts from a large candidate vocabulary (e.g., all substrings up to some length, or the output of a BPE pass) and iteratively prunes it down to the target size. ``` ALGORITHM: Unigram-Train (SentencePiece unigram mode) INPUT: corpus, initial large seed vocabulary, target size T OUTPUT: vocabulary of size T with unigram probabilities 1. V ← seed vocabulary (each piece v with probability p(v), initialized e.g. proportional to frequency) 2. repeat: 3. // E-step: for each word, find its most likely (or 4. // marginalize over all) segmentations under current V 5. // using the Viterbi algorithm over a lattice of substrings 6. run EM to re-estimate p(v) for all v in V, maximizing corpus log-likelihood: L = sum over words w of log( sum over segmentations s of w of prod_{v in s} p(v) ) 7. // pruning: for each piece v, compute how much L would 8. // DROP if v were removed from V (its "loss contribution") 9. remove the bottom fraction (e.g. 20%) of pieces by loss contribution, always keeping single characters 10. if |V| <= T: break 11. return V, p ``` At inference, unigram-mode SentencePiece finds the segmentation of a string that maximizes total sequence probability (product of piece probabilities) using the Viterbi algorithm over the directed acyclic graph of all substrings that are valid vocabulary pieces — an exact dynamic program, not a greedy heuristic like WordPiece's longest-match.

Training complexity. A naive implementation of BPE-Train recomputes all pair counts from scratch at every merge step. With corpus vocabulary of $W$ distinct words (total length $L$ symbols) and $K$ target merges, this costs $O(K \cdot L)$ in the worst case, since each merge step rescans the whole corpus. Production implementations avoid this by maintaining a priority queue of pair counts and only updating the counts of pairs adjacent to a merge site after each step, since a single merge can only change counts local to occurrences of that pair — this reduces the practical cost to roughly $O(L \log L)$ over the whole training run, dominated by priority-queue operations, since only a bounded number of pair-count entries change per merge and each change is an $O(\log L)$ heap update. WordPiece training has the same asymptotic profile, since it differs from BPE only in the score computed per candidate pair (still $O(1)$ per pair per step given running counts). Unigram (SentencePiece) training is more expensive per iteration: each EM step must run a Viterbi decode over every word in the corpus to estimate expected piece usage. For a word of length $n$ and a vocabulary where any substring might be a piece, exact Viterbi over the substring lattice costs $O(n \cdot m)$ per word, where $m$ bounds the maximum piece length considered — summed over the corpus this is $O(L \cdot m)$ per EM iteration, repeated for a handful of iterations at each pruning round, and pruning rounds themselves repeat $O(\log(|V_0|/T))$ times to shrink from seed size $|V_0|$ to target $T$. This is why unigram training is noticeably slower than BPE/WordPiece training in practice, though still entirely feasible offline on large corpora.

Encoding complexity (the cost that matters at serving time). This is the number that dominates production latency, since encoding runs on every request:

• BPE encode: naively $O(n^2)$ per word of length $n$ (rescan all adjacent pairs after every merge), but with a priority queue over applicable merges this is $O(n \log n)$.
• WordPiece encode: the greedy longest-match scan is $O(n^2)$ in the worst case per word (for each of $n$ start positions, scan backward up to $n$ characters), though a trie-based vocabulary lookup makes the common case close to linear, $O(n \cdot \bar{m})$ where $\bar{m}$ is average matched token length.
• Unigram encode (SentencePiece): exact Viterbi over the lattice costs $O(n \cdot m)$ where $m$ is the maximum piece length — a clean dynamic program, not a heuristic.

Correctness argument. The key invariant across all three algorithms is: every character (or byte) individually is guaranteed to be in the final vocabulary, because training always seeds the vocabulary with the full base alphabet before any merges are considered, and merges only ever combine existing symbols rather than deleting them. This one invariant is what eliminates the OOV problem entirely: in the worst case, a novel string just falls back to its raw characters/bytes, never to an information-destroying ``. (Some implementations, including certain vocabularies, do retain an explicit `` for pieces outside a byte-level alphabet — but byte-level BPE, used in GPT-2 and later models, guarantees full coverage of all 256 byte values, making `` provably unreachable.) A second correctness property is determinism: given a fixed vocabulary/merge table, encoding a string always produces the same token sequence, both in training and in serving. This matters enormously in practice — a model trained on one tokenization of a string and served with a different tokenization of the same string will see out-of-distribution input embeddings it was never trained on, silently degrading quality. Reproducing the exact training-time merge order (BPE) or the exact greedy scan (WordPiece) or the exact Viterbi optimum (unigram) is what guarantees this consistency.

Tradeoffs, honestly. BPE's greedy, purely frequency-driven merges can produce linguistically awkward splits (frequent character pairs that cross morpheme boundaries), and its encode is a heuristic replay, not a global optimum. WordPiece's likelihood-ratio score better respects statistical independence, but its greedy longest-match encoder can make a locally optimal choice that is not globally optimal — a longer initial match can sometimes force an ugly `[UNK]`-adjacent tail, whereas a shorter first match would have allowed clean coverage. Unigram's Viterbi encoding is provably optimal given the fixed piece probabilities, and its probabilistic framing additionally supports subword regularization (sampling alternate valid segmentations during training as data augmentation) — but training cost is higher, and the pruning heuristic (which pieces to drop each round) is itself an approximation, not exact marginal-likelihood maximization.

Consider training a tiny BPE tokenizer on a corpus with these word frequencies (a toy example, chosen to expose real merge-order subtleties, not a trivial single-word case):

Initial symbol sequences (character-level, `` marks end of word): ``` l o w (freq 5) l o w e r (freq 2) n e w e s t (freq 6) w i d e s t (freq 3) ```

Step 1 — count all adjacent pairs (weighted by word frequency):

The three-way tie between `(e,s)`, `(s,t)`, `(t, )` at 9 is broken by a fixed rule (e.g., leftmost-first in a canonical ordering); take `(e, s)` → merge into `es`.

Step 2 — apply merge `e s → es` everywhere: ``` l o w l o w e r n e w es t w i d es t ``` Recount: now `(es, t)` has count 6+3 = 9 — still the maximum. Merge `es t → est`. ``` l o w l o w e r n e w est w i d est ``` Next highest: `(est, )` at 9. Merge `est → est`. ``` l o w l o w e r n e w est w i d est ``` Next: `(l, o)` and `(o, w)` are now tied at 7 (5+2 each, present in `low` and `lower`). Take `(l,o)` first (leftmost rule) → merge `l o → lo`. ``` lo w lo w e r n e w est w i d est ``` Next: `(lo, w)` now at 7. Merge → `low`. ``` low low e r n e w est w i d est ``` After six merges the vocabulary contains: the original characters, plus `es`, `est`, `est`, `lo`, `low`, and so on. Note the emergent structure: `est` becomes a single reusable token that fires on both `newest` and `widest`, despite those words sharing no prefix — the algorithm discovered a shared suffix purely from co-occurrence statistics, exactly the kind of subword generalization that lets an unseen word like `"lowest"` (never in the training corpus) tokenize cleanly as `low` + `est` at inference time, rather than falling back to six separate characters or an ``.

Encoding `"lowest"` with the learned merges (replaying merge order): start `l o w e s t ` → apply `e s → es` (learned early) → `l o w es t ` → apply `es t → est` → `l o w est ` → apply `est → est` → `l o w est` → apply `l o → lo` → `lo w est` → apply `lo w → low` → `low est`. Final tokenization: `low`, `est</w>` — two tokens, both drawn from a vocabulary built without ever seeing the word `lowest`, demonstrating the OOV-free generalization property directly.

Byte-Pair Encoding began life not as an NLP idea at all, but as a general-purpose data compression trick, later repurposed for subword vocabulary construction and popularized in neural machine translation before becoming the default tokenizer family for GPT-style models.

Nearly every production LLM depends on one of these three families. GPT-2 and its successors use a byte-level BPE variant, operating on raw UTF-8 bytes rather than Unicode characters, which guarantees full coverage of any input string (including malformed text, emoji, and arbitrary binary-looking sequences) without ever needing an `` token. BERT and many of its derivatives use WordPiece, with the `##` continuation-prefix convention still visible in tokenizer outputs today. Multilingual and instruction-tuned models — including T5, XLNet, ALBERT, and most Llama-family models — rely on SentencePiece, precisely because its whitespace-as-symbol design avoids privileging any one language's word-segmentation conventions, which matters enormously for fair multilingual coverage. Beyond individual models, tokenization choices ripple into system-level engineering: API pricing for commercial LLMs is billed per token, so the tokenizer's compression efficiency on a given language directly determines cost; context-window budgeting (how much text fits in, say, 128K tokens) depends on the average tokens-per-word ratio of the tokenizer for the language and domain in question; and the Scaling Laws literature measures model and dataset size in tokens, making the tokenizer an implicit unit-of-account that must be held fixed for fair comparisons across models. Code-focused models additionally require tokenizers tuned to preserve meaningful substructure in identifiers, indentation, and punctuation — a domain where naive whitespace-based pre-tokenization performs especially poorly, motivating custom vocabularies trained on code corpora.

Ask the tutor: How would changing a model's tokenizer vocabulary size affect its position on a compute-optimal scaling curve?