Byte Pair Encoding from Scratch

Building a BPE tokenizer step by step: the algorithm that decides how language models see text

NLP
Author

Imad Dabbura

Published

April 10, 2024

Modified

January 13, 2025

evergreen

Why Tokenization Matters

When you type “unhappiness” into ChatGPT, the model doesn’t see the word “unhappiness.” It sees something like ["un", "happ", "iness"], three tokens that were chosen by an algorithm months before the model was even trained. That algorithm decided, based on statistics from a massive training corpus, that these three pieces are the right granularity. The tokenizer is its own model with its own training run, fit once on its own corpus to compress text into a fixed vocabulary, then frozen before the language model sees a single example. Not individual characters (too many tokens, too little meaning per token). Not whole words (too many unique words, no way to handle words never seen in training). Subwords: the sweet spot.

This isn’t a minor preprocessing detail. Tokenization defines what the model can see: the model perceives the world only through tokens, and a surprising share of language-model failures (trouble with arithmetic, spelling, and rare languages) are really tokenizer failures. Consider three strategies on the same sentence:

Strategy “The cat sat unhappily” becomes Tokens Vocab Size
Character-level ["T","h","e"," ","c","a","t"," ","s","a","t"," ","u","n","h","a","p","p","i","l","y"] 21 ~256
Word-level ["The", "cat", "sat", "unhappily"] 4 100,000+
Subword (BPE) ["The", " cat", " sat", " un", "happ", "ily"] 6 ~50,000

With characters, a fixed context window of 2048 tokens covers ~400 words. With subwords, the same window covers ~1500 words, nearly 4× more context for the model to reason over. Word-level is compact but brittle: “unhappily” might never appear in training data, making it an <UNK> token the model is completely blind to. But “un”, “happ”, and “ily” almost certainly do appear, and the model can compose meaning from pieces it knows.

The algorithm that learns these splits is Byte Pair Encoding (BPE), originally a data compression technique (Gage, 1994), adapted for NLP by Sennrich et al. (2016), and now used in GPT-2, GPT-3/4, LLaMA, and most modern language models. In this post, we’ll understand how it works, implement it from scratch, and see how GPT-2 refined the basic algorithm for production. For the broader picture, I compare character, word, and subword tokenization in Breaking Text Apart (The Smart Way).

How BPE Works

The core insight is simple: if two symbols frequently appear next to each other, they probably belong together. Merge them into a single token, then look for the next most frequent pair, and repeat. It’s exactly how you’d compress a text file: find repeated patterns and replace them with shorter symbols. Frequent patterns get absorbed into single tokens; rare patterns stay as smaller pieces.

Think of it like learning abbreviations. If you keep writing “machine learning” in your notes, you’d eventually start writing “ML.” Then if “ML model” keeps appearing, maybe you’d abbreviate that too. BPE does the same thing, but systematically and bottom-up, starting from the smallest units (bytes) and building up to subwords.

Seeing It in Action

Before formalizing the algorithm, let’s watch it work on a real example. Consider a tiny training corpus containing the words "low lower lowest":

Step Token Sequence Most Frequent Pair New Token
Start l o w _ l o w e r _ l o w e s t - -
Merge 1 lo w _ lo w e r _ lo w e s t (l, o) → lo 3×
Merge 2 low _ low e r _ low e s t (lo, w) → low 3×
Merge 3 low _ lowe r _ lowe s t (low, e) → lowe 2×

BPE discovered that l and o always appear together, then that lo and w always appear together, building up low as a token, effectively learning the word stem. Then it found lowe as a shared prefix of “lower” and “lowest.” Without any linguistic rules, purely from frequency, BPE learned morphological structure.

Notice what happened in merge 2: the algorithm merged lo with w, where lo itself was created in merge 1. BPE builds tokens hierarchically: later merges compose earlier ones. We can visualize this as a tree:

graph BT
    l["l (byte)"] --> lo["lo (merge 1)"]
    o["o (byte)"] --> lo
    lo --> low["low (merge 2)"]
    w["w (byte)"] --> low
    low --> lowe["lowe (merge 3)"]
    e["e (byte)"] --> lowe

BPE merges build tokens bottom-up. Each merge composes two existing tokens into a new one, forming a hierarchy from bytes to subwords.

Each level in the tree depends on the levels below it. This is why merge order matters during encoding: you can’t build low until lo exists.

The Algorithm

With the intuition in place, here’s the formal procedure:

  1. Initialize: Start with a base vocabulary of all 256 byte values (0–255). Every string can be represented as bytes, so this guarantees full coverage: no <UNK> tokens, ever.

  2. Count pairs: Scan the corpus and count every adjacent pair of tokens.

  3. Merge the most frequent pair: Create a new token for it and replace all occurrences in the corpus.

  4. Repeat steps 2–3 until you’ve done vocab_size - 256 merges.

The output is a merge table: an ordered list of pair → token mappings. This table is the tokenizer.

Training vs. Encoding: A Subtle Difference

There’s an important asymmetry between how BPE learns merges (training) and how it applies them to new text (encoding).

During training, we always merge the globally most frequent pair; that’s how we decide which merges to learn. But during encoding, we apply merges in the order they were learned, not by their frequency in the new text.

WarningEncoding Replays Merges: It Doesn’t Re-learn Them

A common misconception is that encoding finds the most frequent pair in the new text and merges it. It doesn’t. Encoding applies the training-time merges in their original order. The token low only exists after lo has been created (merge 1). If we tried to merge (lo, w) before creating lo, we’d never find the pair. In the implementation, this shows up as min(stats, key=lambda p: self.merges.get(p, float("inf"))): picking the pair with the lowest merge index, not the highest frequency.

Why Bytes, Not Characters?

Starting from bytes (0–255) rather than Unicode code points is a practical decision. Unicode has over 150,000 code points, an impractically large base vocabulary. By working at the byte level, we start with just 256 symbols and can represent any string in any language or script, since UTF-8 encodes every Unicode code point as one to four of these bytes. BPE merges then learn to compose bytes into characters, characters into subwords, and subwords into common words, all driven by frequency in the training data.

NoteThe Multilingual Tax

This is a property of the tokenizer’s training data, not of the language. English dominates most tokenizer corpora, so English merges into long, dense tokens while an underrepresented script like Korean stays fragmented into many short ones. The same sentence then costs several times more tokens in Korean than in English. Two costs follow. The model burns more of its fixed context window on the same meaning, so within one window an English token effectively attends to more real content than a Korean one; and it runs more forward passes for that sentence, so inference is more expensive. It is a well-documented source of multilingual inefficiency (Petrov et al., 2023), and it traces back entirely to which languages were frequent when the tokenizer was trained.

Vocabulary Size: A Key Hyperparameter

How many merges should we do? This is the vocabulary size, and it’s a meaningful trade-off:

Vocab Size Tokens per Text Embedding Table Character
Small (~1k) Many - close to character-level Tiny Better generalization on rare words, but sequences are long and training is slow
Medium (~32k–50k) Moderate - good compression Manageable The sweet spot for most models (GPT-2: 50k, LLaMA: 32k)
Large (~100k+) Few - common phrases become single tokens Very large Risk of overfitting to training distribution; rare tokens get poorly trained embeddings

Larger vocabularies mean each token carries more information, so sequences are shorter and the model sees more context per forward pass. But each token also needs an embedding vector, so the embedding table grows linearly, and so does the output head: the final layer scores every candidate token with a dot product, so a wider vocabulary makes the last layer and its softmax more expensive at every step. And tokens that appear rarely in training will have poorly learned embeddings: they’ve simply not been seen enough times.

There is a subtler ceiling than cost. The Transformer does a fixed amount of work per token, so compressing more text into each token eventually packs in more than a single forward pass can unpack. A token that stands for a whole common phrase leaves the model no intermediate steps in which to reason about its parts. The sweet spot is therefore not as much compression as the hardware allows: it is the point where tokens are dense enough to give long-range context but still coarse enough that one forward pass can digest each one.

Most modern models settle in the 32k–100k range. GPT-2 uses ~50k tokens. LLaMA uses 32k. GPT-4 reportedly uses ~100k. The right size depends on the training data, the target languages, and the compute budget.

ImportantBPE Is Adaptive Computation

There is a deeper way to read what merging buys you. The Transformer spends the same compute on every token: one slot in the residual stream, one forward pass. BPE decides how much text each of those fixed-cost slots has to cover. Common words are merged into a single token and get one forward pass; rare words survive as several tokens and get several. Because a word’s rarity tracks its information content, this is the right allocation almost by accident: the tokenizer routes more of the model’s compute toward the surprising parts of the input and less toward the boilerplate. Merging also hands the model priors for free, since a word arriving as un + happ + iness means morphology is baked into the input rather than relearned from scratch.

Implementation

Let’s turn the algorithm into code. The BPETokenizer class below has four core methods, each mapping directly to a step we’ve discussed:

  • train (the learning loop): encode the corpus to bytes, then greedily merge the most frequent pair vocab_size - 256 times. Each merge is recorded in self.merges as a (pair) → index mapping. This ordered dictionary is the tokenizer.
  • encode (the encoding step): convert new text to bytes, then apply merges in learned order (earliest first, using the min trick we discussed). This is where training-order matters: we pick the pair with the smallest merge index, not the most frequent.
  • decode (the inverse): look up each token ID in the vocabulary to get its byte sequence, concatenate, and decode back to a string. Not every byte sequence is valid UTF-8 (a merge can produce bytes that don’t form a legal character), so decoding passes errors="replace", substituting � rather than crashing.
  • _get_stats / _merge: Helpers that count adjacent pairs and replace a specific pair with its merged token throughout a sequence.

One implementation detail: _build_vocab relies on Python 3.7+ dictionary insertion order. Since merges are inserted chronologically, iterating self.merges replays them in order: each merged token is the byte-concatenation of its two parents, which must already exist in the vocabulary.

Code 
from typing import Iterable
import requests
class BPETokenizer:
    """Byte-pair encoder."""

    def __init__(self, vocab_sz: int):
        """
        Args:
            vocab_sz (int): Vocabulary size.
        """
        self.vocab_sz = vocab_sz
        self.vocab = {}
        self.merges = {}

    def train(self, text: Iterable[str]):
        """Train Byte-pair encoder."""
        ids = list(text.encode("utf-8"))
        for idx in range(256, self.vocab_sz):
            stats = self._get_stats(ids)
            pair = max(stats, key=stats.get)
            self.merges[pair] = idx
            ids = self._merge(ids, pair, idx)
        self.vocab = self._build_vocab(ids)

    def encode(self, text):
        """Encode string to bytes using vocabulary built during training."""
        ids = list(text.encode("utf-8"))

        ## If text is empty or has one character -> it is already encoded from previous step
        while len(ids) >= 2:
            ## stats is used only for getting pairs next to each other
            stats = self._get_stats(ids)
            ## Because we built vocab (and merges) bottom-up, we need to encode
            ## idx from smallest index because some later pairs depend on pairs
            ## occured before. In other words, more frequent pairs would have
            ## lower indices that less frequent pairs -> To get the fist pairs
            ## we need to get the lowest indices first before moving on.
            ## If a pair doesn't exist, it wouldn't participate in the list
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))
            if pair not in self.merges:
                break  ## No more pairs to merge
            idx = self.merges[pair]
            ids = self._merge(ids, pair, idx)
        return ids

    def decode(self, tokens: Iterable[int]):
        """Decode tokens into string using the vocabulary built during training."""
        tokens = b"".join(self.vocab[idx] for idx in tokens)
        ## It is important to replace tokens that were not seen during training
        ## with `?`; otherwise, it would fail
        return tokens.decode("utf-8", errors="replace")

    def _get_stats(self, ids: Iterable[int]):
        """Get pair counts."""
        counts = {}
        for pair in zip(ids, ids[1:]):
            counts[pair] = counts.get(pair, 0) + 1
        return counts

    def _merge(self, ids: Iterable[int], pair: Iterable[int], idx: int):
        """Merge pairs that match `pair` with new index `idx`."""
        newids = []
        i = 0
        while i < len(ids):
            if i < len(ids) - 1 and pair[0] == ids[i] and pair[1] == ids[i + 1]:
                newids.append(idx)
                i += 2
            else:
                newids.append(ids[i])
                i += 1
        return newids

    def _build_vocab(self, ids: Iterable[int]):
        """Build vocabulary from 0-255 bytes and merges."""
        vocab = {idx: bytes([idx]) for idx in range(256)}
        ## Here we assume the items returned would be in the same order they were inserted.
        ## This is Okay Python 3.7+
        for (p0, p1), idx in self.merges.items():
            ## This would be a concatenation of the bytes
            vocab[idx] = vocab[p0] + vocab[p1]
        return vocab
text = requests.get("https://docs.python.org/3/library/stdtypes.html#bytes.decode").text
tokenizer = BPETokenizer(300)
tokenizer.train(text)
tokenizer.decode(tokenizer.encode(text)) == text
True
print(f"Compression rate: {len(list(text.encode('utf-8'))) / len(tokenizer.encode(text)):.1f}x")
Compression rate: 1.9x
BPETokenizer(10).train("imad")

From Vanilla BPE to GPT-2’s Tokenizer

The implementation above is vanilla byte-level BPE: it works, but it has a practical problem. Because merges are purely frequency-driven, the algorithm doesn’t respect word boundaries. The word “play” might appear in the corpus as “play.”, “play!”, “play,”, and “play”, and BPE will learn separate tokens for each variant, wasting vocabulary slots on what is essentially the same word with different punctuation.

GPT-2 (Radford et al., 2019) introduced a key refinement: pre-tokenization with a regex pattern that splits text into chunks before BPE runs. The regex prevents merges from crossing certain boundaries: letters can’t merge with digits, punctuation stays separate from words, and spaces attach to the beginning of words rather than the end.

The GPT-2 regex pattern:

'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+

This ensures that:

  • Contractions are split cleanly: “don’t” → ["don", "'t"]
  • Spaces attach to the next word: ” hello” stays together, preserving word boundaries
  • Punctuation stays isolated: “play!” → ["play", "!"] instead of learning “play!” as one token
  • Digits don’t merge with letters: “h3llo” → ["h", "3", "llo"]

BPE then runs within each chunk independently. The result: a much cleaner vocabulary where tokens correspond to linguistically meaningful units rather than artifacts of adjacent punctuation.

TipTry It Yourself

Use Tiktokenizer to see how GPT-2 and GPT-4 tokenize arbitrary text. Try pasting the same sentence in English and another language, and you’ll immediately see the multilingual tokenization tax in action: the non-English version will use significantly more tokens for the same meaning.

This pre-tokenization pattern has been refined in later models. GPT-4 uses a more sophisticated pattern that handles apostrophes, numbers, and whitespace more carefully, and also limits the length of digit sequences to avoid learning overly specific number tokens. The core idea remains the same: constrain where merges can happen to produce a more useful vocabulary. I build a working GPT-2 on top of a tokenizer like this in Building GPT-2 from Scratch.

References & Resources

Back to top