Byte-Pair Encoding (BPE)

1.4 Byte-Pair Encoding (BPE)

BPE began life as a text-compression algorithm and was later adopted by OpenAI to tokenize text when pre-training GPT. The intuition: start from characters and repeatedly merge the most frequent adjacent pair into a new token. Frequent sequences (like ing or tion) become single tokens; rare words fall back to smaller pieces.

Training

Suppose our entire corpus is these five words with their counts:

Word	Frequency
hug	10
pug	5
pun	12
bun	4
hugs	5

Step 0, split every word into characters. The initial vocabulary is just the alphabet present in the data:

Vocab:  ["b", "g", "h", "n", "p", "s", "u"]
Corpus: (h u g, 10)  (p u g, 5)  (p u n, 12)  (b u n, 4)  (h u g s, 5)

(In the real world the initial vocabulary contains all ASCII bytes and more, and the corpus is gigabytes of text.)

Step 1, count adjacent pairs and merge the most frequent. The pair ("u","g") appears in hug (10) + pug (5) + hugs (5) = 20 times, the most of any pair. Merge it into a new token ug and add it to the vocabulary:

Vocab:  [... "u", "ug"]
Corpus: (h ug, 10)  (p ug, 5)  (p u n, 12)  (b u n, 4)  (h ug s, 5)

Step 2, repeat. Now ("u","n") appears in pun (12) + bun (4) = 16 times. Merge:

Vocab:  [... "u", "ug", "un"]
Corpus: (h ug, 10)  (p ug, 5)  (p un, 12)  (b un, 4)  (h ug s, 5)

Keep merging until the vocabulary reaches a target size you chose in advance. The ordered list of merges is the trained tokenizer.

Inference, tokenizing new words

To tokenize a new word, apply the learned merges in order. Given the vocabulary [... "u", "ug", "un"]:

Word	Tokens
bug	["b", "ug"]
mug	["[UNK]", "ug"]

bug splits cleanly. mug contains m, which never appeared in training, so it becomes the unknown token [UNK]. (Byte-level BPE, used by GPT-2+, avoids this by starting from raw bytes, every possible character is representable, so [UNK] essentially disappears.)

---

BPE training, step by step

Step 1 / 5

Start from characters. Every word in the corpus is split into single characters, the initial vocabulary. Word counts matter: "hug" appears 10 times, "pug" and "hugs" 5 times each.

← Back

Next →

1.5 Unigram tokenization

Unigram takes the opposite approach to BPE. Instead of growing a vocabulary by merging, it starts with a large vocabulary and prunes it down.

The name comes from its unigram language model: it assumes each token's occurrence is independent of the others, so the probability of a segmentation is just the product of its token probabilities. Tokenizing "I love Paris" means choosing, among all possible ways to cut it, the split with the highest total (log-)probability.

Training

Step 0, build a big initial vocabulary of all frequent substrings (often seeded with BPE):

Word	Frequency	Substrings
hug	10	h, u, g, hu, ug, hug
pug	5	p, u, g, pu, ug, pug
pun	12	p, u, n, pu, un, pun
bun	4	b, u, n, bu, un, bun
hugs	5	h, u, g, s, hu, ug, hug, ugs, hugs, …

Step 1, iteratively remove the least useful tokens. The training loop:

while vocab_size > target_size:
    1. Compute the best split for every word (highest log-probability)
    2. Calculate the "removal loss" for each token, how much total probability we'd lose if it were gone
    3. Remove the lowest-loss tokens (e.g. the bottom X%)

Worked example: computing a removal loss

Say training has assigned these (toy) unigram probabilities to a few candidate tokens: $P(\text{pu}) = 0.10$, $P(\text{g}) = 0.05$, $P(\text{p}) = 0.02$, $P(\text{u}) = 0.03$.

With "pu" in the vocabulary, the best split of "pug" is pu + g, with probability $0.10 \times 0.05 = 0.0050$. Now ask what happens to "pug" if "pu" is removed from the vocabulary: the best remaining split falls back to single characters, p + u + g, with probability $0.02 \times 0.03 \times 0.05 = 0.00003$. That is a drop from 0.0050 to 0.00003, over 99% of the probability mass for this one word disappears. Add up that kind of drop across every word that used "pu" in its best split, and that total is the removal loss for "pu". It is large, so "pu" survives the pruning round. A token that barely changes any word's best-split probability when removed has a tiny loss and gets cut instead.

A token that is almost never used in any best split has a tiny removal loss and gets cut. Essential pieces survive. After training, each word has a preferred segmentation:

Word	Best split
hug	hu + g
pug	pu + g
pun	pu + n
bun	b + un
hugs	hug + s

BPE vs. Unigram in one line: BPE grows a vocabulary bottom-up by merging frequent pairs; Unigram shrinks a large vocabulary top-down by removing low-value tokens. BPE powers the GPT family; Unigram (via SentencePiece) powers T5, ALBERT, and many multilingual models.

---