SentencePiece and unigram: lattices, normalization and compatibility

First separate the toolkit from the algorithm

SentencePiece is a toolkit supporting BPE, unigram, character and word models. “SentencePiece” does not mean “unigram.” LLaMA1 describes BPE implemented with SentencePiece; Llama2 retains that tokenizer lineage. Llama3 uses a tiktoken-style byte BPE tokenizer. The original claim that all three use SentencePiece unigram was false, as was the story that Llama3 switched from unigram because unigram inference is nondeterministic.

Unigram can choose a deterministic best segmentation. BPE can also introduce randomness via merge dropout. Algorithm, normalization, pre-tokenization, inference mode, special-token policy and implementation are separate choices. Bring the ordered-byte-merge model from DL044; here we derive the probabilistic alternative, implement its lattice, examine normalization and provide complete local-library procedures with explicit unexecuted boundaries.

1 · A probability model over segmentations

A vocabulary V assigns each piece a positive probability p. For a particular segmentation z, its score is the product of piece probabilities. For a raw normalized string x, many segmentations may spell x; the string's likelihood sums their scores:

Maximizing this marginal likelihood differs from maximizing the probability of only the best segmentation. Viterbi finds the maximum-probability path for deterministic encoding. Forward–backward sums over paths to obtain posterior expected counts for the EM update. Calling Viterbi the ordinary E-step silently replaces soft EM with a hard-assignment approximation.

For ab and pieces a:.4, b:.4, ab:.2, the paths are[a,b] with score.16 and[ab] with score.2. The total likelihood is.36; posterior probabilities are4/9 and5/9. Viterbi choosesab, but the expected count ofa is4/9, not0. This small example distinguishes all three quantities.

2 · Growing versus pruning: useful analogy, bounded claim

BPE is an additive shorthand builder; unigram is an editor removing weak candidates from a large seed vocabulary. Kudo's2018 algorithm optimizes probabilities for a fixed candidate set, estimates loss from deleting pieces, prunes low-utility pieces while retaining required coverage, and repeats. Candidate mining and deletion scoring are heuristic. The paper explicitly calls joint vocabulary/probability optimization intractable; it does not promise a globally optimal vocabulary or mandate a10% pruning rate. Its example retention factor is80%.

Pruning is a practical search strategy, not a logical necessity imposed by a global objective. Other search procedures are possible. A piece's value depends on alternatives: deletingab routes probability througha,b, but deleting botha andab can destroy coverage. Never prune indispensable base symbols merely because their standalone frequency is small.

3 · Executable lattice, Viterbi and soft EM

This CPU program uses short strings so direct products remain numerically safe. Production implementations need log-space or scaled dynamic programming for long strings. It is a unigram mechanism demonstration, not a replacement for the optimized SentencePiece trainer.

import math, random
from collections import Counter
 
def lattice(text, probs):
    if not probs or any(not t or p <= 0 for t,p in probs.items()):
        raise ValueError('nonempty pieces with positive probabilities required')
    if not math.isclose(sum(probs.values()), 1., abs_tol=1e-10):
        raise ValueError('probabilities must sum to one')
    edges = [[] for _ in range(len(text)+1)]
    for i in range(len(text)):
        for token,p in probs.items():
            if text.startswith(token,i):
                edges[i].append((i+len(token),token,p))
    return edges
 
def forward_backward(text, probs):
    edges = lattice(text,probs); n = len(text)
    alpha = [0.]*(n+1); alpha[0] = 1.
    for i in range(n):
        for j,t,p in edges[i]:
            alpha[j] += alpha[i]*p
    if alpha[n] == 0:
        raise ValueError('unrepresentable string or numeric underflow')
    beta = [0.]*(n+1); beta[n] = 1.
    for i in reversed(range(n)):
        beta[i] = sum(p*beta[j] for j,t,p in edges[i])
    counts = Counter()
    for i in range(n):
        for j,t,p in edges[i]:
            counts[t] += alpha[i]*p*beta[j]/alpha[n]
    return alpha[n], counts, beta, edges
 
def viterbi(text, probs):
    edges = lattice(text,probs); best = [-math.inf]*(len(text)+1)
    paths = [None]*(len(text)+1);best[0]=0.;paths[0]=[]
    for i in range(len(text)):
        if paths[i] is None:
            continue
        for j,t,p in edges[i]:
            score = best[i]+math.log(p)
            if score > best[j]:
                best[j],paths[j] = score,paths[i]+[t]
    if paths[-1] is None:
        raise ValueError('unrepresentable input')
    return paths[-1],best[-1]
 
def posterior_sample(text, probs, rng):
    total,counts,beta,edges = forward_backward(text,probs)
    i,out = 0,[]
    while i < len(text):
        options = [(j,t,p*beta[j]) for j,t,p in edges[i] if beta[j] > 0]
        chosen = rng.choices(options, weights=[x[2] for x in options])[0]
        i = chosen[0];out.append(chosen[1])
    return out
 
def em_step(corpus,probs):
    expected = Counter(); old_loss = 0.
    for text in corpus:
        z,c,_,_ = forward_backward(text,probs)
        old_loss += math.log(z);expected.update(c)
    denominator = sum(expected.values())
    if not denominator:
        raise ValueError('corpus must contain nonempty text')
    updated = {t:c/denominator for t,c in expected.items() if c>0}
    new_loss = sum(math.log(forward_backward(x,updated)[0]) for x in corpus)
    return updated,old_loss,new_loss
 
p = {'a':.4,'b':.4,'ab':.2}
z,expected,_,_ = forward_backward('ab',p)
assert math.isclose(z,.36)
assert math.isclose(expected['a'],4/9) and math.isclose(expected['ab'],5/9)
assert viterbi('ab',p)[0] == ['ab']
assert not math.isclose(expected['ab'],1.)  # hard/Viterbi E-step is not soft EM
new,before,after = em_step(['ab','a','b','abab'],p)
assert after >= before-1e-12
rng = random.Random(45)
draws = Counter(tuple(posterior_sample('ab',p,rng)) for _ in range(5000))
assert abs(draws[('ab',)]/5000 - 5/9) < .03
assert ''.join(viterbi('abab',p)[0]) == 'abab'
print('likelihood',z,'expected counts',dict(expected),'EM',before,after,'samples',dict(draws))

The M-step normalizes posterior expected piece counts across the corpus. With a fixed vocabulary and exact arithmetic it does not decrease the marginal-likelihood objective. Pruning may decrease it; the design question is how much likelihood loss is acceptable for a smaller vocabulary. Token probability is not a linguistic word probability, and the independent-piece model is a tokenizer model rather than the contextual LM trained afterward.

4 · Whitespace and normalization are not lossless by default

SentencePiece represents whitespace with the visible metaspace glyph▁. It can operate from raw sentences without an externally supplied language-specific word segmenter. That does not mean every configuration allows pieces to cross whitespace: the v0.2.1 proto has split_by_whitespace=true by default. Its normalizer defaults also include NFKC-style normalization, a dummy prefix and removal of leading/trailing/repeated whitespace. Bytes lost by normalization cannot be recovered by joining pieces.

Hello world may be normalized to a stream with a dummy leading metaspace and segmented as▁Hello, ▁world; the actual pieces depend on the trained model. A processor's decoder understands normalization and special-piece types. Blindly replacing every glyph with a space can mishandle dummy-prefix rules, byte-fallback pieces and literal occurrences of the glyph.

Three separate contracts matter:

1. Raw text round trip: decode(encode(x)) equals x, only if the full pipeline preserves x.
2. Normalized text round trip: decode(encode(x)) equals the specified normalized representation.
3. Token-ID round trip: encode(decode(ids)) equals ids, which need not hold even for lossless text because alternative segmentations can spell the same text.

Here is a concrete ID-level counterexample using the lattice above. Treat piece names as IDs for this fixture. Decoding the sampled path ['a', 'b'] gives ab exactly; deterministic re-encoding chooses ['ab'], so the text is unchanged but the sequence length and IDs change. A cache keyed by the original prefix IDs must not be reused for that new prefix merely because the displayed text matches.

sampled_ids = ['a', 'b']
decoded_text = ''.join(sampled_ids)
canonical_ids = viterbi(decoded_text, {'a': .4, 'b': .4, 'ab': .2})[0]
assert decoded_text == ''.join(canonical_ids) == 'ab'
assert canonical_ids == ['ab'] and canonical_ids != sampled_ids

This is a segmentation/caching counterexample, not a claim that every SentencePiece model emits these particular pieces.

Test leading/repeated/trailing spaces, tabs/newlines, combining forms, full-width characters, mixed scripts, emoji and literal special-token spellings. Byte fallback can represent unknown characters after normalization but cannot undo lossy normalization. It is disabled by default in the cited SentencePiece proto, not magically enabled by choosing BPE or unigram.

import unicodedata
raw = '  Ａ  cafe\u0301  '
normalized = ' '.join(unicodedata.normalize('NFKC',raw).split())
assert normalized == 'A café' and normalized != raw
# This is a normalization counterexample, not an execution of SentencePiece.
print('normalization loses raw distinctions',repr(raw),'->',repr(normalized))

5 · Complete local-library training procedures

The existing CPU runtime does not contain SentencePiece or Hugging Face tokenizers. The following callable programs are source-reviewed and syntax-checked, unexecuted. They neither download corpora/models nor install dependencies. A reader with the stated packages already available supplies a permitted UTF-8 corpus and a dedicated output directory. Split train/validation by provenance before calling them, hash inputs and record actual package versions.

The SentencePiece procedure explicitly chooses normalization and whitespace policy rather than relying on those defaults; piece splitting still uses the versioned default split_by_whitespace=True. Corpus files are line-oriented; newline handling still needs a task-specific test. hard_vocab_limit=False permits a small corpus to produce fewer pieces than the requested maximum. Byte fallback consumes256 slots, so budget accordingly.

# Optional reference: SentencePiece v0.2.1; unexecuted in this review.
def train_sentencepiece_local(corpus_path, output_dir, vocab_size=8000):
    from pathlib import Path
    import sentencepiece as spm
    import hashlib, json
    source = Path(corpus_path).resolve(); out = Path(output_dir).resolve()
    if not source.is_file() or vocab_size < 300:
        raise ValueError('existing corpus and vocabulary budget >=300 required')
    out.mkdir(parents=True,exist_ok=True)
    result = {}
    for algorithm in ('bpe','unigram'):
        prefix = out/algorithm
        if prefix.with_suffix('.model').exists():
            raise FileExistsError(prefix.with_suffix('.model'))
        spm.SentencePieceTrainer.train(input=str(source),model_prefix=str(prefix),
            model_type=algorithm,vocab_size=vocab_size,character_coverage=1.0,
            normalization_rule_name='identity',remove_extra_whitespaces=False,
            add_dummy_prefix=False,byte_fallback=True,hard_vocab_limit=False,
            shuffle_input_sentence=False,num_threads=1)
        processor = spm.SentencePieceProcessor(model_file=str(prefix)+'.model')
        probes = ['Hello world','  leading  spaces  ','తెలుగు 🙂','Ａ cafe\u0301',
                  'def f():\n    return 1','<s> literal']
        checks = [{'input':s,'ids':processor.encode(s,out_type=int),
                   'decoded':processor.decode(processor.encode(s,out_type=int))} for s in probes]
        result[algorithm] = dict(vocab=processor.get_piece_size(),checks=checks,
            model_sha256=hashlib.sha256(Path(str(prefix)+'.model').read_bytes()).hexdigest())
        if algorithm == 'unigram':
            result[algorithm]['samples'] = [processor.encode('Hello world',out_type=str,
                enable_sampling=True,nbest_size=-1,alpha=0.1) for _ in range(5)]
    result['input_sha256'] = hashlib.sha256(source.read_bytes()).hexdigest()
    (out/'manifest.json').write_text(json.dumps(result,ensure_ascii=False,indent=2))
    return result

Do not claim the awkward probes all pass until inspecting the installed processor's output. For code, preserve record boundaries/newlines under an explicitly tested serialization policy; normalization settings alone are not a universal guarantee for every Unicode/control character.

The HF0.22.1 API exposes BPE, WordPiece, WordLevel and Unigram models, not an independently named “char” model. BPE with a complete byte-level initial alphabet is one way to cover bytes; a WordLevel tokenizer is not automatically character tokenization. The original tokenizer.encode(text, sampling=True) is not this API's unigram sampling method. Use SentencePiece's documented sampling arguments above when that is the desired procedure.

# Optional reference: tokenizers v0.22.1; unexecuted in this review.
def train_hf_local(corpus_path, output_dir, vocab_size=8000):
    from pathlib import Path
    from tokenizers import Tokenizer,models,trainers,pre_tokenizers,decoders
    source,out = Path(corpus_path),Path(output_dir)
    if not source.is_file() or vocab_size < 300:
        raise ValueError('existing UTF-8 training file and sufficient budget required')
    out.mkdir(parents=True,exist_ok=True)
    bpe = Tokenizer(models.BPE(unk_token='<unk>'))
    bpe.pre_tokenizer = pre_tokenizers.ByteLevel(add_prefix_space=False)
    bpe.decoder = decoders.ByteLevel()
    bpe.train([str(source)],trainers.BpeTrainer(vocab_size=vocab_size,
        initial_alphabet=pre_tokenizers.ByteLevel.alphabet(),special_tokens=['<unk>']))
    uni = Tokenizer(models.Unigram())
    uni.pre_tokenizer = pre_tokenizers.Metaspace(replacement='▁',prepend_scheme='never')
    uni.decoder = decoders.Metaspace(replacement='▁',prepend_scheme='never')
    uni.train([str(source)],trainers.UnigramTrainer(vocab_size=vocab_size,
        special_tokens=['<unk>'],unk_token='<unk>'))
    outputs = {}
    for name,tok in [('bpe',bpe),('unigram',uni)]:
        target = out/(name+'.json')
        if target.exists():
            raise FileExistsError(target)
        tok.save(str(target)); restored = Tokenizer.from_file(str(target))
        probe = 'Hello  world! తెలుగు 🙂'
        ids = tok.encode(probe).ids
        assert restored.encode(probe).ids == ids
        outputs[name] = dict(ids=ids,decoded=tok.decode(ids,skip_special_tokens=False),
                             tokens=tok.encode(probe).tokens)
    return outputs

This HF comparison deliberately uses two different preprocessing families. To attribute a quality difference to the segmentation algorithm alone, align normalization, coverage, special IDs and pre-tokenization in a separate controlled experiment. The unigram HF example does not promise unknown-character byte fallback; inspect unknown rates and reject a corpus/model configuration that loses required information.

6 · Choosing a tokenizer and measuring its budget

Deterministic BPE and Viterbi unigram are both suitable for reproducible serving if every artifact and option is fixed. Unigram posterior sampling supplies principled alternative paths; BPE-dropout supplies an alternative stochastic segmentation procedure. Use augmentation only where training/evaluation policy expects it, and freeze deterministic inference behavior for cache keys and token budgeting.

A decision should start with checkpoint compatibility, then representative data, then algorithm experiments:

• Existing checkpoint: use its exact tokenizer/config/template. Matching vocabulary size is insufficient. Changing ID meaning makes embeddings refer to the wrong pieces; they do not suddenly become random arrays.
• New code model: test indentation, identifiers, operators, repeated whitespace and literal control spellings. BPE with a suitable pre-tokenizer is a candidate, not proof that unigram “does not respect syntax.” Neither algorithm parses code by itself.
• New multilingual model: stratify token counts and unknown rates by language/script and normalize by bytes, characters or a documented linguistic unit. “Words” is not a stable denominator for every language. Both algorithms can work; corpus balance and normalization can matter more than the label.
• Small model: Vd tied embedding parameters can dominate. Choose vocabulary size together with width, token budget and output-projection cost, not from another model's nominal vocabulary.

The original “0.75 tokens/word =1.3 tokens/word” inverted units. If a measured corpus has1.3 tokens/word, it has about.769 words/token. There is no verified universal tokens-per-language table. Tokenize the actual text before enforcing a window or pricing an API request; byte/character ratios are rough planning assumptions, not admission checks.

7 · Model landscape without invented motives

LLaMA1/2's SentencePiece BPE, Llama3's tiktoken-style BPE, GPT-2's visible-byte BPE and T5's SentencePiece pipeline are not interchangeable files. GPT-4-family encoding names such ascl100k_base ando200k_base identify tokenizer families; use the provider's exact model-to-encoding mapping rather than assume all GPT-4 variants share one. Mistral7B/Mixtral SentencePiece-era tokenizers differ from Tekken; Qwen and DeepSeek byte-BPE variants have their own digit/pre-tokenizer/special-ID conventions.

Gemma3's large SentencePiece tokenizer does not license importing a T5 probability model, a2048-wide embedding assumption or a claim of being permanently the largest vocabulary. The Gemma3 report specifically describes a SentencePiece tokenizer with split digits, preserved whitespace and byte-level encodings; it reports302M embedding and698M non-embedding parameters for the1B model. It does not establish the original assertion of a500M embedding table or prove unigram merely by naming SentencePiece. Record the actual model/config revision. Mistral NeMo's Tekken comparison is against the previous SentencePiece tokenizer for its reported30% language/code compression result; its comparison with Llama3 is separately reported across languages. A family table cannot establish why every designer made their choice.

TokenMonster is a separate ungreedy vocabulary/segmentation implementation with reported compression and LM experiments; inspect its mode and benchmark before claiming a neural LM training objective or universal advantage. Vocabulary-scaling research studies joint budget allocation, not a rule that a256k vocabulary is always too large for a small model.

Byte/latent alternatives: MEGABYTE uses a hierarchy of global patches and local byte processing to address longer raw-byte sequences. Byte Latent Transformer learns variable-size patches based on byte-level entropy and allocates latent computation to them. These still have a representation/segmentation mechanism; “no tokenizer” does not mean no boundaries or no Unicode issues. SSM byte models trade recurrence and state for attention's pair interactions. Longer byte sequences do not automatically imply a fixed4–5x cost, and there is no justified2028 prediction to teach as fact.

8 · Failure diagnosis and migration

When token IDs differ between training and fine-tuning, compare the entire pipeline in order: input serialization, Unicode normalization, whitespace policy, pre-tokenizer, vocabulary/ranks/probabilities, special insertion and chat template. Hash the files and compare probe IDs. Reloading a different tokenizer can error, or silently differ; AutoTokenizer alone is not a proof when remote revisions/configs changed. Prefer an explicit trusted local revision and disallow unintended remote custom code.

Special strings in user content need a clear treatment as ordinary text, rejected reserved syntax or trusted structure. Do not blindly strip them, and do not assume they always map to special IDs. Tokenizer structural isolation is only one layer of prompt-safety design.

Changing a vocabulary after pretraining requires remapping retained IDs, initializing new rows/output weights, deciding whether to tie them, adjusting optimizer state, and continuing training with evaluation of old and new tasks. Tokenizer changes can alter every prefix ID and therefore invalidate cached states; KV shape itself is controlled by attention architecture, not directly by vocabulary size. There is no universal1–2-point migration penalty or a single recipe guaranteed to preserve quality.

9 · Recall and worked answers

1. Unigram training loop? Seed candidate pieces; use marginal likelihood and soft posterior counts to optimize probabilities; estimate deletion costs; prune while preserving coverage; repeat. Viterbi is best-path inference, not the soft E-step. The toyab posterior supplies the explicit distinction.
2. BPE versus unigram? BPE learns ordered frequency-driven merges; unigram scores segmentations probabilistically. Both have deterministic inference options, and both have stochastic augmentation techniques. Code/multilingual quality requires matched experiments, not an algorithm stereotype.
3. What is metaspace? ▁ represents whitespace in the model's normalized stream. It supports reversible segmentation of that stream, but default normalization may have removed raw distinctions. Inspect actual processor decode rather than replacing glyphs blindly.
4. When choose each? Match an existing checkpoint first. For new models, use BPE for an auditable ranked-merge baseline and unigram when a probabilistic lattice/sampling objective is useful; test either on the target domains. A desire for deterministic serving does not disqualify unigram.
5. Why language token-count differences? Vocabulary frequency and training distribution, Unicode byte lengths, pre-tokenization and normalization interact. Larger/more balanced vocabularies may help but do not guarantee a fixed script ratio or lower overall serving cost.
6. Why not change the tokenizer casually? IDs index learned rows and templates define structure. Save/hash model and tokenizer together, compare awkward probes after reload and treat migration as retraining work.
7. Stretch comparison solution: train on the same permitted train split with recorded policies; tokenize a fixed held-out prose/code/multilingual suite; report tokens, bytes/token, unknowns, raw/normalized round trips and timing. Sample five unigram paths with the supported SentencePiece API and observe that alternatives occur only where the learned vocabulary permits them. No fixed1.25 versus1.3 tokens/word result is promised.
8. Three-sentence answer to “Why Llama SentencePiece instead of BPE?” The question confuses a toolkit with an algorithm. LLaMA1/2 use BPE through SentencePiece, while Llama3 uses a different byte-BPE pipeline. Use the model's exact artifact, because normalization, boundaries and IDs matter as much as the algorithm name.

Tomorrow reconstruct the soft-count calculation; after a week inspect a normalization counterexample without using a generic “lossless” label.

Sources and optional navigation

SentencePiece v0.2.1 README, normalizer/trainer proto, Python API, Kudo2018 unigram paper, BPE-dropout, HF tokenizers0.22.1, LLaMA, Llama3, MEGABYTE, BLT, vocabulary scaling. Optional inherited resources: Karpathy, unigram video, SentencePiece paper. No library-specific run or tokenizer-training benchmark is claimed here.

Course map · Previous DL044 · Next DL046.