在线分词实现最优延迟：对 tiktoken 首 token 延迟最高快 34.8 倍
Online Tokenization with Optimal Delay in Linear Time
分词器也能流式跑了：新算法对比 tiktoken，首 token 延迟最高快 34.8 倍，内存还不随输入长度涨。
arXiv 论文（2610.19139）形式化了在线分词问题，提出延迟指标衡量输出滞后于最优解的程度。作者给出近线性时间算法，延迟在常数因子内最优，并证明除非 P=NP，多项式时间算法无法将延迟再改进超过常数倍。实现版本兼容 OpenAI 的 tiktoken 与 HuggingFace 的 tokenizers，以首 token 时间计延迟较 tiktoken 快 7.9 到 34.8 倍。吞吐量较 tiktoken 提升 2.4 到 7.0 倍，较 tokenizers 提升 15.8 到 38.1 倍，内存占用近似恒定、不随输入规模增长。该实现同样超过近期的 gigatoken 分词器。
Online Tokenization with Optimal Delay in Linear Time
Tokenization is an essential preprocessing step in almost all large language models (LLMs). One of the most popular frameworks is BPE tokenization, which consists of special token segmentation, pretokenization, and byte-pair encoding (BPE). However, existing algorithms are sequential, with each stage only processing complete output from the previous stage. In order to reduce latency and memory footprints, recent works (Jiang and Gong, ICML 2026) (Li, Yang and Mamouras, ASPLOS 2026) (Mamouras, Li and Yang, PLDI 2026) have initiated the study of online algorithms for subroutines such as pretokenization and BPE with a goal of streaming input to output as the input arrives online. However, the search for efficient online tokenization remains open. In this work, we formalize and resolve online tokenization. We introduce the notion of delay for online tokenization which characterizes the extent to which the algorithm output lags behind the (possibly computationally intractable) optimum. We give a near-linear time algorithm with optimal delay (up to constant factors). We complement this algorithm with a conditional lower bound: unless $\mathbf{P} = \mathbf{NP}$, there is no polynomial time algorithm that beats the delay of our algorithm by more than a constant factor. We implement a practical variant for tokenizers from OpenAI's tiktoken and HuggingFace's tokenizers. We obtain a $7.9\times$-$34.8\times$ latency advantage (measured as time to first token) over tiktoken (as well as the recent gigatoken tokenizer) and our implementation maintains approximately constant memory usage independent of input size. Our implementation also achieves a $2.4\times$-$7.0\times$ improvement in throughput over tiktoken and $15.8\times$-$38.1\times$ over tokenizers.
