Byte-Pair Encoding

The Intuition

Given that it's hard to write rules that can comprehensively cover all meaningful subwords in the English language (or whatever language we're tokenizing), we want an algorithm that can learn from data that certain character sequences (e.g., "re" and "ism") tend to occur frequently and are therefore good candidates for treating as valid tokens.

At the same time, for the sake of efficiency, we don't want to always split words into their constituent subwords. If we've seen a word like "rebuild" in the data a lot, it makes more sense to just treat it as a single token instead of splitting it into "re" and "build". Splitting by subword should be viewed as a fallback option in the event that we see an unknown word.

Since our goal is to learn from data, we will proceed with a typical machine learning setup: we will train the BPE algorithm on a provided set of input data, known as the training data. The training phase is where the algorithm learns words and subwords. We can then use the trained algorithm to tokenize any given (new) input text.

Training the Tokenizer

Remember, we're starting with the premise that we don't have any hand-written rules for tokenization. Therefore, our algorithm needs to start from scratch.

What does "from scratch" mean in the context of tokenization? Well, if we have no rules for what constitutes a valid token, then we have no choice but to break our text into the smallest possible units: that is, characters! The BPE algorithm starts by taking the training data, splitting it into individual characters, and adding each unique character to the vocabulary as a token.

Consider a toy example where the training data is the string "defsasadepdef". The first pass of BPE tokenization will split this into one-character tokens: ['d', 'e', 'f', 's', 'a', 's', 'a', 'd', 'e', 'p', 'd', 'e', 'f']. The resulting vocabulary will be the set {'a', 'd', 'e', 'f', 's', 'p'}.

We're not done, of course. Now that we have a very basic set of tokens to start with, our goal is to build our way up to more complex tokens. This is where the "pair" in byte-pair encoding comes in. The algorithm now looks at all unique pairs of adjacent tokens in the data: ('d', 'e'), ('e', 'f'), ('f', 's'), and so on. It will count how many times each pair occurs. Then, the most frequent pair gets merged into a single token that gets added to the vocabulary.

In the toy example, we see that ('d', 'e') is in the lead, occurring a total of three times. Therefore, the BPE algorithm will merge 'd' and 'e' into a single token 'de' and add that to the vocabulary. Now the text is tokenized as ['de', 'f', 's', 'a', 's', 'a', 'de', 'p', 'de', 'f'], and the vocabulary contains {'a', 'd', 'e', 'f', 's', 'p', 'de'}.

The BPE algorithm continues until no further merges are possible (alternatively, you can set a max number of iterations or a max vocabulary size). The key thing to understand is that now that 'de' is a token, it can also be merged with other tokens. If you were to continue running the algorithm, you would see that 'de' eventually gets merged with 'f' (which follows it twice) to form a token 'def'.

It might help make things more clear if you see the BPE algorithm working on a more realistic example. You can interact with the applet below to step through the BPE algorithm one iteration at a time. On each iteration, pay attention to the token pair counts and observe how the most common token pair in the previous iteration gets merged into a single token in the current iteration. You can feel free to try running the algorithm on your own training data, but please note that all subsequent discussion will focus on the provided default training data ("run rush push pull running rushing pushing"), so you should do at least one full run with the default data so you can follow the rest of the discussion.

Stepping through the algorithm is pretty neat, since you can watch it slowly learn intuitive subword splits in real time:

• After 4 iterations (on the provided default training data) the algorithm has learned the "ing" suffix.
• After 6 iterations, it has learned the word "push" and tokenized "pushing" into "push" and "ing".
• After 7 iterations, it has learned the word "run" and tokenized "running" into "run", "n", and "ing". (That extra 'n' in "running" is certainly annoying...thanks, English!)
• After 8 iterations, it has learned the word "rush" and tokenized "rushing" into "rush" and "ing".
• And after 14 iterations, it has learned every word in the training data and added all of them to the vocabulary!

We need to note an important subtle difference between the results of the BPE algorithm and the results of a simpler split-by-whitespace tokenizer. Yes, every word that the BPE algorithm sees during training ends up in the vocabulary. But the key observation is that the vocabulary learned by BPE doesn't only include these words, it includes every subword that resulted from merges during training! So while "pushing" is in the vocabulary as a single token, "push" and "ing" are also in there as separate tokens. This wouldn't have happened with the simpler split-by-whitespace tokenizer. This property turns out to be very useful when you use the trained BPE tokenizer on new data and encounter out-of-vocabulary words!

Using the Trained Tokenizer

Suppose we take the BPE tokenizer learned above on the provided default training data and use it to tokenize some new text where the word "pulling" appears. "pulling" is not in the vocabulary we learned, so it is out-of-vocabulary. If this was a basic rule-based tokenizer, at this point we would probably have to either discard it or replace it with a generic "<OOV>" token. But the BPE algorithm lets us do something that feels more humanlike!

When you use a trained BPE tokenizer (sometimes also referred to as an encoder) to tokenize new text, it basically runs the exact same algorithm as it did during training, just without the ability to add new tokens to the vocabulary. So, here's a walkthrough of what will happen with "pulling":

1. As before, the algorithm will start by splitting "pulling" into individual character tokens: ['p', 'u', 'l', 'l', 'i', 'n', 'g'].
2. Then, like before, it will attempt to merge adjacent token pairs. The difference from before is that, since we cannot add new tokens to the vocabulary, we can only perform merges that exist in the vocabulary. Of the token pairs in ['p', 'u', 'l', 'l', 'i', 'n', 'g'], the ones that exist as tokens in the vocabulary are 'pu', 'll', and 'ng'. So the algorithm will do those merges and produce ['pu', 'll', 'i', 'ng'].
3. BPE is a greedy algorithm: it will perform every possible merge until no more merges are possible. In this case, the algorithm sees that it can keep merging, because 'pu' and 'll' can be merged into 'pull', and 'i' and 'ng' can be merged into 'ing'. So on the next iteration, it will do those merges and produce ['pull', 'ing'].
4. At this point, no further merges are possible (there is only one remaining token pair and that pair doesn't have a corresponding token in the vocabulary), so ['pull', 'ing'] is the final result.

Notice how this final result looks pretty much like how a human might intuitively split "pulling": the word "pull" followed by the suffix "ing"!

In practice, all modern LLMs use some kind of subword tokenizer. This is what gives them the ability to process out-of-vocabulary tokens (like WartCo) in humanlike ways (e.g., knowing that "Co" is a company suffix). BPE is one of the most popular subword tokenizers, and is the one used by OpenAI's GPT family of models (which powers ChatGPT). But other popular choices include WordPiece (invented by Google for their BERT model) and a variation known as SentencePiece.

(When logged in, completion status appears here.)

Previous Page Go to Parent Page