Online Tokenization with Optimal Delay in Linear Time

Mina Dalirrooyfard; Christopher Ye

cs.DSOct 13, 2026

Online Tokenization with Optimal Delay in Linear Time

Authors: Mina Dalirrooyfard, Christopher Ye

Organizations: Morgan Stanley · University of California San Diego

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.

Figures & tables

Encoding	Github	English	Chinese
r50k	21.7 $\times$	17.8 $\times$	14.3 $\times$
p50k	19.2 $\times$	20.3 $\times$	13.8 $\times$
cl100k	34.8 $\times$	11.1 $\times$	7.9 $\times$
o200k	17.8 $\times$	11.8 $\times$	12.5 $\times$

Table 1: Time to first token (TTFT) speedup of our tokenizer over the better of tiktoken and gigatoken on each corpus.

Encoding	Github	English	Chinese
r50k	3.9 $\times$	2.7 $\times$	2.5 $\times$
p50k	4.2 $\times$	2.7 $\times$	2.4 $\times$
cl100k	4.4 $\times$	2.9 $\times$	2.8 $\times$
o200k	7.0 $\times$	4.8 $\times$	3.7 $\times$
GPT2	38.1 $\times$	36.0 $\times$	32.2 $\times$
Mistral	32.8 $\times$	27.9 $\times$	23.1 $\times$

Table 2: Throughput speedup of our tokenizer over tiktoken (top) and tokenizers (bottom).

Panel of Figure 1 — Figure 1: Illustration of $O(\mathfrak{m}\mathfrak{t})$ delay algorithm. Characters up to $\mathrm{out}$ are output in $P$ . $\mathrm{last},\mathrm{last}(2),\dots,\mathrm{last}(5),i$ are endpoints of pretokens if the current input $x_{\leqslant i}$ terminates. Square brackets describe the substring of the input maintained by each data structure. Here, we have $q=4$ .

Encoding	Dataset	tiktoken	gigatoken	Ours	Speedup
r50k	Github	10.91 (10.89-16.77)	10.70 (10.67-10.74)	0.49 (0.45-0.56)	21.7 $\times$
r50k	English	10.95 (10.94-10.99)	10.86 (10.85-10.89)	0.61 (0.51-0.84)	17.8 $\times$
r50k	Chinese	11.04 (11.00-11.11)	50.24 (46.48-172.62)	0.77 (0.72-0.85)	14.3 $\times$
p50k	Github	10.88 (10.86-10.91)	10.70 (10.68-10.72)	0.56 (0.49-0.61)	19.2 $\times$
p50k	English	10.95 (10.93-10.99)	10.83 (10.81-10.86)	0.53 (0.47-0.68)	20.3 $\times$
p50k	Chinese	11.01 (10.99-11.04)	46.63 (31.03-64.26)	0.80 (0.72-0.87)	13.8 $\times$

Table 3: Time to first token (TTFT) of all comparison of all tokenizers on tiktoken encodings measured in milliseconds (ms). We report the median TTFT over 30 runs for each row with upper and lower quartiles in the parentheses.

Figure 2: Peak RSS vs. input size on Github datasets. The blue line is tiktoken , the green line is gigatoken , while the red line is our algorithm.

Figure 3: Peak RSS vs. input size on English datasets. The blue line is tiktoken , the green line is gigatoken , while the red line is our algorithm.

Figure 4: Peak RSS vs. input size on Chinese datasets. The blue line is tiktoken , the green line is gigatoken , while the red line is our algorithm.

Encoding	Dataset	tiktoken	Ours	Speedup
r50k	Github	11.3 (11.3-11.3)	43.6 (43.5-43.7)	3.9 $\times$
r50k	English	17.8 (17.7-17.8)	47.7 (47.4-48.3)	2.7 $\times$
r50k	Chinese	15.0 (14.9-15.0)	38.0 (38.0-38.1)	2.5 $\times$
p50k	Github	10.8 (10.8-10.8)	45.0 (44.7-45.2)	4.2 $\times$
p50k	English	18.0 (17.9-18.0)	49.2 (48.8-49.4)	2.7 $\times$
p50k	Chinese	15.0 (14.9-15.0)	36.6 (36.5-36.7)	2.4 $\times$

Table 4: Throughput comparison of our tokenizer on tiktoken encodings measured in MiB/s. tiktoken is provided with a string as input and gives an array as output, both in memory. Our algorithm is provided with a file path as input and writes output to file. We report the median throughput over 10 runs for each row with upper and lower quartiles in the parentheses.

Model	Dataset	tokenizers	Ours	Speedup
GPT2	Github	1.2 (1.2-1.2)	45.7 (45.5-45.8)	38.1 $\times$
GPT2	English	1.4 (1.4-1.4)	50.4 (50.0-51.3)	36.0 $\times$
GPT2	Chinese	1.2 (1.2-1.2)	38.6 (38.4-38.6)	32.2 $\times$
RoBERTa	Github	1.1 (1.1-1.2)	40.7 (37.5-41.0)	37.0 $\times$
RoBERTa	English	1.3 (1.3-1.3)	46.2 (45.7-46.4)	35.5 $\times$
RoBERTa	Chinese	1.2 (1.2-1.2)	35.0 (34.7-35.2)	29.2 $\times$

Table 5: Throughput comparison of our tokenizer on tokenizers models measured in MiB/s. tokenizers is provided with a string as input and gives an array as output, both in memory. Our algorithm is provided with a file path as input and writes output to file. We report the median throughput over 10 runs for each row with upper and lower quartiles in the parentheses.

Encoding	Dataset	gigatoken (A)	gigatoken (S)	Ours (A)	Ours (S)
r50k	Github	178.3	26.9	185.5	117.5
r50k	English	331.1	44.6	298.7	181.9
r50k	Chinese	39.9	13.1	45.3	37.8
p50k	Github	188.7	32.2	191.5	126.8
p50k	English	329.2	44.6	297.6	180.0
p50k	Chinese	39.8	13.0	45.9	37.8

Table 6: Throughput comparison of optimized tokenizer on tiktoken encodings (MiB/s). gigatoken and our algorithm are provided with a file path as input. The array (A) column reports throughput when output is collected as array in memory, the stream (S) column reports when output is written to a temporary file. We report the median of 10 runs (quartiles omitted for space).

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: R50K reference pattern as a delayed-accept DFA. $X$ denotes non-whitespace characters as in Figure 6 ; $\sqcup$ = space, $w$ = other whitespace, $\$$ = end of input. The non-whitespace part ($ q_{0},sp,R,G $) is an ordinary DFA (boundary unconditional at run/contraction end); the whitespace part ($ W_{1},W_{2},c_{=},c_{-} $) is a delayed DFA.$ c_{=} $includes the last ws char;$ c_{-} $trims it (imposed by the rule$ \backslash\mathrm{s}^{+}(?!\backslash\mathrm{S}) $). Peeling fires only from$ W_{2} $, i.e. when the run of whitespace is at least$ 2$ characters long.

Panel of Figure 6 — Figure 6: R50K simplified pattern. $X$ denotes non-whitespace characters such as letters, digits, and symbols. In each case, the run continues on the same class $X$ ; $\sqcup$ = literal space, $w$ = other whitespace $(\backslash\mathrm{s}\setminus\sqcup)$ . $W$ accepts the maximal $\backslash\mathrm{s}^{+}$ run unconditionally (no lookahead).

Panel of Figure 7 — Figure 7: CL100K reference pattern. $G$ denotes the DFA to compute the first rule. Next, $L$ denotes the DFA to compute runs of letters with leading horizontal whitespace or punctuation (e.g. $[\hat{}\,\backslash\mathrm{r}\backslash\mathrm{n}\backslash\mathrm{p}\{L\}\backslash\mathrm{p}\{N\}]$ ). $D_{i}$ denotes the DFA to compute runs of $\leqslant 3$ digits. $Pu$ and $PN$ denote the DFA to compute runs of symbols followed by newlines. Priority: contraction, word, digit, punct, ws. $\mathrm{Wh}$ and $\mathrm{Wh}_{2}$ denote the first and subsequent horizontal whitespace respectively. $\mathrm{Wnl}$ denotes vertical whitespace/newline. From $\mathrm{Wnl}$ we always keep the last whitespace. From $\mathrm{Wh}_{2}$ , we trim the last character when a non-whitespace is encountered.

Panel of Figure 8 — Figure 8: O200K reference pattern. Words are case split, with upper case characters $U=[\backslash\mathrm{p}\{Lu,Lt,Lm,Lo,M\}]$ first, followed by lower case characters $l=[\backslash\mathrm{p}\{Ll,Lm,Lo,M\}]$ with an optional contraction suffix $G$ . Digits have run length $\leqslant 3$ . Symbols can have a leading space, followed by an arbitrary number of newlines. Horizontal whitespace followed by letters reaches the first two cases, while followed by any other non-whitespace character immediately outputs the single space. Remaining runs of whitespace either must end with a newline or leave a trailing space before the next whitespace character.

Panel of Figure 9 — Figure 9: O200K simplified pattern. Most of the DFA (except whitespace handling) is identical to Figure 8 . For whitespace, any run of whitespace that contains vertical whitespace/newline must end on vertical whitespace/newline. Otherwise, a run that contains only horizontal whitespace is matched as a single run.

Tokenization

See all 45 papers

Incremental BPE Tokenization
May 29, 2026Shenghu Jiang, Ruihao GongSubword Tokenization Byte-Pair Encoding
1Beihang University · 2SenseTime Research.
Tokenisation via Convex Relaxations
May 21, 2026Jan Tempus, Philip Whittington, Craig W. Schmidt +2Token Efficiency Linear Programming
ETH Zurich · Kensho Technologies
GPUTOK: GPU Accelerated Byte Level BPE Tokenization
Mar 3, 2026Venu Gopal Kadamba, Kanishkha JaisankarSubword Tokenization LLM Inference Acceleration
M.S. in Data Science, New York University

May 29, 2026J/K move · Enter open · S save

Incremental BPE Tokenization

Shenghu Jiang, Ruihao Gong

1Beihang University · 2SenseTime Research.

Subword Tokenization Byte-Pair Encoding Tokenization in Language Models Tokenization

Open paper AskPDF arXiv

We propose a novel algorithm for incremental Byte Pair Encoding (BPE) tokenization. The algorithm processes each input byte in worst-case

\mathcal{O}(\log^2 t)

time, leading to an overall complexity of

\mathcal{O}(n \log^2 t)

, where

n

is the input length and

t

is the maximum token length. The algorithm incrementally maintains BPE tokenization results for every prefix of the input text, implementing the standard BPE merge procedure defined by a fixed set of merge rules. This enables efficient partial tokenization in streaming settings. Functioning as a drop-in replacement for standard BPE, our approach achieves a speedup of up to

{\sim}3\times

over Hugging Face's tokenizers, and demonstrates significant latency reductions over OpenAI's tiktoken on pathological inputs. We further introduce an eager output algorithm that enables streaming output, emitting tokens as soon as token boundaries are determined during incremental tokenization. Overall, our results demonstrate that BPE tokenization can be performed incrementally with strong worst-case guarantees, while providing practical latency benefits in modern large language model pipelines. Code: https://github.com/ModelTC/mtc-inc-bpe

Abstract

Tokenization

Explore similar work

Incremental BPE Tokenization

Tokenisation via Convex Relaxations

GPUTOK: GPU Accelerated Byte Level BPE Tokenization