Tokenisers Lab

Byte-level tokenisation

Every tokeniser here starts from the 256 byte values. Any UTF-8 text can be encoded and decoded back exactly, and there is no unknown token. A token is a byte string, so it can end in the middle of a multi-byte character; the playground shows such pieces as �.

Pre-tokenisation

Before merges are learned, text is cut into pre-tokens, and no token crosses a pre-token boundary. Our pre-tokeniser isolates every whitespace run: “the cat” becomes “the”, “ ”, “cat”. GPT-2's regex instead attaches one leading space to the following word: “the”, “ cat”. With our rule nearly every space costs a token, so on English our tokenisers cover fewer bytes per token than GPT-2 (GPT-2 swap tab). The space-prefix rerun uses GPT-2's rule; SuperBPE drops the boundary in its second stage.

Bottom-up merges (the BPE family)

Start from bytes. Score every adjacent pair $(u, v)$ in the training corpus, merge the best pair into a new token $uv$ everywhere, and repeat until the vocabulary has $V$ tokens. Encoding replays the merges in order. The variants differ only in the score. A pair seen fewer than min_frequency times is never merged: 2 for wordpiece_pmi, wp_bpe_ft, wp_bpe_scp, wp_bpe_npmi, wp_bpe_ppig and mdl_bits, 1 for the others.

Frequency — bpe_frequency

Standard byte-level BPE: merge the most frequent pair. The baseline every Δ is measured against.

WordPiece likelihood — wordpiece_pmi

Pair count over the product of Laplace-smoothed part counts. With $\alpha = 0$ and no cutoff it is exactly wp_bpe_base.

The PMI ratio and why it degenerates — wp_bpe_base, wp_bpe_ft

The ratio is at most $1/\max(\mathrm{freq}(u), \mathrm{freq}(v))$, and it reaches its maximum, 1, for a pair seen once whose parts occur nowhere else. So the rarest pairs are merged first. Each merge creates a rare token whose pairs are rare too, and the vocabulary fills with long strings that hardly recur in new text, which then falls back to near byte-level tokens.

The frequency threshold $\theta = 2$ removes singleton pairs, but pairs seen twice still outrank frequent ones, and the result stays close to wordpiece_pmi.

Pointwise information gain — wp_bpe_pig

PMI weighted by the pair's count: the total pointwise information of the pair over the corpus. A frequent, associated pair now outscores a singleton.

Symmetric conditional probability — wp_bpe_scp

Geometric-mean calibrated PMI with a Kneser-Ney style discount $d = 0.75$; with $d = 0$ it is $\sqrt{P(u \mid v)\,P(v \mid u)}$. Bounded in $[0, 1)$, symmetric in $u$ and $v$.

Normalised PMI — wp_bpe_npmi

Bouma's NPMI is bounded in $[-1, 1]$ and is $+1$ exactly when $u$ and $v$ only occur together; the support weight $\mathrm{freq}(uv)^{\alpha}$, $\alpha = 0.5$, keeps rare, perfectly associated pairs from winning outright.

Penalised information gain — wp_bpe_ppig

Information gain counting only positive association, divided by a merged-length penalty with $\eta = 0.35$.

Length-penalised frequency — length_penalized

Frequency divided by the merged length to the power $\beta = 0.5$, to slow down the growth of long tokens.

Minimum description length — mdl_bits

Merge the pair that most shortens the corpus under a unigram code, minus the cost of the new vocabulary entry: 24 bits plus 8 bits per byte.

SuperBPE — super_bpe

Two stages. Up to $V_{\mathrm{switch}}$ it is ordinary BPE with pre-tokenisation; after that the whitespace boundary is lifted and merges may join words into “superword” tokens (“ of the”). The benchmark suite switches after 90% of the merges, $V_{\mathrm{switch}} = 256 + 0.9\,(V - 256)$ (recorded in meta.variants); the playground switches at $0.75\,V$. It gives the most bytes per token of our tokenisers.

Morpheme prior — morpheme_bpe

Frequency BPE whose scores are scaled by $e^{\lambda M}$. $M$ is the share of the pair's current occurrences, in lexicon words, whose merged token stays inside one morpheme, minus the share that would span a morpheme boundary. Pairs with $\mathrm{count}(uv)\,e^{\lambda M} \lt 1$ are never merged. The formula shows the playground's $\lambda = 2.5$; the benchmark suite trains with $\lambda = 2$ and a lexicon from the SIGMORPHON 2022 train split, with every gold test word removed.

Unigram language model — unigram_lm

Top-down instead of bottom-up. Start from a large seed vocabulary (the most frequent substrings, found with a suffix array, about $3V$ of them) and give every token a probability. The corpus likelihood sums over all segmentations $\mathcal{S}(X_i)$ of each word.

• EM: the E-step runs forward-backward over each word's segmentation lattice (in log space) to get expected token counts; the M-step renormalises them into probabilities. 10 EM iterations per round.
• Pruning: drop the tokens whose removal costs the least likelihood under Viterbi segmentation, keeping a factor 0.75 of the vocabulary per round, until $V$ tokens remain.
• Encoding: the Viterbi (most probable) segmentation.

BPE-dropout

While encoding LM training text, each applicable merge is skipped with probability $p$, so the model sees several segmentations of the same word. In the proxy LM, bpe_dropout_p0.1 uses the bpe_frequency vocabulary with $p = 0.1$ on training ids; validation ids are deterministic.

Unigram sampling (subword regularisation)

Instead of the Viterbi path, sample a segmentation from the Unigram lattice in proportion to its probability (forward-filtering backward-sampling), or among the $k$ best paths. Implemented, not benchmarked.

Byte-entropy patching

BLT-style dynamic patches instead of a fixed vocabulary: a back-off Markov model over bytes predicts the next byte, and a new patch starts before a byte whose predictive entropy exceeds a threshold $\tau$ bits, within a minimum and maximum patch length. Implemented, not benchmarked.

Metrics

Bytes per token ↑

UTF-8 bytes of held-out text divided by the number of tokens. More bytes per token means shorter sequences: more text per context window and per training step.

Fertility ↓

Tokens per word (whitespace-separated; per character for Chinese and Japanese in Tokka-Bench).

Word split % ↓

Share of words that become two or more tokens (Tokka-Bench, on a sample of words).

Continued-word rate ↓

Share of tokens that continue a word instead of starting it: $\sum_w (n_w - 1) / \sum_w n_w$ over the sampled words $w$, where word $w$ has $n_w$ tokens.

Rényi efficiency ↑

$E_\alpha = H_\alpha(p) / \log_2 |V|$ with $H_\alpha(p) = \frac{1}{1-\alpha} \log_2 \sum_t p_t^{\alpha}$ (Shannon entropy at $\alpha = 1$), where $p$ is the token distribution on held-out text. 1 means every token is used equally often; a larger $\alpha$ penalises a few very frequent tokens more. Zouhar et al. (2023) proposed it, with $\alpha = 2.5$, as a predictor of downstream quality.

Gini ↓, active fraction ↑

Gini coefficient of the token frequencies on held-out text (0 = every token equally often), and the share of the vocabulary that occurs there at all.

Morph F1 ↑

For each SIGMORPHON 2022 gold word, the byte offsets where the tokeniser cuts it are compared with the gold morpheme boundaries: precision, recall and F1 per word, averaged per language, then over the 5 languages unweighted.

Identifier F1 ↑

The same on identifiers mined from held-out code. Gold cuts are at _/- runs, lower-to-upper humps (get|User), acronym ends (HTTP|Server); digits stay with the word before them. Splitting an underscore off is neither rewarded nor penalised.

Bits per byte (BPB) ↓

$\mathrm{BPB} = \sum_i -\ln p(t_i) \,/\, (\ln 2 \cdot B)$: the language model's total negative log-likelihood of the validation tokens, in bits, over the $B$ UTF-8 bytes of that text. Per-token perplexity cannot be compared across tokenisers: a tokeniser with longer tokens has fewer, harder predictions. BPB charges every tokeniser for the same bytes, so it is the code length the model plus tokeniser needs for the text.

Fixed byte budget

Proxy LM: every tokeniser's model trains on the same number of bytes of text, so a tokeniser with more bytes per token trains on fewer tokens. The GPT-2 swap fixes the other way: the same tokens per step and the same steps (the same compute), so a tokeniser with more bytes per token sees more text.

GPT-2-equivalent steps ↑

The first step at which GPT-2's own train BPB (its train loss in bits per byte, smoothed by a centred rolling mean) reaches a tokeniser's final val BPB: how many of GPT-2's steps buy the same quality.