Unit 1.2 · about 6 h
291 / 324Byte-level BPE: training, merges and tie-breaking
Every later count in this stage, from sequence lengths to KV-cache bytes, is measured in tokens, and BPE decides what a token is. The merge list is part of the model's identity: change one tie-break and every token ID downstream shifts.
- derive
- implement
You can now
- Run BPE training by hand on a small corpus, apply the tie-breaking rule, and predict the merge list.
- Implement byte-level BPE training from a blank file, with regex pre-tokenization and special tokens as hard boundaries.
- Explain why a byte-level vocabulary encodes any input without an unknown token.
Covers
- Byte-level tokenization and complete input coverage
- BPE pair counts, merges and deterministic tie breaking
Study, in this order
2 steps
- BPE tokenizer from scratch (notebook)LLMs from Scratch companion - tokenization and data loading
Sections 1.1 to 1.4 for bytes, the vocabulary and a worked example, then 3.1 for training, encoding and decoding
Depth · Skim section 2, the simple implementation. Skip 3.3, loading OpenAI's GPT-2 files, until the identity unit.
- CS336 Assignment 1 handoutStanford CS336 Assignment 1 - tokenizer contract
Section 2.4, BPE Tokenizer Training, with Example (
bpe_example) (pp. 5 to 7), then Section 2.5 on removing special tokens before pre-tokenization and optimizing the merge step (pp. 8 to 9)
Focus on
- The base vocabulary is all 256 byte values, so coverage is complete before the first merge. Merges only shorten sequences.
- Pairs are counted inside pre-tokens, weighted by how often each pre-token occurs. No pair crosses a pre-token or special-token boundary.
- Ties go to the lexicographically greater pair. Without a fixed rule, two correct trainers produce different merge lists.
- After a merge, only the counts of pairs that overlap the merged occurrences change. Updating just those makes training fast.
Reproduce closed-book
[ne, west].Traps
- Decoding token bytes to
strto compare or print them. A merged token can be a partial UTF-8 sequence, so decoding fails or maps distinct tokens to the same replacement character. - Pre-tokenizing before splitting on special tokens. Their text then enters the pair counts as ordinary pieces such as
<|andendoftext, and steals merges. - Treating
vocab_sizeas the number of merges. It includes the 256 byte values, the merges and the special tokens.
Practice
CS336 Assignment 1: `train_bpe`
Problem (train_bpe) in Section 2.4; connect your trainer to run_train_bpe in tests/adapters.py and pass tests/test_train_bpe.py
The public tests compare your merges and vocabulary with a reference, check special-token handling, and require training on the small fixture in under 1.5 seconds. Implement it in your own repository.
Self-test
-
Why can byte-level BPE encode any string, while a character vocabulary built from a corpus cannot?
Its base vocabulary holds all 256 byte values, and every string has a UTF-8 encoding. A character vocabulary covers only the characters seen in training, so an unseen character needs an unknown token. -
The pairs (A, B), (A, C), (B, ZZ) and (BA, A) tie for the highest count. Which one merges under the CS336 rule?
(BA, A). The rule takes the lexicographically greatest pair, and BA sorts after A and B. -
After (s, t) merges into st, which pair counts can change?
Only counts next to the merged occurrences. Each neighbouring pair (x, s) or (t, y) loses those occurrences, the new pairs (x, st) and (st, y) gain them, and (s, t) loses every occurrence that merged. All other counts stay the same. -
A training file contains [Doc 1]
<|endoftext|>[Doc 2]. What goes wrong if you pre-tokenize it without splitting on the special token first?The special token's text is pre-tokenized like ordinary text, so its pieces enter the pair counts and can earn merges. The trainer should split on special tokens so that they act as hard boundaries and contribute nothing to the counts.
Completion criterion
Stop when
You reproduce the six example merges by hand, and your own trainer passes all three tests in tests/test_train_bpe.py.
Leads to
- 1.4 A tokenizer you can trust: round trips, identity and streaming Turn the merge list into an encoder and decoder you can trust.
- 1.3 Tokenizer design choices: vocabulary size, Unigram and special tokens Weigh vocabulary size and contrast BPE with Unigram.
Comes after
- 1.1 Text as bytes: Unicode, encodings and normalizationUse bytes as the complete base vocabulary.
Resources for this unit
- LLMs from Scratch companion - tokenization and data loading Work through the ch02 main notebook, 05_bpe-from-scratch and 04_bonus_dataloader-intuition. Rebuild byte-level BPE, serialization and packed windows in blank files, then add multilingual, control, whitespace and chunk-boundary properties.
- Stanford CS336 Assignment 1 - tokenizer contract Read the Assignment 1 tokenizer handout and use the named unicode1, unicode2, train_bpe, tokenizer and tokenizer_experiments specifications plus public tests as an acceptance contract. Implement independently in your own repository and do not copy or modify course solutions.
Also in this section
- Modern LLM Notebook - tokenization and data experiments Run English notebooks 01-tokenizer-basics and 02-bpe-tokenizer. Use only the quality, deduplication and mixture examples from 15-data-engineering. Change the corpus and tie cases, then verify every quantitative claim independently.
- Tokenizer and Corpus Pipeline - reduced foundation slice Use the byte, identity, split, deduplication, contamination, packing, manifest and restart correctness requirements. Keep the corpus small and stop before distributed processing or internet-scale filtering.
- Hugging Face LLM Course - tokenizer translation After the blank-file tokenizer passes, use the tokenizer chapters to map vocabulary, special tokens, fast tokenizers and batching into library APIs. Do not replace the deterministic implementation gate with a pretrained tokenizer call.
- Python unicodedata - normalization forms Read
unicodedata.normalizefor canonical and compatibility equivalence, andunidata_versionfor recording the normalization database version. - Hugging Face Datasets - streaming, sharding and resume Read Shard, Interleave, Save a dataset checkpoint and resume iteration, and Export. Use tiny local data and inspect the warning that shuffle buffers are lost on resume; do not download web-scale corpora or upload to the Hub.