基于凸松弛的分词

Tokenisation via Convex Relaxations

arXiv: 2605.22821v1

论文信息

标题: Tokenisation via Convex Relaxations

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

发布日期: 2026-05-21

arXiv ID: 2605.22821v1

PDF 链接: 下载 PDF

3 分钟速览

  • 研究问题：如何突破传统分词算法（如 BPE）的贪心局部最优限制，找到全局近似最优的分词器（tokeniser），以提升语言模型的压缩效率与下游性能。
  • 核心方法：将分词器构建问题建模为线性规划（LP），利用凸优化工具求解，并通过三种舍入（rounding）方案将连续解转化为离散的词汇表。
  • 关键结果：基于 LP 的 ConvexTok 分词器在 128k 和 256k 词汇量下，压缩效果距理论下界不到 1%（表 2）；在 12 层 GPT 模型上，Det 舍入方案的 bits-per-byte（BpB）在 16k 及以上词汇量全部优于 BPE 基线（表 4）。
  • 主要局限：论文仅以压缩率为优化目标，未将 LP 框架推广到其他分词目标函数；且 ConvexTok 在不同数据子集上的词汇表稳定性弱于 BPE（图 3）。
  • 适合读者：从事大语言模型（LLM）预训练、数据压缩、数学优化（特别是整数规划与凸松弛）以及分词算法研究的技术人员。

论文背景和研究动机

分词（Tokenisation）是现代自然语言处理管道中的关键一环，它将原始字节序列转换为语言模型可消费的离散符号。当前主流的子词分词算法，如字节对编码（BPE）和 Unigram，本质上都是贪心算法：它们通过一系列局部最优决策（例如每次合并出现频率最高的一对符号）来构建词汇表，并不以全局视角考察最终词汇表的整体压缩效果或其他质量指标。

已有研究表明，分词器的压缩率与下游语言模型的性能存在一定相关性（Gallé, 2019; Zouhar et al., 2023a）。因此，寻找压缩最优的分词器便成为一个重要问题。然而，这一问题已被证明是 NP-hard（Kozma and Voderholzer, 2024; Whittington et al., 2025），意味着无法高效求得精确解，实践中只能依赖近似方法。

论文的核心动机在于：既然求解压缩最优分词器具有理论上的困难，能否利用数学优化领域的经典工具——线性规划与凸松弛——来获得一个 “可证明” 逼近全局最优的近似解，从而替代当前广泛使用的贪心算法？

核心方法和技术细节

为了形式化分词问题，作者首先将数据集 mathcalD\\mathcal{D} 中的全部字节串转换为一个有向无环图（Tokenisation Graph, 定义 3.1）。图中每个节点对应字符串中两个字节之间的位置，所有相邻节点间有 “字节边”（byte-edges），所有非相邻节点间有 “词符边”（token-edges）。每个词符边根据其跨越的字节子串被赋予一个 “颜色”（即一个候选词符）。词汇量预算 KK 对应选择 KK 种颜色，而一个合法的分词方案对应一条从全局起点到终点的路径，其使用边的颜色必须在所选颜色集合内或为字节边。

在此图上，压缩最小化等价于求解最短词符问题（Shortest Tokenisation Problem, 定义 3.2）。为对其进行优化，作者引入了一个整数规划（IP）模型（式 15）。模型中：

  • 变量包含自由边实例向量 f\mathbf{f}、定价边实例向量 p\mathbf{p} 与定价颜色向量 c\mathbf{c}，均为 0-1 整数变量；
  • 约束包括流守恒（保证路径合法）、词符实例必须属于已选词汇（p−Cc≤0\mathbf{p}-\mathbf{C}\mathbf{c}\le 0）以及词汇量预算（⟨1,c⟩≤K\langle 1,\mathbf{c}\rangle\le K）；
  • 目标是最小化路径总长度 ⟨1,p⟩+⟨1,f⟩\langle 1,\mathbf{p}\rangle+\langle 1,\mathbf{f}\rangle。

该 IP 等价于原问题（观察 3.4 与 3.5），但仍是 NP-hard。因而作者将变量的定义域从离散集合 0,1\\{0,1\\} 松弛为连续区间 [0,1][0,1]，得到线性规划（LP）（式 18）。该 LP 可在多项式时间内高效求解，但其最优解通常包含分数值，代表 “部分” 选取的词符或边。

为从连续解恢复出可用的离散分词器，作者设计了三种舍入方案（图 2）：

  • 确定性舍入（Det）：直接选取 c\mathbf{c} 中数值最大的 KK 个颜色置为 1，其余置 0。
  • 偏置舍入（Bias）：将 c\mathbf{c} 中每个颜色的值除以该词符的长度，按比值排序后截取前 KK 个。这有利于在得分相近时选择更短、泛化性可能更强的词符。
  • 纯整舍入（Int）：仅保留取值已经极接近 1（≥0.999）的颜色，其余均舍弃。该方案通常只选取远小于预算 KK 的核心词符。

舍入得到离散词汇表后，论文再通过标准最短路径算法计算最优词符实例向量，即实现最优编码。因此，ConvexTok 在推理阶段的效率与 UnigramLM 和 BPE 相当。

创新点和贡献

  1. 全新的分词优化框架：首次将分词器构建转化为线性规划问题并利用凸松弛求解，为这一 NP-hard 问题提供了具备理论下界的近似算法。相比 BPE 的贪心合并，ConvexTok 能直接逼近全局最优压缩效果。
  2. 可证明的接近最优性与认证能力：LP 的最优值天然构成所有可能分词器压缩长度的下界。论文通过比较不同分词器与 LP 下界的差距，认证了它们距真正最优解的距离。例如在 128k 词汇量时，Det 的积分间隙比（Integrality Gap Ratio）仅为 100.231%，即距理论最优不超过 0.3%（表 2）。
  3. 系统性的实证分析与见解：
    • 较大的词汇量（≥128k）下，LP 的解已高度整数化（表 1），意味着进一步改进压缩的空间已极小。
    • ConvexTok 的 Det 舍入在大部分设置下取得最优的 BpB，且趋势随词汇量增大变明显（表 4）。
    • 同时揭示出贪心的 BPE 出乎意料地已高度接近压缩最优（在 128k 仅为 100.385%），但 ConvexTok 仍能稳定带来增益。

实验结果分析

论文在 ClimbMix400B 数据集上以 BPE 为基线，系统评估了 ConvexTok 的三种舍入方案，主要发现如下：

压缩率与最优性认证（表 2）：Det 方案在所有词汇量下的压缩表现均最接近 LP 下界；在 16k 时差距为 0.285%，在 64k 时仅为 0.018%。BPE 的压缩差距虽然也极小，但始终位于 Det 与 Bias 之间。Int 方案由于词汇量受限，压缩差距较大，但在大词汇量下也进入 1% 以内。

分词器稳定性（图 3）：用数据集的不同子集重新训练分词器，BPE 的词汇表 Jaccard 相似度始终高于 ConvexTok，显示贪心策略对样本扰动更鲁棒。ConvexTok 内部中 Int 的稳定性最高，因其只保留对 LP 而言 “不可回避” 的词符。

内在指标（表 3）：Bias 方案在词汇利用率、平均词符排名、每行词符数等指标上通常优于 BPE，但 Rényi 熵表现混合。这说明仅为压缩而优化的 Det 虽压缩最优，但在某些语言学驱动的均匀性指标上可能不如偏向短词符的 Bias。

语言建模性能（表 4）：

  • BpB：对于 12 层 GPT 模型，从 16k 到 256k 词汇量，Det 的 BpB 全部低于 BPE（更低越好），如在 64k 时为 0.8438 vs BPE 的 0.8465。18 层和 24 层模型中 Det 同样在多数设置下领先。
  • CORE 基准：结果相对不一致。在 12 层 32k、64k 及 128k 设置下 ConvexTok 略微占优，但在 8k 时 BPE 略好。整体上 ConvexTok 保持具备竞争力，且在大词汇量下有优势趋势。

实践建议

对于计划将 ConvexTok 或其思想应用于生产级语言模型分词的团队，以下建议可供参考：

  1. 舍入方案的选择取决于目标：若极端追求压缩率和 BpB（即总 tokens 数最小化），应优先使用 Det 舍入，它在大词汇量下几乎达到 LP 下界。若下游任务涉及跨域泛化，或内在指标（如词汇利用率、词符长度分布）也同样重要，可考虑 Bias 舍入，其长度偏置有助于消除罕见的长词符。
  2. 词汇量预算建议设在 128k 以上：实验表明此时 LP 解已高度整数化，各舍入方案之间的差距缩小，ConvexTok 的相对优势也最为显著。同时，该区间内即便 BPE 性能已近于饱和，ConvexTok 仍可提供约 0.1–0.15 个百分点的 BpB 改进（表 4）。
  3. 利用 LP 下界进行质量认证：即便是使用 BPE 或其他分词器的团队，也可在自己的数据集上求解一次 LP，以获得压缩率的绝对下界。这提供了一个与分词器实现细节无关的量化比较基准，能帮助判断继续改进分词算法的潜在收益空间。
  4. 训练稳定性权衡：ConvexTok 的词汇表对训练集采样更为敏感。如果应用场景中需要频繁更新分词器或需保持多个版本间的词汇一致性，可采用 Int 舍入或混合方式（先取所有接近 1 的 “核心词符”，再用偏置/确定性方式补足余量），以提高可复现性。
  5. 计算开销：论文使用 NVIDIA CuOpt 求解 LP，耗时约在 3 至 15 分钟数量级（表 1），但其约束数达亿级，变量数也达约 1 亿。对于更大的训练集，建议先对数据进行抽样或裁剪低频边，以控制问题规模；在满足条件时可启用 GPU 加速的 LP 求解器以维持可接受的词表训练时间。