BPE Tokenizer
Implement a trainable byte-level Byte Pair Encoding tokenizer from scratch in Python
What You Will Build
Large Language Models do not read raw characters or whitespace-split words; they read subword tokens produced by Byte Pair Encoding (BPE). Starting from a base vocabulary of the 256 raw UTF-8 byte values (`0..255`), byte-level BPE iteratively counts adjacent token pairs across a training corpus, mints a new token ID (`256, 257, ...`) for the most frequent pair, and records the merge rule `(p0, p1) -> new_id`. Because every UTF-8 string is a sequence of bytes, a byte-level BPE tokenizer can encode and decode ANY text—including multilingual scripts, source code indentation, math symbols, and emojis—with zero `<unk>` out-of-vocabulary failures. In this project, you will implement a standalone, trainable BPE tokenizer from scratch in pure Python.
Why This Project Matters in the AI/LLM Stack
Tokenization directly governs an LLM's context window efficiency, arithmetic behavior, code formatting, and multilingual token fertility. Furthermore, you will use your custom BPE tokenizer directly in Project 11 to tokenize the pretraining corpus for `MyLLM v1`.
Learning Objectives
- Convert arbitrary Unicode strings into raw UTF-8 byte sequences (`0..255`) and explain why byte-level BPE eliminates `<unk>` tokens.
- Implement pair frequency counting, iterative merge execution, and vocabulary construction (`vocab: dict[int, bytes]` and `merges: dict[tuple[int, int], int]`).
- Implement deterministic `.encode(text)` (applying learned merges in priority order) and `.decode(ids)` (concatenating byte chunks and decoding UTF-8 safely).
- Support regex pre-tokenization splits and special control tokens (`<|endoftext|>`, `<|pad|>`) and verify lossless round-trip encoding/decoding across diverse inputs.
Prerequisites
- Python `str.encode('utf-8')`, `bytes.decode('utf-8', errors='replace')`, dictionaries, and regular expressions
- Phase 4 Module 4.1 & 4.2 (Tokenization & Subword Vocabulary Construction)
Required Mathematical Concepts
- UTF-8 variable-length (1 to 4 bytes) character encoding
- Greedy iterative pair frequency maximization: (a*, b*) = argmax_{(a,b)} count(a, b)
- Compression ratio (bytes per token) and token fertility (tokens per word)
- Priority ordering of merge rules during deterministic encoding
Step-by-Step Implementation Tasks (14 Steps)
Check off each engineering task as your code passes its acceptance criteria. Progress is saved automatically in your browser.
UTF-8 Byte Representation & Pair Frequency Counting
Convert text to UTF-8 byte integers (`0..255`), count adjacent pairs, and implement the single-step pair replacement primitive.
Python strings are sequences of Unicode code points (`ord(ch)`), while `.encode('utf-8')` maps them into raw bytes (`0..255`).
Training a representative BPE merge table requires a corpus containing prose, punctuation, numbers, and code or dialogue.
Initializing token IDs `0..255` to the 256 single-byte values `bytes([i])` guarantees completeness over all valid UTF-8 strings.
At each step of BPE training, we count how often every adjacent pair `(ids[i], ids[i+1])` appears across the corpus.
Selecting the pair with the highest count (with deterministic tie-breaking) ensures reproducible tokenizer training.
Given a sequence `ids`, a target `pair = (p0, p1)`, and a new token ID `new_id`, `merge_ids(ids, pair, new_id)` replaces all non-overlapping occurrences of `(p0, p1)` from left to right with `new_id`.
Merge Vocabulary Training, Encoding & Decoding
Train the ordered merge table up to target `vocab_size`, build byte vocabularies, and implement `.encode()` and `.decode()`.
Each merge mints token ID `256 + step` whose byte sequence is the concatenation `vocab[p0] + vocab[p1]`.
During `.encode(text)`, you MUST apply merges in the order they were learned (lowest merge index `self.merges[pair]` first), NOT by most frequent pair inside the test string!
Decoding maps each integer token ID `idx` to its `bytes` chunk `self.vocab[idx]`, joins them with `b''.join(...)`, and decodes UTF-8.
Edge Cases, Unicode Safety, Special Tokens & Round-Trip Tests
Handle pre-tokenization regex splits, special tokens, arbitrary Unicode, round-trip tests, and comparison against `tiktoken`.
Regex pre-tokenization (like GPT-2 / GPT-4's split pattern) prevents BPE from merging across word boundaries and punctuation (e.g., preventing `'dog.'`, `'dog!'`, and `'dog?'` from becoming 3 unrelated tokens).
Multi-byte Unicode characters (emojis, accented characters, non-Latin scripts) split into 2–4 raw UTF-8 bytes that recombine seamlessly during `b''.join` decoding.
The fundamental correctness invariant of a lossless tokenizer is `decode(encode(text)) == text`.
Comparing your tokenizer's token boundaries and compression ratio against GPT-2 / GPT-4 (`tiktoken` or Hugging Face `tokenizers`) highlights how vocabulary size (`512` vs `50,257`) affects sequence length.
BPE tokenization introduces well-known LLM quirks: inconsistent integer splitting (`'12345'`), trailing-space sensitivity (`'hello '` vs `' hello'`), and higher token fertility on non-English languages.
Starter & Verification Code Examples
Core Byte-Level BPE Merge & Priority-Ordered Encoding
Shows the exact left-to-right `merge_ids` primitive and rank-ordered `.encode()` loop.
def get_pair_stats(ids: list[int]) -> dict[tuple[int, int], int]:
counts: dict[tuple[int, int], int] = {}
for pair in zip(ids, ids[1:]):
counts[pair] = counts.get(pair, 0) + 1
return counts
def merge_ids(ids: list[int], pair: tuple[int, int], new_id: int) -> list[int]:
new_ids: list[int] = []
i = 0
while i < len(ids):
if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
new_ids.append(new_id)
i += 2
else:
new_ids.append(ids[i])
i += 1
return new_ids
def encode_bytes(raw_bytes: bytes, merges: dict[tuple[int, int], int]) -> list[int]:
ids = list(raw_bytes)
while len(ids) >= 2:
stats = get_pair_stats(ids)
pair = min(stats, key=lambda p: merges.get(p, float("inf")))
if pair not in merges:
break
ids = merge_ids(ids, pair, merges[pair])
return idsHow to Test Your Implementation
Verify pair frequency counting, overlapping merge edge cases, merge-priority encoding order, and lossless round-trip identity across ASCII and Unicode.
Lossless Encode/Decode Round-Trip Across Unicode & Code
Prove `decode(encode(s)) == s` across ASCII, multi-byte UTF-8 emojis/math, and indented Python code.
Steps: Train tokenizer (`vocab_size=320`) on sample corpus, then test round-trip on 10 diverse strings including `'def f(x):\n return x 🚀 ∑'`.
Pass Criteria: `decode(encode(s)) == s` is True for 100% of test strings.
Overlapping Pair Merge Invariant (`[6, 6, 6]`)
Ensure left-to-right non-overlapping replacement handles consecutive identical tokens properly.
Steps: Call `merge_ids([6, 6, 6, 6], (6, 6), 256)` and `merge_ids([6, 6, 6], (6, 6), 256)`.
Pass Criteria: Returns `[256, 256]` and `[256, 6]` respectively.
Overall Project Acceptance Criteria
- The tokenizer demonstrates reliable, 100% lossless round-trip encoding and decoding (`decode(encode(s)) == s`) for all declared supported UTF-8 inputs.
- Base 256 byte vocabulary and iterative pair merges implemented from scratch in pure Python.
- Encoding applies merges strictly in learned priority order rather than test-string frequency order.
- Includes automated round-trip tests covering ASCII, multi-byte Unicode, source code, and special tokens.
Expandable Hints & Debugging Tips
Try implementing each stage on your own first. Expand a hint below if you want to verify tensor shapes, mathematical identities, or common edge cases.
Optional Stretch Challenges
Compare Tokenizer Vocabulary Sizes (512 vs 2,048 vs 8,192)
Train 3 tokenizers with vocabulary sizes 512, 2,048, and 8,192 on the same corpus and plot the compression ratio (bytes/token) and encoding speed.
What You Learn: How increasing `vocab_size` trades embedding table parameters `(V × d_model)` for shorter sequence lengths `T`.
Individual Digit Splitting Rule (Llama-3 / GPT-4 Style)
Add a regex rule that prevents numbers longer than 1 or 3 digits from merging together, and explain why this helps LLMs perform multi-digit addition.
What You Learn: How pre-tokenization regex design directly impacts LLM mathematical reasoning.
What Your Completed Repository Should Contain
A standalone trainable BPE tokenizer.
Deliverable Artifacts
- Pure-Python `BPETokenizer` with `.train()`, `.encode()`, `.decode()`, `.save()`, and `.load()`
- Regex pre-tokenization and special control token support
- Automated round-trip test suite across ASCII, Unicode, and source code
After Completing This Project, You Should Be Able To...
- Explain why byte-level BPE over UTF-8 bytes (`0..255`) achieves open-vocabulary coverage without `<unk>` tokens.
- Implement iterative BPE pair counting and merge table construction from scratch in Python.
- Implement rank-ordered BPE encoding, regex pre-tokenization, special token handling, and fault-tolerant UTF-8 decoding.
- Analyze how vocabulary size and pre-tokenization rules impact compression ratio and LLM behavior.
GitHub Repository Submission
Link your public or private GitHub repository URL to keep a structured portfolio of your from-scratch AI builds. Stored locally in your browser (self-reported; no GitHub tokens or remote code execution).
Suggested Repository: bpe-tokenizer-from-scratch
Recommended Directory Layout:
tokenizer/bpe.py tokenizer/regex_patterns.py tests/test_bpe_tokenizer.py README.md
Recommended README Documentation Checklist
- Explanation of UTF-8 byte-level BPE training and encoding priority
- Compression ratio and vocabulary size benchmark table
- Examples of subword segmentation and known BPE edge cases