M5-002M5: NLP & Large Language ModelsTokenization (BPE / WordPiece / Unigram)Easy
⚡Flashcard Drill➔Mastery:

Comparison of BPE, WordPiece, and Unigram Tokenization

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M5-003 →
📐 Mathematical Definition
WordPiece score(a,b)=count(ab)count(a)count(b);Unigram:L=∑log⁡p(subword)\text{WordPiece score}(a,b)=\frac{\mathrm{count}(ab)}{\mathrm{count}(a)\mathrm{count}(b)};\qquad \text{Unigram}: \mathcal{L}=\sum\log p(\text{subword})
⚡ One-Sentence Core Answer
BPE merges subwords based on raw co-occurrence frequency, WordPiece merges subwords based on mutual information (maximum likelihood), and Unigram prunes a large initial candidate pool based on sentence-level likelihood loss.

📌 Key Takeaways

  • •
    BPE: bottom-up; greedy merge maximizing co-occurrence frequency count(ti,tj)\text{count}(t_i, t_j); deterministic and simple (GPT, LLaMA, RoBERTa)
  • •
    WordPiece: bottom-up; greedy merge maximizing training corpus unigram likelihood improvement count(ti,tj)count(ti)count(tj)\frac{\text{count}(t_i, t_j)}{\text{count}(t_i) \text{count}(t_j)} (BERT)
  • •
    Unigram: top-down; starts with a massive vocabulary and iteratively prunes tokens that cause the smallest drop in corpus unigram language model likelihood (SentencePiece, T5, LLaMA-3)

📐 Mathematical Derivations

Mathematical Mechanism: 1. BPE Merge Criterion: Score(ti,tj)=Freq(ti,tj)\text{Score}(t_i, t_j) = \text{Freq}(t_i, t_j) Merges the pair that occurs most frequently in the raw text corpus. 2. WordPiece Merge Criterion: Evaluates the increase in corpus log-likelihood when merging tit_i and tjt_j: Score(ti,tj)=Freq(ti,tj)Freq(ti)×Freq(tj)\text{Score}(t_i, t_j) = \frac{\text{Freq}(t_i, t_j)}{\text{Freq}(t_i) \times \text{Freq}(t_j)} This measures Pointwise Mutual Information (PMI). High-frequency individual tokens (like 'the') are penalized unless their combination appears far more frequently than independent chance. 3. Unigram Pruning Criterion: Assumes independent unigram probabilities p(t)=count(t)Np(t) = \frac{\text{count}(t)}{N}. Corpus log-likelihood is L=∑xlog⁡P(x)=∑xlog⁡(max⁡S∈Seg(x)∏t∈Sp(t))\mathcal{L} = \sum_{x} \log P(x) = \sum_{x} \log \left( \max_{S \in \text{Seg}(x)} \prod_{t \in S} p(t) \right). For each candidate token tt: compute the drop in likelihood ΔLt=LV−LV∖{t}\Delta \mathcal{L}_t = \mathcal{L}_{\mathcal{V}} - \mathcal{L}_{\mathcal{V} \setminus \{t\}}. The bottom p%p\% (e.g., 10–20%10\text{--}20\%) of tokens with the smallest ΔLt\Delta \mathcal{L}_t are pruned. Repeats until target size VV is reached.

🏭 Production Trade-offs

Deep Dive & Engineering Trade-offs: ① Deterministic vs Probabilistic Segmentation: BPE and WordPiece are bottom-up greedy algorithms yielding a single deterministic segmentation per word. Unigram naturally models a probability distribution over multiple valid segmentations for a sentence, enabling subword regularization (sampling different segmentations during training to boost robustness). ② Inference Complexity: BPE applies ordered merge rules (O(Llog⁡∣V∣)O(L \log |\mathcal{V}|)). Unigram uses the Viterbi algorithm over a dynamic programming trellis to find the most probable token sequence in O(L⋅Lmax⁡)O(L \cdot L_{\max}). ③ SentencePiece Library Dominance: Google's SentencePiece library implements both BPE and Unigram natively in C++, treating whitespace as a regular character (_ or ) to avoid language-dependent pre-tokenization. ④ Subword Regularization: Unigram sampling introduces data augmentation during training: the same sentence 'unhappiness' can be seen as ['un', 'happiness'] or ['un', 'happy', 'ness'], dramatically reducing overfitting on rare words. ⑤ Interview Strategy: Contrast bottom-up merging (BPE/WordPiece) with top-down pruning (Unigram), compare the score metrics (Frequency vs PMI vs Likelihood Drop), and explain subword regularization.
⚠️ Common Interview Pitfalls
  • ✕
    Believing WordPiece merges tokens based on raw frequency like BPE (WordPiece normalizes by individual token frequencies via PMI)
  • ✕
    Assuming Unigram builds its vocabulary bottom-up (Unigram is top-down pruning from an oversized initial candidate set)
  • ✕
    Overlooking that Unigram natively supports subword regularization via Viterbi trellis sampling
🎯 Interviewer Follow-up Inquiries
  • ?
    How does Unigram's Viterbi segmentation find the globally optimal subword breakdown for a sentence?
  • ?
    Why does subword regularization improve downstream translation and classification accuracy?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM5-001: BPE Algorithm and Why It Is Widely Used in LLMs📋 Back to BankNext →M5-003: Vocabulary Size Trade-offs in LLMs