Before a transformer sees a single weight update, your text is already gone. Not metaphorically — literally converted into a list of integers. I used to treat tokenization as plumbing you import from tiktoken and forget. Then I started building AL-1, a GPT in pure NumPy, and realized the tokenizer is half the data pipeline. Get BPE wrong and your model trains on garbage IDs; get it right and suddenly def foo(): compresses to a handful of tokens instead of twelve unrelated bytes.
Byte Pair Encoding is the algorithm behind GPT-2, GPT-3, LLaMA, and most modern LLM vocabularies. This post is one continuous walkthrough: why character-level and word-level tokenization fail, how byte-level BPE fixes both, the math of merge selection with every count written out, a complete training example on the tiny corpus "low low lower lowest" from pretokenization through four merges to final encodings, inference-time encoding step by step, decoding, and the Python I’m using in zyn/bpe.py. Same pipeline as numerical gradient checking for autograd — own the data path before you trust the model.
flowchart LR
TXT["Raw text\n'def hello():'"] --> PRE["Pretokenize\nregex splits"]
PRE --> BYTES["Bytes per pretoken\n[100, 101, 102, ...]"]
BYTES --> MERGE["Apply learned merges\nrank-ordered"]
MERGE --> IDS["Token IDs\n[412, 891, 37]"]
IDS --> EMB["Embedding lookup\nin the transformer"]
Why can’t the model just read characters?
You could map each Unicode character to an integer. Shakespeare at ~1 MB becomes ~1M tokens. A 1024 context window holds roughly one screen of text. Training becomes painfully slow because every forward pass processes far more positions than necessary.
Word-level tokenization has the opposite problem. The vocabulary explodes — every typo, hashtag, and async def variant is a new symbol you’ve never seen. Out-of-vocabulary (OOV) words become <UNK> and the model loses information.
BPE sits in the middle. Start with a small base vocabulary (256 raw bytes), then learn the most frequent pairs and merge them into new symbols. Common fragments like ` the, ing, def, ()` get their own IDs. Rare strings still tokenize — they just fall back to bytes. No OOV dead ends.
What is byte pair encoding?
BPE is a compression algorithm adapted for NLP. The training loop is brutally simple:
- Split corpus into pretokens (word-like chunks).
- Represent each pretoken as a sequence of byte IDs.
- Count every adjacent pair $(a, b)$ across all pretokens, weighted by word frequency.
- Merge the most frequent pair into a new token ID.
- Repeat until you hit your target vocabulary size.
At inference time you don’t recount anything. You greedily apply the merges you learned, in the order they were created (earliest merge = highest priority).
The original paper (Sennrich et al., 2016) operated on characters for neural machine translation. GPT-2 (Radford et al., 2019) went byte-level: each of the 256 UTF-8 bytes is a starting symbol. That single decision eliminates unknown Unicode — any string encodes to bytes, bytes decode back to UTF-8.
Why bytes, not characters?
UTF-8 is variable-width. The character é might be one code point but two bytes. Byte-level BPE sidesteps the entire Unicode normalization rabbit hole:
- Vocabulary floor is fixed: 256 bytes + a few special tokens. You always know the minimum size.
- No OOV:
🤖, Cyrillic, Zalgo text — all bytes, all representable. - Compression where it matters: Frequent English/code fragments merge into multi-byte tokens; rare emoji stay as 4 byte tokens.
Tradeoff: byte sequences are longer than character sequences for non-Latin scripts. For English + Python code (what I’m training on), it’s a good deal.
My implementation reserves 6 special tokens before the 256 bytes:
| ID | Token | Purpose |
|---|---|---|
| 0 | <pad> |
Batch padding |
| 1 | <bos> |
Beginning of sequence |
| 2 | <eos> |
End of sequence |
| 3–5 | <tool_call>, </tool_call>, <tool_result> |
Tool-calling fine-tune later |
So byte_base = 6, and raw byte $b$ maps to token ID $6 + b$.
For the letter l:
For ASCII space:
Minimum vocabulary size:
You cannot train with vocab_size < 262 — the code raises immediately.
What is pretokenization?
BPE doesn’t run on the raw string as one blob. First, a regex splits text into pretokens — chunks that look like words, numbers, or punctuation. GPT-2 uses this pattern (same in my code):
PAT = re.compile(
r"""'s|'t|'re|'ve|'m|'ll|'d| ?[^\W\d]+| ?\d+| ?[^\s\w]+|\s+(?!\S)|\s+"""
)
What it captures:
- Contractions:
're,'ve,'ll - Words with optional leading space: ` hello
,def` - Numbers: ` 42`
- Punctuation clusters:
(): - Whitespace runs
The leading-space convention matters. In English, a space before a word is semantically attached — GPT learns ` the as one token, not ` + the. That’s why "low" and " low" are different pretokens with different merge histories.
How does training pick the next merge?
For each pretoken $w$ with frequency $\text{freq}(w)$, maintain a sequence of byte IDs. Count adjacent pairs:
Pick the pair with maximum count:
If the count is below min_freq (default 2), stop early.
Assign the merged pair a new ID next_id, store merges[(a,b)] = next_id, and set:
where $\Vert$ is byte concatenation. Then replace every occurrence of the pair $(a,b)$ with next_id in all pretoken sequences. Increment next_id. Loop until next_id == vocab_size.
flowchart TD
A["Count all adjacent pairs\nweighted by pretoken freq"] --> B{"Best pair count\n≥ min_freq?"}
B -->|no| STOP["Stop training"]
B -->|yes| C["Assign new ID,\nstore merge rule"]
C --> D["Concat vocab bytes\nvocab[new] = vocab[a]+vocab[b]"]
D --> E["Replace pair everywhere\nin pretoken ID lists"]
E --> F{"next_id < vocab_size?"}
F -->|yes| A
F -->|no| STOP
Full worked example: "low low lower lowest"
I will train BPE on the corpus "low low lower lowest" with byte_base = 6, vocab_size = 280, and min_freq = 2. Every pretokenization step, byte conversion, pair count, merge, and final encoding is written on its own line. This is the same worked example GPT tutorials use — I’m using real token IDs from my implementation, not abstract letters.
Step 1 — Pretokenize the corpus
Input string:
The regex PAT.findall splits on word boundaries and keeps leading spaces attached:
Each distinct pretoken appears once in this tiny corpus:
Note: "low" and " low" are different strings because of the leading space on the second occurrence.
Step 2 — Convert each pretoken to byte token IDs
Token ID formula: $\text{id} = 6 + \text{byte}$.
Pretoken 'low' — bytes l, o, w:
Pretoken ' low' — bytes space, l, o, w:
Pretoken ' lower' — bytes space, l, o, w, e, r:
Pretoken ' lowest' — bytes space, l, o, w, e, s, t:
Step 3 — Count all adjacent pairs (before any merges)
Pair $(114, 117)$ — the bytes lo — appears in all four pretokens:
Pair $(117, 125)$ — the bytes ow — same four pretokens:
Pair $(38, 114)$ — space followed by l:
Pair $(125, 107)$ — we — only in ` lower and lowest`:
All other pairs have count $1$. The maximum is $4$. Ties go to whichever pair the Counter returns first — here $(114, 117)$ wins.
Step 4 — Merge 1: $(114, 117) \rightarrow 262$
New token ID:
Vocabulary entry:
Replace $(114, 117)$ everywhere:
Step 5 — Count pairs after merge 1
Pair $(262, 125)$ — merged lo followed by w — in all four pretokens:
Pair $(38, 262)$ — space followed by merged lo:
Pair $(125, 107)$ — we:
Maximum count is $4$. Merge $(262, 125)$.
Step 6 — Merge 2: $(262, 125) \rightarrow 263$
Replace $(262, 125)$ everywhere:
The pretoken 'low' is now a single token.
Step 7 — Count pairs after merge 2
Pair $(38, 263)$ — space + low — in three pretokens ( low, ` lower, lowest`):
Pair $(263, 107)$ — low + e:
Maximum is $3$. Merge $(38, 263)$.
Step 8 — Merge 3: $(38, 263) \rightarrow 264$
Replace $(38, 263)$ everywhere:
Step 9 — Count pairs after merge 3
Pair $(264, 107)$ — ` low + e — in lower and lowest`:
This meets min_freq = 2. Merge it.
Step 10 — Merge 4: $(264, 107) \rightarrow 265$
Replace $(264, 107)$ everywhere:
Step 11 — Final encodings after training
| Pretoken | Token IDs | Decoded bytes |
|—|—|—|
| 'low' | [263] | low |
| ' low' | [264] | ` low |
| ’ lower’ | [265, 120] | low + e + r |
| ’ lowest’ | [265, 121, 122] | lowe + s + t` |
The shared prefix ` lowe merged once into token 265. The suffix r in lower and st in lowest` stay as individual byte tokens because they appeared only once. That is the compression story — common substrings collapse, rare suffixes don’t.
Merge rank table (encoding priority):
Step 12 — Encode 'lowest' at inference time
The string 'lowest' has no leading space, so it pretokenizes to a single chunk 'lowest' (not in our training corpus, but the learned merges still apply).
Convert to byte IDs:
Greedy merge pass 1 — scan adjacent pairs, pick lowest rank:
Best pair: $(114, 117)$ with rank $0$. Apply merge $\rightarrow 262$:
Greedy merge pass 2:
All other adjacent pairs have no merge rule. Apply merge $\rightarrow 263$:
Greedy merge pass 3 — no adjacent pair exists in merges. Stop.
Final encoding:
One merged low token plus three byte tokens for est.
With BOS/EOS:
t.encode("lowest", add_bos=True, add_eos=True)
# [1, 263, 107, 121, 122, 2]
Round-trip check:
How does decoding work?
Decoding is the easy direction. Each token ID maps to a byte string in vocab. Concatenate, decode UTF-8:
For our encoding $[263, 107, 121, 122]$:
Special tokens can be skipped with skip_specials=True so <bos> doesn’t appear in generated text.
The invariant I test before wiring the dataloader:
The implementation skeleton
The full tokenizer lives in ~160 lines. Four pieces do the real work.
Pretokenize and bytes:
def _pretokens(text: str) -> list[str]:
return PAT.findall(text)
def _word_to_ids(word: str, byte_base: int) -> list[int]:
return [byte_base + b for b in word.encode("utf-8")]
Merge a pair in a sequence (left-to-right, non-overlapping):
def _merge_seq(ids: list[int], pair: tuple[int, int], new_id: int) -> list[int]:
a, b = pair
out, i, n = [], 0, len(ids)
while i < n:
if i < n - 1 and ids[i] == a and ids[i + 1] == b:
out.append(new_id)
i += 2
else:
out.append(ids[i])
i += 1
return out
Training loop — count pairs, pick best, merge everywhere:
while next_id < vocab_size:
pair_counts = Counter()
for w, freq in word_freq.items():
for a, b in zip(word_ids[w], word_ids[w][1:]):
pair_counts[(a, b)] += freq
best, cnt = pair_counts.most_common(1)[0]
if cnt < min_freq:
break
self.merges[best] = next_id
self.vocab[next_id] = self.vocab[best[0]] + self.vocab[best[1]]
for w in word_ids:
word_ids[w] = _merge_seq(word_ids[w], best, next_id)
next_id += 1
self.ranks = {pair: i for i, pair in enumerate(self.merges)}
Encoding — greedy lowest-rank merge:
while len(ids) >= 2:
best_pair, best_rank = None, None
for pair in zip(ids, ids[1:]):
r = self.ranks.get(pair)
if r is not None and (best_rank is None or r < best_rank):
best_rank, best_pair = r, pair
if best_pair is None:
break
ids = _merge_seq(ids, best_pair, self.merges[best_pair])
Save/load serializes specials and the merge list to JSON — no pickle, easy to inspect.
sequenceDiagram
participant T as Text
participant P as Pretokenizer
participant B as Byte IDs
participant M as Merge engine
participant V as Vocab lookup
T->>P: findall(regex)
P->>B: UTF-8 encode each pretoken
B->>M: greedy rank merges
M->>V: final token IDs
Note over V: decode = concat bytes → UTF-8
What vocabulary size should you use?
For my AL-1 code model I’m targeting 8k–16k merges on top of the 262-byte floor. Code has more distinct symbols than TinyShakespeare — operators, indentation, string delimiters. A 4k vocab works for prose; Python benefits from headroom.
Training data: I’m using a 100-file slice of the-stack-smol-xs Python split (~1 MB) for smoke tests, then scaling to a ~10 MB sample for the real merge table. You don’t need the full corpus to learn reasonable merges — frequency tails off fast.
| Setting | My value | Why |
|---|---|---|
vocab_size |
8,000–16,000 | Code needs more symbols than char-level |
min_freq |
2 | Ignore one-off pair noise |
| Special tokens | 6 | Pad, boundaries, future tool calls |
| Floor | 262 | $6 + 256$ bytes |
Compare to GPT-2: 50,257 tokens. Same algorithm, bigger corpus, more merges.
Tokenizer design is also a model-efficiency trade. For vocabulary size $V$ and model width $d$, an untied input plus output embedding table costs about $2Vd$ parameters. Attention cost grows roughly with sequence length squared. A smaller vocabulary means fewer embedding parameters but longer sequences; a larger vocabulary shortens sequences but inflates the embedding matrices and creates rarer tokens that receive fewer gradient updates.
BPE vs WordPiece vs SentencePiece
| Method | Merge criterion | Used by |
|---|---|---|
| BPE | Most frequent pair | GPT-2/3/4, LLaMA, Mistral |
| WordPiece | Pair that maximizes language-model likelihood | BERT |
| SentencePiece | BPE or unigram, trained on raw bytes with meta-symbols | T5, LLaMA 2 tokenizer option |
For a decoder-only GPT clone, BPE is the path of least resistance — it’s what tiktoken implements for gpt2 encoding, and the merge-rank encode logic matches what you need for a from-scratch rebuild.
Common bugs I watch for
Forgetting the leading space in pretokens. "hello" and " hello" learn different merges. If your training data strips spaces but inference doesn’t, token counts drift.
Off-by-six in byte IDs. Special tokens shift everything. ord('a') is 97, but the token ID is 103 when byte_base=6. Every pair count depends on this.
Merge order mismatch. Encoding must use ranks (creation order), not frequency at encode time. Re-sorting merges breaks round-trip.
vocab_size too small. Below 262 the code refuses to start. Below ~1000 on code and you’re mostly bytes anyway — defeats the purpose.
Run round-trip tests on snippets from your actual corpus before you wire the tokenizer into the dataloader. Same advice as numerical gradient checking for autograd — catch data-pipeline bugs before they poison training.
Where this fits in the build
AL-1 pipeline so far: autograd engine → gradient checker → BPE tokenizer → token embeddings → positional encoding → transformer blocks.
The tokenizer is the bridge between raw .py files and the integer sequences the embedding layer consumes. The GPT-2 architecture post shows where those IDs go once they’re ready — wte, causal attention, lm_head with weight tying.
I built this tokenizer by hand because I wanted to stare at merge tables when generation looks wrong. When import tiktoken is one line, you lose visibility into whether the bug is the model or the bytes going in. For a toy GPT that might be overkill. For learning how these systems actually work, it’s the difference between using a library and owning the pipeline.
Train the merges. Check round-trips. Then trust your IDs.
Support the writing
If this post helped, a coffee keeps the deep dives, paper picks, and news digests coming.
Buy Me a Coffee