AI summary by TwinMind

Let's build the GPT Tokenizer

Andrej Karpathy

2h 13m 34s

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

TwinMind

Get summaries like this for your own meetings

TwinMind takes notes in the background during meetings, lectures, and calls, then writes the summary for you.

Free plan to get started

No bot joins your calls

Phone, desktop & Chrome apps

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome

Your next meeting, summarized like this

TwinMind listens in the background and turns meetings, lectures, and calls into searchable notes you can chat with. Start free.

Available on phone, desktop & Chrome