CNF-MCE Tokenizer: Counting & Min-Cost Encoding Beats BPE with 26-60% Compression Gains

Background: Tokenizer Efficiency Matters

Tokenizers are the first gate for all text input to large language models. For the same 10,000-character text, some tokenizers produce 8,000 tokens while others need only 5,000. Fewer tokens mean faster inference, lower KV‑Cache memory, reduced long‑context pressure, and lower serving costs. Yet nearly all mainstream models (GPT, Llama, Qwen) still rely on BPE or its variants. BPE builds vocabularies by iteratively merging frequent adjacent subwords — simple and battle‑tested — but its greedy merging leads to vocabulary waste and limited scalability.

CNF: Counting and Filtering for Vocabulary Construction

CNF (Counting and Filtering) replaces iterative merging with a two‑step process:

Counting: Directly count occurrences of “legal candidate tokens” in the training corpus. Legal candidates include words, subwords, and complete multi‑word phrases, but exclude fragments that start mid‑word or span multiple words incompletely. A parallel, multi‑round, length‑bucketed counting algorithm with early stopping processes 1 million English documents in under an hour on 32 threads.

Filtering: Run the MCE encoder (described below) over the entire corpus once, tally how many times each candidate token is actually used in the globally optimal segmentation, and retain only those with high “real usage frequency.” This single filtering step shifts selection from raw occurrence counts to counts under the true encoding objective, aligning vocabulary with actual tokenization behavior.

MCE: Min‑Cost Encoding for Optimal Segmentation

MCE (Min‑Cost Encoding) frames tokenization as a global cost minimization problem on the byte sequence. Each candidate token receives a cost: a base cost of 1 (encouraging fewer tokens) plus a boundary penalty and an optional small bias term.

The boundary penalty is designed around “word‑like units.” Tokens that lie completely inside one unit or exactly cover multiple whole units incur zero penalty. Tokens crossing a single boundary with incomplete endpoints receive a tiny penalty. Tokens crossing more than one boundary incompletely are forbidden. This allows meaningful multi‑word phrases (further compression) while suppressing semantically unnatural splits.

Because costs are additive, the globally optimal segmentation is found via dynamic programming on the byte sequence, guaranteeing the minimum‑cost path. Crucially, MCE does not depend on merge lists or token probabilities; it can be applied to any vocabulary — BPE, Unigram, CNF, or others. In the report, applying MCE to the fixed qwen250k BPE vocabulary further reduced token count, with byte‑level segmentation consistency above 96% in most scenarios, demonstrating practical migration feasibility.

Experimental Results

Compression Efficiency

At 250K vocabulary size on English web text: CNF‑MCE improves compression by 26.7% over o200k base and 32.4% over qwen250k.

Chinese text shows even larger gains: nearly 50% improvement over o200k base.

Scaling vocabulary to 1M: token efficiency increases over 60%, and vocabulary utilization jumps from 52.9% to 96.9%.

Model Training Evaluation

To verify that compression gains do not harm model quality, the team trained 1.8B and 8B parameter models using CNF‑MCE and BPE tokenizers, evaluating on 11 English benchmarks.

Average performance across benchmarks remains comparable between CNF‑MCE and BPE baselines at both model scales.

Notable improvements: 8B model GSM8K score rises from 20.8 to 38.7; LAMBADA also improves.

Regressions: HumanEval drops from 11.6 to 4.3; MMLU and TriviaQA show moderate declines.

Conclusion

Tokenizers have long been treated as a secondary component in LLM research, overshadowed by model depth, MoE architectures, and data scale. BPE has served well but its vocabulary waste and limited extensibility become bottlenecks as context windows grow to millions of tokens. CNF‑MCE breaks the “iterative merging” paradigm, proving that high‑compression, high‑utilization tokenization is achievable without greedy merges. As long‑context and million‑token windows become standard, tokenizer efficiency will directly translate to lower inference costs, longer effective context, and higher throughput on the same hardware.