The Tokenizer Is a Stein

A tokenizer's vocabulary is sometimes called a Stein — not after anyone in particular, but as a reminder that it is a specific, arbitrary object. It is not a dictionary. It is a list of frequent strings that a merge process produced from a particular corpus, at a particular time, with a particular budget.

This matters because the vocabulary is load-bearing. The model is trained on tokens, and the tokenization decides what the model sees. The vocabulary is not a neutral interface. It is a prior.

This note starts with a ten-line BPE implementation, derives the vocabulary that falls out of it, then shows the fertility gap as a direct consequence of the merge budget and the corpus skew.

The naïve version: split on the word boundary#

The first attempt at a tokenization is whitespace. Words become tokens, and the vocabulary is the set of distinct words in the corpus:

def split_whitespace(text):
    return text.lower().split()
 
def build_vocab(texts):
    vocab = set()
    for text in texts:
        vocab.update(split_whitespace(text))
    return sorted(vocab)
 
corpus = ["The cat sat on the mat", "The dog sat on the rug"]
vocab = build_vocab(corpus)
print(vocab)

This works for a corpus where every word is known in advance. It fails the moment the input contains a word outside the training set, which happens continuously in real text. A language model cannot embed a word it has never seen, so the vocabulary must include a mechanism for novel strings.

Character-level tokenization is the opposite extreme: every character is a token, and any string can be represented. The cost is length. A model with a finite context window sees fewer words for the same token budget, and the statistical patterns the model learns are harder to find, because a word's identity is spread across several positions.

First principles: byte-pair encoding#

Byte-pair encoding sits between the extremes. Start with the 256 possible bytes, scan a corpus, count adjacent pairs, merge the most frequent pair into a new symbol, and repeat. The merges are greedy and frequency-driven, and the most frequent strings in the corpus acquire the shortest representations.

from collections import Counter
 
def get_pair_stats(word_counts):
    stats = Counter()
    for word, count in word_counts.items():
        symbols = list(word)
        for a, b in zip(symbols, symbols[1:]):
            stats[(a, b)] += count
    return stats
 
def merge_pair(word_counts, pair):
    first, second = pair
    merged = first + second
    new_counts = Counter()
    for word, count in word_counts.items():
        symbols = list(word)
        merged_symbols = []
        i = 0
        while i < len(symbols):
            if (i < len(symbols) - 1 and symbols[i] == first
                    and symbols[i + 1] == second):
                merged_symbols.append(merged)
                i += 2
            else:
                merged_symbols.append(symbols[i])
                i += 1
        new_counts["".join(merged_symbols)] = count
    return new_counts
 
def train_bpe(corpus, num_merges):
    word_counts = Counter()
    for line in corpus:
        for word in line.split():
            word_counts[word] += 1
    merges = []
    for _ in range(num_merges):
        stats = get_pair_stats(word_counts)
        if not stats:
            break
        best = max(stats, key=stats.get)
        merges.append(best)
        word_counts = merge_pair(word_counts, best)
    return merges
 
merges = train_bpe(["the cat the dog"], 3)
print(merges)

Each merge creates one new vocabulary entry, so the vocabulary size grows by exactly the number of merges. A vocabulary budget of $V$ entries means $V - 256$ merges, and merge number $k$ is always the $k$-th most useful pair in the corpus at the time it was chosen.

Bottleneck one: the budget runs out#

The merge order follows corpus frequency, so the survivors after a budget cut are the most frequent strings. That has three consequences.

English is cheap. The most frequent strings in English corpora are common words, sub-words, and morphemes. A prevalent English word is often one token. A common English phrase is a few.

Other languages are expensive. A language that appears less frequently in the corpus receives fewer merges. Its strings are represented as smaller pieces, sometimes down to individual bytes. The same budget buys less text.

The vocabulary is not linguistic. The merges are driven by frequency, not by morphology. A frequent non-morpheme string will be learned. A rare true morpheme may not. The tokens are units of compression, not units of meaning.

The encoder that applies the learned merges is a greedy scan:

def encode(word, merges):
    symbols = list(word)
    for first, second in merges:
        merged_symbols = []
        i = 0
        while i < len(symbols):
            if (i < len(symbols) - 1 and symbols[i] == first
                    and symbols[i + 1] == second):
                merged_symbols.append(first + second)
                i += 2
            else:
                merged_symbols.append(symbols[i])
                i += 1
        symbols = merged_symbols
    return symbols
 
print(encode("concatenation", merges))
print(encode("tokenizer", merges))

Training chooses merges; encoding applies them. Both are greedy, and neither inspects what the resulting pieces mean.

Bottleneck two: fertility#

The standard measure is fertility: tokens per word. For English, typical values are around 1.2 to 1.5. For a lower-resource language written in a different script, fertility can be 2, 3, or higher. For byte-level fallbacks, it can be an order of magnitude higher.

The merge process makes the gap derivable rather than surprising. A word that appears in the corpus often enough to have its sub-strings merged into whole tokens costs one or two tokens to encode. A word that appears rarely is encoded as the smaller pieces the merges did produce, and a word whose characters never participated in any merge is encoded byte by byte.

def fertility(text, encode_fn):
    words = text.split()
    if not words:
        return 0.0
    total_tokens = sum(len(encode_fn(w)) for w in words)
    return total_tokens / len(words)
 
def bytes_per_token(text, encode_fn):
    tokens = len(encode_fn(text))
    return len(text.encode("utf-8")) / max(1, tokens)

This is not a marginal difference. Fertility determines how much text fits in a context window, how expensive an inference call is, and how many examples fit in a training batch. It is the mechanism by which corpus frequency becomes a per-language cost, because the merges that make a language cheap were learned from the corpus that contained that language.

Bottleneck three: the corpus is skewed#

The vocabulary is built from the training corpus. The training corpus reflects availability. Availability reflects the internet, and the internet is skewed. English is overrepresented. Code is overrepresented. Western languages are overrepresented. The vocabulary inherits the skew and encodes it as cost.

A language that is underrepresented in the corpus is punished twice. It has less data for training, and the data it has costs more to process. The model's totals — parameters, compute, context — are the same for all languages. The per-word cost is not.

The skew enters at a second point as well. Byte-level BPE is universal in coverage — any byte sequence can be represented — but universality is not efficiency. Scripts whose bytes are common in the corpus begin with many merges already in place, and scripts whose bytes are rare start from the floor. UTF-8 encodes every non-ASCII character in multiple bytes, so the same word in Devanagari or Arabic costs more tokens than the same word in Latin before frequency enters the picture at all.

Fix attempt one: per-language vocabularies#

A tokenizer trained on Nepali will have Nepali merges, and it will cost less per Nepali word. The problem is that a model is trained on one vocabulary, and multilingual models must share it. Splitting the vocabulary by language is possible at the system level but not at the model level.

def compare_languages(samples, encode_fn):
    report = {}
    for language, text in samples.items():
        report[language] = {
            "fertility": fertility(text, encode_fn),
            "bytes_per_token": bytes_per_token(text, encode_fn),
        }
    return report

Measuring the gap costs one function call per language, and no multilingual model should ship without the table.

Fix attempt two: increase the vocabulary size#

More merges means more frequent strings are learned. This helps low-resource languages, but the marginal benefit declines, and the vocabulary size has its own costs — embedding matrix, softmax, and the model's ability to learn rare tokens.

Each additional merge is the single most frequent remaining pair, so the benefit per merge falls off. The early merges are the highest-frequency pairs and save the most tokens; the late merges save progressively less. The relationship is close to Zipfian over the pair distribution, and the budget that looks generous in absolute terms is quickly spent on pairs that occur rarely enough to matter little.

def merge_savings(corpus, num_merges):
    """Cumulative tokens saved per merge, in corpus order (approximation)."""
    word_counts = Counter(w for line in corpus for w in line.split())
    savings = []
    current = word_counts
    for _ in range(num_merges):
        stats = get_pair_stats(current)
        if not stats:
            break
        best = max(stats, key=stats.get)
        savings.append(stats[best])
        current = merge_pair(current, best)
    return savings
 
savings = merge_savings(["token tokenizer tokens tokenized"], 5)
print(savings)

The first entries in the list are large; the last entries are small. That shape is the diminishing return, and it is why doubling the vocabulary does not halve the fertility gap.

The cost side is concrete. A vocabulary of size $V$ with model dimension $d$ requires an embedding matrix of $V \times d$ parameters, and the output softmax computes $V$ logits per generated token. Both scale linearly in $V$, and the trained embeddings for the rare tail of the vocabulary receive few updates, so the entries with the most vocabulary budget spent on them carry the least training signal.

def embedding_bytes(vocab_size, dim, bytes_per=4):
    return vocab_size * dim * bytes_per / 1e9
 
for v in (32000, 50000, 100000, 256000):
    print(v, f"{embedding_bytes(v, 4096):.2f} GB of embedding")

Fix attempt three: train on more data#

The most direct fix is a corpus with more of the underrepresented language, because the merges follow the frequencies wherever they point. The same mechanism that makes English cheap makes any sufficiently represented language cheap.

The problem is that gathering the corpus is slow, and the model must be retrained. A vocabulary learned from one corpus is frozen into the model trained on it, and changing the vocabulary means changing the embedding matrix, the softmax, and every token the model ever learned. The Stein persists because the cost of replacing it is a new model.

Bottleneck four: the Stein is load-bearing#

The tokenization decides what the model can easily see. A concept that exists as a single token gives the model one embedding to learn and one position to attend from; the same concept split into four tokens requires the model to assemble the meaning across positions, and the assembly is learned rather than guaranteed.

def token_count(text, encode_fn):
    """Tokens for the whole span, not words."""
    return len(encode_fn(text))
 
# A concept that is a single token in one language, four in another.
print("English:", token_count("photosynthesis", encode_en))
print("Nepali:", token_count("प्रकाशसंश्लेषण", encode_ne))

Scripts and languages whose common words are single tokens hand the model shorter dependency paths. Languages whose words fragment into bytes hand it longer ones, and the extra positions are compute the model must spend learning composition that another language gets for free.

What to measure#

The checklist for any tokenizer, before a model is trained on it:

def tokenizer_report(texts_by_language, encode_fn):
    rows = []
    for language, text in texts_by_language.items():
        rows.append((language, fertility(text, encode_fn),
                     bytes_per_token(text, encode_fn)))
    rows.sort(key=lambda r: -r[1])
    return rows
 
def context_capacity(context_tokens, fert):
    """Words of text that fit in the context at this fertility."""
    return context_tokens / fert
 
for language, fert, bpt in tokenizer_report(samples, encode_fn):
    words = context_capacity(8192, fert)
    print(f"{language}: fertility {fert:.2f}, "
          f"{words:.0f} words in an 8k context")

• Report fertility by language, always. A model that is cheaper for English than for Urdu is not equally good at both, and the score should not pretend it is.
• Track bytes per token alongside fertility. Fertility measures words; cost is paid per token, and the two diverge across scripts.
• Measure fertility on held-out text, not on the training corpus. The tokenizer was fitted to the training distribution, and the gap on new text is the number that matters in deployment.
• Check the byte-fallback rate. A high rate of single-byte tokens means the language was nearly absent from the merge corpus, and increasing the vocabulary will not fix it without more data.
• Verify that privacy-sensitive deployment respects the vocabulary boundary. A word split into bytes across tokens can leak information that a whole-word token would not, and the tokenization is part of the privacy surface.

The Stein does not know what a morpheme is. It knows what was frequent. That is the whole design, and it is also the limitation.