How does byte-pair encoding learn its merge table when a tokenizer is trained?
answer
- greedy counting, no gradients
- adjacent pairs weighted by word frequency
- merge the winner, then recount
- the table is ordered
- replay rules in rank order to encode
basics
~20 sBPE starts with every word split into single symbols, counts every adjacent symbol pair across the corpus, merges the single most frequent pair into a new token, and repeats until the vocabulary target is reached. The ordered list of merges is the tokenizer.
solid answer
~50 sTraining is a greedy frequency loop. You start from a base alphabet — characters, or all 256 byte values — and represent each word in the training corpus as a sequence of those symbols, weighted by how often the word occurs. Then you count every adjacent symbol pair across the whole corpus, take the single most frequent pair, and merge it everywhere into one new symbol, which is added to the vocabulary. Recount, merge again, and repeat until you hit the target vocabulary size. The output is an ordered **merge table**: rule 1, rule 2, and so on. Encoding new text replays those rules in that exact rank order over the base symbols, which is what makes tokenization deterministic and reproducible. Nothing here is learned by gradient descent — it is pure corpus counting, done once before pretraining.
code
python · 29 linesfrom collections import Counter
corpus = {
"l o w </w>": 5,
"l o w e r </w>": 2,
"n e w e s t </w>": 6,
"w i d e s t </w>": 3,
}
def best_pair(corpus):
pairs = Counter()
for word, freq in corpus.items():
symbols = word.split()
for a, b in zip(symbols, symbols[1:]):
pairs[(a, b)] += freq
return pairs.most_common(1)[0][0]
def apply_merge(corpus, pair):
bigram, joined = " ".join(pair), "".join(pair)
return {w.replace(bigram, joined): f for w, f in corpus.items()}
merges = []
for _ in range(4):
pair = best_pair(corpus)
merges.append(pair)
corpus = apply_merge(corpus, pair)
print(merges)
print(corpus)go deeper
Know the loop in one sentence: count adjacent pairs, merge the most frequent, repeat until the vocabulary is full. Being able to name that the output is a list of merge rules is enough at this level.
Be ready to run the toy corpus by hand and get es, est in the right order, and to explain that encoding replays the rules in rank order rather than searching for longest matches.
Show you understand what the corpus choice bakes in — which morphemes, which languages and which code patterns earn slots — and that the artefact is frozen once pretraining begins.
Own the consequences of a one-shot, ungoverned greedy fit: the merge table silently encodes the data mix of the day, and correcting it later costs vocabulary extension plus continued pretraining, so it deserves the same review as any long-lived interface.
## The training loop Byte-pair encoding was borrowed from data compression and adapted to tokenization. The training procedure is short enough to state completely: 1. **Pre-tokenize.** Split the corpus into words or word-like chunks (typically on whitespace and punctuation boundaries) and count how often each chunk occurs. Merges are never allowed to cross these boundaries, which is what stops the algorithm from learning a single token for a common two-word phrase in most implementations. 2. **Seed the vocabulary.** Every symbol of the base alphabet gets a slot: all distinct characters, or in byte-level variants all 256 byte values. Each word becomes a sequence of those symbols, usually with an end-of-word marker so that a piece appearing word-finally is distinguishable from the same piece appearing mid-word. 3. **Count pairs.** For every adjacent pair of symbols inside a word, add that word's corpus frequency to the pair's count. 4. **Merge the winner.** Take the highest-count pair, concatenate it into a single new symbol, add it to the vocabulary, and rewrite every occurrence in the corpus. Record the rule. 5. **Repeat** from step 3 until the vocabulary reaches the target size. ## The classic walkthrough The standard toy corpus is `low` x5, `lower` x2, `newest` x6, `widest` x3. Split into characters, the pair `e`+`s` occurs 6 times inside `newest` and 3 inside `widest`, for 9 — the joint winner, so `es` is created. Recounting, `es`+`t` now scores 9 and becomes `est`. Then `est` plus the end-of-word marker scores 9. Only after those does `l`+`o` win at 7 (5 from `low`, 2 from `lower`), producing `lo`. Four merges in, the tokenizer has discovered the English superlative suffix `est` and the stem `low` without anyone telling it what a morpheme is. That is the whole appeal: the pieces that earn a slot are exactly the pieces that recur. Notice what the counting rewards. A sequence that is frequent *as a substring across many distinct words* wins early; a long word that is itself very frequent also survives whole, because its internal pairs are counted at its full frequency and get merged all the way up. Both common-word-stays-whole and rare-word-splits behaviour fall out of the same rule. ## Merge order is part of the artefact The merge table is ordered, and the order matters as much as the contents. At encoding time, a word is split into base symbols and the rules are tried in learned rank order: rule 1 applied wherever it matches, then rule 2, and so on. Applying the same set of rules in a different order can produce a different segmentation, so shipping the merges as an unordered set would break reproducibility. This is also why BPE encoding is not "find the longest token that matches" — that is a different algorithm with different output. ## What this implies downstream **The tokenizer inherits its corpus's biases.** Merges are learned from whatever text was fed in. If that text is 90% English web pages, the merge table encodes English morphemes, and everything else fragments. If code was underrepresented, common identifier patterns and indentation runs get no slots. **Training is cheap and offline.** No gradients, no GPUs in the usual sense — it is counting over a corpus sample, typically a small fraction of the pretraining data. Practical implementations keep incremental pair counts rather than rescanning, but the semantics are exactly the naive loop. **The result is frozen.** Once pretraining starts, ids are bound to embedding rows. Adding a merge later renumbers nothing, but adding tokens means growing the embedding and output matrices and continuing training so the new rows are not random. **Numbers and whitespace are shaped by the same greedy counting.** Whether digits are grouped into multi-digit tokens or forced to split individually is a choice made in pre-tokenization and merge policy, and it has real consequences for arithmetic behaviour. Modern tokenizers often deliberately constrain digit merging for exactly that reason. ## What interviewers probe The usual follow-ups are: what exactly is being counted (adjacent pairs weighted by word frequency, not raw substring counts); what stops merges from spanning words (pre-tokenization); how encoding works given the table (replay in rank order); and what happens on a tie (implementation-defined, commonly first-encountered or lexicographic — the honest answer is that it is a convention, not a principle). Being able to run the toy corpus by hand is the difference between having read about BPE and understanding it.
- Given a trained merge table, how does the tokenizer encode a word it has never seen?It splits the word into base symbols — characters or bytes — and then applies the merge rules in their learned rank order, merging every position where a rule matches before moving to the next rule. Whatever symbols remain unmerged are the output tokens. So an unseen word is assembled from the highest-ranked pieces that happen to fit it, and in the worst case falls back to individual base symbols.
- Why does pre-tokenization matter before the merge loop runs?Pre-tokenization sets the boundaries merges may not cross, usually at whitespace and punctuation. Without it, a frequent two-word collocation could be merged into one token, blowing up the vocabulary with phrase-level entries and making the tokenizer brittle to word order. It also determines how whitespace itself is represented — typically attached to the following token — which is why leading spaces change token ids.
- Two candidate pairs tie for the highest count. What happens?It is an implementation convention, not a property of the algorithm — commonly the first pair encountered in iteration order, or a lexicographic tiebreak. What matters is that the convention is deterministic, because the merge table must be reproducible: the same corpus and the same code have to yield the same ordered rules, or encodings will not match the ids the model was trained on.
- Does the merge loop optimise any objective, the way training a model does?No. It is greedy frequency counting with no objective function and no lookahead, so the resulting vocabulary is not optimal by any global criterion — it is simply what repeated local wins produce. That is precisely the gap WordPiece and Unigram target, by scoring candidates against corpus likelihood instead of raw count.
saying these in an interview costs you the question
- Says BPE merges are learned by gradient descent with the model
- Describes encoding as longest-match lookup in the vocabulary
- Thinks merges are counted per document rather than weighted by word frequency
- Treats the merge table as an unordered set of pieces
- Believes merges can span whitespace to capture phrases