Tokenization & Vocabulary Design

Let the vocabulary be a set of strings (or byte sequences) $\mathcal V$. A tokenizer maps an input string $x$ into a sequence of tokens (where $n$ is the token count):

BPE and unigram tokenization search in different ways

BPE (Sennrich et al., 2016) learns vocabulary entries by merging frequent adjacent symbols. Following Kudo's unigram-language-model formulation, unigram tokenization instead scores candidate segmentations with token probabilities $p(t)$. For the fixed vocabulary $\mathcal V$, these form a normalized distribution: $p(t)\ge 0$ and $\sum_{t\in\mathcal V}p(t)=1$. In the display below, the left rule is one BPE merge step (fuse the most frequent adjacent pair $a,b$ into a new symbol $ab$); the right is the unigram choice, the segmentation of $x$ with the highest total log-probability:

The unigram path is found by dynamic programming over string positions (the Viterbi algorithm). The BPE merges are learned greedily, once, and then replayed in order as fixed rules on every new text.

Vocabulary size affects parameter count

If embeddings and output logits both use a $|\mathcal V|\times d$ matrix, then token-related parameters scale like:

If the input and output share one matrix (tied embeddings), this halves to $|\mathcal V|\,d$. The tokenizer is not just preprocessing: it sets part of the model's size, the length of every sequence, and which strings the model sees as one thing.

Both algorithms in plain Python, standard library only. learn_bpe_merges counts pairs inside words, weighted by how often each word occurs; unigram_map finds the most probable segmentation of one string.

from collections import Counter
import math

def learn_bpe_merges(corpus, num_merges=3):
    vocab = {tuple(word): freq for word, freq in corpus.items()}
    merges = []
    for _ in range(num_merges):
        counts = Counter()
        for symbols, freq in vocab.items():
            for pair in zip(symbols, symbols[1:]):
                counts[pair] += freq
        if not counts:
            break
        best = max(counts, key=counts.get)
        merges.append(best)
        merged_vocab = {}
        for symbols, freq in vocab.items():
            out, i = [], 0
            while i < len(symbols):
                if i + 1 < len(symbols) and (symbols[i], symbols[i + 1]) == best:
                    out.append(symbols[i] + symbols[i + 1])
                    i += 2
                else:
                    out.append(symbols[i])
                    i += 1
            merged_vocab[tuple(out)] = freq
        vocab = merged_vocab
    return merges, vocab

def unigram_map(x, tok_logp):
    n, NEG = len(x), -1e30
    dp, back = [NEG] * (n + 1), [None] * (n + 1)
    dp[0] = 0.0
    buckets = {}
    for tok, lp in tok_logp.items():
        buckets.setdefault(tok[0], []).append((tok, lp))
    for i in range(n):
        if dp[i] <= NEG / 2:
            continue
        for tok, lp in buckets.get(x[i], []):
            if x.startswith(tok, i):
                j, s = i + len(tok), dp[i] + lp
                if s > dp[j]:
                    dp[j], back[j] = s, (i, tok)
    if back[n] is None:
        return None
    out, j = [], n
    while j > 0:
        i, tok = back[j]
        out.append(tok)
        j = i
    return out[::-1], dp[n]

merges, vocab = learn_bpe_merges({"low": 5, "lower": 2, "new": 6, "newer": 3}, num_merges=4)
print("bpe merges:", merges)
print("bpe vocab:", vocab)

raw_weights = {
    "the": 0.08, "there": 0.02, "re": 0.05, "th": 0.06,
    "e": 0.07, "r": 0.03, "t": 0.02, "h": 0.02,
}
normalizer = sum(raw_weights.values())
probs = {t: weight / normalizer for t, weight in raw_weights.items()}
assert all(p > 0.0 for p in probs.values())
assert abs(sum(probs.values()) - 1.0) < 1e-12
tok_logp = {t: math.log(p) for t, p in probs.items()}
x = "there"
res = unigram_map(x, tok_logp)
assert res is not None, "No valid segmentation"
seg, score = res
print("x:", x)
print("raw-weight normalizer:", round(normalizer, 3))
print("probability sum:", round(sum(probs.values()), 12))
print("seg:", seg, "tokens:", len(seg), "logp:", round(score, 3))

On its four-word corpus BPE learns ne, new, lo, low, in that order. The unigram model keeps "there" as a single token, with log-probability −2.862, because every split into smaller pieces scores lower.

Nobody has settled what a model's atoms should be. Merges learned mostly from English split other languages into more pieces, so the same message can cost several times as many tokens, and so more money and more context, in some languages than in others (Petrov et al., 2023). Byte-level models drop the learned vocabulary and read raw UTF-8 (ByT5: Xue et al., 2022), at the price of much longer sequences. Newer designs group bytes into patches whose length follows how hard the next byte is to predict (Pagnoni et al., 2025). Whether a fixed tokenizer is a necessary compromise or an avoidable handicap is still open.