The last lesson ended on a pointed question: who decides that tokenization becomes token plus isation, and not some other split? The answer is an algorithm, and the one behind most modern tokenizers is byte-pair encoding, or BPE. Its idea is almost disarmingly data-driven: start with the smallest pieces you can — single characters — and repeatedly glue together the adjacent pair that shows up most often, until you have built up a useful vocabulary of common chunks. No linguist hands the model a dictionary; the dictionary emerges from counting. In this lesson you implement that merge loop yourself. By the end, the rule that the same word can cost different amounts stops being a slogan and becomes a number you computed by hand — because your tokenizer, trained on a tiny corpus, made a different choice than one trained on a larger one would.
Symbols, pairs, and merges
BPE works on a corpus — a list of example words — and at the start it pretends to know nothing larger than a character. Each word is represented as a list of symbols, which initially are just its characters: lower becomes l, o, w, e, r. The algorithm's whole job is to decide which adjacent pairs of symbols deserve to be merged into a new, larger symbol. A merge takes two neighbouring symbols a and b and replaces every occurrence of that adjacent pair with a single new symbol ab. After enough rounds, common fragments of words — th, ing, ation — have become single symbols, while rare letter combinations stay separate. The ordered list of merges you performed is the tokenizer's vocabulary: to handle brand-new text later, you simply replay those same merges in the same order.
flowchart LR C["corpus of words"] --> S["each word as symbols"] S --> P["count adjacent pairs"] P --> M["merge the most frequent pair"] M -->|"repeat"| P style M fill:#8b5cf6,color:#fff
Counting is the judgement
The counting step is what gives BPE its taste. You walk every word's symbol list and tally each adjacent pair: in l o w e r the pairs are l-o, o-w, w-e, e-r. Do this across the whole corpus and the pair that turns up most often is your best candidate for a merge, because merging it will shorten the greatest number of words. A pair that appears only once is barely worth a token of its own; a pair that appears a thousand times clearly is. Frequencies are the only signal, and the algorithm trusts nothing else — which is precisely why two tokenizers trained on different corpora disagree about where a word splits. What is common in source code is rare in poetry, so the same word earns a different merge under each.
function countPairs(words) {
const freq = {};
for (const syms of words) {
for (let i = 0; i + 1 < syms.length; i++) {
const key = syms[i] + "|" + syms[i + 1];
freq[key] = (freq[key] || 0) + 1;
}
}
return freq;
}
const corpus = [["a", "b"], ["a", "b"], ["a", "b", "c"]];
console.log(countPairs(corpus)); // { "a|b": 3, "b|c": 1 }
Pick the winner and apply it
Counting gives you a frequency table; the next move is to act on it. The best pair is the key with the highest count — and because two pairs can tie, you need a deterministic tie-break so training is reproducible: on a tie, take the lexicographically smallest key. Then you apply that merge to every word, replacing each adjacent occurrence of the pair with the merged symbol, and record the merge in order. Applying a merge is a careful left-to-right sweep: when you spot the pair, emit the new symbol and jump two places ahead, so overlapping candidates like the two pairs hidden inside a a a are handled without double-counting. One count, one pick, one sweep, and the whole corpus is one symbol shorter on average.
flowchart LR I["a b a b"] -->|"merge a,b"| O["ab ab"] style O fill:#166534,color:#fff
function mergeWord(syms, a, b) {
const out = [];
let i = 0;
while (i < syms.length) {
if (i + 1 < syms.length && syms[i] === a && syms[i + 1] === b) {
out.push(a + b);
i += 2;
} else {
out.push(syms[i]);
i += 1;
}
}
return out;
}
const merges = [["a", "b"], ["ab", "c"]];
function applyMerges(syms) {
let s = syms.slice();
for (const [a, b] of merges) s = mergeWord(s, a, b);
return s;
}
console.log(applyMerges(["a", "b", "c"]).join(",")); // abc -> 1 token
console.log(applyMerges(["a", "c"]).join(",")); // ac -> a,c (no merge applies)
Where cost actually comes from
Here is the link back to the bill. Because merges are learned from frequencies, the token count of a word is just whatever this particular set of merges reduces it to — and nothing more. A word whose pieces all got merged is one token; a word built from pieces that never paired up stays several. That is the literal mechanism behind the claim that the same word costs different amounts: not magic, not a price table, just a different merge history. Retrain on a different corpus and the frequencies change, different pairs win, and a word that used to be one token may suddenly be three. The billable unit is a side-effect of whatever your training data happened to make common.
flowchart TD D1["trained on docs"] --> M1["merges favour word fragments"] D2["trained on code"] --> M2["merges favour symbols and camelCase"] W["one word"] --> T1["under D1: fewer tokens"] W --> T2["under D2: more tokens"] style T1 fill:#166534,color:#fff style T2 fill:#b91c1c,color:#fff
What does this print? mergeWord replaces every adjacent a,b pair with ab, sweeping left to right and jumping two places after each merge.
function mergeWord(syms, a, b) {
const out = [];
let i = 0;
while (i < syms.length) {
if (i + 1 < syms.length && syms[i] === a && syms[i + 1] === b) {
out.push(a + b);
i += 2;
} else {
out.push(syms[i]);
i += 1;
}
}
return out;
}
console.log(mergeWord(["a", "b", "c", "a", "b"], "a", "b").join(","));
Positions 0 and 1 are a,b -> they become ab, then skip to index 2.
Index 2 is c (kept), then indices 3 and 4 are another a,b -> ab. Join with commas.
Write countPairs(words) where words is an array of symbol-arrays. Return a plain object mapping each adjacent pair — keyed as first + "|" + second — to how many times it occurs across all words.
function countPairs(words) {
// tally each adjacent pair as "a|b" -> count
}
Loop over each word's symbols with i from 0 to length - 2.
Build the key as syms[i] + "|" + syms[i+1] and increment freq[key].
function countPairs(words) {
const freq = {};
for (const syms of words) {
for (let i = 0; i + 1 < syms.length; i++) {
const key = syms[i] + "|" + syms[i + 1];
freq[key] = (freq[key] || 0) + 1;
}
}
return freq;
}
mergeWord should replace every adjacent a,b pair with ab, but this version stops after the first merge and leaves later pairs untouched. Fix it so all occurrences are merged. (The merged flag is the culprit.)
function mergeWord(syms, a, b) {
const out = [];
let merged = false;
let i = 0;
while (i < syms.length) {
if (!merged && i + 1 < syms.length && syms[i] === a && syms[i + 1] === b) {
out.push(a + b);
merged = true;
i += 2;
} else {
out.push(syms[i]);
i += 1;
}
}
return out;
}
The merged flag freezes the function after one replacement.
Drop the flag (and its check) so the loop keeps merging every a,b pair it meets.
function mergeWord(syms, a, b) {
const out = [];
let i = 0;
while (i < syms.length) {
if (i + 1 < syms.length && syms[i] === a && syms[i + 1] === b) {
out.push(a + b);
i += 2;
} else {
out.push(syms[i]);
i += 1;
}
}
return out;
}
Write learnMerges(corpus, numMerges) that learns BPE merges. corpus is an array of word strings; start each word as its list of characters. Each round: count adjacent pairs (use countPairs, provided), pick the best pair with topPair (provided — most frequent, ties broken lexicographically), record it, then apply that merge to every word. Return the ordered list of [a, b] merges. Stop early if no pairs remain.
function countPairs(words) {
const freq = {};
for (const syms of words) {
for (let i = 0; i + 1 < syms.length; i++) {
const key = syms[i] + "|" + syms[i + 1];
freq[key] = (freq[key] || 0) + 1;
}
}
return freq;
}
function topPair(freq) {
let best = null;
for (const key in freq) {
if (best === null || freq[key] > freq[best] || (freq[key] === freq[best] && key < best)) {
best = key;
}
}
return best === null ? null : best.split("|");
}
function mergeWord(syms, a, b) {
const out = [];
let i = 0;
while (i < syms.length) {
if (i + 1 < syms.length && syms[i] === a && syms[i + 1] === b) {
out.push(a + b);
i += 2;
} else {
out.push(syms[i]);
i += 1;
}
}
return out;
}
function learnMerges(corpus, numMerges) {
// start each word as chars; loop numMerges times: count, pick best, record, apply
}
Map corpus to char-arrays once, then loop numMerges times.
Each round: pair = topPair(countPairs(words)); if null, break; else push [a,b] and re-map every word through mergeWord.
function countPairs(words) {
const freq = {};
for (const syms of words) {
for (let i = 0; i + 1 < syms.length; i++) {
const key = syms[i] + "|" + syms[i + 1];
freq[key] = (freq[key] || 0) + 1;
}
}
return freq;
}
function topPair(freq) {
let best = null;
for (const key in freq) {
if (best === null || freq[key] > freq[best] || (freq[key] === freq[best] && key < best)) {
best = key;
}
}
return best === null ? null : best.split("|");
}
function mergeWord(syms, a, b) {
const out = [];
let i = 0;
while (i < syms.length) {
if (i + 1 < syms.length && syms[i] === a && syms[i + 1] === b) {
out.push(a + b);
i += 2;
} else {
out.push(syms[i]);
i += 1;
}
}
return out;
}
function learnMerges(corpus, numMerges) {
let words = corpus.map((w) => w.split(""));
const merges = [];
for (let n = 0; n < numMerges; n++) {
const pair = topPair(countPairs(words));
if (pair === null) break;
const [a, b] = pair;
merges.push([a, b]);
words = words.map((syms) => mergeWord(syms, a, b));
}
return merges;
}
In BPE, which pair does the algorithm merge in each round?
BPE is frequency-driven: each round it merges the adjacent pair with the highest count, because that merge shortens the greatest number of words. Ties are broken deterministically so the same corpus always yields the same vocabulary.
Recap
- BPE starts from single characters and repeatedly merges the most frequent adjacent pair into a new symbol.
- A word is a list of symbols; a merge turns every adjacent
a bintoab. The ordered merge list is the vocabulary. - Counting pairs across the corpus is the judgement: frequency alone decides what becomes a token, with ties broken lexicographically for reproducibility.
- Applying a merge is a left-to-right sweep that skips two places after each replacement, so overlapping pairs are not double-counted.
- Different training data produces different merges, so the same word can cost a different number of tokens under different vocabularies.
- At inference you replay merges in their learned order; merging greedily by current frequency would diverge from the provider's counts.
Next: putting tokens to work in a context window — counting a budget, reserving room for the reply, and deciding what falls off the edge.