BPE, WordPiece, and SentencePiece

Before a language model can process the log line prompt cache failed unexpectedly, a tokenizer slices that text into discrete pieces and assigns each piece an integer ID. An ID is a model-local vocabulary index: it selects a row of a learned embedding table $W_E \in \mathbb{R}^{V \times d}$. It isn't a physical memory address or a meaning shared by all models.

Suppose ID 421 represented cache during training, but a replacement tokenizer assigns it to failed. The replacement now selects the vector learned for the wrong piece. Other changes may affect only certain strings, or preserve every encoding; a different file doesn't automatically scramble every ID. The compatibility requirement is that text segmentation, ID meanings, special tokens, and decoding agree with the checkpoint.

We'll compare three segmentation algorithms: Byte-Pair Encoding (BPE), WordPiece, and Unigram. SentencePiece is a toolkit that implements both BPE and Unigram, along with normalization and decoding. Our classroom examples expose their mechanics; their invented IDs and small vocabularies aren't outputs from a commercial model's tokenizer.

The granularity trade-off: characters, subwords, and words

Before choosing a merge algorithm, consider what granularity of text to feed a neural network. You could feed raw characters, whole words, or subword chunks. Each choice changes sequence length, vocabulary requirements, and coverage.

Why not whole words? The OOV trade-off

At first glance, splitting text on spaces into whole words (prompt, cache, failed, unexpectedly) feels intuitive. Natural language, however, has an open, constantly expanding vocabulary:

1. Out-of-Vocabulary (OOV) failures: Any rare word, technical jargon, typo, new compound word, or code identifier (like tokenCount or deserialize_payload) that didn't appear in a fixed word dictionary can't be represented directly. Without a fallback, the tokenizer replaces it with an unknown token (<UNK>) and loses that word's identity.
2. Vocabulary memory: A broad word vocabulary can grow to millions of entries. For an illustrative vocabulary with $V = 1{,}000{,}000$, hidden dimension $d = 4096$, input embeddings $W_E \in \mathbb{R}^{V \times d}$, and an untied output matrix $W_{\text{head}} \in \mathbb{R}^{V \times d}$ in 16-bit precision, the two tables would consume:

That is over 16 GB of weight memory before loading a transformer layer, a substantial fixed cost even though the practical limit depends on the hardware and deployment.

Why not raw bytes or characters? The quadratic attention cost

Going to the opposite extreme can solve the OOV problem. A byte-level tokenizer needs only 256 base byte values to represent any UTF-8 string, while a character-level tokenizer needs a defined character inventory or fallback. Either approach keeps the base vocabulary small.

The catch is sequence length ($L$). Dense self-attention over a full sequence, as in training or prompt prefill, has a quadratic sequence-length term:

With a key-value (KV) cache, attending from one newly generated position to $L$ cached positions instead takes $O(L \cdot d)$ attention work. KV storage grows linearly with cached length, with constants set by the number and size of KV heads and the layer count. In the running example below, character tokenization produces 32 positions while the illustrative subword segmentation produces 7. Their conceptual dense score matrices contain $32^2 = 1{,}024$ and $7^2 = 49$ cells per head. This 20.9-fold difference isn't an end-to-end speedup; causal masking and implementations that avoid materializing the full matrix also affect actual work and memory.

The subword balance

Subword tokenization usually provides a practical balance:

• High-frequency strings such as prompt and cache can remain single, compact tokens.
• Rare, technical, or inflected words can decompose into reusable fragments (un + expect + ed + ly).
• Vocabulary size stays fixed after training. At fixed hidden size, vocabulary-weight memory grows linearly with $V$.

Measuring this sequence-length trade-off on our running log fixture:

prompt cache failed unexpectedly

message = "prompt cache failed unexpectedly"

characters = list(message)
words = message.split()
subwords = ["prompt", " cache", " failed", " un", "expect", "ed", "ly"]

print("characters:", len(characters))
print("words:", len(words))
print("candidate subwords:", len(subwords), [piece.replace(" ", "·") for piece in subwords])
assert "".join(subwords) == message

characters: 32
words: 4
candidate subwords: 7 ['prompt', '·cache', '·failed', '·un', 'expect', 'ed', 'ly']

The hand-written segmentation reconstructs this fixture in seven positions. A word dictionary missing unexpectedly would lose its identity without a fallback. Neither example establishes coverage of arbitrary future text: that requires checking the actual base alphabet and unknown-token policy.

Byte pair encoding: bottom-up frequency merges

Philip Gage originally developed Byte Pair Encoding (BPE) in 1994 as a data compression algorithm that repeatedly replaces the most frequent adjacent pair of bytes with an unused byte symbol.^{[1]Reference 1A New Algorithm for Data Compression.https://dl.acm.org/doi/10.5555/177910.177914} Sennrich, Haddow, and Birch adapted the algorithm to neural machine translation in 2016, establishing the foundation for modern subword modeling.^{[2]Reference 2Neural Machine Translation of Rare Words with Subword Units.https://arxiv.org/abs/1508.07909}

How BPE training works

BPE training is a greedy, bottom-up algorithm:

1. Initialize the alphabet: Start with all unique base characters (or bytes) in the training corpus. Every word is represented as a sequence of individual characters.
2. Count adjacent pairs: Count the occurrences of all adjacent symbol pairs across the corpus, weighted by word frequencies.
3. Merge the winner: Find the pair with the highest frequency and merge it into a single new vocabulary token.
4. Append to merge rules: Record the merge rule in an ordered merge table.
5. Iterate: Repeat until reaching the requested vocabulary size or a stopping condition, such as no remaining eligible pairs.

Tracing this step by step on a small vocabulary:

At initialization, all words are split into characters: c o d e, c o d e r, c o p e. The pair c + o appears in code (3), coder (2), and cope (2), yielding a weighted count of $3 + 2 + 2 = 7$. It easily beats all competitors and merges into co.

Next, recount adjacent pairs. The candidate co + d appears in code (3) and coder (2) for a total count of 5. The candidate d + e also appears in code (3) and coder (2) for a count of 5. They tie! A production trainer must break ties deterministically (such as by lexicographic order or first-encountered order). Our classroom trainer selects co + d, creating cod.

Recount once more. cod + e appears in code (3) and coder (2), reaching a count of 5 and merging into code. Within three merges, code has become a single token.

Here's a three-merge classroom trainer. It omits end-of-word markers, special-token assignment, vocabulary export, and a general stopping condition; Sennrich's original word-based formulation includes an end-of-word symbol.^{[2]Reference 2Neural Machine Translation of Rare Words with Subword Units.https://arxiv.org/abs/1508.07909} The figure displays the first three terms, whose 30 weighted character positions determine these winning pairs; the code also includes token and prompt.

from collections import Counter

frequencies = {
    "code": 3,
    "coder": 2,
    "cope": 2,
    "token": 2,
    "prompt": 1,
}
state = {tuple(word): count for word, count in frequencies.items()}

def count_pairs(words: dict[tuple[str, ...], int]) -> Counter[tuple[str, str]]:
    pairs: Counter[tuple[str, str]] = Counter()
    for pieces, count in words.items():
        for pair in zip(pieces, pieces[1:]):
            pairs[pair] += count
    return pairs

def merge_pair(
    pieces: tuple[str, ...], pair: tuple[str, str]
) -> tuple[str, ...]:
    merged: list[str] = []
    i = 0
    while i < len(pieces):
        if i + 1 < len(pieces) and pieces[i : i + 2] == pair:
            merged.append("".join(pair))
            i += 2
        else:
            merged.append(pieces[i])
            i += 1
    return tuple(merged)

merges: list[tuple[str, str]] = []
for step in range(3):
    pair, count = count_pairs(state).most_common(1)[0]
    state = {merge_pair(pieces, pair): freq for pieces, freq in state.items()}
    merges.append(pair)
    print(step + 1, pair, "->", "".join(pair), "count", count)

print("learned merges:", merges)

1 ('c', 'o') -> co count 7
2 ('co', 'd') -> cod count 5
3 ('cod', 'e') -> code count 5
learned merges: [('c', 'o'), ('co', 'd'), ('cod', 'e')]

Replaying merges at inference time

Ordinary deterministic BPE encoding uses fixed learned merge ranks, without fitting new rules to each prompt. This lab replays its three rules in order; production implementations can use more efficient rank-based operations. Learning a new vocabulary piece during serving wouldn't create a trained embedding for it.

For our classroom encoder, that means applying the three saved rules in order:

def apply_rule(pieces: list[str], pair: tuple[str, str]) -> list[str]:
    result: list[str] = []
    i = 0
    while i < len(pieces):
        if i + 1 < len(pieces) and tuple(pieces[i : i + 2]) == pair:
            result.append("".join(pair))
            i += 2
        else:
            result.append(pieces[i])
            i += 1
    return result

rules = [("c", "o"), ("co", "d"), ("cod", "e")]

def encode(term: str) -> list[str]:
    pieces = list(term)
    for rule in rules:
        pieces = apply_rule(pieces, rule)
    return pieces

for term in ["coder", "codec", "coper"]:
    print(term, "->", encode(term))

whole = encode("code")
separate = encode("co") + encode("de")
print("whole string:", whole)
print("separate chunks:", separate)
assert "".join(whole) == "".join(separate) == "code"
assert whole != separate

coder -> ['code', 'r']
codec -> ['code', 'c']
coper -> ['co', 'p', 'e', 'r']
whole string: ['code']
separate chunks: ['co', 'd', 'e']

Notice the output: coder gets split into ['code', 'r'] because code was learned in round three. coper becomes ['co', 'p', 'e', 'r'] because cope was never merged, but co was merged in round one. The ordering of the merge list guarantees deterministic segmentation.

The chunk example exposes another boundary: encoding co and de separately gives three pieces, while encoding their concatenation gives one. Both decode to code, but they select different embedding rows. Token counts aren't generally additive across arbitrary text chunks, and appending text can change the final pieces of an encoded prefix. For exact counts and prompt-cache comparisons, encode the actual serialized input. A streaming tokenizer needs a way to retain or revise an unfinished boundary; concatenating independent chunk encodings doesn't reproduce whole-string encoding.

Byte-level BPE and UTF-8 fallbacks

Character BPE with a corpus-derived alphabet can encounter unseen characters. Without an additional fallback, an obscure glyph, emoji, or script may map to <UNK>.

GPT-2 uses byte-level BPE, whose base alphabet covers all 256 byte values.^{[3]Reference 3Language Models are Unsupervised Multitask Learners.https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf} Each Unicode scalar value encodes as one to four UTF-8 bytes, so valid Unicode text is representable without an unknown-character token. Encoding may still reject reserved special-token text or invalid inputs under a particular API policy; alphabet coverage isn't a promise that every request is accepted.

Llama 2 uses SentencePiece BPE and decomposes unknown UTF-8 characters into bytes.^{[4]Reference 4Llama 2: Open Foundation and Fine-Tuned Chat Models.https://arxiv.org/abs/2307.09288} Llama 3 instead uses a tiktoken-based tokenizer, so the two generations don't share the same tokenizer implementation or pre-tokenization rules.^{[5]Reference 5The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783[6]Reference 6Llama 3 Tokenizer Implementationhttps://github.com/meta-llama/llama3/blob/main/llama/tokenizer.py}

Testing this byte round-trip property on a Japanese string with an emoji:

message = "関数✨"
byte_ids = list(message.encode("utf-8"))
reconstructed = bytes(byte_ids).decode("utf-8")

print("byte count:", len(byte_ids))
print("first byte ids:", byte_ids[:8])
print("round trip:", reconstructed)
assert reconstructed == message
assert all(0 <= value <= 255 for value in byte_ids)

# A byte token can contain only part of a Unicode character.
decoded_separately = "".join(
    bytes([value]).decode("utf-8", errors="replace") for value in byte_ids
)
print("per-byte decode exact:", decoded_separately == message)
assert decoded_separately != message

byte count: 9
first byte ids: [233, 150, 162, 230, 149, 176, 226, 156]
round trip: 関数✨
per-byte decode exact: False

Joining the bytes before UTF-8 decoding preserves this string. Decoding each byte separately with replacement errors loses it: token boundaries needn't be Unicode character boundaries.^{[7]Reference 7Fishing for Magikarp: Automatically Detecting Under-trained Tokens in Large Language Modelshttps://arxiv.org/abs/2405.05417} Byte fallback guarantees representation rather than compression. A rarely learned script can use several byte tokens per character, increasing sequence length.

Why regex pre-tokenization is critical

Without boundaries, BPE can learn pieces spanning letters, punctuation, or newlines when the training counts favor them. It doesn't necessarily merge every failed., failed!, or failed\n string. GPT-2's authors report vocabulary waste from such variants and constrain merges by character categories, with an exception for spaces.^{[3]Reference 3Language Models are Unsupervised Multitask Learners.https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf}

To control which text spans can participate in merges, many production BPE tokenizers apply a regular expression pre-tokenizer first. GPT-2 and tiktoken-style encodings use patterns that separate categories such as:

• Contractions ('s, 't, 're, 've, 'm, 'll, 'd)
• Letter sequences
• Numeric digits
• Punctuation marks
• Whitespace runs

Merges stay within the spans produced by that encoding's regex. Don't generalize the listed categories into a universal punctuation rule: Llama 3's letter branch, for example, allows a preceding character outside its letter/number/newline categories. The exact pattern determines which boundaries exist.^{[6]Reference 6Llama 3 Tokenizer Implementationhttps://github.com/meta-llama/llama3/blob/main/llama/tokenizer.py}

WordPiece: likelihood-driven subword selection

WordPiece was developed by Schuster and Nakajima (2012) for Japanese and Korean speech recognition and later became famous as the tokenizer behind BERT.^{[8]Reference 8Japanese and Korean Voice Search.https://research.google/pubs/japanese-and-korean-voice-search/[9]Reference 9BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.https://arxiv.org/abs/1810.04805}

Likelihood intuition and a teaching proxy

BPE selects by eligible adjacent-pair count. WordPiece's published motivation instead considers language-model likelihood.^{[10]Reference 10Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates.https://arxiv.org/abs/1804.10959} This is a statistical objective, not a test that two fragments form a meaningful morpheme.

Be careful about implementation claims: Google didn't publish BERT's WordPiece trainer. Hugging Face labels its detailed training reconstruction a best guess from the literature. Its classroom reconstruction ranks eligible pairs using this association-score proxy:^{[11]Reference 11WordPiece tokenization: training reconstruction and greedy encodinghttps://huggingface.co/learn/llm-course/en/chapter6/6}

For piece-frequency counts and adjacent-pair counts in the current segmentation:

This ratio favors pairs whose components occur together relative to their individual frequencies. It isn't literally pointwise mutual information, which is a logarithm of normalized joint and marginal probabilities. Nor is it a documented exact likelihood-gain formula for every WordPiece trainer. Compare two hypothetical within-word candidates:

The proxy selects code + ##base despite its lower pair count. A phrase such as the model isn't an eligible within-word merge in BERT's pipeline, so comparing those two whole words would teach the wrong boundary.

Greedy longest-match inference and ## continuations

BERT's full tokenizer cleans text, handles Chinese-character boundaries, splits punctuation and whitespace, and optionally lowercases and strips accents before WordPiece. WordPiece then segments each resulting unit, using ## to mark continuations in BERT's vocabulary.^{[12]Reference 12BERT Tokenization Implementationhttps://github.com/google-research/bert/blob/master/tokenization.py} This prefix is a vocabulary convention; it isn't part of the original word.

At inference time, WordPiece matches greedily from left to right using longest-match-first:

The next two functions isolate that search. They don't implement BERT's basic tokenizer or its maximum-word-length limit.

def wordpiece_tokenize(word: str, vocabulary: set[str]) -> list[str]:
    result: list[str] = []
    start = 0
    while start < len(word):
        chosen = None
        for end in range(len(word), start, -1):
            candidate = word[start:end]
            if start > 0:
                candidate = "##" + candidate
            if candidate in vocabulary:
                chosen = candidate
                start = end
                break
        if chosen is None:
            return ["[UNK]"]
        result.append(chosen)
    return result

vocabulary = {"code", "##base", "token", "##ized"}
for term in ["code", "codebase", "tokenized"]:
    print(term, "->", wordpiece_tokenize(term, vocabulary))

code -> ['code']
codebase -> ['code', '##base']
tokenized -> ['token', '##ized']

The greedy dead-end failure

Because BERT-style WordPiece matches greedily without backtracking, it has a notable failure mode: if the longest valid prefix leads to a dead end where no continuation token can finish the word, the tokenizer rejects the entire word and emits [UNK]. It won't backtrack to try a shorter initial match, even if a valid full decomposition exists.^{[12]Reference 12BERT Tokenization Implementationhttps://github.com/google-research/bert/blob/master/tokenization.py}

def encode_word(word: str, vocabulary: set[str]) -> list[str]:
    pieces: list[str] = []
    cursor = 0
    while cursor < len(word):
        match = None
        for end in range(len(word), cursor, -1):
            candidate = word[cursor:end]
            if cursor:
                candidate = "##" + candidate
            if candidate in vocabulary:
                match = candidate
                cursor = end
                break
        if match is None:
            return ["[UNK]"]
        pieces.append(match)
    return pieces

vocabulary = {"code", "##base", "token"}
known = encode_word("codebase", vocabulary)
missing = encode_word("codebot", vocabulary)

print("known term:", known)
print("missing continuation:", missing)
assert known == ["code", "##base"]
assert missing == ["[UNK]"]

# A complete alternative path exists, but greedy matching won't find it.
greedy_trap = {"code", "cod", "##ebot"}
print("greedy dead end:", encode_word("codebot", greedy_trap))
assert "cod" + "ebot" == "codebot"
assert encode_word("codebot", greedy_trap) == ["[UNK]"]

known term: ['code', '##base']
missing continuation: ['[UNK]']
greedy dead end: ['[UNK]']

In greedy_trap, cod + ##ebot could segment codebot completely. But WordPiece greedily consumes code, finds no continuation for bot, and collapses the whole word to [UNK].

SentencePiece and the Unigram language model

Many BPE and WordPiece pipelines apply whitespace splitting or a language-specific segmenter before learning subwords. A naive whitespace boundary is a poor fit for languages that don't delimit every word with spaces, such as Japanese, Chinese, and Thai. SentencePiece instead trains from raw sentences and packages normalization with the model.

Kudo and Richardson's SentencePiece toolkit learns from raw sentences without requiring an external word segmenter.^{[13]Reference 13SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing.https://arxiv.org/abs/1808.06226} Raw input doesn't mean unconstrained pieces: its default trainer still restricts crossing whitespace, script, and number boundaries.^{[14]Reference 14SentencePiece model specification: coverage, segmentation, and normalization optionshttps://github.com/google/sentencepiece/blob/master/src/sentencepiece_model.proto}

Raw stream processing and reversible whitespace detokenization

SentencePiece treats input text as a continuous raw stream of Unicode characters. It introduces two major innovations:

1. Explicit whitespace character: Spaces in the normalized stream become ▁ (U+2581 Lower One Eighth Block). The default dummy-prefix option also adds an initial marker, so prompt cache becomes ▁prompt▁cache even without a raw leading space.
2. Reversible whitespace encoding: After normalization, spaces remain explicit in the token stream, so decoding the normalized text is straightforward:

decoded = "".join(tokens).removeprefix("▁").replace("▁", " ")

Explicit markers preserve spaces in the normalized stream. This string-join expression illustrates ordinary pieces with the default leading-space convention. Use the actual decoder for model-specific special tokens, byte pieces, and whitespace options. Recovery of normalized text requires that no content was collapsed into an unknown ID. A model without byte fallback can lose unseen characters, and normalization can remove distinctions before segmentation.^{[14]Reference 14SentencePiece model specification: coverage, segmentation, and normalization optionshttps://github.com/google/sentencepiece/blob/master/src/sentencepiece_model.proto}

The Unigram LM: top-down loss-minimizing pruning

SentencePiece can train BPE models and also implements the Unigram Language Model described by Kudo (2018a).^{[10]Reference 10Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates.https://arxiv.org/abs/1804.10959}

Unlike BPE and WordPiece (which build vocabulary bottom-up by iteratively merging characters), Unigram operates top-down:

1. Initialize an oversized seed vocabulary: Start with required individual characters plus frequent substrings extracted from the corpus, producing more candidates than the target vocabulary needs.
2. Estimate piece probabilities: Use Expectation-Maximization (EM) to fit the candidate-token probabilities $P(x)$ toward higher corpus log-likelihood. This doesn't guarantee the global optimum:

where $\mathcal{S}(s)$ is the set of all valid segmentations of sentence $s$. 3. Estimate pruning loss: Rank candidate pieces by the estimated likelihood reduction from removal. This pruning approximation avoids solving the intractable joint vocabulary/probability optimization exactly. 4. Remove a fraction of low-loss pieces: The paper illustrates keeping 80%. Retain required single-character pieces, which protect coverage of the selected character alphabet, not every future Unicode character. 5. Iterate: Recompute probabilities and repeat until reaching the target vocabulary size $V$.

Viterbi decoding on candidate lattices

At inference time, an input string can be segmented across dozens of candidate boundaries. Unigram evaluates complete paths by joint probability:

The Viterbi algorithm uses dynamic programming to find the optimal global segmentation without enumerating all combinatorial paths.

Subword regularization: training with segmentation noise

Unigram also supports subword regularization.^{[10]Reference 10Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates.https://arxiv.org/abs/1804.10959} During model training, instead of always taking the deterministic 1-best Viterbi path, SentencePiece can sample segmentations from the posterior distribution:

where $\alpha$ controls the sampling distribution. A model might see ['▁token'] in one epoch and ['▁', 'token'] in the next. This acts as data augmentation over valid segmentations and can improve robustness to segmentation variation.

The sampling distribution $q_\alpha$ is normalized over legal paths for this fixed input. Smaller positive $\alpha$ flattens it; larger values concentrate it toward the best path. The original paper studies neural machine translation training. Sampling is an option for model training, not something every pretrained SentencePiece-based LLM used. For reproducible serving, use the checkpoint's intended encoding mode.

Here's a miniature Viterbi decoder with hand-assigned piece probabilities. Python's Unicode NFKC and our simple space marker illustrate preprocessing; they aren't a full SentencePiece normalizer or trainer. The extra to/ken pieces align its candidate paths with the figure.

from math import inf, isclose, log
import unicodedata

probabilities = {
    "▁token": 0.30,
    "▁": 0.15,
    "token": 0.10,
    "to": 0.02,
    "ken": 0.03,
    "f": 0.02,
    "i": 0.04,
    "l": 0.04,
    "e": 0.04,
    "de": 0.08,
    "a": 0.04,
    "y": 0.04,
    "ed": 0.08,
    "d": 0.02,
}
assert isclose(sum(probabilities.values()), 1.0)
logp = {piece: log(probability) for piece, probability in probabilities.items()}

def viterbi_segment(text: str, scores: dict[str, float]) -> list[str]:
    n = len(text)
    if "" in scores:
        raise ValueError("empty pieces are not supported")
    if not text:
        return []
    if not scores:
        raise ValueError("no legal segmentation")
    best = [(0.0, -1, "")] + [(-inf, -1, "")] * n
    max_len = max(map(len, scores))
    for start in range(n):
        if best[start][0] == -inf:
            continue
        for end in range(start + 1, min(n, start + max_len) + 1):
            piece = text[start:end]
            if piece not in scores:
                continue
            score = best[start][0] + scores[piece]
            if score > best[end][0]:
                best[end] = (score, start, piece)
    if best[n][0] == -inf:
        raise ValueError("no legal segmentation")
    pieces: list[str] = []
    cursor = n
    while cursor > 0:
        _, prev, piece = best[cursor]
        pieces.append(piece)
        cursor = prev
    pieces.reverse()
    return pieces

raw_message = "token file delayed"
normalized = unicodedata.normalize("NFKC", raw_message)
marked = "▁" + normalized.replace(" ", "▁")
pieces = viterbi_segment(marked, logp)
decoded = "".join(pieces).removeprefix("▁").replace("▁", " ")

print("raw:", raw_message)
print("normalized with marker:", marked)
print("pieces:", pieces)
print("decoded:", decoded)
assert raw_message != decoded
assert marked == "▁token▁file▁delayed"
assert pieces == ["▁token", "▁", "f", "i", "l", "e", "▁", "de", "l", "a", "y", "ed"]
assert decoded == "token file delayed"

raw: token file delayed
normalized with marker: ▁token▁file▁delayed
pieces: ['▁token', '▁', 'f', 'i', 'l', 'e', '▁', 'de', 'l', 'a', 'y', 'ed']
decoded: token file delayed

▁token stays whole because its log-probability ($-1.204$) beats ▁ plus token ($-1.897 + -2.303 = -4.200$). Meanwhile, delayed decomposes into de, l, a, y, and ed according to the optimal joint likelihood.

Vocabulary economics: parameter memory vs context efficiency

When designing a tokenizer, how big should $V$ be? Historical checkpoints illustrate different choices: GPT-2 uses 50,257 IDs; Llama 2 uses 32,000.^{[3]Reference 3Language Models are Unsupervised Multitask Learners.https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf[4]Reference 4Llama 2: Open Foundation and Fine-Tuned Chat Models.https://arxiv.org/abs/2307.09288} Llama 3's report describes 128K pieces, and its original implementation adds 256 reserved special-token IDs. Gemma 2's report describes 256K entries.^{[5]Reference 5The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783[6]Reference 6Llama 3 Tokenizer Implementationhttps://github.com/meta-llama/llama3/blob/main/llama/tokenizer.py[15]Reference 15Gemma 2: Improving Open Language Models at a Practical Sizehttps://storage.googleapis.com/deepmind-media/gemma/gemma-2-report.pdf} Inspect the actual vocabulary and weight shapes, including special IDs and padding, for an exact memory budget.

Every additional vocabulary token represents a trade-off between weight memory and sequence length.

Calculating the parameter memory bill

For hidden dimension $d_{\text{model}}$, the input embedding table $W_E \in \mathbb{R}^{V \times d_{\text{model}}}$ stores $V \times d_{\text{model}}$ parameters. If the final output projection matrix ($W_{\text{head}}$) is untied (not sharing weights with $W_E$), it stores another $V \times d_{\text{model}}$ parameters:

Computing the exact memory footprint across vocabulary sizes:

def embedding_memory_mib(
    vocabulary_size: int, hidden_size: int, bytes_per_weight: int = 2
) -> float:
    return vocabulary_size * hidden_size * bytes_per_weight / (1024**2)

hidden_size = 4096
for vocabulary_size in [8_000, 32_000, 128_000]:
    input_mib = embedding_memory_mib(vocabulary_size, hidden_size)
    untied_mib = 2 * input_mib
    print(
        f"{vocabulary_size:>6,} tokens:",
        f"input={input_mib:>7.1f} MiB",
        f"input+untied-output={untied_mib:>7.1f} MiB",
    )

8,000 tokens: input=   62.5 MiB input+untied-output=  125.0 MiB
32,000 tokens: input=  250.0 MiB input+untied-output=  500.0 MiB
128,000 tokens: input= 1000.0 MiB input+untied-output= 2000.0 MiB

The sequence compression payoff

The illustrative untied 128,000-row budget above is 2,000 MiB, or 1.953 GiB. A larger, appropriately trained vocabulary can shorten sequences, but size alone doesn't guarantee better compression on your corpus:

1. Sequence and attention savings: Llama 3's report measures 3.17 versus 3.94 characters per token on a sample of English data.^{[5]Reference 5The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783} Treating those reported rates as representative of fixed text gives $1 - 3.17 / 3.94 \approx 19.5\%$ fewer positions and $1 - (3.17 / 3.94)^2 \approx 35.3\%$ fewer conceptual dense attention score cells. These are derived ratios, not promised per-request savings or an end-to-end speedup.
2. KV cache savings: Holding model architecture and text fixed, 19.5% fewer token positions means 19.5% fewer key and value positions stored for that request.
3. Context capacity: At the reported compression rates, a fixed token window holds about $3.94 / 3.17 \approx 1.243$ times as many characters from the same content distribution. Word counts vary by language and corpus, so character compression shouldn't be converted into a universal words-per-window claim.

Modern tokenizer failure modes in production

Tokenization choices affect cost and representations before the model's first layer. The following four cases are useful audits; fragmentation alone isn't proof of incorrect model behavior.

1. Multilingual token inflation ("The fertility tax")

Fertility measures how many tokens a tokenizer requires per word or another chosen text unit. The value depends on both the tokenizer and the evaluation corpus, so comparisons should use parallel content and a consistent unit.

Tokenizers can use far more tokens for some languages than for English. Across parallel FLORES-200 translations, Petrov et al. measured a 15.05-fold token premium for Shan with the cl100k_base tokenizer used by ChatGPT and GPT-4 at the time.^{[16]Reference 16Language Model Tokenizers Introduce Unfairness Between Languages.https://arxiv.org/abs/2305.15425} This compares translations with the same underlying content, not identical text.

This creates three measurable risks:

• Billing: Token-metered input charges scale with token count, although the monetary ratio depends on the provider's pricing policy.
• Context capacity: A higher token ratio leaves proportionally less room for comparable content in a fixed token window.
• Latency: Longer token sequences increase prefill work, and fragmented outputs can require more autoregressive decoding steps. Petrov et al. observed up to roughly twice the processing time for some languages, not a universal 15-fold latency penalty.^{[16]Reference 16Language Model Tokenizers Introduce Unfairness Between Languages.https://arxiv.org/abs/2305.15425}

Expanding vocabulary size to 128k (as Meta did in Llama 3 by dedicating 28,000 specific tokens to non-English languages) directly targets this fertility gap.^{[5]Reference 5The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783}

2. Arithmetic and numeric pre-tokenization

Tokenization is one factor that can make multi-digit arithmetic harder. It determines whether digit positions are exposed consistently or hidden inside variable-length pieces, but training data, model capacity, and learned algorithms matter too.

In byte-level BPE tokenizers such as GPT-2's, numeric substrings can be merged into pieces according to learned merge ranks. Similar-looking numbers can therefore receive different boundaries.

Llama 2 chose a different policy and split numbers into individual digits.^{[4]Reference 4Llama 2: Open Foundation and Fine-Tuned Chat Models.https://arxiv.org/abs/2307.09288} Llama 3 doesn't preserve every digit separately. Its official tokenizer uses the regex span \p{N}{1,3}, which groups one to three numeric characters before BPE.^{[6]Reference 6Llama 3 Tokenizer Implementationhttps://github.com/meta-llama/llama3/blob/main/llama/tokenizer.py}

Single-digit spans expose each column explicitly, while bounded multi-digit spans limit how much numeric text enters one pre-tokenization chunk. Neither policy guarantees arithmetic correctness. Audit the exact regex and resulting token boundaries instead of assuming all modern tokenizers use the same rule.

3. Code indentation and whitespace handling

In languages such as Python, indentation changes program structure. Four levels of four-space indentation use 16 leading spaces on the deepest line. An encoding with only single-space pieces would spend 16 tokens on that run; other lines can have different indentation depths.

Code-aware tokenizers can learn pieces for multi-space runs. In the illustration's concrete example, representing 16 leading spaces as four 4-space pieces reduces indentation from 16 tokens to 4, a 75% reduction for that run. Actual savings depend on the tokenizer vocabulary and the code sample.

Exact casing can change which learned pieces match. Our mini-BPE below produces these boundaries:

• tokenCount $\to$ ['token', 'C', 'o', 'un', 't'] (5 tokens!)
• encodePrompt $\to$ ['encode', 'P', 'rompt'] (3 tokens here)

Its corpus includes some code, but the limited merge budget doesn't learn whole Count or Prompt pieces. These counts aren't predictions for Llama, GPT, or another checkpoint's tokenizer.

4. Glitch tokens and under-trained vocabulary entries

Researchers have documented glitch tokens, vocabulary entries such as SolidGoldMagikarp that can trigger anomalous model behavior.^{[7]Reference 7Fishing for Magikarp: Automatically Detecting Under-trained Tokens in Large Language Modelshttps://arxiv.org/abs/2405.05417}

The robust conclusion is narrower than a single causal story. Tokenizer construction and neural model training use different objectives and may use different corpora. A token can enter the vocabulary yet be nearly or entirely absent during model training, leaving it under-trained. Weight-based signatures depend on the architecture: tied and untied input and output embeddings don't receive identical updates. Corpus counts, vector norms, and prompt behavior can help identify candidates, but they don't prove that a particular token received exactly zero gradients or that attention logits saturated.^{[7]Reference 7Fishing for Magikarp: Automatically Detecting Under-trained Tokens in Large Language Modelshttps://arxiv.org/abs/2405.05417}

Testing these multilingual and camelCase behaviors on a trained mini-BPE:

from collections import Counter
import re

PRETOK = re.compile(r"[^\W\d_]+|\d+|\s+|[^\s]")

def utf8_pieces(text: str) -> tuple[str, ...]:
    return tuple(bytes([b]).decode("latin-1") for b in text.encode("utf-8"))

def pretok(text: str) -> list[str]:
    return PRETOK.findall(text)

def count_pairs(words: dict[tuple[str, ...], int]) -> Counter[tuple[str, str]]:
    pairs: Counter[tuple[str, str]] = Counter()
    for pieces, count in words.items():
        for pair in zip(pieces, pieces[1:]):
            pairs[pair] += count
    return pairs

def merge_pair(pieces: tuple[str, ...], pair: tuple[str, str]) -> tuple[str, ...]:
    merged: list[str] = []
    i = 0
    while i < len(pieces):
        if i + 1 < len(pieces) and pieces[i : i + 2] == pair:
            merged.append(pieces[i] + pieces[i + 1])
            i += 2
        else:
            merged.append(pieces[i])
            i += 1
    return tuple(merged)

def encode(text: str, merges: list[tuple[str, str]]) -> list[str]:
    output: list[str] = []
    for span in pretok(text):
        pieces = list(utf8_pieces(span))
        for pair in merges:
            pieces = list(merge_pair(tuple(pieces), pair))
        output.extend(pieces)
    return output

def visible(pieces: list[str]) -> list[str]:
    shown: list[str] = []
    for piece in pieces:
        raw = piece.encode("latin-1")
        try:
            shown.append(raw.decode("ascii").replace(" ", "·"))
        except UnicodeDecodeError:
            shown.append("<byte>")
    return shown

corpus = {
    "const tokenCount = encodePrompt(prompt).length;": 3,
    "How do I tokenize this prompt?": 5,
    "prompt cache failed unexpectedly": 4,
    "token budget pending": 3,
    "encode the prompt cache": 3,
    "failed unexpectedly": 2,
}
state: dict[tuple[str, ...], int] = Counter()
for text, count in corpus.items():
    for span in pretok(text):
        state[utf8_pieces(span)] += count

merges: list[tuple[str, str]] = []
for _ in range(25):
    pair, _count = count_pairs(state).most_common(1)[0]
    state = {merge_pair(pieces, pair): freq for pieces, freq in state.items()}
    merges.append(pair)

fixtures = {
    "english": "How do I tokenize this prompt?",
    "portuguese": "Como tokenizo este prompt?",
    "japanese": "このプロンプトをトークン化するには？",
    "typescript": "const tokenCount = encodePrompt(prompt).length;",
}

english_tokens = len(encode(fixtures["english"], merges))
for name, text in fixtures.items():
    pieces = encode(text, merges)
    print(f"{name:>10}: {len(pieces):>2} tokens {len(pieces) / english_tokens:>4.2f}x english")
    assert "".join(pieces).encode("latin-1").decode("utf-8") == text

typescript = encode(fixtures["typescript"], merges)
print("typescript pieces:", visible(typescript))
assert [len(encode(text, merges)) for text in fixtures.values()] == [20, 17, 54, 25]
assert visible(typescript) == [
    "co", "n", "s", "t", "·", "token", "C", "o", "un", "t",
    "·", "=", "·", "encode", "P", "rompt", "(", "prompt", ")",
    ".", "l", "en", "g", "th", ";",
]

english: 20 tokens 1.00x english
portuguese: 17 tokens 0.85x english
  japanese: 54 tokens 2.70x english
typescript: 25 tokens 1.25x english
typescript pieces: ['co', 'n', 's', 't', '·', 'token', 'C', 'o', 'un', 't', '·', '=', '·', 'encode', 'P', 'rompt', '(', 'prompt', ')', '.', 'l', 'en', 'g', 'th', ';']

The regex is a classroom approximation using Unicode word characters, decimal digits, whitespace, and remaining characters. Unlike an ASCII-only letter branch, it keeps this Japanese sentence's letter sequences together. It isn't GPT-2's or Llama 3's exact pattern. The fixture audit shows:

• Portuguese reuses token in tokenizo, keeping token count low (0.85x).
• Japanese has no learned merges in this ASCII-centric corpus and uses 54 raw byte tokens (2.70x the English fixture).
• tokenCount uses ['token', 'C', 'o', 'un', 't']; this limited vocabulary has no piece spanning the uppercase suffix.

These are token-count ratios for four authored strings, not a multilingual benchmark or per-word fertility measurement. The English string is also in the tokenizer's training corpus. Evaluate the real checkpoint on separate, representative parallel content before making deployment or billing claims; message formatting and special-token overhead can add tokens beyond raw text.

Unicode normalization policies: NFC vs NFKC

Two text strings can look identical on screen while holding completely different Unicode code points.

For example, café can be written as:

• Composed form: c + a + f + é (\u00E9, single code point).
• Decomposed form: c + a + f + e + ◌́ (\u0065\u0301, letter e plus combining acute accent).

If the configured tokenizer doesn't unify those forms, visually similar requests can produce different IDs and miss an exact-prefix cache match. If its normalizer already unifies them, they can encode identically. Cache results also depend on the full request prefix and the serving system's policy.

Unicode defines four normalization forms: NFD, NFC, NFKD, and NFKC. Here we compare the two composition forms:^{[17]Reference 17Unicode Standard Annex 15: Unicode Normalization Formshttps://unicode.org/reports/tr15/}

• NFC (Normalization Form C): Canonical decomposition followed by canonical composition where allowed. Some combining sequences have no precomposed equivalent. NFC preserves compatibility distinctions such as fi versus fi.
• NFKC (Normalization Form Compatibility Composition): Compatibility decomposition followed by canonical composition where allowed. The ligature fi (U+FB01) becomes f + i, full-width Latin letters and digits become ASCII, and superscript digits become standard digits.

SentencePiece's current default is nmt_nfkc, a variant with additional whitespace handling; its implementation doesn't perform every part of standard Unicode NFKC. The model can specify another rule, including identity. Default whitespace options remove leading, trailing, and repeated spaces.^{[18]Reference 18Text Normalization in SentencePiecehttps://github.com/google/sentencepiece/blob/master/doc/normalization.md[14]Reference 14SentencePiece model specification: coverage, segmentation, and normalization optionshttps://github.com/google/sentencepiece/blob/master/src/sentencepiece_model.proto} That matters for code and exact identifiers: don't substitute Python NFKC or assume every SentencePiece checkpoint uses the default.

Testing standard NFC and NFKC in Python makes their differences concrete:

import unicodedata

composed = "café"
decomposed = "cafe\u0301"
ligature = "file"

print("raw cafe equal:", composed == decomposed)
print("NFC cafe equal:", unicodedata.normalize("NFC", composed) == unicodedata.normalize("NFC", decomposed))
print("NFC ligature:", unicodedata.normalize("NFC", ligature))
print("NFKC ligature:", unicodedata.normalize("NFKC", ligature))

assert composed != decomposed
assert unicodedata.normalize("NFC", composed) == unicodedata.normalize("NFC", decomposed)
assert unicodedata.normalize("NFC", ligature) != "file"
assert unicodedata.normalize("NFKC", ligature) == "file"

raw cafe equal: False
NFC cafe equal: True
NFC ligature: file
NFKC ligature: file

Use the normalizer bundled with the checkpoint consistently. Adding external normalization can change training-time distinctions, and applying it before every request isn't automatically beneficial. Neither NFC nor NFKC is a general visual-lookalike detector or a complete text-safety policy.

The immutability of the tokenizer contract

Comparing the core subword families highlights how each framework approaches training, inference, and fallback:

Why tokenizer swaps destroy model performance

A checkpoint stores learned vectors and projections; the tokenizer bundle supplies the mapping between pieces and IDs:

• Input embedding lookup selects row $i$ from $W_E \in \mathbb{R}^{V \times d_{\text{model}}}$.
• The final LM head computes dot products against row $i$ of $W_{\text{head}} \in \mathbb{R}^{V \times d_{\text{model}}}$.

Equal vocabulary size doesn't preserve token meanings. An incompatible replacement can severely degrade a model, but not every file change produces gibberish, and full retraining isn't the only possible adaptation. A pure bijective ID renaming can preserve behavior if all vocabulary-indexed weights, special IDs, and associated state are remapped consistently. New segmentation or new pieces generally require model adaptation and evaluation.

Try the simplest case: keep the pieces, reorder their IDs, and observe what happens if the table stays put.

ids_a = {"prompt": 0, "cache": 1, "failed": 2}
ids_b = {"failed": 0, "prompt": 1, "cache": 2}
rows_a = [(1.0, 0.0), (0.0, 1.0), (-1.0, -1.0)]
message = ["prompt", "cache"]

expected = [rows_a[ids_a[piece]] for piece in message]
wrong = [rows_a[ids_b[piece]] for piece in message]
rows_b = [None] * len(rows_a)
for piece, new_id in ids_b.items():
    rows_b[new_id] = rows_a[ids_a[piece]]
remapped = [rows_b[ids_b[piece]] for piece in message]

# Assume a tied input/output table and a supplied final hidden vector.
hidden = (0.8, 0.2)
def piece_logits(ids, rows):
    return {
        piece: sum(h * w for h, w in zip(hidden, rows[ids[piece]]))
        for piece in ids
    }

print("original vectors:", expected)
print("new IDs, old table:", wrong)
print("new IDs, remapped table:", remapped)
print("piece logits preserved:", piece_logits(ids_a, rows_a) == piece_logits(ids_b, rows_b))
assert wrong != expected
assert remapped == expected
assert piece_logits(ids_a, rows_a) == piece_logits(ids_b, rows_b)

original vectors: [(1.0, 0.0), (0.0, 1.0)]
new IDs, old table: [(0.0, 1.0), (-1.0, -1.0)]
new IDs, remapped table: [(1.0, 0.0), (0.0, 1.0)]
piece logits preserved: True

The equality applies to piece-associated logits under this supplied hidden vector. No transformer is run here. For an untied model, both input and output tables need the same ID remapping; output biases and other indexed state, if present, also matter. This exercise doesn't license replacing an existing checkpoint's tokenizer with one that splits text differently.

Production review checklist

Bundle the chat template and special-token policy with the tokenizer too. Correct piece IDs don't help if one path inserts different role delimiters, beginning/end markers, padding, or truncation. Keep ordinary user text distinct from trusted control-token insertion.

Check the tokenizer contract