Vocabulary size tradeoffs: Exercises — AI-ML deep dive

Two facts we reuse everywhere (both derived in the parent note):

Level 1 — Recognition

Exercise 1.1

A tokenizer uses $V = 32000$ tokens and embedding dimension $d = 512$ . How many parameters does the embedding table hold?

Recall Solution

WHAT we do: Apply $V \times d$ directly — no sequence, no attention involved, just the shelf of vectors. $32000 \times 512 = 16, 384, 000 \approx 16.4 M$ WHY only this: The embedding table cost never depends on $n$ or on how long documents are. It is one vector per token slot, full stop.

Exercise 1.2

Text is 1000 characters long. A byte-level tokenizer averages 1 token per character; a BPE tokenizer averages 4 characters per token. Give the sequence length $n$ for each.

Recall Solution

Byte-level: one token per character, so $n = 1000$ . BPE: each token swallows 4 characters, so $n = \frac{1000}{4} = 250 tokens.$ WHAT this shows: a bigger vocabulary (BPE has thousands of merges) produces shorter sequences. That is the whole tension of this chapter in one line.

Exercise 1.3

True or false: "Doubling the sequence length $n$ doubles the self-attention cost."

Recall Solution

False. Attention cost $\propto n^{2} d$ . Replace $n$ with $2 n$ : $(2 n)^{2} d = 4 n^{2} d .$ Doubling $n$ quadruples attention cost. The square is the reason short sequences matter so much.

Level 2 — Application

Exercise 2.1

Model A: $V = 8000$ , $d = 768$ . Model B: $V = 50000$ , $d = 768$ . How many extra embedding parameters does B carry over A?

Recall Solution

WHAT we do: the shared $d$ factors out, so subtract the vocab sizes first. $(50000 - 8000) \times 768 = 42000 \times 768 = 32, 256, 000 \approx 32.3 M extra parameters.$ WHY factor $d$ out: it exposes the clean rule — extra embedding cost = (extra tokens) $\times d$ . This is the left-hand side of the parent's breakeven inequality.

Exercise 2.2

A 1000-character document. Vocab A gives average token length $\overset{ˉ}{ℓ} = 4$ ; vocab B (larger) gives $\overset{ˉ}{ℓ} = 5$ . By what factor does the attention cost drop when moving A → B?

Recall Solution

Sequence lengths: $n_{A} = \frac{1000}{4} = 250, n_{B} = \frac{1000}{5} = 200.$ Attention cost $\propto n^{2}$ , so the ratio is $\frac{n _{A}^{2}}{n _{B}^{2}} = (\frac{250}{200})^{2} = (\frac{5}{4})^{2} = 1.5625.$ WHAT it means: the bigger vocab makes attention about $1.56 \times$ cheaper — a 36% cut — even though tokens only got 25% longer. The square amplifies the gain.

Exercise 2.3

Batch size $b = 8$ , layers $L = 12$ , sequence $n = 2000$ , scores stored in float16 (2 bytes). Compute the attention score matrix memory (scalars only, one $n \times n$ per layer per batch item).

Recall Solution

WHAT we count: each layer produces an $n \times n$ table of scalar scores. $b \times L \times n^{2} \times 2 bytes = 8 \times 12 \times 200 0^{2} \times 2.$ Step by step: $200 0^{2} = 4, 000, 000, \times 2 = 8, 000, 000, \times 12 = 96, 000, 000, \times 8 = 768, 000, 000 bytes \approx 768 MB .$ WHY no $d$ : the scores are single numbers, not $d$ -vectors. Multiplying by $d$ here is the classic blunder (see below).

Level 3 — Analysis

Exercise 3.1

Using the breakeven inequality from the parent note, $(V_{l} - V_{s}) d < (n_{s}^{2} - n_{l}^{2}) d \cdot B,$ where $B$ is the number of batches processed. Cancel $d$ and solve for the minimum $B$ at which the large vocab wins, given $V_{s} = 32000$ , $V_{l} = 128000$ , $n_{s} = 2000$ , $n_{l} = 1400$ .

Recall Solution

WHAT we do: $d$ appears on both sides, so it cancels — the winner does not depend on embedding dimension here. $V_{l} - V_{s} = 96000, n_{s}^{2} - n_{l}^{2} = 200 0^{2} - 140 0^{2} = 4, 000, 000 - 1, 960, 000 = 2, 040, 000.$ Inequality becomes $96000 < 2, 040, 000 \cdot B ⟹ B > \frac{96000}{2 , 040 , 000} \approx 0.047.$ WHAT it means: $B > 0.047$ means the large vocab wins after the very first batch ( $B = 1$ ). The one-time parameter overhead (96000 units) is tiny next to the per-batch activation savings (2.04M units per batch). See the figure — the amber savings line overtakes the flat white overhead almost immediately.

Exercise 3.2

For Chinese text: character-level gives $V \approx 1000$ , $n = 100$ ; subword gives $V = 50000$ , $n = 35$ . Embedding dim $d = 512$ . Compare (a) embedding tables and (b) attention costs (as ratios).

Recall Solution

(a) Embedding table ratio: $\frac{V _{sub}}{V _{char}} = \frac{50000}{1000} = 50 \times larger table for subword.$ (b) Attention cost ratio (character ÷ subword): $\frac{n _{char}^{2}}{n _{sub}^{2}} = \frac{10 0 ^{2}}{3 5 ^{2}} = \frac{10000}{1225} \approx 8.16 \times more attention work for character-level.$ The tradeoff in words: subword pays $50 \times$ more in fixed embedding memory but character-level pays $\approx 8 \times$ more in per-input attention compute. For a model that processes lots of text, the $8 \times$ recurring cost usually dominates → subword wins for Chinese, matching the parent note.

Exercise 3.3

The parent claims $\overset{ˉ}{ℓ}$ (average characters per token) is sublinear in $V$ : "doubling $V$ raises $\overset{ˉ}{ℓ}$ by 20–30%." If $\overset{ˉ}{ℓ} = 4$ at $V = 32 K$ and grows 25% per doubling, estimate $\overset{ˉ}{ℓ}$ at $V = 128 K$ .

Recall Solution

WHAT we do: $32 K \to 128 K$ is two doublings ( $\times 2$ , then $\times 2$ ). $\overset{ˉ}{ℓ} = 4 \times 1.25 \times 1.25 = 4 \times 1.5625 = 6.25 characters per token.$ WHY sublinear matters: $V$ grew $4 \times$ but $\overset{ˉ}{ℓ}$ only grew $\approx 1.56 \times$ . You pay linearly for a bigger table but only get diminishing sequence shortening — the core reason vocabularies plateau around 32K–128K instead of ballooning.

Level 4 — Synthesis

Exercise 4.1

Design decision. A model budget allows 65M embedding parameters. With $d = 512$ , what is the largest vocabulary you can afford? Then state one downside of using that whole budget on vocabulary.

Recall Solution

WHAT we do: invert $V \times d = 65 M$ . $V = \frac{65 , 000 , 000}{512} = 126, 953 \approx 127 K tokens.$ Downside: at 127K tokens, many slots hold rare tokens seen only a handful of times in training. Their embedding vectors get few gradient updates, stay noisy, and generalize poorly — the exact failure mode the parent's final [!mistake] warns about. A smaller, well-trained vocab can outperform a bloated one.

Exercise 4.2

Combine both cost laws into a single total memory expression for one batch, then decide which term to attack first when $n$ is large. Use $V = 50 K$ , $d = 768$ , $n = 4096$ , $L = 24$ , $b = 1$ , float16.

Recall Solution

Embedding (fixed): $V d \times 2 = 50000 \times 768 \times 2 = 76, 800, 000 \approx 76.8 MB$ (bytes for the stored table in fp16). Attention scores (per batch): $b L n^{2} \times 2 = 1 \times 24 \times 409 6^{2} \times 2$ . $409 6^{2} = 16, 777, 216, \times 2 = 33, 554, 432, \times 24 = 805, 306, 368 bytes \approx 805 MB .$ Which term to attack: the attention term (805 MB) dwarfs the embedding term (76.8 MB) by more than $10 \times$ , and it grows with $n^{2}$ . Attack sequence length first — via a bigger/smarter vocab, or the memory tricks in 5.1.03-Memory-optimization-techniques — before shrinking the embedding table.

Level 5 — Mastery

Exercise 5.1

Full end-to-end verdict. A multilingual system (see 6.2.01-Multilingual-models) chooses between:

Option S: $V = 32 K$ , average $n = 2000$ .
Option L: $V = 250 K$ , average $n = 1500$ .

Shared: $d = 1024$ , $L = 32$ , $b = 16$ , float16, and the team runs 50,000 training batches. Compute (a) extra embedding memory of L, (b) per-batch attention savings of L, (c) total savings across all batches, and (d) the final verdict.

Recall Solution

(a) Extra embedding memory (one-time, fp16 bytes): $(250000 - 32000) \times 1024 \times 2 = 218000 \times 1024 \times 2 = 446, 464, 000 \approx 446 MB extra, permanently.$ (b) Per-batch attention-score savings: $n_{S}^{2} - n_{L}^{2} = 200 0^{2} - 150 0^{2} = 4, 000, 000 - 2, 250, 000 = 1, 750, 000.$ $savings = b L (n_{S}^{2} - n_{L}^{2}) \times 2 = 16 \times 32 \times 1, 750, 000 \times 2 = 1, 792, 000, 000 bytes \approx 1, 792 MB per batch.$ (c) The per-batch saving already exceeds the one-time overhead on the first batch (1792 MB > 446 MB). Across 50,000 batches the recurring activation saving is the dominant story; the 446 MB parameter cost is paid once and forgotten. (d) Verdict: Option L wins on resources — provided (i) the 250K vocabulary genuinely reduces sequences to $n = 1500$ for your languages, and (ii) rare-token embeddings stay trainable. The recurring $n^{2}$ savings crush the one-time parameter overhead.

Exercise 5.2

Conceptual mastery — connect three chapters. Explain in 3 sentences why increasing $V$ helps 4.3.01-Transformer-attention-complexity but pressures 4.5.02-Embedding-layer-design, and how 4.2.02-Byte-pair-encoding positions the vocab in the middle.

Recall Solution

A larger $V$ lets each token absorb more characters, shrinking $n$ , and since attention scales as $n^{2} d$ this shortening delivers quadratic compute relief. But that same larger $V$ inflates the embedding table $V \times d$ linearly and dilutes training signal across many rare slots, straining embedding-layer design. BPE is the compromise engine: it greedily merges only the frequent substrings, so it buys most of the sequence-shortening benefit while keeping $V$ modest enough that every token still gets enough training exposure.

Recall Self-test: can you answer without looking?

Doubling $n$ multiplies attention cost by ::: 4 (because cost $\propto n^{2}$ ) Embedding table parameter count formula ::: $V \times d$ Why the attention score matrix has no $d$ factor ::: each score is a dot product — two $d$ -vectors collapse to one scalar The core reason large vocabularies plateau (don't grow forever) ::: $\overset{ˉ}{ℓ}$ grows sublinearly in $V$ , and rare-token embeddings train poorly