Chapter 2 · Section 2.2 · 75 min

Byte pair encoding from scratch

In 1994 a programmer named Philip Gage published a tiny compression algorithm in The C Users Journal. Find the pair of adjacent bytes that occurs most often in the file, replace every occurrence with a single byte value the file never uses, write down the replacement in a table, and repeat. He called it byte pair encoding. It was a modest compressor, quickly outclassed by others, and it would have been forgotten if Sennrich, Haddow and Birch had not noticed in 2016 that its replacement table is exactly what a neural network needs as a vocabulary. Frequent pairs become units, frequent units pair up into bigger units, and after a few thousand rounds the table holds common words, common word endings, and common prefixes, all learned from data with no linguistics.

Today a direct descendant of Gage's loop builds the vocabulary of GPT-2, GPT-4, Llama 3, and most other large language models. In this section you'll run it by hand, prove what its encoder does, implement both halves the way an interviewer expects, and learn how real implementations make it fast.

BPE by hand

Take a toy corpus. A pre-tokenizer (the subject of §2.3) has already split the text into words, and we have counted how often each word occurs.

word	count	as characters
tea	6	t e a
teas	2	t e a s
eat	5	e a t
eats	3	e a t s
seat	4	s e a t
set	3	s e t

The base vocabulary is the four characters $\{a, e, s, t\}$ , and the corpus is written with $6\cdot3 + 2\cdot4 + 5\cdot3 + 3\cdot4 + 4\cdot4 + 3\cdot3 = 78$ tokens. Now repeat one step.

Step 1. Count every pair of adjacent symbols, weighting each word by its count. The pair e a occurs once in each of tea, teas, eat, eats, and seat, so its count is $6 + 2 + 5 + 3 + 4 = 20$ . The runner-up is a t with $5 + 3 + 4 = 12$ . We merge e a into a new symbol ea, record "merge 1 is (e, a)", and rewrite the corpus. Every word except set shrinks by one token, so the corpus now takes 58 tokens.

Step 2. Recount. Now ea t occurs in eat, eats, and seat for $5 + 3 + 4 = 12$ , and t ea occurs in tea and teas for $6 + 2 = 8$ . Merge ea t into eat. The corpus takes 46 tokens.

Step 3. The best pair is t ea with count 8. Merge it into tea. Now tea is a single token, and the corpus takes 38 tokens.

Step 4. The candidates are s eat (4, from seat), and e t, eat s, and s e, each with 3. Merge s eat into seat. The corpus takes 34 tokens.

Step 5. Now there is a three-way tie at count 3 between e t (from set), eat s (from eats), and s e (from set). Something has to decide. This is where implementations differ, and it matters more than it looks, because a different choice here changes every later merge and therefore the whole vocabulary. We'll use a simple deterministic rule. Among pairs with the highest count, pick the smallest pair in ordinary string order, comparing the left symbols first and then the right ones. Since "e" < "eat" < "s", the winner is e t.

Before applying that fifth merge, take stock. After four merges our vocabulary has $4 + 4 = 8$ entries, $\{a, e, s, t, ea, eat, tea, seat\}$ , and the corpus shrank from 78 tokens to 34. The merge table, the ordered list of the merges, is the trained tokenizer. The vocabulary is just the base symbols plus one new symbol per merge, so with $m$ merges over a base of $b$ symbols,

V = b + m .

In plain words, the vocabulary size is a knob you set by choosing how many merges to run. GPT-2 runs 50,000 merges over a base of 256 bytes and adds one special token, which is where its peculiar size of 50,257 comes from.

Here is the same procedure in code. Read it next to the steps above.

Python · cell 1

The printout matches the hand computation, and it shows step 6 resolving another tie (eat s beats s et because "eat" < "s").

Warm-up

Count weighted pairs

Implement pair_counts(words) where words maps a tuple of symbols to its count, for example {("t", "e", "a"): 6}. Return a dict mapping each adjacent pair (a, b) to its total count, weighted by the word counts. Count every adjacent position, including overlapping ones, as in the callout above.

def pair_counts(words):
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

Core

Merge a pair, left to right

Implement merge_pair(symbols, pair) that returns a new tuple in which every occurrence of pair has been replaced by the concatenated symbol, scanning left to right without overlaps. So merge_pair(("a", "a", "a"), ("a", "a")) is ("aa", "a"), and merge_pair(("t", "e", "a", "t", "e", "a"), ("t", "e")) is ("te", "a", "te", "a").

def merge_pair(symbols, pair):
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

Watch it learn

Type any text into the box below. The widget pre-tokenizes it into words with their leading spaces (shown as ␣), then runs exactly the loop above on your text. Step through the merges one at a time and watch three things, the segmentation of the text, the merge table, and the candidates competing for the next merge.

Notice the order. On the default sentence the first merges are a t (count 15) and h e, then the and ␣the, and after six merges ␣cat is a single token. Paste in a few paragraphs of ordinary English and you'll see whole frequent words (␣the, ␣and) appear within a few dozen merges, followed by common endings like ing and ed. Repeated words become single tokens quickly, which is the compression doing its job. With enough merges every word of the training text becomes one token. That is overfitting in the tokenizer's sense, and we'll measure it shortly.

Encoding new text by merge rank

Training gave us a merge table. Now a new word arrives, one the tokenizer may never have seen. How do we split it?

The rule is to replay the merges in the order they were learned. Each merge has a rank, its position in the table (merge 1 has rank 0, merge 2 rank 1, and so on). Start from characters, and repeatedly apply the lowest-ranked merge that is possible anywhere in the current sequence, until no merge applies.

Let's encode "seats" with our table of six merges, whose ranks are (e, a) 0, (ea, t) 1, (t, ea) 2, (s, eat) 3, (e, t) 4, and (eat, s) 5.

Start with s e a t s. The possible merges are only (e, a), at rank 0. Apply it to get s ea t s.
The adjacent pairs are (s, ea), (ea, t), and (t, s). Only (ea, t) is in the table, at rank 1. Apply it to get s eat s.
The pairs are (s, eat) at rank 3 and (eat, s) at rank 5. The lower rank wins, giving seat s.
The only pair is (seat, s), which is not in the table. Stop. The encoding is seat + s.

Notice that step 3 is a genuine competition. A left-to-right greedy that merged the first possible pair would also pick (s, eat) here, but try "steat". After s t ea t the pairs (t, ea) at rank 2 and (ea, t) at rank 1 compete. Rank order applies (ea, t) first and gives s t eat. Merging the leftmost possible pair first would give s tea t, which training would never have produced. Getting this wrong is the most common bug in hand-written BPE encoders.

Why replay in rank order? Because it reproduces exactly what training did to every word of the training corpus, so a word seen in training is tokenized the same way at inference time. And there is a cleaner reason the "lowest rank present" loop is right.

∂ Why the lowest-rank loop equals replaying the merge table in order

Write the merge table as $\mu_0, \mu_1, \dots, \mu_{m-1}$ , where $\mu_r = (a_r, b_r) \to a_r b_r$ . Replaying in order means applying $\mu_0$ everywhere, then $\mu_1$ everywhere, and so on. The encoder instead repeatedly applies the lowest-ranked merge present. We show both produce the same sequence of operations.

The key fact is about when symbols are born. The symbol $a_r b_r$ is created by merge $r$ . Any merge that uses it as an input must have been learned after it existed, so it has a rank larger than $r$ . (This assumes each merge creates a symbol that no earlier merge created, which holds for every table where $V = b + m$ , since otherwise the vocabulary would be smaller than $b + m$ .)

The proof is an induction on the steps of the encoder. Suppose that just before some step, no merge of rank below $r$ is present anywhere in the sequence, and the lowest-ranked merge present is merge $r$ , so the encoder applies it once, at its leftmost occurrence. Two things change. The pair it consumed is gone, and the new symbol $a_r b_r$ forms new adjacent pairs with its left and right neighbors. By the key fact every merge that uses $a_r b_r$ has rank above $r$ , and merge $r$ itself cannot reappear, since its inputs $a_r$ and $b_r$ are shorter than the new symbol. So after the step, still no merge of rank below $r$ is present, and the lowest rank present is $r$ again (if other occurrences remain) or larger. The ranks the encoder applies therefore never decrease. Applying merges in non-decreasing rank order, each to all of its occurrences before moving on, is exactly replaying the table in order (merges that are absent are skipped). ∎

One subtlety remains. When the lowest-ranked pair occurs more than once, implementations merge its occurrences left to right, just as training did, so runs like a a a come out the same in both.

Python · cell 2

"tease" ends in an e that never got merged with anything, and "east" uses the pieces it can. A word with a character the tokenizer never saw, say "z", keeps that character as a lone symbol. In a byte-level tokenizer (§2.3) that symbol is a byte, which is always in the vocabulary, so nothing is ever unknown.

This loop is quadratic in the chunk length (each pass scans all pairs and removes one symbol), but pre-tokenized chunks are short, usually under ten symbols, so it is fast in practice. Libraries also cache the encodings of frequent chunks, since the same word recurs constantly.

Decoding is the easy half. Every token id maps to a string (or, in byte-level tokenizers, a byte string), and decoding concatenates them. Nothing is ever lost, because every merge just glues two strings together. The one thing decoding must recover is where the spaces were, since the pre-tokenizer split on them. Sennrich, Haddow and Birch appended an end-of-word symbol </w> to every word before training, so tea</w> (a whole word) and tea (the start of "teas") are different tokens and the decoder puts a space after every </w>. GPT-2 instead attaches each space to the start of the following word, as our cell below does, so the spaces live inside the tokens themselves (§2.3).

Interview

Train BPE with deterministic tie-breaking

This is one of the most common coding questions in LLM interviews. Implement train_bpe(word_counts, num_merges).

word_counts maps each word (a string) to its count. Start every word as a tuple of its characters.
Repeat up to num_merges times. Count adjacent pairs weighted by word counts (every position, overlaps included). Choose the pair with the highest count. Break ties by the smallest pair in Python's tuple order, so ("e", "t") beats ("eat", "s") beats ("s", "e"). Merge it everywhere, left to right.
Stop early if no word has two or more symbols left.
Return the list of merges, each a tuple (left, right), in the order learned.

def train_bpe(word_counts, num_merges):
    """Returns a list of (left, right) merges, in the order learned."""
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

Interview

Encode a word by merge rank

Implement encode_bpe(word, merges), where merges is the ordered list returned by training. Start from the characters of word and repeatedly apply the merge of lowest rank that occurs anywhere in the current sequence (leftmost occurrence first), until no merge applies. Return the list of symbols. Characters never seen in training stay as single symbols, and an empty word gives an empty list.

def encode_bpe(word, merges):
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

A real text, and the overfitting curve

Let's train on something longer than six words. The cell below takes a few paragraphs, pre-tokenizes them with a simple pattern that attaches each word to its leading space (the GPT-2 convention), trains on the first two thirds, and measures the compression $\rho$ (bytes per token, from §2.1) on both the training part and the held-out last third.

Python · cell 3

The first merges are what you'd guess for English (he, ␣t, ␣the, ␣a, nd, er), and both curves rise together at first, because those pieces are useful everywhere. Then they separate. After a couple of hundred merges the tokenizer is spending its vocabulary on whole words and phrases that occur in the training paragraphs but not in the held-out ones. By the last merge every training chunk is a single token, and the training compression is far above the held-out compression. Real tokenizers are trained on gigabytes of text precisely so that their merges are reusable.

Here are some held-out words that never occurred in training, encoded with every merge.

Python · cell 4

The unseen words are built from pieces the tokenizer learned elsewhere (␣storm + i + er), which is the whole point of subwords. " keeping" did occur in training and comes out as one token.

Making it fast

The loop above is fine for a few paragraphs. A real tokenizer is trained on tens of gigabytes. Let's count the work.

Let the deduplicated word table have $S$ symbols in total (the sum of word lengths over distinct words). Each naive iteration recounts every pair, which costs $O(S)$ , and we run $m$ iterations, so naive training costs $O(mS)$ . With $m = 50{,}000$ that is fifty thousand passes over the data. Three ideas make it practical.

Deduplicate first. Pre-tokenize the corpus into chunks and count each distinct chunk once. Our paragraphs have 357 chunks but only 165 distinct ones. A real corpus of billions of words has a few million distinct chunks. This is one of the main reasons for pre-tokenization (§2.3).
Update pair counts incrementally. Merging $(a, b)$ only changes words that contain $(a, b)$ . Keep an index from each pair to the words containing it. For each affected word, subtract the counts of its old pairs, merge, and add the counts of its new pairs. Everything else stays untouched. Since most merges late in training affect only a few words, the total cost drops from $O(mS)$ to roughly $O(S)$ plus the sizes of the affected words.
Find the best pair with a priority queue. Keep the pairs in a max-heap keyed by count, and lazily skip entries whose stored count has gone stale. Picking the best pair then costs $O(\log P)$ for $P$ distinct pairs instead of a scan over all of them.

Production trainers, such as the Rust trainer inside Hugging Face's tokenizers library, use all three, and count in parallel.

There is one more trick worth knowing for byte-level data, where the symbols are small integers. You can count all pairs in a single vectorized operation by encoding each pair $(a, b)$ as the integer $aV + b$ .

Python · cell 5

Look at the winner. Without pre-tokenization, the most frequent pair in raw text is e␣, an e followed by a space, which straddles a word boundary. Byte pair encoding run directly on raw text would happily merge across word boundaries and learn tokens like e␣t. The pre-tokenizer we used earlier forbids that, which is why our first learned merge was he instead. Section 2.3 makes this design choice precise.

Research

Incremental pair-count updates

Implement the core of a fast trainer. The state is

words, a list where words[i] is the current list of symbols of distinct word $i$ ,
counts, a list where counts[i] is how often word $i$ occurs,
stats, a dict from each pair to its weighted count over all words (every position, overlaps included),
where, a dict from each pair to a set of word indices that contain it (it may also contain stale indices of words that no longer do).

Write merge_and_update(words, counts, stats, where, pair), which merges pair in every word that contains it (left to right), updates words, stats, and where in place so that stats again equals the true pair counts (with no zero entries) and every pair's true words are in where, and returns the sorted list of indices of the words that actually changed. You may not loop over all the words. The tests hand you a words list that raises an error if you iterate over it, so you must use where.

def merge_and_update(words, counts, stats, where, pair):
    raise NotImplementedError

Hidden tests, hints, and AI help, from $1.99 a month.

The real way

You'll rarely train a tokenizer by hand. Here is how it looks with Hugging Face's tokenizers library, which implements every trick above in Rust. It runs in seconds on hundreds of megabytes.

The hot loop of training, counting pairs, vectorizes naturally in PyTorch when the symbols are integer ids. Real trainers do this counting in parallel over shards of the corpus and then sum the counts.

🔥 In PyTorchfor a machine with PyTorch

Note that this version runs on raw bytes without pre-tokenization, so it is free to learn merges that cross spaces. That is fine for a demonstration and wrong for a real tokenizer, for the reasons §2.3 explains.

implementation	training cost	encoding	used by
naive loop (this section)	$O(mS)$	quadratic per chunk	teaching, interviews
incremental counts and heap	about $O(S + m \log P)$ plus affected words	quadratic per chunk with a cache	HF `tokenizers`
tiktoken (encoder only)	not a trainer	Rust, per-chunk merge loop, with a fast path for chunks that are whole tokens	GPT-3.5, GPT-4, GPT-4o

⚠️ Common BPE bugs

Encoding with the leftmost mergeable pair instead of the lowest-ranked one. It silently produces segmentations that training never produced.
Non-deterministic tie-breaking. Iterating over a hash set or an unordered dict can change which pair wins a tie between runs or machines, and one different early merge changes the whole vocabulary.
Forgetting to weight by word counts after deduplicating, which turns BPE into "most widespread pair" instead of "most frequent pair".
Training on raw text with no pre-tokenization, which wastes merges on cross-word junk such as e␣t.
Assuming BPE finds the shortest encoding. It does not. It replays a greedy history. Train on the words "ab" (10 times) and "bcd" (6 times) and the merges are (a, b), (b, c), and (bc, d). The new word "abcd" then encodes as ab c d, three tokens, because (a, b) has the lowest rank and uses up the b, even though a + bcd would take two. Section 2.6 meets a worse version, tokens that encoding can never produce at all.

🎯 Interview questions on this section

Walk me through BPE training. What is the output, and what is the vocabulary size?

Start with a base vocabulary (characters or the 256 byte values) and a corpus that has been pre-tokenized into chunks and counted. Repeatedly count all adjacent symbol pairs weighted by chunk counts, pick the most frequent pair (with a deterministic tie-break), add the concatenation as a new symbol, record the merge, and rewrite every chunk. Stop after $m$ merges. The output is the ordered merge table, and the vocabulary is the base symbols plus one symbol per merge, $V = b + m$ , plus any special tokens. GPT-2 is $256 + 50{,}000 + 1 = 50{,}257$ .

How do you encode a new word with a trained BPE, and why that order?

Start from its base symbols and repeatedly apply the merge with the lowest rank (earliest learned) that occurs anywhere in the current sequence, until none applies. This replays the training history, so words from the training corpus get exactly their training segmentation. It is equivalent to applying the merges one by one in table order, because a symbol created by merge $r$ can only take part in merges of rank greater than $r$ , so the ranks applied never decrease. Applying the leftmost mergeable pair instead is a classic bug, as "steat" shows with the hand-example table.

What is the time complexity of naive BPE training, and how do production implementations speed it up?

Naive training rescans all $S$ symbols of the deduplicated word table for each of the $m$ merges, so $O(mS)$ . Production trainers deduplicate words first (via pre-tokenization), maintain pair counts incrementally using an index from each pair to the words containing it (only affected words are updated after each merge), select the best pair with a max-heap with lazy deletion, and count in parallel. Encoding is quadratic in chunk length in the simple implementation, which is fine because chunks are short, and encoders cache frequent chunks.

Why does tie-breaking matter in BPE?

Every merge changes all later pair counts, so a different choice at one tie can change every merge that follows and therefore the whole vocabulary. Without a deterministic rule (for example, smallest pair in a fixed order, or the pair seen first in a defined iteration order), two runs on the same data can produce different tokenizers, which breaks reproducibility and any comparison between experiments.

Does BPE produce the shortest possible tokenization of a string given its vocabulary?

No. It applies a fixed greedy merge history, not a shortest-path search. Training on "ab" (10 times) and "bcd" (6 times) learns the merges (a, b), (b, c), and (bc, d). Encoding the new word "abcd" applies (a, b) first, which consumes the b, and gets stuck at ab c d, three tokens. A shortest-segmentation tokenizer over the same vocabulary would pick a + bcd, two tokens. Choosing among segmentations by an explicit criterion is one motivation for likelihood-based tokenizers like Unigram (§2.4), which pick the most probable segmentation with dynamic programming.

Why do BPE tokenizers overfit, and how would you detect it?

Later merges are spent on long strings that are frequent only in the tokenizer's training data, such as boilerplate, usernames, or repeated documents. Compression on the training text keeps rising while compression on held-out text levels off. Measure bytes per token on held-out text from each target domain and language as a function of the number of merges, and look for merges whose tokens almost never occur in the model's own training data. Those tokens are the glitch tokens of §2.6.

🧭 What to remember

Byte pair encoding repeatedly merges the most frequent adjacent pair. The ordered merge table is the tokenizer, and $V = b + m$ for $b$ base symbols and $m$ merges.
Deterministic tie-breaking and a fixed convention for overlapping pairs are required for reproducible vocabularies.
Encoding applies the lowest-ranked available merge until none remains, which provably replays the table in order. Decoding concatenates token strings.
A tokenizer can overfit its training text. Held-out bytes per token rise quickly at first and then level off.
Fast training deduplicates words, updates pair counts incrementally through a pair-to-word index, and picks the best pair with a heap.
Next, §2.3 moves BPE from characters to bytes and adds the pre-tokenization rules that make GPT-style tokenizers work on any text.

Gage (1994). A New Algorithm for Data Compression. The original byte pair encoding, as a compressor. Two pages.
Sennrich, Haddow & Birch (2016). Neural Machine Translation of Rare Words with Subword Units. BPE as a subword vocabulary, with the end-of-word marker and a ten-line reference implementation.
Karpathy (2024). minbpe. A clean BPE trainer, encoder, and decoder in a few hundred lines, with exercises.
Hugging Face. Byte-Pair Encoding tokenization, LLM course chapter 6. A worked example and a from-scratch implementation that matches the library.
Hugging Face. tokenizers. The Rust implementation behind most open-model tokenizers, worth reading for the incremental training loop.
Zouhar et al. (2023). A Formal Perspective on Byte-Pair Encoding. BPE as greedy approximation of an optimal merge problem, with bounds and faster algorithms.

Zero to Frontier is made for larger screens

Byte pair encoding from scratch

BPE by hand

Count weighted pairs

Merge a pair, left to right

Watch it learn

Encoding new text by merge rank

Train BPE with deterministic tie-breaking

Encode a word by merge rank

A real text, and the overfitting curve

Making it fast

Incremental pair-count updates

The real way

Read more

Watch next