Let's build the GPT Tokenizer

Andrej Karpathy

Let's build the GPT Tokenizer - YouTube

Let's build the GPT Tokenizer Andrej Karpathy

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