Tokens and Embeddings, lesson 2
Training a BPE tokenizer
Merge the most common pair again and again until the vocabulary is full.
Byte tokens never meet an unknown, but they make long lists. This lesson builds the fix that GPT models and many others use: start from bytes, and keep gluing the most common pair of neighbours into a new token. You need the bytes and token IDs from "Text as bytes, bytes as tokens".
By the end, you can:
Part 1. Pieces of words
Work out how many tokens a new piece saves, and why common pieces win.
Whole words keep lists short but meet unknowns. Bytes never meet an unknown but make long lists. The middle way keeps the 256 byte tokens and adds tokens for longer pieces that turn up often. Then common words come out whole, and a rare word like "unhappiness" can split into common pieces like un, happi and ness.
Example 1.1
One new token, two choices
Your text is four words: playing, jumping, reading, walking. On top of the 256 byte tokens you may add one token. Which saves more: "ing" or "jumping"?
- Count the byte tokens7 + 7 + 7 + 7 = 28
Each word is 7 plain letters, so 7 bytes.
- Add "ing"4 × (3 − 1) = 8 saved
Each time it appears, 3 tokens become 1, so 2 are saved. It's in all four words.
- Add "jumping" instead1 × (7 − 1) = 6 saved
7 tokens become 1, but only once.
Answer"ing": 28 tokens become 20, against 22 with "jumping".
A new token saves its length minus one, every time its piece appears. A long rare word saves a lot, once. A short common piece saves a little almost everywhere, and over millions of words that adds up to far more.
Subword token
A token for a piece of a word, like ing or un. With bytes plus subword tokens, common words come out whole, rare words come out in pieces, and nothing is unknown.
saved = (length − 1) × times it appears
Pieces also overlap. Once "ing" is a token, a token for "in" saves nothing in these four words, because every "in" is already inside an "ing". What's worth adding depends on what you already have, so the method in the next part adds pieces one at a time and counts again after each.
Your turn
Your text is: going, doing, being, seeing, running. You may add one token. Which saves more, and how many tokens?
Part 2. Merge the commonest pair
Run BPE by hand: count neighbouring pairs, merge the most common, repeat.
Here's the method. Start from bytes. Count every pair of neighbouring tokens, glue the most common pair into one new token, and count again. The classic small example is "aaabdaaabac", 11 bytes. New tokens take the IDs after the bytes: 256, 257, 258.
Example 2.1
Three merges on aaabdaaabac
Merge the most common pair until no pair appears twice. When two pairs tie, take the one that appears first. What's left?
- Count the pairsaa 4, ab 2, bd 1, da 1, ba 1, ac 1
Each "aaa" holds two "aa" pairs, so "aa" appears 4 times.
- Merge aa into 256aa a b d aa a b a c
Reading left to right, each "aaa" becomes "aa" then "a". 9 tokens.
- Merge aa + a into 257aaa b d aaa b a c
"aa a" and "a b" both appear twice. "aa a" comes first. 7 tokens.
- Merge aaa + b into 258aaab d aaab a c
It appears twice. Now every pair appears once, so stop.
Answer5 tokens, and the vocabulary grew from 256 to 259.
Each merge takes the pair that, by the count, should shorten the text most right now. Repeat that tens of thousands of times on a large pile of text, and the common pieces of words grow out of single bytes, one merge at a time.
Byte pair encoding (BPE)
Training a tokenizer by merging. Start from the 256 byte tokens, count every pair of neighbouring tokens, merge the most common pair into a new token, and repeat for as many merges as you chose. GPT-2's and GPT-4's tokenizers were trained this way.
vocabulary = 256 + number of merges
Watch the overlaps. The count said "aa" appears 4 times, yet the first merge made the string only 2 tokens shorter, 11 to 9. Inside "aaa" the two "aa" pairs share the middle a, and only one of them can merge. A pair's count is a guide, not the saving.
Your turn
Run one BPE step on "dddcddd". Which pair merges, and how many tokens are left?
Part 3. The merge list is the tokenizer
Encode new text by replaying the merges, decode it back, and size a vocabulary.
Training leaves a list of merges, in the order they were learned. That list is the whole tokenizer. To encode new text, write it as bytes and apply the merges one by one, in that order. To decode, swap each token for its bytes and read them as UTF-8.
Example 3.1
Encoding aaabac
Use the three merges learned above: a + a → 256, 256 + a → 257, 257 + b → 258. Which tokens does "aaabac" get?
- Write the bytes97 97 97 98 97 99
a is 97, b is 98, c is 99. 6 tokens.
- Apply merge 1256 97 98 97 99
The first a a becomes 256. 5 tokens.
- Apply merges 2 and 3257 98 97 99, then 258 97 99
256 and a become 257, then 257 and b become 258.
- Decode to checkaaab + a + c = aaabac
Joining each token's bytes gives back the text exactly.
Answer3 tokens: 258, 97, 99.
Encoding and decoding
Encoding turns text into token IDs: write it as bytes, then apply the merges in the order they were learned. Decoding turns IDs back into text: join each token's bytes and read them as UTF-8. Decoding what you encoded gives back the original text.
aaabac → 258 97 99 → aaabac
The size of the vocabulary is a setting you pick: the 256 bytes, plus however many merges you ask for, plus a few special tokens that mark things like the end of a text. GPT-2's vocabulary has 50,257 tokens, with one special token. GPT-4o's has about 200,000.
Your turn
With the same three merges, which tokens does "abaaab" get?
Where you'll meet it
If you're asked to code BPE, it fits in about 15 lines: count pairs with a Counter, take the most common, merge it with one left-to-right scan, repeat. Say how you break ties and what happens to an overlap like "aaa". Then name the cost: every merge rescans all the text, which is why real trainers use faster code.
Every model comes with its own merge list, so the same text gives different tokens in different models. GPT-2's vocabulary has about 50,000 tokens, GPT-4's about 100,000 and GPT-4o's about 200,000. A bigger vocabulary makes token lists shorter, but each token needs its own row of numbers inside the model.
from collections import Counter
def merge(ids, pair, new_id):
out, i = [], 0
while i < len(ids):
hit = tuple(ids[i:i + 2]) == pair # the pair starts here
out.append(new_id if hit else ids[i])
i += 2 if hit else 1
return out
ids = list("aaabdaaabac".encode("utf-8"))
for new_id in range(256, 259): # three merges
pair = Counter(zip(ids, ids[1:])).most_common(1)[0][0]
ids = merge(ids, pair, new_id)
print(pair, "->", new_id, ids)
# (97, 97) -> 256 [256, 97, 98, 100, 256, 97, 98, 97, 99]
# (256, 97) -> 257 [257, 98, 100, 257, 98, 97, 99]
# (257, 98) -> 258 [258, 100, 258, 97, 99]most_common breaks ties by the order pairs were first seen, the same rule as the example. Andrej Karpathy's minbpe builds this loop out into a full tokenizer, with encoding, decoding and GPT-4's rule for cutting text into words first.
Check yourself
Four questions from across the lesson. Try each one before you look back.
1
Before BPE counts any pairs, "naïve" is written as byte tokens. How many?
2
You get 1,000 slots on top of the 256 bytes, to fill with longer pieces of English. Which pieces shorten your lists the most?
3
How does BPE decide which pieces go into its vocabulary?
4
GPT-2's vocabulary has 50,257 tokens: the 256 bytes, one special token that marks the end of a text, and the rest learned by merging. How many merges did it learn?
What to remember
1Pieces of words
A new token saves its length minus one each time its piece appears, so "ing" in four words (8 saved) beats "jumping" once (6).
2Merge the commonest pair
BPE counts neighbouring pairs, merges the most common into a new token and repeats: three merges turn "aaabdaaabac" from 11 tokens into 5.
3The merge list is the tokenizer
To encode, write the text as bytes and replay the merges in the order learned: "aaabac" becomes 258, 97, 99.
3The merge list is the tokenizer
A vocabulary is 256 bytes plus the merges plus any special tokens: 256 + 50,000 + 1 = 50,257 for GPT-2.
Recap and going further
The lesson on one page
- Common words stay whole
- Rare words split into common pieces
- A token saves (length − 1) each time it appears
- Start from the 256 bytes
- Count neighbouring pairs, merge the commonest
- Repeat for as many merges as you choose
- "aaa" holds two aa pairs
- Only one of them can merge
- Text to bytes, then replay the merges in order
- The merge list is the tokenizer
- Join each token's bytes, read them as UTF-8
- Encode then decode gives back the same text
- 256 bytes + merges + special tokens
- GPT-2: 256 + 50,000 + 1 = 50,257
Try this
Train a tokenizer on your own text
Clone Karpathy's minbpe and train its BasicTokenizer on a few pages of text you pick, asking for a vocabulary of 256 + 100. Print the first 20 merges as text. Encode a sentence that wasn't in the training text, decode it, and check you get it back. Then train RegexTokenizer on the same text and compare its merges.
You need: Python, the minbpe code from GitHub, and pip install regex for the regex version.
Look for
- What the first merges are: often a common letter pair, or a letter with a space.
- Whether any
BasicTokenizertokens run across two words, and whether anyRegexTokenizerones do. - How many tokens your new sentence takes against its byte count.
- That "aaabdaaabac" with three merges gives the lesson's 5 tokens: 258, 100, 258, 97, 99.
The words, in plain language
- Subword token
- A token for a piece of a word, like ing or un. With bytes plus subword tokens, common words come out whole, rare words come out in pieces, and nothing is unknown.
- Byte pair encoding (BPE)
- Training a tokenizer by merging. Start from the 256 byte tokens, count every pair of neighbouring tokens, merge the most common pair into a new token, and repeat for as many merges as you chose. GPT-2's and GPT-4's tokenizers were trained this way.
- Encoding and decoding
- Encoding turns text into token IDs: write it as bytes, then apply the merges in the order they were learned. Decoding turns IDs back into text: join each token's bytes and read them as UTF-8. Decoding what you encoded gives back the original text.
Read next
- Byte-Pair Encoding tokenizationHugging FaceBPE training and encoding worked through on a small set of words, then written in Python.
- Neural Machine Translation of Rare Words with Subword UnitsSennrich, Haddow and Birch, 2016The paper that brought BPE to neural language models, as a way to handle rare words.
- minbpeAndrej Karpathy, on GitHubShort, readable byte-level BPE, with GPT-4's tokenizer rebuilt on top of it.
- encoder.py in the GPT-2 releaseOpenAI, on GitHubGPT-2's own tokenizer: the pattern that cuts text into words, and the loop that replays the merges.
Tokens and Embeddings overviewSpotted a mistake? Tell us.