Chapter 4.1 β€” Tokenization

Contents

  1. Picking up where architecture leaves off: text is not numbers
  2. Character-level and word-level tokenization, and why both fail
  3. Subword tokenization: the practical middle ground
  4. Byte-Pair Encoding
  5. WordPiece
  6. SentencePiece and the unigram language model
  7. Vocabulary size as an engineering tradeoff
  8. Interview angle
  9. Self-check questions
  10. Sources

1. Picking up where architecture leaves off: text is not numbers

Part III ended by noting that once you have an architecture that can attend efficiently over long context, run inference cheaply through a KV-cache, quantize its weights, and serve requests at scale, you still haven't actually trained the thing. Every discussion so far β€” attention scores, MoE routing, speculative decoding β€” has quietly assumed that the input to the model is already a sequence of discrete tokens, each one an integer index into a fixed vocabulary, each one mapped to a vector via an embedding table. That assumption is not free. Before any transformer layer, any positional encoding, any softmax over a vocabulary can do its job, someone has to answer a much more basic question: how does a raw string of Unicode characters become a sequence of integers in the first place?

This is tokenization, and it is easy to underrate because it sits upstream of everything glamorous. But the choice of tokenizer determines the effective vocabulary the model reasons over, how long a given piece of text becomes once encoded, how gracefully the model handles words it has never seen, and β€” as we'll see at the end of this chapter β€” some genuinely strange failure modes that show up in deployed LLMs and that interviewers like to probe precisely because they reveal whether a candidate understands the pipeline below the model, not just the model itself.

2. Character-level and word-level tokenization, and why both fail

The most literal way to turn text into tokens is to treat each character as a token. This has real virtues: the vocabulary is tiny (a few hundred symbols at most, covering every letter, digit, and punctuation mark you'll encounter), and there is no such thing as an out-of-vocabulary word, since any string can be spelled out character by character. But it fails for a reason that should be familiar from the sparsity and context-length discussions earlier in this book: character-level sequences are long. A sentence that might be twenty subword tokens becomes on the order of a hundred characters, and every architectural cost that scales with sequence length β€” attention's quadratic term, KV-cache memory, positional encoding range β€” gets paid at that much higher a rate. Worse, the model now has to learn long-range structure (that "ing" tends to follow certain letter patterns, that "the" is a coherent unit) from scratch, spending capacity and context purely to reconstruct units a smarter tokenizer would have handed it for free.

The opposite extreme is word-level tokenization: split text on whitespace and punctuation, and give every distinct word its own token. This directly revisits the sparsity problem from Chapter 1.2. Natural language has a long tail β€” Zipf's law guarantees that most distinct words in any large corpus are rare β€” so a word-level vocabulary either has to be enormous to cover the tail (which blows up the embedding table and, more expensively, the output softmax, since both scale linearly with vocabulary size) or it has to cap the vocabulary and treat every word outside it as a single generic "unknown" token. That second option is a genuine catastrophe for a language model: the model loses all information about what the out-of-vocabulary word actually was, and any word not in the training vocabulary β€” a typo, a rare name, a word in a language variant not well represented in training data, a coinage β€” becomes invisible. A model that cannot represent "cryptocurrency" or "COVID" because they postdate its vocabulary freeze is not a model you can ship.

3. Subword tokenization: the practical middle ground

Subword tokenization resolves this by choosing units that are neither full words nor single characters, but frequently-occurring chunks somewhere in between, discovered directly from corpus statistics rather than imposed by a linguist's notion of what a "word" is. Common words end up as single tokens ("the", "is", "language"), while rare or unseen words decompose into a small number of familiar pieces ("cryptocurrency" might become "crypto" + "currency", or something closer to "crypt" + "o" + "currency" depending on the algorithm and training corpus). Critically, every possible string can still be represented, because the finest-grained fallback units β€” individual characters or even individual bytes β€” are always available as tokens in their own right. This gives you the word-level tokenizer's compactness for common text and the character-level tokenizer's total coverage as a safety net, without fully paying either one's costs. The three dominant algorithms for building such a vocabulary β€” BPE, WordPiece, and the unigram model used inside SentencePiece β€” differ in the criterion they use to decide which subword units deserve to exist, but they all share this same basic bet: let frequency statistics on real text tell you where to draw token boundaries, rather than deciding a priori.

4. Byte-Pair Encoding

Byte-Pair Encoding, or BPE, was originally a data compression algorithm with nothing to do with language modeling: given a string, repeatedly find the most frequent pair of adjacent symbols and replace every occurrence with a new symbol representing that pair, shrinking the representation with each merge. Sennrich, Haddow, and Birch repurposed exactly this idea for neural machine translation in 2016, motivated by precisely the out-of-vocabulary problem described above β€” a translation system with a fixed word vocabulary has no principled way to translate a rare or unseen word, but a system that can fall back to subword units can still produce something sensible for "Woltschach" by decomposing it into recognizable pieces, the way a competent human translator would sound out an unfamiliar name syllable by syllable.

The algorithm as used for tokenization works as follows. Start with a vocabulary consisting of the individual characters (or bytes) present in the training corpus, with each word represented as a sequence of these atomic symbols, typically with a special marker for word boundaries. Then repeat a simple procedure a fixed number of times: count the frequency of every adjacent pair of symbols across the entire corpus, find the single most frequent pair, and merge it β€” replacing every occurrence of that pair with a new, single symbol added to the vocabulary. Each merge is recorded, in order, as a rule. Running this for, say, 32,000 or 50,000 merges yields a vocabulary approximately that size β€” precisely, $|V_{\text{final}}| = |V_{\text{base}}| + M$, where $M$ is the number of merge operations performed and $|V_{\text{base}}|$ is the size of the base alphabet (256 for byte-level BPE), so "50,000 merges" and "a 50,000-token vocabulary" are the same only up to that small additive offset. The vocabulary is built bottom-up entirely from the statistics of the corpus you trained on, with the most frequent character sequences ending up as full tokens and the rarest strings still expressible as sequences of shorter, more frequent pieces. Applying a trained BPE tokenizer to new text is deterministic: you apply the recorded merge rules in the same order they were learned, greedily, until no more merges apply.

Modern implementations, starting with GPT-2, apply BPE at the byte level rather than the Unicode-character level: the base alphabet is the 256 possible byte values, not Unicode code points, and every merge operates on sequences of bytes. This one change closes a real gap in the character-level version β€” a character-level base vocabulary still has to decide what to do with a character it never saw during its own construction (an emoji, an unusual script, a stray control character), and any such gap forces some kind of escape hatch. Byte-level BPE has no such gap by construction: every possible input, in any language or encoding, is already a sequence of bytes, so the 256-symbol byte alphabet guarantees total coverage before a single merge rule is even applied β€” there is no "unknown byte." The price is that a character outside the Latin range typically costs more byte-tokens than a Latin character does, which is part of why non-English text reliably tokenizes to more tokens per word than English text in tokenizers built this way β€” a real, measurable cost that shows up directly in the context budget and API pricing available to non-English users of the same model.

5. WordPiece

WordPiece, developed for Google's speech recognition and machine translation systems and later adopted as the tokenizer behind BERT, follows the same broad strategy as BPE β€” start from characters, iteratively merge pairs, build a vocabulary bottom-up β€” but changes the criterion for choosing which pair to merge at each step. Where BPE simply merges whichever adjacent pair is most frequent, WordPiece merges whichever pair, once merged, most increases the likelihood of the training corpus under a language model built from the resulting vocabulary β€” equivalently, it favors merges where the pair co-occurs far more often than would be expected if the two symbols were independent β€” scoring each candidate pair $(a, b)$ roughly as $\text{score}(a, b) = \dfrac{P(ab)}{P(a)\,P(b)} \approx \dfrac{\text{count}(ab)}{\text{count}(a)\cdot\text{count}(b)}$ β€” rather than merges that are frequent merely because both symbols individually are common. In practice this produces broadly similar-looking vocabularies to BPE, but the selection criterion is a genuine methodological difference worth being able to state precisely in an interview: BPE optimizes raw pair frequency, WordPiece optimizes a likelihood criterion. WordPiece itself was described before the arXiv era of easy citation and is standardly cited secondhand through the BERT paper that popularized it, which is the citation convention this book follows as well.

6. SentencePiece and the unigram language model

BPE and WordPiece as originally described assume you can pre-tokenize on whitespace before applying subword merges β€” you split into words first, then break rare words into pieces. This is a reasonable assumption for English but breaks down for languages without clear whitespace-delimited word boundaries (Japanese and Chinese being the standard examples), and it also throws away information about whitespace itself, which can matter for faithfully reconstructing the original text. SentencePiece, introduced by Kudo and Richardson, sidesteps this by treating the input as a raw, language-agnostic stream of characters β€” including whitespace, which it encodes as an ordinary symbol (conventionally rendered as "▁") rather than treating it as a delimiter to be stripped before tokenization begins. This makes the tokenizer fully reversible: detokenization is just concatenation, with no language-specific rules needed to reinsert spaces correctly, which matters a great deal in production systems that need to handle arbitrary multilingual input without a battery of special cases.

SentencePiece supports BPE as one of its two segmentation algorithms, but its more interesting contribution is the second option: a unigram language model tokenizer, described in Kudo's companion paper on subword regularization. Here the vocabulary is built top-down rather than bottom-up β€” you start from a large candidate set of subword units and iteratively prune it, at each step removing the subwords whose removal least hurts the likelihood of the training corpus under a unigram model (a model that treats each token in a segmentation as independent, so the probability of a segmentation $x_1, \dots, x_n$ is simply $P(x_1,\dots,x_n) = \prod_{i=1}^{n} p(x_i)$, with the per-token probabilities $p(x_i)$ estimated via expectation-maximization), until the vocabulary reaches the target size. The genuinely useful trick this unlocks is subword regularization: because a unigram model can score multiple different valid segmentations of the same input string, you can sample among them during training rather than always using the single best (Viterbi) segmentation β€” the one that maximizes $P(x_1,\dots,x_n)$ over all valid segmentations of the input string. This exposes the model to more than one way of splitting the same word across different training steps, acting as a form of data augmentation and regularization that makes the model more robust to whichever segmentation it happens to encounter at inference time, rather than overfitting to one canonical tokenization of every string.

7. Vocabulary size as an engineering tradeoff

Whichever algorithm you use, you still have to pick a vocabulary size, and this is a real, consequential engineering decision rather than a hyperparameter you tune away. A larger vocabulary means common words and even common short phrases collapse into single tokens, so any given piece of text becomes a shorter token sequence β€” which is valuable because sequence length drives compute cost, context budget, and generation latency almost everywhere else in the stack. But a larger vocabulary also means a larger embedding table and, more expensively, a larger final projection matrix mapping hidden states to a distribution over the vocabulary β€” each one holding $|V| \times d_{\text{model}}$ parameters, since that output layer's cost scales linearly with vocabulary size and sits on the critical path of every single forward pass. A smaller vocabulary inverts these tradeoffs: cheaper embedding and output layers, but longer sequences for the same text, and β€” somewhat counterintuitively β€” often better generalization to genuinely rare or novel words, precisely because those words are forced to decompose into smaller, more frequently-seen pieces rather than being memorized as one large, rarely-updated embedding.

This tradeoff is not merely theoretical; it is the direct cause of some of the odder failure modes visible in deployed LLMs. When people ask a model to reverse a string, count the letters in a word, or perform careful character-level arithmetic, and the model gets it wrong in ways that seem bizarrely inconsistent with its evident fluency elsewhere, tokenization is usually the proximate cause. A number like "3752" might be split into "375" and "2" by one tokenizer's merge rules and "37" and "52" by another's, and neither split corresponds to the base-10 place-value structure a human would use to do arithmetic; the model has to learn to undo an arbitrary, corpus-frequency-driven segmentation before it can even begin the arithmetic itself. Similarly, asking a model how many letters are in a word it perceives as a single opaque token is asking it a question about the internal structure of a symbol it was never shown broken apart. This is a genuinely useful fact to carry into interviews: it demonstrates that you understand a model's apparent capabilities and failures are not solely a function of its parameters and training objective, but also of a preprocessing choice made before training ever begins β€” and it sets up the concern of Chapter 4.2, "Pretraining Objectives and Data," which is what objective you actually train the model on once its input has been reduced to a sequence of these discrete tokens.

The vocabulary-size tradeoff also explains one of the stranger public discoveries about deployed tokenizers: glitch tokens. In 2023, Rumbelow and Watkins probed GPT-2 and GPT-3's vocabularies and found individual tokens β€” most infamously "SolidGoldMagikarp," a Reddit username that had been scraped into the corpus used to build the tokenizer's vocabulary in enough volume to earn its own token, but that appeared rarely or not at all in the (differently sourced, much larger) corpus later used to train the model's weights. Feeding the model that token produced wildly incoherent, sometimes unsettling completions, with the model deflecting, free-associating, or producing outright nonsense rather than anything resembling a normal response. The mechanism follows directly from the tradeoff above: a token can exist in the vocabulary because it was frequent in whatever corpus the tokenizer itself was fit on, while its embedding remains almost entirely untrained because that same string never showed up, or showed up only a handful of times, in the corpus used to train the model. The embedding sits close to its random initialization, and the model has learned nothing sensible to do when it appears β€” a vivid, concrete instance of the general point that a tokenizer built at one stage of the pipeline, on one corpus, can quietly diverge from the data the model actually learns from at another stage.

8. Interview angle

Q: Why did subword tokenization win out over both character-level and word-level tokenization for large language models? A strong answer states the tradeoff precisely rather than just naming "subwords are better": character-level tokenization inflates sequence length, which is expensive because most architectural and inference costs scale with sequence length, and it forces the model to relearn word-level structure from scratch. Word-level tokenization creates a vocabulary sparsity problem β€” a long Zipfian tail of rare words that either bloats the vocabulary or gets mapped to an uninformative unknown token, destroying information about genuinely important rare strings (names, new terms, typos). Subword tokenization gets the best of both: common strings are compact single tokens, rare strings decompose gracefully into smaller known pieces, and coverage is total because the finest-grained units are always available as a fallback.

Q: What's the actual algorithmic difference between BPE and WordPiece? A strong answer doesn't just say "they're similar" β€” it states that both build vocabularies bottom-up via iterative merges of adjacent symbol pairs, but BPE merges whichever pair is most frequent in the corpus, while WordPiece merges whichever pair, once merged, most improves the likelihood of the corpus under the resulting vocabulary (equivalently, favors pairs that co-occur far more than chance given their individual frequencies). The point of contrast is "raw frequency" versus "a likelihood-based criterion."

Q: What problem does SentencePiece solve that BPE and WordPiece as originally described do not? A strong answer notes that classic BPE/WordPiece assume whitespace-delimited pre-tokenization, which breaks for languages without clear word boundaries and discards information needed to reconstruct whitespace faithfully. SentencePiece treats input as a raw character stream including whitespace as an ordinary symbol, making it language-agnostic and making detokenization a pure concatenation with no special-casing required.

Q: What is subword regularization, and why would you want it? A strong answer explains that under a unigram-language-model tokenizer, a given input string generally has multiple valid segmentations, each with a computable probability; instead of always tokenizing with the single best segmentation, you sample among plausible segmentations during training. This exposes the model to varied tokenizations of the same underlying text across training steps, acting as a data augmentation/regularization technique that reduces the model's sensitivity to the specific segmentation it happens to see at inference time.

Q: Why can LLMs sometimes fail at seemingly trivial tasks like counting letters in a word or doing multi-digit arithmetic? A strong answer connects this directly to tokenization: the model never sees individual characters of a word tokenized as one opaque unit, so it cannot straightforwardly "look inside" that token, and multi-digit numbers get split into arbitrary, frequency-driven chunks that don't align with place value, forcing the model to implicitly learn to undo an inconsistent segmentation before doing the actual arithmetic. This is presented as a preprocessing-driven failure mode, not evidence of a fundamental reasoning deficiency unrelated to input representation.

9. Self-check questions

  1. Why does the chain-rule decomposition of language modeling from Chapter 1.1 presuppose that text has already been converted into a fixed, discrete vocabulary?
  2. What specific costs does character-level tokenization impose that scale with sequence length, and which architectural components from Part III do those costs affect?
  3. Explain, in one or two sentences, why word-level tokenization recreates the same sparsity problem discussed in Chapter 1.2's treatment of n-gram models.
  4. Walk through one merge step of BPE by hand: given a toy corpus, how would you identify which pair to merge next, and what happens to the vocabulary as a result?
  5. What is the precise difference between the selection criterion used by BPE and the one used by WordPiece?
  6. Why does SentencePiece encode whitespace as a regular token rather than treating it as a delimiter to be stripped before tokenization?
  7. If you had to choose a smaller vocabulary size for a new model, what would you expect to gain and what would you expect to lose, in terms of sequence length, embedding/output matrix size, and generalization to rare words?

10. Sources

  • Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. ACL 2016. arXiv:1508.07909. https://arxiv.org/abs/1508.07909
  • Kudo, T., & Richardson, J. (2018). SentencePiece: A Simple and Language Independent Subword Tokenizer and Detokenizer for Neural Text Processing. EMNLP 2018. arXiv:1808.06226. https://arxiv.org/abs/1808.06226
  • Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL 2018. arXiv:1804.10959. https://arxiv.org/abs/1804.10959
  • Schuster, M., & Nakajima, K. (2012). Japanese and Korean Voice Search. ICASSP 2012. (WordPiece; not on arXiv β€” cited here as used and described in Devlin et al.'s BERT paper, arXiv:1810.04805, referenced in Chapters 2.3 and 4.2.)
  • Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., & Sutskever, I. (2019). Language Models are Unsupervised Multitask Learners. (GPT-2; introduces byte-level BPE.) https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf
  • Rumbelow, J., & Watkins, M. (2023). SolidGoldMagikarp (plus, prompt generation). LessWrong. https://www.lesswrong.com/posts/aPeJE8bSo6rAFoLqg/solidgoldmagikarp-plus-prompt-generation

Self-check quiz

Test your understanding of this chapter with a short quiz β€” a mix of concept questions and quick calculations.

Why does word-level tokenization recreate the sparsity problem from Chapter 1.2?

Explanation: Just like n-gram sparsity, a long Zipfian tail of rare words either bloats the vocabulary or gets collapsed into an "unknown" token, destroying information about the actual word.

What is the precise difference between BPE's and WordPiece's merge-selection criterion?

Explanation: BPE optimizes raw pair frequency; WordPiece optimizes a likelihood-based criterion, favoring pairs that co-occur more than their individual frequencies would predict.

What problem does SentencePiece solve that classic BPE/WordPiece, as originally described, do not?

Explanation: Classic BPE/WordPiece assume you can split on whitespace first β€” this breaks for languages without clear word boundaries. SentencePiece encodes whitespace itself as a token, making detokenization pure concatenation.

Why can LLMs sometimes fail at tasks like counting letters in a word or multi-digit arithmetic?

Explanation: A number like "3752" might split into "375"+"2" for one tokenizer and "37"+"52" for another β€” neither aligns with base-10 place value, so the model must undo an arbitrary segmentation before it can even begin the arithmetic.

A toy corpus has the words "cat" (frequency 8), "car" (frequency 5), and "cap" (frequency 2), each initially split into individual characters. What is the frequency count of the most frequent adjacent symbol pair β€” the one BPE would merge first?

Explanation: The pair (c,a) appears in all three words: 8 + 5 + 2 = 15, more than any other pair (a,t)=8, (a,r)=5, or (a,p)=2.

A model has a vocabulary of 32,000 tokens and a hidden dimension of 768. How many parameters are in the embedding table alone?

Explanation: 32,000 Γ— 768 = 24,576,000 parameters.

The chapter notes that a sentence of about 20 subword tokens becomes on the order of 100 characters at the character level. Based on this, what is the average number of characters per subword token?

Explanation: 100 characters / 20 tokens = 5 characters per token on average.

Starting from a base vocabulary of 256 byte values, if you run 32,000 BPE merges, what is the resulting vocabulary size?

Explanation: 256 base symbols + 32,000 merged symbols = 32,256 total vocabulary entries.