提出一种增量式BPE分词算法，支持流式处理且速度提升3倍。
Incremental BPE Tokenization
- 按字节增量维护前缀分词结果，每次处理耗时O(log²t)
- 整体复杂度O(n log²t)，在长文本上比Hugging Face快3倍
- 支持边处理边输出，适合LLM推理等低延迟场景
我们提出一种新型增量式字节对编码（BPE）分词算法。该算法最坏情况下每个输入字节处理时间为O(log²t)，总复杂度为O(n log²t)，其中n为输入长度，t为最大词元长度。算法增量维护输入文本每个前缀的BPE分词结果，实现由固定合并规则定义的标准BPE合并过程。这使得在流式场景中能高效进行部分分词。作为标准BPE的即插即用替代方案，该方法在性能上相比Hugging Face分词器提速约3倍，并在极端输入下显著降低OpenAI tiktoken的延迟。我们还引入一种主动输出算法，可在增量分词过程中尽早输出词元。结果表明，BPE分词可在保证强最坏情况复杂度的前提下实现增量处理，并在现代大语言模型流水线中带来实际延迟收益。
原文摘要 · Abstract (English)
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
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。