Online tokenization method cuts language model latency drastically
Online Tokenization with Optimal Delay in Linear Time
Data Structures and AlgorithmsMachine Learning
Summary
Tokenization splits text into chunks that AI models like those used in language apps can understand. Traditional methods take all the input before starting to work, causing delays. The authors developed a way to tokenize text as it comes in, with the smallest possible delay and fast speed. This new method works much faster and uses memory more efficiently than popular existing tools, making AI systems quicker and more responsive.
What this means in practice
- •For natural language processing engineers: Implement tokenization that starts outputting tokens immediately to reduce language model startup delay significantly.
- •For cloud ai service providers: Improve throughput and maintain steady memory use under variable load by applying efficient streaming tokenization.
- •For real-time transcription developers: Offer near-instant token streaming for live speech-to-text systems to enhance responsiveness and user experience.$Commercial implications: Enables competitive real-time transcription products with lower latency during audio input processing.
Authors
Mina Dalirrooyfard, Christopher Ye
Abstract
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.