Tokenization

BPE was invented for compression in 1994 (Gage), then re-invented for NMT by Sennrich, Haddow & Birch in 2015. The algorithm:

# Train BPE from a corpus
def train_bpe(corpus, vocab_size):
    # 1. Start with character-level vocab
    vocab = set(''.join(corpus))
    # 2. Count pairs in corpus
    while len(vocab) < vocab_size:
        pairs = count_adjacent_pairs(corpus)
        best = max(pairs, key=pairs.get)        # most common pair
        corpus = merge_pair(corpus, best)       # replace pair → token
        vocab.add(best[0] + best[1])
    return vocab

# Example trace on "low, lower, newest, widest"
# l,o,w  l,o,w,e,r  n,e,w,e,s,t  w,i,d,e,s,t
# merge "e,s" → "es"   (most common pair)
# l,o,w  l,o,w,e,r  n,e,w,es,t  w,i,d,es,t
# merge "es,t" → "est"
# l,o,w  l,o,w,e,r  n,e,w,est   w,i,d,est

Key properties: deterministic, no <UNK> needed if you start from bytes, vocabulary is a function of training corpus frequency. The downside: the merge sequence is greedy and locally optimal — there's no global re-segmentation.

Standard BPE has a problem: rare Unicode characters explode the base vocab, or get mapped to <UNK>. GPT-2 (Radford 2019) fixed this by working on raw UTF-8 bytes:

# Every byte 0–255 is a valid token. No OOV possible.
# But we need to remap "weird" bytes (whitespace, control chars)
# to printable Unicode for the merge table to be readable.

def bytes_to_unicode():
    bs = list(range(33, 127)) + list(range(161, 173)) + list(range(174, 256))
    cs = bs[:]
    n = 0
    for b in range(256):
        if b not in bs:
            bs.append(b)
            cs.append(256 + n)
            n += 1
    return dict(zip(bs, [chr(c) for c in cs]))

# Now BPE merges happen over this remapped space.
# At decode time, every byte is recoverable.

This is what tiktoken implements (in Rust, fast). It's also what HuggingFace's GPT2Tokenizer does. The 256-byte base means any byte sequence is encodable, including invalid UTF-8 — which matters for code, binary, and adversarial inputs.

WordPiece (Schuster & Nakajima 2012, used by BERT) picks the merge that maximizes the language-model likelihood of the corpus:

# BPE merge criterion:        argmax  count(a, b)
# WordPiece merge criterion:  argmax  count(a, b) / (count(a) * count(b))
#                            ↑ pointwise mutual information

# Practical effect: WordPiece prefers merges where a and b
# co-occur more than chance, even if absolute count is lower.

WordPiece also marks subwords with ## prefix: "playing" → ["play", "##ing"]. This makes detokenization unambiguous but adds a special token to the vocab. BERT used a 30k-token WordPiece vocab. WordPiece feels old now — every modern LLM uses BPE or Unigram instead.

SentencePiece (Kudo 2018) is a library; Unigram is its preferred algorithm. It works top-down:

# 1. Start with a huge candidate vocab (e.g., 1M substrings)
# 2. Assign each token a probability via EM
# 3. Compute loss if we drop each token from vocab
# 4. Drop the bottom 10% (lowest contribution to likelihood)
# 5. Re-run EM, repeat until vocab size = target

# At inference, tokenize via Viterbi over the unigram LM:
#   "lowest" could be ["low", "est"] or ["lo", "west"] or ["l", "owest"]
#   Pick the path with max product of token probabilities.

Unigram is not greedy — it considers all segmentations and picks the most likely. This produces shorter, more linguistically reasonable tokens, especially for non-English. It also enables subword regularization (sample alternative segmentations during training) for free.

SentencePiece treats whitespace as a special character (▁), so "Hello world" becomes "▁Hello▁world" and there's no separate pre-tokenization step. Llama-1, Llama-2, T5, mBART all use SentencePiece+Unigram.

import tiktoken

# OpenAI uses different encodings per model family
enc = tiktoken.encoding_for_model("gpt-4o")     # o200k_base
ids = enc.encode("Hello, world!")
# [13225, 11, 2375, 0]
text = enc.decode(ids)
# "Hello, world!"

# Available encodings:
# - cl100k_base    GPT-3.5, GPT-4 (100,256 tokens)
# - o200k_base     GPT-4o, o1 (200,019 tokens)
# - p50k_base      Codex, text-davinci (50,281 tokens)
# - r50k_base      GPT-3 (50,257 tokens)

The Rust core uses a precomputed merge table and a regex split (via fancy-regex) for pre-tokenization. The pre-tokenizer regex for cl100k_base is famous — it splits on contractions, numbers, whitespace runs, and punctuation in a specific order that took empirical tuning.

The embedding matrix (and tied output head) scale linearly with vocab size. For a 4096-dim model, a 200k vocab burns ~820M params on the embedding alone. But the savings in token count (~10% shorter sequences) pay for it during inference, since the per-token cost dwarfs the one-time embedding lookup.

A long list of LLM bugs trace to tokenization:

• Reverse-string fails: "lollipop" reversed → wrong, because the model sees three tokens, not eight characters.
• Counting letters fails: "How many R's in strawberry?" → 2, because "berry" is one token.
• Glitch tokens: SolidGoldMagikarp existed in the BPE vocab but was almost absent from training data; the model produced unhinged output when prompted with it.
• Code indentation issues: a single space and four spaces are different tokens, so the model has to learn each indentation level separately.
• Multilingual fairness: the same paragraph in Burmese costs ~8× the tokens of English. Same API price, less context, slower output.
• Cross-tokenizer training: embeddings don't transfer between vocabularies, so distillation requires re-training the student tokenizer.

Andrej Karpathy's "Let's build the GPT Tokenizer" video crystallized the term — tokenization is the boring layer that breaks in surprising ways.