Build a BPE tokenizer

Arjun was reconciling the monthly API bill when a pattern jumped out. Crumb’s WhatsApp ordering line handles messages in English, Hindi and Marathi. He pulled two orders from the logs, both from the same regular customer, saying roughly the same thing:

• “One eggless mawa cake for Saturday, please.”
• The same order, typed in Hindi.

The API’s usage report said the English message was 10 tokens. The Hindi one was 31.

“Are they charging extra for Hindi?” he asked Priya. “That’s three times the price for the same order.”

“The price per token is identical,” Priya said. “The question is how many tokens your text turns into, and that is decided by the tokenizer, before the model sees a thing. Most LLMs use a method called byte-pair encoding. Build one today, in plain Python, about 60 lines, and you’ll see exactly where your Hindi tokens go.”

Why not split on words?

A token is the unit of text a model reads: sometimes a whole word, sometimes part of one, sometimes a single byte. A tokenizer converts text into a list of token ids (whole numbers) and back. Its vocabulary is the full list of tokens it knows. You met tokens in Module 01; today you see how the vocabulary gets chosen.

Arjun’s first instinct was the obvious one. “Why not one token per word?”

“How many words are there?” Priya asked. “Include mawa, ghevar, every customer’s misspelling of eggless, every order number, every emoji, in every language.”

“Millions.”

“And each token needs its own row of numbers in the model’s embedding table. GPT-2’s 50,257 tokens with 768 numbers each is already about 38.6 million parameters before the model does anything. And the day a customer types a word you’ve never seen, what’s its id?”

“Unknown. Fine, then one token per character.”

“Then ‘eggless chocolate cake’ is 22 tokens instead of 3. Remember the attention lesson: the work grows with the square of the length. Triple the tokens, roughly nine times the attention work.”

Priya drew Crumb’s kitchen order board. “How do your bakers write orders up there?”

“Shorthand. ‘ELC’ for eggless chocolate cake. ‘PC’ for plum cake. Everything rare gets written out in full.”

“Exactly. Common things earn an abbreviation; rare things get spelled out letter by letter. That is BPE. It is a compromise between words and characters, learned from data.”

What you are building

Byte-pair encoding (BPE) began as a 1994 data-compression trick and was adapted for language models in 2016. GPT-2 used a byte-level version with a vocabulary of about 50,000 tokens. You will build the same algorithm at toy scale, in three parts:

• Train: learn an ordered list of merge rules from some text.
• Encode: turn new text into token ids by replaying those merges.
• Decode: turn token ids back into text.

No libraries needed. Create a file bpe.py, add each step’s code to the end of it, and run it with uv run bpe.py (or python bpe.py) after each step.

Step 1: Turn text into bytes

Computers store text as bytes: whole numbers from 0 to 255. The UTF-8 standard (the near-universal way of storing text) uses one byte for each plain English letter and two to four bytes for other characters. A Devanagari letter takes 3 bytes; an emoji usually takes 4.

Starting from bytes gives BPE a superpower: a base vocabulary of only 256 tokens that can represent any text in any language. Nothing is ever “unknown”.

# Step 1: the corpus, a few of Crumb's support replies
corpus = """
Your eggless chocolate cake is out for delivery.
Your plum cake is out for delivery and will reach you soon.
Sorry, your delivery is late. Your eggless cake will reach you by 6 pm.
Our eggless cakes are baked in a separate kitchen.
Your refund for the late delivery is on its way.
""".strip()

text_bytes = list(corpus.encode("utf-8"))
print(len(corpus), "characters ->", len(text_bytes), "bytes")
print(text_bytes[:12])

.encode("utf-8") turns the string into bytes; list(...) turns those bytes into a list of ordinary numbers.

You should now see 280 characters -> 280 bytes and a list starting [89, 111, 117, 114, 32, ...]. Those are the bytes for Y, o, u, r and a space. English text is one byte per character. Hold on to that 280: it is the “no compression” baseline.

Step 2: Count neighbouring pairs

BPE asks only one question, over and over: which two tokens sit next to each other most often?

# Step 2: count neighbouring pairs
def get_pair_counts(ids):
    """Count how often each neighbouring pair of ids appears."""
    counts = {}
    for pair in zip(ids, ids[1:]):
        counts[pair] = counts.get(pair, 0) + 1
    return counts

counts = get_pair_counts(text_bytes)
top = max(counts, key=counts.get)
print("Most common pair:", top, "=", repr(bytes(top).decode()), "seen", counts[top], "times")

zip(ids, ids[1:]) walks the list two at a time: (1st, 2nd), (2nd, 3rd), and so on. max(counts, key=counts.get) returns the pair with the biggest count.

Arjun guessed the winner would be e followed by a space, since English loves words ending in e. You should now see Most common pair: (111, 117) = 'ou' seen 9 times. Your, our, out and you all contain it. Crumb’s replies are very second-person.

Step 3: Merge one pair everywhere

Now replace every occurrence of that pair with a single new id. New ids start at 256, because 0 to 255 are taken by the raw bytes.

# Step 3: merge one pair everywhere
def merge(ids, pair, new_id):
    """Replace every occurrence of `pair` in `ids` with `new_id`."""
    out = []
    i = 0
    while i < len(ids):
        if i < len(ids) - 1 and (ids[i], ids[i + 1]) == pair:
            out.append(new_id)   # found the pair: emit one new token
            i += 2               # and skip both halves
        else:
            out.append(ids[i])
            i += 1
    return out

print(merge([5, 6, 6, 7, 9, 1], (6, 7), 99))

The loop walks left to right. Whenever the current item and the next one form the pair, it writes the new id and jumps two places; otherwise it copies one item and moves on.

You should now see [5, 6, 99, 9, 1]. Only the 6, 7 pair was replaced; the lone 6 before it was left alone.

Step 4: The training loop

Training is Steps 2 and 3 on repeat. Each round: find the most common pair, merge it, record the rule. Stop when the vocabulary reaches the size you asked for.

# Step 4: the training loop
def train(text, vocab_size):
    """Learn (vocab_size - 256) merges from `text`."""
    ids = list(text.encode("utf-8"))
    merges = {}                                   # (id_a, id_b) -> new_id, in learning order
    vocab = {i: bytes([i]) for i in range(256)}   # id -> the bytes it stands for
    for new_id in range(256, vocab_size):
        counts = get_pair_counts(ids)
        if not counts:
            break
        pair = max(counts, key=counts.get)
        ids = merge(ids, pair, new_id)
        merges[pair] = new_id
        vocab[new_id] = vocab[pair[0]] + vocab[pair[1]]    # the new token's bytes
        print(f"merge {new_id - 255:2}: {vocab[pair[0]]!r} + {vocab[pair[1]]!r} -> {vocab[new_id]!r}")
    return merges, vocab

merges, vocab = train(corpus, vocab_size=256 + 30)

Two dictionaries come out. merges is the rule book, and Python dictionaries remember insertion order, so it also records when each rule was learned. vocab maps every id to the bytes it stands for, built by joining the bytes of the two parts.

You should now see 30 merges scroll by. The early ones are tiny: b'o' + b'u' -> b'ou', then b'r' + b' ' -> b'r '. Then whole words assemble themselves, a letter at a time:

merge 13: b'd' + b'e' -> b'de'
merge 14: b'de' + b'l' -> b'del'
...
merge 18: b'delive' + b'ry' -> b'delivery'
...
merge 25: b'eggles' + b's ' -> b'eggless '

Arjun leaned back. “Nobody told it delivery was a word.”

“It found it because your replies say delivery in four of five sentences,” said Priya. “That is the whole idea. The vocabulary is a fingerprint of what the training text talks about most.”

Step 5: Decode

Decoding is the easy direction: look up the bytes for each id, join them, turn the bytes back into text. Arjun wrote it the way that seemed natural, decoding each token as he went:

# Arjun's first decode
def decode_naive(ids):
    return "".join(vocab[i].decode("utf-8") for i in ids)

print(decode_naive([256 + 7, 256 + 24, 256 + 26]))

It printed Your eggless cake . Ids 263, 280 and 282 are merges 8, 25 and 27. So far so good. Then he tried Hindi:

print(decode_naive(list("मावा".encode("utf-8"))))

UnicodeDecodeError: 'utf-8' codec can't decode byte 0xe0 in position 0: unexpected end of data

“Each Devanagari letter is three bytes,” Priya said. “Your tokens here are single bytes. Byte 0xe0 on its own is the first third of a letter, which isn’t valid text. You can’t decode a third of a character.”

The fix is to join all the bytes first, then decode once:

# Step 5: decode
def decode(ids):
    """Turn token ids back into text."""
    raw = b"".join(vocab[i] for i in ids)            # glue every token's bytes together
    return raw.decode("utf-8", errors="replace")     # then turn bytes into text, once

print(decode([256 + 7, 256 + 24, 256 + 26]))
print(decode(list("मावा".encode("utf-8"))))

You should now see Your eggless cake and then मावा. The errors="replace" is a safety net: if a sequence of ids genuinely ends half-way through a character (a model can generate that), Python shows a replacement symbol instead of crashing.

Step 6: Encode

Encoding new text means replaying the merges. Arjun reused the logic from training: find the most frequent pair, merge it, repeat.

# Arjun's first encode
def encode_naive(text):
    ids = list(text.encode("utf-8"))
    while len(ids) >= 2:
        counts = get_pair_counts(ids)
        pair = max(counts, key=counts.get)
        ids = merge(ids, pair, merges[pair])
    return ids

print(encode_naive("Your cake is late."))

KeyError: (89, 111)

Pair (89, 111) is Yo. In this short sentence every pair appears once, so max picked the first one, and Yo was never learned as a merge. Frequency in the new text is the wrong question.

“Think about merge 14,” Priya said. “de + l. Could you ever apply it before merge 13?”

“No. Merge 13 is what creates de.” He saw it. “So I have to replay merges in the order they were learned. At each step, out of the pairs in my text, apply the one that was learned earliest.”

# Step 6: encode
def encode(text):
    """Turn text into token ids by replaying the learned merges, earliest first."""
    ids = list(text.encode("utf-8"))
    while len(ids) >= 2:
        counts = get_pair_counts(ids)
        # Earliest-learned pair has the lowest new id. Unknown pairs rank as infinity.
        pair = min(counts, key=lambda p: merges.get(p, float("inf")))
        if pair not in merges:
            break                     # no known merge applies any more: done
        ids = merge(ids, pair, merges[pair])
    return ids

msg = "Your eggless cake is out for delivery."
ids = encode(msg)
print(len(msg.encode("utf-8")), "bytes ->", len(ids), "tokens")
print([vocab[i].decode("utf-8", errors="replace") for i in ids])

merges.get(p, float("inf")) gives each pair its merge id, or infinity if it was never learned, so min picks the earliest known merge. When even the best candidate is unknown, nothing more can be merged.

You should now see 38 bytes -> 9 tokens and the pieces:

['Your ', 'eggless ', 'cake ', 'is ', 'ou', 't', ' for ', 'delivery', '.']

Notice out is still two pieces. That merge would have come after merge 30, and we stopped training there.

Step 7: Test round trips and compare languages

A tokenizer has one sacred rule: decode(encode(text)) == text for every text. Test it, and measure how many tokens different messages need.

# Step 7: round trips and token counts
for s in [msg, "Your cake is late.", "Ghevar for Diwali", "मावा केक 🎂"]:
    ids = encode(s)
    assert decode(ids) == s, f"round trip failed for {s!r}"
    print(f"{s!r}: {len(s.encode('utf-8'))} bytes -> {len(ids)} tokens")

You should now see no assertion errors, and:

'Your eggless cake is out for delivery.': 38 bytes -> 9 tokens
'Your cake is late.': 18 bytes -> 6 tokens
'Ghevar for Diwali': 17 bytes -> 15 tokens
'मावा केक 🎂': 27 bytes -> 27 tokens

There is Arjun’s bill, in miniature. Define the compression ratio as:

$$\text{compression}=\frac{\text{bytes in}}{\text{tokens out}}$$

The Crumb-style English reply compresses at $38/9\approx 4.2$ bytes per token. “Ghevar” never appeared in training, so it barely compresses: $17/15\approx 1.1$. The Hindi text is 10 characters (counting spaces) but 27 bytes, because each of its 7 Devanagari letters takes 3 bytes and the emoji takes 4. With no Hindi in the training text, not one merge applies: $27/27=1$. Every byte is its own token.

Real tokenizers train on far more varied text, so the gap is smaller than in this toy, but it is real. Text in languages that were rare in a tokenizer’s training data usually needs noticeably more tokens. That means a higher bill, slower replies, and less room in the context window (the maximum amount of text a model can read at once).

What happened next

Arjun went back to the real logs with a different question: not “which model is cheapest per token?” but “how many tokens does each model’s tokenizer produce for our messages?” He took 200 real WhatsApp orders and counted tokens with the tokenizers of the three models on his shortlist. For the English orders, all three were within 10% of each other. For the Hindi and Marathi orders, the best tokenizer produced about 40% fewer tokens than the worst. On Crumb’s message mix, that difference mattered more than a small gap in the per-token price.

“So the cheapest model on the pricing page,” he told Meera, “isn’t the cheapest for us.”

Common mistakes

• Encoding by frequency instead of merge order. Frequency is for training only. Encoding must replay merges earliest first, or it crashes (as Arjun’s did) or builds tokens out of order.
• Decoding token by token with strict UTF-8. A token can hold part of a character. Join all the bytes first, then decode, with errors="replace".
• Training on too little text. Our 30 merges memorised Crumb’s favourite words. A real tokenizer learns tens of thousands of merges from gigabytes of mixed text.
• Letting merges cross spaces. Our merges include 'r ' and ' for ', mixing word endings with spaces. GPT-style tokenizers first split text into word-like chunks with a regular expression, then run BPE inside each chunk.
• Comparing models on price per token alone. Token counts for the same text differ between tokenizers, especially outside English. Measure on your own data.

Recap

• BPE starts from 256 byte tokens, so it can represent any text with no unknown tokens.
• Training repeatedly merges the most common neighbouring pair and records the order of the merges.
• Encoding replays merges in learned order; decoding joins all the bytes, then converts to text once.
• Frequent strings in the training text become single tokens; rare text stays fragmented into bytes.
• Token counts drive cost, speed and context usage, and they vary a lot by language and by tokenizer.

Meera read Arjun’s comparison and asked the question he had hoped she wouldn’t: “Could we make a model that’s good at our Hindi and our menu? Not only pick the least bad one?”

“You can fine-tune a model to talk like Crumb,” Priya said. “The tokenizer usually stays as it is. But before any of that, there’s a stranger corner of AI to visit first: models that don’t predict the next word at all, but invent whole new images. That’s the next module.”

Stretch goals

• Pre-split the text with a regular expression such as re.findall(r" ?\w+|[^\w\s]+|\s+", text) and run BPE inside each chunk, so merges never cross word boundaries.
• Save merges to a JSON file and load it back, so you train once and encode many times.
• Train on a mix of English and Hindi messages and watch Devanagari merges appear. How much does the Hindi compression ratio improve?
• Compare with a real tokenizer: uv add tiktoken, then len(tiktoken.get_encoding("cl100k_base").encode(text)) for each test string.

Go deeper

• Hugging Face LLM course, which has a chapter on tokenizers including BPE.
• Hugging Face docs, see the Tokenizers library.