← Master Index
Vol. 12 Module 12.1 Lecture

Byte Pair Encoding (BPE)

Tokenization Deep Dive

How This Lesson Fits the Module & Volume

Volume 11 introduced the tokenizer and fixed vocabulary as production contracts. Module 12.1 opens the algorithms behind those artifacts. Byte-Pair Encoding (BPE) is the workhorse merge procedure behind GPT-2/3-style tokenizers and many open LLMs.

Mastering BPE lets you read merge files, predict why a domain word splits oddly, and decide when to train a new vocab versus reuse an existing one—skills you will reuse in byte-level BPE, tiktoken, and vocabulary building.

Learning Objectives

By the end of this lesson, students should be able to:

  • Explain BPE training as iterative merges of the most frequent adjacent symbol pairs.
  • Distinguish BPE training (learn merges) from BPE encoding (apply merges greedily).
  • Trace a toy corpus through several merge steps to a final subword inventory.
  • Use Hugging Face tokenizers to train a small BPE model and encode text.
  • Relate BPE vocab size to sequence length, OOV handling, and embedding cost.
  • Contrast classic word-boundary BPE with later byte-level and Unigram variants.
Definition

Byte-Pair Encoding (BPE) is a data compression–inspired subword algorithm that starts from an initial alphabet (characters or bytes) and repeatedly merges the most frequent adjacent pair into a new symbol until a target vocabulary size is reached. At inference, the same ordered merge list is applied greedily to segment new text.

Training vs Encoding

Init

Split words into chars (+ end marker).

Count

Tally adjacent pair frequencies.

Merge

Promote top pair; repeat.

Encode

Apply learned merges greedily.

PhaseInputOutput
TrainCorpus + target |V|Vocab + ordered merge rules
EncodeRaw text + merge rulesSubword IDs
DecodeIDsSurface string (may normalize)

Toy Walkthrough

Suppose the corpus frequencies are low×5, lowest×2, newer×6, wider×3. After character splitting with an end-of-word marker </w>, the first merges often promote frequent pairs like e r or l o. Each merge creates a reusable multi-character token used in later pair counts—rare full words may remain fragmented while common stems become single tokens.

What BPE Optimizes

  • Compression of frequent patterns
  • Open-vocabulary coverage via pieces
  • Deterministic, fast encoding

What It Does Not

  • Linguistic morphology awareness
  • Likelihood-optimal segmentation
  • Guaranteed round-trip identity

Seen In

  • Neural MT (Sennrich et al., 2016)
  • GPT-2 / many decoder LMs
  • HF BPE trainers

Code: Train a Tiny BPE with tokenizers

from tokenizers import Tokenizer from tokenizers.models import BPE from tokenizers.trainers import BpeTrainer from tokenizers.pre_tokenizers import Whitespace tok = Tokenizer(BPE(unk_token="[UNK]")) tok.pre_tokenizer = Whitespace() trainer = BpeTrainer( vocab_size=100, special_tokens=["[UNK]", "[PAD]", "[CLS]", "[SEP]"], ) # Provide a list of text files or an iterator of strings: tok.train_from_iterator( ["low lowest newer wider low low newer newer", "widest lowest newer low"], trainer=trainer, ) print(tok.encode("newer lowest").tokens) print(tok.encode("unseenword").tokens)

Strengths

  • Simple, reproducible merges
  • Handles rare words via subwords
  • Widely supported tooling

Tradeoffs

  • Greedy encode ≠ global optimum
  • Whitespace / Unicode edge cases
  • Domain shift changes token length
Common Misconception

“BPE merges characters into linguistically correct morphemes.” Merges follow frequency, not grammar. ing may become a token because it is common—not because BPE “knows” English morphology. Always inspect tokens on your domain corpus before trusting length or readability.

Knowledge Check

  1. Short Answer: What does one BPE training step merge? Answer: The most frequent adjacent symbol pair into a new symbol.
  2. True/False: BPE encoding re-learns merges for every new sentence. Answer: False—it applies the stored merge list.
  3. Multiple Choice: BPE was popularized for NMT by: (a) Word2Vec, (b) Sennrich et al., (c) TF-IDF. Answer: (b).
  4. Short Answer: Name the two artifacts BPE training produces. Answer: A vocabulary and an ordered list of merge rules.
  5. True/False: Larger BPE vocab always shortens every sequence. Answer: False—on average yes, but rare/domain text can still fragment.
  6. Multiple Choice: Classic BPE typically starts from: (a) POS tags, (b) characters (or bytes later), (c) random IDs. Answer: (b).
  7. Short Answer: Why can two synonymous rare words share pieces? Answer: Shared frequent substrings become merges reused across words.
  8. Short Answer: What library class trains BPE above? Answer: BpeTrainer from Hugging Face tokenizers.
  9. Multiple Choice: Greedy BPE encode finds: (a) maximum-likelihood Unigram path, (b) merge-list segmentation, (c) parse trees. Answer: (b).
  10. True/False: BPE alone guarantees no unknown Unicode. Answer: False—character BPE can still hit UNK; byte-level BPE addresses coverage.

Key Takeaways

  • BPE learns merges by frequency and encodes with that ordered merge list.
  • It is a compression heuristic, not a morphological analyzer.
  • Vocab size trades sequence length against embedding/softmax cost.
  • Train and ship merges with the model; never invent merges at inference.
  • Next: WordPiece—BERT’s likelihood-flavored cousin with ## markers.
Trainer’s Guide

Hands-on: Train BPE at |V|=50, 200, and 1000 on the same mini-corpus; plot average tokens per word.

Discussion: When would you freeze a public BPE vocab instead of training your own?

Recap: BPE is iterative pair merging plus greedy application of those merges. Continue with WordPiece.