一句话：提出基于合并规则延迟界的流式 BPE 分词算法，以常数内存和线性时间完成分词。
大语言模型常需对海量文本进行实时 BPE 分词，离线算法易带来高延迟或高内存开销。论文将 BPE 分词视为序列到序列转换，针对有序合并规则列表提出“延迟”概念，即确定当前 token 前所需的前瞻量，并给出延迟上界。基于该上界，作者设计了一种流式分词算法：内存占用与输入文本长度无关，且时间复杂度与输入长度成线性。实验与现有 BPE 分词器比较表明，该算法在性能上表现良好。
Tokenization is an essential text preprocessing step in almost all large language models (LLMs), and byte-pair encoding (BPE) is a popular tokenization method used by models such as GPT, GPT-2, and RoBERTa. Since LLMs have many applications that require the fast processing of large amounts of data (e.g., real-time document summarization and analysis), offline tokenization algorithms may have high latency or prohibitive memory requirements. In this paper, we study BPE tokenization with a focus on providing a streaming implementation. A BPE tokenizer is specified with an ordered list of token merge rules, where each rule describes the merging of two adjacent tokens. We introduce the concept of delay for a list of BPE merge rules, which corresponds to the amount of lookahead needed before tokens can be finalized. We view BPE tokenization as a sequence-to-sequence transduction and show how to obtain a bound on delay. This bound enables streaming tokenization with a low memory footprint. We propose a novel streaming algorithm that uses a small amount of memory (independent of the input text) and has linear time complexity in the length of the input text. Our experimental evaluation shows that our algorithm performs well in comparison to existing BPE tokenizers.
@article{MamourasLY26,
title = {An Efficient Algorithm for Streaming BPE Tokenization},
author = {Konstantinos Mamouras and Angela W. Li and Yudi Yang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {PLDI},
year = {2026},
doi = {10.1145/3808330}
}