Tokenizers

Fundamentally, tokenization is a bidirectional mapping between raw text and a list of integers. Tokenizers discretize the input/output space, which is necessary to make tractable all subsequent learning steps in LLMs. There are different approaches to tokenizers, but the central tradeoff is between the information contained within each token and vocabulary size. We want informational content per token to be as high as reasonably possible - this will save us time in training and inference. But we want to keep the vocabulary size small for a couple reasons:

  • Most vocabulary usage follows a predictable power law distribution, where a small minority of the terms in the vocabulary account for the vast majority of the content. As vocabulary grows, this distribution does not change, but the tail continues to get longer. As a result, more and more of the vocabulary space is dedicated to terms with infrequent usage. In short, this results in lots of dead weight(s).

  • Tokens map to a more compact representation called an embedding. Without fully explaining embedding matrixes here, suffice it to say that every additional term added to the vocabulary incurs a nontrivial computational cost during training and inference.

As informational content increases, vocabulary size increases as well: there's not a ton of information in a single letter, but there's only 26 of them. There's much more information in a word, but there's a million of them. There's even more information in a sentence (or a paragraph, or a book, or the entire internet), but the complete list of possible sentences is functionally innumerable. The optimal solution lives somewhere in the middle: we tokenize terms that are just slightly smaller than words in most cases, which allows us to capture a substantial amount of information per token while keeping the total vocabulary at a manageable size (GPT had a ~40k token vocabulary, and GPT-2 & 3 had a 50,247 token vocabulary).

With the fundamental goal of tokenization in mind, the next important question is how that vocabulary, that set of subword tokens, is produced. The GPTs use an approach called Byte Pair Encoding (BPE), which functions like so:

  1. Split all the training/input text into characters (bytes)

  2. Count all adjacent symbol pairs

  3. Add the most frequent pair to our vocabulary as a new, distinct symbol

  4. Replace all occurances of that pair with this new symbol

  5. Repeat until we hit our ideal vocab size

This approach has very nice generality, and allows for vocabulary size to be explicitly controlled while ensuring that every possible sequence remains tokenizable. While it does not explicitly guarantee a uniform distribution of informational content per token, in practice it seems to produce this effect.