# Let's build the GPT Tokenizer

Andrej Karpathy

Let's build the GPT Tokenizer - YouTube

[Let's build the GPT Tokenizer](https://www.youtube.com/watch?v=zduSFxRajkE) [Andrej Karpathy](https://www.youtube.com/channel/UCXUPKJO5MZQN11PqgIvyuvQ)

## Introduction to Tokenization

- Tokenization: process of converting text into sequences of tokens for LLMs
  - Necessary but complex part of working with LLMs
  - Many issues with LLMs trace back to tokenization problems
- Previous video used simple character-level tokenization
  - Created vocabulary of 65 characters for Shakespeare dataset
  - Each character mapped to an integer token
  - Used embedding table (65 rows) to convert tokens to vectors
- State-of-the-art LLMs use more complex tokenization schemes
  - Work on chunk level rather than character level
  - Use algorithms like Byte Pair Encoding (BPE)

## Tokenization in GPT Models

- GPT-2 paper introduced byte-level encoding for tokenization
  - Vocabulary of 50,257 tokens
  - Context size of 1,024 tokens
- Tokens are fundamental units in LLMs
  - Everything measured in tokens (training data, context window)
  - Llama 2 paper mentions training on 2 trillion tokens

## Tokenization Issues and Oddities

- Many LLM limitations trace back to tokenization problems:
  - Difficulty with spelling tasks
  - Issues with simple string processing
  - Poor performance with non-English languages
  - Problems with simple arithmetic
  - Issues with Python code
  - Warnings about trailing whitespace
  - Strange behavior with certain tokens (e.g., "solid gold Magikarp")

## Tokenizer Web Demo

- TikToken.app demonstrates live tokenization in browser
- Examples of tokenization inconsistencies:
  - "Tokenization" becomes two tokens (1634, 318)
  - Numbers tokenize inconsistently (127 is one token, 677 is two tokens)
  - "egg" by itself is two tokens, but " egg" is one token
  - Case sensitivity affects tokenization
  - Non-English languages use more tokens for equivalent text
  - Python code spaces are individual tokens in GPT-2

## Unicode and Byte Representations

- Strings in Python are immutable sequences of Unicode code points
- Unicode defines ~150,000 characters across 161 scripts (as of v15.1, Sept 2023)
- Python's `ord()` function returns Unicode code point for a character

- Example: ord('H') = 104, ord('😀') = 128512
- Unicode encodings translate code points to byte streams:
  - UTF-8: variable length (1-4 bytes per code point), most common
  - UTF-16: less efficient for ASCII/English
  - UTF-32: fixed length but wasteful

## Byte Pair Encoding (BPE) Algorithm

- Basic principle: iteratively merge most frequent pairs of bytes/tokens
- Example process with small vocabulary (a,b,c,d):
1. Start with sequence of tokens from small vocabulary
2. Find most frequent pair (e.g., "aa")
3. Create new token (e.g., "Z" = "aa")
4. Replace all occurrences of pair with new token
5. Repeat until desired vocabulary size or no more frequent pairs
- Implementation steps:
1. Convert text to UTF-8 bytes
2. Find most common byte pairs
3. Replace with new token
4. Repeat until desired vocabulary size reached
- After merges, sequence is compressed but vocabulary expanded
- Compression ratio achieved: 1.27 after 20 merges in demo

## Tokenizer Architecture

- Tokenizer is separate from LLM itself
  - Has its own training set
  - Pre-processing stage run once
  - Trained using BPE algorithm
- Tokenizer acts as translation layer:
  - Encoding: text → token sequence
  - Decoding: token sequence → text
- After tokenizer is trained, LLM is trained on tokenized data

## Encoding and Decoding Implementation

- Decoding function:
  - Takes list of token IDs
  - Uses vocabulary mapping (token ID → bytes)
  - Concatenates bytes and decodes with UTF-8
  - Needs error handling for invalid UTF-8 sequences
- Encoding function:
  - Takes text string
  - Encodes to UTF-8 bytes
  - Iteratively applies merges from lowest to highest index
  - Returns list of token IDs
- Challenges:
  - Handling invalid UTF-8
  - Ensuring correct merge order
  - Edge cases with single characters

## GPT-2 Tokenizer Details

- Uses regex pattern to split text before tokenization
  - Prevents merging across different types (letters, numbers, punctuation)
  - Example pattern splits on:
    - Apostrophes ('s, 't, etc.)
    - Letters (any language)
    - Numbers (any script)
    - Punctuation
    - Whitespace
  - Case-sensitive (should have used re.IGNORECASE)
- Implementation details:
  - Text split into chunks based on regex
  - Each chunk tokenized independently
  - Results concatenated
  - Prevents certain merges (e.g., letter + punctuation)

## Special Tokens

- Tokens added outside normal BPE process
- GPT-2 has one special token: end of text (ID 50256)
  - Used to delimit documents in training set
- GPT-4 adds more special tokens:
  - FIM (Fill in the Middle) tokens: prefix, middle, suffix
  - Additional special token for SLERP
- Chat models add conversation structure tokens
  - Start/end of messages
  - User/assistant identifiers
- Adding special tokens requires model surgery
  - Extending embedding matrix
  - Extending final layer projection

## TikToken Library

- Official tokenization library from OpenAI
  - Only for inference, not training
  - Supports different tokenizers (GPT-2, GPT-4)
- GPT-4 tokenizer improvements over GPT-2:
  - Vocabulary size ~100K vs ~50K
  - Case-insensitive regex pattern
  - Better handling of whitespace in code
  - More efficient with Python spaces
  - Limits number merges to 3 digits

## Sentence Piece Tokenizer

- Alternative tokenization library used by Llama and Mistral
- Key differences from TikToken:
  - Works directly on code points (not bytes)
  - Falls back to bytes for rare code points
  - Has many configuration options
  - Has concepts like "sentences" and normalization
- Llama 2 configuration:
  - Uses byte fallback (true)
  - Adds dummy prefix (space at beginning)
  - Has special tokens (UNK, BOS, EOS)
  - Splits digits
- Complex with many settings and potential pitfalls

## Vocabulary Size Considerations

- Impacts model architecture in two places:
  - Token embedding table size
  - Final layer projection size
- Trade-offs:
  - Larger vocabulary → denser input but more parameters
  - Smaller vocabulary → longer sequences but less computation
  - Too large vocabulary → undertrained token embeddings
  - Too small vocabulary → inefficient context usage
- State-of-the-art models use ~100K tokens
- Model surgery for adding tokens:
  - Resize embedding table
  - Resize final layer projection
  - Initialize new parameters with small random values

## Advanced Tokenization Applications

- Gist tokens: compressing prompts into few learned tokens
- Multimodal tokenization: extending to images, video, audio
- Parameter-efficient fine-tuning using token embeddings

## Tokenization-Related Issues Explained

1. Spelling difficulties
   - Long tokens make character-level tasks difficult
   - "default_style" is a single token, can't count letters in it
2. Non-English language performance
   - Tokenizes less efficiently (more tokens per sentence)
   - Training data imbalance for both model and tokenizer
3. Arithmetic issues
   - Numbers tokenized inconsistently
   - Digit-by-digit operations difficult across token boundaries
4. Python code performance
   - GPT-2: each space is separate token, wastes context
   - GPT-4: improved by merging spaces
5. Special token behavior
   - "end of text" causes model to halt
   - Special token handling in inference
6. Trailing whitespace warning
   - Space changes token boundaries
   - Creates out-of-distribution scenario
7. "Solid gold Magikarp" phenomenon
   - Token in vocabulary but never seen in LLM training
   - Untrained embedding leads to undefined behavior
8. Format efficiency
   - YAML more token-efficient than JSON
   - Important for context length and cost optimization