增量BPE分词

# 增量 BPE 分词

**来源：** https://arxiv.org/html/2605.30813

###### 摘要

我们提出了一种用于增量字节对编码（BPE）分词的新算法。该算法在最坏情况下以 O(log² t) 的时间复杂度处理每个输入字节，从而整体复杂度为 O(n log² t)，其中 n 是输入长度，t 是最大分词长度。该算法增量式地维护输入文本每个前缀的 BPE 分词结果，实现了由固定合并规则集定义的标准 BPE 合并过程。这使得在流式场景中能够进行高效的部分分词。作为标准 BPE 的即插即用替代，我们的方法相较于 Hugging Face 的 tokenizers 实现了高达约 3 倍的加速，并在病态输入上相较于 OpenAI 的 tiktoken 展现了显著的延迟降低。我们进一步引入了一种急切输出算法，支持流式输出，在增量分词过程中一旦确定分词边界即可立即发出分词结果。总体而言，我们的结果表明，BPE 分词可以在强最坏情况保证下增量执行，同时为现代大语言模型流水线提供实际的延迟优势。源代码可在 https://github.com/ModelTC/mtc-inc-bpe 获取。

字节对编码，分词，增量算法，LLM 效率，流式推理，最坏情况复杂度

## 1 引言

字节对编码（BPE）最初由 Gage（1994）(https://arxiv.org/html/2605.30813#bib.bib2) 作为数据压缩技术提出，在经 Sennrich 等人（2016）(https://arxiv.org/html/2605.30813#bib.bib1) 改编后，已成为现代大语言模型（LLM）事实上的分词方法。通过迭代合并频繁出现的相邻符号对，BPE 构建了一个紧凑的词汇表，平衡了表现力与计算效率。因此，高度优化的实现（如 Hugging Face 的 tokenizers (Hugging Face, 2026) (https://arxiv.org/html/2605.30813#bib.bib5) 和 OpenAI 的 tiktoken (OpenAI, 2026b) (https://arxiv.org/html/2605.30813#bib.bib6)）已成为现代 LLM 流水线的标准组件。图 1 (https://arxiv.org/html/2605.30813#S1.F1) 展示了现代 LLM 分词中使用的一个代表性流水线，其中 BPE 作为更广泛的预处理步骤序列中的核心阶段。

![图 1](https://arxiv.org/html/2605.30813/S1.F1)  
*图 1：现代 LLM 分词中的代表性流水线。原始文本经过一系列特定于模型的预处理阶段后，再对每个结果块应用 BPE 分词。我们的工作重点是在不改变正确性和周围阶段的情况下，使 BPE 阶段具备增量能力。*

然而，这些工具主要设计为离线流程：它们需要在完全观察到整个输入序列（或预先分割的块）后才能产生规范的分词结果。因此，分词和预填充是按顺序而非并发执行的，这在流式和长上下文推理中引入了额外的延迟。在算法层面，现有实现通常依赖基于堆的优先队列在整个输入上选择合并，导致其本质上是一种全局性表述，难以适应逐字节的更新。Berglund 和 van der Merwe（2023）(https://arxiv.org/html/2605.30813#bib.bib3) 对 BPE 的形式化揭示了一个结构性质：文本每个前缀的分词结果构成一个分词的前缀树。这一性质暗示了即时反馈和部分处理的可能性；然而，高效地利用它需要超出标准实现的算法支持。

在本文中，我们提出了一种新颖的**增量 BPE 分词**算法，能够实时高效维护每个前缀的 BPE 分词结果。该算法在最坏情况下以 O(log² t) 的时间复杂度处理每个输入字节，整体时间复杂度为 O(n log² t)，其中 n 是输入长度，t 是最大分词长度。我们在 Rust 中实现了该算法，作为核心 BPE 阶段的即插即用替代。基准测试结果（表 1 (https://arxiv.org/html/2605.30813#S7.T1)）显示，相较于 Hugging Face 的 tokenizers，端到端加速高达约 3 倍。此外，尽管 OpenAI 的 tiktoken 等现有工具在某些输入上表现出 O(n²) 的行为，我们的方法保持稳定的 O(n log² t) 代价，从而在病态情况下显著降低延迟（图 3 (https://arxiv.org/html/2605.30813#S6.F3)）。

除了原始速度和流式输入，我们引入了一种**急切输出**机制用于流式输出，一旦稳定的分词边界确定，即可发出分词结果。这使得分词能够与模型推理完全流水线化。当前系统的性能分析（附录 I (https://arxiv.org/html/2605.30813#A9)）显示，BPE 之外的其他阶段可能成为分词流水线的瓶颈，给流式输入和输出带来负担。凭借严格的最坏情况复杂度保证，这样的预分割在算法上可能是冗余的。此外，结合增量更新，该算法自然支持需要**全前缀访问**的场景，即需要所有前缀的分词结果，例如从分词的前缀树中推导注意力掩码用于“填充中间”（FIM）任务，而无需随机或启发式截断和重新计算。我们的结果表明，增量 BPE 分词在算法上可行且在实际中有益，同时具有**严格的最坏情况保证**和**精确的语义兼容性**。

#### 贡献。我们做出以下贡献：
- • 提出了一种增量 BPE 算法，具有严格的每字节 O(log² t) 最坏情况复杂度，确保与标准 BPE 精确等价以及严格的性能保证。
- • 提出的急切输出机制支持高效、实时的流式处理以及与模型推理的流水线化。
- • 我们在 Rust 中的高效实现可作为即插即用替代，相比当前最先进的工具实现高达约 3 倍的加速。
- • 使用我们的方法，传统流水线中仅用于规避全局 BPE 限制的阶段可以在不影响性能的情况下安全移除。
- • 我们的方法通过高效提供所有前缀的分词结果，原生支持全前缀任务（例如 FIM、分词修复），消除了启发式截断或重新计算的需要。

## 2 相关工作

字节对编码（Sennrich 等人，2016）(https://arxiv.org/html/2605.30813#bib.bib1) 已成为现代 LLM 事实上的标准，被 GPT-5 (OpenAI, 2026a) (https://arxiv.org/html/2605.30813#bib.bib10) 和 Qwen-3 (Qwen Team, 2025a) (https://arxiv.org/html/2605.30813#bib.bib18) 等最先进架构所采用。尽管 BERT (Devlin 等人，2019) (https://arxiv.org/html/2605.30813#bib.bib13) 中使用的 WordPiece (Schuster 和 Nakajima, 2012) (https://arxiv.org/html/2605.30813#bib.bib11) 和 T5 (Raffel 等人，2020) (https://arxiv.org/html/2605.30813#bib.bib14) 采用的 Unigram (Kudo, 2018) (https://arxiv.org/html/2605.30813#bib.bib12) 等替代方案也存在，但 BPE 仍是当前模型的主要选择。在模型架构方面，使用模式已经演变：早期模型通常对未分割的输入文本应用 BPE，而现代 LLM 越来越多地采用基于正则表达式的预分割和其他规范化手段来强制语言边界并划分输入。主流库以不同方式实现这些策略：Hugging Face 的 tokenizers (Hugging Face, 2026) (https://arxiv.org/html/2605.30813#bib.bib5) 使用优先队列提供通用实现，而 OpenAI 的 tiktoken (OpenAI, 2026b) (https://arxiv.org/html/2605.30813#bib.bib6) 专门针对基于正则表达式的方法，依靠分割来限制 BPE 合并的代价。尽管有这些优化，生产级分词仍然主要是**离线**的。无论是依赖全局队列还是预分割，规范的 BPE 分词通常在完整段可用后才执行。这种架构限制了通过细粒度流水线化分词与模型推理来隐藏延迟的能力。此外，依赖正则表达式引擎进行复杂度控制可能很脆弱，可能在病态输入（如大量重复）上引入性能退化或栈溢出。

在理论方面，Berglund 和 van der Merwe（2023）(https://arxiv.org/html/2605.30813#bib.bib3) 分析了不同 BPE 实现的形式语义，并指出其在分词级别截断下的一致性。这一观察意味着字符串前缀的分词结果在完整分词中是稳定的，暗示了增量处理的可能性。然而，他们的工作侧重于代数性质而非算法构造，并且没有解决在线更新所需的前瞻界的问题。在工程领域，诸如 crate bpe in rust-gems (GitHub, 2026) (https://arxiv.org/html/2605.30813#bib.bib7) 等实际实现（其技术由 van Antwerpen 和 Neubeck (2024) (https://arxiv.org/html/2605.30813#bib.bib8) 讨论）已采用 Aho–Corasick 自动机 (Aho 和 Corasick, 1975) (https://arxiv.org/html/2605.30813#bib.bib4) 进行增量分词。详细比较在附录 J (https://arxiv.org/html/2605.30813#A10) 中讨论。尽管展示了实际效用，这些方法通常缺乏形式化的最坏情况复杂度保证。我们的工作通过提供具有 O(log² t) 最坏情况更新时间的增量算法并保持与标准 BPE 的严格兼容性，弥合了这一差距。

## 3 增量 BPE 的结构基础

在本节中，我们建立算法的结构基础。我们首先形式化增量分词问题，明确定义**最后一个分词**的概念，并推导 BPE 的递归性质。然后，我们引入 BPE 词汇表的归一化表示以消除冗余。最后，我们构建**后继森林**和**后缀-后继树**，用于组织增量分词的搜索空间。这些结构为后续章节中提出的理论性质和搜索算法提供了拓扑基础。

### 3.1 预备知识与定义

令 Σ 为有限字母表，V ⊂ Σ⁺ 为有限词汇表。词汇表 V 由**原子分词**（其中 |t|=1）和**非原子分词**（其中 |t|>1）组成。字符串 s 的**后缀分词**定义为任何属于 V 且是 s 后缀的分词 t。**分词序列** φ = [t₁, ..., tₙ] 通过逆分词化 π(φ) = t₁...tₙ 映射回字符串。**词典**由有序列表的合并规则 D = [r₁, r₂, ..., rₘ] 定义。每条规则 rᵢ 指定一对相邻分词 (x, y)，它们将被合并为新的分词 z = xy。将规则 r 应用于分词序列 φ（记为 T_r(φ)）会从左到右依次替换相邻分词 x 和 y 的出现。字符串 s 在词典 D 下的完整 BPE 分词结果（记为 T_D(s)）通过首先将 s 映射为字符序列 φ₀，然后按优先级应用 D 中的规则得到：
T_D(s) = (T_{rₘ} ∘ ... ∘ T_{r₂} ∘ T_{r₁})(φ₀)   (1)
其中 r₁ 代表最高优先级的规则。注意，在此定义下，标准 BPE 与 SentencePiece (Kudo 和 Richardson, 2018) (https://arxiv.org/html/2605.30813#bib.bib9) 的语义不同。我们的分析基于标准 BPE 合并语义。关于两种分词语义的差异以及如何“规范化”标准 BPE 合并规则的详细讨论见附录 A (https://arxiv.org/html/2605.30813#A1)。在本文余下部分中，当词典上下文清晰时，我们省略下标 D，直接写作 T(s)。

### 3.2 问题形式化

#### 前缀一致性。
我们的增量方法依赖于 BPE 分词在分词级别截断下的一致性。正如 Berglund 和 van der Merwe（2023）(https://arxiv.org/html/2605.30813#bib.bib3)（注 3）所指出的，有效的 BPE 分词 T(·) 可以自由截断：剩余序列仍是其对应子串的有效分词。

###### 引理 3.1（前缀一致性）。
令 s 为字符串，φ = T(s) 为其分词后的分词序列。对于分词序列的任意真前缀 μ ⊂ φ，以下恒等式成立：T(π(μ)) = μ.

直观上，该引理成立是因为每个 BPE 合并步骤是一个**边界消除**过程，如图 4 (https://arxiv.org/html/2605.30813#A2.F4) 所示。我们在附录 B (https://arxiv.org/html/2605.30813#A2) 中提供了一个独立的正式证明。该引理确保增长字符串的分词可以建模为扩展某个较短前缀的先前有效分词，而非从头重新计算。

#### 最后一个分词。
基于这种一致性，我们定义**最后一个分词**，记为 θ(s)。对于任意非空字符串 s，θ(s) 是其 BPE 分词序列中的最后一个分词：θ(s) = last(T(s))。根据前缀一致性引理（引理 3.1 (https://arxiv.org/html/2605.30813#S3.Thmtheorem1)），由于移除最后一个分词后剩余部分仍是剩余字符串前缀的有效分词序列，我们可以递归地表示分词结果：
T(s) = T(s_pre) ⊕ [θ(s)]   (2)
其中 s_pre 是从字符串 s 中移除 θ(s) 的后缀字符串后的结果，⊕ 表示序列拼接。在复杂度方面，全前缀分词需要维护 Θ(|s|) 个状态。

#### 分词前缀树。
这种递归关系意味着所有前缀的分词结果自然形成一种层次结构。严格来说，这种结构构成一个森林，因为一个分词序列可以以任何有效分词开头。为了将其统一为单个**分词前缀树**，我们引入一个**虚拟根节点**表示空字符串 ε 的分词结果，它作为所有初始分词的共享根。虽然我们将所有前缀分词的空间可视化为这棵树，但严格维护显式结构是不必要的。相反，任何前缀的分词结果可以仅通过使用 θ(·) 进行**回溯**直到字符串开头（虚拟根节点）来检索。

#### 增量目标。
考虑一个增量场景：一个字符 c 被追加到当前字符串 s 上，得到 s' = sc。为了更新分词结果，我们只需要找到 θ(s') 的值。目标是在 s' 可能比 θ(s) 长得多的情况下识别出 θ(s')。