LearnCore LLM FoundationsBPE, WordPiece, and SentencePiece

📝MediumNLP Fundamentals

BPE, WordPiece, and SentencePiece

Build a small subword tokenizer, compare BPE, WordPiece, and SentencePiece, then audit fertility, camelCase splits, and Unicode policy.

23 min read

Learning path

Step 54 of 196 in the full curriculum

The Bitter Lesson & Compute Static to Contextual Embeddings

Personalize this lesson

Adapt explanations and teaching visuals to your background and preferred voice.

Two services receive the same visible string, prompt cache failed unexpectedly. Service A normalizes and tokenizes with artifact A; service B uses artifact B. Their logs still print identical text, but their integer sequences can differ, so the model looks up different embedding rows before it performs any attention.

The mismatch happens before model computation. Tokenization is part of the model input contract, not a cosmetic preprocessing step. A common subword method, Byte Pair Encoding (BPE), learns merges between frequent adjacent pieces.

The previous lesson argued that methods which improve with data and compute tend to outlast hand-written rules. A frozen word list is a rule: it knows only strings that earned entries. A subword vocabulary learns reusable fragments from corpus counts, then serves them through a fixed artifact.

Byte Pair Encoding (BPE), WordPiece, and SentencePiece make different choices about fragments, boundaries, and fallbacks. We'll follow one status line from characters to IDs, trigger its failure modes, and measure the tradeoffs.

Tokenization trace for prompt cache failed unexpectedly: prompt, leading-space cache, leading-space failed stay whole, unexpectedly becomes leading-space un plus expect, ed, and ly, seven local IDs are assigned, and each ID selects one colored embedding row. — The tokenizer fixes both sequence length and lookup addresses. Three common words stay whole, including a leading space on the later ones, while unexpectedly becomes four reusable pieces. The seven tokenizer-local IDs are row addresses, not universal names.

Diagram showing Raw text, Pieces, Token IDs, and Embedding rows. — Raw text, Pieces, Token IDs, and Embedding rows.

An embedding is a vector stored at a token ID. Each integer is an address, not a universal meaning. ID 421 can point to different vectors under two tokenizers, while a reserved ID can mark a sequence boundary instead of a text fragment.

Pair each model checkpoint with its exact tokenizer artifact, including its normalizer, vocabulary, merge rules, special-token map, and fallback behavior. The next lesson teaches those vectors.

Choose pieces between characters and words

A word-level tokenizer could keep unexpectedly as one item, but it needs a policy for every rare identifier, version string, and prompt marker.

A character-level tokenizer keeps a small base vocabulary and can represent rare text, but it turns a short status line into a long sequence. Subword tokenization keeps frequent fragments whole while retaining smaller fallback pieces for the rest.

The running fixture is that status line, including its three spaces:

prompt.txt

prompt cache failed unexpectedly

Before looking at a trainer, predict what each unit gives up. Words keep this line short until a missing word needs an unknown-token policy. Characters preserve coverage but spend positions. Subwords try to keep both costs bounded.

Token unit	Example pieces	What it buys you	What it costs
Character	`p r o m p t <space> ...`	Every character, including whitespace, is representable	Long input sequence
Word	`prompt`, `cache`, `failed`, `unexpectedly`	Short common strings	Rare words and IDs need fallbacks
Subword	`prompt`, `cache`, `failed`, `un`, `expect`, `ed`, `ly`	Compact common patterns with fallback parts	Requires a learned vocabulary

Token granularity for prompt cache failed unexpectedly: 32 character positions including three spaces, seven subwords that keep leading spaces on later words, and four whole words that minimize positions but carry unknown-token risk. — Larger pieces shorten this fixture from 32 characters, including whitespace, to seven space-preserving subwords to four words. Vocabulary cost moves the other way, so subwords sit in the practical middle: short sequences with reusable fallback pieces.

The seven-piece split is a teaching fixture, not a learned result. Concatenating the pieces rebuilds the line only because leading spaces stay attached to later tokens. The trainer will later show which fragments this corpus earns, so you can compare a candidate split with a deployed artifact.

01-count-token-units.py

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

Output

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

Four words look cheapest until unexpectedly is missing from the vocabulary. Subwords spend extra vocabulary rows to preserve a fallback path. That sequence-versus-coverage decision drives the merge algorithms next.

Train byte pair encoding from counts

Philip Gage introduced BPE as a compression algorithm that repeatedly replaces the most frequent adjacent pair of bytes with a new symbol.^{[1]Reference 1A New Algorithm for Data Compression.https://dl.acm.org/doi/10.5555/177910.177914} Sennrich, Haddow, and Birch adapted the same loop to open-vocabulary neural machine translation: start from characters inside pre-separated words, merge frequent adjacent pairs, and reuse the resulting pieces for rare words.^{[2]Reference 2Neural Machine Translation of Rare Words with Subword Units.https://arxiv.org/abs/1508.07909}

The learned merge list is the contract. Training chooses it once; serving replays it.

For teaching, start with characters inside pre-separated code terms. This isolates the merge loop. A production tokenizer also decides how to split on whitespace and punctuation before merging, because boundaries control which pairs can become vocabulary entries.

Three BPE recount panels use weighted code, coder, and cope terms. Round one selects c plus o at count 7, round two selects co plus d at count 5 over a tied d plus e pair, and round three selects cod plus e at count 5. — Each column recounts adjacent pairs after the previous merge. Round two contains a 5-5 tie: this classroom implementation picks the pair encountered first, while a production trainer must define a stable tie-break so the learned vocabulary is reproducible.

Use weighted adjacent-pair counts to predict the first winner. Suppose a code-text corpus contains these term counts:

Term	Count
`code`	3
`coder`	2
`cope`	2
`token`	2
`prompt`	1

At the start, c + o appears seven times: three in code, two in coder, and two in cope. It wins because term frequencies weight each occurrence.

Merge it into co, then recount. co + d and d + e tie at five. The toy trainer encounters co + d first, so it becomes cod; a production trainer needs an explicit deterministic tie-break.

Recount once more. cod + e now wins at five, producing code. Every later round sees the pieces created by earlier rounds, not the original characters.

The miniature trainer below mirrors those state transitions. It stores each term as a tuple of current pieces, counts adjacent pairs, merges the winner everywhere, and prints the first three rules.

02-train-mini-bpe.py

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)

Output

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

Those merges aren't a linguistic analysis. BPE doesn't know that code relates to programming. It knows only that a boundary occurs often enough to compress. If the corpus changes, the winning pairs and every downstream ID can change with it.

Replay merges on a new term

Now vary the input while keeping the artifact fixed. Training chooses an ordered merge list once. Encoding a new input doesn't recount a new corpus; it replays those learned rules. That separation keeps the model's IDs stable.

Take the three rules above and apply them to new terms. coder benefits from the common stem. coper gets only the co merge because the corpus never earned cope as one piece in the first three steps.

03-replay-bpe-merges.py

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")]

for term in ["coder", "codec", "coper"]:
    pieces = list(term)
    for rule in rules:
        pieces = apply_rule(pieces, rule)
    print(term, "->", pieces)

Output

coder -> ['code', 'r']
codec -> ['code', 'c']
coper -> ['co', 'p', 'e', 'r']

Use bytes as a complete base alphabet

Character-starting BPE still has a coverage hole: a character absent from its base vocabulary needs an unknown-token policy. GPT-2 used a byte-level BPE variant instead. Its base alphabet represents the 256 UTF-8 byte values, then learned merges build larger pieces over that base.^{[3]Reference 3Language Models are Unsupervised Multitask Learners.https://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf}

Because any Unicode string has a UTF-8 byte representation, every input remains representable without an unknown character token.

Some tokenizers use an explicit byte fallback only when ordinary pieces can't encode an input. Llama 2's SentencePiece BPE does that with a 32k vocabulary: unknown UTF-8 characters are decomposed into bytes.^{[4]Reference 4Llama 2: Open Foundation and Fine-Tuned Chat Models.https://arxiv.org/abs/2307.09288}

The coverage goal matches GPT-2's byte alphabet, but the fallback path runs only for inputs ordinary pieces can't spell.

Before choosing between these policies, test what each one promises. The next snippet doesn't train merges; it isolates the common foundation. A status note containing Japanese characters and an emoji is reversible through raw UTF-8 byte values.

04-utf8-byte-round-trip.py

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)

Output

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

The round trip proves coverage, not compactness. If training data rarely covers a script or emoji sequence, several bytes may remain separate pieces, so token count still needs measurement.

WordPiece chooses vocabulary differently

WordPiece appeared in Google's Japanese and Korean voice-search work and later became familiar through BERT's 30,000-token tokenizer.^{[5]Reference 5Japanese and Korean Voice Search.https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37842.pdf}^{[6]Reference 6BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.https://arxiv.org/abs/1810.04805} It shares BPE's reusable pieces, but changes the selection question.

BPE asks which adjacent pair occurs most often; WordPiece asks which vocabulary addition best improves the language-model objective.

Exact training recipes aren't fully specified by the short original paper, and library trainers can differ. To see why raw frequency isn't enough, compare a very common pair with a rarer pair that almost always appears together. A useful classroom proxy is an association score:

\operatorname{score}(a,b) = \frac{\operatorname{count}(ab)} {\operatorname{count}(a)\operatorname{count}(b)}

The numerator rewards neighboring pieces that appear together. The denominator penalizes pieces that occur frequently in many other contexts, so a less frequent but tightly associated pair can look attractive. Treat this as intuition for WordPiece's likelihood motivation, not as the original implementation specification.

Candidate pair	Pair count	Individual counts	Proxy score	Lesson
`code` + `base`	42	50 and 44	`0.0191`	Often occurs together
`the` + `model`	90	900 and 300	`0.0003`	Frequent pieces aren't necessarily exclusive

The table makes the boundary visible: the + model has the larger pair count, yet code + base wins this proxy because its pieces co-occur more exclusively. This is the decision WordPiece adds beyond frequency.

At encoding time, BERT-style WordPiece uses continuation pieces such as ##ing and a greedy longest-match lookup. A piece beginning with ## continues the current word rather than beginning a new word. The encoder makes this choice at each cursor position, using the vocabulary it was given.

The lookup below shows the local decision. It always tries the longest valid piece from the current cursor position.

05-wordpiece-longest-match.py

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))

Output

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

Expose the unknown-token failure

Standard WordPiece can't necessarily spell a word from arbitrary bytes. If no valid segmentation reaches the end of a word, BERT-style tokenization emits [UNK] for that word.

The fallback preserves a valid model input, but loses distinctions between two different unseen strings.

The same algorithm with a missing ##bot continuation shows where the contract fails. A matched code prefix can't be kept when the rest of the word has no legal path. Don't silently map the new string to a known ID. Use the model's tokenizer contract, or change the vocabulary and corresponding model parameters as a training decision.

06-wordpiece-unknown-token.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]"]

Output

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

SentencePiece treats boundaries as part of the artifact

BPE and WordPiece in the original papers assume you already have word-like units. Ask who owns that boundary for Japanese, Chinese, or a code comment where spaces don't mark each word. SentencePiece is a tokenizer and detokenizer framework that trains directly from raw sentences instead of requiring pre-tokenized word sequences.^{[7]Reference 7SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing.https://arxiv.org/abs/1808.06226}

SentencePiece makes spaces visible as ▁ (U+2581), so prompt cache failed becomes a stream like ▁prompt▁cache▁failed before final pieces are chosen. A leading ▁ dummy prefix lets a sentence-initial word use the same piece as that word after a space.

Decoding therefore targets the normalized input string, not necessarily the original raw byte sequence, because normalization can fold equivalent or compatibility forms.

The same artifact can reserve IDs for protocol symbols. SentencePiece documents <unk>, BOS <s>, EOS </s>, and padding as special meta symbols; BERT uses [CLS] and [SEP] for sequence roles.^{[7]Reference 7SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing.https://arxiv.org/abs/1808.06226}^{[6]Reference 6BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.https://arxiv.org/abs/1810.04805}

These IDs aren't ordinary substrings. A serving wrapper must decide whether text that resembles a marker is treated as control input or literal text, then pin that choice with the checkpoint.

SentencePiece raw-text path for token ﬁle delayed: NFKC folds the ﬁ ligature to fi, a dummy-prefix meta-space marks boundaries as ▁token▁file▁delayed, Unigram Viterbi emits the lab's twelve pieces, and replacing ▁ restores token file delayed. — Follow the lab string left to right: the artifact folds `ﬁ`, inserts visible boundary markers, then segments. Decoding restores spaces from `▁` and matches the normalized text, not the original ligature.

SentencePiece can host BPE, and it also supports the Unigram language model algorithm proposed with subword regularization. Unigram starts with many candidate pieces, assigns probabilities, and removes pieces that contribute least to corpus likelihood.^{[8]Reference 8Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates.https://arxiv.org/abs/1804.10959}

Candidate removal keeps the vocabulary small while retaining alternate paths that explain the corpus.

Training can sample multiple valid segmentations. Serving usually needs one reproducible answer, so it selects the highest-probability path. Viterbi dynamic programming finds that path by keeping, at each character offset, the best-scoring piece that ends there.

The classroom version uses Python's NFKC fold as a stand-in for SentencePiece's packaged NFKC-family default, then scores a tiny hand-set vocabulary. It isn't the official trainer. It isolates the serving path: normalize, mark spaces, pick one segmentation, decode.

07-unigram-viterbi.py

from math import inf
import unicodedata

logp = {
    "▁token": -0.4,
    "▁": -1.2,
    "token": -2.0,
    "f": -1.8,
    "i": -1.8,
    "l": -1.8,
    "e": -1.8,
    "de": -1.0,
    "a": -1.8,
    "y": -1.8,
    "ed": -0.9,
    "d": -2.2,
}

def viterbi_segment(text: str, scores: dict[str, float]) -> list[str]:
    n = len(text)
    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 ﬁle delayed"
normalized = unicodedata.normalize("NFKC", raw_message)
marked = "▁" + normalized.replace(" ", "▁")
pieces = viterbi_segment(marked, logp)
decoded = "".join(pieces).replace("▁", " ").lstrip()

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"

Output

raw: token ﬁle 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 that piece outscores ▁ plus token. file fragments because this vocabulary never made file a cheap path.

The decoded line matches NFKC text, so the original ﬁ ligature is gone. Boundary handling and normalization shaped both the pieces and the round trip, which is why SentencePiece belongs in the artifact contract.

Vocabulary size spends parameters to save positions

Suppose a larger vocabulary saves three tokens on one prompt. Ask what those saved positions cost. Every added vocabulary entry can compress a recurring string into fewer tokens, but it also adds an embedding row.

If the output projection isn't tied to the input embedding matrix, it adds another row there too.

For a vocabulary of size $V$ and hidden dimension $d$ , an input embedding matrix contains $Vd$ parameters. With float16 weights, each parameter takes two bytes. A second untied output matrix doubles that vocabulary-dependent memory, so the cost grows linearly with $V$ .

Llama 2 shipped a 32k SentencePiece BPE vocabulary.^{[4]Reference 4Llama 2: Open Foundation and Fine-Tuned Chat Models.https://arxiv.org/abs/2307.09288} Llama 3 moved to 128k tokens: 100k pieces from the tiktoken family plus 28k extra tokens aimed at non-English text.^{[9]Reference 9The Llama 3 Herd of Models.https://arxiv.org/abs/2407.21783}

On a sample of English, the Llama 3 report measured compression improving from 3.17 to 3.94 characters per token. That sample is evidence of a tradeoff, not a workload-wide guarantee. Extra rows are justified only when measured token savings and downstream quality pay for them.

The next snippet compares hypothetical vocabularies for a model with hidden dimension 4096. It calculates embedding memory, including an untied output matrix, rather than treating a larger vocabulary as free.

08-vocabulary-memory-budget.py

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",
    )

Output

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 output makes the parameter bill concrete. Sequence compression still needs its own measurement: a vocabulary can shorten common English prompts and fragment another script or a TypeScript identifier. Tokenizer design is an evaluation problem, not a race to the largest V.

Audit language and code token budgets

Fertility measures token length. At word level, calculate the average number of tokenizer pieces needed per word. For parallel-message audits, compare total token count or a locale-to-baseline ratio for equivalent text.

That ratio can change product economics. Petrov et al. measured translated text and found tokenizer-length disparities as large as 15 times: with the ChatGPT and GPT-4 tokenizer, Shan can take about 15 times as many tokens as English for the same content, affecting cost, latency, and available context.^{[10]Reference 10Language Model Tokenizers Introduce Unfairness Between Languages.https://arxiv.org/abs/2305.15425}

The classroom BPE trainer started from whole terms. Production BPE usually pre-tokenizes first: split on whitespace and punctuation so a repeated sentence can't collapse into one memorized piece. Merges then run inside those spans.

That boundary explains why tokenCount doesn't automatically become one token just because token is common.

CamelCase split on a lowercase merge table: tokenCount becomes token, C, o, un, t and encodePrompt becomes encode, P, rompt, while lowercase prompt stays one piece. — The audit trainer learned `token`, `encode`, and lowercase `prompt`. CamelCase identifiers therefore fracture: `tokenCount` keeps `token` and spells the rest, and `encodePrompt` becomes `encode` + `P` + `rompt`.

Now test the same artifact against different input forms. Train a small byte-level BPE on a handful of English and TypeScript spans, then encode parallel fixtures. Japanese has no learned merges here, so it stays a UTF-8 byte sequence.

The sample isn't a language-quality study; use it as a repeatable audit shape you can point at a real tokenizer later.

09-audit-token-lengths.py

from collections import Counter
import re

PRETOK = re.compile(r"[A-Za-z]+|\d+|\s+|[^\sA-Za-z\d]")

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():
    ids = encode(text, merges)
    print(f"{name:>10}: {len(ids):>2} tokens {len(ids) / english_tokens:>4.2f}x english")
    assert "".join(ids).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", ";",
]

Output

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 output gives three different diagnoses. Portuguese reuses token inside tokenizo, so it can land shorter than English on this toy merge list. Japanese stays at 54 byte pieces because no Japanese pair was ever selected. encodePrompt becomes encode + P + rompt because prompt was learned in lowercase.

None of those single samples ranks a language or codebase. Build a locale-aware test set, record tokenizer version, compare distribution summaries, and then check downstream task quality.

The hand-written split of unexpectedly into un expect ed ly was optimistic. This corpus earned une and ed, not expect, so the same word still fragments. A candidate split describes an intention; a trained artifact determines the actual budget.

Make Unicode policy explicit

Two strings can look identical while holding different Unicode code points. For example, café may contain one composed é or the sequence e plus a combining accent. If clients normalize differently, cache keys, token counts, and filter behavior can disagree before the model sees the text.

Normalization Form C (NFC) composes canonically equivalent forms without folding broad compatibility distinctions. Normalization Form Compatibility Composition (NFKC) also folds compatibility characters, such as the ﬁ ligature into fi.

SentencePiece's published default is NFKC-family normalization packaged inside the model file.^{[7]Reference 7SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing.https://arxiv.org/abs/1808.06226} Python exposes both forms through unicodedata.normalize. Choosing between them is a product policy decision, not an automatic cleanup rule.

NFC can make equivalent spellings share IDs while preserving compatibility distinctions; NFKC may remove distinctions your product needs.

Unicode normalization comparison: composed café and decomposed cafe plus U+0301 begin unequal but NFC makes them equal, while NFC preserves the ﬁ ligature in ﬁle and NFKC folds it to file before token IDs are assigned. — The left lane reproduces the lab's `False → True` canonical-equivalence result under NFC. The right lane makes the policy boundary explicit: NFC preserves `ﬁle`, while NFKC changes it to `file`. Version that choice with cache keys and tokenizer IDs.

The checks below make both boundaries visible. For user-visible prompts, you might choose NFC first and add separate security checks for invisible or confusable characters. Another product may deliberately choose NFKC after deciding the information loss is acceptable.

10-normalize-before-tokenizing.py

import unicodedata

composed = "café"
decomposed = "cafe\u0301"
ligature = "ﬁle"

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"

Output

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

Tokenizer behavior must be versioned with this policy. If one service normalizes with NFC and another silently folds with NFKC, they can send different IDs to the same model or generate different cache keys for text that looks unchanged. Test normalization before tokenization, not only after decoding.

Compare algorithms without mixing contracts

The common tokenizer families are design choices, not names to memorize. Return to unexpectedly from the running status line and ask one operational question: what exact serving rule turns it into IDs?

Three compact lanes tokenize unexpectedly with different inference rules: BPE replays ranked merges into un, expect, ed, ly; WordPiece scans longest valid spans with hash-hash continuations; Unigram compares complete segmentation paths by score. — One word exposes three different mechanics. BPE replays learned merge ranks, WordPiece scans for the longest valid piece, and Unigram selects among scored segmentation paths. Each model still depends on its exact vocabulary, normalizer, and fallback policy.

Method	Training view	Serving view	Boundary/fallback detail
BPE	Add frequent adjacent merges	Replay ordered merges	Byte-level variants retain UTF-8 coverage; trainers usually pre-tokenize
WordPiece	Grow vocabulary for likelihood objective	Greedy longest valid piece	BERT-style continuation uses `##`; missing segmentation can yield `[UNK]`
SentencePiece BPE	BPE trained directly on raw normalized text	Replay packaged model	Visible whitespace marker can be part of pieces
SentencePiece Unigram	Estimate and prune candidate-piece probabilities	Best path or sampled alternatives when requested	Segmentation sampling supports regularized training

The table turns that question into a review path. Start with observed symptom, identify the contract boundary that could explain it, then run the smallest check that separates cause from coincidence.

Production review checklist

Symptom	Likely cause	Check or fix
Model output collapses after swapping tokenizer file	IDs no longer match trained embeddings	Pin tokenizer artifact and model checkpoint together
Locale hits token limit sooner than English	Unequal fertility on translated requests	Measure parallel message sets by locale and task
CamelCase identifiers explode into many pieces	Merges were learned on lowercase fragments	Audit real repository files, not English prompts alone
A WordPiece model emits `[UNK]` for new identifiers	No valid vocabulary segmentation	Evaluate vocabulary/model update rather than masking the failure
Cache misses differ across clients for same visible message	Unicode preprocessing isn't consistent	Version and test normalization plus tokenizer pipeline
Repository prompt holds less code than expected	Code fixtures fragment into many tokens	Measure actual files with intended deployed tokenizer

Mastery check

Evaluation rubric

Foundational: Given a five-word corpus, you can calculate one BPE winner by hand and apply it to updated pieces.
Intermediate: You can implement BPE replay and WordPiece longest-match segmentation, then explain why their failure behavior differs.
Intermediate: You can show the difference between SentencePiece BPE and SentencePiece Unigram without calling SentencePiece a merge algorithm.
Advanced: You can present a tokenizer audit with locale fixtures, code fixtures, pre-tokenization, normalization policy, vocabulary memory cost, and artifact versioning.

Follow-up questions

Common pitfalls

Retraining during inference: Pair frequencies are counted while building BPE rules, not while serving each prompt. Serving must replay fixed rules.
Skipping a pre-tokenizer: BPE on raw repeated strings can memorize whole prompts. Production trainers split on whitespace and punctuation first, then merge inside those spans.
Conflating byte-level BPE with byte fallback: GPT-2 starts from byte representations. Other tokenizers may invoke explicit byte fallback only when ordinary pieces can't encode an input. Both preserve coverage, but they aren't the same mechanism.
Describing the WordPiece proxy as its spec: The association score clarifies the intuition. The original method is likelihood-driven, and implementations can vary.
Calling SentencePiece a fourth algorithm: SentencePiece packages raw-text handling and can host BPE or Unigram models.
Assuming byte fallback means fair multilingual cost: Coverage avoids unknown characters; it doesn't make segment lengths equal.
Normalizing without a policy: NFC and NFKC solve different problems. Compatibility folding can discard distinctions your product intended to preserve.

Next Step

Continue to Static to Contextual Embeddings

Token IDs are a stable input contract, and their cost is something you can measure. Next you'll look up a vector for each ID and see why the same row isn't enough when a word such as `charge` appears in two senses.

PreviousThe Bitter Lesson & Compute

Share this article