具有最优延迟的线性时间在线分词

arXiv:2610.19139v1 公告类型：交叉发布 摘要：分词是几乎所有大语言模型（LLMs）必不可少的预处理步骤。最流行的框架之一是 BPE 分词，它包括特殊词元分割、预分词和字节对编码（BPE）。然而，现有算法采用顺序处理方式，每个阶段只有在前一阶段输出完整结果后才能进行处理。为了降低延迟和内存占用，近期研究（Jiang and Gong, ICML 2026）（Li, Yang and Mamouras, ASPLOS 2026）（Mamouras, Li and Yang, PLDI 2026）开始探索预分词和 BPE 等子过程的在线算法，旨在输入在线到达时，以流式方式将其转换为输出。然而，如何实现高效的在线分词仍是一个开放问题。在本研究中，我们对在线分词进行了形式化定义并解决了这一问题。我们引入了在线分词的延迟概念，用于刻画算法输出相对于最优输出（其计算可能不可行）的滞后程度。我们提出了一种近线性时间算法，其延迟在常数因子范围内达到最优。我们还给出了一个条件性下界：除非 $\mathbf{P} = \mathbf{NP}$，否则不存在多项式时间算法，能够将我们算法的延迟缩短超过一个常数因子。我们针对 OpenAI 的 tiktoken 和 HuggingFace 的 tokenizers 中的分词器，实现了一个实用变体。相较于 tiktoken（以及近期推出的 gigatoken 分词器），我们在延迟方面（以首个词元生成时间衡量）获得了 $7.9\times$-$34.8\times$ 的优势，同时，我们的实现保持了近似恒定的内存占用，不受输入规模影响。在吞吐量方面，我们的实现相较于 tiktoken 提升了 $2.4\times$-$7.0\times$，相较于 tokenizers 提升了 $15.8\times$-$38.1\times$。