PaperlayerView exact revision on arXiv

Source-linked AI summary

Counting and Min-Cost Encoding for Tokenization in Large Language Models

Shuming Shi, Xiang Zhang, Hao Yu, Wenbo Fei, Changjian Wang, Zhan Wang, Guoqing Pang, Guangye Yu, Quan Lu, Ning Jiang

arXiv:2610.01127v1cs.CL

TL;DR

Tokenizers can produce substantially different sequence lengths for the same text, affecting inference time, while common vocabulary methods rely on merges or iterative refinement. The paper proposes CNF for counting and filtering vocabulary candidates and MCE for globally minimizing segmentation cost. CNF-MCE improves compression over evaluated BPE tokenizers while models at 1.8B and 8B achieve comparable average performance across 11 benchmarks.

  • Problem

    The paper asks whether token efficiency can improve under a fixed vocabulary budget without merge-based construction or repeated vocabulary refinement.

    Source: §1 · p. 2

  • Method

    CNF counts valid substrings and filters the raw vocabulary by token usage under MCE, which globally minimizes an encoding cost for a given vocabulary.

    Source: §1 · p. 2

  • Results

    CNF-MCE achieves consistently better compression than evaluated BPE tokenizers; mix250k has 26.7% and 32.4% higher token efficiency than o200k base and qwen250k, with comparable average performance across 11 English benchmarks at 1.8B and 8B.

    Source: §1 · p. 2, §5 · p. 14

  • Takeaways & Limitations

    MCE does not depend on merge information or token probability estimation, so it can operate on vocabularies built by CNF, BPE, UnigramLM, or other methods.

    Source: §1 · p. 2

    The 8B downstream comparison uses qwen152k, and a comparison with qwen250k is deferred because the vocabularies differ in size.

    Source: §4.6 · p. 13

Abstract

from arXiv · show

Mainstream large language models rely on a tokenizer to encode text into a token sequence. Different tokenizers may yield token sequences of substantially different lengths for the same text. With a fixed model architecture, shorter token sequences correspond to lower inference time. We propose a tokenizer training approach named Counting and Filtering (CNF) and a text encoding algorithm called Min-Cost Encoding (MCE). MCE defines a cost function over a text segment, and determines the best segmentation by globally minimizing the overall segmentation cost. CNF builds a raw vocabulary by directly counting valid substrings, and then constructs the final vocabulary through a filtering step based on actual token usage when segmenting the training corpus with MCE. The CNF-MCE conbination offers several advantages over BPE, including higher token efficiency, greater scalability, and lower dependency. Across six text categories and two vocabulary-size groups, CNF-MCE consistently achieves better compression than the evaluated BPE tokenizers. With a 250K vocabulary, CNF-MCE increases compression rate by 26% and 30% on English web text over the o200k_base and qwen250k tokenizers. Experiments scaling the vocabulary to 1M entries on English web text demonstrate sustained improvements over BPE, with a token efficiency improvement of over 60% and vocabulary utilization rising from 52.9% to 96.9%. The MCE algorithm does not depend on a merge list (as in BPE) or token probability (as in UnigramLM), making it applicable to a wide range of vocabularies, including those built from BPE, UnigramLM, CNF, and others. Language models trained from scratch at the 1.8B and 8B scales achieve comparable average performance to models using the BPE tokenizers across 11 benchmarks. These results demonstrate that CNF-MCE can improve token efficiency significantly while maintaining competitive downstream performance.

1 Introduction

Tokenizers affect token-sequence length and inference time, but common vocabulary-training methods have structural constraints. The paper introduces CNF and MCE and reports improved compression alongside comparable downstream performance.

1 Introduction

  • Under a fixed model architecture, shorter token sequences correspond to lower inference time, making compression rate a key tokenizer-design objective.Compression rate measures average raw text, such as UTF-8 bytes, encoded per token.Source: §1 · p. 1
  • BPE uses order-dependent merges that can consume vocabulary capacity with underused intermediate tokens, while UnigramLM relies on probability estimation and iterative pruning.Hard pretokenization boundaries also restrict tokens from spanning pretokens; SuperBPE relaxes this constraint but remains merge-based.Source: §1 · p. 2
  • Across evaluated BPE tokenizers, CNF-MCE achieves consistently better compression, with comparable average performance across 11 English benchmarks at 1.8B and 8B scales.The mix250k vocabulary achieves 26.7% and 32.4% higher token efficiency than o200k base and qwen250k, respectively.Source: §1 · p. 2
  • CNF counts valid substrings to form a raw vocabulary, then filters it once using realized token usage under MCE.This shifts selection from raw substring occurrence frequency to how often tokens are used in MCE segmentation.Source: §1 · p. 2
  • MCE globally minimizes an encoding cost combining token count with penalties for partial-word boundary crossings, and applies across vocabulary sources.The paper reports scaling to 1M entries on English web text with over 60% higher token efficiency and utilization rising from 52.9% to 96.9%.Source: §1 · p. 2

2 Related work

Prior tokenizer approaches construct vocabularies through sequential merges or iterative refinement, while separate work studies multiword tokens and alternative segmentation. CNF-MCE instead combines direct substring counting with a single usage-based filtering step and avoids ordered merges.

2 Related work

  • BPE repeatedly merges frequent adjacent symbols, while UnigramLM estimates token probabilities and iteratively prunes candidates; both approaches couple vocabulary construction to sequential or iterative procedures.PickyBPE and Scaffold-BPE remove infrequent merge products, while MinGram uses BPE initialization, Hard EM, and a final pruning step.Source: §2 · pp. 2–3
  • CNF-MCE constructs vocabularies through direct substring counting and one filtering step based on MCE token usage, without sequential merges or iterative refinement.Its candidate-validity rules and MCE penalties and constraints control partial-word boundary crossings while permitting multiword tokens.Source: §2 · p. 3
  • Methods including SuperBPE and BoundlessBPE support multiword tokens but retain ordered merge operations for vocabulary construction or inference.SuperBPE permits merges across whitespace through a pretokenization curriculum; BoundlessBPE merges adjacent pretokens represented by single tokens.Source: §2 · p. 3

3 Methodology

The methodology separates vocabulary construction from segmentation: CNF counts and filters candidates, while MCE selects a minimum-cost encoding for a given vocabulary. MCE’s boundary costs permit multiword tokens while discouraging selected partial-word crossings, and dynamic programming recovers a globally optimal segmentation.

3.1 Vocabulary Construction: Counting and Filtering (CNF)

  • CNF constructs a raw vocabulary by counting valid substrings, then filters it using how often MCE selects each token in corpus segmentations.The filtering phase retains the top-k tokens ranked by segmentation frequency.Source: §3.1 · p. 3, §3 · p. 3, §3.1.2 · p. 5

3.1.1 Raw Vocabulary Construction by Counting

  • Raw-vocabulary counting aggregates candidate substring frequencies and selects the top-m candidates, allowing words, subwords, and multiword phrases while excluding invalid cross-word substrings.CNF validity rules can exclude a substring that spans multiple words but begins within a word.Source: §3.1.1 · pp. 3–4
  • Multi-round counting, early stopping, and parallel aggregation reduce unnecessary substring enumeration, computation time, and memory use.The raw-vocabulary construction algorithm takes less than one hour with 32 threads on one million English documents.Source: §3.1.1 · p. 4

3.1.2 Filtering

  • Filtering uses MCE segmentations to rank tokens by realized usage, addressing the mismatch between substring frequency and how often a candidate is selected.A shared substring can occur frequently across words yet be selected infrequently when those complete words are included in the vocabulary.Source: §3.1.2 · pp. 4–5

3.2 Text Tokenization: Min-Cost Encoding (MCE)

  • MCE minimizes additive token costs over byte-position segmentations; its boundary penalties allow complete-unit and multiword tokens while penalizing or excluding some partial crossings.A token touching one unit or covering complete units incurs no boundary penalty; an incomplete crossing of one boundary incurs λ, set to 0.05, and an incomplete token touching three or more units is excluded. Dynamic programming recovers a globally optimal segmentation, and MCE can operate on vocabularies built by different methods.Source: §3.2 · pp. 5–6

4 Experiments

Across six text categories and multiple vocabulary sizes, the experiments evaluate compression, vocabulary scaling, intrinsic tokenizer properties, segmentation algorithms, and downstream language-model performance. CNF–MCE improves compression and vocabulary scaling while maintaining competitive downstream performance, with a scope limitation in the 8B comparison.

4.1 Experimental Setup

  • Experiments span six text categories, while CNF vocabularies are built from 6.9 million documents and evaluated alongside BPE baselines and models trained with differing tokenizers.CNF targets mix138k and mix250k; downstream tests train models from scratch at 1.8B and 8B parameters, with tokenizer as the only within-scale difference.Source: §4.1 · p. 7, §4.2 · p. 7, §4.6 · p. 12

4.2 Compression Performance across Tokenizers

  • Mix138k and mix250k achieve the highest CPT in all six categories within their respective vocabulary-size groups.For smaller vocabularies, mix138k reaches 5.599 characters per token on English web text, 20.6% and 23.2% above ds128k and qwen152k; for larger vocabularies, mix250k's gains over qwen250k range from 15.3% on Chinese to 37.6% on mathematics.Source: §4.2 · p. 8, Table 2 · p. 8, Table 3 · p. 9

4.3 Vocabulary Scaling

  • At 1M entries, CNF–MCE reaches 67.0% higher CPT than BPE and 96.9% vocabulary utilization versus BPE’s 52.9%.From 512K to 1M entries, CPT rises 6.8% for CNF–MCE and 0.6% for BPE; Figure 1 plots token efficiency and utilization across vocabulary sizes on en-web.Source: §4.3 · p. 9, Figure 1 · p. 9

4.4 Intrinsic Evaluation

  • Mix250k records a compression rate of 6.329 versus 5.143 for qwen250k, with 23.1% higher compression and 25.6% higher vocabulary utilization.It also lowers fertility by 20.2%, increases mean token length by 23.1%, and improves three-digit boundary alignment F1 by 106.7%; both tokenizers have exact reconstruction of 1.0.Source: §4.4 · p. 10, Table 4 · p. 10

4.5 Segmentation with Fixed Vocabularies

  • On the fixed qwen250k vocabulary, MCE produces the fewest tokens across all four datasets, with over 96% agreement with BPE on English web, mathematics, and Chinese.Agreement is 87.50% on Python code, showing that segmentation similarity varies by domain.Source: §4.5 · p. 11, Table 5 · p. 11
  • On mix250k, MCE is more token-efficient than FMM across all four categories and has no incomplete crossings of multiple word-like units, unlike FMM.On English web, MCE with mix250k uses 168.0 tokens/kchar versus 222.5 for BPE with qwen250k, a reduction of approximately 24.5%.Source: Table 6 · p. 11, §4.5 · p. 12

4.6 Downstream Task Evaluation

  • The 8B downstream comparison uses vocabularies of different sizes, so mix250k versus qwen250k is not a controlled comparison at comparable vocabulary sizes.The paper leaves that size-matched downstream comparison to future work.Source: §4.6 · p. 13
  • CNF–MCE achieves better compression while maintaining competitive downstream performance at both model scales.At 1.8B, phase-1 average scores were 40.4 for mix138k and 40.5 for qwen152k; at 8B, mix250k and qwen152k scored 45.9 vs. 45.2 in phase 1 and 51.6 vs. 51.0 after decay.Source: §4.6 · pp. 12–13, Table 7 · p. 13, Table 8 · p. 13

5 Conclusion

CNF–MCE separates vocabulary construction from segmentation, combining substring counting and usage-based filtering with globally cost-minimizing encoding. The conclusion reports compression gains and competitive downstream performance, while identifying broader downstream comparisons as future work.

5 Conclusion

  • CNF–MCE combines direct substring counting with one filtering step based on realized token usage, while MCE minimizes encoding cost and permits multiword tokens.The cost combines token count with penalties for partial-word boundary crossings.Source: §5 · p. 14
  • Across six text categories, CNF–MCE improves compression over evaluated BPE tokenizers and sustains gains with high vocabulary utilization up to 1M entries on English web text.The conclusion also reports higher token efficiency, scalability, and lower dependency than BPE.Source: §5 · p. 14
  • Models trained at 1.8B and 8B achieve comparable average performance to the Qwen tokenizer baseline across 11 English benchmarks.The authors identify comparisons across more vocabulary sizes, architectures, model sizes, languages, and benchmarks as future work.Source: §5 · p. 14

A.1 Data Sources for Tokenizer Training and Testing

The appendix identifies the data sources and sampling practices used in tokenizer experiments, distinguishing evaluation categories and separate samples for datasets used in both training and testing.

A.1 Data Sources for Tokenizer Training and Testing

  • The experiments distinguish English web text from English PDF text; code data span 14 programming languages, and multilingual data cover 11 human languages.Only a small portion of most listed datasets is used in the experiments.Source: §A.1 · p. 19
  • When a dataset serves both training and testing, the experiments use different randomly sampled subsets for each purpose.The passage notes that most listed datasets are quite large.Source: §A.1 · p. 19

A.2 Vocabulary Scaling Results

The appendix points to Table 10 for the detailed results of the vocabulary scaling experiment; the supplied passage does not report its values.

A.2 Vocabulary Scaling Results

  • Table 10 provides detailed results for the vocabulary scaling experiment in Section 4.3.The passage does not state the table's numerical findings.Source: §A.2 · p. 19

A.3 Tokenization Examples

The appendix presents tokenization examples for fixed vocabularies, including qwen250k and mix250k, with BPE unavailable for the latter because it has no merge information.

A.3 Tokenization Examples

  • Table 11 compares BPE, FMM, and MCE segmentations using the fixed qwen250k vocabulary.The supplied passages identify the methods and vocabulary but do not state which segmentation performs better.Source: §A.3 · p. 19, Table 11 · p. 20
  • Table 12 shows tokenization examples for the mix250k vocabulary, but BPE cannot operate on it because the vocabulary contains no merge information.The passages do not report a comparative outcome for the examples.Source: §A.3 · p. 20, Table 12 · p. 20

B.1 Model Configurations

Table 13 lists the configurations of the CNF–MCE models used for downstream evaluation at the 1.8B and 8B scales.

B.1 Model Configurations

B.2 Benchmarks

The 11 English benchmarks span scientific and commonsense reasoning, mathematics, code generation, contextual word prediction, and factual and subject knowledge.

B.2 Benchmarks

  • The 11 English benchmarks cover scientific and commonsense reasoning, mathematics, code generation, contextual word prediction, and factual and subject knowledge.Shot settings are specified in the main text, with evaluation methods and metrics in Appendix B.3.Source: §B.2 · p. 21
  • ARC evaluates grade-school science reasoning in Challenge and Easy sets, while GSM8K tests multi-step arithmetic reasoning in grade-school word problems.Source: §B.2 · p. 21
  • HumanEval evaluates code generation by functional correctness on 164 handwritten programming problems with unit tests.Source: §B.2 · p. 21
  • Lambada tests final-word prediction using broader passage context, while TriviaQA requires factual retrieval and reasoning across documents.Source: §B.2 · pp. 21–22
  • MMLU covers 57 subjects in few-shot multiple-choice evaluation, while OpenbookQA tests reasoning over provided facts.Source: §B.2 · p. 21
  • PIQA tests physical commonsense in everyday tool-use and object-manipulation choices, while CommonsenseQA tests ConceptNet-derived commonsense and inference.Source: §B.2 · p. 21
  • Winogrande assesses commonsense coreference resolution, while HellaSwag tests selection of plausible context continuations using adversarially filtered examples.Source: §B.2 · pp. 21–22

B.3 Evaluation Methods and Metrics

The evaluation uses cloze-prompting accuracy for seven multiple-choice benchmarks, exact match for three answer-prediction tasks, and pass@1 for HumanEval.

B.3 Evaluation Methods and Metrics

  • Cloze prompting reports accuracy for ARC, CommonsenseQA, HellaSwag, MMLU, OpenBookQA, PIQA, and WinoGrande by selecting the candidate with lowest perplexity.It supports zero-shot evaluation without in-context examples, unlike multiple-choice prompting, which typically requires examples for base models.Source: §B.3 · p. 22
  • Exact match reports the percentage of GSM8K, LAMBADA, and TriviaQA predictions matching an accepted reference answer after task-specific extraction and normalization.Source: §B.3 · p. 22
  • HumanEval is scored with pass@1, the probability that one generated program passes all unit tests, averaged across problems.Source: §B.3 · p. 22

Related papers

Loading 2610.01127v1…