Chapter 28 — How BPE builds a vocabulary (by hand)

BPE (Byte-Pair Encoding) is the algorithm behind GPT, Llama, and most other models. It is genuinely simple: repeatedly merge the most frequent adjacent pair.

The training algorithm

1. Split your training text into words. Write each word as a list of characters,
   with a marker for the end of the word.
2. Count every adjacent pair of symbols across the whole corpus.
3. Merge the most frequent pair into one new symbol.
4. Repeat steps 2-3 until you have as many merges as you want.
5. SAVE THE ORDERED LIST OF MERGES. That list IS the tokenizer.

"low"     x5     ->   l o w </w>
"lower"   x2     ->   l o w e r </w>
"newest"  x6     ->   n e w e s t </w>
"widest"  x3     ->   w i d e s t </w>

(l,o)  = 5+2 = 7          (n,e)   = 6
(o,w)  = 5+2 = 7          (e,w)   = 6
(w,</w>) = 5              (w,e)   = 2+6 = 8
(e,r)  = 2                (e,s)   = 6+3 = 9   <-- tied winner
(r,</w>) = 2              (s,t)   = 6+3 = 9   <-- tied
                          (t,</w>) = 6+3 = 9  <-- tied
(w,i)  = 3   (i,d) = 3    (d,e)   = 3

l o w </w>        x5
l o w e r </w>    x2
n e w es t </w>   x6        <- "e s" became "es"
w i d es t </w>   x3

(es,t) = 6+3 = 9   <-- winner
(t,</w>) = 9
(l,o) = 7, (o,w) = 7, ...

l o w </w>       x5
l o w e r </w>   x2
n e w est </w>   x6
w i d est </w>   x3

1. e + s      -> es
2. es + t     -> est
3. est + </w> -> est</w>
4. l + o      -> lo
5. lo + w     -> low

Using it on new text (encoding)

Apply the merges in the order they were learned:

Encode "lowest":
  start:   l o w e s t
  merge 1 (e+s):    l o w es t
  merge 2 (es+t):   l o w est
  merge 4 (l+o):    lo w est
  merge 5 (lo+w):   low est
  no more merges apply
  RESULT: ["low", "est"]     -> 2 tokens

Encode "newest":
  start:  n e w e s t
  merge 1: n e w es t
  merge 2: n e w est
  (merges 4,5 don't apply -- no "lo")
  RESULT: ["n", "e", "w", "est"]   -> 4 tokens

Notice: "lowest" costs 2 tokens (it's made of frequent pieces), "newest" costs 4. Frequency in the training corpus determines cost. That's the whole economics of tokenization.

The variants you'll see named

They differ in details; the mental model — build a vocabulary of frequent pieces — is the same for all.

from collections import Counter

def get_pair_counts(words):
    """words: dict of tuple-of-symbols -> count"""
    pairs = Counter()
    for word, freq in words.items():
        for a, b in zip(word, word[1:]):
            pairs[(a, b)] += freq
    return pairs

def merge_pair(words, pair):
    new_words = {}
    a, b = pair
    for word, freq in words.items():
        out, i = [], 0
        while i < len(word):
            if i < len(word) - 1 and word[i] == a and word[i+1] == b:
                out.append(a + b)
                i += 2
            else:
                out.append(word[i])
                i += 1
        new_words[tuple(out)] = freq
    return new_words

# the corpus from the worked example
words = {
    tuple("low") + ("</w>",):     5,
    tuple("lower") + ("</w>",):   2,
    tuple("newest") + ("</w>",):  6,
    tuple("widest") + ("</w>",):  3,
}

merges = []
for step in range(10):
    pairs = get_pair_counts(words)
    if not pairs:
        break
    best = max(pairs, key=pairs.get)
    print(f"step {step+1}: merge {best} (seen {pairs[best]} times)")
    merges.append(best)
    words = merge_pair(words, best)
    for w in words:
        print("      ", " ".join(w))
    print()

print("learned merges:", merges)

Train a real tokenizer

from tokenizers import Tokenizer, models, trainers, pre_tokenizers, decoders

tok = Tokenizer(models.BPE())
tok.pre_tokenizer = pre_tokenizers.ByteLevel(add_prefix_space=True)
tok.decoder = decoders.ByteLevel()

trainer = trainers.BpeTrainer(
    vocab_size=2000,
    special_tokens=["<|endoftext|>", "<|pad|>"],
    initial_alphabet=pre_tokenizers.ByteLevel.alphabet(),
)
tok.train(["input.txt"], trainer)       # the Shakespeare file from Chapter 26

out = tok.encode("To be or not to be, that is the question")
print(out.tokens)
print(len(out.ids), "tokens")

Compare the token count against tiktoken on the same sentence. A small vocabulary trained on one book will need more tokens than a 100k vocabulary trained on the internet.