核心发现
方法论
本文提出了ConvexTok，一种基于凸松弛的Tokeniser构建方法。作者首先将Tokeniser构造问题形式化为整数规划（IP），随后通过将离散约束松弛为连续区间，将IP转化为线性规划（LP）。该LP可通过高效凸优化工具求解，获得近似全局最优解。为将LP的连续解离散化，文中设计了三种不同的舍入策略：确定性舍入（Det）、偏置舍入（Bias）和积分舍入（Int），以构造实际可用的离散词汇表。该方法不仅提供了词汇表的最优压缩下界，还能量化当前Tokeniser与最优解的差距，实验证明在常见词汇规模（8k至256k）下，差距小于1%。
关键结果
- ConvexTok在ClimbMix400B数据集上训练，词汇规模128k时，LP求解的压缩下界与实际舍入后Tokeniser压缩率差距不足1%，显著优于传统BPE的2%以上差距。
- 在Intrinsic指标上，Bias舍入策略在词汇利用率、类型-标记比和压缩率等指标均优于BPE，尤其在词汇利用率提升超过5%。
- 语言模型性能方面，Det舍入策略在Bits-per-byte（BpB）指标上优于BPE，提升约0.1至0.3个百分点，且在CORE下游任务中表现更稳定，表明更优的Tokeniser压缩有助于模型性能提升。
研究意义
Tokenisation作为自然语言处理的基础环节，直接影响语言模型的输入表示和性能。传统BPE和Unigram算法因其贪心策略，无法保证全局最优词汇表，导致压缩效率和下游任务表现受限。ConvexTok通过凸优化框架，首次实现了Tokeniser构造问题的全局近似最优求解，并提供了理论下界和最优性证书，填补了Tokeniser设计中缺乏全局视角的空白。这对于提升大规模语言模型的训练效率和泛化能力具有重要意义，推动了Tokenisation从启发式向理论驱动的转变。
技术贡献
本文的核心技术贡献在于将Tokeniser构造问题转化为带颜色分区的有向无环图上的最短路径问题，进一步建模为整数规划，并通过凸松弛转为线性规划，利用现代LP求解器高效获得近似最优解。该方法不仅克服了NP难问题的计算瓶颈，还设计了多种舍入策略保证离散词汇表的高质量构建。此外，提供了压缩下界的理论证书，使得用户能够量化Tokeniser的最优性距离，具备理论与实践的双重保障。
新颖性
ConvexTok是首个将Tokeniser构造问题系统性地转化为凸优化问题并求解的工作，突破了传统贪心算法的局限。与现有BPE、Unigram等启发式方法不同，ConvexTok提供了全局优化视角和最优性证书，首次实现了Tokeniser构造的理论下界计算和近似最优解的高效求解，具有显著的理论创新和工程实用价值。
局限性
- ConvexTok的LP求解在词汇规模较小（如8k）时计算时间较长，且对训练数据的敏感度高，导致词汇稳定性不及BPE。
- 舍入策略仍需进一步优化，部分策略如积分舍入在压缩率和下游任务表现上不及其他策略，存在实用性折中。
- 当前方法主要聚焦于压缩率优化，未充分探索其他目标函数如语义保真度或多语言适应性，应用范围有限。
未来方向
未来工作可聚焦于设计更高效的舍入算法以提升词汇稳定性和下游任务表现，同时扩展凸优化框架以支持多目标优化，如语义一致性和跨语言泛化。此外，结合深度学习模型训练过程中的动态Tokeniser调整，探索端到端联合优化策略，将进一步提升语言模型的整体性能和实用价值。
AI 总览摘要
Tokenisation是自然语言处理（NLP）中将文本转换为模型可处理的离散符号序列的关键步骤。传统方法如BPE和Unigram采用贪心策略，逐步合并频繁的字节对或选择高概率子词，虽然简单高效，但无法保证全局最优，导致词汇表在压缩率和泛化能力上存在不足。本文提出了ConvexTok，一种基于凸松弛的Tokeniser构造新方法，突破了传统贪心算法的局限。
ConvexTok首先将Tokeniser构造问题形式化为整数规划问题，利用有向无环图表示文本的所有可能分割路径，并通过颜色分区表示词汇选择。随后，作者将整数规划松弛为线性规划，利用现代凸优化求解器高效获得近似最优解。为解决线性规划解的连续性问题，设计了三种舍入策略（Det、Bias、Int）将解离散化为实际词汇表。该方法不仅提升了压缩率，还能提供理论下界，量化Tokeniser与最优解的距离。
在ClimbMix400B大规模数据集上，ConvexTok在词汇规模从8k到256k的多种设置下均表现出优越性能。Bias舍入策略在词汇利用率、类型-标记比和压缩率等内在指标上均优于BPE，Det舍入策略在语言模型的Bits-per-byte指标上实现了显著提升，且在CORE下游任务中表现更稳定。实验还显示，随着词汇规模增大，LP解趋于整数，舍入步骤影响减小，表明方法具备良好的扩展性。
该研究不仅为Tokeniser设计提供了全局最优的理论框架，还为实际应用提供了高效可行的算法，推动了Tokenisation从启发式方法向理论驱动优化的转变。其最优性证书功能为Tokeniser性能评估提供了新的视角，有助于未来Tokeniser设计的标准化和系统化。
尽管ConvexTok在压缩率和模型性能上取得了显著进展，但其在小规模词汇表上的计算效率和训练数据敏感性仍有待提升。未来研究可探索更高效的舍入策略、多目标优化以及与深度模型训练的联合优化，进一步提升Tokeniser的泛化能力和实用性。总之，ConvexTok为NLP领域的Tokenisation问题提供了创新且实用的解决方案，具有广泛的学术和工业应用前景。
深度分析
研究背景
Tokenisation是自然语言处理（NLP）中将连续文本转换为离散符号序列的基础步骤，直接影响语言模型的输入表示和性能。早期方法多基于规则或词典，难以适应大规模无监督语料。近年来，字节对编码（BPE）和Unigram模型成为主流，它们通过贪心策略迭代合并频繁子串或选择概率最高的子词，极大提升了压缩率和模型效果。BPE由Sennrich等人提出，因其简单高效被广泛应用于现代大规模语言模型如GPT系列。Unigram模型则基于概率分布优化词汇选择。尽管如此，这些方法均为局部最优，未能考虑词汇表整体最优性，导致压缩效率和泛化能力受限。近年来有研究尝试改进贪心策略，但未根本解决全局最优问题。本文基于凸优化理论，提出全新框架，系统性解决Tokeniser构造的全局最优问题，填补了该领域的理论空白。
核心问题
Tokeniser构造的核心问题是如何在给定词汇表大小预算下，选择最优的子词集合，使得训练语料的编码长度最短，实现最大压缩。该问题可形式化为组合优化问题，已被证明为NP难，无法通过穷举或简单启发式方法高效求解。传统BPE和Unigram算法采用贪心策略，逐步合并或选择局部最优子词，忽视词汇表整体结构，导致压缩效果次优。此外，缺乏理论下界和最优性证书，使得Tokeniser性能评估缺乏标准。如何设计高效算法，获得接近全局最优的词汇表，同时提供最优性保证，是该领域亟待解决的难题。
核心创新
本文的核心创新包括：
- �� 将Tokeniser构造问题转化为带颜色分区的有向无环图（DAG）上的最短路径问题，利用图结构表达所有可能的文本分割路径及词汇选择。
- �� 基于该图模型，构建整数规划（IP）形式的优化问题，精确描述词汇选择与文本编码的约束关系。
- �� 通过凸松弛技术，将IP转化为线性规划（LP），实现高效求解近似全局最优解，克服NP难题的计算瓶颈。
- �� 设计三种舍入策略（确定性、偏置、积分）将连续LP解离散化为实际词汇表，兼顾压缩率和泛化能力。
- �� 提供理论下界和最优性证书，量化Tokeniser与最优解的距离，填补Tokeniser性能评估的空白。
这些创新突破了传统贪心算法的局限，首次实现了Tokeniser构造的全局优化视角和理论保障。
方法详解
- �� 构建Tokenisation图：对训练语料中的每个字节串，构建有向无环图，顶点表示字节间位置，边表示可能的子词分割，边按子词颜色分区。
- �� 定义整数规划（IP）：引入自由边和定价边，表示必须包含和可选子词，定义流约束保证路径有效性，词汇预算约束限制词汇表大小。
- �� 凸松弛转线性规划（LP）：将IP中二元变量放宽至[0,1]连续区间，允许部分选择子词，利用现代LP求解器高效求解。
- �� 舍入策略设计：
- 确定性舍入（Det）：选择LP解中值最大的K个词汇。
- 偏置舍入（Bias）：按词汇值除以词长排序，优先选短词汇。
- 积分舍入（Int）：只选择LP中接近1的词汇，忽略其他。
- �� 词汇表构建与编码：基于舍入结果构建离散词汇表，利用最短路径算法对文本进行编码。
- �� 性能评估：在ClimbMix400B数据集上训练Tokeniser和语言模型，评估压缩率、词汇利用率、Rényi熵、BpB和下游任务表现。
实验设计
实验使用ClimbMix400B大规模预训练语料，预先用正则表达式进行粗粒度预分词，防止跨词边界。训练集包含593,920文档，词汇规模从8k到256k，按2的幂次递增。基线为传统BPE算法。ConvexTok采用三种舍入策略（Det、Bias、Int）分别训练。LP求解使用NVIDIA CuOPT库，问题规模超过1亿变量和约1亿约束。语言模型采用nanochat架构，参数规模从1.35亿到35亿不等，训练时间从17分钟到199分钟不等。实验评估包括LP解的积分性、舍入后压缩率、词汇稳定性、内在指标（词汇利用率、类型-标记比、Rényi熵）、语言模型Bits-per-byte及CORE下游任务表现。通过多次随机采样训练集验证词汇稳定性。
结果分析
LP解随着词汇规模增大趋于整数，表明问题在大规模下更易求解。Bias舍入策略在词汇利用率和压缩率上显著优于BPE，词汇利用率提升超过5%。Det舍入策略在语言模型Bits-per-byte指标上优于BPE，提升约0.1-0.3个百分点，且在CORE下游任务中表现更稳定。积分舍入策略虽然压缩率较低，但在某些规模下仍接近最优。BPE虽为贪心算法，但压缩率距离最优仅约2%，显示其有效性。词汇稳定性实验表明BPE更稳定，ConvexTok对训练数据敏感，尤其在小词汇规模时。整体结果验证了ConvexTok在压缩率和模型性能上的优势及其理论最优性证书的有效性。
应用场景
ConvexTok可直接应用于大规模语言模型的Tokeniser设计，提升压缩率和模型性能，适用于预训练和微调阶段。其理论下界功能为Tokeniser性能评估和算法改进提供科学依据，有助于标准化Tokeniser设计流程。该方法亦适合多语言、多域文本的Tokeniser优化，提升跨语言模型的泛化能力。未来可结合动态Tokeniser调整，实现端到端联合优化，推动NLP模型训练效率和效果的提升。
局限与展望
ConvexTok在小词汇规模时求解时间较长，影响实际应用效率。训练数据敏感性导致词汇稳定性不及BPE，可能影响模型泛化。舍入策略尚未完全优化，部分策略在压缩率和下游任务表现上存在折中。当前研究主要聚焦压缩率，未充分考虑语义保真和多语言适应性。LP求解对硬件资源需求较高，限制了大规模部署。未来需优化算法效率，增强稳定性和多目标适应能力。
通俗解读 非专业人士也能看懂
想象你有一大堆拼图块（字节），你想把它们拼成图画（文本），但拼图块太多，拼起来很慢。传统方法像是你每次只看眼前两块最容易拼的，拼完再看下一对，这样虽然快，但可能拼出来的图画不够完美。ConvexTok就像是你先把所有拼图块的可能组合都画成一张地图，然后用数学方法找出一条最短路径，告诉你应该怎么拼才能用最少的拼图块完成图画。这样拼出来的图画更完整，拼图块用得更少，节省了空间和时间。虽然这个方法一开始看起来复杂，但它能保证你拼的图画接近最完美的状态，还能告诉你离完美有多远。这个方法还设计了几种把数学结果变成实际拼图步骤的技巧，确保你能真正用这些拼法来拼图。最终，这种方法让语言模型能更好地理解和生成文本，就像拼图拼得更快更准一样。
简单解释 像给14岁少年讲一样
嘿，想象你在玩乐高积木，要搭一个超酷的城堡！但积木太多了，你得选哪些积木搭最漂亮又结实。以前的方法就像你每次只挑眼前最合适的积木，虽然快，但可能没搭出最棒的城堡。现在，有个叫ConvexTok的超级聪明方法，它先帮你画出所有可能的搭建路线图，然后用数学魔法帮你找出最棒的搭法，保证用最少的积木搭出最酷的城堡！而且它还能告诉你，这个搭法离完美有多近。虽然听起来有点复杂，但它让电脑学语言的时候，也能像你搭乐高一样，选最合适的“积木”，让电脑更聪明、更快地理解和说话。是不是很酷？
术语表
Tokenisation (分词)
将文本拆分成更小的单元（如子词或字节序列），以便语言模型处理。是NLP的基础步骤。
本文研究如何优化Tokenisation以提升语言模型性能。
Byte-Pair Encoding (BPE，字节对编码)
一种贪心算法，通过迭代合并最频繁的字节对构建词汇表，广泛用于现代语言模型。
作为本文的主要对比基线，BPE存在局部最优问题。
Integer Programming (整数规划)
一种组合优化方法，变量取整数值，常用于解决离散决策问题。
本文将Tokeniser构造问题建模为整数规划。
Linear Programming (线性规划)
一种优化方法，变量取连续值，目标和约束均为线性函数，可高效求解。
通过凸松弛将整数规划转化为线性规划，便于求解。
Convex Relaxation (凸松弛)
将离散优化问题的约束放宽为连续凸集合，便于利用凸优化工具求解近似解。
本文核心技术，用于将Tokeniser问题转为可解的LP。
Rounding (舍入)
将连续解转换为离散解的过程，确保最终词汇表可用。
设计了三种舍入策略实现LP解的离散化。
Bits-per-byte (BpB，字节每比特数)
衡量语言模型压缩效率的指标，数值越低表示压缩越好。
用于评估Tokeniser对语言模型性能的影响。
Rényi Entropy (Rényi熵)
一种信息熵度量，反映词汇分布的多样性和不确定性。
作为内在指标评估Tokeniser的词汇分布特性。
Directed Acyclic Graph (DAG，有向无环图)
一种图结构，边有方向且不存在环路，用于表示文本的所有可能分割路径。
构建Tokenisation图的基础结构。
Jaccard Similarity (雅卡尔相似度)
衡量两个集合相似度的指标，定义为交集大小除以并集大小。
用于评估不同训练样本下Tokeniser词汇表的稳定性。
开放问题 这项研究留下的未解疑问
- 1 如何设计更高效且稳定的舍入策略，以兼顾压缩率和下游任务性能，仍是未解决的问题。
- 2 当前方法主要优化压缩率，如何将语义保真度、多语言适应性等多目标纳入Tokeniser设计尚未充分探索。
- 3 LP求解的计算资源需求较高，如何降低计算复杂度，实现大规模实时Tokeniser构建是挑战。
- 4 Tokeniser对训练数据的敏感性导致词汇稳定性不足，如何提升其鲁棒性和泛化能力需要深入研究。
- 5 如何将凸优化框架与语言模型训练过程联合优化，实现端到端自适应Tokeniser仍是未来方向。
应用场景
近期应用
大规模语言模型预训练
利用ConvexTok设计的高效Tokeniser提升训练语料的压缩率，减少模型输入长度，加快训练速度，提升模型性能。
多语言Tokeniser优化
通过凸优化框架为多语言文本构建统一且最优的词汇表，增强跨语言模型的泛化能力。
Tokeniser性能评估与标准化
利用ConvexTok提供的最优性证书，科学量化和比较不同Tokeniser的性能，推动行业标准制定。
远期愿景
端到端联合优化语言模型
结合ConvexTok与深度模型训练，实现动态自适应Tokeniser，提升模型整体训练效率和泛化能力。
多目标Tokeniser设计
扩展凸优化方法支持语义保真、多语言适应等多目标优化，推动Tokeniser设计向更智能化方向发展。
原文摘要
Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and Unigram are greedy algorithms -- they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as a linear program and solve it using convex optimisation tools, yielding a new algorithm we call ConvexTok. We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models; it also improves downstream task performance, but less consistently. Furthermore, ConvexTok allows the user to certify how far their tokeniser is from optimal, with respect to a certain objective, via a lower bound, and we empirically find it to be within 1\% of optimal at common vocabulary sizes.
参考文献 (20)
Investigating the Effectiveness of BPE: The Power of Shorter Sequences
Matthias Gallé
Flows in Networks
E. Denardo
Scaling neural machine translation to 200 languages
M. Costa-jussà, James Cross, Onur Çelebi 等
Paths and cycles in colored graphs
H. Broersma, Xueliang Li, G. Woeginger 等
Practical Guidelines for Solving Difficult Mixed Integer Linear
Ed Klotz, A. Newman
The Traveling Salesman Problem: A Computational Study
D. Applegate, R. Bixby, V. Chvátal 等
A Formal Perspective on Byte-Pair Encoding
Vilém Zouhar, Clara Meister, Juan Luis Gastaldi 等
An approximation algorithm for the generalized assignment problem
D. Shmoys, É. Tardos
Our Method
Imene Bensalem, Paolo Rosso, S. Chikhi
Boundless Byte Pair Encoding: Breaking the Pre-tokenization Barrier
Craig W. Schmidt, Varshini Reddy, Chris Tanner 等
Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling
Stella Biderman, Hailey Schoelkopf, Quentin Anthony 等
Language Models
Jordan Boyd-Graber, Philipp Koehn
Scaling Laws for Neural Language Models
J. Kaplan, Sam McCandlish, T. Henighan 等
Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates
Taku Kudo
Approximation algorithms and hardness results for labeled connectivity problems
Refael Hassin, J. Monnot, D. Segev
Nemotron-CLIMB: CLustering-based Iterative Data Mixture Bootstrapping for Language Model Pre-training
Shizhe Diao, Yu Yang, Y. Fu 等
Scaffold-BPE: Enhancing Byte Pair Encoding for Large Language Models with Simple and Effective Scaffold Token Removal
Haoran Lian, Yizhe Xiong, Jianwei Niu 等
Random Contractions and Sampling for Hypergraph and Hedge Connectivity
M. Ghaffari, David R Karger, D. Panigrahi