Tokenization — BPE, WordPiece, SentencePiece

Why this session exists

A tokenizer defines the discrete interface between text and model weights. Sequence length affects context budgets, memory and cost; ID meanings affect correctness. Tokenization is not the sole explanation of spelling errors or hallucinations, and fine-tuning explicitly changes model weights. We will train a reversible byte-BPE toy, hand-count a word-based BPE example, distinguish WordPiece from unigram/SentencePiece, and test Unicode, whitespace, special tokens and vocabulary compatibility.

Prerequisites

S104 embedding rows, S103 sequence inputs, Python strings/bytes, Unicode code points versus grapheme clusters, and dictionaries. A tokenizer produces IDs; an embedding layer supplies vector width.

(a) Intuition · 5 min

A bag of reusable Lego pieces is a better metaphor than a dictionary of meanings. Frequent substrings can become one piece, while other strings require several. The pieces depend on normalization, corpus, base alphabet and training algorithm. A 'word' need not correspond to one piece; an emoji can contain multiple code points, and a code point can span multiple UTF-8 bytes. Do not attach a universal token count to a string without naming the exact encoder version and settings.

Why we don't use characters or words

A character vocabulary is not inherently 256 entries—that is the byte alphabet. WordPiece can emit [UNK]; SentencePiece may also use unknowns without adequate character coverage or byte fallback. Subword therefore does not mean 'no OOV ever'. A byte-complete encoder can represent every valid UTF-8 input byte sequence, but applications can still reject special-token text, invalid IDs, oversized inputs or malformed surrogate strings.

A short history of how we chop text

BPE began as compression, then Sennrich et al. (2015/2016) adapted it to subword translation. WordPiece predates BERT; GNMT describes a wordpiece model. SentencePiece (2018) is a toolkit supporting BPE and unigram, not a synonym for one algorithm or 'raw Unicode bytes'. GPT-2 was released in 2019 and used byte-level BPE. LLaMA-1 used SentencePiece BPE with byte fallback; the LLaMA-2 report says it uses the same tokenizer, not a newly retrained code tokenizer. Vendor/model families change: inspect the actual tokenizer artifacts rather than guess from a model name.

The BPE merge algorithm

Each replacement reduces length by one. Pair counts with overlaps need care: aaa has two adjacent aa pairs but only one can be merged in a left-to-right non-overlapping pass. Thus raw pair frequency is not always exactly the realized one-step compression gain. BPE is greedy, not a proof of globally optimal vocabulary. Pre-tokenization can forbid cross-boundary merges; an end-of-word marker does not magically enforce boundaries if the implementation trains one concatenated stream.

BPE by hand on a tiny corpus

Use word frequencies low:5, lower:2, newest:3, widest:2, with separate character sequences and </w> markers. Initially (l,o) and (o,w) each occur 7 times. (e,s), (s,t) and (t,</w>) each occur 5, not 3, because both newest and widest contribute. Choose (l,o) among the tied leaders, then (lo,w) at 7. The next count-5 candidates include (low,</w>), (e,s), (s,t) and (t,</w>); selecting whole low is one tie policy, not a uniquely forced step. Save the policy and ranks so training and encoding are reproducible. With such a tiny corpus training can stop before a requested large vocabulary.

BPE vs WordPiece vs SentencePiece

BPE inference: apply learned merge priority to base pieces within the allowed segments. BERT WordPiece inference: the primary tokenizer source uses greedy longest-match-first vocabulary lookup, with ## for continuation pieces, and falls back to [UNK] when segmentation fails or a word exceeds its length limit. It does not replay BPE merge ranks. Likelihood-based descriptions and pair-frequency-ratio heuristics for WordPiece training should not be presented as a fully reproduced historical Google training algorithm.

Unigram: a segmentation $z=(z_1,\ldots,z_m)$ has score $\prod_i p(z_i)$, equivalently sum of log probabilities. Dynamic programming can find a best path over a fixed vocabulary; training estimates probabilities and heuristically prunes pieces, preserving coverage. For ab, pieces with $p(a)=p(b)=0.3$ and $p(ab)=0.4$ give scores 0.09 versus 0.4, so ab wins. Marginal likelihood sums over segmentations rather than choosing only one. Sampling segmentations is a regularization option, not obligatory nondeterminism at inference.

SentencePiece supports both approaches, operates on raw text without a required language-specific word splitter, and normally uses NFKC-based normalization and an explicit whitespace marker ▁. Normalization or whitespace options can prevent exact original-text round trips. Output markers are clues, not enough to identify an algorithm: a SentencePiece BPE and unigram model can display the same whitespace symbol.

The four moving parts every tokenizer has

1. Normalization: define Unicode/case/accent/whitespace transformations. BERT uncased processing lowercases and strips accents; not every tokenizer does.
2. Pre-tokenization: decides which spans may merge. Regex choices for letters, numbers, punctuation and spaces affect both coverage and compression.
3. Model/vocabulary: BPE ranks, WordPiece pieces or unigram scores map spans to IDs.
4. Post-processing and decoding: add the particular model's special-token/template structure and invert the representation under its normalization contract.

These are conceptual stages, not necessarily four separately configurable objects. Leading spaces may change tokens; stripping them to make a test pass changes the input. BOS/EOS/padding IDs and chat templates belong to a model/version; 'LLaMA' does not name one universal template. Content containing a control-token spelling must have a deliberate literal-versus-special policy.

How tokens map to model input

Range checking catches an ID beyond the table but cannot catch a permutation of valid IDs. The latter silently selects the wrong learned rows. Vocabulary size also costs parameters: an untied input/output pair uses roughly $2Vd$ weights; tying shares them. Output logits can be expensive, so sequence length is not the only compute term. Dense attention's pairwise arithmetic grows quadratically with length, whereas projections and many other layers grow linearly; incremental cached decoding has a different cost profile.

Reuse, extend or replace the codebook

Reuse a pretrained tokenizer unless a measured benefit and a controlled adaptation plan justify change. Adding tokens while preserving old IDs requires compatible input and output tables, tied-weight handling and training the new rows; initialization may be random or use a library's other policy. Replacing all IDs makes direct checkpoint use incompatible, but learned remapping/adaptation is possible—it does not logically require discarding every pretrained layer. For a hosted model you generally cannot change its tokenizer.

Measure tokens per record, bytes and, where meaningful, whitespace-delimited word. Include prose, code, JSON, identifiers, emoji and target scripts. No fixed English/Hindi token ratio or current API price is asserted. Simplifying payloads may save tokens but must preserve needed semantics, stable IDs and auditability. Character reasoning can be harder when characters are hidden inside pieces, yet models can learn spelling structure; the tokenizer is not a proof of inability.

(c) Hands-on · 25 min

This standalone byte-BPE implementation trains on inline text, stores integer IDs and merge ranks, and decodes exactly. It preserves case and whitespace, unlike the earlier lowercase/regex toy that claimed a decoder without implementing one. No tiktoken vocabulary, model or external dataset is downloaded. The toy has no commercial pre-tokenizer or special-token template; comparisons printed below are local toy compression, not GPT measurements.

from collections import Counter
import json,hashlib
 
def merge(ids,pair,new):
    result=[];i=0
    while i<len(ids):
        if i+1<len(ids) and (ids[i],ids[i+1])==pair:result.append(new);i+=2
        else:result.append(ids[i]);i+=1
    return result
 
class ByteBPE:
    def __init__(self):
        self.vocab={i:bytes([i]) for i in range(256)};self.rules=[]
    def train(self,texts,target=280):
        if target<256:raise ValueError('byte-complete vocabulary needs 256 entries')
        if self.rules:raise ValueError('train a fresh model')
        streams=[list(t.encode('utf-8')) for t in texts]
        while len(self.vocab)<target:
            counts=Counter(pair for ids in streams for pair in zip(ids,ids[1:]))
            if not counts:break
            pair=min(counts,key=lambda p:(-counts[p],p)) # stable integer tie break
            if counts[pair]<2:break
            new=len(self.vocab);self.vocab[new]=self.vocab[pair[0]]+self.vocab[pair[1]]
            self.rules.append((pair,new));streams=[merge(ids,pair,new) for ids in streams]
        return self
    def encode(self,text):
        ids=list(text.encode('utf-8'))
        for pair,new in self.rules:ids=merge(ids,pair,new)
        return ids
    def decode(self,ids):
        if any(type(i) is not int or i not in self.vocab for i in ids):raise ValueError('invalid ID')
        return b''.join(self.vocab[i] for i in ids).decode('utf-8',errors='strict')
    def fingerprint(self):
        return hashlib.sha256(json.dumps(self.rules,separators=(',',':')).encode()).hexdigest()
 
training=['low low lower newest widest\n'*8,'def run(x):\n    return x + 1\n'*6]
bpe=ByteBPE().train(training,290)
assert bpe.fingerprint()==ByteBPE().train(training,290).fingerprint()
samples=['','hello',' hello','  hello\n','supercalifragilistic','AAAAAAAAAA',
 '1234567890','print(hello_world)','🎉🎊🎈','नमस्ते दुनिया','తెలుగు',
 'é','e\u0301','<|endoftext|>','{"id":"9f1c2d3e-4b5a"}']
for s in samples:
    ids=bpe.encode(s);assert bpe.decode(ids)==s
    assert all(0<=i<len(bpe.vocab) for i in ids)
    words=len(s.split());ratio=len(ids)/words if words else None
    print(repr(s),'bytes',len(s.encode()),'tokens',len(ids),'tokens/space-word',ratio)
assert bpe.encode(' hello')!=bpe.encode('hello')
assert bpe.encode('é')!=bpe.encode('e\u0301') # no normalization in THIS toy
# Overlapping pair negative control: two counts do not mean two replacements.
assert Counter(zip(b'aaa',b'aaa'[1:]))[(97,97)]==2
assert merge([97,97,97],(97,97),256)==[256,97]
try:bpe.decode([len(bpe.vocab)]);raise AssertionError('bad ID accepted')
except ValueError:pass
# Dropping whitespace/case is a genuinely lossy alternative, not a decoder bug.
s=' The  CAT\n';assert ' '.join(s.lower().split())!=s
# Hand-count word BPE independently of the byte-stream trainer.
words={'low':5,'lower':2,'newest':3,'widest':2}
counts=Counter()
for word,freq in words.items():
    pieces=list(word)+['</w>']
    for p in zip(pieces,pieces[1:]):counts[p]+=freq
assert counts[('l','o')]==7 and counts[('e','s')]==5 and counts[('t','</w>')]==5
# Fixed-vocabulary unigram Viterbi objective: ab beats a,b under these probabilities.
import math
p={'a':.3,'b':.3,'ab':.4}
assert math.log(p['ab'])>math.log(p['a'])+math.log(p['b'])
print('roundtrip, unknown-ID, overlap, word-count and unigram checks passed',bpe.fingerprint())

Anatomy of the script

Base byte IDs make held-out scripts representable; they do not make them efficiently compressed. Training treats each supplied string as a separate stream, so merges never cross records but may cross spaces within a record. Encoding applies saved rules, never learns from test text. Pair replacement is left-to-right/non-overlapping; recording constituent IDs prevents ambiguity in concatenated piece spellings. The fingerprint binds ordered rules under the declared fixed byte alphabet and identity normalization. A production artifact also hashes every normalizer, pre-tokenizer, special-token and template file.

Decoding joins bytes before UTF-8 decoding. Decoding each token independently may fail when a token ends mid-code-point; strict decoding also correctly rejects an arbitrary incomplete byte sequence. Empty text has zero tokens and no word-ratio denominator. The test's control-token-looking string is ordinary text because this toy defines no specials; that does not make it a safe drop-in chat tokenizer.

For a provisioned real encoder, pin package and encoding artifact hashes, encode the same unmodified samples, and report counts and exact round-trip policy. cl100k_base and o200k_base are distinct encodings in tiktoken 0.12.0's tagged registry, not synonyms for every GPT model. Loading their mergeable ranks may fetch data; that comparison was deliberately not run. Use actual serialized chat-template overhead when estimating a model's context budget.

(d) Production reality · 15 min

Multilingual budgets: measure distributions by language/script and payload type, not a claimed permanent English tax. Training balance, vocabulary, segmentation and model behavior all matter; translating a request to estimate a 'same content' ratio introduces another variable. Pricing also distinguishes input, output, cache and other service-specific units; no fabricated dollar example is retained.

Tokenizer upgrades: the LLaMA-2 report explicitly retains LLaMA-1's tokenizer. A vocabulary increase in another model cannot imply an equal percentage latency reduction: projections, output vocabulary work, cache and hardware also change. Benchmark the complete pipeline with the matching model, not only shorter token sequences.

Template bugs: verify a golden serialized example, exact BOS/EOS count, padding/attention masks and target shift. A missing BERT classification token changes the readout input but does not logically force every prediction to garbage. There is no established 'thousands of tutorials fixed overnight' incident here. Duplicating specials is as important to catch as omitting them.

Where this shows up in the rest of the plan

Token count feeds attention cost and RAG chunk budgets. Masked-language modeling masks IDs under a particular vocabulary. Fine-tuning must maintain or deliberately adapt ID/table compatibility; it does not mean pretrained weights cannot change. Pre-tokenizer regex and Unicode choices are part of the model artifact, not cosmetic text cleanup.

(e) Recall + stretch · 10 min

1. Why subwords? A tunable vocabulary/length tradeoff, with coverage only when the base/fallback supports it.
2. BPE in three steps? Count current adjacent pairs; merge a chosen pair non-overlapping and save rank; repeat, then encode with fixed rules.
3. BPE versus WordPiece? Ranked merges versus longest vocabulary matching at inference; distinguish a training heuristic from that verified decoder.
4. Byte BPE? Start with 256 bytes; concatenate byte pieces before decoding valid text.
5. Hindi cost? Measure the exact encoder on actual requests; no fixed multiplier follows from a script name.
6. Wrong template? A valid-shaped tensor can carry the wrong control semantics; test golden IDs and readout positions.
7. Add a token? Preserve old IDs, resize compatible input/output tables, handle tying and train/evaluate the new representations.
8. Spelling? Subword boundaries obscure character structure, but are not a complete explanation of model failures or a proof of impossibility.
9. Byte fallback? An explicit unknown-symbol-to-UTF-8-byte policy; different from an entire byte-level BPE base and not a no-crash guarantee.
10. Code tokenizer? Preserve whitespace/case, evaluate identifiers/operators/digits and multilingual comments, tune vocabulary and pre-split constraints on training data. No arbitrary 16K vocabulary or 0–999 digit rule is automatically best; compare compression and downstream loss in compatible units.

Explain-out-loud test

Recount the tiny BPE corpus after two merges, demonstrate why aaa defeats the naive gain count, and diagnose a valid-range but permuted-vocabulary bug.

What comes next

Attention intuition operates on the vectors indexed by these IDs. Learning-plan hub.

Primary references

• BPE for translation, unigram subword regularization, SentencePiece.
• SentencePiece 0.2.1 README, BERT tokenizer source, tiktoken 0.12 registry: source-reviewed; vendor token-count benchmark not run.