S17 Reading — Transformer II | Deep Learning

Module 3 · Reading 3.4 · read before S17: Transformer II

The PDF posted in Canvas is the assigned version of this reading. It is built from this page, so the text is identical; anything here marked as deep reading is optional and is not in the PDF.

The Transformer block above consumes a sequence of vectors, and those vectors come from an embedding table indexed by integers. So before any language model can run, text must become a sequence of integer ids — and how you cut text into pieces turns out to be a consequential modeling decision, not a preprocessing chore. Cut too coarsely (whole words) and your vocabulary explodes while novel words become unrepresentable. Cut too finely (characters) and every input becomes painfully long, spending your model’s fixed context window on spelling instead of meaning.

Modern models settle in between with subword tokenization, learned from data. This section implements the dominant algorithm (byte-pair encoding) from scratch on a toy corpus, measures the vocabulary-size trade-off with real numbers, contrasts BPE with its two main rivals (WordPiece and the unigram model) on the same corpus, and stress-tests the result on the inputs that make real tokenizers stumble: capital letters, digits, and other languages. Then it zooms out to the second big design fork this chapter has been building toward: given tokens, which parts of the Transformer do you keep, and what objective do you train? The three answers (encoder-only, decoder-only, encoder–decoder) define the model families (BERT, the GPT line, T5) that organize the rest of this chapter.

How to read this

The complete block, in one page
The vocabulary problem
Byte-pair encoding: learn the merges
The trade-off, measured
Same corpus, different algorithms: WordPiece and unigram
When tokenizers meet the real world
Three ways to keep a Transformer
Choosing a family
Going deeper
Common pitfalls
Try it yourself
Further reading

The complete block, in one page

Section 3.3 ended with the three ingredients that turn self-attention into something you can stack: residual connections, layer normalization, and a per-position feedforward network. This section assembles them, so that this page carries the whole block on its own.

A block is two sublayers, each wrapped in a residual connection. Attention mixes information across positions; the FFN transforms each position in place. Everything else is bookkeeping:

x = x + Attention(LayerNorm(x)), then x = x + FFN(LayerNorm(x))

The three ingredients, and what each buys:

Residual connections. Every sublayer computes x + sublayer(x), so the block’s default behavior is to pass its input along, and each block gives the gradient a direct route back — the same argument as ResNet, with the same caveat: it improves the path, it does not guarantee an unattenuated one.
Layer normalization standardizes each token’s own feature vector and rescales it with learned parameters. No batch statistics are involved, which is why it suits variable-length sequences and small batches where BatchNorm struggles.
The FFN is Linear(d_model, d_ff), a nonlinearity (ReLU originally, GELU in most modern models), then Linear(d_ff, d_model), conventionally with d_ff = 4 * d_model.

Where the norm goes is the one genuinely contested choice. The 2017 paper is post-norm, LayerNorm(x + sublayer(x)); most models since GPT-2 are pre-norm, x + sublayer(LayerNorm(x)), which leaves the residual stream unnormalized end to end and is generally easier to train deep. Pre-norm is a sensible implementation default and the one HW3 expects — not a universal law: post-norm can reach slightly better tuned quality, and either way large recipes still tune warmup, initialization, residual scaling, and gradient clipping.

Here is the block, with the shape of every intermediate it produces. Read the shape column as the actual argument: a block takes (batch, positions, features) and returns the same shape, which is precisely why blocks stack.

import math
import torch
import torch.nn as nn
import torch.nn.functional as F

torch.manual_seed(0)

class Block(nn.Module):
    """One pre-norm Transformer block: x + Attn(LN(x)), then x + FFN(LN(x))."""

    def __init__(self, d_model, n_heads, d_ff):
        super().__init__()
        assert d_model % n_heads == 0
        self.n_heads, self.d_head = n_heads, d_model // n_heads
        self.ln1, self.ln2 = nn.LayerNorm(d_model), nn.LayerNorm(d_model)
        self.qkv = nn.Linear(d_model, 3 * d_model)
        self.proj = nn.Linear(d_model, d_model)
        self.ffn = nn.Sequential(
            nn.Linear(d_model, d_ff), nn.GELU(), nn.Linear(d_ff, d_model))

    def attn(self, x):
        B, T, D = x.shape
        q, k, v = self.qkv(x).chunk(3, dim=-1)
        shape = lambda t: t.view(B, T, self.n_heads, self.d_head).transpose(1, 2)
        q, k, v = shape(q), shape(k), shape(v)
        scores = q @ k.transpose(-2, -1) / math.sqrt(self.d_head)
        mask = torch.triu(torch.ones(T, T, dtype=torch.bool), diagonal=1)
        w = F.softmax(scores.masked_fill(mask, float("-inf")), dim=-1)
        out = (w @ v).transpose(1, 2).contiguous().view(B, T, D)
        return self.proj(out)

    def forward(self, x):
        x = x + self.attn(self.ln1(x))     # sublayer 1: mix ACROSS positions
        x = x + self.ffn(self.ln2(x))      # sublayer 2: transform WITHIN one
        return x

B, T, d_model, n_heads, d_ff = 2, 8, 64, 4, 256
block = Block(d_model, n_heads, d_ff)
x = torch.randn(B, T, d_model)
y = block(x)

print(f"in {tuple(x.shape)} -> out {tuple(y.shape)}   (a block preserves its shape)")
print()
print(f"{'tensor':<24}{'shape':<22}{'note'}")
rows = [
    ("x (input)",              (B, T, d_model),                   "batch, positions, features"),
    ("qkv(LN(x))",             (B, T, 3 * d_model),               "Q, K, V in one matmul"),
    ("q per head",             (B, n_heads, T, d_model//n_heads), "split d_model across heads"),
    ("scores = q @ k^T",       (B, n_heads, T, T),                "every position vs every position"),
    ("attn @ v",               (B, n_heads, T, d_model//n_heads), "weighted mix of values"),
    ("concat heads -> proj",   (B, T, d_model),                   "back to model width"),
    ("ffn hidden",             (B, T, d_ff),                      "expand (d_ff = 4 * d_model)"),
    ("y (output)",             (B, T, d_model),                   "same shape as x -> stackable"),
]
for name, shape, note in rows:
    print(f"{name:<24}{str(tuple(shape)):<22}{note}")

total = sum(p.numel() for p in block.parameters())
attn_p = sum(q.numel() for m in (block.qkv, block.proj) for q in m.parameters())
ffn_p = sum(q.numel() for q in block.ffn.parameters())
print()
print(f"parameters: {total} total | attention {attn_p} | FFN {ffn_p} "
      f"({100 * ffn_p / total:.0f}% in the FFN)")

Running this prints:

in (2, 8, 64) -> out (2, 8, 64)   (a block preserves its shape)

tensor                  shape                 note
x (input)               (2, 8, 64)            batch, positions, features
qkv(LN(x))              (2, 8, 192)           Q, K, V in one matmul
q per head              (2, 4, 8, 16)         split d_model across heads
scores = q @ k^T        (2, 4, 8, 8)          every position vs every position
attn @ v                (2, 4, 8, 16)         weighted mix of values
concat heads -> proj    (2, 8, 64)            back to model width
ffn hidden              (2, 8, 256)           expand (d_ff = 4 * d_model)
y (output)              (2, 8, 64)            same shape as x -> stackable

parameters: 49984 total | attention 16640 | FFN 33088 (66% in the FFN)

Two things to take from the numbers. The shape column never changes at the block boundary ((2, 8, 64) in, (2, 8, 64) out), which is the whole reason a Transformer is a stack of identical units; depth costs you nothing in plumbing. And the parameter split is the measured version of a claim worth remembering: 66% of this block’s parameters sit in the FFN, not in attention. Attention gets the attention; the FFN holds most of the weights.

The causal mask in attn is what makes this block usable as a language model: position \(t\) never sees \(t+1\) onward. Section 3.3 verifies that property by perturbation (edit the token at position 5 and watch positions 0–4 stay bit-for-bit identical), and HW3 asks you to reproduce the test.

With the block settled, the rest of this section turns to the two questions it raises: what the integers feeding the embedding table should be, and which parts of the architecture you keep.

The vocabulary problem

Consider the word-level approach first, because its failure teaches the most. Assign one id per distinct word: sequences get short (one token per word), and embeddings align with meaningful units. But natural language has a heavy tail — new names, typos, morphological variants, compounds. Train on a fixed corpus and the first out-of-vocabulary word at test time has no id at all; the classic fix, a catch-all [UNK] token, throws the word’s identity away entirely. Worse, morphology is invisible: “learn,” “learns,” “learned,” and “learner” are four unrelated ids, and the model must rediscover their relationship from usage alone. Vocabulary sizes also balloon (hundreds of thousands of forms for morphologically rich languages), and every id is a row in the embedding table and the output softmax.

Character-level tokenization inverts every property. A few dozen ids cover everything, and nothing is ever out of vocabulary. But sequences grow several times longer (costly when self-attention’s compute grows quadratically with sequence length and every model has a finite context window), and each token is nearly meaningless on its own, pushing all compositional work into the network.

Subword tokenization takes both ends: keep whole tokens for frequent words, but let rare words decompose into meaningful fragments (“un” + “believ” + “able”). The insight that made this practical is that the segmentation can be learned from corpus statistics with an almost embarrassingly simple algorithm.

Byte-pair encoding: learn the merges

Byte-pair encoding (BPE) began life as a 1994 data-compression trick by Philip Gage: repeatedly replace the most frequent adjacent byte pair with a new symbol. Rico Sennrich, Barry Haddow, and Alexandra Birch adapted it to neural machine translation in a 2016 ACL paper, “Neural Machine Translation of Rare Words with Subword Units,” and it spread through NLP from there. The training procedure:

Start with words as sequences of characters, plus an end-of-word marker </w> so the algorithm can distinguish “est” ending a word from “est” starting one.
Count all adjacent symbol pairs across the corpus (weighted by word frequency).
Merge the most frequent pair into a single new symbol everywhere; record the merge.
Repeat for a fixed number of merges — the number of merges is your vocabulary-size knob.

To tokenize new text, replay the recorded merges in order. Here is the whole thing, on the same style of toy corpus Sennrich et al. used:

from collections import Counter

# Byte-pair encoding on a toy corpus (word -> count). Each word starts as
# characters plus an end-of-word marker; we repeatedly merge the most
# frequent adjacent pair.
corpus = {"low": 5, "lower": 2, "newest": 6, "widest": 3}
words = {tuple(w) + ("</w>",): c for w, c in corpus.items()}

def pair_counts(words):
    counts = Counter()
    for symbols, c in words.items():
        for pair in zip(symbols, symbols[1:]):
            counts[pair] += c
    return counts

def apply_merge(words, pair):
    merged = {}
    a, b = pair
    for symbols, c in words.items():
        out, i = [], 0
        while i < len(symbols):
            if i + 1 < len(symbols) and symbols[i] == a and symbols[i + 1] == b:
                out.append(a + b); i += 2
            else:
                out.append(symbols[i]); i += 1
        merged[tuple(out)] = c
    return merged

merges = []
for step in range(8):
    counts = pair_counts(words)
    best, freq = counts.most_common(1)[0]
    merges.append(best)
    words = apply_merge(words, best)
    print(f"merge {step + 1}: {best[0]!r} + {best[1]!r} -> {best[0] + best[1]!r}  (count {freq})")

print("\nvocabulary entries for each corpus word after 8 merges:")
for symbols, c in words.items():
    print(f"  {' '.join(symbols)}")

# Segment an UNSEEN word with the learned merge list (apply in learned order).
def segment(word, merges):
    symbols = tuple(word) + ("</w>",)
    for pair in merges:
        symbols = tuple(next(iter(apply_merge({symbols: 1}, pair))))
    return symbols

for w in ["lowest", "newer", "lowlow"]:
    print(f"unseen word {w!r} -> {' '.join(segment(w, merges))}")

Running this prints:

merge 1: 'e' + 's' -> 'es'  (count 9)
merge 2: 'es' + 't' -> 'est'  (count 9)
merge 3: 'est' + '</w>' -> 'est</w>'  (count 9)
merge 4: 'l' + 'o' -> 'lo'  (count 7)
merge 5: 'lo' + 'w' -> 'low'  (count 7)
merge 6: 'n' + 'e' -> 'ne'  (count 6)
merge 7: 'ne' + 'w' -> 'new'  (count 6)
merge 8: 'new' + 'est</w>' -> 'newest</w>'  (count 6)

vocabulary entries for each corpus word after 8 merges:
  low </w>
  low e r </w>
  newest</w>
  w i d est</w>
unseen word 'lowest' -> low est</w>
unseen word 'newer' -> new e r </w>
unseen word 'lowlow' -> low low </w>

Read the merge log as a story about the corpus. “est” appears in newest (count 6) and widest (count 3), so e+s and then es+t win the first merges with count 9: the algorithm has discovered the superlative suffix with no linguistic knowledge whatsoever, just pair counting. Then “low” (7 occurrences across low and lower) gets assembled, then “new”. The payoff is the last three lines: “lowest” never appears in the corpus, yet it tokenizes as low + est</w> — two frequent, meaningful units that the model will have seen in many contexts. “newer” decomposes into new + e + r + </w>, falling back to characters where no merge applies. No word built from the corpus’s characters is ever out of vocabulary: the worst case is a full spell-out.

Historical note. BPE’s path into deep learning is a nice case of an idea crossing fields: Gage’s 1994 article in The C Users Journal was about squeezing bytes, not language, and it went largely unnoticed in NLP for two decades. Sennrich, Haddow, and Birch picked it up (their paper credits the compression lineage directly) because neural translation systems of 2015 were crippled by fixed 30–50K word vocabularies on morphologically rich languages like German. Variants followed quickly: WordPiece (used by BERT) selects merges by likelihood gain rather than raw frequency, and the SentencePiece library (Kudo & Richardson, 2018) made the whole pipeline language-agnostic by treating the input as a raw character stream, whitespace included.

The trade-off, measured

The number of merges interpolates between character-level and word-level tokenization, and you can watch every consequence at once on a slightly larger corpus. The script below trains BPE on a 16-word corpus with recurring morphemes, then reports, at 0, 10, 20, and 30 merges, the embedding-table size a model would need (base symbols plus one new token per merge), the total tokens to encode the corpus (sequence-length cost), and the fate of a held-out word, “learners,” which never occurs in the corpus.

from collections import Counter

# The vocabulary-size trade-off: characters vs learned BPE merges vs words.
text = ("the tokenizer tokenizes the text the transformer transforms "
        "the tokens a learner learns the learned tokens")
corpus = Counter(text.split())
held_out = "learners"   # never appears in the corpus

words = {tuple(w) + ("</w>",): c for w, c in corpus.items()}

def pair_counts(words):
    counts = Counter()
    for symbols, c in words.items():
        for pair in zip(symbols, symbols[1:]):
            counts[pair] += c
    return counts

def apply_merge(words, pair):
    merged = {}
    a, b = pair
    for symbols, c in words.items():
        out, i = [], 0
        while i < len(symbols):
            if i + 1 < len(symbols) and symbols[i] == a and symbols[i + 1] == b:
                out.append(a + b); i += 2
            else:
                out.append(symbols[i]); i += 1
        merged[tuple(out)] = c
    return merged

def segment(word, merges):
    symbols = tuple(word) + ("</w>",)
    for pair in merges:
        symbols = tuple(next(iter(apply_merge({symbols: 1}, pair))))
    return symbols

merges = []
snapshots = {0: dict(words)}
for step in range(1, 31):
    best, _ = pair_counts(words).most_common(1)[0]
    merges.append(best)
    words = apply_merge(words, best)
    if step in (10, 20, 30):
        snapshots[step] = dict(words)

n_base = len({ch for w in corpus for ch in w} | {"</w>"})
print(f"{'merges':>6}  {'table size':>10}  {'corpus tokens':>13}  {'held-out word split':>28}")
for n, snap in snapshots.items():
    total = sum(len(symbols) * c for symbols, c in snap.items())
    seg = segment(held_out, merges[:n])
    # embedding-table size = base symbols + one new token per merge
    print(f"{n:>6}  {n_base + n:>10}  {total:>13}  {' '.join(seg):>28}")

# Word-level for comparison: smallest sequences, but the held-out word
# has no id at all -- it becomes a single unknown token.
n_word_tokens = sum(corpus.values())
print(f"{'words':>6}  {len(corpus) + 1:>10}  {n_word_tokens:>13}  {'[UNK]':>28}")

Running this prints:

merges  table size  corpus tokens           held-out word split
     0          17            107          l e a r n e r s </w>
    10          27             65            l e a r n er s</w>
    20          37             41                learn er s</w>
    30          47             26                learn er s</w>
 words          12             16                         [UNK]

Every row is a point on the trade-off curve. At 0 merges (pure characters), 17 table entries suffice but the corpus costs 107 tokens. Thirty merges nearly quadruples the corpus compression (107 → 26 tokens) at the price of a table almost three times larger — and the held-out “learners” segments into learn + er + s</w>, three units a model can actually work with. The word-level row wins on both counts for text it has seen (12 entries, 16 tokens) and then fails absolutely on the one word it hasn’t: [UNK]. Production systems buy sequence compression with much bigger tables: GPT-2’s byte-level BPE tokenizer has 50,257 entries, BERT’s WordPiece vocabulary about 30,000, and byte-level BPE (operating on UTF-8 bytes, so even emoji and typos decompose into the 256 base bytes) removes [UNK] from the picture entirely.

The knob has real consequences downstream. A larger vocabulary means shorter sequences (cheaper attention, more effective context), but a bigger embedding table and softmax, and rarer tokens each seen less often during training. It also silently allocates capability: text that tokenizes inefficiently (many tokens per word — common for languages underrepresented in the tokenizer’s training corpus, and for unusual formats like digit strings) gets less effective context and often worse model performance per character of input.

Pitfall. A tokenizer is part of the model, not an accessory. Every pretrained checkpoint was trained against one specific tokenizer, and pairing it with any other (even one trained the same way on different data) scrambles the mapping from ids to meanings; the failure mode at fine-tuning time is a model that emits fluent nonsense or crashes on out-of-range ids. Similarly, small text quirks (a leading space, unusual Unicode, digit grouping) can change token counts substantially. When something is weird in an LLM’s behavior, “look at the actual token ids” is diagnostic step one.

Same corpus, different algorithms: WordPiece and unigram

BPE won the popularity contest, but two rivals appear in enough model cards that you should know exactly how they differ. Both are best seen against BPE on the same data.

WordPiece (developed at Google for a 2012 speech system and later used by BERT) is often taught as a greedy learner whose candidate merge is scored by association or likelihood gain rather than raw pair count. The original production training details were not published as one universal algorithm, and libraries differ. The score below is therefore a useful pedagogical approximation, not a normative WordPiece specification:

\[\operatorname{score}(a, b) = \frac{\operatorname{count}(a, b)}{\operatorname{count}(a) \cdot \operatorname{count}(b)}\]

the pair that co-occurs more than its parts’ popularity predicts — which is, up to a logarithm, the pair whose merger most improves a unigram language model’s likelihood of the corpus. Frequency asks “what do I see most?”; the score asks “what is most surprising to see together?”. The script runs both rules on this section’s first corpus:

from collections import Counter

# BPE vs WordPiece on the same corpus. Both learn merges greedily; the
# difference is the selection rule. BPE merges the most FREQUENT adjacent
# pair. WordPiece merges the pair with the highest ASSOCIATION score
#   score(a, b) = count(a, b) / (count(a) * count(b))
# -- the pair that co-occurs more than its parts' frequencies predict,
# which is (up to a log) the likelihood gain of adding the merged token
# to a unigram model.

corpus = {"low": 5, "lower": 2, "newest": 6, "widest": 3}

def pair_counts(words):
    counts = Counter()
    for symbols, c in words.items():
        for pair in zip(symbols, symbols[1:]):
            counts[pair] += c
    return counts

def unit_counts(words):
    counts = Counter()
    for symbols, c in words.items():
        for s in symbols:
            counts[s] += c
    return counts

def apply_merge(words, pair):
    merged = {}
    a, b = pair
    for symbols, c in words.items():
        out, i = [], 0
        while i < len(symbols):
            if i + 1 < len(symbols) and symbols[i] == a and symbols[i + 1] == b:
                out.append(a + b); i += 2
            else:
                out.append(symbols[i]); i += 1
        merged[tuple(out)] = c
    return merged

def train(rule, n_merges=6):
    words = {tuple(w) + ("</w>",): c for w, c in corpus.items()}
    picked = []
    for _ in range(n_merges):
        pc, uc = pair_counts(words), unit_counts(words)
        if rule == "bpe":
            best = max(sorted(pc), key=lambda p: pc[p])
        else:  # wordpiece
            best = max(sorted(pc), key=lambda p: pc[p] / (uc[p[0]] * uc[p[1]]))
        picked.append(best)
        words = apply_merge(words, best)
    return picked

bpe, wp = train("bpe"), train("wordpiece")
print(f"{'step':>4}  {'BPE (by count)':>16}  {'WordPiece (by score)':>21}")
for i, (b, w) in enumerate(zip(bpe, wp), 1):
    print(f"{i:>4}  {b[0] + '+' + b[1]:>16}  {w[0] + '+' + w[1]:>21}")

Running this prints:

step    BPE (by count)   WordPiece (by score)
             e+s                    i+d
            es+t                    l+o
        est+</w>                    s+t
             l+o                   lo+w
            lo+w                   w+id
             e+w                 r+</w>

The two algorithms walk through the same corpus in visibly different orders. BPE goes straight for e+s: nine occurrences, the raw-count champion. WordPiece’s first pick is i+d, which occurs only three times: but i and d occur nowhere else, so the association is perfect (seeing i means d is coming), while e+s scores poorly because e is scattered across half the corpus. (A note on the exact rows: several pairs tie on both criteria in a corpus this small, and this script breaks ties alphabetically, so other implementations may print a slightly different order; the pattern, count-champions versus association-champions, is the robust part.) In practice the two algorithms produce broadly similar vocabularies at scale, and WordPiece’s visible legacy is mostly cosmetic: BERT-family tokenizers mark word-internal continuation pieces with ##, as in learn, ##er.

Unigram tokenization (Kudo, ACL 2018) starts from a large candidate vocabulary, fits token probabilities, and prunes candidates whose removal least hurts likelihood. Its best segmentation is a max-product path found by Viterbi-style dynamic programming. CTC used a related dynamic-programming mindset but a different operation: its forward algorithm sums probabilities over all valid alignments rather than selecting one best path.

import math

# The unigram tokenizer's inference step. Unlike BPE/WordPiece, a unigram
# model does not replay merges. It holds a vocabulary of tokens with
# probabilities and segments new text into the sequence of in-vocabulary
# tokens with the highest total log-probability, found by dynamic
# programming (Viterbi). Here the vocabulary and counts are given; a real
# trainer would also learn them (by EM, pruning a large seed vocabulary).

vocab_counts = {
    "l": 2, "o": 2, "w": 4, "e": 5, "s": 2, "t": 2, "n": 1, "r": 2,
    "lo": 3, "low": 7, "est": 9, "er": 4, "new": 6, "wid": 3, "id": 3,
    "west": 2, "lowe": 1,
}
total = sum(vocab_counts.values())
logp = {tok: math.log(c / total) for tok, c in vocab_counts.items()}

def viterbi_segment(word):
    # best[i] = (score, segmentation) for the prefix word[:i]
    best = [(0.0, [])] + [(-math.inf, None)] * len(word)
    for i in range(1, len(word) + 1):
        for j in range(max(0, i - 5), i):        # max token length 5
            piece = word[j:i]
            if piece in logp and best[j][0] > -math.inf:
                score = best[j][0] + logp[piece]
                if score > best[i][0]:
                    best[i] = (score, best[j][1] + [piece])
    return best[-1]

for word in ["lowest", "newest", "lowers"]:
    score, seg = viterbi_segment(word)
    if seg is None:
        print(f"{word!r}: no segmentation with this vocabulary")
    else:
        print(f"{word!r} -> {' '.join(seg)}   (total log-prob {score:.3f})")

# Why does 'lowest' become low+est and not, say, lo+west or lowe+st?
# Enumerate a few candidate segmentations and score them by hand:
cands = [["low", "est"], ["lo", "west"], ["l", "o", "w", "est"]]
print("\ncandidate scores for 'lowest':")
for seg in cands:
    s = sum(logp[p] for p in seg)
    print(f"  {' + '.join(seg):<22} log-prob = {s:.3f}")

Running this prints:

'lowest' -> low est   (total log-prob -3.978)
'newest' -> new est   (total log-prob -4.132)
'lowers' -> low er s   (total log-prob -8.156)

candidate scores for 'lowest':
  low + est              log-prob = -3.978
  lo + west              log-prob = -6.329
  l + o + w + est        log-prob = -11.272

The candidate table shows the decision being made: low + est wins not by rule but by probability — two frequent tokens beat one frequent plus one rare (lo + west), which beats a spell-out. This probabilistic framing has a bonus BPE cannot offer: since every segmentation has a well-defined probability, you can sample segmentations instead of always taking the best one. Kudo’s paper introduced exactly this as a training-time augmentation (subword regularization), showing translation gains from exposing the model to varied segmentations of the same text. The unigram algorithm is one of the two options in the SentencePiece library and was the choice of T5 and many multilingual models. Kudo’s paper also reports the empirical bottom line that keeps all three algorithms alive: their end-task differences are usually small, so the choice is more about ecosystem (which library, which checkpoint you must match) than accuracy.

When tokenizers meet the real world

The trade-off table used clean lowercase English, which is the best case the tokenizer will ever see. Deployed tokenizers meet capital letters, numbers, other languages, and whitespace conventions — and every one of these is a chance to spend context window at an unfavorable exchange rate. The script trains the same 30-merge BPE as the trade-off experiment and then confronts it with four inputs of identical character length:

from collections import Counter

# Tokenization pathologies, demonstrated on the toy BPE from earlier in
# this section (retrained here so the script is self-contained). The
# tokenizer is trained on lowercase English prose -- then asked to encode
# capitalized words, digits, and German. Watch the token counts.

text = ("the tokenizer tokenizes the text the transformer transforms "
        "the tokens a learner learns the learned tokens")
corpus = Counter(text.split())
words = {tuple(w) + ("</w>",): c for w, c in corpus.items()}

def pair_counts(words):
    counts = Counter()
    for symbols, c in words.items():
        for pair in zip(symbols, symbols[1:]):
            counts[pair] += c
    return counts

def apply_merge(words, pair):
    merged = {}
    a, b = pair
    for symbols, c in words.items():
        out, i = [], 0
        while i < len(symbols):
            if i + 1 < len(symbols) and symbols[i] == a and symbols[i + 1] == b:
                out.append(a + b); i += 2
            else:
                out.append(symbols[i]); i += 1
        merged[tuple(out)] = c
    return merged

merges = []
for _ in range(30):
    best, _ = pair_counts(words).most_common(1)[0]
    merges.append(best)
    words = apply_merge(words, best)

base = {ch for w in corpus for ch in w} | {"</w>"}
vocab = base | {a + b for a, b in merges}

def segment(word, merges):
    symbols = tuple(word) + ("</w>",)
    for pair in merges:
        symbols = tuple(next(iter(apply_merge({symbols: 1}, pair))))
    return symbols

tests = [
    ("in-domain     ", "the learner learns"),
    ("capitalized   ", "The Learner Learns"),
    ("numbers       ", "learner 2026 44444"),
    ("German        ", "der lernende lernt"),
]
print(f"{'case':>14}  {'tokens':>6}  {'chars':>5}  {'tok/char':>8}   worst word")
for name, sent in tests:
    toks, worst = [], ("", 0)
    for w in sent.split():
        seg = segment(w, merges)
        seg = tuple(s if s in vocab else f"<?{s}?>" for s in seg)  # true OOV symbol
        toks.extend(seg)
        if len(seg) > worst[1]:
            worst = (f"{w} -> {' '.join(seg)}", len(seg))
    n_chars = len(sent.replace(" ", ""))
    print(f"{name:>14}  {len(toks):>6}  {n_chars:>5}  {len(toks)/n_chars:>8.2f}   {worst[0]}")

Running this prints:

          case  tokens  chars  tok/char   worst word
in-domain            5     16      0.31   learner -> learn er</w>
capitalized         16     16      1.00   Learner -> <?L?> e a r n er</w>
numbers             13     16      0.81   44444 -> <?4?> <?4?> <?4?> <?4?> <?4?> </w>
German              15     16      0.94   lernende -> l er n e n d e </w>

Same sixteen characters, wildly different bills. In-domain text costs 5 tokens. Capitalize it and the cost more than triples: no merge was ever learned for T or L, and worse, uppercase letters are not even in the base vocabulary; the <?L?> marker flags a symbol with no id at all, the [UNK] problem resurfacing one level down. Digits fare no better: 44444 spells out digit by digit (each flagged, since the training text had no numerals). This is the toy version of a real phenomenon: how digit strings split varies by tokenizer and affects arithmetic behavior, and several modern tokenizers force single-digit splits deliberately to make number representations uniform. German, related to English as languages go, still costs three times in-domain English because its inflections (lernende) match no learned merges — the fate of every underrepresented language in a tokenizer’s training corpus, and the mechanism behind unequal per-character API costs and effective context lengths across languages documented in tokenizer-fairness studies.

Real systems can patch the representability hole with byte-level BPE or an explicit byte fallback. With all 256 byte values available, any UTF-8 string is representable without [UNK]; character-level BPE without such a fallback can still encounter unseen symbols. Tokenization is a corpus-fitted, variable-rate segmentation scheme: byte-level encoding is reversible at the byte/string level, while optional Unicode normalization or cleaning may be lossy. Whitespace is handled by convention rather than algorithm: GPT-2-style tokenizers fold a leading space into the following word, so hello and ` hello are different tokens with different ids (a classic source of prompt-engineering confusion), while SentencePiece models mark it with a visible ▁` symbol. Text unlike the training corpus typically pays in more tokens and shorter effective context.

Three ways to keep a Transformer

Tokens in hand, return to the architecture. The original Transformer had an encoder tower (unmasked self-attention) and a decoder tower (causal self-attention plus cross-attention). The years 2018–2020 sorted the field into three families according to which parts survive — and, inseparably, which training objective the surviving parts serve.

Encoder-only: BERT. BERT keeps the bidirectional encoder and trains with masked-token reconstruction (15% of tokens masked). It is designed for parallel representations rather than efficient left-to-right generation. Iterative masked-token generation methods can be built around encoder-style models, so “cannot generate” is too strong; the accurate distinction is that BERT has no native causal autoregressive decoder.

Decoder-only: the GPT lineage. GPT kept the causal decoder and next-token objective; GPT-2 and GPT-3 (GPT-2, 1.5B parameters, 2019; GPT-3, 175B, 2020) demonstrated how far that recipe scales. Decoder-only causal models dominate public general-purpose LLM ecosystems, including GPT and Llama families. For proprietary systems such as Claude and Gemini, public technical reports describe causal generation components but do not expose every architectural detail, so avoid claiming a complete private design from the interface alone.

Encoder–decoder: T5. Raffel et al.’s T5 (“Text-to-Text Transfer Transformer,” JMLR 2020) kept both towers and recast every task (translation, summarization, classification, even regression) as text-to-text: instruction and input go into the encoder, the answer comes out of the decoder. The bidirectional encoder reads the full input; the causal decoder generates the output while cross-attending to it. This division is natural for tasks with a clear input→output structure, and encoder–decoder models remain strong for machine translation and summarization at a given size. Their relative decline for general-purpose use is mostly practical: a single decoder handles free-form dialogue more gracefully (everything is just one growing sequence), and the engineering ecosystem consolidated around the simpler recipe.

People. Alec Radford, lead author of the GPT reports, is an unusual figure in a credential-heavy field: he joined OpenAI after undergraduate study at Olin College and went on to be a driving author behind GPT-1/2/3’s precursor line, CLIP, and Whisper. Jacob Devlin’s BERT paper, by most accounts one of the most cited NLP papers of its era, came out of Google roughly a year after the Transformer itself — a reminder of how compressed this period was: encoder-only, decoder-only, and text-to-text families all crystallized within about two years of the 2017 paper.

Choosing a family

A working decision rule for practitioners. If the task is understanding with a fixed output (classify a document, embed sentences for retrieval, tag entities), an encoder-only model gives you bidirectional context and cheap inference, and small BERT-family checkpoints remain excellent value. If the task is open-ended generation (dialogue, code completion, anything instruction-following), the answer today is a decoder-only model, and the interesting choices move to scale, fine-tuning, and prompting (Sections 3.5–3.7). If the task maps one text to another with distinct roles (translation, summarization with tight input grounding), encoder–decoder models are purpose-built for it. And whichever you pick, the tokenizer travels with the checkpoint: family, weights, and vocabulary are one artifact.

The decision rule, as a table you can consult when a project starts:

	Encoder-only (BERT-like)	Decoder-only (GPT-like)	Encoder–decoder (T5-like)
Attention pattern	bidirectional	causal	bidirectional in, causal out
Training objective	masked-token reconstruction	next-token prediction	span corruption / text-to-text
Native autoregressive generation?	no	yes	yes
Sees full input context?	yes, both directions	left context only	yes, in the encoder
Typical tasks	classification, embeddings/retrieval, tagging, reranking	dialogue, code, instruction following, anything open-ended	translation, summarization, structured input-to-output
Inference shape	one parallel pass over input	token-by-token with KV cache	one encoder pass, then token-by-token
Representative checkpoints	BERT, RoBERTa, sentence-embedding models	GPT line, Llama, Claude, Gemini	T5, Flan-T5, T5Gemma

Two rows repay a second look. The inference shape row is often the deciding factor in production: an encoder-only reranker scores a document in one parallel pass, while a decoder must crawl token by token — for fixed-output tasks at high volume, the encoder’s shape is a large cost advantage. And the sees full input row explains a subtlety of decoder-only instruction models: when a decoder reads your prompt, every prompt token is processed causally, so early tokens cannot condition on later ones; an encoder reads the whole input bidirectionally before generation starts. For most tasks the decoder’s scale advantages swamp this, but it is a real representational difference, not a cosmetic one.

The encoder–decoder family also deserves a fairer ending than “declined for practical reasons,” because instruction-era work kept returning to it. Flan-T5 (Chung et al., 2022) applied large-scale instruction tuning (fine-tuning on thousands of tasks phrased as instructions) to T5 checkpoints and produced models that were, at equal size, strikingly competitive with much larger decoders on instruction-following benchmarks; for years, Flan-T5 checkpoints were a default answer for cheap, capable, open task models. And the design resurfaced explicitly in 2025 with T5Gemma, a Google release that adapts pretrained decoder-only Gemma models into encoder–decoder form and reports quality-versus-inference-cost advantages over the decoder-only originals on several benchmarks. The honest summary: decoder-only dominance is a fact about ecosystem momentum and the free simplicity of one growing sequence, not a theorem about architecture; when a task has a clearly separated input worth reading bidirectionally, two towers remain a live and sometimes better option.

Going deeper

Do we need tokenizers at all? Every pathology in this section traces to one decision: freezing a segmentation before training. A recurring research program asks whether the model could just consume raw bytes. ByT5 (Xue et al., TACL 2022) trained T5-style models directly on bytes — robust to typos and any script, but slower, since sequences stretch several-fold and attention pays quadratically. More recent work restructures the model around the problem: Meta’s Byte Latent Transformer (2024) groups bytes into learned patches sized by predictability, spending compute where the byte stream is surprising, and reports competitiveness with tokenizer-based models at substantial scale. Nothing byte-level has displaced BPE-family tokenizers in mainstream LLMs as of this writing, but the direction is one to watch: the tokenizer is the last large hand-designed component in the pipeline, and the field has a consistent record of eventually learning what it once engineered.

Tokenization shapes what models can do — including arithmetic. Because the model sees ids, not characters, the tokenizer decides which structures are even visible. Multi-digit numbers are the sharpest example: if 2026 is one token, its digits are an opaque bundle, and digit-level algorithms like carrying become awkward to express; if digits are split individually, as several modern tokenizers do by design, numbers get uniform, compositional representations, and studies of arithmetic behavior report cleaner digit-wise generalization. Similar stories play out for code (indentation and identifiers), for morphology-rich languages, and for anything where meaning lives below the token boundary (the standard demonstration being character-counting questions, which ask a model about units it quite literally does not see). When a capability question puzzles you, asking “what does this look like after tokenization?” is often the fastest route to an answer.

Vocabulary size has quietly become a scaling knob. GPT-2’s 50K vocabulary was standard for years, but recent open models moved sharply upward (the Llama 3 family to 128K entries, Gemma models to 256K), trading a larger embedding table for fewer tokens per text, hence more effective context and less compute per document, with the biggest gains on non-English text. The optimal size grows with model scale (embedding parameters are a shrinking share of large models, as you computed in 3.3), and research on compute-optimal vocabularies now treats vocabulary size as a first-class scaling variable alongside depth and width rather than a fixed convention.

When ids and meanings drift apart. A tokenizer’s vocabulary is fitted to its training text, and tokens can exist that the model afterward barely trains on — strings frequent in the tokenizer’s corpus but rare or filtered out in the model’s. Prompted with such a token, a model may behave erratically; documented 2023 investigations of so-called glitch tokens in GPT-2/3-family vocabularies (odd artifacts like usernames and debug strings) traced bizarre completions to exactly this gap. It is the purest illustration of this section’s central warning: the mapping from text to ids and the mapping from ids to behavior are learned separately, and everything depends on them staying consistent.

Common pitfalls

Fine-tuning loss is reasonable but generations are gibberish. Cause: tokenizer/checkpoint mismatch — ids no longer mean what the pretrained weights expect. Fix: always load the tokenizer distributed with the exact checkpoint; verify with a round-trip encode/decode of a sample sentence.
“My BPE implementation gives different splits than the paper’s example.” Cause: tie-breaking — several pairs often share the top count (as in this section’s first run, where three pairs tie at 9), and different implementations break ties differently. Fix: fix a deterministic tie-break rule and document it; small split differences are expected between implementations.
A BERT-style model is asked to continue a prompt and produces nonsense. Cause: family/task mismatch — masked-language models are not trained for left-to-right generation. Fix: match the family to the task: encoder-only for representation, decoder-only (or encoder–decoder) for generation.
Token counts (and API costs, and context usage) triple on non-English text. Cause: the tokenizer’s merges were learned mostly from English, so other scripts fall back toward characters or bytes. Fix: measure tokens-per-character on your data before budgeting context, and prefer tokenizers trained on the languages you serve.

Try it yourself

In the first script, continue to 12 merges. Predict which pairs win merges 9–12 before running, using the corpus counts.
Add {"slowest": 4} to the toy corpus and retrain. How do the learned merges change, and how does the unseen word “slower” now segment?
In the trade-off script, sweep merges from 0 to 60 in steps of 5 and record table size and corpus tokens for each. Where does compression visibly saturate for this corpus, and why must it saturate?
The end-of-word marker looks like a detail. Remove </w> from both scripts and rerun: find a concrete pair of strings that becomes indistinguishable, and explain what that would do to a language model’s outputs.
In the WordPiece comparison, compute by hand the association scores of e+s and i+d at step 1 from the corpus counts, and confirm they explain the two algorithms’ different first merges. Then predict what happens to WordPiece’s ordering if you add {"id": 20} (the word “id”) to the corpus, and check.
In the unigram script, double the count of west to 4 and rerun. Which segmentations flip, at what count would lo + west overtake low + est for “lowest”, and what does this tell you about how vocabulary probabilities steer segmentation?
Extend the pathologies script with a fifth test case of your own design that gets a worse tokens-per-character ratio than the German row, and explain the mechanism that makes it expensive.

Before class you should be able to

Write the pre-norm block’s two update lines, \(x + \mathrm{MHA}(\mathrm{LN}(x))\) and \(x + \mathrm{FFN}(\mathrm{LN}(x))\), and say why pre-norm is a common default (and what HW3 expects)
State the causal-mask property (editing token \(t\) leaves positions before \(t\) unchanged) and why one forward pass yields \(T\) next-token training examples
Trace a few BPE training merges by hand from word counts, and segment an unseen word by replaying merges
Explain what the number of merges controls and the costs on each side of the knob
Explain why a checkpoint must be paired with its own tokenizer, and the failure mode if not
State what byte-level BPE fixes and what it does not
Contrast the training objectives of BERT, GPT, and T5, and which can generate text
Match a task (classification, dialogue, translation) to the right model family with a reason
Explain why bidirectional models cannot be trained on next-token prediction

Connects to

This session is covered by Quiz 3 (Module 3: S13–S22), given at S23.
The project proposal is due the week of S23 — if your project touches text, the family-choice table is directly relevant to your architecture pick.
HW3 (out at S18): the tiny language model you train uses a deliberately simple tokenizer; this section explains what the real ones do.

← S16 · Transformer I · All readings · S18 · LLM Pretraining →

How to read this

The complete block, in one page

The vocabulary problem

Byte-pair encoding: learn the merges

The trade-off, measured

Same corpus, different algorithms: WordPiece and unigram

When tokenizers meet the real world

Three ways to keep a Transformer

Choosing a family

Going deeper

Common pitfalls

Try it yourself

Further reading

Before class you should be able to

Connects to