BPE分词是LLM推理的常见瓶颈，这个增量算法让流式场景提速3倍，做模型部署或实时推理的团队可以直接替换现有方案，值得一试。
研究人员提出了一种增量BPE分词算法，能够在流式场景中高效处理输入文本。该算法在最坏情况下每个字节的处理时间为O(log² t)，总体复杂度为O(n log² t)，其中n为输入长度，t为最大token长度。相比Hugging Face的tokenizers，该算法实现了约3倍的速度提升，并在病态输入上显著降低了延迟。此外，算法还支持流式输出，能在确定token边界后立即输出结果。这项研究为大型语言模型管道中的分词环节提供了实用的延迟优化。
Incremental BPE Tokenization
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