Does a certifiably better tokenizer make a better language model?

ClimbMix, Qwen3 0.6B dense, Megatron-Core on B200. Dual decomposition (dr-tokenization) vs byte-level BPE, everything else held fixed.

Result. No. At matched vocabulary size and matched training data, dual decomposition compresses 2.6% better than greedy BPE, and the language model trained on it is 0.0030 BPB worse, at every one of 12 checkpoints. The deficit persists when the comparison is matched on bytes instead of tokens. Vocabulary size moved BPB about 9x more than the construction method.

Setup

Corpus

ClimbMix (NVIDIA CLIMB, 400B tokens), sampled from the detokenized mirror OptimalScale/ClimbMix at a pinned revision. The release is cluster-sorted: each part_*.jsonl holds one topic cluster (19 clusters, byte shares 0.2% to 22.0%), so a prefix of the parts is one or two topics rather than the mixture. Sampling therefore lays a 16 MiB byte grid over every part, takes blocks in proportion to part size, and shuffles globally.

pool

116.5 GB text, 39.14M docs, 224 shards, 0 failed blocks

held-out

last 4 shards, unseen by both tokenizer and model

tokenizer training

25.00 GiB of characters, byte-identical stream for both arms (same seeded shard shuffle, same document order, same cutoff)

chunk table

5.50B chunk instances, 10.22M types, mean chunk 4.89 bytes

Tokenizers

Both arms: vocabulary built from the same 25 GiB, same pre-tokenizer (digits split individually, then GPT-2 byte-level regex), ChatML specials plus 256 reserved slots, all 256 single bytes for coverage.

BPE control

HuggingFace Rust models.BPE + BpeTrainer, greedy merge sequence, no math upsampling

DD candidate

dual decomposition: minimizes corpus token count + λ·|V| with per-arc prices; unrestricted vocabulary class; max_token_len 16; warm-started from the BPE vocabulary so its primal can only improve on it; exported as HF Unigram with one shared score, which makes Viterbi a min-token-count segmenter (DD's own inference rule)

certificates

every DD vocabulary ships a dual bound, so distance from the optimum of its class is measured, not assumed

Model and recipe

Identical across arms; only the tokenizer and therefore the tokenized corpus differ.

model

Qwen3 dense, hidden 1536, 20 layers, 12 q / 6 kv heads, head_dim 128, intermediate 4096, seq 4096, tied embeddings. 0.617B at vocab 64000; 0.530B at vocab 6912

optimizer

Muon, 8-way layer-wise sharded, AdamW for scalars

precision

bf16 parameters, MXFP8 compute, TE cuDNN attention

schedule

WSD: warmup 500, cosine cooloff over the last 15%, LR 7e-4 to 7e-5

budget

mbs 8, GBS 512 x seq 4096 = 2.097M tokens/iter, 6000 iters = 12.6B tokens (~20 tokens/param)

throughput

537 to 560 TFLOP/s/GPU; 2.5 h on 8 B200, 4.9 h on 4 B200 (same cost per iteration)

metric

BPB, bits per byte of the same held-out text. Comparable across vocabularies; per-token loss and perplexity are not

Experiment 1: compression vs vocabulary size

DD at a λ ladder on the 25 GiB chunk table, then BPE trained at the exact sizes DD landed on, both scored on 12,000 held-out documents (46 MB). H0 = order-0 (context-free) entropy of the emitted token stream per byte; it is a property of the token IDs, not of the tokenizer's model class.

At K=64,604 the two produce token-for-token identical segmentations on ordinary prose, and only 74.7% of DD's entries appear in BPE's: they differ in the tail, not the common case. DD's extra entries are long whole words ( unconditionally, cerebrovascular) that greedy merging never forms.

The language-model arms therefore run at K=6,331, where the gap is largest (+2.58% bytes/token) and any effect is most detectable. A null at maximum signal is a stronger null than a null at 64k.

Experiment 1b: the same curve with 4x the tokenizer training data

Both methods retrained on 100 GiB of characters instead of 25 GiB (same pool, same pre-tokenizer, same recipe), scored on the same held-out shards. This separates "how much text the tokenizer saw" from "how the vocabulary was built".

Effect of tokenizer training-set size on each method

Positive means more tokenizer training data packed more bytes per token.

Experiment 2: two language models at matched K

vocabulary

6849 entries in both (6331 learned + 256 bytes + 262 specials); model vocab_size 6912, with the same 63 unused rows in each arm

corpus

same 220-shard text pool, tokenized twice. DD 30,107,772,932 tokens vs BPE 30,730,599,716 for identical text, so BPE needs 2.07% more tokens

consumed at 6000 iters

DD 47.8 GB of text, BPE 46.8 GB (equal tokens means unequal bytes)

Mean over all 12 checkpoints: +0.0030 BPB (sd 0.0006), DD worse at every point. The curves are parallel: the gap appears by iter 500 and narrows slightly to +0.0019 by the end, so this is a level shift, not a convergence-rate difference.

Reading the result

Perplexity disagrees with BPB, and BPB is the one to trust

DD's held-out perplexity is 6.66% worse while its BPB is 0.24% worse. The per-token loss ratio factorizes exactly:

Each DD token spans more text and is intrinsically harder to predict, so perplexity penalizes DD for compressing better. BPB divides that factor out.

Not a data-rate artifact

At equal tokens DD has seen 2.07% more text, which should have helped it. Matching on bytes instead (interpolating the BPE curve to DD's byte count in the peak-LR region) makes DD look worse, not better:

So BPE wins at matched compute (equal tokens) and by more at matched data (equal bytes).

H0 pointed the wrong way

The context-free statistic favored DD by 1.81% at this K, and the trained models put DD 0.24% behind. DD's long whole-word tokens are cheap to encode and cheap to predict without context; with context, the model does relatively better on BPE's more compositional pieces. Minimizing token count is not minimizing what a language model has to model, and neither compression nor order-0 entropy predicted the sign.

Size dominates method

Choosing the vocabulary size mattered about 9x more than choosing how the vocabulary is built.

Limit of the evidence. One run per arm. The sd 0.0006 above is consistency across checkpoints of the same two runs, not seed-to-seed variation, which on this stack is roughly 0.002 to 0.005 BPB. The mean effect (0.0030) sits inside that band. The supportable claim is that DD's compression advantage produced no BPB improvement, and if anything a small regression, not a precise -0.003. Resolving the sign would need 2 to 3 seeds per arm.

Where the DD tokenizer is still worth something

2.07% fewer tokens for the same text is 2.07% fewer decode steps and a 2.07% shorter KV cache per byte generated, for 0.24% worse BPB. That trade is a serving-cost question, not a quality one. The mechanism also predicts that the deficit should shrink with model capacity, since fewer, longer tokens mean less compute spent per byte; testing that needs the same pair at another model size.