Tokenization

1. The Core Problem

Neural networks need numbers as input. But text is a sequence of characters, words, and symbols. How do we bridge this gap?

Three Approaches

---

2. Byte Pair Encoding (BPE)

The dominant tokenization algorithm — used by GPT, Claude, Llama, and most modern LLMs.

Core Idea

Start with individual characters, then iteratively merge the most frequent adjacent pairs.

Step-by-Step Example

Training corpus: "low low low lower lowest"

Initial representation (characters + end-of-word token </w>):

l o w </w>       (freq: 3)
l o w e r </w>   (freq: 1)
l o w e s t </w> (freq: 1)

Iteration 1 — Count pairs, merge most frequent:

Merge (l, o) → "lo":

lo w </w>       (freq: 3)
lo w e r </w>   (freq: 1)
lo w e s t </w> (freq: 1)

Iteration 2 — Merge (lo, w) → "low":

low </w>       (freq: 3)
low e r </w>   (freq: 1)
low e s t </w> (freq: 1)

Iteration 3 — Merge (low, </w>) → "low</w>":

low</w>            (freq: 3) ← standalone "low"
low e r </w>       (freq: 1)
low e s t </w>     (freq: 1)

Repeat thousands of times on billions of words until vocabulary size target (typically 50,000–100,000 tokens) is reached.

---

3. The BPE Vocabulary

After training, we get a hierarchical vocabulary:

---

4. Tokenizing Real Text

Example Tokenizations (GPT-4 style)

Note: The space is attached to the following word in BPE. " world" (with leading space) is a single token.

---

5. Special Tokens

Modern LLMs use special tokens to structure conversations:

---

6. Positional Token IDs

Every token maps to a unique integer ID:

$\text{Token} \xrightarrow{\text{lookup}} \text{ID} \xrightarrow{\text{embedding}} \mathbf{e} \in \mathbb{R}^d$

Example vocabulary slice:

---

7. Context Window and Token Limits

Every model has a maximum number of tokens it can process at once:

Token Budget in a Conversation

$\underbrace{500}_{\text{system prompt}} + \underbrace{200}_{\text{user msg}} + \underbrace{800}_{\text{response}} + \underbrace{2500}_{\text{history}} = 4000 \text{ tokens used}$

When the limit is hit → earliest messages are dropped → model "forgets" old context.

---

8. Tokens → Words Conversion

Rule of thumb for English:

$1 \text{ token} \approx 0.75 \text{ words}$

---

9. Why Tokenization Causes Weird Failures

Problem 1 — Letter Counting

"How many R's in STRAWBERRY?"

Tokenized: ["STR", "AW", "BER", "RY"]

The model sees tokens, not individual letters. It must infer character content from token representations → often fails.

$P(\text{correct count} \mid \text{token representations}) \ll 1$

Problem 2 — Arithmetic with Large Numbers

"1,234,567 × 89"
Tokenized: ["1", ",", "234", ",", "567", " ×", " 89"]

Math must be performed across arbitrary token boundaries → unreliable without tools.

Problem 3 — Language Inequality

The tokenizer was trained primarily on English → non-English text is tokenized less efficiently:

Non-English text uses more tokens → costs more, uses context window faster.

---

10. SentencePiece vs BPE

---

11. Complete Pipeline: Text to Prediction

---

12. Quick Reference

---

13. The Full AI Backbone — Complete Summary