基于凸松弛的分词方法

论文信息

标题: Tokenisation via Convex Relaxations

作者: Jan Tempus, Philip Whittington, Craig W. Schmidt, et al.

发布日期: 2026-05-21

PDF 链接: 下载 PDF

背景与研究动机

分词（Tokenisation）是现代自然语言处理流程中不可或缺的一环，它将原始字节序列转换为语言模型可直接使用的 token 序列。目前主流的词表构建算法，如字节对编码（BPE）和 Unigram，本质上都是贪心算法：它们在每一步做出局部最优的合并或选择，而从未从整体词表的角度进行全局优化。尽管近期研究表明，分词器的压缩能力与下游语言模型的性能存在一定正相关，但寻找压缩最优的分词器已被证明是 NP 难问题，因而现有方法始终停留在贪心近似阶段。

论文《Tokenisation via Convex Relaxations》直面这一困境，提出了一种全新的思路：将分词器的构造转化为线性规划问题，并借助凸优化工具进行求解。该算法被命名为 ConvexTok。与贪心方法不同，ConvexTok 试图逼近全局最优的分词方案，不仅能获得更紧凑的词表，还能提供理论下界，帮助研究者明确任何给定分词器离最优解究竟有多远。实验显示，在常规词表规模下，ConvexTok 的压缩性能已处于最优解的 1% 差距之内，这为分词技术的全局优化提供了理论依据和实用工具。

核心方法：从图构建到线性规划

ConvexTok 的核心在于将字符级的分词任务重新表述为一个图上最短路径问题，进而化为整数规划并松弛求解。整个过程分为三个步骤：图构造、整数规划建模以及线性松弛与舍入。

图构造。 给定一个训练数据集，算法将每个字节串表示为顶点序列，相邻字节之间、以及跨越多字节的子串之间都引入有向边。具体而言，每个字节位置对应一个顶点，相邻顶点之间用“字节边”相连；所有非相邻的顶点对则通过“token 边”连接，这些 token 边根据其代表的子串内容染上不同颜色。于是，一个传统意义上的词表就对应于选定的一组颜色，而一条从数据集起点到终点的路径恰好等价于对整个数据集的一种分词方式。路径的长度（边的数量）就是分词后的 token 总数，即压缩代价。这样，寻找压缩最优分词器的问题，就变成了在预算 $K$ 内选择 $K$ 种颜色、并找到一条最短路径的组合优化问题。

整数规划建模。 论文引入三个向量变量： $\mathbf{f}$ 表示免费边（字节边）是否被使用， $\mathbf{p}$ 表示付费边（token 边）是否被使用， $\mathbf{c}$ 表示某种颜色（即潜在 token）是否被选入词表。通过关联矩阵 $\mathbf{F}$ 、 $\mathbf{P}$ 和颜色-边矩阵 $\mathbf{C}$ ，可以写出流守恒约束：

$\mathbf{P}\mathbf{p} + \mathbf{F}\mathbf{f} = \mathbf{d}$

其中 $\mathbf{d}$ 是一个仅在起点和终点有非零值的向量，用于保证形成一条完整路径。此外，付费边仅在其对应颜色被选择时才允许被使用： $\mathbf{p} - \mathbf{C}\mathbf{c} \le 0$ ，并且选择的颜色总数不超过预算： $\langle 1, \mathbf{c}\rangle \le K$ 。目标函数是 $\langle 1, \mathbf{p}\rangle + \langle 1, \mathbf{f}\rangle$ ，即路径总长度。该整数规划精确描述了全局最优分词器的搜索空间，但依然是 NP 难问题。

线性松弛与舍入。 为高效求解，论文将所有 0-1 整数约束松弛为连续区间 $[0,1]$ ，将整数规划转换为线性规划（LP）。此时， $\mathbf{c}$ 的分量可以为分数，表示“部分选中”某个 token。LP 可以在多项式时间内用标准求解器解出。然而，分数解不能直接用于构造词表，因此需要舍入操作。文中给出了三种简单的舍入策略：

确定性舍入（Det）：直接取 $\mathbf{c}$ 中取值最大的 $K$ 个颜色，将其置为 1，其余置 0。
偏置舍入（Bias）：按 $\mathbf{c}$ 的取值除以 token 长度排序，再选前 $K$ 个。这倾向于在评分相近时选择更短的 token，以提升泛化能力。
仅整舍入（Int）：只保留 $\mathbf{c}$ 中已经接近 1 的颜色，不强行凑满预算。

舍入后，可以用已知的最短路径算法在选定词表下重新计算最优的 $\mathbf{p}$ 和 $\mathbf{f}$ ，得到最终分词器。这整套流程就构成了 ConvexTok。

创新点与贡献

论文的主要贡献体现在三个方面：

首次将分词器构造转化为凸优化问题。此前所有分词算法均为贪心或基于局部统计，而该工作通过图与整数规划的桥梁，将全局优化目标引入分词，并用成熟的凸优化工具求解。这是方法论上的根本创新。
提供可证明的压缩下界与最优性认证。线性规划的解不仅给出一个上界（舍入后所得分词器的成本），还天然给出一个下界（LP 的最优值）。两者的差距衡量了当前解离全局最优有多远。实验表明，在 128k 以上的词表规模下，差距已缩小到 1% 以内，这证明了全局最优的逼近程度极高。
将图着色与网络流问题引入 NLP 分词。该问题形式化地定义了一般化 token 图，允许任意子串边，甚至可扩展至跨词边界、添加特殊 token 等约束，为后续研究提供了灵活且理论坚实的框架。

实验结果分析

实验在 ClimbMix400B 语料上训练分词器，词表规模从 8k 到 256k，以 BPE 为基线，考察压缩率、内在指标、语言模型 bits-per-byte（BpB）和 CORE 下游任务。

压缩与最优性：从 LP 求解统计中发现，随着词表增大， $\mathbf{c}$ 中取值为 1 的占比从 66% 升至 90% 以上，解的整体性增强。舍入后，Det 方案获得的 token 总数与 LP 下界非常接近，在 128k 和 256k 时差距均在 0.4% 以内；BPE 相比最优下界的差距也仅在 1%–3% 之间，但 ConvexTok 的 Det 几乎达到了最优。这说明在压缩维度上，BPE 已经相当不错，但全局优化的空间依然存在并已被充分挖掘。

内在指标：ConvexTok 在词汇利用率、类型-标记比、每行 token 数等指标上普遍优于 BPE，展现出更高效的编码。Rényi 熵上二者互有高低，无绝对优势。

语言模型性能：在 BpB 上，Det 方案在 12 层模型的所有词表尺寸下均胜过 BPE，且在更深模型的大多数设置下也保持微弱优势，表明压缩的改进能够转化为更好的似然度。CORE 下游任务结果则较为混合：虽然 ConvexTok 在平均分上不输于 BPE，部分词表尺寸甚至更好，但并没有一致的显著提升。这可能因为分词对下游任务的影响受模型容量、微调过程等多种因素干扰，压缩的最优性并不是下游性能的唯一决定因素。

稳定性：通过在不同随机子集上重训分词器并计算词表 Jaccard 相似度，发现 BPE 的词表稳定性高于 ConvexTok 的 Det 和 Bias 方案。Int 由于只包含 LP 认为“确定”的 token，稳定性最高。这表明全局优化方法对训练数据的分布更敏感，但可以通过 Int 方案在牺牲部分压缩的条件下换取稳定性。

实践应用建议与未来方向

对于实际场景中的分词器选型，本论文给出了清晰的指导：

若下游任务高度依赖语言建模的似然（如生成式预训练），建议使用 ConvexTok 的 Det 方案，它能稳定提升 BpB，且实现成本可控（LP 求解在几小时内可完成，推理时与 Unigram 同速）。
如果对词表稳定性有较高要求（如在多领域迁移或持续学习中），可优先考虑 Int 方案，或结合 BPE 初始化后再用 ConvexTok 精调。
因为压缩下界已经很小，单纯追求更高的训练数据压缩不再有意义。未来研究的重点应转向其他优化目标，如 Unigram 对数似然、Rényi 效率，甚至直接以模型困惑度为目标，将分词与语言模型联合优化。

技术上，当前 LP 仍受限于预分词（pre-tokenization）边界，若能扩展至跨边界 token（如 SuperBPE），结合超图结构，或许能进一步突破。另外，舍入方案的改进（如随机舍入、依赖上下文的自适应舍入）也值得探索。

总结与展望

ConvexTok 成功将分词器构建问题纳入凸优化框架，打破了贪心方法长期以来的统治地位。它不仅从理论上为“最优分词”提供了可计算的下界，而且在实践中以微小的代价换取了压缩和语言建模性能的稳定提升。尽管下游任务的增益尚不鲁棒，但该工作揭示了分词全局优化的有效性，并为未来围绕分词目标函数的创新铺平了道路。随着模型规模和训练成本的持续攀升，零成本或低成本的分词优化将成为大语言模型基础组件改进的一个重要分支，而 ConvexTok 无疑是这个方向上的一个里程碑式探索。