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

📄 arXiv: 2610.01127v1 📥 PDF

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

分类: cs.CL

发布日期: 2026-10-01

💡 一句话要点

提出CNF-MCE方法以提高大语言模型的编码效率

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 分词器 文本编码 令牌效率 压缩率 自然语言处理 机器学习

📋 核心要点

  1. 现有的分词器在处理相同文本时可能生成长度差异较大的令牌序列，导致推理时间不一致。
  2. 本文提出的CNF-MCE方法通过计数和过滤有效子字符串来优化词汇表，并通过最小化分割成本来提高编码效率。
  3. 实验表明，CNF-MCE在压缩率和令牌效率上均优于BPE，尤其在250K和1M词汇规模下，压缩率提升显著。

📝 摘要（中文）

主流的大语言模型依赖于分词器将文本编码为令牌序列。不同的分词器可能会对相同文本生成长度差异显著的令牌序列。本文提出了一种名为Counting and Filtering (CNF)的分词器训练方法和一种文本编码算法Min-Cost Encoding (MCE)。MCE通过定义文本段的成本函数，全球最小化整体分割成本来确定最佳分割。CNF通过直接计数有效子字符串构建原始词汇表，并通过基于实际令牌使用的过滤步骤构建最终词汇表。CNF-MCE在多个文本类别和词汇规模组中表现出比BPE更高的压缩率和更好的令牌效率。实验结果表明，CNF-MCE在多个基准测试中与BPE分词器的模型性能相当，同时显著提高了令牌效率。

🔬 方法详解

问题定义：本文旨在解决现有分词器在文本编码时产生的令牌序列长度差异问题，导致推理时间不一致，影响模型效率。

核心思路：提出CNF和MCE两种方法，CNF通过计数有效子字符串构建词汇表，MCE通过定义成本函数来优化文本分割，从而提高编码效率。

技术框架：整体架构包括两个主要模块：CNF用于构建原始词汇表，MCE用于根据成本函数进行文本编码和分割。

关键创新：CNF-MCE结合了计数和过滤的策略，显著提高了令牌效率和词汇利用率，且不依赖于传统的合并列表或令牌概率。

关键设计：在参数设置上，CNF通过有效子字符串计数构建词汇表，MCE定义了全局最小化的成本函数，确保了在不同规模下的高效编码。实验中，词汇规模的扩展也验证了其在大规模数据集上的有效性。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

实验结果显示，使用250K词汇的CNF-MCE在英语网页文本上比o200k_base和qwen250k分词器的压缩率分别提高了26%和30%。在1M词汇规模下，CNF-MCE的令牌效率提升超过60%，词汇利用率从52.9%提升至96.9%。

🎯 应用场景

该研究的潜在应用领域包括自然语言处理、机器翻译和对话系统等。通过提高分词效率，CNF-MCE能够加速模型推理，降低计算成本，提升用户体验，具有广泛的实际价值和未来影响。

📄 摘要（原文）

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.