Abstract:

This comprehensive guide, a text-based adaptation of Andrej Karpathy's video tutorial, delves into the critical and often overlooked process of tokenization in Large Language Models (LLMs). It begins by explaining the fundamentals, moving from basic character-level encoding to the necessity of UTF-8 byte representation. The core of the tutorial is a detailed walkthrough of the Byte Pair Encoding (BPE) algorithm, demonstrating how it iteratively merges frequent byte pairs to create a compressed and efficient token vocabulary. The guide then contrasts this basic implementation with the more sophisticated approaches of modern LLMs like GPT-2 and GPT-4, which use regex-based pre-tokenization to prevent nonsensical merges across linguistic categories (e.g., words and punctuation). It also explores alternative methods like SentencePiece, used by models such as Llama 2, which operates on Unicode code points with a byte fallback. The article highlights the crucial role of special tokens (e.g., <|endoftext|>) in structuring data for the model. Finally, it provides clear explanations for many common LLM failures—including poor spelling, arithmetic errors, and biases against non-English languages—by tracing them back to the inherent quirks and limitations of their tokenization schemes.

A Complete Guide to Tokenization in LLMs

• Introduction: Why Tokenization Matters Tokenization is the process of converting text into a sequence of integers (tokens) that an LLM can understand. It is the root cause of many peculiar LLM behaviors, including difficulties with spelling, string manipulation, arithmetic, non-English languages, and coding. Understanding tokenization is essential for diagnosing and working around these issues.

• The Unicode and UTF-8 Foundation To handle all the world's languages and symbols, text is represented as a sequence of Unicode code points. However, using these directly as tokens would create an unstable and massive vocabulary (~150,000+). The standard approach is to first encode the text into a universal byte stream using UTF-8. This creates a small, stable base vocabulary of 256 possible bytes, but results in very long sequences, which is inefficient for LLMs with finite context windows.

• The Byte Pair Encoding (BPE) Algorithm BPE is a compression algorithm that addresses the long sequence problem of raw byte encoding. It works by:

  1. Starting with a base vocabulary (e.g., the 256 UTF-8 bytes).
  2. Iteratively finding the most frequently occurring pair of consecutive tokens in the training text.
  3. Merging this pair into a new, single token and adding it to the vocabulary.
  4. Repeating this process for a desired number of merges, resulting in a larger vocabulary and a shorter, more compressed token sequence.

• GPT-2 and GPT-4 Tokenizers: Regex Pre-tokenization A naive BPE algorithm can merge text across logical boundaries (e.g., merging "dog" and "." into a single "dog." token). To prevent this, GPT-2 and GPT-4 use a crucial pre-processing step:

  • A complex regular expression (regex) first splits the input text into chunks based on character categories (letters, numbers, punctuation, spaces).
  • The BPE algorithm is then applied within these chunks but never across them.
  • This results in more meaningful tokens that respect linguistic structure. GPT-4's tokenizer improves upon GPT-2's with features like case-insensitive matching for contractions. The tiktoken library is OpenAI's official implementation.

• SentencePiece and Alternative Approaches SentencePiece, used by models like Llama 2 and Mistral, is another popular tokenization library. It differs from the GPT approach in a key way:

  • tiktoken (GPT): Works directly on UTF-8 bytes. Text -> Bytes -> BPE on Bytes.
  • SentencePiece (Llama): Works primarily on Unicode code points. For rare characters not in the vocabulary, it "falls back" to representing them as a sequence of their individual UTF-8 byte tokens. This can make it more efficient for non-English languages with large character sets.

• Special Tokens and Extensions Special tokens (e.g., <|endoftext|>, <|im_start|>) are strings that are handled separately from the BPE algorithm. They are mapped directly to specific token IDs and are used to provide structural signals to the LLM, such as marking the end of a document or delimiting conversations between a user and an assistant. Adding new special tokens requires "model surgery" to expand the LLM's embedding table.

• Common Tokenization Issues and Pitfalls Explained

  • Why LLMs can't spell: A word like ".DefaultCellStyle" might become a single, indivisible token. The model sees it as one atomic unit and has no access to its internal character structure, making tasks like spelling or reversing the string impossible.
  • Why LLMs are worse at non-English: Tokenizers trained primarily on English data are less efficient for other languages. A simple English phrase might become 5 tokens, while its Korean translation becomes 15, consuming context length much faster.
  • Why LLMs are bad at arithmetic: Numbers are tokenized arbitrarily (e.g., "804" might become tokens for "80" and "4"). This breaks the positional alignment of digits that is critical for performing algorithms like addition.
  • The SolidGoldMagikarp phenomenon: This Reddit username became a single token due to its high frequency in the tokenizer's training data. However, it was absent from the LLM's training data. When a user provides this token, the model accesses an untrained, random part of its memory (embedding), leading to bizarre and unpredictable behavior.
  • Why YAML is preferred over JSON: YAML is often more "token-efficient" than JSON, meaning the same structured data can be represented with fewer tokens. This saves on cost and context window space.