技术摘要：基于分割树的 Tokenization（ToaST）

问题陈述

Tokenization（分词）是自然语言处理中的基础步骤，然而现有方法通常依赖于贪婪启发式算法，这可能无法针对压缩率或下游任务性能进行优化。虽然字节对编码（BPE）通过贪婪合并策略最小化 token 数量，但它仅是一种启发式近似。先前的研究已证实，即使在有界字母表上，寻找最大化压缩率的 tokenizer 也是 NP 完全问题。此外，压缩率与下游任务性能之间的关系仍存在争议；虽然一些研究表明两者存在相关性，但另一些观点认为仅靠压缩率不足以解释 tokenization 的质量。现有的替代方案，如 UnigramLM 或 PathPiece，采用了不同的推理过程（例如，自上而下的消融法或最短路径推理），但仍面临全局优化和计算扩展方面的挑战。

方法论

作者提出了基于分割树的 Tokenization（ToaST），这是一种子词 tokenization 方法，它将候选 token 的构建与最终词汇表的选择解耦。该方法包含三个主要阶段：

1. 分割树构建

与自底向上构建 token 的 BPE，或自顶向下学习概率的 UnigramLM 不同，ToaST 为训练语料库中的每个唯一预分词（pretoken）独立构建一棵完整的二叉树，且该过程不依赖于任何词汇表。

• 预处理：使用正则表达式将训练数据分割为预分词。
• 分割逻辑：对于给定的预分词，算法递归地将其分割为两个非空部分。分割点的选择是确定性的，旨在基于语料库中预计算的 n-gram 统计信息，最大化生成的左右字节 n-gram 的最小计数（$\max \min(c_p, c_{p'})$）。
• 结构：此过程持续进行，直到叶子节点为单个字节。这些树的节点构成了所有候选 token 的集合。该构建过程独立于最终词汇表，且无需迭代训练。

2. 递归推理

给定词汇表 $V$，tokenization 通过分割树的递归下降执行：

• 从根节点（完整预分词）开始，算法检查当前节点是否在 $V$ 中。
• 如果节点在 $V$ 中，则将其作为 token 输出。
• 如果不在，则算法递归处理其两个子节点。
• 特性：此过程确保任何包含所有必要单字节的词汇表都能生成有效的 tokenization。从词汇表中移除一个 token 仅会迫使推理进一步深入树中，而不会像基于合并的方法那样对其他 token 产生级联效应。

3. 通过整数规划进行词汇表选择

核心创新在于将词汇表选择表述为**整数规划（IP）**问题，以最小化训练语料库上的总 token 数量。

• 变量：二进制变量 $x_i$ 表示候选 token $i$ 是否在词汇表中。二进制变量 $z_{jk}$ 表示分割树 $j$ 中的节点 $k$ 是否在推理过程中被输出。
• 目标：最小化输出 token 的总加权计数：$\min \sum_{j} c_j \sum_{k} z_{jk}$。
• 约束：
  • 词汇表大小：所选 token 的总和必须等于目标大小 $m$。
  • 覆盖性：对于从叶子到根的每一条路径，必须恰好选择一个节点（确保整个预分词被覆盖）。
  • 一致性：仅当节点在词汇表中（$x_i=1$）且其祖先节点均未被选中时，该节点才能被输出（$z_{jk}=1$）。
• 求解：将 IP 松弛为线性规划（LP）。在实践中，LP 松弛是“近整数”的，意味着解中包含极少的分数值。应用简单的舍入启发式算法即可获得整数解，该解在理论上被证明是近最优的（与全局最优解的差距可忽略不计）。

主要贡献

1. 新的 Tokenization 框架：ToaST 引入了一种基于分割树的方法，避免了 BPE 的贪婪近似和 UnigramLM 的特定推理约束。
2. 全局优化通过将词汇表选择表述为具有紧密 LP 松弛的 IP，ToaST 能够找到在给定分割树集合下全局最小化 token 数量的词汇表，而不是依赖局部的贪婪决策。
3. 可扩展性：该方法的扩展性与分割树数量呈二次方关系，允许在可行的训练时间内处理大型语料库（覆盖 99% 的预分词计数）。
4. 解耦设计：树构建（基于语料库统计）与词汇表选择（基于优化）的分离允许灵活的扩展，例如在不重新训练优化模型的情况下，融入形态学或字符级偏好。

实验结果

作者在 CulturaX 数据集上对英文文本评估了 ToaST，并将其与 BPE、WordPiece 和 UnigramLM 进行了比较。

• 压缩率：在词汇表大小为 40,960 及以上时，与所有基线相比，ToaST 将 token 数量减少了**11%**以上。该指标以每 token 字节数衡量。
• Token 分布：在词汇表大小为 65,536 时，与基线相比，ToaST 显著减少了“叶子”token（单字节回退）的频率，降低了 14–19 倍。相反，它产生了更多的“根”token（完整预分词），表明更好地保留了语义单元。
• Rényi 效率：ToaST 实现了更高的 Rényi 效率（$\alpha=2.5$），表明 token 分布更均匀，高频 token 更少，这通常与更好的下游性能相关。
• 下游性能：在训练 15 亿参数语言模型（nanochat）的实验中，ToaST 取得了最高的CORE 分数（22 个基准测试的平均值），比基线高出2.6% 至 7.6%。它显著优于 BPE 和 UnigramLM，并在 22 个单项任务中的 13 个任务中表现最佳。
• 优化质量：LP 松弛被发现有极佳的紧密性。在 128 个问题实例中，舍入后的整数解与 LP 边界之间的最大相对差距为 $5.76 \times 10^{-7}$，许多实例完全为整数。

意义与主张

该论文主张，ToaST 证明了使用全局优化框架直接针对压缩率优化 tokenization 的价值，而非依赖贪婪启发式算法。作者认为，卓越的压缩率带来了更大的有效上下文窗口，从而提升了下游性能。

该工作的意义在于：

• 实用性：尽管最优 tokenization 在理论上是 NP 完全的，但 LP 松弛使得该方法在计算上可行，并适用于大规模训练。
• 性能：实证结果表明，token 数量减少 11% 转化为语言模型性能（CORE 分数）的可衡量提升，支持了更好的压缩率与更好的模型效用之间存在相关性的假设。
• 灵活性：该架构允许未来的扩展，例如通过修改树构建层次结构来处理多字节字符或形态学分割，而无需改变词汇表优化逻辑。

作者指出了局限性，具体而言，实验仅在英文文本上进行，且针对非空格分隔语言，在聚合后的顶级预分词上进行训练的有效性可能会有所不同。他们还披露了使用大语言模型（LLM）进行代码实现和图表生成。