Byte-Pair Encoding Deep Dive

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 w

This 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>     ×3

Count 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 merge

For 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.