AI summary by TwinMind
Let's build the GPT Tokenizer
Andrej Karpathy
2h 13m 34s
Introduction to Tokenization
- Tokenization is least favorite part of working with LLMs but necessary to understand
- Many oddities with LLMs trace back to tokenization issues
- Tokenization is the process of converting text into sequences of tokens (integers)
- In previous "Let's Build GPT" video, used naive character-level tokenization with 65 possible characters
- Character-level approach: each character maps to integer token, used embedding table for lookup
Problems with Character-Level Tokenization
- State-of-the-art models use more complicated schemes than character-level
- Deal with chunk-level tokens using algorithms like Byte Pair Encoding (BPE)
- GPT-2 paper introduced byte-level encoding for tokenization
- Vocabulary of 50,257 possible tokens
- Context size of 1,024 tokens
- Llama 2 paper: trained on 2 trillion tokens
- Tokens are fundamental unit/atom of large language models
Common Tokenization Issues
- Spelling tasks difficulty due to tokenization
- Simple string processing challenges
- Non-English languages work worse (tokenization-related)
- Simple arithmetic problems
- Python coding issues (especially GPT-2)
- Trailing whitespace warnings
- "Solid gold Magikarp" causing model breakdown
- YAML preferred over JSON for efficiency
Tokenization Demonstration
- Used tiktoken web app to show live tokenization
- Example: "tokenization is at the heart" → 300 tokens in GPT-2
- Numbers tokenized inconsistently (127 as single token, 677 as two tokens)
- Case sensitivity: "egg" vs "Egg" vs " egg" all different tokens
- Korean text uses more tokens than English equivalent
- Python code: individual spaces become separate tokens (token 220)
Unicode and UTF-8 Encoding
- Python strings are sequences of Unicode code points
- Unicode standard defines ~150,000 characters across 161 scripts
- Used ord() function to get Unicode code points
- UTF-8 encoding translates Unicode to binary data (1-4 bytes per code point)
- UTF-8 preferred over UTF-16/UTF-32 for efficiency and ASCII compatibility
- Raw UTF-8 bytes would give vocabulary of only 256 tokens (too small)
Byte Pair Encoding (BPE) Algorithm
- Starts with UTF-8 byte sequences (256 base tokens)
- Iteratively finds most frequent consecutive pair
- Replaces pair with new token, increments vocabulary
- Example: AA → Z, AB → Y, ZY → X
- Compresses sequence length while growing vocabulary
- Creates binary forest structure of merges
BPE Implementation
- Training text encoded to UTF-8 bytes
- get_stats() function counts consecutive pairs
- merge() function replaces pairs with new tokens
- Iterative process: find most common pair → merge → repeat
- Compression ratio achieved: ~1.27 with 20 merges
- Tokenizer training is separate preprocessing stage from LLM training
Encoding and Decoding
- Decoding: token IDs → bytes → UTF-8 decode → text
- Handle invalid UTF-8 with errors='replace' parameter
- Encoding: text → UTF-8 bytes → apply merges in order
- Must handle edge cases (empty strings, single characters)
- Bidirectional: encode(decode(tokens)) = tokens for valid sequences
GPT-2 Tokenizer Details
- Uses regex pattern to split text before BPE
- Prevents merging across categories (letters, numbers, punctuation)
- Pattern separates: letters, numbers, apostrophe contractions, punctuation
- Spaces included at beginning of tokens
- Issues: case sensitivity, Unicode apostrophes, language-specific rules
- 50,257 tokens = 256 bytes + 50,000 merges + 1 special token
Special Tokens
- End-of-text token (50256) delimits documents
- GPT-4 adds: fim_prefix, fim_middle, fim_suffix tokens
- Fill-in-the-middle (FIM) functionality
- Special tokens bypass normal BPE algorithm
- Used extensively in chat models for conversation structure
- Require model surgery when added (embedding table, output layer)
Tiktoken Library
- Official OpenAI tokenization library (inference only)
- GPT-2: 50K vocabulary, GPT-4: 100K vocabulary
- Same text uses ~half tokens in GPT-4 vs GPT-2
- Improved Python handling: groups multiple spaces into single tokens
- Pattern changes: case-insensitive matching, 1-3 digit number limits
Sentence Piece
- Google library supporting both training and inference
- Used by Llama, Mistral, and other models
- Works on Unicode code points, not bytes
- Byte fallback for rare characters
- Many configuration options and historical baggage
- Add dummy prefix to normalize word boundaries
- Character coverage parameter determines rare token handling
Vocabulary Size Considerations
- Affects embedding table size and final linear layer computation
- Trade-off: larger vocab = shorter sequences but more parameters
- Risk of undertrained token embeddings with very large vocabularies
- Typical modern sizes: 50K-100K tokens
- Can extend vocabulary with model surgery for new special tokens
Tokenization Problems Explained
- Spelling issues: Long tokens like "defaultStyle" compress too much information
- Non-English inefficiency: 3x token bloat (Korean "hello" = 3 tokens vs English 1 token)
- Arithmetic problems: Numbers tokenized arbitrarily, breaks digit-level algorithms
- Python issues: Each space = separate token, wastes context length
- Trailing whitespace: Breaks token boundaries, causes distribution shift
- Solid gold Magikarp: Untrained tokens from mismatched training sets cause undefined behavior
- Format efficiency: YAML more token-efficient than JSON
Advanced Topics
- Multimodal tokenization: images, videos, audio as tokens
- Gist tokens for prompt compression
- Parameter-efficient fine-tuning via token embeddings
- Unstable tokens and partial token issues
- Security implications of special token handling
