有界字母表上的分词是困难的

论文信息

标题: Tokenisation over Bounded Alphabets is Hard

作者: Violeta Kastreva, Philip Whittington, Dennis Komm, et al.

发布日期: 2025-11-19

arXiv ID: 2511.15709v1

PDF 链接: 下载 PDF

3 分钟速览

研究问题：已有工作证明无界字母表上的分词（tokenisation）是 NP 完全的，但实际分词器总是运行在固定大小的有界字母表（如字节、Unicode）上，该论文试图填补这一 “有界字母表” 情形的理论空白。
核心方法：作者采用计算复杂性归约技术，将经典的 NP 完全问题（如 3SAT、集合覆盖）在多项式时间内变换为有界字母表上的分词决策问题，以此建立下界并排除高效精确算法和近似方案。
关键结果：即使在最极端的二元字母表（ $n=2$ ）上，自底向上分词与直接分词两种自然变体都不仅是 NP 完全的，而且不存在多项式时间近似方案，除非 P = NP；更令人惊讶的是，直接分词在字母表大小仅为一元时依旧保持 NP 完全性。
主要局限：这是一项纯理论工作，未涉及实验验证；一元字母表的结果虽然在理论上揭示了分词难解性的内在障碍，但本身缺乏实用价值；论文也未给出正面的近似算法或启发式方案。
适合读者：从事自然语言处理、数据压缩或组合优化研究，特别是关注分词算法原理、文本预处理计算复杂度的研究者；对计算复杂性理论感兴趣的计算机科学从业者。

论文背景和研究动机

分词（tokenisation）是现代自然语言处理、代码生成以及多模态模型中的基础预处理步骤。它将原始文本切分为词元（tokens），为后续的语言模型提供离散的输入单元。两种最流行的分词范式分别是 “自底向上” 的字节对编码（BPE）和 “直接分词” 的 UnigramLM，前者通过反复合并最频繁的字符/词元对构建词表，后者则直接学习一个词表及其概率分布以最大化训练数据的似然。尽管这些启发式算法被广泛部署，其理论性质在很长一段时间内并不清晰。

近年的一系列工作证明了在无界字母表（即输入字符串可能由任意大小的字符集合构成）下的分词问题是 NP 完全的。这意味着除非 P = NP，否则不存在能够在多项式时间内为所有输入找到最优词表或最优合并序列的算法。然而，这一结论建立在一个偏离实际的假设之上：实际分词器几乎总是工作在固定大小的字母表上——例如，字节级分词器的字母表大小为 256，Unicode 分词器的字母表为约 15 万个码点，而分词合并操作只能组合已有的有限类别。因此，很自然地会问：当我们将字母表限定为有限大小 $n$ 时，分词问题是否会变得容易？会否因为字母表固定而出现高效算法甚至完全多项式近似方案（FPTAS）？

正是这一理论与实践的鸿沟驱动了本论文的研究。作者试图确认，即使在字母表被严格限制的 “温和” 条件下，分词的最优解是否依然具有难以逾越的计算壁垒。

核心方法和技术细节

论文同时考察了两种分词形式化变体，以覆盖主流实践算法的计算本质。

自底向上分词（Bottom‑up Tokenisation）：给定一个字符串数据集和预定义的词汇表最大规模 $k$ ，每次选择一个相邻符号对进行合并，形成一个新词元，并用该新词元替换所有该对的出现，直至词表达到规模 $k$ 或无法继续合并。此过程精确对应 BPE 算法的每次合并选择，但 BPE 采用的是贪婪策略，而该论文研究的是最优合并序列：是否存在一个长度不超过 $k$ 的合并序列，使最终序列长度（或其它目标）达到给定阈值。这一决策问题被记为 BottomUpTokenise。

直接分词（Direct Tokenisation）：给定字符串数据集和词表最大规模 $k$ ，要求直接选出一个最多包含 $k$ 个词元的词汇表，使得基于该词汇表对数据集进行某种最优编码（例如最短路径分词）后，压缩后的大小不超过某个界。这对应于 UnigramLM 训练中直接寻找最优词表的核心难题，记为 DirectTokenise。

技术工具的核心是多项式时间归约（polynomial‑time reduction）。为了证明问题对所有有界字母表都是难的，论文首先指出一个单调性事实：对 $n$ 元字母表的难解结果自动蕴含对任何更大字母表的难解结果。因此，只需要在最坏的可能情形——尽可能小的字母表上——建立 NP 完全性。作者于是将火力集中在二元字母表（ $n=2$ ）甚至一元字母表（ $n=1$ ）。

对二元字母表，论文构造了从 3SAT 到 BottomUpTokenise 的归约，以及从集合覆盖问题到 DirectTokenise 的归约。基本思路是将布尔变量赋值或集合元素的选定向编码为二元字符串上的合并操作或词表选择。例如，在 BottomUpTokenise 的归约中，每个子句和变量被映射为特定模式的 0/1 序列，合并操作被强制只能以某些顺序进行，从而使得能够达到目标压缩量的合并序列恰好对应于满足原 3SAT 实例的赋值。此类构造证明模型是 NP 困难的；而成员性（属于 NP）则通过展示一个合法合并序列或词汇表可以被非确定性猜测并在多项式时间内验证来确立。

更进一步，论文通过修正归约并调用 APX 难性理论，证明这两种问题在二元字母表上甚至不存在多项式时间近似方案（PTAS），除非 P = NP。也就是说，不仅最优解难以找到，连以一个任意接近 1 的比率近似最优压缩量都可能困难。

最令人震撼的结果出现在一元字母表上。当字母表仅由单个字符（比如全‘a’）组成时，任何字符串只是一连串的该字符，分词问题似乎退化到组合计数的层面。然而，论文证明 DirectTokenise 在一元字母表上仍然是 NP 完全的。其归约借助了经典数论问题——通过将数分解为不同大小的 “块” 并将压缩目标与子集和之类的困难问题挂钩，表明即便在如此简单的输入上，直接词表选择的决策空间依然复杂到足以容纳 NP 完全性。这一结果尤其有力地排除了 “难解性仅仅来自大字母表或编码复杂度” 的猜想，揭示出词表容量约束本身即构成根本性障碍。

创新点和贡献

本工作的首要贡献是将分词的理论难解性从理想化的无界字母表推广到了实践中的有界字母表，并给出了 “字母表大小” 这一参量的精确图景。具体创新点可归纳为：

闭合字母表缝隙：论文首次在固定字母表（尤其是极小字母表）上建立了自底向上和直接分词两种自然变体的 NP 完全性，填补了理论与应用之间的认知鸿沟。先前工作假设字母表无限，本工作证明即使字母表为 2，难度并未消失。
近似困难性：除了精确优化，论文进一步证明了二元字母表上两种分词问题不存在多项式时间近似方案（除非 P = NP）。这是更强的负向结果，它不仅封堵了精确算法的希望，也使得寻找具有任意逼近保证的高效算法变得同样不可能（见论文推论部分）。
一元字母表的极端归约：DirectTokenise 在一元字母表上保持 NP 完全性的证明尤为深刻。它将问题从可能复杂的字符交互中剥离出来，表明即便在完全同质的字符序列上，最优词表选择的组合困难依然存在，从而指明了困难的核心在于 “词表容量受约束” 这一离散选择性质。
对实践算法的理论解释：基于上述结论，作者指出 BPE 和 UnigramLM 等流行算法本质上只能是启发式或指数级耗时的精确算法，不存在多项式时间的最优保证。这为分词社区长期依赖启发式策略提供了坚实的计算辩护，并明确将未来方向指向近似算法的设计与分析。

局限与待解决问题

尽管论文提供了深入且优美的理论下界，但它本身的定位决定了若干固有的局限和后续待解问题。

首先，论文完全是理论复杂性分析，不包含任何实验评估或实用算法设计。结果给出了 “不可能” 的上限，却没有回答 “在何种程度上可能” 的问题。也就是说，对于实践中大规模部署的 BPE 或 UnigramLM，虽然在最坏情形下得不到最优解，但它们在典型或平均数据上的近似比究竟如何，仍是一个开放的经验问题。

其次，一元字母表的 NP 完全性证明更多是一种概念纯净性的宣示，其实际意义有限。如何将该结果反映到实际分词任务（例如中文分词、基因序列建模）中，论文未作延伸讨论。

此外，论文证明了常规近似方案的缺失，但没有触及参数化复杂性或超越最坏情形的分析。未来的工作可以探讨：当词表规模 $k$ 或输入字符串长度固定为某个参数时，是否存在固定参数可解（FPT）算法；或者能否基于数据分布假设（如幂律分布）设计出具有期望近似比保证的算法。

最后，论文对直接分词在一元字母表上的 NP 完全性给出了证明，但自底向上分词在一元字母表上的复杂程度是否依然 NP 完全，论文并未给出明确结论，这一缝隙有待后续研究填补。

总体而言，本工作为理解分词的计算难度树起了清晰的标尺，它提醒实践者：看似简单的文本预处理问题背后，潜伏着深刻的组合困难，而设计兼具效率与理论保证的近似分词算法，将是该领域走向健全的重要路径。