Failed Star / fs

Learning 03 · learned once, replayed forever

Byte-pair encoding: two phases, one of them learning

Context: before building the M0 tokenizer · Status: understood

We kept saying BPE “keeps merging common adjacent pairs.” That phrase hides the single most important fact about tokenizers: there are two phases, and only one of them involves learning. The model creators learn the merges from a corpus; at M0 we only replay their frozen rules.

One-liner. Training learns merges by frequency over a corpus → frozen (vocab, merges). Inference replays those merges in rank order. Encoding does zero learning and zero counting — it is deterministic table lookup.
📖 Inference Engineering · §2.2 “LLM Inference Mechanics” (p.46) 🔧 ds4 · bpe_tokenize_text (~ds4.c:21140), str_i32_table vocab / merge-rank tables 🧭 Raschka · “Build a Large Language Model (From Scratch)” — clean BPE walkthrough

The whole idea

The two phases

Frequency-driven merging happens once, upstream, when the model is built. What ships with the model is two static artifacts — a vocab (token string → id) and an ordered merges list (the rules, in the order they were learned; order = frequency rank, and rank is everything). Our tokenizer never re-derives them.

Phase 1 — Training (done once, by the model creators — the “learned” part)

Unsupervised ML over a big corpus:

  1. Vocabulary starts as the 256 raw bytes.
  2. Scan the corpus, count every adjacent pair of symbols.
  3. Merge the single most frequent pair (say t+h) into a new symbol, give it the next free id, and append the rule ("t","h") → "th" to the ordered merges list.
  4. Repeat — re-count (the new symbol can now participate), merge the next most frequent pair — until the vocab hits a target size (Qwen3 ≈ 151,936).

Phase 2 — Encoding at inference (what we build at M0 — not learned)

Zero learning, zero frequency counting — just replay the frozen rules:

  1. Pre-split the text into coarse chunks with a fixed regex. Merges never cross a chunk boundary.
  2. Turn each chunk into per-byte symbols: encode as UTF-8 bytes, then map each byte through the byte↔unicode table.
  3. Repeatedly apply the adjacent pair whose merge rule has the lowest rank (earliest in the list = most frequent at training time).
  4. Stop when no adjacent pair appears in the merges list.

That is why ds4 stores a merge_rank hash table (ds4.c:20791): “given this pair, what is its rule rank?” — pure exact lookup, no counting. The learning already happened upstream.

A tiny replay trace — "low"

One chunk, printable ASCII, so its byte-level form is just low. Each pass applies the lowest-rank merge present (ranks are illustrative):

passsymbolscandidate pairs (rank)winner
1l o w(l,o)=5, (o,w)=2(o,w)
2l ow(l,ow)=rule(l,ow)
3lownone— stop
Rank, not position, decides. Pass 1 fires (o,w) — the pair in the middle — because rank 2 beats rank 5, even though (l,o) sat right at the front. Left-to-right greedy would be wrong; you must pick the global-minimum rank. (The M0 milestone pins the full hello → 14990 version of this as a test.)

The encoding question

What “raw bytes” means

“Split into raw bytes” hides an assumption: the input is UTF-8. There is no encoding-detection step. The pipeline treats the text as a UTF-8 byte sequence and walks it one byte (0–255) at a time — ds4's byte_encode (ds4.c:20914) iterates the input as raw uint8_t. In Rust this is free: a &str is always valid UTF-8, so .as_bytes() is already the right bytes.

UTF-8 is part of the contract with the model. Its merges were trained over UTF-8 bytes. Feed the same text as Latin-1 or UTF-16 and you get different bytes → different merges → wrong IDs. Not a free choice.

The nice consequence: a character is its UTF-8 bytes, not one symbol. é (U+00E9) enters BPE as 2 bytes, 中 as 3, an emoji as 4. Because all 256 byte values are in the base vocab, anything is representable — no out-of-vocabulary case, no UNK token. That is the whole reason byte-level BPE exists.

One subtlety: you do not merge over raw 0x00–0xFF directly. Each byte is first remapped to a printable codepoint via the GPT-2 byte↔unicode table (gpt2_byte_to_codepoint, ds4.c:20896): printable ASCII/Latin-1 stay as-is; the ~68 awkward bytes (control chars, space, newline) map to codepoints from 256 up — which is why a space shows as Ġ in vocab dumps. Each remapped codepoint still stands for exactly one original byte; it just keeps the merge symbols printable and whitespace-free.

A guard rail, not the algorithm

The pre-tokenization regex — yes, really a regex

Before BPE runs, the text is split into coarse chunks by a single fixed regex. The classic GPT-2 pattern:

's|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+

Read it as: contractions · optional-space + letters · optional-space + digits · optional-space + punctuation · whitespace. So " hello world!" pre-splits into [" hello", " world", "!"]. Qwen uses a more elaborate cl100k/GPT-4-style variant, same idea.

The regex is not the tokenizer. It only pre-splits so the learned merge loop has clean boundaries — merges never cross a chunk. Without it, BPE would learn merges across word/space/punctuation boundaries ("dog.", "the quick"), wasting vocab and making segmentation wildly context-dependent.

Where the regex comes from depends on the model's format — and either way it is part of the model's definition, not something we invent:

Isn't this just how a compiler tokenizes?

Largely yes — lexical analysis is the textbook use of regular expressions (lex/flex compile regexes to a DFA). But the parallel breaks in ways worth holding onto:

Compiler lexerLLM BPE tokenizer
Rules arehand-designed in the language speclearned from a corpus by frequency
A token isa grammatical category (IDENT, IF, +) — dozensa statistical fragment (" dog", "tion") — ~150k
The regexis the whole tokenizeronly pre-splits; a learned merge loop does the real work
Greedy rulelongest-match + rule priorityapply the lowest-rank merge

Deeper: a lexer is lossless and meaningful (every token is one lexical unit the parser depends on; there is a right answer). BPE segmentation is arbitrary — the same word tokenizes differently with a leading space, and the model is fine because it trained on that messiness. Fancier schemes exist (Unigram/SentencePiece uses Viterbi; WordPiece uses greedy longest-match; ByT5 drops tokenization entirely). BPE's greedy-merge is one of the simpler methods; the regex pre-tokenizer is widely seen as an inelegant-but-necessary wart.

Correct is relative to one model

Making our tokenizer match a specific model

A tokenizer is correct only relative to one model's vocab + merges. “Implementing BPE” is not enough — we must reproduce that model's exact rules and conventions. For our target (Qwen3, GPT-2-style byte-level BPE):

Exact-ID parity across a diverse set is the definition of “works with this model.” It proves the byte map, the regex, and the merge order are all right at once. Treat any single ID mismatch as a bug in one of the four conventions above, not a rounding detail.

Keep this

Mental model & the M0 shape

Training = learn merges by frequency over a corpus → frozen (vocab, merges). Inference = replay merges in rank order, deterministic, no learning. Correct = byte-for-byte ID parity with the model's own official tokenizer.

For M0 (Rust):