acceptodds
Under review as a conference paper at ICLR 2027

Online Tokenization with Optimal Delay in Near Linear Time

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 , 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 - 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 - improvement in throughput over tiktoken and - over tokenizers.

Primary area:
learning theory
Keywords:
tokenization, pretokenization, BPE

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_zCnkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Tokenization usually runs offline and stage by stage: special-token splitting, then regex pretokenization, then BPE, and each stage waits for the complete output of the previous one. This paper formalizes end-to-end online tokenization and introduces "delay" to measure how far a streaming output lags behind the longest safe token prefix. The authors also implement a practical streaming variant for tiktoken and HuggingFace tokenizers, reporting 7.9-34.8x lower time to the first tokenized token, roughly constant peak memory, and 2.4-7.0x throughput over tiktoken.

Critical strengths
  • The idea of running all tokenization stages online in one pipeline is natural.
  • The proofs about optimality and upper/lower bounds look theoretically solid.
Critical weaknesses
  • The organization of the paper is a bit messy. The paper is a sandwich: Section 2 gives the experimental results before the algorithm is described in Section 3, and the formal definitions needed to read those results (Section 1.1) come before both. Then most of the proofs and most of the experiment details are pushed into Appendices A-F, which mix theory (A-C, F) and experiments (D-E)
  • From an inference acceleration point of view, I think using "TTFT" here is not appropriate. In LLM serving, TTFT (time to first token) means the time from when the user sends the question to when the LLM produces the first answer token, and it is a key metric for user experience. In this paper TTFT only means the first token produced by the tokenizer, which does not match what the community means by this term.
  • Can the authors clarify the concrete scenarios where this work matters? (1) From the inference side, online tokenization is like chunked prefill (the whole prefill is chopped into finer pieces), but we cannot prefill token by token (that would be the online generation regime). How should online tokenization be combined with an LLM inference engine (vLLM, SGLang)? (2) From the training side, tokenization is a one-time cost. Compared with the huge cost of LLM pre-training/post-training, optimizing it does not seem to bring much benefit. It would also help to say for which input lengths and hardware the tokenizer is actually the bottleneck.
Questions for authors

see Weaknesses.

2 comments

We thank the reviewer for their careful reading and thoughtful engagement with our work. We are excited by the positive comments, and address specific weaknesses and concerns below.

The organization of the paper is a bit messy. The paper is a sandwich: Section 2 gives the experimental results before the algorithm is described in Section 3, and the formal definitions needed to read those results (Section 1.1) come before both. Then most of the proofs and most of the experiment details are pushed into Appendices A-F, which mix theory (A-C, F) and experiments (D-E)

Regarding the organization of the paper, we start with introducing the problem and then present results (both theory and empirical) to grasp the reader’s attention to continue into the technical overview and details. We find that especially for the audience of ICLR or any reader that is not a theoretician, seeing the empirical results early on is beneficial. As suggested, we will reorder the paper to include technical overview before empirical results. We begin with (informal) definitions so that readers unfamiliar with tokenization can understand the heart of the problem and grasp the motivation of our results, without getting bogged down in notation and formal definitions which we present for completeness in the appendix.As the space was limited, we provided the most important parts of our theoretical and empirical results in the body, and pushed the details in the appendix as is common practice. As suggested, we will move appendix F in front of appendix D (we originally put it at the end because it mostly discusses prior work and is provided only so that our paper is self-contained).

From an inference acceleration point of view, I think using "TTFT" here is not appropriate. In LLM serving, TTFT (time to first token) means the time from when the user sends the question to when the LLM produces the first answer token, and it is a key metric for user experience. In this paper TTFT only means the first token produced by the tokenizer, which does not match what the community means by this term.

Since our work focuses on tokenization, we focus on TTFT as the time when the first token is produced by the tokenizer to isolate the latency of the tokenizer from the inference engine. We can rename this metric (to for example TokTTFT) for clarity. While we believe integration with a full inference pipeline is an exciting future direction, it is outside of the scope of this work.

Can the authors clarify the concrete scenarios where this work matters? (1) From the inference side, online tokenization is like chunked prefill (the whole prefill is chopped into finer pieces), but we cannot prefill token by token (that would be the online generation regime). How should online tokenization be combined with an LLM inference engine (vLLM, SGLang)? (2) From the training side, tokenization is a one-time cost. Compared with the huge cost of LLM pre-training/post-training, optimizing it does not seem to bring much benefit. It would also help to say for which input lengths and hardware the tokenizer is actually the bottleneck.

We first want to point out that our paper’s primary contribution is theoretical: our goal is to precisely characterize in the worst-case (across all tokenization instances) how efficient online tokenization can be. LLM inference can be divided into many steps and tokenization is the first step which is our focus, and we acknowledge that tokenization is not necessarily the slowest or the most inefficient part (in terms of memory etc) of this process. However, as research works towards accelerating all the steps, it is important to know the limits of tokenization.

Online tokenization corresponds to chunked prefill, and while it does allow prefill token by token, we do not have to. While the tokenizer outputs tokens one at a time, chunked prefill can process chunks whenever a chunk is available. What online tokenization guarantees is that we minimize the latency of the first chunk.

While we don’t have an exact number on the input lengths or hardware specifications for which tokenization is hard, our experiments show that our online tokenizer exhibits meaningful advantages on several natural inputs.

We do not address training. Our work focuses on inference, as the tokenizer (the pretokenization regex, the BPE dictionary) are assumed to be trained, and our goal is to efficiently apply this tokenizer to an arbitrary input string.

Dear Reviewer zCnk, thank you again for your engagement and effort in reviewing our submission. As the discussion period is closing soon, we wanted to kindly follow up to ensure our rebuttal and revised manuscript have adequately addressed your concerns. In particular, we hope that we have justified the motivation for studying and characterizing when efficient online tokenization is possible.

Reviewer_sTYgOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
3(+2)
Read review
Paper summary

This paper investigates online tokenization, formalizing concepts such as maximum stable prefix and delay to prove that exact or near-zero-delay streaming tokenization is computationally intractable in polynomial time. Because naively chaining online pretokenization with online BPE introduces suboptimal delay due to regex lookback, the authors introduce a coupled algorithm that achieves theoretically optimal delay and space in near-linear time. Finally, they implement their tokenization empirically and achieve constant memory usage alongside substantial latency and throughput improvements over standard tokenizers.

Critical strengths

This work makes compelling contributions across both theory and systems. On the theoretical side, the paper provides a useful formalization of online tokenization, introduces valuable concepts like stable prefix and lookback, and uses its hardness result to motivate a practical relaxation that optimally solves the problem with strong space and time guarantees. On the systems side, the empirical implementation achieves 10x to 20x latency and throughput improvements over baseline tokenizers. While the latency reduction follows naturally from streaming, the throughput gain is a particularly insightful result, revealing that standard tokenization is memory-bound and that online processing substantially reduces data transfer overhead.

Critical weaknesses

The paper's presentation follows an unconventional structure, opening with empirical results before explaining the methodology and ending abruptly on the hardness proof without a concluding section. More importantly, there is a disconnect between the theoretical framework and the evaluated system. As noted in lines 2144–2146, the empirical implementation diverges from the theoretical composition algorithm, which emits accepted prefixes of candidate pretokens to an online BPE merging algorithm. Because the theoretical algorithm is not what is actually implemented and benchmarked, the theoretical results (despite being significant on their own) read as somewhat of a misdirection and require clearer reconciliation with the empirical results.

Questions for authors
  1. How exactly does the empirical implementation differ from the theoretical composition algorithm?

  2. What primarily drives the throughput gains over tiktoken? Is it the reduced memory traffic inherent to the online algorithm, or orthogonal engineering optimizations?

  3. Given that the O(mt)O(\mathsf{mt}) optimal delay bound is quite large, how much does this worst-case delay matter in practice?

2 comments

We thank the reviewer for their careful reading and thoughtful engagement with our work. We are excited by the positive comments, and address specific weaknesses and concerns below.

Critical Weaknesses

Regarding the presentation of the paper, our paper’s primary contribution is theoretical: our goal is to precisely characterize in the worst-case (across all tokenization instances) how efficient online tokenization can be. Therefore, our technical overview focuses on our theoretical, not empirical algorithms. In addition to the theory, our secondary goal was to obtain a practical algorithm for empirical use, that is inspired by our theoretical observations, and is actually fast in practice. It is often the case that for a problem, a lot of theoretical optimizations are unnecessary because they are not needed for the practical outputs, and instead other optimizations are needed. Regarding the organization of the paper, the original motivation was that results (both theory and empirical) would grasp the reader’s attention to continue into the technical overview and details. As suggested, we will reorder the paper to include technical overview before empirical results. We agree with the reviewer that providing a conclusion/discussion instead of the proof of the hardness result may be of greater value, and will reflect that in the final draft.

How exactly does the empirical implementation differ from the theoretical composition algorithm? What primarily drives the throughput gains over tiktoken? Is it the reduced memory traffic inherent to the online algorithm, or orthogonal engineering optimizations?

We describe the key differences between our main empirical implementation and the theoretical composition algorithm:

  1. In pretokenization, we only emit completed pretokens to the BPE phase, whereas the composition algorithm (Theorem 1.2) emits any accepted prefix.

In practice, pretokens are typically short, so this does not increase the delay significantly. We make this implementation choice because the BPE algorithm of prior work that we use is most efficient in the offline setting (see discussion in Jiang and Gong, 2026), and we note that this efficiency is just observed in practice.

  1. We simplify the regular expression used for pretokenization (see Section D.3).

This engineering optimization is the primary driver of our throughput gains. By simplifying the regular expression, we can use a more efficient regex engine to parse the input. The fixup step efficiently ensures that the behavior is identical to the complex regex engine.

  1. We use the simple O(nb) pretokenization algorithm instead of Lemma B.17.

We make this implementation choice as the lookback is small in practice. Furthermore, the simple algorithm has lower overhead than the worst-case optimal algorithm of Lemma B.17 which maintains a full transition table of the regex engine.

Given that the optimal delay bound is quite large, how much does this worst-case delay matter in practice?

Yes, the worst case delay is quite large (e.g. m can be ~100K) but as we discuss in practice, the lookback is typically quite small (see e.g. Claim D.2 and D.3 which shows that lookback is ~2 for practical patterns). Furthermore, in practice pretokens (e.g. words or numbers) are quite short, so even the practical variant that emits completed pretokens has delay bounded by the size of a given pretoken (e.g. average length of a word).

Thank you for the clarifications. My concerns have been addressed, and I will raise my score.

Reviewer_9jNTOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the problem of online tokenization. It seeks an efficient algorithm for incrementally processing text in a manner that does not require unbounded delays, such that no tokens are emitted by the tokenizer.

This is a solid algorithms paper with many detailed theoretical results and analyses. It also includes an efficient algorithm and implementation.

Critical strengths

S1. The paper formalizes online tokenization of a fairly complete tokenization pipeline: special-token splitting, pretokenization, and BPE. They give an efficient algorithm with O(mt)O(\mathfrak{m}\mathfrak{t}) delay. The paper also gives a conditional hardness result for substantially smaller delay. [One notable omission that appears in practical pipelines is the Unicode decoding (e.g., utf-8). I suspect this doesn't complicate things, but the authors may want to add a footnote about it in future revisions.]

S2. The paper combines solid theory with an efficient implementation and reports lower time-to-first-token and peak memory usage on some datasets.

S3. The paper identifies useful limitations of a direct composition of online subroutines, and its lower bounds clarify which space and delay costs can be inherent in the general problem.

Critical weaknesses

W1. The hardness result is parameterized over families of tokenization instances. It does not, by itself, rule out zero-delay processing for one fixed tokenizer such as GPT-2’s.

W2. The paper's framing would be stronger if it explained which workloads benefit from online tokenization. In ordinary turn-based chat, the full text is usually available before inference begins, so the value of emitting tokens to the LM earlier is not obvious.

W3. The authors adopt the simpler rank-by-rank procedure associated with "HuggingFace" semantics (Berglund and van der Merwe, 2023). [Berglund and van der Merwe show that it agrees with SentencePiece semantics for so-called "proper" merge lists, but the two can differ on improper lists. The paper’s assumption that each merge’s input IDs are smaller than its output ID appears to restrict the formal model to proper lists, assuming IDs follow merge order.] Stating this connection explicitly would clarify that the results also apply to SentencePiece on proper lists, but do not automatically cover arbitrary merge lists.

W4. [Not critical]. Missed citation https://arxiv.org/abs/2410.15696

Questions for authors

N/A

2 comments

We thank the reviewer for their careful reading and thoughtful engagement with our work. We are excited by the positive comments, and address specific weaknesses and concerns below.

The hardness result is parameterized over families of tokenization instances. It does not, by itself, rule out zero-delay processing for one fixed tokenizer such as GPT-2’s.

Yes, our paper’s primary contribution is theoretical: our goal is to precisely characterize in the worst-case (across all tokenization instances) how efficient online tokenization can be. Therefore, our main lower bound (Theorem 1.1) is for the worst case and exhibits a hard tokenizer instance. Our secondary goal is to develop a framework to characterize the performance of specific tokenizers. Towards this goal, we define and bound the lookback (see Claims D.2 and D.3) and observe that (1) this parameter controls the delay of online tokenization (Theorem 1.2) and (2) this quantity is typically a small constant (e.g. 2) for tokenizers such as GPT-2. For other tokenizers (e.g. CL100K and O200K) while the lookback is theoretically unbounded, it is still typically quite small on natural text: Claim D.3 shows that lookback is large only on specific inputs (e.g. long runs of whitespace following newline).

The paper's framing would be stronger if it explained which workloads benefit from online tokenization. In ordinary turn-based chat, the full text is usually available before inference begins, so the value of emitting tokens to the LM earlier is not obvious.

Even when the input is fully available, it is useful to be able to process it in a streaming fashion: this allows us to save memory, by not loading the full input if it is large, and reduce latency, by outputting tokens as the input is read, instead of waiting to read the whole input first. In a setting where a downstream process (e.g. prefill) is waiting on tokenization, this could lead to meaningful speedups. We believe that for example, it is an interesting future direction to investigate whether online tokenization can be combined with prefill to optimize inference. Similarly, our algorithm allows a large dataset to be tokenized on a machine with small memory (whereas offline tokenization algorithms do not allow this even when the dataset is fully present in storage).

The authors adopt the simpler rank-by-rank procedure associated with "HuggingFace" semantics (Berglund and van der Merwe, 2023). [Berglund and van der Merwe show that it agrees with SentencePiece semantics for so-called "proper" merge lists, but the two can differ on improper lists. The paper’s assumption that each merge’s input IDs are smaller than its output ID appears to restrict the formal model to proper lists, assuming IDs follow merge order.] Stating this connection explicitly would clarify that the results also apply to SentencePiece on proper lists, but do not automatically cover arbitrary merge lists.

We, like previous works on BPE (Jiang, Gong 26), follow the HuggingFace semantics (and as pointed out by the reviewer, the analysis extends to SentencePiece semantics on proper dictionaries). We believe that showing similar guarantees for SentencePiece semantics on arbitrary dictionaries is interesting future work, and will include this discussion in the updated draft.

[Not critical]. Missed citation https://arxiv.org/abs/2410.15696

We will address missing citations and minor concerns in the draft. For example, unicode decoding does not incur additional delay since the coding is prefix-free and can be unambiguously decoded.

Thanks for the response. I encourage the authors to add more some of the potential benefits (present and future) of online tokenization will help readers situated the work. I'll keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.