Tokenization & Language Modeling

Question 1 (12)

(a) BPE iteratively finds the most frequent adjacent pair of symbols in the corpus and merges it into a single new token, repeating until the target vocab size is reached. (2)

(b) Words as symbol sequences with counts:

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

Count candidate pairs:

Merge 1: count pairs —

• e s: newest(6) + widest(3) = 9 ← highest
• s t: 6 + 3 = 9 (tie)
• l o: 5+2=7; o w: 7; w </w>: 5

e s and s t tie at 9. Choose e s (either acceptable if consistent). Merge 1 = es (count 9). (2)

After: n e w es t </w>×6, w i d es t </w>×3.

Merge 2: now es t = 6+3 = 9 highest → Merge 2 = est (count 9). (2)

After: n e w est </w>×6, w i d est </w>×3.

Merge 3: est </w> = 6+3 = 9 highest → Merge 3 = est</w> (count 9). (3)

(Accept es → est → est</w>; award full marks for correct counts and greedy selection even if the initial tie is broken toward st provided the chain is consistent.)

(c) BPE builds subword units; unseen words decompose into known subwords (or ultimately characters), so there are no OOV tokens — every string is representable, while a fixed word vocab maps unseen words to a single <UNK>, losing information. (3)

Question 2 (11)

(a) CLM loss (per-token cross-entropy in nats): $H = -\frac{1}{T}\sum_{t=1}^{T}\ln p(x_t\mid x_{<t})$ Perplexity is the exponential of average cross-entropy: $PP = \exp(H) = \left(\prod_t p(x_t\mid x_{<t})\right)^{-1/T}$ (geometric mean of inverse probabilities). Base must match: $2^{H_2}$ if $H$ is in bits. (3)

(b) Product of probs = $0.5\cdot0.25\cdot0.1\cdot0.4 = 0.005$. $PP = 0.005^{-1/4} = (200)^{1/4}$ $200^{1/4} = (200)^{0.25}$. $\sqrt{200}\approx14.142$, $\sqrt{14.142}\approx3.761$. $PP \approx 3.76$ (5) (marks: product 1, inverse & 1/T exponent 2, numeric answer 2)

(c) $PP = 1.0 \Rightarrow$ the model assigned probability 1 to every correct token (perfect prediction). In practice this signals data leakage / train-test contamination or a degenerate/trivial task, not a genuinely perfect language model. (3)

Question 3 (10)

(a) Causal LM (autoregressive, next-token): $\mathcal{L}_{CLM} = -\sum_{t=1}^{T}\ln p_\theta(x_t \mid x_{<t})$ Masked LM: let $M\subseteq\{1,\dots,T\}$ be masked positions: $\mathcal{L}_{MLM} = -\sum_{t\in M}\ln p_\theta(x_t \mid x_{\setminus M})$ Symbols: $x_t$ token at position $t$; $x_{<t}$ preceding tokens; $x_{\setminus M}$ = all tokens except masked ones (bidirectional context); $\theta$ params. (6) (3 each; 1 for def of symbols)

(b) MLM conditions on bidirectional context (both left and right), so it has no natural left-to-right factorization and predicts only masked positions given the whole sentence — it cannot generate token-by-token because it "sees the future." Causal LM factorizes the joint as $\prod p(x_t\mid x_{<t})$, letting you sample one token at a time from left to right. (4)

Question 4 (10)

(a) (i) Input embedding: $V\times d = 50000\times768 = 38{,}400{,}000$. (ii) Output projection: same shape $50000\times768 = 38{,}400{,}000$. (3)

(b) Tying shares one matrix, eliminating the second → save 38,400,000 parameters. (2)

(c) (5)

class TiedLM(nn.Module):
    def __init__(self, V, d):
        super().__init__()
        self.embed = nn.Embedding(V, d)
        # no separate output weight; tie to embedding
    def forward(self, ids, hidden):
        x = self.embed(ids)                  # (B,T,d)
        logits = hidden @ self.embed.weight.T  # (B,T,V), tied
        return logits

Key point: output projection uses self.embed.weight.T — same tensor, so gradients update one shared matrix. (5)

Question 5 (9)

(a) Benefit: larger vocab → fewer tokens per sentence (shorter sequences, faster/longer effective context, better handling of rare words). (1) Costs: (i) larger embedding + softmax matrices → more parameters & memory; (ii) each token seen less often → sparser training signal / rarer tokens undertrained; (also acceptable: bigger output softmax compute). (3)

(b) Cost ∝ $T^2$: ratio $= (4096/2048)^2 = 2^2 = 4$. Grows 4×. (2)

(c) For fixed text, a larger vocabulary compresses text into fewer tokens (shorter sequences → more content fits in a fixed context window); a smaller vocabulary splits into more subwords (longer sequences, context fills faster). (3)

Question 6 (8)

(a) NSP: input is two segments A and B packed as [CLS] A [SEP] B [SEP]. The [CLS] representation is classified as IsNext (B genuinely follows A, positive) or NotNext (B is a random sentence from the corpus, negative). Positives = consecutive sentences; negatives = 50% random sentence. (4) (2 input/labels, 2 pair construction)

(b) Any two: (i) The task is too easy — topic mismatch of a random sentence makes it solvable by topic, not by coherence, so little signal. (ii) It conflates topic prediction with coherence. (iii) Removing NSP and training on longer contiguous text (full-sentences/doc-level) matched or improved downstream performance (RoBERTa finding). (iv) NSP negatives introduce noise into segment embeddings. (4) (2 each)

[
  {"claim":"BPE merge pair 'es' has corpus count 9",
   "code":"newest=6; widest=3; result=(newest+widest==9)"},
  {"claim":"Perplexity of probs 0.5,0.25,0.1,0.4 is 200**0.25 approx 3.761",
   "code":"import sympy as sp; p=sp.Rational(5,1000); PP=p**(-sp.Rational(1,4)); result=abs(float(PP)-3.7606)<0.001"},
  {"claim":"Embedding params for V=50000,d=768 equal 38.4M",
   "code":"result=(50000*768==38400000)"},
  {"claim":"Doubling context from 2048 to 4096 grows T^2 attention cost 4x",
   "code":"result=((4096/2048)**2==4)"}
]