Tokenization fundamentals

What is a Token?

Why not just use words?

Rare words problem: "antidisestablishmentarianism" appears once in training data → model never learns it properly
Out-of-vocabulary (OOV): New words ("COVID-19") didn't exist when model trained
Morphology: "run", "running", "ran" are treated as completely separate → no shared understanding
Vocabulary explosion: English has ~170K words, but infinite variations with proper nouns, typos, emoji

Why not just use characters?

Sequence length explosion: "Hello" = 5 tokens vs1 word token → 5× longer sequences
Computational cost: Transformer complexity is O(n²) in sequence length
Long-range dependencies: Harder for model to connect "H" + "e" + "l" + "o" into meaning

Why each step: We're building from bottom-up, capturing the most common patterns first. "low" is frequent → becomes one token. "est" suffix is common → becomes one token. This generalizes: "newest" and "widest" now share the "est" token.

Step 4: Numericalization

What happens: Map each token string to a unique integer ID

Vocabulary: {"<pad>": 0, "<unk>": 1, "hello": 100, "world": 250 ...}
Tokens: ["hello", "world"]
Token IDs: [100, 250]

This is a simple dictionary lookup. Special tokens:

<pad> (ID 0): Padding for batching
<unk> (ID 1): Unknown/rare tokens (fallback)
<bos> / <eos>: Beginning/end of sequence
<mask>: For masked language modeling

Encoding and Decoding

Worked example Full Encoding Example (GPT-2 Tokenizer)

Input text: "Hello, world!"

Step 1 - Normalization: (GPT-2 does minimal normalization)

"Hello, world!"

Step 2 - Pre-tokenization: Split on whitespace, mark spaces with Ġ

["Hello", ",", "Ġworld", "!"]

(Ġ is a special character indicating "this token had a space before it")

Step 3 - BPE tokenization: Apply learned merges

"Hello" → ["Hello"]  (common word, single token)
"," → [","]
"Ġworld" → ["Ġworld"]  (common word with space)
"!" → ["!"]

Step 4 - Numericalization:

Tokens: ["Hello", ",", "Ġworld", "!"]
IDs: [15496, 11, 995, 0]

Decoding:

[15496, 11, 995, 0] → ["Hello", ",", "Ġworld", "!"]
→ "Hello,Ġworld!" → "Hello, world!"

(Replace Ġ with actual space)

Why GPT-2 uses Ġ: Preserves information about whitespace position, allows perfect reversibility.

Key Properties of Good Tokenization

Formula Tokenization Quality Metrics

Vocabulary size $|V|$ : Typically 30K-100K
- Too small → long sequences, loss of semantic units
- Too large → sparse embedings, rare tokens
Average sequence length $\bar{n}$ : For corpus $C$ , $\bar{n} = \frac{1}{|C|} \sum_{s \in C} |\text{encode}(s)|$ Lower is better (efficiency), but not at cost of semantic loss.
Coverage: Probability that tokens appear in training: $\text{Coverage} = \frac{\text{\# known tokens in new text}}{\text{total tokens in new text}}$ Should be > 99.5% to avoid excessive <unk> tokens.
Fertility: Average tokens per word: $\text{Fertility} = \frac{\text{tokens}}{\text{words}}$ ~1.3-1.5 is typical for BPE. Lower = more efficient.

Common Tokenization Algorithms

Algorithm	Strategy	Used By
BPE (Byte-Pair Encoding)	Merge most frequent pairs iteratively	GPT-2, GPT-3, RoBERTa
WordPiece	Similar to BPE, but maximizes likelihood	BERT, DistilBERT
Unigram	Start with large vocab, prune low-probability tokens	T5, ALBERT
SentencePiece	Treats text as raw byte stream, language-agnostic	T5, XLNet, many multilingual models

Why different algorithms?

BPE: Simple, greedy, deterministic
WordPiece: More principled (likelihood-based), slightly better for BERT-style models
Unigram: Allows probabilistic tokenization (multiple valid splits), used in Japanese/Chinese
SentencePiece: Handles languages without clear word boundaries, no pre-tokenization needed

Common mistake Common Tokenization Pitfalls

Mistake 1: "Tokenization is just splitting on spaces" Why it feels right: In English, words are separated by spaces—seems obvious!

Why it's wrong:

Languages like Chinese/Japanese have no spaces: "我爱编程" (I love programming)
Compounds: "New York", "COVID-19" → should "New" and "York" be separate?
Morphology: "running" = "run" + "ing" → loses shared structure if treated as atomic
Rare words: "antidisestablishmentarianism" → model never learns it as one unit

The fix: Use subword tokenization. BPE/WordPiece learn that "running" = "run" + "##ing", so model can understand new forms like "jumping" = "jump" + "##ing".

Mistake 2: "Larger vocabulary is always better"

Why it feels right: More tokens = more precision, capture rare words!

Why it's wrong:

Embedding matrix size: $|V| \times d$ parameters. 100K vocab × 768 dim = 77M parameters just for embeddings!
Rare tokens: If "antidisestablishmentarianism" appears once, its embedding never gets properly trained
Softmax output: Probability distribution over 100K classes → expensive, hard to train The fix: Optimal vocab size balances coverage and trainability. 30K-50K is sweet spot for most languages. Subwords handle rare words by composition.

Mistake 3: "Tokenization is just preprocessing, doesn't affect model performance"

Why it feels right: It's just converting text to numbers—model does the real learning!

Why it's wrong:

Token boundaries = hard limits on what model can learn. If "New York" is one token, model can't learn "New" separately.
OV handling: Poor tokenization → many <unk> tokens → model blind to that content
Sequence length: Inefficient tokenization → longer sequences → quadratic attention cost
Multilingual: Byte-level tokenization enables truly universal models (mT5, BLOOM)

Real example: GPT-2 trained on English text encodes " (space) inefficiently in Python code, hurting code generation. Later models (Codex) use code-aware tokenization.

The fix: Tokenization is a core modeling choice. Match tokenizer to your domain and language distribution.

Recall Explain to a 12-Year-Old

Imagine you're teaching a robot to read, but the robot only understands numbers, not letters or words.

The problem: You show the robot the sentence "I love pizza," but it just sees squiggly shapes. It needs a translator.

Bad solution1: Break everything into letters: I → 9, (space) → 0, l → 12, o → 15, v → 22, e → 5... Now "love" is [12, 15, 22, 5]. The sentence becomes a list of 13 numbers! That's really long, and the robot has to remember that "l + o + v + e" means something about feelings—super hard!

Bad solution 2: Make every possible word a number: "I" → 1, "love" → 2, "pizza" → 3. Great! Short list: [1, 2, 3]. But what if tomorrow you say "I adore pizza"? The robot doesn't know "adore" because we never taught it that number. And English has like 170,000 words—too many numbers to remember!

Smart solution (tokenization): Break words into common PIECES. Like Lego blocks!

Common words stay together: "I" → 1, "love" → 2, "pizza" → 3
Rare words get broken into pieces: "adore" → "ad" (17) + "ore" (18)
Now if the robot learned "ad" from "advent" and "ore" from "explore," it can understand "adore" even though it's new!

How we choose pieces: We look at lots of sentences and find pairs of letters that appear together ALL THE TIME. Like "th," "ing," "ed." Those become blocks. We keep combining until we have about 50,000 different blocks—enough to build any word, but not too many to remember.

Magic moment: When the robot reads "I'm running to eat pizza," it knows "running" = "run" + "ing" and "eating" = "eat" + "ing," so it understands the pattern even if it's only seen "running" before, not "eating"!

Connections

4.2.02-BPE-algorithm - Deep dive into Byte Pair Encoding
4.2.03-WordPiece-and-SentencePiece - Alternative tokenization algorithms
4.3.01-Word-embedings - Tokens → vectors (next step)
4.1.05-Vocabulary-and-OV - Why vocabulary management matters
5.1.02-Transformer-architecture - Where tokenized sequences are processed
4.2.08-Multilingual-tokenization - Handling non-English text
3.4.03-Sequence-length-and-padding - Dealing with variable-length tokenized sequences

#flashcards/ai-ml

What is a token in NLP? :: The basic unit of text that a language model processes. Can be a complete word, subword, character, or byte. The model's vocabulary is the set of all possible tokens.

Why use subword tokenization instead of word-level?

(1) Handles rare/unseen words via composition (2) Reduces vocabulary size (3) Captures morphology (prefixes/suffixes) (4) No out-of-vocabulary problem (5) More efficient than character-level

What are the 4 steps of tokenization? :: (1) Normalization (clean text) (2) Pre-tokenization (split into words) (3) Token splitting (apply subword algorithm like BPE) (4) Numericalization (map to integer IDs)

What is the core idea of BPE?

Start with character vocabulary. Iteratively find the most frequent consecutive pair and merge it into a new token. Repeat until target vocabulary size. Frequent patterns become single tokens; rare words are character combinations.

What is the typical vocabulary size for modern LMs?

30K-100K tokens. Balance between coverage (fewer <unk> tokens) and efficiency (smaller embedding matrix, faster softmax).

Why does GPT-2 use the Ġ character?

Marks tokens that had a space before them. Preserves whitespace information for perfect reversibility when decoding token IDs back to text.

What is token fertility?

Average number of tokens per word. Typical BPE fertility is 1.3-1.5. Lower = more efficient tokenization (shorter sequences for same text).

What happens if vocabulary is too large?

(1) Huge embedding matrix (more parameters) (2) Rare tokens don't train well (sparse updates) (3) Expensive softmax over large vocabulary (4) Slower training and inference

What is the difference between BPE and WordPiece?

BPE merges most frequent pairs (gredy). WordPiece merges pairs that maximize likelihood of training data (more principled). Both achieve similar results; WordPiece used in BERT, BPE in GPT models.

Why is tokenization important for model performance?

(1) Token boundaries limit what can be learned (2) Poor tokenization → long sequences → higher compute cost (3) Many <unk> → model loses information (4) Domain mismatch hurts (e.g., code vs natural language) (5) Affects multilingual capability

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho yaar, tokenization ka core idea bahut simple hai — neural networks sirf numbers samajhte hain, text nahi. Toh humein raw text ko chote-chote units mein todna padta hai jinhe "tokens" kehte hain, aur phir un tokens ko numbers mein map karte hain. Ye ek bridge ki tarah hai text aur model ke beech. Ab yahan ek balance ka game hai: agar hum pura word ko ek token banate hain toh vocabulary explode ho jati hai (english mein lakhon words, plus typos aur naye words jaise "COVID-19" jo training ke time exist hi nahi karte). Aur agar hum har character ko alag token banate hain toh sequence bahut lambi ho jati hai — "Hello" 5 tokens ban jayega instead of 1 — aur transformer ka cost O(n²) hota hai, matlab lamba sequence = zyada computation.

Isliye smart solution hai subword tokenization, jismein sabse popular algorithm hai BPE (Byte Pair Encoding). Iska intuition ekdum natural hai: shuru mein sab kuch character-level pe hota hai, phir hum baar-baar sabse frequent consecutive pair dhundhte hain aur unhe merge karke ek naya token bana dete hain. Ye process repeat hota rehta hai jab tak humein desired vocabulary size na mil jaye. Iska magic ye hai ki common words automatically single token ban jaate hain (kyunki wo frequent hote hain), jabki rare words character combinations ki tarah rehte hain — isse OOV (out-of-vocabulary) problem solve ho jati hai. Morphology bhi capture hoti hai, jaise "run", "running", "ran" ka common part share ho jata hai.

Ye topic tumhare liye important kyun hai? Kyunki har modern LLM — ChatGPT ho ya koi bhi — pehle tumhara input tokenize karta hai. Tokenization pipeline (normalization → pre-tokenization → splitting → numericalization) samajhna zaroori hai kyunki yahi decide karta hai ki model kitna efficiently text ko process karega aur naye words ke saath kaise deal karega. Agar tum future mein NLP ya AI mein kaam karna chahte ho, toh ye foundation hai — iske bina baaki sab language modeling concepts adhure lagenge.

What is a Token?

The Tokenization Process

Step 1: Normalization

Step 2: Pre-tokenization

Step 3: Token Splitting (The Core Algorithm)

Step 4: Numericalization

Encoding and Decoding

Key Properties of Good Tokenization

Common Tokenization Algorithms

Connections

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Tokenization & Language Modeling

Connections