Byte-Pair Encoding (BPE)

4.2.2 · AI-ML › Tokenization & Language Modeling

BPE Kaunsi Problem Solve Karta Hai?

Teen tokenization approaches aur unki problems:

Word-level: Vocabulary explode ho jaati hai (millions of words), typos/"unknownwords" handle nahi ho paate → <UNK> tokens har jagah
Character-level: Chhoti vocab (26-100 chars), lekin sequences BAHUT lambi ho jaati hain, model ko spelling scratch se seekhni padti hai
BPE (subword-level): Fixed vocab size (10k-50k), rare words ko decomposition se handle karta hai, morphology capture karta hai

The 80/20: BPE aapko word-level efficiency ka 80% deta hai word-level vocabulary size ke sirf 20% mein, plus zero <UNK> tokens.

BPE Algorithm: First Principles Se

Yeh Design Kyun?

Greedy frequency-based merging: Compression ke liye optimize karta hai (common patterns ek baar store karo)
Bottom-up construction: Characters se shuru hota hai (koi bhi input handle karta hai) aur upar build karta hai (frequent patterns capture karta hai)
Deterministic: Same corpus + same $V$ → same vocabulary (reproducible)

Chaliye ek tiny corpus par BPE train karte hain jiska target vocab size = 11 hai. Counting easy karne ke liye, maano corpus mein yeh word frequencies hain: low (×5), lower (×2), newest (×6), widest (×3).

Corpus (counts ke saath): 5× "low" 2× "lower" 6× "newest" 3× "widest"

Step 0: Characters Se Initialize Karo

Har word ko characters mein split karo aur word boundary </w> lagao:

5×:  l o w </w>
2×:  l o w e r </w>
6×:  n e w e s t </w>
3×:  w i d e s t </w>

Base vocabulary $V_{0} = {l, o, w, e, r, n, s, t, i, d, </w>}$ → size = 11

Pairs ki frequencies (pair occurrences ko word count se multiply karo):

(l, o): low(×5) + lower(×2) mein hai = 7
(o, w): low(×5) + lower(×2) = 7
(w, </w>): low(×5) = 5
(w, e): lower(×2) + newest(×6) = 8 ← highest
(e, s): newest(×6) + widest(×3) = 9 ← actually highest
(s, t): newest(×6) + widest(×3) = 9
(e, r): lower(×2) = 2

Step 1: Most Frequent Pair Merge Karo

Top pairs 9 par tie karte hain: (e, s) aur (s, t). Alphabetically tie break karo → (e, s) merge karo.

Naya token: es
Updated corpus:

5×:  l o w </w>
2×:  l o w e r </w>
6×:  n e w es t </w>
3×:  w i d es t </w>

$V_{1} = V_{0} \cup {es}$ → size = 12

Yeh step kyun? es newest aur widest dono mein share hota hai (9 baar) → is round mein maximum compression.

Step 2: Agla Merge

Pairs recount karo:

(es, t): newest(×6) + widest(×3) = 9 ← most frequent
(w, e): lower(×2) + newest(×6) = 8
(l, o): 7, (o, w): 7

(es, t) merge karo → naya token est

Updated corpus:

5×:  l o w </w>
2×:  l o w e r </w>
6×:  n e w est </w>
3×:  w i d est </w>

$V_{2} = V_{1} \cup {est}$ → size = 13

Target Vocab Size Tak Continue Karo...

Algorithm continue karega, aage (w, e) (=8) merge karega, phir (l, o) (=7), phir (lo, w), eventually low, est</w>, newest</w> jaisi subwords form hongi.

Final learned merges ("BPE merge rules", order mein):

1. e s → es
2. es t → est
3. w e → we
4. l o → lo
5. lo w → low
...

Encoding Example: "lowest"

Merge rules learned (simplified, order mein):

e s → es
es t → est
l o → lo
lo w → low

Step-by-step (rules priority ke anusaar apply karo, lowest index pehle):

Input: l o w e s t </w>

Apply rule 1 (e s→es):   l o w es t </w>
Apply rule 2 (es t→est): l o w est </w>
Apply rule 3 (l o→lo):   lo w est </w>
Apply rule 4 (lo w→low): low est </w>

Output tokens: [low, est, </w>]

Yeh encoding kyun? "low" aur "est" frequent subwords hain. Model "est" ko "lowest", "newest", "widest" mein dekhega → comparative/superlative morphology seekhega.

BPE Kaam Kyun Karta Hai: Math

Yeh formula kyun? Har merge jahan bhi pair hota hai wahan 2 adjacent symbols ko 1 se replace karta hai, aur average token length $k$ badhti hai. Isliye sequence length roughly linearly $k$ ke saath shrink hoti hai: $L_{BPE} \approx C / k$ . Khaas baat, $k$ merges ki sankhya ke saath badhti hai lekin diminishing returns ke saath — pehle merges (bahut frequent pairs) sequences bahut chhoti kar dete hain, baad ke merges (rare pairs) mushkil se kuch karte hain. Yeh empirical hai, $V$ mein koi clean logarithmic law nahi hai.

Diminishing returns: 10k → 50k vocab jaane par $k$ thoda hi badhta hai, isliye extra sequence-length reduction 1k → 10k ke mukable mein bahut kam hai.

Worked example Full Example: "hug" Corpus Par Training

Corpus (counts ke saath): 1× "hug" 2× "pug" 2× "bug"

Target vocab size: 10

Initial: </w> ke saath chars mein split karo

1×:  h u g </w>
2×:  p u g </w>
2×:  b u g </w>

$V_{0} = {h, u, g, p, b, </w>}$ → size = 6

Iteration 1: Pairs count karo (word count se multiply karo)

(u, g): hug(×1) + pug(×2) + bug(×2) = 5 ← merge
(g, </w>): hug(×1) + pug(×2) + bug(×2) = 5

5 par tie; alphabetically break karo → (u, g) merge karo → ug

1×:  h ug </w>
2×:  p ug </w>
2×:  b ug </w>

$V_{1} = {h, u, g, p, b, </w>, ug}$ → size = 7

Iteration 2: Pairs count karo

(ug, </w>): hug(×1) + pug(×2) + bug(×2) = 5 ← merge
(h, ug): 1, (p, ug): 2, (b, ug): 2

(ug, </w>) merge karo → ug</w> (full-word-ending token!)

1×:  h ug</w>
2×:  p ug</w>
2×:  b ug</w>

$V_{2} = {h, u, g, p, b, </w>, ug, ug</w>}$ → size = 8

Iteration 3: Pairs count karo

(b, ug</w>): bug(×2) = 2 ← merge ((p, ug</w>) ke saath tie; alphabetical wins)
(p, ug</w>): pug(×2) = 2
(h, ug</w>): hug(×1) = 1

(b, ug</w>) merge karo → bug</w>

1×:  h ug</w>
2×:  p ug</w>
2×:  bug</w>

$V_{3} = {h, u, g, p, b, </w>, ug, ug</w>, bug</w>}$ → size = 9

Iteration 4: Pairs count karo

(p, ug</w>): pug(×2) = 2 ← merge

(p, ug</w>) merge karo → pug</w>

Final vocab ( $V = 10$ ): $V = {h, u, g, p, b, </w>, ug, ug</w>, bug</w>, pug</w>}$

Learned merge rules (order mein):

1. u g → ug
2. ug </w> → ug</w>
3. b ug</w> → bug</w>
4. p ug</w> → pug</w>

Naye word "hugs" ko encode karna:

Input: h u g s </w>
Apply rule 1: h ug s </w>
No more rules apply (no ug</w> because 's' interrupts).
Output: [h, ug, s, </w>]

"hug" kyun nahi bana? Pair (ug, </w>) yahaan kabhi adjacent nahi hota (kyunki s, ug aur </w> ke beech hai). BPE unseen word ko gracefully decompose karta hai.

Common mistake Common Mistake: Merges Ko Out of Order Apply Karna

Galat approach: Saari merge rules simultaneously apply karo, ya encoding ke time frequency order mein apply karo.

Kyun sahi lagta hai: "Zyada frequent merges ki priority zyada honi chahiye, hai na?"

Kyun galat hai: Baad ke merge rules pehle waalon par depend karte hain. Agar aapne es seekha phir est (usi order mein), lekin encoding ke dauran aap dono ek saath apply karne ki koshish karo, to galat tokenization milegi.

Example:

Merge rules: (e, s) → es (pehle seekha), (es, t) → est (baad mein seekha)
Word: "est"
Galat: (e, s) aur (es, t) simultaneously dhundne ki koshish → es pair nahi milega kyunki es abhi exist hi nahi karta
Sahi: Pehle rule 1 apply karo: e s t → es t, phir rule 2 apply karo: es t → est

Fix: Rules ko ek priority queue mein learning iteration ke anusaar store karo, sequentially apply karo.

Common mistake Misconception: BPE "Meaningful" Morphemes Discover Karta Hai

Belief: BPE linguistic morphology (prefixes, suffixes, roots) seekhta hai.

Kyun sahi lagta hai: Aap vocabulary mein "walk" + "ing" → "walking" dekhte hain. Morphology jaisa lagta hai!

Reality: BPE purely statistical hai. Yeh frequent pairs merge karta hai, jo often morphology ke saath align hote hain (kyunki morphology frequency patterns create karti hai), lekin isko linguistics ka koi gyaan nahi hai. Aap "cat" vs "cata" + "log" jaisi splits bhi dekhenge jo linguistic boundaries tod deti hain.

Jab yeh matter karta hai: Expect mat karo ki BPE morphological rules ko unseen combinations par generalize karega. Yeh empirically kaam karta hai kyunki frequency ≈ linguistic structure hai, na ki isliye ki yeh grammar model karta hai.

Recall BPE Ko Ek 12-Saal Ke Bachche Ko Explain Karo

Socho tum apne friend group ke messages ke liye ek secret code bana rahe ho. Tum kar sakte ho:

Poore words use karo: "pizza" = ek code. Lekin tumhe har possible word ke liye MILLIONS of codes chahiye honge, aur jab koi naya slang word invent hoga, tum stuck ho jaoge!
Letters use karo: "p" "i" "z" "z" "a" = 5 codes. Total sirf 26 codes (letters), lekin ab har message super long ho jaata hai!
BPE approach: Letters se shuru karo. Notice karo ki tum "th" BAHUT BAAR saath type karte ho? "th" ka apna code banao. "the" notice karo? Use ek code banao. Jinhe tum sabse zyada use karte ho unhe combine karte raho jab tak exactly 10,000 codes na ho jaayein. Ab "the" 1 code hai, "pizza" shayad "pizz" + "a" (2 codes) ho sakta hai, aur jab tumhara friend "supercalifragilistic" text karta hai, tum ise un parts mein tod dete ho jo tumne pehle dekhe hain: "super" + "cal" + "i" + "frag" + "il" + "istic".

Jadu: Tumhare 10,000 codes pieces mix aur match karke INFINITE words handle kar sakte hain. Common words = kam pieces (fast). Rare words = zyada pieces (phir bhi kaam karta hai).

Modern BPE Variants

WordPiece (BERT)

BPE jaisa hi hai lekin har merge ko training corpus likelihood maximize karne ke liye choose karta hai ek unigram language model ke under
Concretely, yeh woh pair choose karta hai jiska merge log-likelihood mein sabse bada increase deta hai, $Δ lo g P (corpus)$ . Unigram model ke liye yeh closely ratio $\frac{P ( ab )}{P ( a ) P ( b )}$ (pointwise mutual information) se related hai, lekin exact criterion likelihood gain hai, raw PMI nahi.
Kyun: Behtar theoretical grounding (har merge isko choose kiya jaata hai ki data zyada probable ho, na ki sirf zyada compressed)

SentencePiece (T5, LLaMA)

Input ko raw byte/character stream treat karta hai (whitespace par koi pre-tokenization nahi)
BPE (ya unigram LM) directly Unicode characters ya bytes par seekhta hai
Kyun: Language-agnostic, spaces ko normal symbols treat karta hai, un languages ke liye kaam karta hai jahan clear word boundaries nahi hain

Byte-level BPE (GPT-2, GPT-3)

BPE ko bytes (UTF-8 encoded) par run karta hai characters ki jagah
Base vocab = 256 bytes, phir merge karo
Kyun: Truly universal (kisi bhi language mein koi bhi text), koi special handling ki zaroorat nahi

BPE In Practice: Hyperparameters

Parameter	Typical Range	Effect
Vocab size $V$	10k-50k	Bada → zyada lamba training, chhotas sequences, zyada rare-word memorization
Min frequency	2-10	Rare pairs filter karo training speed up karne ke liye
Pre-tokenization	Word/byte	Word-level: words intact rakhta hai (GPT-2 spaces + punctuation par split karta hai)
Special tokens	`[PAD]`, `[UNK]`, `[CLS]`, etc.	Vocab mein alag se add hote hain, kabhi merge nahi hote

The 80/20: 30k vocab, min frequency = 2, byte-level pre-tokenization zyaatar modern LM needs cover karta hai.

Connections

4.2.01-Tokenization-Overview: BPE teen major tokenization strategies mein se ek hai
4.2.03-WordPiece-Tokenization: Variant jo raw frequency ki jagah likelihood gain use karta hai
4.2.04-SentencePiece: Unigram LM + BPE bina pre-tokenization ke
4.3.01-Language-Model-Basics: Tokenization LMs ke liye preprocessing hai; vocab size model size affect karta hai
3.1.05-Embedding-Layer: Vocab size $V$ embedding matrix size determine karta hai $(V \times d)$
6.2.02-Inference-Optimization: Chhota vocab → kam embedding lookups → faster inference

#flashcards/ai-ml

Byte-Pair Encoding (BPE) ki core idea kya hai?

BPE ek data compression algorithm hai jo vocabulary ko iteratively most frequent character pairs merge karke seekhta hai, aur subword units create karta hai jo vocabulary size aur rare words represent karne ki ability ke beech balance banate hain.

BPE training ke teen steps kya hain?

1. Character-level vocabulary se initialize karo. 2. Iteratively most frequent adjacent pair merge karo aur vocabulary mein add karo. 3. Jab target vocabulary size reach ho jaaye tab ruko.

BPE words ki jagah characters se kyun shuru karta hai?

Characters se shuru karna guarantee karta hai ki KISI BHI input text ko encode kiya ja sakta hai (koi unknown tokens nahi), aur phir is universal base se frequent patterns build hote hain.

BPE encoding ke dauran, merge rules ko usi order mein kyun apply karna zaroori hai jisme yeh seekhe gaye the?

Kyunki baad ke merge rules pehle waalon par depend karte hain. Example ke taur par, "es" ko "est" merge hone se pehle create hona chahiye. Out of order apply karne se dependency chain toot jaati hai.

BPE sequence length average token length k ke saath kaise scale karti hai?

Roughly linearly: L_BPE ≈ C/k, jahan C characters mein corpus length hai aur k average characters per token hai. Yeh vocabulary size ke saath logarithmically scale nahi karta.

BPE out-of-vocabulary words kaise handle karta hai?

BPE mein koi sachchi OOV problem nahi hai. Kisi bhi word ko subword tokens mein decompose kiya ja sakta hai, zaroorat padne par individual characters tak. Rare words subword pieces ki sequences ban jaate hain.

BPE aur WordPiece mein kya fark hai?

BPE woh pair merge karta hai jiska raw frequency sabse zyada ho. WordPiece woh pair merge karta hai jo unigram model ke under corpus likelihood mein increase maximize karta hai (Δ log-probability), jo raw PMI se related hai lekin identical nahi.

Modern LLMs (GPT-2, GPT-3) byte-level BPE kyun use karte hain?

Bytes (UTF-8 encoding) par operate karna tokenization ko language-agnostic aur universal banata hai. Base vocab exactly 256 bytes hai, aur yeh bina special cases ke kisi bhi language mein koi bhi text handle karta hai.

Common mistake: Encoding ke dauran saari BPE merge rules simultaneously kyun apply nahi kar sakte?

Kyunki merge rules ki dependencies hoti hain. "es" exist karna chahiye "est" create karne se pehle. Simultaneous application dependent pairs dhundne mein fail ho jaati. Rules ko learning order mein sequentially apply karna zaroori hai.