Lesson 2.2: Byte-pair encoding from scratch
Write byte-pair encoding in about fifty lines: learn merges from text, encode and decode losslessly, and test it on unseen words and accented text.
By the end of this lesson you will be able to explain byte-pair encoding, work through it by hand on a few words, write a trainer, an encoder and a decoder in plain Python, test that the round trip is lossless, and explain why the order of the merges matters. You will show that the first merge on a toy text joins a and l with a count of 14, that training 150 merges on 18,042 words takes the text from 4.43 to 1.25 tokens per word in under a tenth of a second, that the first version of our tokenizer silently lost double spaces and a round-trip test caught it, and that café ☕ costs nine tokens while the doctor was kicking the small house . costs nine tokens for 41 bytes. You should have read Lesson 2.1. The code is plain Python. This course is education about how language models work, not a guide to any commercial product.
Lesson 2.1 argued that the right token is a subword: whole for common words, spelled out for rare ones. This lesson builds the tool that finds the pieces. Byte-pair encoding, or BPE, began as a data-compression method in 1994 and was adapted for language models in 2016. The algorithm is simple enough to state in one sentence: start with single bytes, and repeatedly join the pair of neighbouring tokens that occurs most often into a new token. We will see what that does, step by step, and then write it down.
The algorithm by hand
Take a tiny text of fourteen words: walk five times, walking four times, walked three times and talks twice. Each word is written with a leading space, as it would appear in running text, and each is cut into single characters. We keep a count of how many times each word occurs, because every occurrence contributes to the pair counts.
The training loop is:
1. Count every adjacent pair of tokens across all the words, weighted by the word counts.
2. Find the most frequent pair.
3. Create a new token for it and replace the pair by the new token everywhere.
4. Repeat.
Here is what happens, with the three most frequent pairs at each step. A pair is shown as left|right, and the first line of each step gives the pair counts before the merge.
Step · Top pairs (count) · Merge · Words after the merge0 · a\ · l 14, l\ · k 14, \ · w 12 · a + l → al · w al k, w al k e d, w al k i n g, t al k s
1 · al\ · k 14, \ · w 12, w\ · al 12 · al + k → alk · w alk, w alk e d, w alk i n g, t alk s
2 · \ · w 12, w\ · alk 12, alk\ · i 4 · + w → w · w alk, w alk e d, w alk i n g, t alk s
3 · w\ · alk 12, alk\ · i 4, i\ · n 4 · w + alk → walk · walk, walk e d, walk i n g, t alk s
4 · walk\ · i 4, i\ · n 4, n\ · g 4 · walk + i → walki · walk, walk e d, walki n g, ...
5 · walki\ · n 4, n\ · g 4, walk\ · e 3 · walki + n → walkin · walk, walk e d, walkin g, ...
6 · walkin\ · g 4, walk\ · e 3, e\ · d 3 · walkin + g → walking · walk, walk e d, walking, ...
Four things are worth noticing.
Ties. At step 0 the pairs a|l and l|k both occur 14 times. The program breaks ties by taking the pair it found first. Any consistent rule works, but the result depends on it, so it is part of the definition of a particular tokenizer.
Frequent letters first, whole words later. The first merges build up the shared stem alk, which appears in all four words. Only then do the merges that produce walk and walking appear. The algorithm finds the pieces the text has most in common.
A rare ending is never built. The word talks appears only twice, so none of its pairs ever beats the others and it stays as t, alk, s. That is the intended behaviour: spend vocabulary on what is frequent.
Merges are recorded in order. Step 3 only makes sense because steps 0 to 2 came first. The list of merges, in order, is the tokenizer.
The code
We work on bytes, as Lesson 2.1 recommended, so that any text can be represented. The starting vocabulary is the 256 possible byte values, and each merge adds one new entry.
First, a decision about what a "word" is. We cut the text into pieces, each a word with the space before it, or a run of whitespace. Merges are only learned within a piece, never across a boundary, so the tokenizer never creates a token like ed the. This is called pre-tokenisation. We use a regular expression.
python
import re
from collections import Counter
def pretokens(text):
"""Cut text into pieces: a word with its leading space, or a run of whitespace."""
return re.findall(r" ?[^\s]+|\s+", text)
Next, the three small helpers: count the pairs, and merge a chosen pair into a sequence.
python
def paircounts(seqs):
counts = Counter()
for seq, n in seqs.items():
for pair in zip(seq, seq[1:]):
counts[pair] += n
return counts
def mergepair(seq, pair, newid):
out, i = [], 0
while i < len(seq):
if i < len(seq) - 1 and (seq[i], seq[i + 1]) == pair:
out.append(newid)
i += 2
else:
out.append(seq[i])
i += 1
return tuple(out)
The trainer follows the four-step loop. It never works on the raw text again after the first step: it keeps a table seqs from each distinct piece, written as a tuple of ids, to the number of times it occurs. This is a large saving, because a text of 18,042 words has only 151 distinct pieces.
python
def trainbpe(text, nmerges):
seqs = Counter()
for piece in pretokens(text):
seqs[tuple(piece.encode("utf-8"))] += 1
merges = {} # (id, id) -> new id, in the order created
vocab = {i: bytes([i]) for i in range(256)} # id -> the bytes it stands for
for m in range(nmerges):
counts = paircounts(seqs)
if not counts:
break
pair = counts.mostcommon(1)[0][0]
newid = 256 + m
merges[pair] = newid
vocab[newid] = vocab[pair[0]] + vocab[pair[1]]
newseqs = Counter()
for seq, n in seqs.items():
newseqs[mergepair(seq, pair, newid)] += n
seqs = newseqs
return merges, vocab
Two dictionaries come out. merges says which pair became which new id, and the id number records the order. vocab says which bytes each id stands for, so that we can turn ids back into text.
Encoding a new text applies the merges to each piece in the order they were learned. At every step it finds, among the pairs present in the piece, the one with the earliest rank, and merges it.
python
def encode(text, merges):
ids = []
for piece in pretokens(text):
seq = tuple(piece.encode("utf-8"))
while len(seq) > 1:
pairs = set(zip(seq, seq[1:]))
best = min(pairs, key=lambda p: merges.get(p, float("inf")))
if best not in merges:
break
seq = mergepair(seq, best, merges[best])
ids.extend(seq)
return ids
def decode(ids, vocab):
return b"".join(vocab[i] for i in ids).decode("utf-8", errors="replace")
Decoding is trivial: look up the bytes for every id, join them, and read the result as UTF-8. That simplicity is the reward for working with bytes. The errors="replace" matters later, when a model generates an invalid sequence of bytes; without it the program would crash.
Why does the earliest merge go first? Because the tokenizer must apply the merges in the order they were learned. The pair joined at step 3 was chosen because the pairs from steps 0 to 2 had already been merged. Applying them in a different order could split a word differently from the way training did, and the model would meet token sequences it never saw.
Training on the suffix-rich text
We train on the 2,700 training sentences of the text from Lesson 2.1 (18,042 words, 79,909 bytes), and learn 150 merges, giving a vocabulary of 256 + 150 = 406 entries.
python
merges, vocab = trainbpe(traintext, 150)
print(len(merges), len(vocab)) # 150 406
The training takes under a tenth of a second on the machine used to check this course (the time varies with the computer). The pieces number only 151, and each merge needs one pass over them. The first twelve merges are:
Merge · Token created · Pair count0 · he · 4,045
1 · the · 3,790
2 · . · 2,700
3 · the · 1,790
4 · w · 1,558
5 · wa · 1,425
6 · a · 1,247
7 · g · 1,226
8 · ll · 1,204
9 · te · 1,029
10 · or · 944
11 · c · 840
The first merge is he, which occurs in "the" and in the verb "help". There is no linguistics in the choice, only counting. The third, ., is a space and a full stop: it occurs once per sentence, 2,700 times. Pairs with a leading space, such as w and a, are the starts of words.
The later merges look more like language. Merges 25 to 60 produce ing, ked, un, er, and the whole words wall, box, small, house, green, gate, door, car, old, boy, doctor, team and aunt. We never told the algorithm about suffixes. It learned ing and er because many words end in them, and learned whole nouns because those appear in every second sentence.
What the tokenizer does to real sentences
Encode a sentence the training text never contained exactly:
python
s = " the doctor was kicking the small house ."
ids = encode(s, merges)
print([vocab[i].decode() for i in ids])
# [' the', ' doctor', ' was', ' kick', 'ing', ' the', ' small', ' house', ' .']
print(ids)
# [259, 308, 280, 378, 281, 259, 290, 293, 258]
The sentence is 41 bytes and nine tokens, about 4.6 bytes per token. Every word but one is a single token; "kicking" is kick and ing. Over the whole text the average is 3.54 bytes per token, and 1.25 tokens per word, as Lesson 2.1 listed. English text with a GPT-2 style tokenizer of 50,000 merges averages roughly four characters per token, a widely quoted rule of thumb.
Now some new verbs, whose stems the training text never contained:
Word · Pieces walkers · walk + ers
kicking · kick + ing
hunted · hun + ted
tracker · t + r + a + c + k + er
walkers is a word form in the training text, and the tokenizer found both parts. hunted splits at an odd place, hun and ted, because the pair te was a more frequent pair in the text than any pair that would split it at the stem. The tokenizer does not know where morphemes begin. It only knows which pairs were frequent. For tracker, a word whose stem is unseen, the pieces are mostly single letters and the learned er, which is the case we wanted to be possible.
A bug found by a round-trip test
The first version of pretokens that we wrote used the pattern ?[^\s]+|\n: a word with an optional leading space, or a newline. It worked on our text and passed the round-trip test on the whole validation set. But a tokenizer should be lossless for any string, so we tested some unusual ones:
python
for s in ["café ☕", " two spaces", "🙂 emoji\n", "", "a"]:
ids = encode(s, merges)
print(repr(s), len(s), len(s.encode()), len(ids), decode(ids, vocab) == s)
With the first pattern, " two spaces" failed: it was thirteen characters going in and came back as eleven, with the doubled spaces lost. The reason is that the pattern allows only one leading space on a word. A second space matches neither alternative, and re.findall silently skips characters that no alternative matches. The fix is the pattern used above, ?[^\s]+|\s+, whose second alternative matches any run of whitespace, so every character in the string belongs to exactly one piece. With it:
String · Characters · Bytes · Tokens · Round trip exactcafé ☕ · 6 · 9 · 9 · Yes
two spaces · 13 · 13 · 13 · Yes
🙂 emoji and a newline · 8 · 11 · 11 · Yes
(empty string) · 0 · 0 · 0 · Yes
a · 1 · 1 · 1 · Yes
Two lessons come out of this. The first is the practical one: always test a tokenizer's round trip on odd strings, not only on the data it was trained on. A tokenizer that drops a space or a character corrupts every document it touches, and the model trained on it will have been taught to produce text that cannot be reconstructed. The second is the pattern behind it: a regular expression that ignores some characters rather than failing on them can be wrong without any sign. Checking that all the pieces joined together give back the input is a one-line guard.
The table also shows the cost of text the tokenizer was not trained on. The tokenizer learned no merges for accented letters, emoji or doubled spaces, so these are spelled out in bytes: café ☕ is nine tokens for six characters, and the doubled-space string costs one token per byte. That is unavoidable in a tokenizer trained on a small English text, but it never fails, which is the point of a byte alphabet.
How much to merge
The number of merges is the one setting in the algorithm. The training text shows the pattern again:
Merges · Vocabulary · Tokens per word · Entries actually used0 · 256 · 4.43 · 26
60 · 316 · 1.87 · 66
150 · 406 · 1.25 · 88
Note the last column. A vocabulary of 406 entries uses only 88 in this text, because most of the 256 byte values never occur in it. In a real tokenizer the leftover entries stay available for the text it will meet later. In a model, an entry that is never used gets almost no training and wastes a row of the embedding table, which is one reason that small-vocabulary models prefer to train their tokenizer on data close to what the model will see.
Choosing the size for a real model balances three things. A larger vocabulary shortens every text, so the model reads more per step and attention is cheaper. It also enlarges the embedding table and the output layer by one row per entry, and the rare tokens are seen too seldom for their rows to be learned well. GPT-2's 50,257 and the 100,000 to 250,000 used by recent multilingual models are choices made by training runs, not theory.
Special tokens and the rest of the toolkit
A few more things complete a tokenizer for real use.
Special tokens. Entries such as an end-of-text marker are added to the vocabulary by hand and are never produced by merging. The encoder must match them first, as whole strings, before it applies pre-tokenisation, or an end-of-text marker in the input would be cut into ordinary pieces.
Saving and loading. A tokenizer is its ordered merges. Save them to a file as the list of pairs, and the vocabulary can be rebuilt. A model must always be used with the exact tokenizer it was trained with.
Speed. Our encoder re-scans a piece after each merge, which is fine for a lesson. Production tokenisers use a priority queue or a compiled implementation and cache the result for each distinct piece.
Better pre-tokenisation. GPT-2 splits text with a more careful pattern that keeps contractions, letters, numbers and punctuation in separate pieces. That prevents merges such as dog. and dog! from becoming separate tokens, and keeps digits from joining words. The principle is the same as ours: choose the boundaries across which merges are not allowed.
With that, the tokenizer is done. It has no neural network, no gradient and no randomness. It is a deterministic procedure that depends only on the text it was learned from, and everything the model learns afterwards sits on top of it.
Key takeaways
Byte-pair encoding starts from the 256 bytes and repeatedly merges the most frequent adjacent pair into a new token. The ordered list of merges is the tokenizer.
On the toy text the first merge was a + l with a count of 14, and the merges built up the shared stem alk before the whole words walk and walking.
Training works on a table of distinct pieces with counts. 150 merges on 18,042 words (151 distinct pieces) took under a tenth of a second and gave a vocabulary of 406 and 1.25 tokens per word.
Encoding applies the merges in the order they were learned, choosing at each step the earliest pair that is present.
Decoding joins the bytes of the ids and reads them as UTF-8. Use errors="replace" so that invalid byte sequences from a model do not crash it.
A lossless tokenizer must be tested on odd strings. Our first pre-tokenisation pattern dropped doubled spaces; the fixed pattern ?[^\s]+|\s+ round-trips every test string.
Unseen words and symbols never fail: café ☕ is nine tokens (nine bytes) and an unseen stem is spelled in letters plus learned endings.
The number of merges trades sequence length against table size. The first 20 merges saved 1.57 tokens per word; the last 50 saved 0.22.
Common mistakes
Merging across word boundaries. Without pre-tokenisation, the tokenizer learns tokens such as ed the that mix words.
Skipping the round-trip test. Check decode(encode(s)) == s on weird input: double spaces, tabs, newlines, accents, emoji, an empty string.
Applying merges in the wrong order. Encode by earliest-learned merge first, or the text will be cut differently from the training text.
Training the tokenizer on test data. Learn the merges from the training text only.
Forgetting that the tokenizer is part of the model. Changing a single merge changes every id after it. Save the merges together with the model.
Treating ties as unimportant. Ties are broken by an arbitrary rule. Fix the rule, or two runs will build different tokenisers.
Check yourself
1. In a text with the ten times and that five times, how often does the pair t|h occur, and which of h|e and h|a is merged first?
t|h occurs 15 times, in both words. h|e occurs 10 times and h|a 5 times, so h|e is merged first.
2. A vocabulary has 256 bytes and 1,000 merges plus one special token. How many entries does it have?
256 + 1,000 + 1 = 1,257.
3. Why does the encoder need the merge order and not just the set of merges?
The merges were learned in a sequence in which each depended on the earlier ones. Applying them in a different order can cut a word differently from the way training did.
4. A tokenizer produces 4.6 bytes per token on common words and 1 byte per token on emoji. What does that imply about cost?
Text full of rare symbols uses many more tokens per character, so it fills the context window sooner and costs more to process.
5. Why is errors="replace" used in decode?
A model can generate a token sequence whose bytes are not valid UTF-8, such as half of a multi-byte character. Replacing them with the symbol � avoids a crash.
Try this
Set aside ninety minutes. You need Python and the corpus generator from Lesson 2.1.
1. Type in the code and train 150 merges. Check the vocabulary size, the first merge he, and that the validation text round-trips.
2. Reproduce the hand-worked toy example. Print the three most frequent pairs after every merge and compare with the table.
3. Run the five odd strings through the round-trip test. Then replace the pattern by ?[^\s]+|\n and repeat. Which strings fail, and why?
4. Train with 20, 60 and 300 merges. Plot tokens per word for the training text and for the new text from Lesson 2.1. At which point does the curve flatten?
5. Add a special token <|end|> as id 406. Make encode recognise it before pre-tokenisation. Check that encode("a <|end|>") ends with 406.
6. Write the merges to a text file, one pair per line, and rebuild the tokenizer from the file. Check that it gives the same ids.
A good result is a tokenizer that round-trips every string you can think of, a table of tokens per word against merges that matches ours, and a clear picture of how an unseen word is cut. The next lesson turns each token id into a vector of numbers that the model can compute with.
Read more
Philip Gage's 1994 article "A New Algorithm for Data Compression" in The C Users Journal is the origin of the method. Sennrich, Haddow and Birch's 2016 paper adapted it to neural language models. The GPT-2 paper and OpenAI's tiktoken documentation describe the byte-level variant with a regular-expression pre-tokenisation. Andrej Karpathy's lecture "Let's build the GPT Tokenizer" and the minbpe repository implement the same algorithm with more detail on the regular expression and special tokens.
Tags: Build an LLM Byte-pair encoding Tokenizer Subword tokens Python