Incremental BPE Tokenization
作者: Shenghu Jiang, Ruihao Gong
分类: cs.CL, cs.DS
发布日期: 2026-05-29
备注: Accepted to ICML 2026 (Spotlight)
🔗 代码/项目: GITHUB
💡 一句话要点
提出增量BPE分词算法以提升流式处理效率
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 增量分词 字节对编码 流式处理 自然语言处理 高效算法
📋 核心要点
- 现有的BPE分词方法在流式处理时效率较低，无法满足实时应用的需求。
- 论文提出了一种增量BPE分词算法，能够逐步维护分词结果，支持流式输入的高效处理。
- 实验结果表明，该算法在处理速度上较Hugging Face的分词器提升了约3倍，并显著降低了延迟。
📝 摘要（中文）
我们提出了一种新颖的增量字节对编码（BPE）分词算法。该算法在最坏情况下以$ ext{O}( ext{log}^2 t)$的时间处理每个输入字节，从而实现整体复杂度为$ ext{O}(n ext{log}^2 t)$，其中$n$为输入长度，$t$为最大标记长度。该算法逐步维护输入文本每个前缀的BPE分词结果，实施由固定合并规则定义的标准BPE合并过程。这使得在流式环境中能够高效进行部分分词。作为标准BPE的替代方案，我们的方法在Hugging Face的分词器上实现了最高约3倍的加速，并在处理特殊输入时显著降低了OpenAI的tiktoken的延迟。此外，我们还引入了一种急切输出算法，能够在增量分词过程中一旦确定标记边界就立即输出标记。总体而言，我们的结果表明，BPE分词可以在强最坏情况保证下增量执行，同时在现代大型语言模型管道中提供实际的延迟收益。
🔬 方法详解
问题定义：现有的BPE分词方法在处理流式输入时存在效率低下的问题，尤其是在需要实时响应的应用场景中，无法快速更新分词结果。
核心思路：论文提出的增量BPE分词算法通过逐步维护每个输入前缀的分词结果，能够在每次输入字节时快速更新分词状态，从而实现高效的部分分词。
技术框架：该算法的整体架构包括输入字节的逐步处理、BPE合并规则的应用以及增量更新机制。主要模块包括字节处理模块、合并规则模块和输出模块。
关键创新：最重要的技术创新在于算法的增量处理能力，使得BPE分词不仅可以在整体输入完成后进行，还可以在输入过程中实时更新，显著提升了处理效率。
关键设计：算法在设计上采用了固定的合并规则，并通过急切输出机制实现了在确定标记边界后立即输出标记，确保了流式处理的实时性。
🖼️ 关键图片
📊 实验亮点
实验结果显示，增量BPE分词算法在处理速度上相比Hugging Face的分词器提升了约3倍，并在处理特殊输入时显著降低了OpenAI的tiktoken的延迟。这些结果表明该算法在实际应用中具有显著的性能优势。
🎯 应用场景
该研究的增量BPE分词算法具有广泛的应用潜力，特别是在实时自然语言处理、在线翻译和对话系统等领域。其高效的分词能力能够显著提升大型语言模型的响应速度和用户体验，未来可能在更多流式数据处理场景中发挥重要作用。
📄 摘要（原文）
We propose a novel algorithm for incremental Byte Pair Encoding (BPE) tokenization. The algorithm processes each input byte in worst-case $\mathcal{O}(\log^2 t)$ time, leading to an overall complexity of $\mathcal{O}(n \log^2 t)$, where $n$ is the input length and $t$ is the maximum token length. The algorithm incrementally maintains BPE tokenization results for every prefix of the input text, implementing the standard BPE merge procedure defined by a fixed set of merge rules. This enables efficient partial tokenization in streaming settings. Functioning as a drop-in replacement for standard BPE, our approach achieves a speedup of up to ${\sim}3\times$ over Hugging Face's tokenizers, and demonstrates significant latency reductions over OpenAI's tiktoken on pathological inputs. We further introduce an eager output algorithm that enables streaming output, emitting tokens as soon as token boundaries are determined during incremental tokenization. Overall, our results demonstrate that BPE tokenization can be performed incrementally with strong worst-case guarantees, while providing practical latency benefits in modern large language model pipelines. Code: https://github.com/ModelTC/mtc-inc-bpe