Handout #9 — Tokenization and Subwords

A learned subword tokenizer represents text as reusable pieces. Its surrounding pipeline decides what to preserve, where to split, and how to mark structure. Two systems can both use BPE and still give different inputs to a language model. This handout explains why, with small examples you can work through and experiments you can run.

Handout #8 introduced word, character, and subword tradeoffs. Here we follow the consequences: what information survives the pipeline, how merges are learned, and how those same merges are used on new text. Predict each result before opening its answer.

1A pipeline, with several chances to lose information

Slides 13–18

For an ordinary text string $x$, a lossless text codec should satisfy $D(E(x))=x$, where $E$ encodes and $D$ decodes. That does not automatically hold for the complete model-input pipeline: normalization can alter $x$, truncation can remove a suffix, and post-processing can insert structural tokens. Always state which operations your round-trip test includes.

1.1 Normalization chooses which distinctions to erase

Suppose the inputs are A and Ａ (fullwidth A). NFKC maps both to A. A decoder receiving only that normalized value cannot know which original was supplied. More training data cannot recover a distinction that the representation removed.

NFC combines canonically equivalent representations, such as e plus a combining acute accent and precomposed é. NFKC also folds compatibility variants, such as fullwidth letters. Neither promises recovery of the original code-point sequence; neither is a general rule for equating everything that looks alike. See Unicode UAX #15.

import unicodedata as ud
assert ud.normalize("NFC", "e\u0301") == "é"
assert ud.normalize("NFKC", "Ａ") == "A"
assert "e\u0301".encode("utf-8") != "é".encode("utf-8")

Other cleanup rules have similar consequences: lowercasing merges US with us; collapsing repeated spaces can change code indentation; dropping punctuation changes Let's eat, Grandma!. Such transformations can suit a task, but “cleaner” does not imply “equivalent.” A reversible merge algorithm cannot undo a lossy preprocessing step.

1.2 Pre-tokenization puts walls around the merge algorithm

Take two chunks, [the] and [ cat]. The leading space is part of the second chunk. A merge can build cat inside that chunk, but cannot build the cat across the wall. A token containing a space is therefore not necessarily a token spanning two words.

Pre-tokenization and BPE answer different questions: where may pieces combine? and which permitted combinations were learned? Increasing the vocabulary cannot overcome a boundary imposed by the first stage. Training and encoding must use compatible rules; changing the regex changes the tokenizer even if the merge table stays fixed.

Throughout our character examples, · displays one actual space. Square brackets surround pre-tokenizer chunks; vertical bars inside them separate current tokens. Neither notation is inserted into the source text.

1.3 Post-processing prepares a sequence for a model

Consider content token IDs [17, 42]. A hypothetical model expects [BOS, 17, 42, EOS]; a batch may then append PAD to match another example's length. These operations serve different purposes.

UNK signals a coverage failure; PAD fills unused positions; EOS is a meaningful boundary that the model may need to predict. They are not interchangeable roles. An attention mask controls which positions the model may attend to; a loss mask controls which targets contribute to the objective. Verify both in a training pipeline.

Chat protocols also assign dedicated IDs to message boundaries and other structure. The readable spelling of a special token and that token's ID are different things: literal text that resembles a marker need not become a control token. Recognition depends on the encoder's special-token policy and the template that constructs the conversation. Learn the role of these markers rather than memorizing any one model's spellings.

2Training BPE: a small compression experiment

Slides 19–28

BPE training repeatedly selects a frequent adjacent pair, creates a new vocabulary entry for its concatenation, and replaces non-overlapping occurrences. The vocabulary retains the old entries too. This is a discrete procedure over a text corpus, separate from neural-network training and backpropagation.

The learned object is not just a bag of substrings. Keep the base alphabet, ordered merge rules, token-to-ID mapping, and preprocessing configuration. Encoding new text needs that same contract.

2.1 Extend the slide example, one decision at a time

Use the slide corpus jhu jhu jhu hopkins hop hops hops, with each space attached to the following word. There are 33 initial character tokens and 10 distinct base symbols. Count adjacent pairs inside the seven chunks; never count across their boundaries.

[j | h | u] [· | j | h | u] [· | j | h | u]
[· | h | o | p | k | i | n | s] [· | h | o | p]
[· | h | o | p | s] [· | h | o | p | s]

Initially, · + h, h + o, and o + p each occur four times. Frequency alone does not choose among them. The slides choose h + o; that is a valid tie choice, not a uniquely determined answer.

Step 2 requires recounting: the old pair h + o has disappeared and new pairs such as ho + p exist. After step 3, the chunks ending in hopkins, hop, and hops share a token ·hop. This sharing follows frequency; it does not establish a shared linguistic meaning.

For this example, if each merge creates a distinct entry and there are $M$ merges and $S$ special entries, $|V|=10+M+S$. For byte-level BPE, replace 10 by 256. A vocabulary count and a corpus token count measure different things: one grows while the other shrinks here.

Try this: follow h + o, then ho + p, then · + hop. Reset and choose · + h first. Both are valid frequency-based training paths, but they learn different intermediate entries. Reproducible training therefore needs a tie-breaking policy.

2.2 Counting occurrences is not the same as replacing them

In a a a, the adjacent pair (a,a) occurs at positions (1,2) and (2,3). The count is 2, but those occurrences overlap. A left-to-right non-overlapping replacement yields aa a, which saves only one token.

This distinction matters when predicting compression. Pair counts can overestimate the immediate number of replacements for repeated symbols. The algorithm is still well-defined if the replacement convention is fixed. It is a greedy heuristic, not a proof that every step gives the largest possible compression gain.

3Encoding: use the learned ranks, not new frequencies

Slides 29–30 and 32. Efficient implementation is bonus (§8.1).

Once training ends, the tokenizer's parameters are fixed. On a new chunk, begin with base units and repeatedly apply the earliest-learned currently applicable rule. Stop when no learned rule applies. A low rank means high priority; the numeric token ID only doubles as a rank in implementations that deliberately assign IDs in merge order.

3.1 A rule can become applicable only after another rule

The slides' rules are l+o→lo (rank 1), lo+w→low (2), e+r→er (3), and low+er→lower (4). For lowered:

[l | o | w | e | r | e | d]
[lo | w | e | r | e | d]     rank 1
[low | e | r | e | d]        rank 2, before rank 3
[low | er | e | d]           rank 3
[lower | e | d]             rank 4

The tokenizer never saw a rule for lower+e, so it stops. It can represent an unseen word using smaller known pieces; it need not store every word. This example assumes the required base characters are supported.

3.2 Why “take the longest token” is not BPE

Consider another learned table, in this order: b+c→bc, a+b→ab, c+d→cd. For example, these can be learned from separate chunks bc repeated four times, ab three times, cd twice, and abcd once. Encoding abcd applies b+c first, yielding [a | bc | d]. The entries ab and cd exist, but neither can form after b and c have been consumed together.

So BPE does not generally search for the segmentation with the fewest tokens or take the longest vocabulary match. The ordered rules matter. Here [ab | cd] would use only two tokens, while BPE produces three. Decoding [ab | cd] and [a | bc | d] gives the same text, but encoding that text selects one canonical sequence under this tokenizer. Thus $D(E(x))=x$ does not imply $E(D(z))=z$ for every arbitrary token sequence $z$.

4Bytes solve coverage, not every representation problem

Slides 33–34 and the coverage issue in slide 36

Character BPE initialized only with characters seen in training can encounter a new character it cannot represent. Adding more merges does not repair a missing base unit. Byte-level BPE instead begins with all 256 possible byte values and converts text to UTF-8 bytes before applying merges. Every well-formed Unicode text string has a UTF-8 representation, so the ordinary-text codec needs no unknown token for an unseen word or character.

Keep three levels distinct: a visible character can contain several Unicode code points; a code point can require several UTF-8 bytes; a BPE token can hold one byte or many. “One character = one byte = one token” is only true in particular examples.

Coverage is not compression. A rarely seen script or domain may be representable but need more tokens per passage. Under a fixed token budget, that leaves less room for context. Token counts depend on the training mixture and learned vocabulary; there is no universal character-to-token ratio.

4.1 Concatenate bytes first, then decode the text

A byte token need not be valid UTF-8 by itself. Suppose two token entries contain C3 and A9. Together they form é. Decoding each separately with replacement characters loses information before concatenation.

pieces = [bytes([0xC3]), bytes([0xA9])]
assert b"".join(pieces).decode("utf-8") == "é"
assert "".join(p.decode("utf-8", errors="replace") for p in pieces) == "��"

This is why a vocabulary viewer may display an odd fragment or a replacement glyph for a perfectly useful token. A round trip from valid text preserves valid bytes when preprocessing is lossless. Arbitrary model-generated IDs are a different case: their concatenated bytes may be invalid UTF-8, so a decoder needs a policy such as replacement or incremental buffering.

5What changes for the language model?

Vocabulary tradeoff in slide 32; algorithm/library distinction in slide 33; limitations in slide 36

5.1 Moving cost from sequence length to vocabulary size

An embedding table with vocabulary size $|V|$ and hidden size $d$ has $|V|d$ parameters. An untied output projection adds another $d|V|$ weights (plus any bias). Weight tying shares the matrix but does not eliminate the cost of producing vocabulary logits.

For a concrete illustration, let $d=1024$ and increase the vocabulary from 32,000 to 48,000. Each matrix gains $16{,}000\times1024=16{,}384{,}000$ parameters. At two bytes per weight that is 32.768 MB, or 31.25 MiB, per matrix, before gradients and optimizer state. If this change reduces a passage from 1,000 to 800 tokens, it also reduces the number of prediction positions. Whether total training becomes cheaper depends on both effects and the architecture.

Do not read a vocabulary-size leaderboard as a quality ranking. Corpus, language mixture, model size, context budget, and implementation all affect the useful tradeoff. Likewise, a library is not an algorithm: SentencePiece supports more than one segmentation algorithm, and BPE can use characters or bytes as its base units. Compare those axes separately.

5.2 Useful pieces need not be morphemes

The example Under | stand does not mean “stand beneath.” BPE rewards recurring adjacent forms; it does not optimize a linguistic analysis. Sharing pieces can help parameter reuse without guaranteeing that the shared substring has the same meaning everywhere.

There is also a structural limitation: contiguous pieces cannot directly isolate a root whose consonants are interleaved with other material, as in Arabic root-and-pattern morphology. Changing a few merge ranks cannot turn a contiguous segmentation into a noncontiguous analysis. The model may still learn such relationships from context; tokenization simply does not encode them explicitly.

5.3 The tokenizer and the checkpoint are one interface

If ID 100 means cat in the pretrained tokenizer but enzyme in a replacement, embedding row 100 and output logit 100 retain their old learned meanings. A successful tensor-shape check will not catch this semantic mismatch. Save and load the tokenizer configuration with the checkpoint.

A compatible change must preserve or deliberately adapt the model's ID-to-piece relationship. Appending new entries also requires suitable embedding/output rows and training; preserving old IDs alone does not teach the model the new entries. Even a normalization or pre-tokenization change can shift inputs while leaving every tensor shape unchanged.

6Core practice: explain the failure, then repair the test

These checks use only core material. They do not require efficient priority queues, byte-fallback internals, WordPiece, Unigram LM, or the other bonus topics.

Show all answers

7Read real code: a small tokenizer you can take apart

BasicTokenizer is intentionally simpler than the slide pipeline: it uses raw UTF-8 bytes, without pre-tokenization or special-token handling. It can therefore learn merges across spaces and word boundaries. Do not expect it to reproduce the chunked jhu exercise or a production tokenizer's output.

7.1 Find the training decision

basic.py · BasicTokenizer.train · verbatim line

pair = max(stats, key=stats.get)

Trace how get_stats obtains stats, how the next ID is assigned, and how merge rewrites the sequence. Connect these operations to §2. Then inspect base.py: the counter sees overlapping pairs, while replacement advances by two after a match. That is the overlap distinction in §2.2.

7.2 Find the encoding decision

basic.py · BasicTokenizer.encode · verbatim line

pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))

Here the pair counts are not the priority. The dictionary keys identify adjacent candidates; stored merge IDs supply their order. Inspect the following membership check: it stops when no candidate has a learned rule. IDs work as ranks in this implementation because training assigns new IDs monotonically (§3).

7.3 Find the decoding decision

basic.py · BasicTokenizer.decode · verbatim line

text_bytes = b"".join(self.vocab[idx] for idx in ids)

The next line UTF-8 decodes the concatenated bytes. Moving decoding inside the loop would break multibyte characters (§4.1). Read the vocabulary construction in train: each new token stores the concatenation of its two parents’ byte strings.

7.4 Change one word, observe a different tokenizer

In a local checkout of minbpe at the linked revision, run this from the repository root. For this tiny ASCII corpus, ties are resolved by first encounter in the dictionary; that is the behavior of the pinned implementation.

from minbpe import BasicTokenizer
from minbpe.base import get_stats, merge

tok = BasicTokenizer()
tok.train("ababac", vocab_size=258)
assert tok.merges == {(97, 98): 256, (256, 256): 257}
assert tok.encode("ababac") == [257, 97, 99]
assert tok.decode(tok.encode("café 😀")) == "café 😀"
assert get_stats([1, 1, 1]) == {(1, 1): 2}
assert merge([1, 1, 1], (1, 1), 2) == [2, 1]
print(tok.encode("ababac"))  # [257, 97, 99]

For one final code check, replace the decode method with one that decodes each vocabulary entry separately. Use an untrained BasicTokenizer() on é: correct decoding returns é; per-token replacement decoding returns ��. Restore the original method. Together these probes distinguish an algorithmic training error, an exhaustion error, and a decoding error.