Tokenization

Chapter 6 defined which text the training run will sample. Before that text can reach a model, a tokenizer must turn it into integer ids. The mapping affects sequence length, multilingual coverage, numerical and code structure, the shape of token-indexed model parameters, and compatibility with every checkpoint and data shard that follows.

This is not just a vocabulary-building problem. A production tokenizer also specifies Unicode normalization, boundaries, byte handling, special tokens, automatic prefix and suffix insertion, and decoding. Those decisions form a versioned model interface. They should be measured and frozen with the same care as an architecture or data mixture.

The artifact is more than a vocabulary

A model consumes ids, but several ordered transforms produce them:

The tokenizer is this full contract, not only the segmentation model. A vocabulary file without the normalizer, boundary rules, special-token ids, and decoder can produce a different id sequence while appearing to contain the same pieces.

Here the ids index model parameters. For vocabulary size $V$ and model width $d$, the input embedding is a matrix $E\in\mathbb{R}^{V\times d}$. An untied output projection has another token-indexed matrix $W_{\mathrm{out}}\in\mathbb{R}^{V\times d}$; a tied model reuses $E$. Changing the meaning of an existing id therefore changes the meaning of an existing row in the checkpoint. That is the central compatibility constraint.

The boundary rules matter before any merge is learned. They decide whether a piece may cross whitespace, punctuation, script changes, or a protected span. The original neural-machine-translation BPE operated inside externally split words. GPT-2-style byte-level BPE first applies a regular expression over categories such as letters, numbers, punctuation, and whitespace. SentencePiece can train from raw sentences without an external language-specific word segmenter, but it still applies configured normalization and boundary behavior (Sennrich et al. 2016; Kudo and Richardson 2018; Radford et al. 2019).

BPE learns merge priorities

Sennrich, Haddow, and Birch adapted byte-pair encoding (BPE), a compression algorithm, to open-vocabulary neural machine translation in 2016 (Sennrich et al. 2016). BPE starts from base symbols and repeatedly joins a frequent adjacent pair. The result is an ordered merge table: earlier merges have higher priority during encoding.

A conceptual trainer is:

1. Normalize and split the training corpus with the frozen boundary rules.
2. Express every pretoken as base symbols plus any boundary marker.
3. Count adjacent symbol pairs, weighted by pretoken frequency.
4. Select the highest-count pair with a deterministic tie-break rule.
5. Replace every non-overlapping occurrence of that pair in the corpus.
6. Append the pair to the ordered merge table.
7. Repeat steps 3–6 until the target vocabulary size is reached.

Here a pretoken is one segment emitted by the boundary rule; the base symbols are characters, bytes, or another guaranteed starting alphabet; and the merge table records both the selected pairs and their ranks. The tie-break rule is part of reproducibility because many corpora contain equally frequent pairs.

Training and encoding are different algorithms. Training counts frequencies and changes the corpus representation after each selected merge. Encoding does not recount the input. It starts from base symbols and repeatedly applies the available learned pair with the best rank, without crossing a protected boundary. A naive pedagogical trainer rescans all symbol positions for every merge; production trainers maintain pair-occurrence indexes and update only affected neighbors. Complexity therefore depends on the implementation, not on the name “BPE” alone.

The interactive example uses low low low lo, so (l, o) occurs four times while (o, w) occurs three times. There is no hidden tie in the first step.

The runnable cell trains a small character BPE, freezes its merge order, and then encodes held-out words. Its end-of-word marker prevents merges across word boundaries. The final example deliberately contains an unseen character to show that character BPE is not automatically free of unknown tokens.

from collections import Counter

EOW = "</w>"
UNK = "<unk>"

def merge_pair(symbols, pair):
    left, right = pair
    out, i = [], 0
    while i < len(symbols):
        if i + 1 < len(symbols) and symbols[i] == left and symbols[i + 1] == right:
            out.append(left + right)
            i += 2
        else:
            out.append(symbols[i])
            i += 1
    return out

training_words = "low low low lo lower newest widest".split()
base_symbols = set("".join(training_words))
encoded_training = [list(word) + [EOW] for word in training_words]
merges = []

for _ in range(8):
    counts = Counter()
    for symbols in encoded_training:
        counts.update(zip(symbols, symbols[1:]))
    if not counts:
        break
    # Highest count first; lexical order makes ties deterministic.
    pair = min(counts, key=lambda candidate: (-counts[candidate], candidate))
    merges.append(pair)
    encoded_training = [merge_pair(symbols, pair) for symbols in encoded_training]

def encode_word(word):
    symbols = [char if char in base_symbols else UNK for char in word] + [EOW]
    for pair in merges:
        symbols = merge_pair(symbols, pair)
    return symbols

print("merge ranks:", [left + "+" + right for left, right in merges])
for word in ["low", "lower", "lowest", "lobster"]:
    pieces = encode_word(word)
    print(f"{word:7s} -> {' '.join(pieces)}  ({len(pieces)} pieces)")

print("UTF-8 bytes for 🐍:", list("🐍".encode("utf-8")))

Byte coverage is not efficient coverage

A generic subword model is open only over its base alphabet. A character BPE can still emit an unknown token for a character absent from that alphabet. Completeness requires an exhaustive base representation or a fallback path.

Byte-level BPE uses all 256 byte values as its base alphabet. A valid Unicode string is encoded as UTF-8 bytes, so every string accepted by the text API has a representation without an encoder-side unknown token. Implementations such as GPT-2 map the bytes to reversible placeholder characters before learning merges; other implementations operate on byte values directly (Radford et al. 2019; Wang et al. 2020). This coverage guarantee does not say the encoding will be short. A rare script, emoji sequence, or binary-looking span may fall back to many byte-sized pieces.

Byte fallback is related but not identical. A character BPE or Unigram model with fallback learns ordinary pieces over characters and emits byte tokens only when a character is otherwise unknown. Byte-level BPE learns its full merge system over a byte base. Both can avoid an unknown token when configured correctly, but they induce different segmentations.

The decoder also needs an error policy. A valid input string becomes valid UTF-8 bytes, but an arbitrary sequence sampled by a model can end inside a multi-byte character or combine bytes into invalid UTF-8. Replacement, strict failure, and byte-preserving display are different contracts.

Normalization changes what can round-trip

Let $N$ be the declared normalizer. Under a deterministic tokenizer with no lossy decoder cleanup, the intended invariant is

$$\operatorname{Decode}(\operatorname{Encode}(x))=N(x).$$

Here $x$ is the input string, $N(x)$ is its normalized form, and $\operatorname{Encode}$ and $\operatorname{Decode}$ are the frozen tokenizer functions. Equality with the original $x$ holds only when $N$ preserves the relevant distinctions. Unicode compatibility normalization, case folding, or whitespace collapsing can intentionally map different raw strings to the same normalized string.

SentencePiece makes whitespace visible to its segmentation model and can reconstruct the normalized stream unambiguously. That does not imply a byte-for-byte round trip to raw input under every normalizer and whitespace configuration (Kudo and Richardson 2018). Code indentation, combining marks, full-width forms, right-to-left text, emoji joiners, and no-space scripts all belong in normalization tests.

Unigram scores complete segmentations

Kudo introduced the Unigram language-model tokenizer in 2018 as a probabilistic alternative to merge-ranked BPE (Kudo 2018). It starts with a large candidate vocabulary, estimates piece probabilities, and prunes pieces whose removal least reduces corpus likelihood. It models an ordered segmentation, not a bag of pieces.

For normalized input $X$, the model is

$$P(z)=\prod_{j=1}^{m}p(z_j), \qquad z^*=\arg\max_{z\in\mathcal{S}(X)}P(z), \qquad \mathcal{L}=\sum_{X\in D}\log\!\sum_{z\in\mathcal{S}(X)}P(z).$$

Here $z=(z_1,\ldots,z_m)$ is one ordered segmentation of $X$; $z_j$ is its $j$-th piece; $p(z_j)$ is that piece's learned probability; $\mathcal{S}(X)$ is the set of valid segmentations under the vocabulary; $z^*$ is the highest-probability segmentation; and $D$ is the tokenizer-training corpus. Dynamic programming finds $z^*$. Training alternates probability estimation with vocabulary pruning.

Because the model assigns probability to complete segmentations, training can sample alternatives instead of always choosing $z^*$. Kudo called this subword regularization and reported it as useful augmentation in neural machine translation (Kudo 2018). It does not remove the need for a complete base alphabet or byte fallback.

BPE and Unigram therefore expose different controls. BPE deterministically applies learned merge priorities. Unigram scores a segmentation lattice and can sample paths through it. Neither is universally better; compare them under the same corpus, vocabulary budget, model compute, and evaluation suite.

Vocabulary size changes both sequence and model cost

A larger vocabulary often compresses in-distribution text into fewer tokens. It also adds token-indexed parameters and makes a dense output projection score more candidates at every position. The token-indexed parameter count, ignoring biases, is

$$P_{\mathrm{token}}= \begin{cases} Vd, & \text{if input and output weights are tied},\\ 2Vd, & \text{if they are untied}. \end{cases}$$

Here $V$ is vocabulary size, $d$ is model width, and $P_{\mathrm{token}}$ counts parameters in the input embedding and output projection. Weight tying reuses one matrix. Optimizer state, quantization, sharding overhead, and output-projection compute are not included.

Figure 7.3 plots this exact relationship for an illustrative width of 4,096 with two bytes of parameter storage. It does not claim a universal optimal vocabulary size.

Sequence length changes the rest of the model's work, while vocabulary size changes both storage and logit computation. Whether a larger vocabulary is cheaper depends on model width, weight tying, hardware, sequence lengths, fixed-token versus fixed-document budgeting, and the serving workload. Tao et al. found a compute-dependent optimum in controlled scaling experiments, not a single vocabulary size that transfers to every run (Tao et al. 2024).

The tokenizer's training mixture matters just as much as $V$. Sampling English web prose, source code, mathematics, and low-resource languages at their raw byte proportions can spend most learned pieces on the largest source. A tokenizer-specific mixture may deliberately rebalance those domains, but that policy and its downstream effect must be recorded. Rare pieces also need enough training occurrences to learn useful rows in the model.

Token-level perplexity cannot compare two tokenizers directly because each defines a different unit. Use a common source unit such as bits per UTF-8 byte, character, or another explicitly defined unit when comparing language models with different tokenizers.

Measure languages and domains, not only compression

“Tokens per word” is not a fair universal metric because languages disagree on what a word boundary is. Parallel content provides a clearer comparison. For parallel item $i$, language $\ell$, reference language $r$, and tokenizer $T$, define the token premium

$$p_{\ell,i}=\frac{|T(s_{\ell,i})|}{|T(s_{r,i})|}.$$

Here $s_{\ell,i}$ and $s_{r,i}$ express the same item in languages $\ell$ and $r$; $|T(s)|$ is the number of emitted tokens; and $p_{\ell,i}$ is the sentence-level premium relative to the reference. Report its distribution, including median and upper quantiles, rather than one hand-picked sentence.

Petrov et al. applied this kind of comparison to parallel translations and found large token-count differences across languages for several tokenizers, including systems designed for multilingual use (Petrov et al. 2023). The result directly affects per-token pricing and usable context. If a parallel content slice has premium $p$, a fixed $C$-token window holds roughly $1/p$ as much of that content as the reference, before prompt-format overhead. Actual latency still depends on batching, kernels, model architecture, and whether the extra tokens occur in prefill or serial generation.

Figure 7.4 shows the audit procedure rather than invented token counts.

Token premium is one metric, not a quality score. Rust et al. found that tokenizer choice can contribute to multilingual downstream differences even when controlling pretraining data, but data coverage, morphology, script, objective, and model capacity also matter (Rust et al. 2021). Report at least:

• tokens per Unicode scalar, grapheme cluster, and UTF-8 byte, with the unit named explicitly;
• unknown-token and byte-fallback rates;
• median, p95, and maximum sequence lengths, plus truncation at the deployed context limit;
• encode and decode throughput on representative hardware;
• slices for prose, code, numbers, formulas, URLs, emoji, and mixed scripts;
• normalization collisions and source-to-token offset accuracy.

Numbers deserve their own ablation. Digit-wise, left-grouped, right-grouped, and fixed-width schemes create different positional groupings. Singh and Strouse showed that number-tokenization direction changed arithmetic behavior in their experiments; they did not establish one universal best scheme (Singh and Strouse 2024). Code needs similar tests for indentation, identifiers, operators, and long literals.

Freeze the compatibility contract

Special tokens are control-plane inputs to the model. Beginning-of-sequence, end-of-sequence, padding, document-boundary, role, tool, and modality markers need stable spellings and ids. The contract must also say whether the encoder inserts them automatically, how literal marker text is escaped or rejected, which tokens participate in loss, and how padding is masked. Treating a control marker as ordinary user text can change both behavior and security boundaries.

A machine-readable tokenizer manifest should include at least:

tokenizer:
  schema_version: <manifest version>
  artifact_sha256: <digest of serialized tokenizer>
  library: <name, version, and build>
input:
  type: <Unicode text or raw bytes>
  encoding: <for example, UTF-8>
  invalid_input_policy: <reject, replace, or preserve>
normalization:
  unicode_version: <pinned version>
  form: <identity, NFC, NFKC, or named custom transform>
  case_and_whitespace_rules: <ordered configuration>
boundaries:
  pretokenizer: <regex or model and exact version>
  protected_spans: <rules that merges may not cross>
model:
  type: <BPE or Unigram>
  vocabulary_sha256: <piece-to-id mapping>
  ranks_or_scores_sha256: <BPE ranks or Unigram probabilities>
  byte_mapping_or_fallback: <complete configuration>
special_tokens:
  ids: <BOS, EOS, PAD, document, role, tool, and modality ids>
  literal_text_policy: <ordinary, escaped, allowed, or rejected>
postprocessor_and_decoder:
  automatic_insertions: <ordered rules>
  cleanup_and_error_policy: <exact behavior>
training:
  corpus_manifest_sha256: <source mixture and sample>
  trainer_flags_and_seed: <complete deterministic configuration>
tests:
  golden_vectors_sha256: <raw, normalized, ids, offsets, decoded output>
compatibility:
  model_config_sha256: <checkpoint-side tokenizer contract>
  stable_id_prefix: <ids whose meanings may never change>

Golden vectors should cover combining marks, compatibility characters, repeated whitespace, right-to-left text, emoji joiners, no-space scripts, code indentation, numbers, URLs, literal control-token strings, and malformed input according to policy. Pin the tokenizer digest in corpus shards, model configs, training checkpoints, serving images, and evaluation reports.

Changing a tokenizer is a migration

Replacing the text-to-id function is not a drop-in preprocessing update, but it is not impossible. An append-only extension can preserve every old id while adding rows to token-indexed parameters; the new rows still need initialization and continued training. Wang et al. demonstrated vocabulary expansion for a pretrained multilingual model (Wang et al. 2019).

Remapping existing ids requires the corresponding embedding and output rows to be remapped exactly. A replacement tokenizer changes segmentation throughout the data distribution and normally needs stronger adaptation or retraining; zero-shot tokenizer-transfer work shows that model surgery and continued training can reduce that cost in some settings (Minixhofer et al. 2024). These are migrations with evidence requirements, not ordinary configuration edits.

Retain source text or an approved normalized representation whenever future retokenization may be required. Token-id shards alone cannot recover distinctions erased by normalization, unknown tokens, or decoder cleanup.

Tokenizer-free models move the boundary

The phrase tokenizer-free model usually means that no separately trained subword vocabulary maps text to variable-length pieces. It does not mean that the model performs no representation or compression. Different systems move that work to different places:

Raw byte and character streams are longer than typical subword streams. Hierarchical models try to keep expensive global computation at the patch or chunk level while using smaller local modules on bytes. Their realized quality, FLOPs, memory, and latency depend on architecture and workload. BLT reported competitive FLOP-controlled scaling up to its tested 8B-parameter setting; H-Net reported gains over its compute- and data-matched baselines. Neither result proves universal superiority over fixed tokenization.

Validate before model training

Before producing final token-id shards:

1. Replay the artifact. Train twice from the pinned sample and confirm vocabulary, ranks or scores, ids, and serialized digests are identical.
2. Run golden vectors. Verify normalization, ids, offsets, special-token insertion, decoding, and error behavior for every required input class.
3. Audit coverage. Measure unknown and byte-fallback rates by language, domain, script, and score band.
4. Audit length. Report common-unit compression and parallel token-premium distributions, including truncation at deployed context limits.
5. Benchmark the system. Measure training-time tokenization, online encode and decode throughput, output projection cost, and end-to-end latency.
6. Ablate model quality. Under matched data and compute, compare tokenizer candidates on held-out loss and target tasks, including multilingual, code, and numerical slices.
7. Test control tokens. Confirm literal marker text, padding, document boundaries, roles, tools, and modality tokens follow the declared policy.
8. Verify hand-offs. Check that corpus manifests, checkpoints, evaluation, and serving all name the same tokenizer digest.

Once these checks pass, the tokenizer becomes the stable interface between the training distribution and the architecture. Later changes remain possible, but they are explicit checkpoint migrations rather than silent preprocessing updates.

Further reading