Tokenization & Language Modeling

Question 1 (12 marks)

Initial symbol sequences with frequencies:

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

(a) Merge 1 (4 marks): Count adjacent pairs across the weighted corpus.

• l o: 5+2 = 7
• o w: 5+2 = 7
• w _: 5 (from low_)
• w e: 2 (lower) + 6 (newest) = 8
• e s: 6+3 = 9
• s t: 6+3 = 9
• t _: 6+3 = 9

Top pairs tie at 9: e s, s t, t _. Break ties by first occurrence / lexicographic — take e s (accept any of the 9-count pairs with justification). Winning pair: e s, count 9 → new symbol es. (2 marks for correct top count of 9; 2 marks for valid identification and tie-handling.)

Updated: n e w es t _ ×6, w i d es t _ ×3.

Merge 2 (4 marks): Recount.

• es t: 6+3 = 9 (now es followed by t)
• s t no longer exists (s absorbed).
• Other candidates: l o=7, o w=7, w e=8, t _=9.

Top count 9: es t and t _. Take es t, count 9 → new symbol est. (2 marks count, 2 marks identification.)

Full marks awarded for any internally consistent tie-break yielding correct counts.

(b) (2 marks): After merges es then est: newest_ → n e w est _. (2 marks)

(c) (2 marks): The _ marker preserves word boundaries so merges do not span two words, keeping tokens morphologically meaningful and allowing detokenization (reconstructing spaces). (2 marks for any valid reason.)

Question 2 (14 marks)

(a) (4 marks): Tied embedding = one matrix of size $V \times d$.

• Vocab A: $8000 \times 1024 = 8{,}192{,}000$ ≈ 8.19M params.
• Vocab B: $50000 \times 1024 = 51{,}200{,}000$ ≈ 51.2M params. (2 marks each.)

(b) (4 marks): Tokens per epoch = words × tokens/word.

• Vocab A: $6.25\text{B} \times 1.60 = 10.0\text{ billion tokens}$.
• Vocab B: $6.25\text{B} \times 1.15 = 7.1875\text{ billion tokens}$. (2 marks each.)

(c) (6 marks):

• Extra embedding cost: $51.2\text{M} - 8.19\text{M} = 43.008\text{M}$ params (≈ 43.0M extra). (2)
• Token reduction: $(10.0 - 7.1875)/10.0 = 0.28125 = 28.125\%$ fewer tokens. (2)
• Recommendation: Vocab B — a ~28% reduction in sequence tokens lowers training/inference compute (attention is superlinear in sequence length) and the extra ~43M embedding params are modest relative to full model size; the shorter sequences also fit more content per context window. (2 for reasoned recommendation; accept Vocab A if student argues small-model / rare-token / memory constraints.)

Question 3 (14 marks)

(a) (6 marks): Cross-entropy in bits/token: $H = -\frac{1}{5}\sum \log_2 p_i$.

$\log_2$ values: $0.5\to-1$, $0.25\to-2$, $0.1\to-3.3219$, $0.4\to-1.3219$, $0.2\to-2.3219$.

Sum of $-\log_2 p = 1 + 2 + 3.3219 + 1.3219 + 2.3219 = 9.9658$ bits. $H = 9.9658/5 = 1.9932$ bits/token. (3 marks)

Perplexity $= 2^{H} = 2^{1.9932} = 3.9811$ (equivalently geometric mean of $1/p$). PPL ≈ 3.98. (3 marks)

(b) (4 marks): $\text{PPL} = \exp(-\overline{\ln p})$, so $\overline{\ln p} = -\ln(\text{PPL}) = -\ln 8 = -2.0794$. Average per-token log-prob ≈ −2.079 nats. (4 marks)

(c) (4 marks): Causal PPL uses factorized probabilities $\prod p(x_t \mid x_{<t})$ — a proper joint over the sequence (left context only). MLM predicts each masked token conditioned on both left and right context, and does not define a normalized joint distribution over the whole sequence (pseudo-likelihood). Hence MLM "perplexity" measures a different quantity and is not on the same scale as autoregressive PPL. (2 marks conditioning difference, 2 marks no valid joint / non-comparable.)

Question 4 (12 marks)

(a) (6 marks): $0.15 \times 7 = 1.05 \to 1$ token selected. Given selection, outcomes:

• Replaced by [MASK]: probability 0.80.
• Replaced by a random token: probability 0.10.
• Left unchanged (kept original): probability 0.10. (2 marks each outcome+probability.)

(b) (4 marks): [MASK] never appears at fine-tuning/inference time, so training only on [MASK] creates a pretrain–finetune distribution mismatch. The 10% random forces the model to use context to judge every token (not just masked positions) and be robust to corrupted input; the 10% unchanged biases the model toward the actual observed token so representations stay accurate for real (non-masked) inputs. (2 marks mismatch, 2 marks role of the two rules.)

(c) (2 marks): NSP mixes topic prediction (easy) with coherence, and the negative "next sentence" is usually from a different document, so it collapses to trivial topic matching — a weak signal that a strong MLM already learns. (2 marks any valid reason.)

Question 5 (8 marks)

(a) (4 marks): $\lceil 10000/4096 \rceil = 3$ forward passes (chunks of 4096, 4096, and remainder). Final chunk $= 10000 - 2\times4096 = 10000 - 8192 = 1808$ tokens. 3 passes; final chunk 1808 tokens. (2+2)

(b) (4 marks): Doubling window: per-window attention scales as $n^2$, so factor $= 2^2 = 4\times$. Chunks needed: $\lceil 10000/8192 \rceil = 2$ chunks (was 3), factor $\approx 2/3 \approx 0.67\times$. Net: attention compute per full pass over the document ≈ $4 \times \frac{2}{3} \approx 2.67\times$ higher — the quadratic per-window growth dominates the fewer-chunks saving. (2 marks factor 4, 1 chunk factor, 1 net comment.)

[
  {"claim":"BPE first merge es and second merge est both have count 9","code":"corpus={('l','o','w','_'):5,('l','o','w','e','r','_'):2,('n','e','w','e','s','t','_'):6,('w','i','d','e','s','t','_'):3}\nfrom collections import Counter\ndef pc(c):\n    p=Counter()\n    for w,f in c.items():\n        for i in range(len(w)-1):\n            p[(w[i],w[i+1])]+=f\n    return p\np=pc(corpus)\nm1=max(p.values())\nresult=(m1==9 and p[('e','s')]==9)"},
  {"claim":"Vocab embedding params and token reduction 28.125%","code":"A=8000*1024; B=50000*1024\nextra=B-A\ntokA=6.25e9*1.60; tokB=6.25e9*1.15\nred=(tokA-tokB)/tokA*100\nresult=(A==8192000 and B==51200000 and abs(red-28.125)<1e-6)"},
  {"claim":"Sequence perplexity approx 3.9811 and CE 1.9932 bits","code":"import math\nps=[0.5,0.25,0.1,0.4,0.2]\nH=-sum(math.log2(p) for p in ps)/len(ps)\nppl=2**H\nresult=(abs(H-1.9931569)<1e-4 and abs(ppl-3.98107)<1e-3)"},
  {"claim":"Model2 avg ln prob = -ln8","code":"import math\nv=-math.log(8)\nresult=abs(v+2.0794415)<1e-6"},
  {"claim":"Context chunks: 3 passes, final 1808; doubled net factor 8/3","code":"import math\npasses=math.ceil(10000/4096); final=10000-2*4096\np2=math.ceil(10000/8192); net=4*(p2/passes)\nresult=(passes==3 and final==1808 and p2==2 and abs(net-8/3)<1e-9)"}
]