Byte-Pair Encoding (BPE) Step by Step

Byte-Pair Encoding is the most widely used subword algorithm. Originally a 1994 data compression technique by Philip Gage, it was repurposed for NMT by Sennrich, Haddow, and Birch in 2016 and now powers GPT-2, GPT-3, GPT-4, GPT-5 (via tiktoken), Llama 3, RoBERTa, and Qwen.

Training (vocabulary construction)

Initialize the vocabulary with all individual characters (or bytes for byte-level BPE) appearing in the training corpus.
Count every adjacent pair of tokens in the corpus.
Find the most frequent pair, merge it into a new single token, and add it to the vocabulary.
Update the corpus to use the new token; repeat until you reach the desired vocabulary size.

This is bottom-up: you start with maximum granularity (one character per token) and incrementally combine. Every merge is recorded in priority order — at inference time, you apply the merges in the same order to encode new text.

Byte-level BPE (BBPE)

GPT-2 introduced a wrinkle: instead of starting from Unicode characters, start from raw bytes. This guarantees that every conceivable input — emoji, control characters, malformed text — has a representation, with zero OOV risk. Cost: emoji and CJK characters become several tokens instead of one. All GPT models, Llama 3, and most modern Western tokenizers are byte-level BPE.

Code

BPE training — minimal but real·python

from collections import Counter

def get_pairs(words):
    pairs = Counter()
    for word, freq in words.items():
        symbols = word.split()
        for i in range(len(symbols) - 1):
            pairs[(symbols[i], symbols[i+1])] += freq
    return pairs

def merge(pair, words):
    new_words = {}
    bigram = ' '.join(pair)
    replacement = ''.join(pair)
    for word, freq in words.items():
        new_word = word.replace(bigram, replacement)
        new_words[new_word] = freq
    return new_words

# words = {'h e l l o </w>': 5, 'h e l p </w>': 2, ...}
# After merges: 'hel' becomes one token, 'lo</w>' another, etc.

BPE inference — apply learned merges in order·python

def encode_bpe(text, merges):
    # merges: list of (a, b) pairs in priority order
    tokens = list(text)
    for a, b in merges:
        i = 0
        new_tokens = []
        while i < len(tokens):
            if i < len(tokens) - 1 and tokens[i] == a and tokens[i+1] == b:
                new_tokens.append(a + b)
                i += 2
            else:
                new_tokens.append(tokens[i])
                i += 1
        tokens = new_tokens
    return tokens

Byte-Pair Encoding (BPE) Step by Step

Training (vocabulary construction)

Byte-level BPE (BBPE)

Code

External links

Exercise

Progress

Comments 0