S02The Model·232 lines

Tokenization

The model never sees text. A BPE tokenizer compresses bytes into a fixed vocabulary, and every latency number you quote is measured per token rather than per character.

BPE
merges
byte fallback
vocabulary
streaming detokenization

Motivation

The problem

In S01 we wrote tokenizer.encode(prompt) and moved on. That single call decides three things an engine cannot change later: how much the request costs, how many forward passes it needs, and whether the output stream is even valid text.

The obvious approaches both fail. Character-level vocabularies are tiny, but they make sequences four to five times longer, and decode is one forward pass per token: that is a 4–5× slowdown. Word-level vocabularies keep sequences short but cannot represent a word they have never seen, and there is no such thing as a closed set of words.

Byte-pair encoding threads the needle. Start from raw bytes, so nothing is ever unrepresentable, then repeatedly merge the most frequent adjacent pair into a new symbol until the vocabulary reaches the size you wanted.

Core idea

The solution

Training is a loop over pair frequencies. Encoding is a loop over merge ranks. Both are about twenty lines.

bpe, the whole ideapython

def train(corpus, num_merges):
    words = {w: list(w) for w in corpus.split()}
    merges = []

    for rank in range(num_merges):
        pairs = Counter()
        for word, parts in words.items():
            for a, b in zip(parts, parts[1:]):
                pairs[(a, b)] += corpus_freq[word]

        if not pairs:
            break
        best = max(pairs, key=pairs.get)   # most frequent adjacent pair
        merges.append(best)
        words = {w: apply(best, p) for w, p in words.items()}

    return merges

Encoding applies merges by rank, not position

The single most common bug in a hand-written BPE is scanning left-to-right and merging whatever fits. Correct BPE finds the lowest-ranked applicable merge anywhere in the word, applies it everywhere, and repeats. Get this wrong and your token IDs silently disagree with the model's training distribution. Output quality degrades without a single error message.

Mechanics

How it works

Diagrambyte-pair encoding, end to end

Left: encoding is a ladder of merges. Right: decoding is not the inverse. A token is a byte string, and bytes must be buffered until they form valid UTF-8.

Streaming detokenization is where engines break

Encoding runs once. Decoding runs on every generated token, in a stream, and it has a nasty property: tokens are byte sequences, and a single character can straddle a token boundary. A naive server that calls decode([token]) per token and pushes the result down an SSE connection will emit replacement characters whenever a glyph's UTF-8 bytes are split across tokens. The happy path hides this, because modern vocabularies encode common emoji and CJK as single tokens. Less-common glyphs and byte-fallback cases split routinely, and one split is all it takes.

the incremental decoderpython

class StreamDecoder:
    """Emits text only when the pending bytes are valid UTF-8."""

    def __init__(self, tokenizer):
        self.tok = tokenizer
        self.pending = b""

    def push(self, token_id: int) -> str:
        self.pending += self.tok.id_to_bytes(token_id)
        try:
            text = self.pending.decode("utf-8")
        except UnicodeDecodeError:
            return ""          # incomplete glyph — wait for more bytes
        self.pending = b""
        return text

Real engines go further, because stop strings and tool-call delimiters are defined over text but detected during a token stream. vLLM keeps a small sliding window of already-emitted text and re-runs the stop-string check over the window each step, so a stop sequence split across three tokens is still caught.

Why your token counts never match

chars/token, English: ~4.0; the number every capacity estimate assumes
chars/token, CJK: ~1.5; ~2.7× more tokens per character than English
chars/token, code: ~2.8; indentation and punctuation fragment badly

Explore

Try it

This trains a real BPE in your browser on a small corpus, then replays the merges one at a time. Watch what happens to batching as you drag the merge count: at zero merges it is nine tokens, at sixty it is two or three.

Simulatorbyte-pair encodingdrag the merge count, then replay

sample text

merges learned60

or type your own

tokenized · 29 tokens

␣the␣cats␣are␣sitting␣on␣mats

Every token is a billing unit and one full forward pass during decode. Compression ratio is why English costs less per word than Japanese on the same model.

characters: 23
tokens: 29
chars / token: 0.79
vocab size: 86

merge replay · word "␣the"

␣the

merge 0 / 0

Starting point: the word split into single characters. Nothing has merged yet. A vocabulary with zero merges produces exactly this.

merge table (first 12 of 60)

#0 ␣+t#1 h+e#2 a+t#3 e+n#4 ␣t+o#5 e+r#6 ␣t+he#7 i+n#8 ␣to+k#9 ␣tok+en#10 o+n#11 ␣+c

Try the out-of-domain sample. Words the corpus never saw break down into single characters and short fragments. The same thing happens when you feed a model trained mostly on English a prompt in Thai, and it is why the same message costs three times as much.

Build it

Implementation

The encode path is the hot one, and the naive version is O(n²) per word because it rescans for the best pair after every merge. Short words make that harmless. Production tokenizers escape it in two different ways: tiktoken keeps the linear min-rank rescan, worst-case quadratic, and relies on its regex pre-split to keep every piece a handful of bytes so the worst case never bites. HuggingFace's Rust tokenizers use a linked list plus a priority queue to get O(n log n).

code/s02_tokenizer.py (excerpt)python

def encode_word(self, word: str) -> list[str]:
    parts = list(word)

    while len(parts) > 1:
        # find the applicable merge with the LOWEST rank
        best_rank, best_i = None, None
        for i in range(len(parts) - 1):
            rank = self.ranks.get((parts[i], parts[i + 1]))
            if rank is not None and (best_rank is None or rank < best_rank):
                best_rank, best_i = rank, i

        if best_i is None:
            break                      # no merge applies — done

        a, b = parts[best_i], parts[best_i + 1]
        parts = merge_all(parts, a, b)  # apply it everywhere, not once

    return parts

The special-token trap

Chat models wrap turns in special tokens like <|im_start|>. These must be matched before BPE runs, and user text must never be allowed to produce them; otherwise a user types the delimiter and impersonates the system role. Every production tokenizer has an allowed_special parameter for this reason, and defaulting it open is a prompt-injection vulnerability.

Run it locally

Trains a byte-level BPE on a small corpus, encodes and round-trips several strings including emoji and CJK, and demonstrates the streaming decoder buffering a multi-byte glyph across two tokens.

$ python code/s02_tokenizer.py

Expect: A merge table, per-sample token counts with chars/token ratios, an assertion that decode(encode(x)) == x for every sample, and a streaming trace showing empty emissions until a glyph completes.

Only NumPy is required — setup instructions.

Production notes

In production

tiktoken (OpenAI) — byte-level BPE with a regex pre-split that forces token boundaries at word starts, contractions and digit runs. The pre-split is why numbers tokenize consistently.
SentencePiece (Llama 1–2, Gemma) — trains directly on raw text with no pre-tokenization, treating space as the symbol ▁. Supports a unigram-LM mode that is not BPE at all. Llama 3 dropped it for a tiktoken-style byte-level BPE with a 128k vocabulary, so its token counts differ from Llama 2's on identical text.
picoLM / llama.cpp — read merges straight out of GGUF metadata in ~200 lines of C, with no Python and no dependencies.
vLLM — delegates to HuggingFace tokenizers but owns the incremental detokenizer, because the streaming and stop-string logic is engine-specific.

Exercises

1
Implement decode and assert decode(encode(s)) == s over a few hundred random unicode strings. Byte-level BPE should round-trip perfectly; if yours does not, you are losing information in the space handling.
2
Replace the O(n²) scan with a priority queue over adjacent pairs. Measure the speedup on a 10,000-character document.
3
Add special-token handling with an explicit allow-list, then write the test that proves user text containing <|im_start|> encodes as literal characters rather than the control token.

Continue

What's next

Token IDs go in and text comes out. The thing in the middle, model.forward(ids), is still a black box. S03 opens it: RMSNorm, rotary embeddings, grouped-query attention and SwiGLU, written in NumPy and small enough to read in one sitting.

Check yourself

Questions

Answer before you look. A wrong answer tells you more than a right one, because the explanation points at the part of the chapter to reread.

Check yourselfQuestion 1 of 6

When encoding a word, which merge should be applied first?

Score 0/6