线性时间最优延迟的在线 Tokenization 算法

研究者提出一种近线性时间、延迟最优的在线 Tokenization 算法，并证明除非 P=NP，否则多项式时间算法无法将延迟再改进超过常数倍。基于 OpenAI tiktoken 和 HuggingFace tokenizers 的实现相比 tiktoken 及 gigatoken 实现首 token 延迟降低 7.9×-34.8×，吞吐量提升 2.4×-7.0×，内存占用近似恒定。