arXiv preprint ·
Online Tokenization with Optimal Delay in Linear Time
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Improved Combinatorial Auctions with and without Samples
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
Query Complexity of Densest Sub(hyper)graph Problems
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.