Byte-Pair Encoding from Scratch

How do you turn a sentence into numbers?

A neural network operates on tensors of floating-point values. You can't feed it the string "The cat sat on the mat" directly. At some point there has to be a mapping from text to integers, and from integers to vectors. We covered the raw byte representation of text in the previous post. Now we need the next piece: how to chop that text into tokens, and build the vocabulary that maps each token to an ID.

A word-level vocabulary gives each word an ID, but it has to account for inflections, compounds, names, and new words. A word absent from the vocabulary becomes an unknown token unless there is a fallback.

A character vocabulary reuses smaller units, at the cost of longer sequences. It still needs coverage for characters absent from training. A complete byte alphabet avoids that coverage problem, and BPE can then shorten the byte sequences by learning common combinations.

Subword tokenization gives common strings their own entries while representing rarer strings with smaller pieces. Byte-Pair Encoding learns those entries by repeatedly merging frequent pairs.

BPE as compression

The algorithm actually comes from data compression, not NLP. Philip Gage published it in the C Users Journal in 1994. The idea is short:

1. Start with a sequence of bytes.
2. Find the most frequent adjacent pair of bytes.
3. Replace every occurrence of that pair with a new byte (a symbol that didn't exist before).
4. Repeat until you've done enough replacements or no pair appears more than once.

Each step reduces the total length of the sequence by replacing two symbols with one. The "merge table" you accumulate along the way is the compression dictionary. To decompress, you just apply the merges in reverse.

Gage's original application was compressing files. But in 2016, Sennrich, Haddow, and Birch realized that the same algorithm could solve the vocabulary problem for neural machine translation. Instead of compressing bytes, you compress a corpus of words. Instead of a compression dictionary, you get a tokenizer.

From compression to tokenization

Sennrich et al. used the learned merge table as a subword vocabulary:

Training phase: You take your training corpus, split every word into individual characters (plus a special end-of-word marker), and then run the BPE algorithm. Count all adjacent pairs across the entire corpus, merge the most frequent one, update the corpus, repeat. After $k$ merges you have a vocabulary of (base characters) + $k$ merged tokens.

Encoding phase: Given a new word at inference time, you start with its character sequence and apply the learned merges greedily, in the order they were learned during training. Merge 1 first, then merge 2, and so on. When no more applicable merges remain, whatever tokens you're left with are the segmentation.

Step through BPE on this small corpus to see which pair wins each round and how the vocabulary grows.

Notice how the first merges tend to grab common character pairs like (e, r) or (l, o). These aren't linguistically meaningful morphemes. Their selection depends on frequency. The token er appears because newer and wider both end in -er, and those words are common enough that the pair (e, r) rises to the top. The algorithm also merges (lo, w) into low pretty quickly, because the word "low" appears five times. By the end, words such as low and newer have merged with their end markers. Other words can remain segmented, depending on where we stop.

Building a BPE trainer

The trainer needs to:

1. Take a corpus and split it into character sequences (with word frequencies for efficiency).
2. Count pair frequencies across the whole corpus, weighted by word frequency.
3. Merge the top pair everywhere.
4. Repeat to a target vocabulary size.

The core data structure is a dictionary that maps each word (as a tuple of tokens) to its frequency in the corpus. We never re-scan the raw text after the initial pass.

import re
from collections import Counter, defaultdict
 
def get_word_freqs(text):
    """Split text into words and count frequencies.
    Each word is stored as a tuple of characters + end-of-word marker."""
    words = text.strip().split()
    freqs = Counter(words)
    # Convert each word to a character tuple with </w> marker
    vocab = {}
    for word, count in freqs.items():
        chars = tuple(list(word) + ["</w>"])
        vocab[chars] = count
    return vocab
 
def count_pairs(vocab):
    """Count frequency of all adjacent pairs across the vocabulary."""
    pairs = defaultdict(int)
    for word, freq in vocab.items():
        for i in range(len(word) - 1):
            pairs[(word[i], word[i + 1])] += freq
    return pairs
 
def merge_pair(pair, vocab):
    """Merge all occurrences of a pair in the vocabulary."""
    new_vocab = {}
    bigram = pair
    for word, freq in vocab.items():
        new_word = []
        i = 0
        while i < len(word):
            # Look for the bigram at position i
            if i < len(word) - 1 and word[i] == bigram[0] and word[i + 1] == bigram[1]:
                new_word.append(bigram[0] + bigram[1])
                i += 2
            else:
                new_word.append(word[i])
                i += 1
        new_vocab[tuple(new_word)] = freq
    return new_vocab
 
def train_bpe(text, num_merges):
    """Train BPE on a text corpus for a given number of merges.
    Returns the merge list and final vocabulary."""
    vocab = get_word_freqs(text)
 
    merges = []
    for i in range(num_merges):
        pairs = count_pairs(vocab)
        if not pairs:
            break
        # Find most frequent pair
        best_pair = max(pairs, key=pairs.get)
        best_freq = pairs[best_pair]
        if best_freq < 2:
            break  # No pair appears more than once
 
        vocab = merge_pair(best_pair, vocab)
        merges.append(best_pair)
        print(f"Merge {i+1}: {best_pair} -> "
              f"{''.join(best_pair)} (freq: {best_freq})")
 
    return merges, vocab

Train on a small corpus with different word frequencies to trace the selected merges:

corpus = ("low low low low low lowest lowest "
          "newer newer newer newer newer newer "
          "wider wider wider new new")
 
merges, final_vocab = train_bpe(corpus, num_merges=10)
 
# Output:
# Merge 1: ('e', 'r') -> er (freq: 9)
# Merge 2: ('er', '</w>') -> er</w> (freq: 9)
# Merge 3: ('n', 'e') -> ne (freq: 8)
# Merge 4: ('ne', 'w') -> new (freq: 8)
# Merge 5: ('l', 'o') -> lo (freq: 7)
# Merge 6: ('lo', 'w') -> low (freq: 7)
# Merge 7: ('new', 'er</w>') -> newer</w> (freq: 6)
# Merge 8: ('low', '</w>') -> low</w> (freq: 5)
# Merge 9: ('w', 'i') -> wi (freq: 3)
# Merge 10: ('wi', 'd') -> wid (freq: 3)

Merges 1-2 collapse e + r + </w> into the token er</w>, because both newer and wider end in -er. That's 9 occurrences (6 from newer, 3 from wider). Merges 3-4 build new from characters. Merges 5-6 build low. Then merge 7 collapses newer</w> into a single token because the full word newer appears 6 times. Merge 8 fuses low</w> (the standalone word "low" shows up 5 times). Merges 9-10 start assembling wider from characters but run out of budget before the full word collapses.

After 10 merges, the word newer is a single token and so is low. The word lowest is segmented as low + e + s + t + </w> because est wasn't frequent enough to get its own merge yet. And wider is still two tokens because the budget stopped before the final merges.

Building the encoder

Training gives you a merge list. Now you need an encoder that applies those merges to new text. The encoder takes a word, splits it into characters, and applies each merge rule in order. This is the greedy left-to-right application within each ranked merge. Whitespace splitting also discards the original spacing, so this toy does not provide a lossless text round-trip. The code returns token strings, not IDs: it does not yet reject unseen characters such as the g in lowering. A production tokenizer needs an alphabet and an explicit fallback policy.

def encode_word(word, merges):
    """Encode a single word using learned BPE merges.
    Apply merges greedily in the order they were learned."""
    tokens = list(word) + ["</w>"]
 
    for left, right in merges:
        new_tokens = []
        i = 0
        while i < len(tokens):
            if (i < len(tokens) - 1
                    and tokens[i] == left
                    and tokens[i + 1] == right):
                new_tokens.append(left + right)
                i += 2
            else:
                new_tokens.append(tokens[i])
                i += 1
        tokens = new_tokens
 
    return tokens
 
def encode(text, merges):
    """Encode a full text string into BPE tokens."""
    words = text.strip().split()
    all_tokens = []
    for word in words:
        all_tokens.extend(encode_word(word, merges))
    return all_tokens
 
# Using the merges from our training run:
print(encode("low", merges))
# ['low</w>']
 
print(encode("lower", merges))
# ['low', 'er</w>']
 
print(encode("newest", merges))
# ['new', 'e', 's', 't', '</w>']
 
print(encode("lowering", merges))
# ['low', 'er', 'i', 'n', 'g', '</w>']

The examples below trace the intermediate token list after each merge rule.

Although lower was absent from training, it becomes low + er</w> because both pieces were learned.

The word newest partially collapses. The new token is there, but est</w> never became a merge in our 10-step run, so the tail stays as characters. More training does not guarantee that est becomes a token: earlier merges may already have absorbed its characters into other pieces.

And watch lowering. The (e, r) merge fires on a position where the </w> marker is not adjacent, because the r is followed by an i. The encoder doesn't look for the longest matching token. It replays merges in training order, and each rule sees whatever pairs exist at the moment it runs.

That ordering is what makes the segmentation stable and deterministic. Rerun the same word against the same merge list and you get the same tokens every time. It also means two tokenizers with the same final vocabulary can produce different segmentations if their merge orders differ. Reproducing the encoding requires the merge ranks as well as the vocabulary.

Byte-level BPE: the GPT-2 variant

Sennrich's original BPE starts with Unicode characters. But which characters? Unicode has many thousands of assigned characters. Putting them all in the base vocabulary is wasteful since most never appear. Filtering to only characters seen in training puts us back at the UNK problem for unseen scripts.

GPT-2 starts from UTF-8 bytes instead. Its base vocabulary contains 256 entries, covering every byte value, and BPE merges build longer pieces from them.

Every valid UTF-8 string is representable with that byte alphabet, without an UNK token.

If you run BPE on raw bytes without boundary restrictions, you'll learn merges that span across word boundaries. The bytes for the space character will get merged with adjacent word bytes, and you'll end up with tokens like " the" (space-t-h-e) absorbing into multi-word chunks. GPT-2 prevents this with a pre-tokenization step: a regex pattern that splits the input into chunks before BPE runs.

The GPT-2 regex looks something like this:

import regex  # the 'regex' module, not 're'
 
# GPT-2's pre-tokenization pattern (simplified)
GPT2_PATTERN = regex.compile(
    r"""'s|'t|'re|'ve|'m|'ll|'d"""
    r"""| ?\p{L}+"""       # optional space + letters
    r"""| ?\p{N}+"""       # optional space + numbers
    r"""| ?[^\s\p{L}\p{N}]+"""  # optional space + punctuation
    r"""|\s+(?!\S)"""      # trailing whitespace
    r"""|\s+"""            # other whitespace
)
 
text = "Hello, I've been learning BPE!"
chunks = GPT2_PATTERN.findall(text)
# ['Hello', ',', ' I', "'ve", ' been', ' learning',
#  ' BPE', '!']

Each chunk becomes an independent unit for BPE. Merges happen within chunks but never across chunk boundaries. So you'll get tokens like " learning" (space attached to the word) but never tokens that span two words. The leading space is part of the token, which is why you'll sometimes see tokenizer outputs like [" Hello", " world"] with those leading spaces.

Changing the pre-tokenization regex can therefore produce a different vocabulary from the same corpus.

Vocab size is a cut on the merge list

Within one BPE training run, vocabulary size determines how many learned merges are retained, in addition to the base alphabet and special tokens. Later merges add pieces selected after the earlier ones. Their final token frequencies depend on which later merges absorb them; merge rank is not a precise frequency ranking of the final vocabulary.

Extending a fixed merge list can shorten sequences, but a larger vocabulary also costs embedding and output parameters. The benefit on English, code, or another language depends on the corpus and pre-tokenization rules.

Misconceptions

"BPE finds linguistically meaningful morphemes." It doesn't. It finds frequent byte-pair patterns. Sometimes those patterns line up with morphemes like un- or -ing, because morphemes tend to be frequent substrings. BPE will happily merge arbitrary character sequences if they're frequent enough. The token " th" (space + t + h) exists in GPT-2's vocabulary not because "th" is a meaningful unit, but because that byte sequence is frequent in its training corpus.

"The merge order doesn't matter at inference." It does. The encoder applies merges in training order, and this creates an implicit priority. If merge 47 combines (a, b) and merge 203 combines (ab, c), the encoder always tries (a, b) first. Scramble the merge order and you get different segmentations. Two tokenizers with the same final vocabulary but different merge orderings are functionally different tokenizers.

"Larger vocabulary is always better." More entries can shorten sequences but increase the parameter and output-projection costs. Measure the tradeoff on representative text. When comparing published sizes, distinguish mergeable tokens, special tokens, and allocated embedding rows; they need not have the same count.

What's next

The next post compares WordPiece, Unigram, and SentencePiece: two other subword methods and the framework that implements BPE and Unigram.

Additional reading (and watching)

• Gage, P. (1994). A New Algorithm for Data Compression. C Users Journal, 12(2).
• Sennrich, R., Haddow, B., & Birch, A. (2016). Neural Machine Translation of Rare Words with Subword Units. ACL 2016.
• Radford, A., et al. (2019). Language Models are Unsupervised Multitask Learners. OpenAI.
• OpenAI. tiktoken — fast BPE tokenizer implementation in Rust.
• Karpathy, A. (2024). minbpe — minimal BPE implementation for educational purposes.
• Zouhar, V. & Meister, C. (2023). A Formal Perspective on Byte-Pair Encoding. ACL Findings 2023. Formalizes BPE as a greedy approximation to a compression objective and shows why the merge list (not just the vocabulary) is the tokenizer.