Tokenization Explained: BPE, WordPiece, and SentencePiece

A text tokenizer maps strings to token IDs, and an embedding table turns those IDs into vectors for a neural model. The pipeline can normalize text, split it into preliminary chunks, segment those chunks, and add special tokens. Its choices affect sequence length, vocabulary size, unknown-input handling, and the amount of text that fits in a context window. Token IDs are lookup indices: a larger ID does not mean a larger or more important word.

Why not words, and why not characters

A fixed word-level vocabulary needs a policy for forms it does not contain. A common policy maps them to one unknown token, losing their spelling distinction at that stage. Separate entries for “run”, “runs”, and “running” do not explicitly share character structure, though learned embeddings can still capture related meanings. Frequency cutoffs, spelling variation, and domain-specific terms all affect coverage.

Character tokenization retains finer spelling structure for characters in its alphabet, but a finite character vocabulary can still miss unseen characters. It usually creates more tokens than word or subword encoding, with a ratio that depends on the language and text. If token length rises by a factor \(r\), dense attention’s pairwise term rises by \(r^2\) at fixed width; total model cost also includes projections, the output vocabulary, and other operations. Bytes cover a fixed alphabet, while Unicode code points and user-perceived characters are different units.

Subword tokenizers learn reusable pieces that may span whole frequent words or parts of rare words. These pieces need not be morphemes. Unknown characters remain possible unless the tokenizer includes an adequate fallback, such as complete byte coverage. A tokenizer can encode a spelling without the model understanding it.

Self-attention, masking, and the full block are derived in Transformers from Scratch: Self-Attention to Encoder–Decoder.

Byte pair encoding

In this word-based BPE demonstration, training begins with characters and an end-of-word marker. Count adjacent symbol pairs weighted by word frequency, merge the most frequent pair, and repeat. Ties use first encounter order in the supplied corpus, which we preserve explicitly. Encoding applies the saved rules in learned order; it does not relearn frequencies from the input. Each rule introduces a merged symbol if it is new, so the number of distinct vocabulary entries is not automatically base size plus rule count in every implementation.

from collections import Counter

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

def learn_bpe(word_freqs, num_merges):
    """Nonempty whitespace-free words with positive integer counts."""
    if num_merges < 0 or any(not w or any(c.isspace() for c in w) or "</w>" in w
                             or not isinstance(n, int) or n <= 0 for w, n in word_freqs.items()):
        raise ValueError("invalid corpus or merge count")
    words = {tuple(w) + ("</w>",): n for w, n in word_freqs.items()}
    merges = []
    for _ in range(num_merges):
        pairs = Counter()
        for symbols, count in words.items():
            for pair in zip(symbols, symbols[1:]):
                pairs[pair] += count
        if not pairs:
            break
        best = max(pairs, key=pairs.get)
        merges.append(best)
        merged = Counter()
        for symbols, count in words.items():
            merged[merge_symbols(symbols, best)] += count
        words = dict(merged)
    return merges

def encode_word(word, merges, alphabet):
    if not word or any(c not in alphabet for c in word):
        raise ValueError("word contains an unknown character or is empty")
    symbols = tuple(word) + ("</w>",)
    for pair in merges:
        symbols = merge_symbols(symbols, pair)
    return symbols

corpus = {"low": 5, "lower": 2, "newest": 6, "widest": 3}
merges = learn_bpe(corpus, 8)
for pair in merges:
    print(pair)
# ('e', 's')
# ('es', 't')
# ('est', '</w>')
# ('l', 'o')
# ('lo', 'w')
# ('n', 'e')
# ('ne', 'w')
# ('new', 'est</w>')
alphabet = set("".join(corpus))
print(encode_word("lowest", merges, alphabet))
# ('low', 'est</w>')

“Lowest” was not in the training corpus, but the learned pieces encode it as low plus est at the word end. This is a useful subword combination; it does not show that BPE understands superlatives. Pair counts are recomputed after each merge, and occurrences are merged left to right without overlapping. Tuple-level matching prevents a pair from accidentally matching a substring inside an already merged token.

The end marker is a separate initial symbol that can join a merged piece, preserving a distinction between internal and word-final forms. In a complete tokenizer, saved symbols map to fixed IDs and a decoder reverses the representation under its normalization and boundary conventions. This educational helper encodes one word and intentionally rejects characters absent from the training alphabet.

Byte-level BPE

Byte-level BPE starts from 256 possible byte values. GPT-2 first converts valid text to UTF-8 bytes, represents bytes through a reversible symbol mapping, and applies merges within regex-defined chunks. This differs from running unrestricted BPE over any arbitrary binary input. A full byte alphabet can represent all valid UTF-8 text, including scripts not present in the training data; the public text API’s handling of malformed input is a separate issue.

Complete byte coverage avoids unknown ordinary-text bytes, but it does not guarantee semantic understanding or efficient segmentation. A token can contain only part of a multibyte character, so decoding one token in isolation may not yield valid text even when decoding the entire sequence does.

WordPiece and Unigram

WordPiece is used by BERT. At encoding time, its common implementation greedily chooses the longest vocabulary piece matching the current prefix; noninitial pieces use the continuation marker ##. If the rest of a pretokenized word cannot be covered, BERT-style WordPiece returns an unknown token for that whole word. Training has likelihood-based origins; the often-taught pair-frequency ratio is not a universal specification of every WordPiece trainer. The saved vocabulary and the inference algorithm are what determine encoding.

def wordpiece_word(word, vocab):
    """Single pretokenized word; longest match with ## continuation pieces."""
    pieces, start = [], 0
    while start < len(word):
        for end in range(len(word), start, -1):
            piece = ("##" if start else "") + word[start:end]
            if piece in vocab:
                pieces.append(piece)
                start = end
                break
        else:
            return ["[UNK]"]
    return pieces

wp_vocab = {"[UNK]", "play", "##ing", "##s"}
print(wordpiece_word("playing", wp_vocab))
print(wordpiece_word("plays", wp_vocab))
print(wordpiece_word("playz", wp_vocab))
# ['play', '##ing']
# ['play', '##s']
# ['[UNK]']

The first two words use stored continuation pieces. For playz, recognizing play is insufficient: the remaining z cannot be covered, so the whole word becomes unknown. This helper demonstrates segmentation only; normalization, pretokenization, maximum word length, and automatic special-token insertion belong to the surrounding implementation.

A Unigram tokenizer assigns probabilities to pieces and scores a segmentation by their product. Training starts from a candidate vocabulary and prunes pieces while re-estimating probabilities to preserve corpus likelihood, subject to coverage constraints. For a toy string ab, suppose piece probabilities are \(P(a)=0.4,P(b)=0.3,P(ab)=0.1\). The segmentation a|b has weight 0.12 and ab has weight 0.1; after conditioning on these two possible segmentations, their probabilities are about 0.545 and 0.455. Best-path decoding chooses a|b, while sampling can choose either. Sampling segmentations during training is subword regularization; it need not be restricted to once per epoch.

SentencePiece is a toolkit supporting BPE and Unigram, not a third merge algorithm. It can train from raw sentences without an external word splitter and represents spaces with ▁ under its usual conventions. This is useful for languages whose word boundaries are not consistently marked by spaces. Default normalization includes an NFKC-based transformation and whitespace processing; a dummy leading-space marker may also appear. For example, compatibility normalization maps full-width Ａ to A, losing that original distinction. Decoding therefore need not reproduce the original string byte for byte. Character coverage, normalization, and optional byte fallback are model settings, not guarantees supplied by the library name.

Choosing a vocabulary size

Vocabulary size trades sequence length against embedding parameters and softmax cost.

The table uses decimal K and rounded M: the embedding count is \(Vd\), so 32,000 entries at width 1,024 require 32,768,000 parameters. A separate output projection adds roughly another \(Vd\); tied weights avoid that parameter duplication but not full-vocabulary scoring cost. A larger vocabulary can shorten sequences while increasing storage and output computation. The net effect depends on the tokenizer, architecture, workload, and data distribution; vocabulary size alone does not establish speed or multilingual coverage.

The multilingual fairness problem

Training-data imbalance can produce different segmentation efficiency across languages. Studies such as Petrov et al. measure substantial disparities for specific tokenizers and parallel text. Their size is not a universal two-to-five multiplier, and an English-heavy corpus does not imply every other language is encoded equally poorly.

More tokens for comparable content consume more of a token-limited context and, under token-based pricing, can increase cost. Measure raw counts on aligned translations as well as length-normalized statistics. Tokens per Unicode code point is a descriptive ratio, not a language-neutral measure of information: composed Hangul syllables, combining marks, spaces, and emoji differ in structure. Fertility is also often defined per word, so state your denominator explicitly.

def tokenization_stats(encode_ids, samples):
    """encode_ids(text) returns ordinary-text IDs without automatic BOS/EOS."""
    result = {}
    for name, text in samples.items():
        ids = encode_ids(text)
        chars = len(text)
        result[name] = {"tokens": len(ids), "code_points": chars,
                        "tokens_per_code_point": len(ids) / chars if chars else None}
    return result

# A UTF-8 byte baseline, not a learned BPE model or a fairness benchmark.
samples = {"en": "cat", "ko": "고양이", "digits": "1234", "empty": ""}
report = tokenization_stats(lambda text: list(text.encode("utf-8")), samples)
for name, row in report.items():
    print(name, row)
# en {'tokens': 3, 'code_points': 3, 'tokens_per_code_point': 1.0}
# ko {'tokens': 9, 'code_points': 3, 'tokens_per_code_point': 3.0}
# digits {'tokens': 4, 'code_points': 4, 'tokens_per_code_point': 1.0}
# empty {'tokens': 0, 'code_points': 0, 'tokens_per_code_point': None}

Effects to inspect in your data

• Arithmetic and digits. Token IDs do not explicitly expose individual digits inside a multi-digit token. This can make digit-level operations harder, but does not make learning numeric structure impossible. Tokenizers use different digit grouping rules; inspect the specific implementation.
• Character-level tasks. Single-token words do not directly expose character positions to the model. Tokenization is one possible contributor to letter-counting difficulty, alongside training and reasoning behavior; it is not a complete diagnosis.
• Leading whitespace. Leading spaces can change segmentation in whitespace-sensitive tokenizers. Encoding two pieces separately and concatenating IDs need not equal encoding their joined text. Use the checkpoint’s intended prompt or chat construction pipeline.
• Rare tokens. Rare entries may receive less informative training. Their initialization, shared structure, and output-layer updates also matter; rarity alone does not prove an embedding stays random or causes erratic output.
• Domain mismatch. Measure fragmentation on domain text. A domain tokenizer may reduce length, but changing an existing model’s tokenizer requires preserving or adapting its ID mapping and training the affected embeddings and output head.

How dense word vectors are learned in the first place is covered in Word Embeddings: Word2Vec, Negative Sampling, GloVe, and Bias.

Practical rules

• Save the tokenizer, normalization rules, special-token IDs, and prompt template with the checkpoint. Incompatible ID mappings can cause errors or degraded predictions; verify IDs and outputs when loading or changing a tokenizer.
• Plan special-token semantics and IDs. Adding a genuinely new ID may require resizing input embeddings and the output head, preserving any weight tying, then training the new entries. Reusing an existing reserved ID is a different operation.
• Test decode(encode(text)) against the documented normalization and special-token policy. A mismatch can be intentional normalization, unknown-token replacement, whitespace cleanup, or special-token handling; inspect the cause instead of assuming exact raw-text recovery.
• Inspect token strings and IDs on representative text, leading spaces, unusual Unicode, numbers, and literal special-token strings. Record the tokenizer version and relevant options.

How these models are pretrained at scale is covered in LLM Pretraining: Objectives, Data, and Scaling Laws.

Exercises

1. Run BPE by hand. Implement the merge loop on a tiny corpus and report the first three merges and the vocabulary after each. Explain what decides the order.

You should get: pair frequency determines the maximum, with deterministic tie-breaking needed when several pairs tie.

from collections import Counter
corpus = {"low": 5, "lower": 2, "newest": 6, "widest": 3}
words = {tuple(w) + ("</w>",): c for w, c in corpus.items()}
for step in range(3):
    pairs = Counter()
    for symbols, count in words.items():
        for pair in zip(symbols, symbols[1:]):
            pairs[pair] += count
    best = max(pairs, key=pairs.get)
    print(f"merge {step+1}: {best} count {pairs[best]}")
    merged = Counter()
    for symbols, count in words.items():
        merged[merge_symbols(symbols, best)] += count
    words = dict(merged)
    print(words)
# merge 1: ('e', 's') count 9
# {('l', 'o', 'w', '</w>'): 5, ('l', 'o', 'w', 'e', 'r', '</w>'): 2, ('n', 'e', 'w', 'es', 't', '</w>'): 6, ('w', 'i', 'd', 'es', 't', '</w>'): 3}
# merge 2: ('es', 't') count 9
# {('l', 'o', 'w', '</w>'): 5, ('l', 'o', 'w', 'e', 'r', '</w>'): 2, ('n', 'e', 'w', 'est', '</w>'): 6, ('w', 'i', 'd', 'est', '</w>'): 3}
# merge 3: ('est', '</w>') count 9
# {('l', 'o', 'w', '</w>'): 5, ('l', 'o', 'w', 'e', 'r', '</w>'): 2, ('n', 'e', 'w', 'est</w>'): 6, ('w', 'i', 'd', 'est</w>'): 3}

2. Measuring segmentation efficiency. Apply tokenization_stats to aligned sentences in the languages you intend to support using a specified tokenizer and revision. Test digit strings separately. Report token counts, code-point counts, and their ratios with automatic boundary tokens excluded.

You should get: measurements tied to a named tokenizer and sample set, without assuming a particular language ranking or multiplier.

3. Literal special-token strings. Explain what goes wrong if a user’s input containing the literal string <|endoftext|> is tokenized with special-token parsing enabled, and describe the fix.

You should get: behavior that depends on the tokenizer’s literal-special-token policy and the application’s interpretation of the resulting ID.

References

• Schuster and Nakajima (2012). Japanese and Korean Voice Search. ICASSP.
• Sennrich, Haddow, and Birch (2016). Neural Machine Translation of Rare Words with Subword Units. ACL.
• Kudo (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL.
• Kudo and Richardson (2018). SentencePiece: A Simple and Language Independent Subword Tokenizer and Detokenizer for Neural Text Processing. EMNLP.
• Radford et al. (2019). Language Models Are Unsupervised Multitask Learners. OpenAI technical report.
• Petrov, La Malfa, Torr, and Bibi (2023). Language Model Tokenizers Introduce Unfairness Between Languages. NeurIPS.
• Implementation documentation: SentencePiece normalization, tiktoken encoding API, and Hugging Face tokenizer options.