在这篇文章中，我将展示一种算法，该算法能够在某些场景下计算出最佳分词器。这个结果很酷，因为最佳分词在理论上是无法处理的，但在实践中似乎是可以解决的。我的发现与旅行推销员问题（TSP）上的各种结果非常相似，即使是困难的实例也可以通过切割平面技术获得最佳解决方案。我想强调的是，尽管这个结果很酷，但有几个原因使其不一定有用。首先，现有的技术已经在某种程度上接近最佳（通常在1%以内）。其次，即使一个分词器在训练数据上是最佳的，当在保留的测试数据上进行评估时，它可能无法像其他分词器一样很好地推广。最后，低效的分词器基本上是可以接受的：您可以通过稍微增加词汇量来支付较低效分词器的成本。尽管有上述警告，我在这个项目中玩得非常开心，我希望其他人也会对推动这一问题的前沿感兴趣。 背景：分词器 前沿的LLM通常是在称为token的整数序列上训练的。每个token对应某个字节序列，这些字节序列通常对应于常见单词。例如，在GPT-5分词器中，token 290对应字节“ the”，而6602对应“ token”，因此文本“ the token”可以编码为序列[290，6602]。从token到字节的映射，称为“词汇”，是在LLM训练之前就固定的。通常，我们会尝试找到一个压缩训练数据切片的词汇。尤其是，我们希望选择一个固定大小的词汇，以最小化编码数据所需的token数量。寻找这种词汇的主要技术是字节对编码（BPE），这是一种已有几十年历史的贪婪压缩算法。 作为整数线性编程的分词 在最近的一篇论文中，Tempus等人将分词与整数线性编程关联起来。他们方法的基本思想是将整个数据集的分词表示为一组整数变量。在这种表述中，每个可能的词汇条目都有一个“颜色”变量。特别地，我们为数据集中每个唯一的子字符串创建一个颜色变量。如果相应的字节序列在词汇中，则颜色变量为1，反之为0。我们添加一个约束，以强制颜色变量的总和等于目标词汇大小。颜色对应于某些字节序列，但给定的字节序列可能在整个数据集中多次出现。对于每个颜色的出现，存在一个单独的“边”变量。这些边共同工作以编码数据集的实际分词。如果一条边为1，则该边的相应token在特定位置使用。我们的线性程序的目标是最小化所有边变量的总和，即用于编码数据集的token数量。例如，在下面的图中，我们将单词“Queue”分词为tokens [“Q”，“ue”，“ue”]。我们可以选择将其分词为[“Qu”，“e”，“ue”]，但那并不是当前ILP解所指示的分词，因为初始“Qu”和“e”边的边变量都是0。我们从两个方面约束线性规划。首先，如果token不在词汇中，我们无法使用它。为此，我们将每个边变量的约束设置为小于或等于其对应的颜色变量。其次，我们希望确保以恰好一种有效的方式对数据集进行分词。为此，我们添加流约束：对于数据集中的每个字节位置，我们希望流入该位置的边的总和等于流出该位置的边的总和，边界位置除外。对于第一个和最后一个位置，我们希望流出或流入为1。在整数解中，您可以将流约束视为断言以下内容：任何一条边流入的点必须有一条边流出，除了第一个和最后一个位置。如果所有变量都是整数并约束在[0，1]之间，则该线性程序足以编码最佳分词。然而，由于我们无法有效地解决任意整数线性规划，Tempus等人将ILP放松为连续线性程序，并使用经过良好优化的求解器来解决。连续线性程序的解通常不是整数的。我们可以在下面看到这个例子，其中我们有单词“Queue”的两个重叠分词：要么我们将其编码为[“Q”，“ue”，“ue”]，要么作为[“Qu”，“e”，“ue”]。这个解的问题在于我们的颜色变量总和为2.5，但我们实际上使用了四种颜色，因此我们实际没有找到大小为3的最佳词汇。通常，我们可能会得到的非零颜色变量比我们目标的实际词汇大小要多得多。Tempus等人提出通过几种不同的方式对颜色变量进行 "取整"，以达到整数解决方案。