你每天用的分词器，其实一直在"将就"——ConvexTok用凸优化证明：离最优只差1%

你每天用的分词器，其实一直在"将就"——ConvexTok用凸优化证明：离最优只差1%

想象一下，你正在打包行李箱出差。BPE分词器就像一个急性子的人——看到什么最常一起出现的东西，就先塞进一个袋子里，然后继续塞，直到袋子满了。至于最后箱子是不是装得最紧凑？它不在乎，因为它只看眼前这一步。

这就是当前所有主流分词器（BPE、Unigram）的工作方式：贪心算法，局部最优，全局听天由命。而ETH Zurich的团队说：等等，我们能不能用数学规划的方法，找到全局最优的分词方案？

分词：NLP管道里最被低估的环节

分词器是所有语言模型的第一道关卡。你输入一段文字，分词器把它切成一个个token，然后模型才能处理。切得好不好，直接决定了模型看到的"世界"清不清晰。

但分词这件事，本质上是一个NP-hard问题——在所有可能的切分方案中找到最优的那个，计算量是指数级的。所以大家一直用贪心算法凑合着过，BPE就是最典型的代表：反复合并最频繁的token对，直到词表达到目标大小。

问题是，BPE的贪心策略会产生很多"中间token"——比如"un"和"able"被合并成"unable"，但"un"本身可能并不是最优的选择。这些不必要的中间产物，白白占用了词表空间，压缩效率自然就打了折扣。

把分词变成一道数学题

ConvexTok的核心思路非常优雅：把分词问题形式化为整数规划（Integer Program），然后松弛为线性规划（Linear Program）来求解。

什么意思呢？想象你有一道选择题，每个选项只能是0或1（选或不选某个token）。这就是整数规划——变量必须是整数。但整数规划很难解。于是ConvexTok做了一个巧妙的松弛：允许变量取0到1之间的任意值（比如0.7），这就变成了线性规划，可以用成熟的求解器高效地找到精确解。

当然，松弛后的解可能包含"半选"的token（比如某个token被选了0.7），这在现实中没有意义。所以ConvexTok提出了三种取整方案，把这些"分数token"变回整数：

• Det（确定性取整）：直接四舍五入，简单粗暴
• Bias（偏置取整）：根据分数值加权随机取整，保留更多信息
• Top-k：保留分数最高的k个token

取整之后，从LP解构建出一个完整的分词器就水到渠成了。

离最优只差1%——而且我们能证明

这是ConvexTok最令人兴奋的发现。因为LP松弛提供了一个下界（任何分词器都不可能比这个值更好），我们可以用它来认证现有分词器离最优有多远。

实验结果令人震惊：在常见的词表大小下，BPE和ConvexTok都只比理论最优差不到1%！这意味着，在压缩率这个维度上，分词器的发展空间其实已经很小了。

但别急着说"那BPE就够了"——ConvexTok在多个内在指标上依然全面领先：

• 压缩率：Bias取整方案在所有词表大小下都优于BPE
• 词表利用率：ConvexTok的词表利用率更高，浪费更少
• Rényi熵：信息论指标上同样更优

下游效果：有进步但不稳定

在语言模型下游任务上，Det取整方案在bits-per-byte（BpB）指标上稳定优于BPE。但在CORE基准测试上，ConvexTok的表现时好时坏——有时明显领先，有时又差不多。

这其实不矛盾。分词器优化的是压缩率，而压缩率和下游任务性能之间的关系并不是严格线性的。一个压缩率更高的分词器，可能把某些语义边界切得更碎，反而干扰了模型学习。

为什么这篇论文重要？

ConvexTok的意义不只是"又一个更好的分词器"。它带来了三个重要的认知升级：

1. 分词可以是精确优化的：我们不必再接受贪心算法的局限，凸优化工具给了我们全局视角
2. 我们可以认证最优性：LP下界让我们第一次能说"这个分词器离最优差多远"，而不只是"这个比那个好"
3. 分词器的天花板可能已经到了：1%的差距意味着，在压缩率维度上，未来的突破可能需要换一个优化目标

这就像GPS导航——以前我们只能沿着一条路走到底，现在我们有了全局地图，不仅能找到更好的路线，还能告诉你"这条路已经是最优的99%了"。

论文链接：Tokenisation via Convex Relaxations

开源代码：github.com/JanTempus/tokenisation_lp