Tokenization: BPE from Scratch, Vocab Size, and What Tokenizers Hide

Tokenization is the process of breaking down text into smaller units called tokens before a language model processes them. These tokens are usually integers that represent words or parts of words. The tokenizer is what the model interacts with, not the original letters or words. To construct a tokenizer, we can use a method called byte pair encoding (BPE).

BPE begins with individual characters and gradually merges the most frequently occurring adjacent character pairs into new tokens. This process continues until the vocabulary reaches a predetermined size. Larger vocabularies can represent text more efficiently, saving both tokens and contextual information, but they also require more parameters in the embedding matrix, which incurs additional computational costs.

The vocabulary, a list of tokens, is learned from data, which means it reflects the biases present in the data it was trained on. For example, English tends to have a smaller vocabulary, while languages like Urdu can require larger vocabularies. Furthermore, not all tokens are created equal, as some are trained more extensively than others.

Philip Gage first described BPE as a data compression technique in 1994. It wasn't until 2016 that Rico Sennrich, Barry Haddow, and Alexandra Birch adapted it for neural machine translation in their paper, Neural Machine Translation of Rare Words with Subword Units. This adaptation allowed any word to be represented as a sequence of frequent pieces, greatly improving the model's ability to handle rare words.

To better understand BPE, we implemented the algorithm in Python and applied it to a small corpus of words from our own published articles. After ten merges, we saw that the most frequent words became whole tokens, while rare words were broken into smaller pieces. For instance, "low" remained as one token, while "newest" became "low + e + s + t" and "wider" became "wid + er".

We then trained our BPE tokenizer on 83,159 real words from a larger corpus and measured its performance. The results showed that the first 100 merges cut the token count in half, and by the 2,000th merge, we achieved a token representation of 4.60 characters per token. However, beyond 5,000 merges, adding more tokens didn't provide any additional benefits for the held-out text, as the extra merges mostly memorized the quirks of our training corpus rather than learning general patterns.

In practical applications, BPE is a crucial component of many language models, including GPT-2 and Llama 3. It efficiently turns text into tokens, allowing the model to focus on the content rather than the individual letters or words.