Chapter 19 Tokenizers in Depth: BPE, WordPiece, SentencePiece, and Byte-Level Models

Chapter 3 gave text pieces hand-written IDs. That was enough to explain a lookup table, but not how to choose useful pieces from a corpus. A whole-word vocabulary can become large and still encounter unseen words. A character vocabulary shares more pieces, but makes some sequences longer. We need a reproducible rule for choosing units between those extremes.

The choice affects more than a display of token boundaries. It determines which embedding row an ID selects, how long a context becomes, and what the output layer predicts. Changing the tokenizer after training changes the model’s interface. We will first learn four merges by hand, then freeze a different, explicitly versioned byte-based tokenizer for Chapters 20–21. Chapter 8’s distinction between original text and normalized search keys remains essential: a generator need not use the knowledge assistant’s search normalization.

19.1 Count adjacent symbols, with boundaries and ties specified

Example 19.1 — Learn four BPE merges. Use exactly four word occurrences: low, low, lower, new. Store them as word frequencies 2, 1, 1. Start each word as its individual characters followed by one special end-of-word symbol </w>. The marker is a single symbol, not four ordinary characters; it records where a word ends. No pair crosses a word boundary. This example takes already separated words and does not promise to preserve the original spacing between them.

The initial alphabet, in the order used for comparisons, is [</w>,e,l,n,o,r,w]. At each step count adjacent pairs of current symbols, weighting each word by its frequency. Choose the most frequent pair. If counts tie, choose the lexicographically smallest pair of symbol strings: compare the first string, then the second. Replace its non-overlapping occurrences from left to right with one concatenated symbol, and recount. Stop after four merges. These tie and stopping rules are part of this teaching specification, not universal BPE defaults.

Table 19.1 — Initial pair counts.

Pair	Count	Where it occurs
l + o	3	Twice in low, once in lower
o + w	3	Twice in low, once in lower
w + </w>	3	Twice in low, once in new
w + e	1	lower
e + r	1	lower
r + </w>	1	lower
n + e	1	new
e + w	1	new

Three pairs tie at 3. l + o wins because l sorts before o and w. Merge them to lo. In the new segmentation, lo + w occurs three times and w + </w> also occurs three times; lo sorts before w, so the second merge produces low. Now low + </w> occurs twice, while every other pair occurs once. That is the third merge. At step four all remaining pair counts are 1; e + r precedes e + w and the other first-symbol choices, so it wins.

Table 19.2 — Every merge and every intermediate word. Word frequencies stay 2, 1, 1 throughout.

Step	Chosen pair; count	low × 2	lower × 1	new × 1
0	Initial symbols	l o w </w>	l o w e r </w>	n e w </w>
1	l + o; 3	lo w </w>	lo w e r </w>	n e w </w>
2	lo + w; 3	low </w>	low e r </w>	n e w </w>
3	low + </w>; 2	low</w>	low e r </w>	n e w </w>
4	e + r; 1	low</w>	low er </w>	n e w </w>

This is byte-pair encoding, or BPE, adapted here to character symbols for subword segmentation. The historical compression name does not mean every modern BPE starts from raw bytes. Each merge in this example adds a piece to the seven-symbol initial inventory, giving eleven pieces after four merges. Older pieces remain available for other words. Character-based subword BPE, Section 3.2.

Step 1: tied at 3

1. A list of numbers(l,o):3; (o,w):3; (w,</w>):3
2. An operationLexical tie → merge l+o

Low contributes two occurrences and lower contributes one to l+o.

Steps 2 and 3: recount

1. An operation(lo,w):3 → low
2. An operation(low,</w>):2 → low</w>

There is no l+o pair inside the current lo symbol.

Step 4: tied at 1

1. An operation(e,r) precedes (e,w) → er
2. Text pieceslow</w> ×2; low er </w>; n e w </w>

Freeze all four ranked rules before encoding new words.

Figure 19.1 — The winning pair changes when the symbols change. Original teaching diagram, CC BY-SA 4.0. Values and rules are declared in the chapter and shared data.

Figure 19.1 shows why counts must be recomputed after a merge. We count adjacent symbols, not all character substrings hidden inside a merged symbol. The word frequency of low stays 2, even when its representation becomes one symbol.

19.2 Encode new text with the learned rules

Learning the vocabulary and encoding another input are different operations. Freeze the ranked merge list. To encode lower, start with l o w e r </w>, apply l+o, then lo+w; low+</w> cannot apply because e follows low. Apply e+r, leaving low er </w>. Do not recount pairs in the new input and invent a different merge order. Rank is part of the tokenizer artifact.

The boundary also matters. For low, the learned symbol is low</w>; for the beginning of lower, it is low without the boundary. Concatenating symbol contents and removing the declared word-end marker recovers the word. It does not recover whether two original words were separated by a tab or three spaces, because this training representation discarded that information before BPE began.

An unseen word assembled from known initial characters may still be encodable. But an unseen character is a different problem: this tiny alphabet has no symbol for the snowman ☃. A chosen unknown-token fallback would map it to [UNK], and decoding [UNK] cannot identify which unknown character was present. “Subword” alone does not imply complete coverage or exact reconstruction.

19.3 WordPiece and SentencePiece answer different questions

Example 19.2 — A supplied WordPiece vocabulary. Give a tokenizer only [UNK], low, ##er, and new. The ## prefix marks a continuation piece rather than literal hashes in the word. In the official BERT encoding procedure, the tokenizer seeks the longest vocabulary match at the current offset. lower has no whole-word match, but begins with low; the remaining er matches ##er, giving [low,##er]. For lowerz, the z suffix cannot be covered. That implementation returns [UNK] for the whole word, not [low,##er,UNK].

This is an encoding rule for a given vocabulary. WordPiece vocabulary learning is associated with improving a language-model likelihood criterion: the probability assigned to the observed training text. Our BPE instead picks the largest adjacent-pair count. The official BERT tokenizer file does not contain that vocabulary trainer. It would be misleading to label an informal pair-score shortcut as the unique original WordPiece training algorithm. Its earlier basic tokenization can also change case, accents, spacing or CJK boundaries depending on configuration. The tiny example isolates the word-piece stage; it is not a complete BERT text pipeline. GNMT, Section 4.1, official BERT tokenizer.

SentencePiece is a software framework that supplies normalization, vocabulary training, encoding and decoding. It can train BPE or a unigram subword model, among other choices. A unigram model assigns probabilities to pieces and scores possible segmentations; it is not the ranked merge procedure just executed. Thus “BPE versus SentencePiece” mixes an algorithm choice with a tool choice. A tokenizer can be both BPE and trained by SentencePiece.

SentencePiece can work from raw sentences and represents whitespace explicitly. Its paper’s reconstruction relation is to the normalized input. The verified release’s default normalization is NFKC-based, and configuration/coverage still matter. That is different from guaranteeing recovery of every original code point or every possible input under all settings. The implementation notes and verified version are in the research record; no SentencePiece performance measurement is claimed here. SentencePiece, Sections 2–3, official release documentation.

19.4 Start from bytes when exact text coverage matters

Chapter 8 distinguished a Unicode code point from the bytes storing it. In UTF-8, 中 uses three bytes [228,184,173], and 🙂 uses four [240,159,153,130]. If every one of the 256 possible byte values has a base token, any valid UTF-8 input can be represented before learning a single merge. A rare character can require several tokens; representation does not mean understanding.

Example 19.3 — Freeze the Mini GPT byte BPE. The shared tokenizer book-byte-bpe-v1 starts with IDs 0–255 representing those exact byte values. IDs 256, 257 and 258 are reserved for BOS, EOS and PAD. It learns 32 merges from the 24 training records only, never across record boundaries or special tokens. Each new piece gets the next ID, starting at 259. The final vocabulary has 291 entries. There is no normalization, case conversion, whitespace splitting or punctuation pretokenization. Literal text such as BOS is still encoded as bytes; the record-building code adds the special BOS ID explicitly.

The merge tie rule here uses the smallest ordered pair of integer IDs after highest count, rather than Example 19.1’s symbol-string order. This is a separately named tokenizer, not a silent modification of the word-boundary example. The first merge is bytes 58 and 32, colon plus space, seen 25 times; new ID 259 represents : . Later, ID 268 represents key, ID 270 red, and ID 282 750. All 32 ranked pairs and counts are visible in data/mini-gpt/tokenizer.json. The code replays those pairs at encoding time.

Table 19.3 — Actual encoding with the same frozen tokenizer. Counts exclude automatically added special tokens; none are added in this table.

Exact input	Code points	UTF-8 bytes / base-byte tokens	BPE tokens	Original input recovered?
red key .	9	9	5	Yes
法国首都是巴黎。	8	24	24	Yes
中	1	3	3	Yes
🙂	1	4	4	Yes
e followed by U+0301	2	3	3	Yes
é (U+00E9)	1	2	2	Yes
Fullwidth A, space, A: Ａ A	3	5	5	Yes

The first input becomes [270,32,268,32,46]: red, space, key, space, full stop. 中 remains [228,184,173], and the emoji remains [240,159,153,130]. The corpus contains little Chinese, and this particular 32-merge budget selected no Chinese-byte merges. These results compare a fixed corpus and two encodings of the same strings; they do not establish a universal English/Chinese token ratio. The round-trip tests also retain two leading spaces, repeated internal spaces and a trailing newline in a separate fixed case.

Learned English pieces

1. Text piecesred key .
2. Row number[270, 32, 268, 32, 46]
3. An operationred + space + key + space + .

Five tokens; exact spaces preserved.

Base-byte coverage

1. Text pieces中 → bytes E4 B8 AD
2. Row number[228, 184, 173]
3. An operationJoin bytes → strict UTF-8 → 中

Three tokens for one code point; do not decode each token alone.

Generation has a different boundary

1. Row numberGenerated ID 255 → byte FF
2. An operationStrict UTF-8 → UnicodeDecodeError

Input coverage does not guarantee that arbitrary generated bytes form valid text.

Figure 19.2 — Join byte payloads before decoding the string. Original teaching diagram, CC BY-SA 4.0. Values and rules are declared in the chapter and shared data.

Figure 19.2 follows the actual bytes and IDs back to text. A token’s byte payload can end in the middle of a multi-byte character. To decode a complete encoded input, concatenate all ordinary token payloads first, then decode the combined bytes as UTF-8. Trying to decode each byte token as a separate character would fail for 中.

A text prefix is not necessarily a token prefix. The byte tokenizer encodes a final colon as ID 58, but a colon followed by a space becomes ID 259. Stopping a prompt just before that space changes the last input token relative to the fully encoded training record. Exact round trip does not remove this boundary effect. Chapter 21 keeps the original failed prompts and adds a matched-boundary comparison; generation itself appends selected IDs without re-encoding the whole growing string.

19.5 A shorter sequence is not automatically a better interface

Example 19.4 — Two round-trip failures with different causes. The visually similar forms e plus U+0301 and precomposed é have different original code-point sequences. Our no-normalization byte tokenizer preserves each exactly. If we first apply NFC, both normalize to é; the first form cannot be recovered from that normalized result alone. This is a deliberately demonstrated normalization loss, not a measured failure of SentencePiece. By contrast, replacing ☃ with [UNK] loses information through missing coverage. Keeping raw text elsewhere can preserve an original record, but does not make its token sequence reversible by itself.

Complete byte coverage does not ensure valid generated text either. The input encoder produces bytes of a valid string; a randomly chosen output token need not obey UTF-8. The single base token 255 corresponds to byte FF, which is invalid alone in UTF-8. Our strict decoder raises UnicodeDecodeError. Generation records must state whether they stopped, returned raw bytes, or displayed replacement characters. Silently printing a replacement symbol would conceal the difference between exact decoding and a display fallback.

More merges can shorten frequent strings, but a bigger vocabulary increases the embedding and vocabulary-output tables. With model width C and V vocabulary entries, an untied input table and output matrix together contain $2VC$ scalar weights, excluding biases. For C=16, moving from 259 entries to 291 adds $2\times32\times16=1024$ weights. Attention score storage depends on squared sequence length, so shorter sequences can save work there; the larger vocabulary costs work elsewhere. Rare merged pieces also have fewer training observations. Neither fewer tokens nor a perfectly reversible encoding proves better task accuracy.

This makes versioning a model requirement. Save the alphabet and ID order, ranked merges, special IDs, normalization, boundary rules, trainer version and training-data identity. Merely keeping the vocabulary size is insufficient: swapping the IDs for red and key leaves every shape unchanged but selects the wrong embedding rows and mislabels the output scores. A model checkpoint must match the tokenizer’s exact identity, or a deliberate migration must remap the corresponding model rows/columns and all affected data.

19.6 Reproduce the interface before training the model

The shared CPU program code/part-iv/tokenizer_example.py calculates the hand merge trace, checks it against the independently established pair/count/segmentation table, exercises the supplied WordPiece vocabulary, and runs strict round trips with code/mini-gpt/tokenizer.py. The latter trains the small byte tokenizer and saves its complete artifact. data/part-iv/tokenizer-run.json contains the actual outputs, code-point/byte/token counts and normalization counterexample. Neither program downloads a vocabulary or model.

For this frozen tokenizer, the canonical SHA-256 identity is 9bb146ce375bda3aa518a48a60d9f69611b8d0afde9df9a8298eae9dfa9dd354. This long string is a reproducibility identifier, not a quantity to memorize. The data card specifies the canonical serialization, distinct from hashing a pretty-printed JSON file. Chapter 20 will bind this identity to the dataset, embedding table and language-model head.

19.7 What the tokenizer has established

We can now explain how an adjacent-pair rule creates a vocabulary, how a frozen vocabulary/rule set encodes another input, and why tool names, algorithm names, initial alphabets and normalization belong to different decisions. The Mini GPT interface has complete byte coverage and tested exact input reconstruction. It has not learned language; only its representation units have been fitted to training text.

The next step is to turn each record into an input sequence and a one-position-shifted target, then follow those IDs through the complete block to logits and loss. That is MG-1 in Chapter 20.

19.8 Exercises

1. Double new’s frequency from 1 to 2 in Example 19.1. Recompute the initial counts that can win, and choose the first merge under the same tie rule. Explain why reusing the original first merge would be wrong.
2. After the original four merges, encode low and lower. Does a new occurrence of lower change the merge ranking? What original spacing information can this word-level setup not recover?
3. With the supplied WordPiece vocabulary, encode lowerz. Why does the official BERT-style rule differ from keeping the successful prefix and adding an unknown suffix?
4. Can exact round trip and fewer tokens prove good handling of Chinese? Use the byte examples to distinguish coverage, sequence length, and learned task behavior.
5. A new tokenizer keeps 291 entries but swaps IDs 268 and 270. Which model/data interfaces are affected? Why does a shape check pass?
6. A generator emits token ID 255. What bytes does it represent here, and what should a faithful result record say if the UI displays a replacement character?

19.9 Reference answers

1. w + </w> now occurs twice in low and twice in new, giving 4. l + o and o + w remain 3. Thus the first merge is w + </w> with count 4. The original first merge was justified by a tie at 3; changing corpus frequencies changes that premise.
2. Low becomes [low</w>]; lower becomes [low,er,</w>]. Encoding replays the frozen ranked rules; it does not train on the new occurrence. The original tabs, multiple spaces or other separators between words were discarded before these word records were constructed.
3. It returns [UNK] for the whole word when the remaining z cannot be segmented. Keeping [low,##er,UNK] would be a different fallback contract with different IDs and reconstruction behavior. The example does not imply all WordPiece implementations must have identical preprocessing or fallback policies.
4. Coverage means the input has a representation; round trip means it can be reconstructed under the declared normalization. Sequence length measures how many units represent this particular string. Task behavior requires a trained model and controlled evaluation. Here Chinese round-trips using 24 byte tokens while the frequent English key phrase compresses; neither establishes comparative understanding.
5. Re-encode stored datasets and prompts consistently; remap the input embedding rows, output vocabulary columns and any output biases for those IDs if preserving the old function. Special IDs, merge references and artifact identities must also be consistent. Dimensions stay 291, so a shape assertion cannot detect the exchanged meanings.
6. It is byte FF, invalid as a standalone UTF-8 string. The strict decoder fails. A display fallback may show a replacement character, but the record must retain the raw byte/token ID and identify replacement decoding rather than claim the model generated that valid original character.

19.10 References

• Sennrich, Haddow, and Birch (2016), Neural Machine Translation of Rare Words with Subword Units. Section 3.2 motivates frequency-weighted character BPE with word boundaries. Our corpus and tie rules are original and explicit.
• Wu et al. (2016), Google’s Neural Machine Translation System, Section 4.1; Google Research, BERT tokenization implementation. The former describes WordPiece vocabulary learning; the latter implements longest-match encoding and whole-word unknown fallback for a supplied vocabulary.
• Kudo and Richardson (2018), SentencePiece, Sections 2–3; SentencePiece v0.2.1 documentation. Explain the software components, algorithm choices, whitespace and normalization contract.
• Kudo (2018), Subword Regularization, Section 3. Introduces the unigram segmentation model that helps distinguish an alternative algorithm from the SentencePiece tool containing it.