BPE (Byte Pair Encoding): What It Is and Why It Matters for LLMs

Are models like GPT limited to just the words in their training set? If the word "long" is in the data but "length" isn't, how does the model handle it? How do models like GPT capture the morphology of a language? That's exactly what this article is about.

To a computer, there's no such thing as quick, quickest, or quickly. There are only numbers. So we first have to split the text into pieces, give each piece an index, and build up a vocabulary. The real question is this: how big should a token be?

Two solutions come to mind first:

• Make every word a single token.
• Make every character a single token.

Try both and you run into the two opposite ends of the problem. Word-level tokenization produces short sequences but can't cope with words it hasn't seen. Character-level tokenization can spell almost any word, but this time it stretches sequences out needlessly, and long sequences can become a headache for both memory and computation.

BPE sits right between these two extremes.

First, why wasn't word-level tokenization enough?

A tokenizer for a simple model like Word2Vec might look like this:

def clean_tokenize(text):
    return re.findall(r"[a-z]+", text.lower())

We lowercase the text, split it into words, and treat each word as its own token. Then we drop words that fall below a certain frequency from the vocabulary:

counter = Counter(
    word
    for document in tokenized_corpus
    for word in document
)
 
vocab = sorted([
    word
    for word, count in counter.items()
    if count >= min_count
])

On a small corpus (all the data we build our words from), this approach is perfectly understandable. But as the data grows, so does the vocabulary. quick, quicker, quickest, and quickly become four completely independent tokens as far as the model is concerned.

Worse, the current code drops words that aren't in the vocabulary outright:

idxs = [
    word_to_idx[word]
    for word in sentence
    if word in word_to_idx
]

So a rare word doesn't just turn into an <unk> token; it disappears from the sentence entirely. Not only does the model fail to learn that word, but the context structure around it can change too.

For example:

the unusual dog

If unusual isn't in the vocabulary, the sequence the model sees turns into:

the dog

Two words that weren't actually next to each other now look like neighbors. Since Word2Vec builds its context window over this sequence, the problem carries all the way from the tokenizer stage into the model's training data.

Is character-level tokenization the answer?

We can go to the other extreme and make every character its own token:

quickest → q · u · i · c · k · e · s · t

This keeps the vocabulary quite small. For an English corpus, letters, digits, and a handful of punctuation marks are usually enough.

The unknown-word problem largely disappears, too. Even if the model has never seen the word quickest before, it can represent its characters one by one.

But now the sequence gets long. thermometer, which the word-level tokenizer represents with a single token, turns into eleven tokens in a character-level tokenizer:

thermometer
↓
t · h · e · r · m · o · m · e · t · e · r

The number of steps the model has to process goes up. On top of that, repeating pieces like the, thermo, or meter get processed character by character every single time.

In short, the word-level approach produces pieces that are too big, and the character-level approach produces pieces that are too small. What we want is something in between: a tokenizer that learns its own pieces by looking at the corpus.

The idea behind BPE

BPE started life as a data-compression algorithm. Adapted to NLP, the core idea doesn't change all that much: we find the most frequent pair of adjacent symbols in the corpus, turn that pair into a single symbol, and repeat.

This approach, which splits rare words into subword units, was used especially in machine translation as a solution to the open-vocabulary problem. One well-known adaptation of BPE in NLP is Sennrich et al.'s “Neural Machine Translation of Rare Words with Subword Units”.

My implementation starts from characters rather than actual byte values. So technically we're writing a character-based BPE subword tokenizer.

The whole algorithm comes down to this loop:

Split words into characters → add an end marker → count pair frequencies → merge the most frequent pair → repeat

Splitting words into starting symbols

First we pull the frequencies of the words in the corpus. As I split each word into characters, I add <w> to the end:

def get_word_freqs(all_words):
    word_freqs = {}
 
    for word in all_words:
        word_key = tuple(word) + ("<w>",)
        word_freqs[word_key] = word_freqs.get(word_key, 0) + 1
 
    return word_freqs

For example, the word the is represented like this:

("t", "h", "e", "<w>")

Here <w> marks that the word has ended. Thanks to this marker, we can tell a character pair at the end of a word apart from the same pair in the middle of a word.

Then we count all the adjacent symbol pairs:

def get_pair_counts(word_freqs):
    pair_freqs = {}
 
    for tokenized_word, frequency in word_freqs.items():
        for first, second in zip(
            tokenized_word,
            tokenized_word[1:]
        ):
            pair = (first, second)
            pair_freqs[pair] = (
                pair_freqs.get(pair, 0) + frequency
            )
 
    return pair_freqs

Here we don't just count how many distinct words a pair appears in. We also factor in the word's corpus frequency. If a word occurs a hundred times, the pairs inside it contribute to the count a hundred times as well.

Merging the most frequent pair

The next step is to merge the pair we found across the entire vocabulary:

def merge_pair(pair, word_freqs):
    new_word_freqs = {}
 
    for word_tuple, frequency in word_freqs.items():
        symbols = list(word_tuple)
        index = 0
 
        while index < len(symbols) - 1:
            if (
                symbols[index] == pair[0]
                and symbols[index + 1] == pair[1]
            ):
                symbols[index] = (
                    symbols[index] + symbols[index + 1]
                )
                del symbols[index + 1]
            else:
                index += 1
 
        new_key = tuple(symbols)
        new_word_freqs[new_key] = (
            new_word_freqs.get(new_key, 0) + frequency
        )
 
    return new_word_freqs

Say the most frequent pair turned out to be ("t", "h"). In that case we merge the two into a new th symbol:

t · h · e · <w>
↓
th · e · <w>

If ("th", "e") is the most frequent pair in the next round, this time we learn the the token:

th · e · <w>
↓
the · <w>

We never told the tokenizer the rules of English morphology or what the word the means. We only counted repetitions in the corpus, and frequently used pieces gradually grew into larger tokens.

Learning the merge rules

The training function picks the most frequent pair each round and stores the operation as a merge rule:

def train_bpe(word_freqs, num_merges):
    merge_rules = []
 
    while len(merge_rules) < num_merges:
        pair_counts = get_pair_counts(word_freqs)
 
        if not pair_counts:
            break
 
        best_pair = max(
            pair_counts,
            key=pair_counts.get
        )
 
        merge_rules.append(best_pair)
        word_freqs = merge_pair(best_pair, word_freqs)
 
    return merge_rules

Running ten merges on a sample corpus produces these rules:

 1. 't'   + 'h'   → 'th'
 2. 'th'  + 'e'   → 'the'
 3. 'the' + '<w>' → 'the<w>'
 4. 's'   + '<w>' → 's<w>'
 5. 'n'   + '<w>' → 'n<w>'
 6. 't'   + '<w>' → 't<w>'
 7. 'd'   + 'o'   → 'do'
 8. 'do'  + 'g'   → 'dog'
 9. 'dog' + '<w>' → 'dog<w>'
10. 'q'   + 'u'   → 'qu'

The frequently occurring words the and dog gradually collapse into single tokens, while less common words keep being made up of small pieces.

If we raise the number of merges, the vocabulary grows and the sequences get shorter. If we lower it, the vocabulary shrinks but words get split into more pieces. So num_merges is one of the key parameters that sets the balance between vocabulary size and sequence length.

Encoding a new word

We apply the rules we learned during training to new words in the same order:

def encode(word, merge_rules):
    symbols = list(tuple(word) + ("<w>",))
 
    for first, second in merge_rules:
        index = 0
 
        while index < len(symbols) - 1:
            if (
                symbols[index] == first
                and symbols[index + 1] == second
            ):
                symbols[index] = first + second
                del symbols[index + 1]
            else:
                index += 1
 
    return tuple(symbols)

Encoding a few words with the ten rules the tokenizer learned gives us this:

quickest    → ('qu', 'i', 'c', 'k', 'e', 's', 't<w>')
smallest    → ('s', 'm', 'a', 'l', 'l', 'e', 's', 't<w>')
thermometer → ('the', 'r', 'm', 'o', 'm', 'e', 't', 'e', 'r', '<w>')
dog         → ('dog<w>',)

Even though the tokenizer never saw the whole word quickest, it can use the qu piece it learned earlier. And dog, which it saw very often, merges all the way down to a single token.

Decoding is even simpler:

def decode(tokens):
    return "".join(tokens).replace("<w>", "")

('qu', 'i', 'c', 'k', 'e', 's', 't<w>')
↓
quickest

Does BPE solve everything?

No. BPE doesn't learn the meaning or morphology of words; it only looks at which symbols frequently sit next to each other. So the subwords it produces don't have to be linguistically meaningful.

The results also depend directly on the corpus. Merge rules learned on a small or unbalanced corpus may not represent real text well.

Another limitation of my implementation is that it starts from characters. When a brand-new Unicode character that was never seen during training shows up, the tokenizer can leave it as a separate character, but the downstream model's vocabulary may not have an embedding for it. Byte-level BPE implementations tackle this differently by first converting text into a limited byte alphabet.

Even so, writing the algorithm from scratch lets us see much more clearly what the tokenizer is actually doing. Between the word-level approach's large, fragile vocabulary and the character-level approach's long sequences, we learn subwords from the corpus's own repetitions.

There's no magical word splitter here. Just frequency counting, two symbols sitting next to each other, and a merge operation applied over and over.

Yes, if you've made it this far, you now have a feel for how large models do tokenization too. Thanks for reading.