- 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
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.
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.
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).
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.
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.