Day 39: Byte-Pair Encoding — Merge Mechanics and Tokenizer Boundaries

01 120 min

Pair counts and the merge loop

Agent-Assisted Engineering Check

Prerequisites

Complete Day 38. If blocked, use the Day 35 recovery link for probability review.

Learning Objective

Trace the BPE training loop — count adjacent pairs, merge the most frequent pair into a fresh id, repeat — and reproduce a verified merge table by hand.

Instructions

Start from the byte ids of 'aaabdaaabac': [97,97,97,98,100,97,97,97,98,97,99]. Required work: each round, count every adjacent pair; the most frequent pair receives the next free id (256, then 257, and so on); ties break by first occurrence, matching Python's max() over an insertion-ordered dict. An empty string '' has no pairs and returns empty immediately; Unicode strings decompose into UTF-8 bytes and follow the identical merge loop. Write the merge trace, then verify with a small script. Optional work: continue to a fourth merge and name the token it creates.

Practice & Prediction Log

Hand-trace 3 merges on 'aaabdaaabac': write the pair counts each round, the chosen pair, and the new sequence. Predict the final token count and vocabulary size before checking.

Mark as Completed

Independent Mastery Criterion

Your handwritten trace reproduces all three merges, the first-occurrence tie-break, the final token list, and the 259 vocabulary size without consulting the reference.

Authoritative Source Resources & Provenance

linking MIT License (repository) / Standard YouTube License (video, subtitle rights unknown) Video subtitles have unknown distribution rights and are not imported

minbpe: Minimal Byte-Pair Encoding tokenizer (Let's build the GPT Tokenizer)

Author: Andrej Karpathy | Original Source Link ↗

Relevant Section / Range: minbpe/base.py: get_stats pair counting and merge loop; minbpe/basic.py BasicTokenizer

Verified Version & Date: commit 1acefe8 (Verified: 2026-10-30)

Selection Rationale:

The reference minimal implementation whose pair-count and merge loop the lesson traces by hand.

Source Prerequisites:

Basic Python and Day 37 bytes/code points

Safe Fallback (Offline Resilience):

The lesson re-implements the merge loop locally and prints a verified merge trace.

Compared Candidate Sources & Selection Analysis (3)

OpenAI tiktoken ↗ compared_alternative [MIT]

Production BPE with Rust core and regex pre-tokenization; selected as the production contrast source rather than the primary teaching implementation.

Hugging Face tokenizers + NLP course chapter 6 ↗ compared_alternative [Apache-2.0 (library) / CC BY-NC-SA? (course text varies)]

High-quality BPE coverage but frames tokenization through library APIs; minbpe exposes the raw merge loop for hand tracing.

Google SentencePiece ↗ compared_alternative [Apache-2.0]

Industrial tokenizer trainer supporting BPE and unigram models; C++ core hides the teaching mechanics.

linking CC BY 4.0 (ACL Anthology, 2016 or later) Paper text is not reproduced; linking only

Neural Machine Translation of Rare Words with Subword Units

Author: Rico Sennrich, Barry Haddow, Alexandra Birch | Original Source Link ↗

Relevant Section / Range: Section 3: byte-pair encoding adapted from compression to subword segmentation

Verified Version & Date: ACL 2016 (Verified: 2026-10-30)

Selection Rationale:

Primary source that introduced BPE as a subword segmentation algorithm for neural sequence models.

Source Prerequisites:

Basic probability and text processing

Safe Fallback (Offline Resilience):

The lesson teaches the complete merge algorithm with worked traces independent of the paper text.

Compared Candidate Sources & Selection Analysis (2)

Schuster & Nakajima: Japanese and Korean Voice Search (WordPiece) ↗ compared_alternative [IEEE copyright]

Related likelihood-scored variant used in BERT; paywalled and less aligned with frequency-greedy teaching merges.

Kudo & Richardson: SentencePiece (unigram language model) ↗ compared_alternative [CC BY 4.0 (paper, ACL Anthology) / Apache-2.0 (code)]

Strong probabilistic alternative segmentation; deferred because deterministic BPE merges are more hand-traceable at this stage.

02 120 min

Encoding, decoding, and the unknown-input policy

Independent Mastery Check (no AI assistance)

Prerequisites

Complete the previous activity; use the listed recovery link if blocked.

Learning Objective

Apply learned merges greedily by rank to encode new text, decode losslessly by concatenating vocabulary byte strings, and explain why byte-level input never needs an unknown token.

Instructions

Encoding repeatedly scans the current id list and merges whichever adjacent pair has the lowest merge rank, until no known pair remains. Required work: with merges {(97,97)→256, (256,97)→257, (257,98)→258}, encode 'aab' and 'baaa' by hand, then decode [258,100,258,97,99]. Optional work: state which production features this teaching tokenizer still lacks.

Practice & Prediction Log

Predict encode('aab') and encode('baaa') under the trained merge table, then decode [258,100,258,97,99]. State what 'é猫' encodes to under byte-level input and why it can never be 'unknown'.

Mark as Completed

Independent Mastery Criterion

Given a merge table, you can encode and decode new strings by hand with correct ids, explain why byte-level input removes the <unk> case, and name two concrete differences from a production tokenizer.

Authoritative Source Resources & Provenance

linking MIT License (repository) / Standard YouTube License (video, subtitle rights unknown) Video subtitles have unknown distribution rights and are not imported

minbpe: Minimal Byte-Pair Encoding tokenizer (Let's build the GPT Tokenizer)

Author: Andrej Karpathy | Original Source Link ↗

Relevant Section / Range: minbpe/base.py: encode iterates merges by rank; decode concatenates vocab byte strings

Verified Version & Date: commit 1acefe8 (Verified: 2026-10-30)

Selection Rationale:

Reference for the rank-ordered encode loop and lossless decode invariant exercised in this activity.

Source Prerequisites:

Day 39 Activity 1 merge table

Safe Fallback (Offline Resilience):

The exercises use a fully printed merge table and verified expected token ids.

Compared Candidate Sources & Selection Analysis (3)

OpenAI tiktoken ↗ compared_alternative [MIT]

Production BPE with Rust core and regex pre-tokenization; selected as the production contrast source rather than the primary teaching implementation.

Hugging Face tokenizers + NLP course chapter 6 ↗ compared_alternative [Apache-2.0 (library) / CC BY-NC-SA? (course text varies)]

High-quality BPE coverage but frames tokenization through library APIs; minbpe exposes the raw merge loop for hand tracing.

Google SentencePiece ↗ compared_alternative [Apache-2.0]

Industrial tokenizer trainer supporting BPE and unigram models; C++ core hides the teaching mechanics.

linking MIT License

tiktoken: Fast byte-pair encoding tokenizer used by OpenAI models

Author: OpenAI | Original Source Link ↗

Relevant Section / Range: README and tiktoken/core.py: byte-level coverage, regex pre-tokenization, and special-token handling

Verified Version & Date: Verified 2026-10-30

Selection Rationale:

Production contrast showing why a teaching tokenizer without regex pre-tokenization and special tokens is not model-compatible.

Source Prerequisites:

Basic Python

Safe Fallback (Offline Resilience):

All encode/decode exercises run on the local merge table with verified outputs.

Compared Candidate Sources & Selection Analysis (2)

Hugging Face tokenizers library ↗ compared_alternative [Apache-2.0]

Broad production tokenizer framework with training APIs; tiktoken is a cleaner contrast for GPT-style compatibility claims.

Google SentencePiece ↗ compared_alternative [Apache-2.0]

Widely used trainer/tokenizer for open models; treated as further production context rather than the contrast reference.

03 120 min

Fit merges on train only; evaluate compression on validation

Agent-Assisted Engineering Check

Prerequisites

Complete the previous activity; use the listed recovery link if blocked.

Learning Objective

Treat the merge table as learned parameters: fit it on the deterministic train split, measure bytes-per-token compression on held-out validation — never test — and record which split each stage consumed.

Instructions

Required work: reuse the Day-37 pipeline — run python3 projects/text_tools/cli.py --input data/names.txt --split --output-dir /tmp/lm-data (seed 42 → 25626/3203/3204). Train merges only on train.txt, then encode a val excerpt and report len(utf8_bytes)/len(token_ids) compression. Repeat with a different merge count and select on val, not test. Optional work: record the chosen merge count and both compression ratios in your notes.

Practice & Prediction Log

Predict whether compression will be higher on the training text or on held-out text, and why. Then verify on the toy corpus: merges fit on 'aaabdaaabac' compress it 11 bytes → 5 tokens; how does the same table compress the held-out string 'aab'?

Mark as Completed

Independent Mastery Criterion

You can state which split each stage consumes, reproduce both compression numbers (2.2× on the fit text, 1.5× on held-out), and explain the leakage that fitting merges on validation data would create.

Authoritative Source Resources & Provenance

linking MIT License (repository) / Standard YouTube License (video, subtitle rights unknown) Video subtitles have unknown distribution rights and are not imported

minbpe: Minimal Byte-Pair Encoding tokenizer (Let's build the GPT Tokenizer)

Author: Andrej Karpathy | Original Source Link ↗

Relevant Section / Range: README exercise: train a tokenizer on your own text and report compression ratio

Verified Version & Date: commit 1acefe8 (Verified: 2026-10-30)

Selection Rationale:

Frames tokenizer training as fitting merge parameters and compression as the evaluable metric.

Source Prerequisites:

Day 39 Activities 1-2

Safe Fallback (Offline Resilience):

The local merge trainer and the deterministic text_tools splits run fully offline.

Compared Candidate Sources & Selection Analysis (3)

OpenAI tiktoken ↗ compared_alternative [MIT]

Production BPE with Rust core and regex pre-tokenization; selected as the production contrast source rather than the primary teaching implementation.

Hugging Face tokenizers + NLP course chapter 6 ↗ compared_alternative [Apache-2.0 (library) / CC BY-NC-SA? (course text varies)]

High-quality BPE coverage but frames tokenization through library APIs; minbpe exposes the raw merge loop for hand tracing.

Google SentencePiece ↗ compared_alternative [Apache-2.0]

Industrial tokenizer trainer supporting BPE and unigram models; C++ core hides the teaching mechanics.

linking MIT

CS336 Assignment 1: Basics (Spring 2025 tagged release)

Author: Stanford University CS336 Staff | Original Source Link ↗

Relevant Section / Range: README setup; tests/adapters.py; tests/test_optimizer.py; tests/test_nn_utils.py; tests/test_serialization.py

Verified Version & Date: spring2025 tag; README, tests and MIT LICENSE checked 2026-11-01

Selection Rationale:

Lead assignment-driven source for pretraining component practice and tests. nanoGPT remains a compact historical code-reading companion, not the current recommended training curriculum.

Source Prerequisites:

Python systems programming

Safe Fallback (Offline Resilience):

The local verification script trains merges on a train split and reports val compression offline.

Compared Candidate Sources & Selection Analysis (2)

Karpathy nanoGPT ↗ compared_alternative [MIT]

Simpler code layout, useful complementary reference for minimal PyTorch Transformer.

Hugging Face Transformers Course ↗ compared_alternative [Apache-2.0]

High-level API focus rather than building from raw tensor fundamentals.

04 120 min

Independent mastery check: hand-trace merges and block retrieval

Independent Mastery Check (no AI assistance)

Prerequisites

Complete the previous activities; use the listed recovery link if blocked.

Learning Objective

Unaided, trace BPE merges on new text, encode with a known table, retrieve the UTF-8 length classes and the add-one formula from memory, and write a recovery plan for anything missed.

Instructions

Do not consult answers or AI during this check. Required work: (1) trace the first two merges for 'ababa'; (2) encode 'aaab' under the Day-39 merge table; (3) from memory, write the four UTF-8 length classes and the add-one smoothing formula; (4) record a recovery plan for each miss. Optional work: contrast a count-based bigram model with a learned-merge tokenizer in two sentences.

Practice & Prediction Log

(a) What are the first two merges for 'ababa' and the final id list? (b) What is encode('aaab') under merges {(97,97)→256, (256,97)→257, (257,98)→258}? (c) From memory: UTF-8 byte counts for 'a', 'é', '猫', '😀', and the add-one formula P(next|context).

Mark as Completed

Independent Mastery Criterion

All merges and ids are exact, the retrieved facts are stated without notes, and the recovery plan names the specific Day 37-39 activity that repairs each miss.

Authoritative Source Resources & Provenance

linking CC BY 4.0 (ACL Anthology, 2016 or later) Paper text is not reproduced; linking only

Neural Machine Translation of Rare Words with Subword Units

Author: Rico Sennrich, Barry Haddow, Alexandra Birch | Original Source Link ↗

Relevant Section / Range: Section 3: merge operations as learned segmentation vocabulary

Verified Version & Date: ACL 2016 (Verified: 2026-10-30)

Selection Rationale:

Primary reference for interpreting merges as a learned vocabulary of subword units.

Source Prerequisites:

Basic probability and text processing

Safe Fallback (Offline Resilience):

The mastery check contains a complete worked merge trace with verified ids.

Compared Candidate Sources & Selection Analysis (2)

Schuster & Nakajima: Japanese and Korean Voice Search (WordPiece) ↗ compared_alternative [IEEE copyright]

Related likelihood-scored variant used in BERT; paywalled and less aligned with frequency-greedy teaching merges.

Kudo & Richardson: SentencePiece (unigram language model) ↗ compared_alternative [CC BY 4.0 (paper, ACL Anthology) / Apache-2.0 (code)]

Strong probabilistic alternative segmentation; deferred because deterministic BPE merges are more hand-traceable at this stage.

linking MIT License (repository) / Standard YouTube License (video, subtitle rights unknown) Video subtitles have unknown distribution rights and are not imported

makemore: Character-level language models on names.txt

Author: Andrej Karpathy | Original Source Link ↗

Relevant Section / Range: makemore.py part 1: bigram count model as the count-based baseline against learned models

Verified Version & Date: Verified 2026-10-30

Selection Rationale:

Connects the count baseline of Day 38 to the tokenizer artifacts of Day 39 for the closing retrieval review.

Source Prerequisites:

Basic Python

Safe Fallback (Offline Resilience):

The retrieval review works entirely from local verified tables and traces.

Compared Candidate Sources & Selection Analysis (2)

Stanford CS336: Language Modeling from Scratch ↗ compared_alternative [No license declared (the repository has no LICENSE file, so all rights are reserved by default)]

More rigorous and comprehensive but assumes PyTorch fluency; retained as the systems-rigor companion source.

Karpathy nanoGPT ↗ compared_deferred [MIT]

Strong Transformer training reference but beyond the count-based baseline scope; deferred to later pretraining days.