Byte Pair Encoding: The Algorithm Behind GPT’s Tokenization

Byte pair encoding (BPE) is a compression algorithm modified to be used in large language model (LLM) tokenization. It is used to encode plain text into smaller meaning subwords in models like GPT-2, 3 and 4. The main idea behind the BPE algorithm is to substitute frequently occurring characters that are adjacent to each other with an unused token until the pre-defined vocabulary size is reached or there aren’t any pairs to merge.

This article covers:

• The BPE algorithm
• Python implementation
• Some questions I had as I was learning the concept

Key words and definition

The following are the key words needed to go through this article with ease:

1. Byte: a group of 8 bits. A bit is the smallest piece of information in a computer (either 0 or 1). Refer top this video here for more information.
2. Token: the smallest unit of data that a model can understand. This can be a character, word or subword.
3. Vocabulary: the complete set of tokens a tokenizer knows
4. UTF-8: a method of encoding Unicode code points into a sequence of bytes for storage and transmission on computers. Unicode is a universal character standard that assigns a unique number (called a code point) to every character, symbol, and emoji in all the world’s writing systems

The algorithm

Lets take the string “AAABDAAABAC” to be encoded using BPE.

The byte pair encoding algorithm visualization. It shows how an initial text is encoded.

This would be done using the following simple steps:

1. Find the most frequent pair
2. Merge it into an unused character/token
3. Repeat steps 1 and 2 until k (vocabulary size) or no more pairs occur

In the first iteration, “AA” occurs the most. This is replaced by Z. The replacement happens inplace. In the second iteration, “A B” is replaced with Y and so on. Fairly simple, but how does this translate to code?

BPE in Python

In python, the algorithm is the same but the end goal is not to compress the whole text entirely but to do it until a pre-defined vocabulary size is reached. This creates a vocabulary size that is large enough to represent common words and subwords as single tokens. The vocabulary size is a hyperparameter that helps balance sequence length, memory and model performance.

As models understand tokens, the text has to be tokenized first and then encoded. The standard technique used is to start with a base vocabulary of 256 possible byte values of UTF-8 encoding.

Code walkthrough

text = """
Ｕｎｉｃｏｄｅ! 🅤🅝🅘🅒🅞🅓🅔‽ 🇺‌🇳‌🇮‌🇨‌🇴‌🇩‌🇪! 😄 The very name strikes fear and awe into the hearts of programmers worldwide. 
We all know we ought to “support Unicode” in our software (whatever that means—like using wchar_t for all the strings, right?). 
But Unicode can be abstruse, and diving into the thousand-page Unicode Standard plus its dozens of supplementary annexes, reports, and notes can be more than a little intimidating. 
I don’t blame programmers for still finding the whole thing mysterious, even 30 years after Unicode’s inception.
A few months ago, I got interested in Unicode and decided to spend some time learning more about it in detail. 
In this article, I’ll give an introduction to it from a programmer’s point of view.
I’m going to focus on the character set and what’s involved in working with strings and files of Unicode text. 
However, in this article I’m not going to talk about fonts, text layout/shaping/rendering, or localization in detail—those are separate issues, beyond my scope (and knowledge) here.
"""

Step 1: Encode the text into UTF-8

tokens = text.encode('utf-8')
tokens = list(map(int, tokens))

We convert the text into a list of integers where each integer is a byte value between 0 and 255, representing UTF-8 encoding of the text.

Step 2: Count frequent pairs

def get_stats(ids):
    pairs = collections.defaultdict(int)
    for i, id_ in enumerate(ids):
        if i < len(ids) - 1:
            pairs[id_, ids[i+1]] += 1
    return pairs

Next, we define a function that counts how many times each adjacent pair of token IDs appears consecutively in the list.

Step 3: Merge frequent pairs

def merge_tokens(ids, pair, idx):
    new_ids = []
    i =0

    while i < len(ids):
        if i < len(ids) - 1 and ids[i] == pair[0] and ids[i+1]==pair[1]:
            new_ids.append(idx)
            i += 2
        else:
            new_ids.append(ids[i])
            i += 1
    return new_ids

The function iterates through the whole token list and replaces every occurance of the target pair with a new single token ID. We repeat this for the total of merges defined. The number of merges is calculated by subtracting 256 from the intended vocabulary size as we have 256 characters in UTF-8.

vocab_size = 276
num_merges = vocab_size - 256
ids = list(tokens)

merges = {}
for i in range(num_merges): #1
    stats = get_stats(ids) #2
    pair = max(stats, key=stats.get) #3
    idx = 256 + i #4
    print(f'merging {pair} into a new token {idx}')
    ids = merge_tokens(ids, pair, idx) #5
    merges[pair] = idx #6

in the above code:

• 1 iterate over the whole text for the number of intended merges

• 2 count all the adjacent pairs

• 3 get the most frequent pair

• 4 assign it a new id

• 5 replace all occurances

• 6 record the merge in a dictionary

Step 4: Build the vocabulary

vocab = {idx: bytes([idx]) for idx in range(256)}
for (p0, p1), idx in merges.items():
    vocab[idx] = vocab[p0] + vocab[p1]

We build the vocabulary, a lookup table with the base 256 bytes and then reconstructing each merged token by adding the two tokens that were merged to create it.

Step 5: Decode text

def decode(ids):
    tokens = b"".join(vocab[idx] for idx in ids) #1
    text = tokens.decode('utf-8', errors='replace') #2
    return text

To decode, we use the vocabulary from step 4 to look up each token ID from the input. We then convert everything back text using UTF-8 decoding.

Encoding and Decoding text

Let’s say we train our tokenizer on the following

text = """
the cat sat on the mat
the cat ate the fat rat
the rat sat on a mat
a cat and a rat and a bat
"""

Now let’s encode text that the tokenizer has not seen before

tokenizer.encode("the bat sat on the cat and the rat ate a mat")

the  --> 260
b --> 98
at  --> 257
s --> 115
at  --> 257
o --> 111
n --> 110
  --> 32
the cat  --> 265
a --> 97
n --> 110
d --> 100
  --> 32
the  --> 260
r --> 114
at  --> 257
at --> 256
e  --> 258
a  --> 262
m --> 109
at --> 256

The encoding shows the the tokenizer learnt from the training text. Common words like at and the have been merged into single tokens while the rare or unseen combinations were represented as raw bytes.

Questions and Answers

This section covers the questions I has as I was learning this concept and some answers that I found when I researched.

1. Why is the substitution of frequent pairs necessary? Why not just use the text as is?

• Using text as is means treating each character or byte as a separate token. Character level tokenizers have a smaller vocabulary but produce longer sequence and a single word like tokenization becomes 12 separate tokens. BPE gives a larger vocabulary but much shorter sequences. Read more from this Reddit post

2. Why use UTF-8 instead of UTF-16 or UTF-32?

• UTF-8 is the most efficient encoding for text used to train LLMs. It encodes ASCII characters as a single byte keeping the vocabulary small and sequences stay short. UTF-16 and UTF-32, even simple characters like a are encoded to 2–4 bytes, unnecessarily increasing the sequence length.

References

1. Wikipedia
2. Philip Gage, A New Algorithm for Data Compression
3. Andrej Karpathy, Let’s build a GPT tokenizer
4. Geeksforgeeks, Byte-Pair Encoding (BPE) in NLP
5. Sebastian Raschka, Implementing A Byte Pair Encoding (BPE) Tokenizer From Scratch