Every modern LLM tokenizer (GPT's, Llama's, essentially all of them) is trained with byte-pair encoding: start with individual characters, and repeatedly merge whichever ADJACENT pair of symbols is currently most frequent across the whole training corpus into one new symbol. Do this thousands of times on a huge corpus and you get a vocabulary where common whole words survive as single tokens and rare words get split into meaningful, reusable pieces.

Each word starts as a tuple of its characters plus an end-of-word marker "</w>" (this stops merges from crossing word boundaries). word_freqs is {word: count}.

get_word_symbols is done for you. Implement:

• count_pairs(vocab) -- vocab maps a tuple-of-symbols to its frequency; return a dict mapping every adjacent (symbol_a, symbol_b) pair to its total frequency across the whole vocab.
• merge_vocab(pair, vocab) -- return a NEW vocab where every adjacent occurrence of pair in each symbol tuple has been merged into one combined symbol (symbol_a + symbol_b).
• train_bpe(word_freqs, num_merges) -- run num_merges rounds: count pairs, pick the best one, merge it, repeat. Return the list of merges performed, in order.

Tie-breaking: when multiple pairs are equally frequent, pick the lexicographically LARGEST pair tuple (max(pairs, key=lambda p: (pairs[p], p)) is exactly this). This makes the result deterministic. Stop early (fewer than num_merges results) if no pairs remain to merge.

The missing link: training a vocabulary isn't the same as using one

train_bpe only ever runs ONCE, offline, over a huge corpus, to produce the ordered merges list. That list is only half the tokenizer -- the other half is apply_bpe(word, merges): given an arbitrary word the model has never seen before, tokenize it using the LEARNED merges, greedily and in the order they were learned. This is the function that actually runs, over and over, every time text goes into or comes out of the model.

Implement apply_bpe(word, merges): start from get_word_symbols(word) (individual characters + </w>). Repeatedly find whichever adjacent pair in the current symbol list has the EARLIEST index in merges (lower index = learned first = higher priority) and merge every occurrence of that exact pair. Stop when no adjacent pair in the word appears in merges at all -- that's the final tokenization. A pair that was never learned (or that's only reachable via merges you haven't done yet) never gets merged, even if it looks obviously mergeable.

Example

train_bpe({"aa": 5, "ab": 1}, num_merges=1)  # -> [("a", "a")]

"aa" (freq 5) contributes pairs ('a','a') and ('a','</w>'), each with total count 5 -- a tie, broken in favor of ('a','a') since it's the larger tuple.

apply_bpe("abc", merges=[("a", "b"), ("ab", "c")])  # -> ["abc", "</w>"]

('a','b') was learned first (index 0), so it merges before ('ab','c') (index 1) even gets a chance -- merge PRIORITY order, not just "any merge that happens to apply."

Real-world grounding

• How llama.cpp/GGML tokenizers apply a trained BPE vocabulary: ggml-org/llama.cpp
• transformers' tokenizer implementations (the training side of BPE lives in the tokenizers Rust library it wraps, but the algorithm is exactly this): huggingface/transformers

Real BPE training runs this same loop tens of thousands of times over gigabytes of text -- the algorithm doesn't change, just the scale.