Speaker Notes

Let's build the GPT Tokenizer

Building a GPT tokenizer from scratch reveals how Byte Pair Encoding compresses text, why regex chunking and byte fallbacks prevent edge-case failures, and how tokenization bottlenecks LLM reasoning and spelling.

Andrej Karpathy · 2:13:34 · YouTube ↗

Tutorial · Solo speaker  Beginner · Concepts and Python implementation

Highlights

13 clips · 27 min of 134 min
    • Non-English text gets heavily fragmented into smaller tokens, bloating sequence length.
    • Token sequence bloating causes models to run out of context length during attention.
    • GPT-2 wastes tokens on individual spaces, severely hurting its ability to handle Python indentation.
    • BPE starts with a small base vocabulary and iteratively finds the most frequent token pairs.
    • Each most-frequent pair is replaced by a newly minted single token appended to the vocabulary.
    • Iterative merging progressively reduces sequence length while increasing vocabulary size.
    • The merge function scans through the token list sequentially from left to right.
    • When a target pair is matched, it appends the new replacement index and skips ahead by two positions.
    • Careful bounds checking is required to avoid out-of-bounds errors at the end of the list.
    • Iterates through token IDs sequentially from left to right
    • Checks for consecutive pair matches and replaces them with a new index
    • Requires careful bounds checking to prevent index errors at the rightmost element
    • Newly minted tokens remain eligible for merging in subsequent iterations
    • The process builds a binary forest rather than a single unified tree
    • Compression ratio tracks token sequence length reduction against vocabulary size growth
    • Certain token sequences predicted by language models may violate valid UTF-8 byte rules
    • Default strict decoding throws an invalid start byte error
    • Setting errors equals replace inserts a fallback character to gracefully handle malformed tokens
    • Regex patterns split text into independent chunks before tokenization begins
    • Prevents undesirable merges across category boundaries like letters and spaces
    • Ensures common words are not fused with adjacent punctuation marks
    • Splits text into independent categories like letters, numbers, and punctuation.
    • Ensures BPE merges never cross category boundaries, such as merging letters with spaces.
    • Fixes case-insensitivity issues for contractions and apostrophes present in GPT-2.
    • Limits number merging to a maximum of three digits to prevent bloated token sequences.
    • Adding special tokens requires expanding the Transformer embedding matrix rows.
    • The final projection layer into the classifier must also be extended and re-initialized.
    • SentencePiece executes BPE directly on code points rather than raw UTF-8 bytes.
    • Byte fallback maps rare code points to UTF-8 bytes to avoid excessive unknown tokens.
    • Unknown characters map to an Unk token by default, harming language model performance.
    • Byte fallback encodes unknown code points into UTF-8 bytes to ensure the model still receives valid inputs.
    • Llama correctly adopts byte fallback to prevent information loss.
    • Larger vocabularies increase embedding table and final linear layer compute costs.
    • Excessively large vocabularies cause individual tokens to appear rarely, resulting in undertrained parameters.
    • Information gets heavily compressed into single tokens, limiting reasoning capacity.
    • Common multi-character words are crammed into single tokens, preventing the model from perceiving individual letters.
    • Forcing the model to explicitly list characters before manipulation bypasses this limitation.
    • Tokenization is the fundamental bottleneck in character-level tasks.
    • Mismatches between tokenizer and model training sets create tokens with zero training updates.
    • These uninitialized embedding vectors act like unallocated memory in C programs.
    • Triggering these phantom tokens forces the Transformer into completely undefined behavior.

Questions this video answers

14 · every answer cites the moment it was said
01 Why does tokenization cause weird issues like poor spelling or arithmetic in LLMs? 2 sources · 4:32

Tokenization acts as the fundamental boundary layer for text, meaning that string manipulations and non-English text are often poorly represented. Simple tasks like spelling or arithmetic fail because the model sees arbitrary subword chunks instead of characters or proper words.

02 Why do non-English languages and Python code waste context window space in GPT-2? 2 sources · 10:27

GPT-2's tokenizer breaks non-English text and Python indentation spaces into many small, separate tokens. This bloats the sequence length and causes the model to run out of context length during attention.

03 Why can't we just use raw Unicode code points directly as inputs to language models? 2 sources · 17:52

While Unicode provides integers for characters, the standard encompasses roughly 150,000 characters and is constantly changing. Using them directly would create an unstable vocabulary and an unnecessarily large embedding space.

04 How does the Byte Pair Encoding algorithm compress text sequences? 2 sources · 24:16

BPE iteratively scans a sequence to find the most frequently occurring pair of tokens. It then mints a new vocabulary token for that pair and replaces all instances of it throughout the sequence.

05 How do I replace a specific token pair across an ID list? 2 sources · 32:02

You iterate through the token list sequentially and check if the current and next positions match the target pair. If a match is found, you append the new replacement index and advance the pointer by two to skip the pair. Otherwise, you just copy the single element over and increment by one.

06 Why does decoding certain token sequences throw a UTF-8 error? 2 sources · 45:48

Invalid UTF-8 errors occur because not every arbitrary byte sequence or poorly predicted language model token forms a valid Unicode character envelope. To prevent crashes when encountering invalid start bytes, you should set the decode error handling parameter to replace.

07 How do I encode text back into tokens using trained merges? 2 sources · 49:00

You start by encoding the raw text into UTF-8 bytes and casting it to a list of integers. Then, in a loop, you find all consecutive pairs using statistics and pick the one with the lowest index in your merges dictionary. You repeat this replacement process until no more eligible pairs can be merged.

08 Why do LLM tokenizers use a regex splitting pattern before merging? 2 sources · 58:25

A regex splitting pattern chunks text into independent categories like letters, numbers, and punctuation before applying merges. This prevents suboptimal cross-category merges, such as combining common words with adjacent punctuation marks into a single token.

09 What are special tokens used for in language model tokenizers? 2 sources · 1:19:49

Special tokens are used to delimit training documents, structure conversation turns between users and assistants, or enable features like fill-in-the-middle. They operate outside standard bpe merges and require extending the model's embedding matrix and final classifier layers.

10 How does SentencePiece differ from Tiktoken in its core approach? 2 sources · 1:29:44

SentencePiece operates directly on raw code points rather than utf-8 encoded bytes and uses a character coverage parameter to handle rare characters. It also includes extensive historical configuration options along with fallback behaviors for handling rare or unknown tokens.

11 What factors limit how large a vocabulary size can be? 1 source · 1:45:46

Increasing vocabulary size expands the token embedding table and the final linear layer, increasing computational cost and parameter count. Furthermore, rare tokens appear less frequently in training data leading to undertrained vectors, and excessively large chunks reduce the model's processing time per character.

12 How does tokenization impact an LLM's ability to spell or reverse words? 2 sources · 1:52:15

Words are chunked into multi-character tokens where too much information is crammed into a single unit, impairing character-level tasks like spelling or string reversal. When forced to process text broken down into individual characters instead of large pre-merged tokens, the model performs significantly better.

13 Why do trailing spaces cause warnings and poor performance in completion models? 2 sources · 1:59:28

Space characters are typically prepended to subsequent tokens, meaning a trailing space isolates a token boundary and forces the model out of its training distribution. Since the model rarely sees isolated trailing space tokens, predicting from this state causes unpredictable behavior or premature stopping.

14 What causes solid gold Magikarp bugs in language models? 2 sources · 2:07:41

These bugs occur when strings common in the tokenization dataset—such as specific Reddit usernames—are merged into dedicated tokens but are entirely absent from the actual model training data. Consequently, those embedding vectors remain completely uninitialized and untrained, acting like unallocated memory that triggers undefined behavior at test time.

Section-by-section summary

27 parts

Tokenization translates raw text into model tokens

Tokenization is a necessary preprocessing step that converts text strings into sequences of integer tokens for neural network embedding tables. State-of-the-art models use chunk-level algorithms like byte pair encoding rather than naive character-level splitting.

Tokenization defects drive many LLM weirdness issues

Many apparent neural network failures like poor arithmetic, non-english degradation, and spelling issues fundamentally trace back to tokenization quirks. Handling spaces, case sensitivity, and special tokens can drastically change model performance.

GPT-4 tokenizer improves efficiency over GPT-2

Comparing tokenizers reveals that GPT-4 reduces token counts by roughly half compared to GPT-2 for the same text. It groups common patterns like Python indentation spaces into single tokens, significantly saving context window length.

Python strings use Unicode code points

Python strings are immutable sequences of Unicode code points covering over 150,000 characters. While code points provide a universal mapping, they are not directly used as model tokens due to standard instability and vocabulary size.

UTF-8 provides variable-length byte encodings

The Unicode Consortium defines encodings like UTF-8 to translate code points into binary streams of one to four bytes. UTF-8 is widely preferred because it is backwards-compatible with ASCII and avoids the wasteful zero-padding seen in UTF-16 and UTF-32.

Byte pair encoding iteratively compresses sequences

Byte pair encoding builds a larger vocabulary by finding the most frequently occurring token pairs in a dataset and merging them into a new mint token. Repeating this process shrinks sequence lengths while expanding the vocabulary size.

Implementing byte pair encoding in Python

Building BPE from scratch involves counting adjacent token pairs using a frequency dictionary and writing a merge function to replace them with a new index. Tuning the number of merge iterations controls the final vocabulary size and sequence compression.

Building a binary forest of token merges

Running the merge loop over a large corpus builds up a merge dictionary, creating a binary forest of combined token representations. Adjusting the target vocabulary size acts as a hyperparameter that directly dictates sequence length compression.

Tokenizers operate as independent pre-processing stages

The tokenizer is entirely separate from the downstream language model and requires its own specialized training corpus. Altering the language and code mix in the tokenizer's training data directly affects token density and model context length efficiency.

Decoding token sequences back to strings securely

Decoding builds a vocabulary mapping from token IDs to byte strings and concatenates them back into raw text. Because not all token sequences form valid UTF-8, handling decoding errors with replacement characters prevents runtime crashes.

Encoding text by applying merges in priority order

Encoding converts text to bytes and iteratively applies learned merges in the exact chronological order they were created. Using Python's min function with a custom key identifies the most eligible merge candidate based on its index in the merges dictionary.

Handling edge cases and validating round-trip consistency

Short or empty input strings require early returns to prevent indexing errors in the merge search logic. Testing round-trip encode and decode operations on training and validation data confirms implementation correctness.

Preventing suboptimal cross-category merges with regex

Naive BPE can undesirably merge words with adjacent punctuation or spaces, clustering semantics incorrectly. State-of-the-art models like GPT-2 use a regex pattern to chunk text into separate categories before tokenization takes place.

Analyzing the GPT-2 regex splitting pattern and its quirks

The GPT-2 regex pattern splits text by letters, numbers, and punctuation, ensuring merges never cross these logical boundaries. However, hardcoded rules for contractions and case sensitivity introduce subtle edge cases and language inconsistencies.

GPT-4 tokenizer updates regex and vocabulary size

OpenAI's Tiktoken library provides official inference code for GPT-2 and GPT-4 tokenizers. GPT-4 expands the vocabulary to 100K and updates the regex to fix case sensitivity and limit multi-digit number merging.

GPT-2's encoder files match custom BPE algorithms

OpenAI's released encoder code relies on two saved files containing vocabulary and merge rules. Despite some spurious byte-encoding wrapper layers, the core algorithm matches custom BPE implementations.

Special tokens delimit documents and conversation turns

Special tokens like end-of-text or fill-in-the-middle are inserted outside the standard BPE pipeline. Adding these tokens to a trained model requires structural model surgery to expand embedding and classifier layers.

Training custom tokenizers reproduces GPT merge patterns

An open-source repository allows building and training custom BPE tokenizers from scratch. Training on custom datasets like Wikipedia yields merge orders remarkably similar to OpenAI's models.

SentencePiece operates directly on code points

Unlike Tiktoken, SentencePiece performs BPE on raw code points rather than UTF-8 bytes. It uses a byte fallback mechanism to handle rare or unseen code points gracefully instead of mapping everything to unknown tokens.

SentencePiece carries extensive historical configuration options

SentencePiece includes numerous legacy configuration parameters inherited from classical NLP tasks. Many options like text normalization and sentence chunking are counterproductive for modern large language models.

SentencePiece vocabulary layout and dummy prefixes

SentencePiece organizes its vocabulary sequentially into special tokens, byte tokens, merge tokens, and raw code points. It also uses dummy prefixes to ensure words at the start and middle of sentences are tokenized consistently.

Vocabulary size is an empirical trade-off

Increasing vocabulary size expands the embedding table and the final linear layer, increasing compute cost and risking parameter undertraining. Engineers can perform minor model surgery to resize embeddings when introducing new special tokens.

Tokenization scales to new modalities and compressed prompts

Transformers process non-text modalities like images and video by chunking inputs into discrete or soft tokens. Techniques like gist tokens compress long prompts into specialized embeddings without retraining the core model weights.

Tokenization causes LLM weaknesses in spelling and math

LLMs struggle with spelling, reverse strings, and arithmetic because words and numbers are arbitrarily chunked into tokens rather than processed character-by-character. Non-English text also suffers from severe token blowup due to undertrained vocabularies.

Special tokens and trailing spaces create edge-case bugs

Hardcoded special tokens can break prompt parsing and trigger unexpected refusal behaviors when exposed to user input. Trailing spaces force models out of distribution by altering token boundaries and splitting prefix characters.

Untrained tokens lead to undefined model behaviors

Tokens present in the tokenizer training set but absent from the model training set remain uninitialized and untrained. Invoking these phantom tokens pulls random embedding vectors, causing erratic behaviors like hallucinations, insults, or safety violations.

Format efficiency and final tokenization recommendations

Structured formats like YAML offer higher token density than JSON, reducing context length and API costs. Developers should use Tiktoken for efficient inference or carefully configure SentencePiece if training custom vocabularies from scratch.

0:00 / 2:13:34
k play/pause · f fullscreen · m mute
n next · p previous clip · t highlights/full
< > slower/faster · / search what was said
  • Byte Pair Encoding5× · first 2:43

    An algorithm used to iteratively compress text sequences by replacing frequent token pairs with new tokens.

  • Unicode code points4× · first 15:51

    Numerical values defined by the Unicode standard to represent characters.

  • get stats2× · first 28:40

    Python function that counts the frequency of consecutive token pairs in a list.

  • merges33× · first 36:13

    Dictionary mapping child token pairs to a new minted token index.

  • UTF-818× · first 18:23

    Byte encoding standard used to convert raw strings into byte sequences.

  • Tik token10× · first 1:10:42

    OpenAI's official open-source library for fast tokenization and inference.

  • SentencePiece15× · first 1:28:52

    An unsupervised text tokenizer and detokenizer library used by models like Llama and Mistral.

  • Fill in the middle1× · first 1:24:09

    A special token training format used for code completion tasks with prefix, middle, and suffix tokens.

  • Byte fallback2× · first 1:38:30

    A mechanism where unknown or rare code points are encoded using UTF-8 bytes instead of mapping to a generic unknown token.

  • Solid gold Magikarp8× · first 5:30

    An untrained token resulting from a dataset mismatch between tokenization and training, causing undefined model behavior.