Tokenization

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. The Tokenization Problem
6. Byte Pair Encoding (BPE)
7. Vocabulary Size and Compression Tradeoff
8. Byte-Level and Unicode Handling
9. The Embedding Map
10. Sequence Length and Compute
11. Worked Examples
12. Connection to the Broader Curriculum
13. Common Pitfalls and Misconceptions
14. Research Perspective
15. Summary of Takeaways
16. Exercises

Learning Objectives

After reading this chapter, you should be able to:

1. Explain why raw text must be tokenized before LLM processing.
2. Describe the BPE merge algorithm and prove it greedily maximizes local co-occurrence frequency.
3. Analyze the tradeoff between vocabulary size $|V|$ and average sequence length.
4. Define the embedding map $\text{token} \mapsto \mathbb{R}^d$ and its role in the pipeline.
5. Compare word-level, subword, and byte-level tokenization strategies.

Prerequisites

• Entropy — information content, compression

Notation

• $\Sigma$ — Text alphabet (bytes or Unicode)
• **$V$, $** — V —$ — Vocabulary and its size
• **$\tau: \Sigma^* \to \lbrace 1,\ldots,** — V — \rbrace^*$ — Tokenizer map
• $\mathbf{E} \in \mathbb{R}^{\lvert V \rvert \times d}$ — Token embedding matrix
• $\rho$ — Average tokens per character
• $(a,b) \to ab$ — BPE merge operation

Core Intuition

Language models operate on vectors, not strings. Tokenization is the first stage: map text to a sequence of integers from a finite vocabulary $V$. This discrete representation is embedded into $\mathbb{R}^d$ and processed by Self-Attention.

The choice of tokenizer affects everything downstream: sequence length (compute cost scales as $O(n^2)$), multilingual coverage, handling of rare words, and Scaling Laws (tokens per parameter).

Series context. Volume III, Chapter 11 (LLM Foundations).

The Tokenization Problem

Definition 1 (Tokenization). A tokenizer is a map $\tau: \Sigma^* \to \{1, \ldots, |V|\}^*$ from strings over alphabet $\Sigma$ to sequences of vocabulary indices.

Definition 2 (Detokenization). The inverse $\tau^{-1}$ reconstructs text (approximately) from token sequences.

Requirements:

• Lossless (or near-lossless) reconstruction
• Compact representation (few tokens per character)
• Open vocabulary coverage (no UNK tokens)

Byte Pair Encoding (BPE)

Algorithm (BPE Training).

1. Initialize vocabulary with all bytes (or characters) in corpus
2. Count frequency of all adjacent symbol pairs
3. Merge most frequent pair into new symbol; add to vocabulary
4. Repeat until $|V| = V_{\text{target}}$

Definition 3 (Merge Rule). At step $k$, merge $(a, b)$ with highest co-occurrence count $f(a, b)$:

Proposition 1. BPE greedily builds subwords capturing high-frequency patterns — morphological units, common words, prefixes/suffixes.

Encoding. Iteratively apply longest-match merge rules to input text.

Vocabulary Size and Compression Tradeoff

Definition 4 (Average Tokens per Character).

• Small (~1K) — High — Long sequences, small embedding table
• Large (~100K) — Low — Short sequences, large embedding table

Proposition 2. Total embedding parameters: $|V| \cdot d$. Attention cost: $O(n^2 d)$ where $n \propto \rho \cdot \text{text length}$.

Optimal $|V|$ balances embedding size vs. sequence length — typically 32K–128K for modern LLMs.

Byte-Level and Unicode Handling

Definition 5 (Byte-Level BPE, GPT-2). Initialize with 256 byte tokens. All Unicode text is UTF-8 encoded first — no UNK tokens.

Proposition 3. Byte-level tokenization covers arbitrary Unicode with fixed base vocabulary 256 + merges.

Used in GPT-2, GPT-3, LLaMA (with SentencePiece variant).

The Embedding Map

Definition 6 (Token Embedding).

$\mathbf{E} \in \mathbb{R}^{|V| \times d}$ is learned during pretraining. See Vectors & Linear Independence.

Output: $\mathbf{X} = [\mathbf{e}_{t_1}, \ldots, \mathbf{e}_{t_n}]^T \in \mathbb{R}^{n \times d}$ fed to Transformer.

Sequence Length and Compute

Theorem 1 (Attention Cost). For sequence length $n$, Self-Attention costs $O(n^2 d)$. Reducing $\rho$ by factor $k$ reduces attention FLOPs by $k^2$.

Connection to Scaling Laws: Training compute $\propto$ tokens processed; tokenizer efficiency directly affects budget.

Worked Examples

Example 1: BPE Merge

Corpus: "low low lower". Frequent pair ("l","o") → "lo". Then ("lo","w") → "low".

Example 2: Vocabulary Size

50K vocab: English ~0.25 tokens/char. 4K vocab: ~0.5 tokens/char — 2× longer sequences.

Connection to the Broader Curriculum

• Self-Attention — processes token embeddings
• Positional Encoding — adds position to embeddings
• Scaling Laws — tokens vs. compute
• LoRA — adapts embedding layer optionally

Common Pitfalls and Misconceptions

Pitfall 1: Tokenization is not learned end-to-end in standard LLMs (fixed before training).

Pitfall 2: Different tokenizers are incompatible across models.

Pitfall 3: Counting "words" vs. "tokens" in context windows.

Pitfall 4: Whitespace handling varies by implementation.

Research Perspective

Subword tokenization emerged from statistical machine translation. Byte Pair Encoding was adapted for NMT by Sennrich et al. (2016), replacing word-level vocabularies with mergeable subword units. SentencePiece (Kudo & Richardson, 2018) treated the tokenizer as a self-contained module with direct Unicode handling. The vocabulary-size tradeoff connects formally to Entropy: larger vocabularies reduce sequence length (fewer tokens per character) at the cost of a larger embedding table and softmax. Active research explores learned tokenization, token-free models (ByT5), and vocabulary adaptation across languages.

Summary of Takeaways

• BPE — Greedy merge by frequency
• **$** — V —$ — Vocabulary size tradeoff
• Embedding $\mathbf{E}$ — Discrete → continuous
• $\rho$ — Tokens per character

Next: RoPE

Exercises

Exercise 1. Apply BPE by hand on corpus $\{\text{low, low, lower}\}$ for three merge steps; record vocabulary after each step.

Exercise 2. Derive relationship between $|V|$, $d$, and embedding parameter count.

Exercise 3. Why does byte-level BPE avoid UNK?

Exercise 4. Estimate attention FLOPs for 8K tokens vs. 4K tokens.

Exercise 5. Compare BPE to Entropy-optimal coding.

Exercise 6. Tokenization impact on KV Cache memory.

Exercise 7. Multilingual tokenization challenges.

Exercise 8. Prove detokenization is well-defined for byte-level BPE.