贪心最长匹配分词联合优化

# 面向贪婪最长匹配分词化的联合优化
来源：https://arxiv.org/html/2607.23362
Adhiraj Singh Deepanshu Mody11footnotemark:1Ghina Al Shdaifat Hamza Alshamy 数据科学中心，纽约大学，纽约，NY，USA \{as19687,dm6262,gha2009,ha2486\}@nyu\.edu Adam Wiemerslage Varshini Reddy Craig W\. Schmidt Kensho Technologies，剑桥，MA，USA \{adam\.wiemerlsage,varshini\.bogolu,craig\.schmidt\}@kensho\.com

###### 摘要

近期研究表明，子词词表可以直接针对特定推理规则优化压缩，而非依赖像字节对编码（BPE）这样的贪婪合并启发式算法。例如，ToaST 针对分裂树推理，ConvexTok 针对最短路径推理。我们将此方法扩展到贪婪从左到右（GL2R）最长匹配解码，即 WordPiece 所使用的高速且广泛采用的推理规则。我们提出**面向贪婪最长匹配分词化的联合优化（JOLT）**，它将 GL2R 词表学习形式化为一个整数规划（IP），涉及词表选择变量和分段选择变量。关键要素是一组贪婪一致性约束，强制每个预词元的分段与所选词表下 GL2R 产生的分段完全一致，从而使优化后的词元计数等于部署时实现的计数。为了大规模求解该整数规划，我们使用线性规划（LP）松弛，仅将未解决的预词元升级到更高阶的分段。该松弛近乎整数：取整后的解在线性规划下界值的 0.008%–0.176% 范围内，确保了在训练范围内 GL2R 压缩的近乎最优性。同一界限揭示出 BPE 在训练范围内已经位于 LP 下界值的 1%–2% 范围内，证实该启发式算法对于 GL2R 推理已是近乎最优；JOLT 关闭了这一差距的 89.6%–99.4%。在四个训练范围（\(N\in\{100\text{k},200\text{k},300\text{k},400\text{k}\}\)）和两个词表大小（\(|V|\in\{32\text{k},64\text{k}\}\)）的保留验证集上，JOLT 相比 BPE 最多减少 0.78% 的词元，且收益随范围增大而增长。这些结果共同表明，BPE 与 LP 下界之间的大部分压缩空间可以通过针对推理对齐的词表优化来恢复。

## 1 引言

大多数 NLP 任务将分词器作为第一步，将文本转换为从固定词表中抽取的词元序列。字节对编码（BPE；Sennrich 等人，2016 (https://arxiv.org/html/2607.23362#bib.bib2)）是最常用的子词分词器之一；WordPiece（Wu 等人，2016 (https://arxiv.org/html/2607.23362#bib.bib11)；Schuster 和 Nakajima，2012 (https://arxiv.org/html/2607.23362#bib.bib10)）和 UnigramLM（Kudo，2018 (https://arxiv.org/html/2607.23362#bib.bib3)）也被广泛部署。BPE 最初作为通用压缩算法提出（Gage，1994 (https://arxiv.org/html/2607.23362#bib.bib13)），后来被用于 NLP（Sennrich 等人，2016 (https://arxiv.org/html/2607.23362#bib.bib2)），它通过重复合并最频繁的相邻词元对，直到达到目标大小，贪心地构建词表。生成更短的词元序列对语言模型有价值：它增加了给定上下文窗口中的文本量，并降低了推理成本。虽然压缩对下游准确率的影响仍有争议（Gallé，2019 (https://arxiv.org/html/2607.23362#bib.bib14)；Rust 等人，2021 (https://arxiv.org/html/2607.23362#bib.bib15)；Ali 等人，2024 (https://arxiv.org/html/2607.23362#bib.bib16)；Goldman 等人，2024 (https://arxiv.org/html/2607.23362#bib.bib17)；Schmidt 等人，2024 (https://arxiv.org/html/2607.23362#bib.bib18)），但其实际优势本身就使得压缩值得优化。

近期研究表明，词表训练不必局限于贪婪合并启发式算法：ToaST（Schmidt 等人，2026 (https://arxiv.org/html/2607.23362#bib.bib9)）和 ConvexTok（Tempus 等人，2026 (https://arxiv.org/html/2607.23362#bib.bib8)）表明，可以通过将词表训练形式化为整数规划（IP），将其松弛为线性规划（LP），并通过取整提取离散词表，直接优化压缩。¹¹精确的压缩导向训练在几种标准形式化中都是 NP 完全的（Whittington 等人，2025 (https://arxiv.org/html/2607.23362#bib.bib5)；Kastreva 等人，2026 (https://arxiv.org/html/2607.23362#bib.bib6)），因此语料库规模的工作求解 LP 松弛并取整得到固定词表，而不是优化完整的整数规划。这将分词器设计从启发式、过程驱动的训练重新定义为特定推理的优化问题。因此，不存在独立于推理规则的“最佳压缩分词器”的概念；最优性必须相对于推理规则来陈述。

贪婪从左到右（GL2R）最长匹配解码是一种简单快速的分词推理规则，WordPiece 最常使用。给定一个词表，GL2R 从左到右扫描输入，在每个位置发出从该位置开始的字节匹配的最长词表词元，并向前推进该词元的长度；由于词表中包含完整的单字节词元集合，这总是成功的，不会出现未知词元。Uzan 等人 (2024 (https://arxiv.org/html/2607.23362#bib.bib4)) 表明 GL2R 即使应用于由其他方法训练的词表也很有效。然而，目前还没有专门为 GL2R 设计的词表构建技术。我们开发了**面向贪婪最长匹配分词化的联合优化（JOLT）**，它遵循与 ToaST 和 ConvexTok 相同的高级方案（整数规划 → LP 松弛 → 取整得到固定词表），但专门针对 GL2R 推理建模，使优化后的词元计数等于部署时实现的计数。

实验上，在四个训练范围（\(N\in\{100\text{k},200\text{k},300\text{k},400\text{k}\}\)）和两个词表大小（\(|V|\in\{32\text{k},64\text{k}\}\)）中，JOLT 在保留文本上相对于 BPE 减少了最多 0.78% 的贪婪 L2R 词元计数，且更大的范围一致地带来相等或更好的压缩。除了压缩收益，LP 界限还提供了一个结构性诊断：训练范围内 BPE 的词元计数在 LP 下界的 1%–2% 范围内，揭示了 BPE 启发式算法在 GL2R 推理下已经是近乎最优的。JOLT 关闭了这一差距的 89.6%–99.4%，其取整后的词表在 LP 界限的 0.008%–0.176% 范围内，因此取整几乎不损失 LP 可实现的压缩。因此，JOLT 在保留验证集上相对于 BPE 的小幅领先反映了 LP 界限之上的空间有限，而不是取整的伪影。

## 2 JOLT 模型

JOLT 将词表学习形式化为一个关于两个耦合选择的联合整数规划：哪些候选词元进入词表，以及每个预词元的哪个候选分段被选中。在 GL2R 下，每个位置的最长匹配词表词元获胜，因此一个分段仅对于这样的词表才是 GL2R 可实现的：在任意分段边界处没有更长的词元侵入。显式地强制执行这一有效性条件（第 2.4 节 (https://arxiv.org/html/2607.23362#S2.SS4)）将词表选择变量和分段选择变量耦合在一起。由于候选分段的数量随预词元长度呈指数增长，JOLT 不会一开始就全部实例化，而是为每个预词元使用少量候选分段，并根据需要添加更多。

### 2.1 预词元、分段和代价

#### 预词元。

我们首先使用正则表达式²²我们使用 GPT-4o 正则表达式的长度受限版本。详见附录 C (https://arxiv.org/html/2607.23362#A3)。将训练语料分割为预词元，并按计数聚合相同的预词元。令 \(P\) 为训练数据中聚合后的预词元集合，每个预词元 \(p\in P\) 的频率为 \(c_p\in\mathbb{N}\)。我们使用字节级分词，因此定义 \(n_p=|p|\) 为预词元 \(p\) 的字节长度。

对于词表训练，我们保留计数最高的 \(N\) 个预词元；在下面的整数规划中，\(P\) 表示这个受限的 top-\(N\) 集合，包含计数 \(c_p\)，而不是完整的预词元词表。

#### 分段。

一个分段 \(s\) 将预词元 \(p\) 划分为相邻的非空候选词元。我们用 \(\|\) 直观地展示示例分段，例如分段 \(s=\texttt{ta}\|\texttt{ble}\) 用于预词元 \(p=\texttt{table}\)。分段 \(s\) 的**阶数**是划分中的片段（词元）数量。一个阶数为 \(r\) 的分段由在 \(n_p-1\) 个字节间隙中选择 \(r-1\) 个内部分割位置决定，因此对于 \(p\) 恰好有 \(\binom{n_p-1}{r-1}\) 个阶数为 \(r\) 的候选分段。对各阶求和表明总数随 \(n_p\) 呈指数增长：

\[\sum_{r=1}^{n_p}\binom{n_p-1}{r-1}=2^{n_p-1}\tag{1}\]

然而，在实际中，以压缩为导向的词表会用低阶分段处理大多数预词元，因此只需显式实例化 \(2^{n_p-1}\) 个候选分段中的一小部分。

为了避免指数级数量的潜在分段，我们只为每个预词元的被界定的阶数之内实例化分段。令 \(\kappa_p\) 表示当前为 \(p\) 实例化的最大分段阶数。对于给定的 \(\kappa_p\)，令 \(S_p\) 为 \(p\) 的分段选择的有限集合：所有满足 \(\mathrm{order}(s)\leq\kappa_p\) 的 \(s\)，加上一个退路 \(\mathcal{F}\)。退路本身不是 \(p\) 的分段；选择 \(\mathcal{F}\) 意味着当前实例化的分段都不够用，求解器希望得到阶数大于 \(\kappa_p\) 的分段。我们初始设置 \(\kappa_p=2\)，因此 \(S_p\) 只包含整个预词元、所有阶数为 2 的分段以及 \(\mathcal{F}\)；这些是 \(p\) 在第一轮中唯一的分段选项。当求解器为 \(p\) 选择 \(\mathcal{F}\) 时，\(\kappa_p\) 增加，下一个阶数分段被追加到 \(S_p\)（第 2.5 节 (https://arxiv.org/html/2607.23362#S2.SS5)）。因此，

\[|S_p|=\sum_{r=1}^{\kappa_p}\binom{n_p-1}{r-1}+1.\tag{2}\]

升级则只对选择了 \(\mathcal{F}\) 的预词元增加 \(\kappa_p\) 并丰富 \(S_p\)（第 2.5 节 (https://arxiv.org/html/2607.23362#S2.SS5)），而非一开始就为每个 \(p\in P\) 实例化高阶分段。这种选择性升级避免了不必要地实例化高阶分段，减少了线性规划规模和求解时间。

#### 词元和代价。

训练在连续的**轮次**中进行。在每一轮中，每个预词元 \(p\) 有一个固定的分段阶数限制 \(\kappa_p\)，并有一个固定的有限集合 \(S_p\)。我们构建并求解整数规划（或其 LP 松弛）；选择退路 \(\mathcal{F}\) 的预词元会触发增加 \(\kappa_p\) 并在下一轮之前重建（第 2.5 节 (https://arxiv.org/html/2607.23362#S2.SS5)）。

图 1 (https://arxiv.org/html/2607.23362#S2.F1)(a) 给出了预词元 \(p=\texttt{table}\)（\(n_p=5\)）的示例。共有 \(2^{n_p-1}=16\) 个潜在分段，但初始 \(\kappa_p=2\) 时只实例化了六个选择：整个预词元、四个阶数为 2 的分段以及 \(\mathcal{F}\)。当一个预词元选择了退路，其 \(\kappa_p\) 在下一轮增加 1，并追加这些新候选（第 2.5 节 (https://arxiv.org/html/2607.23362#S2.SS5)）。图 1 (https://arxiv.org/html/2607.23362#S2.F1)(b) 显示了当 \(\kappa_p\) 增加到 3 时新增的六个阶数为 3 的分段；只有当 \(\kappa_p\) 达到 \(n_p\) 时，所有 \(2^{n_p-1}\) 个分段才进入 \(S_p\)。

(a) 第 1 轮（实例化 6 个 / 可能 16 个）

| 变量 | 可视化 | \(\mathrm{cost}(p,s)\) |
|---|---|---|
| \(z_{\texttt{table},\,\texttt{table}}\) | table | 1 |
| \(z_{\texttt{table},\,\texttt{t}\,\|\,\texttt{able}}\) | table | 2 |
| \(z_{\texttt{table},\,\texttt{ta}\,\|\,\texttt{ble}}\) | table | 2 |
| \(z_{\texttt{table},\,\texttt{tab}\,\|\,\texttt{le}}\) | table | 2 |
| \(z_{\texttt{table},\,\texttt{tabl}\,\|\,\texttt{e}}\) | table | 2 |
| \(z_{\texttt{table},\,\mathcal{F}}\) | — | \(\kappa_p{+}1\) |

(b) 如果退路在第 1 轮被选择则添加（六个新阶数为 3 的分段）

| 变量 | 可视化 | \(\mathrm{cost}(p,s)\) |
|---|---|---|
| \(z_{\texttt{table},\,\texttt{t}\,\|\,\texttt{a}\,\|\,\texttt{ble}}\) | table | 3 |
| \(z_{\texttt{table},\,\texttt{t}\,\|\,\texttt{ab}\,\|\,\texttt{le}}\) | table | 3 |
| \(z_{\texttt{table},\,\texttt{t}\,\|\,\texttt{abl}\,\|\,\texttt{e}}\) | table | 3 |
| \(z_{\texttt{table},\,\texttt{ta}\,\|\,\texttt{b}\,\|\,\texttt{le}}\) | table | 3 |
| \(z_{\texttt{table},\,\texttt{ta}\,\|\,\texttt{bl}\,\|\,\texttt{e}}\) | table | 3 |
| \(z_{\texttt{table},\,\texttt{tab}\,\|\,\texttt{l}\,\|\,\texttt{e}}\) | table | 3 |

图 1: 预词元 \(p=\texttt{table}\)（\(n_p{=}5\)）的实例化分段 \(S_p\)。(a) 第 1 轮（\(\kappa_p{=}2\)）：整个预词元、四个阶数为 2 的分段和退路 \(\mathcal{F}\)。(b) 第 2 轮：当退路在第 1 轮被选择时，添加六个阶数为 3 的分段（第 2.5 节 (https://arxiv.org/html/2607.23362#S2.SS5)）。

令 \(B\) 表示所有 256 个单字节词元的集合，这些词元始终保留在提取的词表中（公式 8 (https://arxiv.org/html/2607.23362#S2.E8)），以避免未知词元。对于每个 \(p\in P\) 且非退路的 \(s\in S_p\)，令 \(E_{p,s}\) 为分段 \(s\) 所使用的不同词元字符串（字节子序列）的集合。该轮的全局**候选词元集合**为

\[T\;=\;B\;\cup\;\bigcup_{p\in P}\;\bigcup_{s\in S_p\setminus\{\mathcal{F}\}}E_{p,s}.\tag{3}\]

元素 \(t\in T\) 是字节字符串；每当任何 \(S_p\) 增长时，新的分段可能引入当前 \(T\) 中不存在的词元字符串，因此在下一个 LP 求解前，\(T\) 会被**重新计算**。

对于非退路分段，\(\mathrm{cost}(p,s)\) 等于 \(s\) 的阶数（\(s\) 下的词元计数）。退路通过一个阶段相关的代价进入目标函数：

\[\mathrm{cost}(p,\mathcal{F})=\begin{cases}
\kappa_p+1, & \text{中间轮次},\\
n_p, & \text{最终重新定价轮次},
\end{cases}\tag{4}\]

在中间轮次中，\(\mathrm{cost}(p,\mathcal{F})=\kappa_p+1\) 故意比当前实例化的阶数 \(\leq\kappa_p\) 的分段中最大的代价多一个词元，因此任何非退路分段严格比 \(\mathcal{F}\) 更便宜。第 2.5 节 (https://arxiv.org/html/2607.23362#S2.SS5) 使用此定价来决定何时丰富 \(S_p\)；最终轮次设置 \(\mathrm{cost}(p,\mathcal{F})=n_p\)，使得一旦 \(S_p\) 收敛，所报告的分数反映任何剩余退路预词元在 GL2R 下的最坏情况词元计数。

### 2.2 决策变量和目标函数

#### 词表选择变量。

对于每个候选词元 \(t\in T\)，定义

\[x_t\in\{0,1\}\quad\forall t\in T,\tag{5}\]

其中 \(x_t=1\) 表示词元 \(t\) 在词表中。例如，对于预词元 table，\(x_{\texttt{tab}}=1\) 表示 tab 全局可用。