Byte-Pair Encoding (BPE) is the algorithm underneath the tokenizers of GPT, Llama, and most modern language models, yet its core is almost embarrassingly simple: count the most frequent adjacent pair of symbols, glue it into one new symbol, and repeat. That single greedy rule, applied a few tens of thousands of times, converts raw bytes into a vocabulary that spends short tokens on common patterns and long sequences on rare ones. This piece stays focused on the math of the merge loop itself — how pairs are counted, why the argmax rule is the whole algorithm, how the vocabulary grows exactly one entry per merge, and how the learned merge order becomes the priority table that drives greedy encoding. Sibling articles cover tiktoken, SentencePiece, and the Unigram alternative; here we derive BPE from first principles and work a complete example by hand.
The starting point: an alphabet of atoms
BPE begins with a base vocabulary of indivisible symbols and nothing else. In the classic character-level formulation the atoms are the distinct characters in the corpus; in the byte-level formulation used by GPT-2 onward, the atoms are the 256 possible byte values, 0x00 through 0xFF. Byte-level is the important case: because every possible input — any Unicode text, in any language, plus emoji and binary noise — is just a sequence of bytes, a 256-symbol base guarantees the tokenizer can never hit an out-of-vocabulary character. There is no <UNK> token and no failure mode.
Every word is first written as a sequence of these atoms. If we track word boundaries, we append an end-of-word marker </w> so the model can tell est at the end of a word from est in the middle. So the token lowest starts life as the atom sequence l o w e s t </w> — seven symbols, all drawn from the base vocabulary. Everything BPE learns from here is which of these atoms to fuse together, and in what order.
Counting pairs: the frequency table
The engine of BPE is a count over adjacent symbol pairs. Given the corpus in its current tokenized form, we scan every word and, for each position, record the ordered pair (s_i, s_{i+1}). Because merges never cross word boundaries, we only count pairs within a word.
Crucially, we weight each pair by how often its word occurs. If we keep the corpus as a map from a word’s symbol sequence to its frequency, then for a word w with count c(w), every adjacent pair inside w contributes c(w) to that pair’s total. Formally the score of a pair p is
freq(p) = Σ_w c(w) · count_p(w)
where count_p(w) = number of times pair p appears adjacently in word wThis weighting is why BPE learns useful merges fast: a pair that shows up in a handful of very common words scores enormously higher than one scattered across rare words. The count table is rebuilt (or incrementally updated) once per merge, and it is the only statistic the algorithm ever consults.
The merge rule is the entire algorithm
Given the frequency table, one merge step is a single line of math: take the pair with the highest score and fuse it.
p* = argmax_p freq(p)
merge p* = (a, b) → new symbol 'ab'
replace every adjacent (a, b) in the corpus with 'ab'That is it. There is no gradient, no probability model, no search over multiple candidates — BPE is a greedy, deterministic procedure that commits to the locally most frequent pair at each step and never reconsiders. Ties are broken by a fixed rule (typically the lexicographically smaller pair, or first-seen order) so the result is fully reproducible.
The new symbol 'ab' is added to the vocabulary and treated as a single atom: the next counting pass can pair 'ab' with its neighbors and merge those. This is how BPE bootstraps multi-character units — a merge of two two-character symbols yields a four-character one, so token length can double every step in principle.
Vocabulary growth: exactly one token per merge
The bookkeeping here is clean and worth stating precisely. You start with a base vocabulary of size V_0 (256 for byte-level). Each merge adds exactly one new symbol and removes none, so after k merges the vocabulary size is
V(k) = V_0 + k
byte-level: V(k) = 256 + k (plus any special tokens)This makes vocabulary size a direct dial: to build a 50,000-token vocabulary from bytes you run roughly 50000 − 256 ≈ 49,744 merges (a few slots are reserved for special tokens like <|endoftext|>). The ordered list of merges is the trained model — that list, plus the base alphabet, is everything the tokenizer needs to serialize and later replay.
Because growth is linear in k, the real question is not ‘how big’ but ‘when to stop’: early merges buy huge compression, later ones capture ever-rarer patterns with diminishing returns.
A worked example, by hand
Take a tiny corpus of four word types with these counts, already split into atoms with an end marker:
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> ×3Count the pairs, weighted by word frequency. The pair (e, s) appears in newest (6) and widest (3), scoring 6 + 3 = 9 — the highest. So merge 1 is (e, s) → es. The two words become n e w es t and w i d es t.
Recount. Now (es, t) scores 6 + 3 = 9, the new winner, so merge 2 is (es, t) → est. Recount again: (est, </w>) scores 9, giving merge 3 (est, </w>) → est</w>. Next the pair (l, o) dominates with 5 + 2 = 7, so merge 4 is (l, o) → lo. After four merges our learned merge list is exactly [es, est, est</w>, lo], and the vocabulary has grown by four entries. Notice how the algorithm discovered the suffix est on its own, purely from co-occurrence counts.
Encoding: replaying merges in rank order
Training produces an ordered merge list; encoding a new piece of text replays it. The order is the whole point: the position of a merge in the list is its rank, and rank is priority. Lower rank (learned earlier, therefore more frequent) wins.
To encode a word, start from its atom sequence and repeat: among all adjacent pairs currently present, find the one whose merge has the lowest rank in the trained list, apply that merge, and loop. Stop when no adjacent pair appears in the merge list.
symbols = atoms(word)
loop:
cand = { pair in adjacent(symbols) if pair in merges }
if cand is empty: break
p = argmin_{pair in cand} rank(pair) # earliest-learned wins
symbols = apply_merge(symbols, p)Encoding lowest with the list above: atoms are l o w e s t </w>. The lowest-rank applicable pair is (e, s) → l o w es t; then (es, t) → l o w est; then (l, o) → lo w est. No further pair is in the list, so lowest tokenizes to three tokens. Deterministic, and identical to how tiktoken and the Hugging Face tokenizers do it.
Why greedy-by-frequency compresses text
BPE is, at heart, a data-compression algorithm — it literally began as one, replacing the most common byte pair with an unused byte. The frequency-greedy rule has a clean information-theoretic flavor: each merge shortens the corpus by roughly freq(p*) tokens for the price of one vocabulary slot, so a slot spent on the highest-frequency pair removes the most occurrences per slot.
Iterating this yields a vocabulary whose token lengths track frequency: common words collapse to a single token, common subwords (ing, tion, est) become one token each, and rare strings fall back to short subwords or individual bytes. That is an approximate variable-length code where frequent patterns are cheap — the logic of Huffman coding without ever computing a probability.
Training complexity and the naive-vs-fast gap
The straightforward implementation is quadratic-ish and worth understanding before optimizing it. Let N be the number of symbol occurrences in the (deduplicated, frequency-weighted) corpus and k the number of merges. A naive loop recounts all pairs from scratch each step:
naive: O(k · N) — recount every pair, every mergeFor a 50k-merge vocabulary this is painfully slow, which is why real trainers avoid the full recount. The key observation is that applying a merge only changes pair counts locally, at the positions where the merged pair occurred. An incremental count table with a priority queue keyed on freq(p) lets each merge touch only the affected neighborhoods, dropping the cost dramatically. That is the gap between a textbook collections.Counter loop and the production trainers in SentencePiece and Hugging Face tokenizers.
Pre-tokenization: the boundaries merges cannot cross
Before any pair counting happens, the text is split by a pre-tokenization regex into chunks — roughly words, punctuation runs, and whitespace groups. Merges are confined to within a chunk, never across. This is not a cosmetic detail; it is a hard constraint on the pair-count math.
Byte-level BPE (as in GPT-2) makes a deliberate choice here: instead of an explicit </w> marker, it folds the leading space into the token, so " the" and "the" become different tokens. The pre-tokenizer also prevents pathological merges — without it, BPE would happily fuse a word with the space and the next word, producing enormous, useless multi-word tokens driven purely by frequency.
What token counts mean for a CPU-bound SLM
For a small language model running on a CPU, the tokenizer’s efficiency is not a footnote — it is a direct multiplier on cost. Attention and feed-forward compute scale with sequence length: self-attention is O(T^2 · d) and the linear layers are O(T · d^2), both linear-or-worse in the token count T. A tokenizer that encodes the same document in 10% fewer tokens gives you a straight ~10% cut in prefill FLOPs and KV-cache memory, for free, before the model runs at all.
The catch is vocabulary size. A larger k yields shorter sequences but a fatter embedding matrix and output projection, both O(V · d) in parameters. On a memory-starved CPU device that table can dominate the model’s footprint, so an SLM often picks a smaller vocabulary than a datacenter model — trading slightly longer sequences for a lighter parameter budget. BPE’s linear V(k) = V_0 + k makes that trade-off explicit and tunable.
Pitfalls: greedy is not optimal
The greedy rule that makes BPE fast also makes it suboptimal. Because each merge is chosen for local frequency and never revisited, the final segmentation of a given word is not guaranteed to be the shortest possible, nor the most linguistically sensible. A word can be split in a way that fuses across a natural morpheme boundary simply because an earlier, higher-frequency merge got there first. This is exactly the objection the Unigram LM tokenizer raises — it scores multiple candidate segmentations probabilistically instead of committing greedily.
Two more traps. Numbers fragment badly: digit pairs merge unpredictably, so 2024 and 2025 may tokenize to different lengths, quietly hurting arithmetic. And whitespace and casing multiply the vocabulary: The, the, and the are distinct tokens. None of these are bugs — they are the direct, predictable consequences of a frequency-greedy merge rule, and knowing them is how you read a token count correctly.