Noesis
Level 5 — MasteryTokenization & Language Modeling

Tokenization & Language Modeling

⏱ 90 minutes60 marksprintable — key stays hidden on paper

Level: 5 (Mastery — cross-domain: math + information theory + coding) Time limit: 90 minutes Total marks: 60

Instructions: Answer all three questions. Show all derivations. Where code is requested, use clean Python with NumPy-level pseudocode acceptable but logic must be exact. Use ...... notation for mathematics.

Question 1 — BPE Merges, Vocabulary Tradeoffs & Embedding Cost (20 marks)

You are training a byte-level BPE tokenizer on a toy corpus. After pre-tokenization the training word-frequency table is:

word frequency
low 5
lower 2
newest 6
widest 3

Treat each word as a sequence of characters with an end-of-word marker </w> appended (e.g. low</w> → l o w </w>).

(a) Perform the first three BPE merge operations. For each step, list the full pair-frequency count of the candidate pairs, state the winning pair (break ties alphabetically by the pair's first-then-second symbol), and give the merged symbol. (9 marks)

(b) After these 3 merges, tokenize the unseen word lowest</w> using the learned merges (applied greedily in learned order). Give the final token sequence. (3 marks)

(c) A production model has embedding dimension d=1024d = 1024 and a vocabulary of size VV. The model uses weight tying between the input embedding and the output projection. Write the parameter count for (i) untied and (ii) tied, as functions of VV and dd (ignore bias). If moving from a character vocabulary (V=256V=256) to a BPE vocabulary (V=50,000V=50{,}000) increases the average tokens-per-word ratio benefit but grows the embedding table, compute the extra embedding parameters saved by tying at V=50,000V=50{,}000. (5 marks)

(d) State one concrete downside of an overly large vocabulary and one downside of an overly small vocabulary, each tied to a quantitative effect (parameters, sequence length, or rare-token statistics). (3 marks)

Question 2 — Causal LM, Cross-Entropy & Perplexity (22 marks)

A causal language model assigns probabilities autoregressively: P(w1,…,wT)=∏t=1TP(wt∣w<t).P(w_1,\dots,w_T) = \prod_{t=1}^{T} P(w_t \mid w_{<t}).

(a) Derive the relationship between the corpus token-averaged cross-entropy loss L\mathcal{L} (in nats) and perplexity PPL\mathrm{PPL}. State the loss in bits and give the perplexity in that case too. (4 marks)

(b) A model is evaluated on the 5-token sequence [the, cat, sat, on, mat]. The predicted probabilities assigned to the correct next token at each position are: 0.5,  0.25,  0.4,  0.1,  0.2.0.5,\; 0.25,\; 0.4,\; 0.1,\; 0.2. Compute (i) the total negative log-likelihood in nats, (ii) the per-token cross-entropy, and (iii) the perplexity. Give numeric answers to 3 significant figures. (7 marks)

(c) Prove that perplexity is invariant under a change of logarithm base used internally (i.e. the metric value is the same whether cross-entropy is computed in nats or bits), and explain why a uniform model over a vocabulary of size VV has perplexity exactly VV. (5 marks)

(d) Write a correct Python function perplexity(logprobs) that takes a list of natural-log probabilities of the correct tokens and returns the perplexity. Then explain in 2–3 sentences why perplexities are only comparable across models that share the same tokenization (relate this to tokens-per-word). (6 marks)

Question 3 — MLM vs CLM Objectives & Expected Loss (18 marks)

(a) Contrast the training objectives of a masked language model (BERT-style) and a causal language model. For each, write the loss as an expectation/summation over the relevant token positions, and state precisely which tokens contribute to the gradient. (6 marks)

(b) BERT masks 15% of tokens. Of those chosen positions, 80% are replaced with [MASK], 10% with a random token, and 10% left unchanged. For a sequence of n=100n=100 tokens, compute the expected number of tokens that (i) contribute to the MLM loss, (ii) are shown as [MASK], (iii) are corrupted with a random token. Explain the purpose of the 10%-random and 10%-unchanged design. (6 marks)

(c) Consider Next Sentence Prediction (NSP) as a balanced binary task (p=0.5p=0.5 positive). A model that outputs a constant probability qq for "IsNext" regardless of input has expected cross-entropy H(q)=−12ln⁡q−12ln⁡(1−q)H(q) = -\tfrac{1}{2}\ln q - \tfrac{1}{2}\ln(1-q). Prove that this is minimized at q=0.5q=0.5 and give the minimum loss value in nats. State what this minimum represents operationally. (6 marks)

Answer keyMark scheme & solutions

Question 1

(a) Three BPE merges (9 marks)

Initial symbol sequences with frequencies:

  • low</w> → l o w </w> (5)
  • lower</w> → l o w e r </w> (2)
  • newest</w> → n e w e s t </w> (6)
  • widest</w> → w i d e s t </w> (3)

Merge 1 — pair counts:

  • l o: 5+2 = 7
  • o w: 5+2 = 7
  • w </w>: 5
  • w e: 2+6 = 8
  • e r: 2, r </w>: 2
  • n e: 6, e w: 6
  • e s: 6+3 = 9 ← highest
  • s t: 6+3 = 9 (tie), t </w>: 9 (tie)
  • w i:3, i d:3, d e:3

Highest = 9, tie among e s, s t, t </w>. Alphabetical by first symbol: e < s < t, so merge e s → es. (3 marks)

Sequences now: newest → n e w es t </w>, widest → w i d es t </w>.

Merge 2 — pair counts:

  • w e: 8 (from lower 2 + newest n e w es gives w e? newest is now n e w es t, contains w es=6). Recompute:
    • l o:7, o w:7, w e(lower):2, w es(newest):6, es t:6+3=9 ← highest, s… gone.
    • t </w>: 6+3=9 (tie)

Highest = 9, tie es t vs t </w>. First symbols: es vs t; e < t, so merge es t → est. (3 marks)

Sequences: newest → n e w est </w>, widest → w i d est </w>.

Merge 3 — pair counts:

  • l o: 7 ← highest
  • o w: 7 (tie), w </w>:5, w e:2, e r:2, r</w>:2
  • n e:6, e w:6, w est:6, est </w>:6+3=9 ← highest!

Recount top: est </w>: newest(6)+widest(3)=9. That's highest. Merge est </w> → est</w>. (3 marks)

(Award marks for correct method even if a defensible tie-break differs, provided rule stated consistently.)

Learned merges (order): es, est, est</w>.

(b) Tokenize lowest</w> (3 marks)

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

  • Apply es: l o w es t </w>
  • Apply est (es+t): l o w est </w>
  • Apply est</w> (est+</w>): l o w est</w>

Final: l o w est</w> (3 marks)

(c) Embedding parameters & tying (5 marks)

  • (i) Untied: input embedding V⋅dV\cdot d + output projection V⋅dV\cdot d = 2Vd2Vd. (1)
  • (ii) Tied: shares one matrix → VdVd. (1)
  • Saved by tying = Vd=50000×1024=51,200,000Vd = 50000 \times 1024 = 51{,}200{,}000 parameters. (3)

(d) Vocabulary tradeoffs (3 marks)

  • Too large: embedding + softmax table grows as VdVd → many rows are rare, poorly trained (sparse gradient statistics); memory/compute cost. (1.5)
  • Too small: words fragment into many subtokens → longer sequences → higher compute (O(T2)O(T^2) attention) and longer dependency chains, worse modeling of long-range structure. (1.5)

Question 2

(a) Loss–perplexity relation (4 marks)

Per-token cross-entropy in nats: L=−1T∑tln⁡P(wt∣w<t)\mathcal{L} = -\frac{1}{T}\sum_t \ln P(w_t\mid w_{<t}). PPL=exp⁡(L).\mathrm{PPL} = \exp(\mathcal{L}). (2) In bits: L2=L/ln⁡2\mathcal{L}_2 = \mathcal{L}/\ln 2, and PPL=2L2\mathrm{PPL} = 2^{\mathcal{L}_2} — the same value. (2)

(b) Numeric computation (7 marks)

Probabilities: 0.5,0.25,0.4,0.1,0.20.5, 0.25, 0.4, 0.1, 0.2.

(i) NLL (nats): −(ln⁡0.5+ln⁡0.25+ln⁡0.4+ln⁡0.1+ln⁡0.2)-(\ln 0.5 + \ln 0.25 + \ln 0.4 + \ln 0.1 + \ln 0.2) =−(−0.6931−1.3863−0.9163−2.3026−1.6094)=6.9077= -(-0.6931 -1.3863 -0.9163 -2.3026 -1.6094) = 6.9077 nats. (3)

(ii) Per-token CE =6.9077/5=1.3815= 6.9077/5 = 1.3815 nats. (2)

(iii) PPL=e1.3815=3.981≈3.98\mathrm{PPL} = e^{1.3815} = 3.981 \approx 3.98. (Equivalently geometric mean of probs =(0.5⋅0.25⋅0.4⋅0.1⋅0.2)1/5=(0.001)0.2=0.2512=(0.5\cdot0.25\cdot0.4\cdot0.1\cdot0.2)^{1/5}=(0.001)^{0.2}=0.2512, reciprocal =3.98=3.98.) (2)

(c) Base invariance & uniform model (5 marks)

Let HeH_e be per-token CE in nats, H2=He/ln⁡2H_2 = H_e/\ln 2 in bits. exp⁡(He)=exp⁡(H2ln⁡2)=2H2.\exp(H_e) = \exp(H_2 \ln 2) = 2^{H_2}. So computing PPL as bHbb^{H_b} where HbH_b is entropy in base bb yields the same number for any bb; the base cancels. (3)

Uniform model: P=1/VP = 1/V for each token, so per-token CE =−ln⁡(1/V)=ln⁡V= -\ln(1/V) = \ln V (nats), and PPL=eln⁡V=V\mathrm{PPL} = e^{\ln V} = V: the model is "as confused as choosing uniformly among VV options." (2)

(d) Code + comparability (6 marks)

import math
def perplexity(logprobs):
    # logprobs: natural log of P(correct token) at each position
    n = len(logprobs)
    mean_nll = -sum(logprobs) / n
    return math.exp(mean_nll)

(4 marks: correct averaging + exp; -1 if uses sum not mean, -1 if wrong sign.)

Comparability (2): PPL is per-token; a tokenizer that splits words into more subtokens lowers per-token perplexity (each prediction is "easier") without the model being genuinely better. Only models with identical tokenization (hence identical tokens-per-word and identical token count TT) can be fairly compared; otherwise convert to per-word or per-character bits.

Question 3

(a) MLM vs CLM objectives (6 marks)

CLM: LCLM=−1T∑t=1Tln⁡Pθ(wt∣w<t)\mathcal{L}_{\text{CLM}} = -\frac{1}{T}\sum_{t=1}^{T}\ln P_\theta(w_t\mid w_{<t}). Every position contributes; strictly left-to-right (causal mask), so no future leakage. (3)

MLM: Let MM be the set of masked positions. LMLM=−1∣M∣∑i∈Mln⁡Pθ(wi∣w∖M)\mathcal{L}_{\text{MLM}} = -\frac{1}{|M|}\sum_{i\in M}\ln P_\theta(w_i\mid w_{\setminus M}), conditioning on the full bidirectional context. Only masked positions contribute to the gradient; unmasked positions do not produce loss. (3)

(b) Masking arithmetic (6 marks)

n=100n=100, 15% chosen ⇒ 15 positions.

  • (i) Contribute to loss = all chosen = 15. (2)
  • (ii) [MASK] shown = 0.8×15=0.8\times15 = 12. (1)
  • (iii) Random token = 0.1×15=0.1\times15 = 1.5. (1)

Purpose (2): The 10%-random and 10%-unchanged reduce the train/inference mismatch — at fine-tuning/inference there is no [MASK] token, so the model must learn to produce good representations for tokens that are not masked and must not blindly trust that an unchanged token is correct (random tokens force it to verify from context rather than copy).

(c) NSP constant-output proof (6 marks)

H(q)=−12ln⁡q−12ln⁡(1−q)H(q) = -\tfrac12\ln q - \tfrac12\ln(1-q), q∈(0,1)q\in(0,1). H′(q)=−12q+12(1−q)=12⋅q−(1−q)q(1−q)=2q−12q(1−q).H'(q) = -\frac{1}{2q} + \frac{1}{2(1-q)} = \frac{1}{2}\cdot\frac{q-(1-q)}{q(1-q)} = \frac{2q-1}{2q(1-q)}. Set H′(q)=0⇒2q−1=0⇒q=1/2H'(q)=0 \Rightarrow 2q-1=0 \Rightarrow q=1/2. (3) H′′(q)=12q2+12(1−q)2>0,H''(q) = \frac{1}{2q^2} + \frac{1}{2(1-q)^2} > 0, so it is a strict minimum. (1) Minimum value: H(1/2)=−12ln⁡12−12ln⁡12=ln⁡2≈0.6931H(1/2) = -\tfrac12\ln\tfrac12 - \tfrac12\ln\tfrac12 = \ln 2 \approx 0.6931 nats. (1)

Operationally (1): this is the loss of a model that has learned the prior (50/50) but nothing input-specific — the baseline an NSP head must beat; achieving less than ln⁡2\ln 2 means it extracts real signal from the sentence pair.

[
  {"claim":"Q1c tying saving = V*d = 51.2M","code":"V=50000; d=1024; result = (V*d == 51200000)"},
  {"claim":"Q2b total NLL in nats ~6.9078","code":"import math; vals=[0.5,0.25,0.4,0.1,0.2]; nll=-sum(math.log(v) for v in vals); result = abs(nll-6.90776)<1e-3"},
  {"claim":"Q2b perplexity ~3.981","code":"import math; vals=[0.5,0.25,0.4,0.1,0.2]; ppl=math.exp(-sum(math.log(v) for v in vals)/5); result = abs(ppl-3.9811)<1e-2"},
  {"claim":"Q3b expected loss/mask/random tokens","code":"n=100; chosen=0.15*n; mask=0.8*chosen; rand=0.1*chosen; result = (chosen==15 and mask==12 and abs(rand-1.5)<1e-9)"},
  {"claim":"Q3c NSP minimum entropy = ln2 at q=1/2","code":"import sympy as sp; q=sp.symbols('q',positive=True); H=-sp.Rational(1,2)*sp.log(q)-sp.Rational(1,2)*sp.log(1-q); crit=sp.solve(sp.diff(H,q),q); result = (crit==[sp.Rational(1,2)] and sp.simplify(H.subs(q,sp.Rational(1,2))-sp.log(2))==0)"}
]