Byte Pair Encoding › Worked Example: Step-by-Step Trace
Language AI HandbookAll chapters Byte Pair Encoding › Worked Example: Step-by-Step TraceOne section · Sections in this chapter6 / 14 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
Let's trace BPE from start to finish on a tiny corpus to make every step concrete. We will use a corpus of six words: "low", "lower", "lowest", "new", "newer", "newest", each appearing once. Working through this example by hand is the single best way to build an accurate mental model of what the algorithm does.
Before running the code, it helps to reason about what we expect to happen. The corpus has six words sharing two roots: "low" and "new". Both roots appear in bare form and with the suffixes "-er" and "-est". The pairs "l+o", "o+w", "n+e", "e+w" should appear frequently because they occur in every word of their respective families. The suffix pairs "e+r" and "e+s", "s+t" should also appear in three words each. We should see the algorithm discover these patterns in roughly this order.
# Minimal corpus for a clean trace
trace_corpus = ["low lower lowest new newer newest"]
trace_wf = build_initial_vocab(trace_corpus)
trace_rules = []Initial character-level vocabulary: ------------------------------------------------------- l o w </w> l o w e r </w> l o w e s t </w> n e w </w> n e w e r </w> n e w e s t </w>
# Run 8 merge steps and record state after each
trace_history = []
current_wf = trace_wf.copy()
for step in range(8):
pairs = count_pairs(current_wf)
if not pairs:
break
best = max(pairs.items(), key=lambda x: x[1])[0]
trace_rules.append(best)
current_wf = merge_pair(current_wf, best)
trace_history.append((best, dict(current_wf)))Merge trace: ----------------------------------------------------------------- Step 1: merge 'w' + 'e' → 'we' l o w </w> l o we r </w> l o we s t </w> n e w </w> n e we r </w> n e we s t </w> Step 2: merge 'l' + 'o' → 'lo' lo w </w> lo we r </w> lo we s t </w> n e w </w> n e we r </w> n e we s t </w> Step 3: merge 'n' + 'e' → 'ne' lo w </w> lo we r </w> lo we s t </w> ne w </w> ne we r </w> ne we s t </w> Step 4: merge 'w' + '</w>' → 'w</w>' lo w</w> lo we r </w> lo we s t </w> ne w</w> ne we r </w> ne we s t </w> Step 5: merge 'lo' + 'we' → 'lowe' lo w</w> lowe r </w> lowe s t </w> ne w</w> ne we r </w> ne we s t </w> Step 6: merge 'r' + '</w>' → 'r</w>' lo w</w> lowe r</w> lowe s t </w> ne w</w> ne we r</w> ne we s t </w> Step 7: merge 's' + 't' → 'st' lo w</w> lowe r</w> lowe st </w> ne w</w> ne we r</w> ne we st </w> Step 8: merge 'st' + '</w>' → 'st</w>' lo w</w> lowe r</w> lowe st</w> ne w</w> ne we r</w> ne we st</w>
Working through this trace teaches you to see BPE from the algorithm's perspective. In the first step, it finds the highest-count pair across all words weighted by frequency. Notice how words that share character sequences contribute their full frequency counts to those pairs. Common character bigrams like "ew" (appearing in "new", "newer", "newest") merge early because they appear in three distinct words. Shared root sequences like "low" get consolidated as more rules accumulate. By step 8, familiar morphological units like "er", "est", "new", and "low" have emerged as single tokens, without any explicit knowledge of English grammar.
The key insight from tracing these steps is that BPE is discovering statistical redundancy, and linguistic structure is a consequence of that statistical redundancy. The reason "er" and "est" emerge as tokens is not that the algorithm knows they are suffixes; it is that English uses those suffix patterns extremely frequently. The algorithm's blindness to linguistic concepts is exactly what makes it generalize: the same process that finds "er" in English will find "-chen" (diminutive) in German and "-tion" cognates across Romance languages.