Exercises — Byte-Pair Encoding (BPE)

(c). BPE training produces two coupled things: a vocabulary (the set of tokens) and an ordered list of merge rules (which pair to glue, in what priority). The order is not decoration — it is part of the answer, because encoding replays these rules from rule 1 downward. See Byte-Pair Encoding (BPE) "BPE Encoding (Inference)". Answer (a) is word-level tokenization (the thing BPE avoids), and (b) is unrelated — BPE is a deterministic counting algorithm, not a trained network.

Slide a two-symbol window left to right: $(n,e),(e,w),(w,es),(es,t),(t,</w>)$. Five pairs, because a string of 6 symbols has $6-1=5$ gaps between neighbours. Note es is one symbol here (an earlier merge already fused it), so (w,es) is a single pair, not (w,e) then (e,s).

False. The base vocabulary contains every single character. Any word, however weird, can always fall back to individual characters, so a valid tokenization always exists — no <UNK>. This is BPE's headline advantage over word-level tokenization. (Detail: modern byte-level BPE goes even lower, to raw bytes, guaranteeing coverage of any Unicode input.)

Split:

4×:  c a t </w>
4×:  c a p </w>

(c, a) appears once per word. Frequency $=4+4=8$.

Count all pairs:

• $(c,a)$: $4+4=8$
• $(a,t)$: $4$
• $(t,</w>)$: $4$
• $(a,p)$: $4$
• $(p,</w>)$: $4$

Winner is $(c,a)$ at 8, uncontested. Merge → new token ca. Corpus becomes:

4×:  ca t </w>
4×:  ca p </w>

Recount after ca:

• $(ca,t)$: $4$
• $(t,</w>)$: $4$
• $(ca,p)$: $4$
• $(p,</w>)$: $4$

Everything ties at 4. The corpus is perfectly balanced. Break the tie alphabetically on the pair's written form. Comparing the four candidates by their concatenated strings cat, cap, p</w>, t</w>: alphabetical order puts cap before cat before p</w> before t</w>. So merge $(ca,p)\to$ cap. Rule 2 is ca p → cap.

Input:            c a p s </w>
Apply rule 1 (c a→ca):   ca p s </w>
Apply rule 2 (ca p→cap): cap s </w>
No rule mentions (cap, s) or (s, </w>) → stop.
Output tokens: [cap, s, </w>]

The lonely s survives as a character token — perfectly legal, and exactly why BPE never fails on new words.

Every word in that corpus ends in ...u g </w>. So whenever (u,g) occurs, (g,</w>) occurs right after it in the same word — they are locked together across all three words. Their counts are therefore forced equal: $1+2+2=5$ each. The tie-break is alphabetical on ug vs g</w>: comparing character by character, g < u, so g</w> would sound like it wins — but the standard convention compares the pair joined as a token string, ug vs g</w>, and ug < g</w> is false (g < u). The parent chose (u,g); the honest reading is that implementations differ, and the parent's convention picks ug. Key insight for the exam: state your tie-break rule explicitly, because the corpus does not decide it for you.

Later rules are built on top of earlier ones. Rule es t → est presupposes the token es already exists, which only rule e s → es can create. If you applied est first, the symbol es isn't in the string yet, so the rule can't fire — you'd get stuck with e s t unmerged. See

BPE merges pairs in descending frequency. The first thousands of merges eat the very common pairs — each fires in a huge fraction of the corpus, so each one shortens many sequences at once, pushing $k$ up fast. By the time you reach the 25,000th merge, the remaining pairs are rare: each fires in only a sliver of the corpus, so gluing it barely moves the average token length. Formally, the marginal gain $\Delta k$ per merge tracks the frequency of the pair being merged, and frequencies fall off steeply (Zipf-like). So going 25k → 50k merges only rare pairs → tiny $\Delta k$ → tiny $\Delta R$. This is the diminishing returns the parent describes. See

Use 6× "low" 3× "lower". (Any corpus where l o w dominates works.)

6×:  l o w </w>
3×:  l o w e r </w>

Iteration 1 pair counts:

• $(l,o)=6+3=9$ ← highest
• $(o,w)=6+3=9$ (tie!) — break alphabetically: lo < ow, merge $(l,o)$.
• $(w,</w>)=6$, $(w,e)=3$, $(e,r)=3$, $(r,</w>)=3$.

Merge l o → lo:

6×:  lo w </w>
3×:  lo w e r </w>

Iteration 2:

• $(lo,w)=6+3=9$ ← highest, uncontested at 9.

Merge lo w → low. Rules: l o → lo, then lo w → low. ✔

Input:            s l o w </w>
Apply rule 1 (l o→lo):   s lo w </w>
Apply rule 2 (lo w→low): s low </w>
Stop (no rule touches (s, low) or (low, </w>)).
Output: [s, low, </w>]

Even though slow never appeared, its frequent inner chunk low is recovered — the whole point of subword tokenization. This same token feeds straight into an 3.1.05-Embedding-Layer, where low gets one shared vector across every word that contains it.

Yes, they can diverge. A tie chooses a different merge, which changes which pairs exist next round, which changes future counts — the effect cascades. So two "valid" BPE runs can yield different vocabularies and different merge orders. Why it matters downstream: a deployed model is bound to its tokenizer forever. If you swap tokenizers (even by a tie-break tweak), previously trained token IDs no longer mean the same thing — the embedding table and all cached KV states become invalid. For 6.2.02-Inference-Optimization, the tokenizer is a frozen contract: reproducibility ⇒ pin the tie-break rule.

• Empty string: chars = []. Adding </w> gives just </w> (or nothing, per convention). No pairs exist (need ≥2 symbols for a pair), so no rule fires. Output: [</w>] or []. The algorithm is total — it never crashes on empty input.
• "a": split → a </w>. Exactly one pair (a, </w>). If no learned rule matches it, output is [a, </w>]. If a rule a </w> → a</w> exists, output [a</w>]. Either way, defined and finite. Takeaway: the merge loop always terminates because each merge strictly reduces the symbol count, which is bounded below by 1.

Rules (in order): u g → ug, ug </w> → ug</w>, b ug</w> → bug</w>, p ug</w> → pug</w>. For hugs:

Input:          h u g s </w>
Rule 1 (u g→ug):   h ug s </w>
Rule 2 needs (ug,</w>) adjacent — but 's' sits between ug and </w>. FAILS.
Rules 3,4 need ug</w>, which never formed. FAIL.
Output: [h, ug, s, </w>]

For bugs, the same wall appears — s blocks (ug, </w>):

Input:          b u g s </w>
Rule 1 (u g→ug):   b ug s </w>
Rule 2 blocked by 's'. Rules 3,4 need ug</w>. All FAIL.
Output: [b, ug, s, </w>]

Crucial lesson: ug</w> and bug</w> are word-ending tokens. A trailing s changes the ending, so those end-anchored tokens can't apply. The </w> boundary is doing real work here.

From the parent's formula $L_{\text{BPE}}\approx C/k$ and $R=k$:

• $L_{\text{BPE}}=1,000,000/4=250,000$ tokens. $R=4$ (sequences are 4× shorter than character-level).
• At $k=5$: $L^{\prime }=1,000,000/5=200,000$ tokens.
• Saved: $250,000-200,000=50,000$ tokens (a 20% reduction). Notice the ratio only rose from 4 to 5 for that saving — the diminishing-returns effect of Ex 3.3 in numbers.

Split with </w>:

3×:  a b </w>
2×:  a b c </w>

Base vocab $V_0=\{a,b,c,</w>\}$ → size 4.

Iteration 1 pairs:

• $(a,b)=3+2=5$ ← highest
• $(b,</w>)=3$, $(b,c)=2$, $(c,</w>)=2$.

Merge a b → ab. $V_1=V_0\cup \{ab\}$, size 5.

3×:  ab </w>
2×:  ab c </w>

Iteration 2 pairs:

• $(ab,</w>)=3$ ← highest
• $(ab,c)=2$, $(c,</w>)=2$.

Merge ab </w> → ab</w>. $V_2$, size 6.

3×:  ab</w>
2×:  ab c </w>

Iteration 3 pairs (only the abc word still has pairs):

• $(ab,c)=2$, $(c,</w>)=2$ — tie at 2. Alphabetical on abc vs c</w>: abc < c</w>, merge $(ab,c)$.

Merge ab c → abc. $V_3$, size 7.

3×:  ab</w>
2×:  abc </w>

Iteration 4 pairs:

• $(abc,</w>)=2$ ← only pair left.

Merge abc </w> → abc</w>. $V_4$, size 8 → target reached, stop.

Final vocabulary (size 8): $V=\{a,b,c,</w>,ab,ab</w>,abc,abc</w>\}$ Merge rules in order: a b → ab, ab </w> → ab</w>, ab c → abc, abc </w> → abc</w>.

BPE merges the most frequent adjacent pair each round. Ties are broken alphabetically (by convention — state it explicitly). BPE can never emit an ==<UNK> token because the base vocab holds every character. Merge rules must be applied during encoding in the order they were learned. The compression ratio equals $k$, the average characters per token, with diminishing returns as vocab grows. Merges must be recounted from the rewritten (post-merge)== corpus, not the original characters.