Optimal-Delay Online Tokenization Algorithm Achieves Up to 34.8x Lower Latency
Online Tokenization with Optimal Delay in Linear Time
Tokenization is usually treated as a solved preprocessing step, so the result that streaming tokenizers can hit provably optimal delay reframes a real bottleneck for serving latency, especially time-to-first-token. Teams building inference infrastructure can swap in this algorithm without changing tokenizer semantics, since it works with tiktoken and HuggingFace vocabularies. The lower-bound proof also signals that further constant-factor gains are unlikely, which narrows where optimization effort should go.
A paper on arXiv (2610.19139) formalizes online tokenization for large language models and introduces a delay metric measuring how far streaming output lags behind the optimum. The authors present a near-linear time algorithm with optimal delay, and prove conditionally that no polynomial-time algorithm can beat it by more than a constant factor unless P equals NP. They implement a practical variant compatible with OpenAI's tiktoken and HuggingFace's tokenizers. The implementation delivers 7.9x-34.8x better time-to-first-token latency than tiktoken and the gigatoken tokenizer, with roughly constant memory usage regardless of input size. Throughput improves 2.4x-7.0x over tiktoken and 15.8x-38.1x over HuggingFace's tokenizers.
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.