Byte-pair merging
Trace a toy tokenizer and explain byte-pair merges, vocabulary IDs and token-budget limits.
THE IDEA
Learning pieces by merging frequent pairs
Byte-pair encoding (BPE) builds a vocabulary of useful pieces from data. Start with single symbols. Count every pair of adjacent symbols across the corpus, merge the most frequent pair into a new symbol, and repeat. Frequent chunks ("est", "low") become single tokens; rare words are still spelled out of smaller pieces.
The smallest case: in the symbols a, b, a, b the pair (a, b) occurs twice. Merging it gives ab, ab and shortens the sequence from 4 to 2.
Start: every word is a list of single letters. Total symbols: 79
| most frequent pairs now | count |
|---|---|
| (e, s) | 9 |
| (s, t) | 9 |
| (w, e) | 8 |
| (l, o) | 7 |
| (o, w) | 7 |
Ties are broken alphabetically by this toy learner. Real tokenizers define their own rules.
Predict first. In the toy symbols a, b, a, b, how often does the adjacent pair a, b occur?
Chapter context
A language model receives token IDs, not visible words. The tokenizer chooses how text becomes those IDs. Different tokenizers can represent the same string with different lengths, so character count is not a universal token count.
TRY IT YOURSELF
Part 1. Do it hands-on
Count pairs and run the first merges by hand on the toy corpus, then write the whole learner in Python.
Start: every word is a list of single letters. Total symbols: 79
| most frequent pairs now | count |
|---|---|
| (e, s) | 9 |
| (s, t) | 9 |
| (w, e) | 8 |
| (l, o) | 7 |
| (o, w) | 7 |
Ties are broken alphabetically by this toy learner. Real tokenizers define their own rules.
- To do: Corpus: low ×5, lower ×2, newest ×6, widest ×3 (split into letters). How many times does the adjacent pair (e, s) occur in total?
- To do: BPE merges the most frequent pair; if two tie, take the alphabetically smaller. Which pair is merged first? Type the new symbol (two letters)
- To do: Total number of symbols in the whole corpus (counting each word as many times as it occurs) after that first merge
- To do: Second merge: after "es" exists, which new symbol is created? Type it
Part 2. Do it in code
- count_pairs(words): words is a list of (symbols, count) where symbols is a list of strings. Return a dict (left, right) -> total count of that adjacent pair, each word counted `count` times.
- best_pair(words): the pair with the highest count; ties go to the smallest pair (compare as tuples). Return None if there are no pairs.
- merge_word(symbols, pair): replace each adjacent occurrence of pair (left to right, non-overlapping) with the joined symbol. Return a new list.
- learn_bpe(words, num_merges): repeat best_pair and merge in every word; return the list of merged pairs. Stop early if no pair is left.
Stuck, or something not working? You can come back to it any time.
CHECK YOUR UNDERSTANDING
In the toy symbols a,b,a,b, how often does adjacent a,b occur?
Chapter reference: math, worked example & code
This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.
Math and notation
In a toy merge, replacing m nonoverlapping adjacent pairs by one symbol reduces sequence length by m. A request budget must include formatted input plus requested output within the model's supported context; exact accounting is model-specific.
Worked example
Start with toy symbols ['a','b','a','b'] and a vocabulary containing a and b. The pair (a,b) occurs twice. A merge creates symbol ab and encodes the sequence as ['ab','ab'], reducing length from 4 to 2. This deliberately omits byte encoding and pre-tokenization so the merge operation is visible.
Reference code
The following example uses the Python standard library and does not call a remote service.
tokens = list('abab')
merged=[]
i=0
while i < len(tokens):
if tokens[i:i+2] == ['a','b']:
merged.append('ab'); i += 2
else:
merged.append(tokens[i]); i += 1
assert merged == ['ab','ab']
assert len(tokens)-len(merged) == 2
Python examples are provided for study and local execution; this page does not execute Python.
Common mistakes
A token is not necessarily a word. A vocabulary ID is a label, not a magnitude. A hand-built toy merge sequence is not a drop-in replacement for a production tokenizer.