💬 NLP

Incremental BPE Tokenization

本文介绍了一种新型增量字节对编码（BPE）分词算法，该算法实现了 $\mathcal{O}(n \log^2 t)$ 的最坏情况时间复杂度，从而实现了高效的流式处理，且相比于 Hugging Face 的 tokenizers 和 tiktoken 等现有库，速度提升高达 3 倍。

原作者： Shenghu Jiang, Ruihao Gong

发布于 2026-06-01

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Shenghu Jiang, Ruihao Gong

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在读一本长篇著作，但你不是逐字阅读，而是“逐字节”阅读（文本的最小数字构建块）。你的目标是将这些字节组合成有意义的块，称为“Token”（标记）。这个过程被称为分词（Tokenization），而实现这一目标最流行的方法叫做字节对编码（Byte Pair Encoding, BPE）。

把 BPE 想象成一场 乐高（Lego） 游戏。你从单个积木块（字节）开始。游戏的规则是：“如果你经常看到两个特定的积木紧挨在一起，就把它们拼在一起，变成一个更大的自定义积木。”你不断重复这个过程，将成对的积木拼接在一起，直到你拥有了一堆由小积木和小型自定义结构组成的混合体。

问题：“等待观察”的瓶颈

目前，大多数玩这个乐高游戏的计算机程序都是**离线（Offline）*的。它们要求必须拿到整页*文本后，才能开始拼接积木。

类比： 想象你在搭建一面乐高墙，但你必须等待送货卡车把整面墙的积木全部送到，你才能开始把前两个积木拼在一起。在整个货运到达之前，你无法开始建造。
后果： 在现代 AI（如聊天机器人）中，这会产生延迟。计算机必须等待整个句子传输完毕后，才能开始处理第一个单词。这就像一条工厂流水线，每当新零件到达时都会停下来，等待整批货物到齐后才继续移动。

解决方案：“增量式”构建者

这篇论文的作者提出了一种更聪明、更高效的玩乐高游戏的方式。他们称之为增量 BPE 分词（Incremental BPE Tokenization）。

他们不再等待整辆卡车，而是在每个新字节到达时就立即将积木拼接在一起。

类比： 想象一位大师级建筑师，他只需看一眼新到的单个积木，就能瞬间知道它如何与之前的积木组合，并立即将其卡入到位。他不需要看到整面墙，就能知道当前部分的构造情况。
工作原理： 论文引入了一种巧妙的数学结构（“后继森林/Successor Forest”和“后缀-后继树/Suffix-Successor Tree”），它就像一张所有可能乐高组合的地图。当一个新字节进入时，算法利用这张地图，能够瞬间计算出将其与过去内容进行分组的最佳方式，而无需重新扫描整个文本。

核心特性与优势

1. 速度与稳定性（“不崩溃”保证）

主张： 旧方法在遇到奇怪模式（比如连续一百万个“a”）时有时会变慢或崩溃。新方法就像一件防弹衣；它保证无论文本多么古怪，都不会变慢。
结果： 它比目前的行业标准（Hugging Face 的分词器）快了高达 3 倍，并且能处理“病态”（异常）输入而不减速，不像 OpenAI 的 tiktoken 那样可能会陷入泥潭。

2. 流式输出（“急切”的大厨）

主张： 该方法不仅处理输入更快，而且还能立即输出完成的乐高积木。
类比： 想象一位大厨，他不会等到整顿饭都做好了才上菜。只要一道菜准备好了，他就会立刻装盘并递给你。这被称为**“急切输出（Eager Output）”**。
益处： 这使得 AI 可以在“阅读”你问题的同时就开始“思考”（生成回复），让对话感觉更加实时且流畅。

3. 即插即用替换

主张： 这种新算法被设计为一种即插即用的升级方案。你不需要重建整个 AI 系统；你只需将旧的分词工具更换为这个新的工具，它就能以完全相同的方式运行，只是速度更快。

总结

简单来说，这篇论文展示了一个用于 AI 文本处理的超高效、实时化的乐高构建器。

旧方式： 等待整个文本到达，然后一次性构建一切。（缓慢，容易产生延迟）。
新方式： 随着每一个字母的到达，实时构建一小部分。（快速、稳定，并允许你在输入的同时，AI 就能开始回应你）。

作者们通过数学证明了这种方法既快速又可靠，并且能完美契合 AI 理解文本的现有规则，为现代语言模型提供了显著的速度提升。

技术摘要：增量 BPE 分词

问题陈述

现代大语言模型（LLM）流水线高度依赖字节对编码（BPE）进行分词。然而，当前最先进的实现方式（例如 Hugging Face 的 tokenizers 和 OpenAI 的 tiktoken）主要设计为离线过程。它们要求在生成规范分词之前，必须完整观测到整个输入序列或预分段的块。这种架构上的局限性迫使分词与模型的预填充（pre-filling）阶段必须顺序执行，而非并发执行，从而在流式传输和长上下文推理场景中引入了延迟。

此外，现有的实现通常依赖于基于堆的优先队列，在整个输入上选择合并项，这导致其公式本质上是全局性的，难以适配字节级的增量更新。虽然一些工具使用基于正则表达式的预分段来限制合并成本，但这种方法可能非常脆弱，会导致性能下降或在处理病态输入（例如大量的字符重复）时出现栈耗尽，某些工具在这种情况下会表现出 $O(n^2)$ 的复杂度。

方法论

作者提出了一种全新的增量 BPE 分词算法，该算法能够实时维护输入文本每个前缀的 BPE 分词结果。该方法基于 BPE 的结构特性，并引入了以下关键算法创新：

1. 结构基础

前缀一致性（Prefix Consistency）： 利用 BPE 分词可以自由截断的特性，算法将增长中的字符串的分词建模为对先前较短前缀有效分词的扩展，而非重新计算。
末尾标记（Last Token, $\theta(s)$ ）： 算法侧重于维护当前字符串 $s$ 的“末尾标记”。完整的分词通过末尾标记序列进行隐式编码，并可通过回溯获取。
后继森林与后缀-后继树（Successor Forest & Suffix-Successor Tree）： 词表被归一化为规范标记，形成了一个拓扑结构，称为后继森林。对于任何输入，新末尾标记的搜索空间被限制在一个后缀-后继树内，该树组织了所有潜在的后缀标记。

2. 单调路径属性（The Monotonic Path Property）

其核心理论贡献是单调路径属性，该属性确立了对于任何输入字符串，能够作为最终标记的后缀标记集合在后缀-后继树中构成一条单一且连续的路径。这条路径锚定在根节点（原子标记）处，并延伸至真实的末端标记 $\theta(s)$ 。该属性将搜索空间从整棵树缩小到单条路径，从而实现了高效验证。

3. 算法实现

增量更新过程包含两个主要步骤：

搜索空间识别： 使用增强了持久化平方根平铺（persistent square-root tiling）的 Aho–Corasick 自动机，在 $O(1)$ 时间内识别最长后缀标记 $\tau(sc)$ ，从而定义边界后缀-后继树。
路径扩展搜索： 为了找到单调路径上最深的有效节点，算法采用了重心分解（Centroid Decomposition）。它遍历一个高度为 $O(\log |\tau|)$ 的预计算重心搜索树（CST）。在每一步中，它利用 DFS 线性化区间验证前缀末尾标记条件（检查可达性和优先级支配性）。这使得算法能够在 $O(\log |\tau|)$ 时间内确定有效路径的方向。

4. 饥饿输出机制（Eager Output Mechanism）

为了支持真正的流式传输，作者引入了饥饿输出算法。它识别分词树的“活跃前沿”（Active Frontier）——即可能成为未来标记之父的前缀范围。通过维护这些候选者的动态子图，系统可以在边界变得不变（即所有活跃路径都收敛到虚拟根的一个单一子节点）时立即发出标记，从而实现与模型推理的全流水线化。

核心贡献

算法复杂度： 所提算法处理每个输入字节的复杂度具有严格的最坏情况保证，为 $O(\log_2 t)$ ，其中 $t$ 是最大标记长度。因此，对于长度为 $n$ 的输入，总复杂度为 $O(n \log_2 t)$ 。
流式能力： 该方法可作为标准 BPE 阶段的掉换组件，在流式设置中实现高效的部分分词，而无需改变周围预处理阶段的正确性。
饥饿输出： 饥饿输出机制的引入允许实时流式传输并与模型推理进行流水线化，在边界解析后立即发出标记。
鲁棒性： 不同于可能在病态输入上退化至 $O(n^2)$ 的现有工具，该方法保持了稳定的性能保证。
全前缀支持： 算法天然支持需要访问所有前缀分词的场景（例如“填空”任务或标记修复），无需启发式截断或重新计算。

结果

作者使用 Rust 实现了该算法，并将其与 Hugging Face 的 tokenizers 和 OpenAI 的 tiktoken 进行了基准测试。

吞吐量： 该增量方法实现了高达 $\sim 3\times$ 于 Hugging Face 分词器的端到端加速，特别是在缺乏基于正则表达式预分段的场景下（例如 CodeLlama）。
病态输入下的延迟： 在具有大量重复内容的输入上，tiktoken 表现出与 $O(n^2)$ 复杂度一致的吞吐量下降。相比之下，所提方法保持了稳定的吞吐量，在这些病态案例中展示了显著的延迟降低。
饥饿输出开销： 与非饥饿版本的增量分词相比，饥饿输出机制引入了约 10% 的端到端吞吐量开销，作者指出这一成本可以在分词与 I/O 或推理进行流水线化作业的系统中得到摊销。

重要性与主张

本文证明了 BPE 分词可以在保持与标准 BPE 完全语义兼容的同时，以严格的最坏情况保证进行增量处理。

作者声称，他们的工作弥合了理论形式化（暗示前缀稳定性）与实际工程（一直依赖全局、离线处理）之间的鸿沟。通过提供一个 $O(n \log_2 t)$ 复杂度的算法，这项工作实现了：

降低延迟： 通过允许分词与模型推理进行完全流水线化，消除了流式推理中的顺序瓶颈。
系统鲁棒性： 通过缓解利用当前分词器 $O(n^2)$ 漏洞的算法复杂度攻击（例如通过构造输入进行的拒绝服务攻击）的风险。
流水线优化： 使某些（旨在限制全局 BPE 成本的）预分段阶段在算法上变得冗余，从而实现更简洁、更高效的流水线设计。

作者总结道，通过将严格的算法保证转化为实际的延迟收益，其方法为构建更鲁棒、响应更快且更节能的 LLM 流水线铺平了道路。