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 P=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×-34.8× 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×-7.0× improvement in throughput over tiktoken and 15.8×-38.1× over tokenizers.
Figures & tables
Encoding
Github
English
Chinese
r50k
21.7 ×
17.8 ×
14.3 ×
p50k
19.2 ×
20.3 ×
13.8 ×
cl100k
34.8 ×
11.1 ×
7.9 ×
o200k
17.8 ×
11.8 ×
12.5 ×
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 ×
2.7 ×
2.5 ×
p50k
4.2 ×
2.7 ×
2.4 ×
cl100k
4.4 ×
2.9 ×
2.8 ×
o200k
7.0 ×
4.8 ×
3.7 ×
GPT2
38.1 ×
36.0 ×
32.2 ×
Mistral
32.8 ×
27.9 ×
23.1 ×
Table 2: Throughput speedup of our tokenizer over tiktoken (top) and tokenizers (bottom).
Figure 1: Illustration of O(mt) delay algorithm. Characters up to out are output in P . last,last(2),…,last(5),i are endpoints of pretokens if the current input x⩽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 ×
r50k
English
10.95 (10.94-10.99)
10.86 (10.85-10.89)
0.61 (0.51-0.84)
17.8 ×
r50k
Chinese
11.04 (11.00-11.11)
50.24 (46.48-172.62)
0.77 (0.72-0.85)
14.3 ×
p50k
Github
10.88 (10.86-10.91)
10.70 (10.68-10.72)
0.56 (0.49-0.61)
19.2 ×
p50k
English
10.95 (10.93-10.99)
10.83 (10.81-10.86)
0.53 (0.47-0.68)
20.3 ×
p50k
Chinese
11.01 (10.99-11.04)
46.63 (31.03-64.26)
0.80 (0.72-0.87)
13.8 ×
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 ×
r50k
English
17.8 (17.7-17.8)
47.7 (47.4-48.3)
2.7 ×
r50k
Chinese
15.0 (14.9-15.0)
38.0 (38.0-38.1)
2.5 ×
p50k
Github
10.8 (10.8-10.8)
45.0 (44.7-45.2)
4.2 ×
p50k
English
18.0 (17.9-18.0)
49.2 (48.8-49.4)
2.7 ×
p50k
Chinese
15.0 (14.9-15.0)
36.6 (36.5-36.7)
2.4 ×
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 ×
GPT2
English
1.4 (1.4-1.4)
50.4 (50.0-51.3)
36.0 ×
GPT2
Chinese
1.2 (1.2-1.2)
38.6 (38.4-38.6)
32.2 ×
RoBERTa
Github
1.1 (1.1-1.2)
40.7 (37.5-41.0)
37.0 ×
RoBERTa
English
1.3 (1.3-1.3)
46.2 (45.7-46.4)
35.5 ×
RoBERTa
Chinese
1.2 (1.2-1.2)
35.0 (34.7-35.2)
29.2 ×
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
Figure 5: R50K reference pattern as a delayed-accept DFA. X denotes non-whitespace characters as in Figure 6 ; ⊔ = space, w = other whitespace, \$$ = end of input. The non-whitespace part ( q_{0},sp,R,G)isanordinaryDFA(boundaryunconditionalatrun/contractionend);thewhitespacepart(W_{1},W_{2},c_{=},c_{-})isadelayedDFA.c_{=}includesthelastwschar;c_{-}trimsit(imposedbytherule\backslash\mathrm{s}^{+}(?!\backslash\mathrm{S})).PeelingfiresonlyfromW_{2},i.e.whentherunofwhitespaceisatleast2$ characters long.
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 ; ⊔ = literal space, w = other whitespace (\s∖⊔) . W accepts the maximal \s+ run unconditionally (no lookahead).
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. [^\r\n\p{L}\p{N}] ). Di denotes the DFA to compute runs of ⩽3 digits. Pu and PN denote the DFA to compute runs of symbols followed by newlines. Priority: contraction, word, digit, punct, ws. Wh and Wh2 denote the first and subsequent horizontal whitespace respectively. Wnl denotes vertical whitespace/newline. From Wnl we always keep the last whitespace. From Wh2 , we trim the last character when a non-whitespace is encountered.
Figure 8: O200K reference pattern. Words are case split, with upper case characters U=[\p{Lu,Lt,Lm,Lo,M}] first, followed by lower case characters l=[\p{Ll,Lm,Lo,M}] with an optional contraction suffix G . Digits have run length ⩽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.
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.
We propose a novel algorithm for incremental Byte Pair Encoding (BPE) tokenization. The algorithm processes each input byte in worst-case O(log2t) time, leading to an overall complexity of O(nlog2t), 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 ∼3× 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
Tokenisation is an integral part of the current NLP pipeline. Current tokenisation algorithms such as BPE and Unigram are greedy algorithms -- they make locally optimal decisions without considering the resulting vocabulary as a whole. We instead formulate tokeniser construction as a linear program and solve it using convex optimisation tools, yielding a new algorithm we call ConvexTok. We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models; it also improves downstream task performance, but less consistently. Furthermore, ConvexTok allows the user to certify how far their tokeniser is from optimal, with respect to a certain objective, via a lower bound, and we empirically find it to be within 1% of optimal at common vocabulary sizes.
Jan Tempus, Philip Whittington, Craig W. Schmidt +2
As large language models move toward million-token context windows, CPU tokenizers become a major slowdown because they process text one step at a time while powerful GPUs sit unused. We built a GPU-based byte-level BPE tokenizer that follows GPT-2's merge rules. It includes a basic BlockBPE-style kernel and a faster, optimized version that uses cuCollections static map, CUB reductions, and a pybind11 interface for Python. On WikiText103 sequences up to 131k tokens, the optimized GPU tokenizer produces the same tokens as a CPU version and, for the longest inputs, is about 1.7x faster than tiktoken and about 7.6x faster than the HuggingFace GPT-2 tokenizer. Nsight profiling shows that 70-80% of CUDA API time goes to memory allocation, so adding memory pooling should give the biggest speed boost next. Tests on generation tasks using WikiText103 prompts show that our GPU tokenizer's outputs stay within about one percentage point of tiktoken and HuggingFace GPT-2 on similarity and overlap metrics, meaning it keeps output quality while making long-context inference more practical.