Incremental BPE Tokenization

Shenghu Jiang, Ruihao Gong · 2026

Read Incremental BPE Tokenization by Shenghu Jiang, Ruihao Gong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30813.txt.

Introduction

Jiang and Gong propose stepwise Byte Pair Encoding tokenization, handling each input byte in log-squared time. The algorithm maintains tokenization results for every input prefix, using the standard merge procedure. This enables partial tokenization in streaming settings. As a drop-in replacement for standard Byte Pair Encoding, it runs up to about three times faster than Hugging Face's tokenizers. It also significantly reduces latency over OpenAI's tiktoken on pathological inputs. An eager output algorithm enables streaming output, emitting tokens as soon as boundaries are determined.

Catalog record

CREATORShenghu Jiang, Ruihao Gong
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112586
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30813

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Incremental BPE Tokenization Shenghu Jiang, Ruihao Gong Abstract We propose a novel algorithm for incremental Byte Pair Encoding (BPE) tokenization. The algorithm processes each input byte in worst-case 𝒪 ⁡ ( log 2 ⁡ t ) \mathcal{O}(\log^{2}t) time, leading to an overall complexity of 𝒪 ⁡ ( n ​ log 2 ​ t ) \mathcal{O}(n\log^{2}t) , where n n is the input length and t 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 × {\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. The source code is available at https://github.com/ModelTC/mtc-inc-bpe . † † affiliationnotice: Email: Shenghu Jiang < [email protected] >. 1 Introduction Byte Pair Encoding (BPE), originally proposed as a data compression technique by 8 , has become the de facto tokenization method for modern large language models (LLMs) following its adaptation by 35 . By iteratively merging frequent adjacent symbol pairs, BPE constructs a compact vocabulary that balances expressiveness with computational efficiency. Consequently, highly optimized implementations such as Hugging Face’s tokenizers ( 13 ) and OpenAI’s tiktoken ( 29 ) have become standard components in modern LLM pipelines. Figure 1 illustrates a representative pipeline used in modern LLM tokenization, where BPE is applied as a core stage within a broader sequence of preprocessing steps. Figure 1 : A representative pipeline in modern LLM tokenization. Raw text is processed by a sequence of model-specific preprocessing stages before applying BPE tokenization to each resulting chunk. Our work focuses on making the BPE stage incremental without altering the correctness and the surrounding stages. However, these tools are predominantly designed as offline processes: they require the entire input sequence (or a pre-segmented chunk) to be fully observed before producing a canonical tokenization. As a result, tokenization and prefilling are executed sequentially rather than concurrently, which introduces additional latency in streaming and long-context inference. At an algorithmic level, existing implementations typically rely on heap-based priority queues to select merges over the full input, leading to a formulation that is inherently global and difficult to adapt to byte-by-byte updates. The formalization of BPE by 2 implies a structural property where the tokenizations for every prefix of a text form a prefix tree of tokens. This property suggests the possibility of immediate feedback and partial processing; however, exploiting it efficiently requires algorithmic support beyond standard implementations. In this paper, we present a novel algorithm for incremental BPE tokenization that efficiently maintains BPE tokenizations for every prefix in real-time. Our algorithm processes each input byte in a worst-case time complexity of \mathcal{O}(\log^{2}t) , resulting in an overall time complexity of \mathcal{O}(n\log^{2}t) , where n is the input length and t is the maximum token length. We implement the algorithm in Rust as a drop-in replacement for core BPE stages. Benchmark results ( Table 1 ) show an end-to-end speedup of up to {\sim}3\times over Hugging Face’s tokenizers . Furthermore, while existing tools like OpenAI’s tiktoken exhibit \mathcal{O}(n^{2}) behavior on certain inputs, our approach maintains a stable \mathcal{O}(n\log^{2}t) cost, leading to significant latency reductions on pathological cases ( Figure 3 ). Beyond raw speed and streaming input, we introduce an eager output mechanism for streaming output, which emits tokens as soon as stable token boundaries are resolved. This enables tokenization to be fully pipelined with model inference. Profiling of current systems (Appendix I ) shows that stages other than BPE can become bottlenecks in tokenization pipelines, burdening both streaming input and output. With strict worst-case complexity guarantees, such pre-segmentation can be algorithmically redundant. Furthermore, along with incremental updates, the algorithm naturally supports scenarios requiring full-prefix access, i.e., scenarios in which tokenizations of all prefixes are required, such as deriving attention masks from the prefix tree of tokens for “fill-in-the-middle” (FIM) tasks without random or heuristic truncation and re-computation. Our results demonstrate that incremental BPE tokenization is both algorithmically feasible and practically beneficial, with strict worst-case guarantees and exact semantic compatibility . Contributions. We make the following contributions: • An incremental BPE algorithm is proposed with a strict worst-case \mathcal{O}(\log^{2}t) per-byte complexity, ensuring exact equivalence with standard BPE alongside rigorous performance guarantees. • The proposed eager output mechanism enables efficient, real-time streaming and pipelining with model inference. • Our efficient implementation in Rust serves as a drop-in replacement that delivers a speedup of up to {\sim}3\times over current state-of-the-art tools. • With our method, stages of traditional pipelines that serve solely to circumvent the limits of global BPE can be safely removed without performance concerns. • Our method provides native support for full-prefix tasks (e.g., FIM, token healing) by efficiently providing tokenizations of all prefixes, eliminating the need for heuristic truncation or re-computation. 2 Related Work Byte Pair Encoding ( 35 ) has established itself as the de facto standard for modern LLMs, employed by state-of-the-art architectures such as GPT-5 ( 28 ) and Qwen-3 ( 31 ) . Despite alternatives like WordPiece ( 34 ) used in BERT ( 7 ) and Unigram ( 16 ) adopted by T5 ( 33 ) , BPE remains the predominant choice for current models. In terms of model architecture, usage patterns have evolved: while earlier models typically applied BPE to the unsegmented input text, modern LLMs increasingly adopt regex-based pre-segmentation and other normalization to enforce linguistic boundaries and partition the input. Leading libraries implement these strategies differently: Hugging Face’s tokenizers ( 13 ) provides a general-purpose implementation using priority queues, whereas OpenAI’s tiktoken ( 29 ) specializes in the regex-based approach, relying on segmentation to bound the cost of BPE merges. Despite these optimizations, production-grade tokenization remains predominantly offline . Whether relying on global queues or pre-segmentation, canonical BPE tokenization is typically performed after a complete segment is available. This architecture restricts the ability to hide latency by pipelining tokenization with model inference at a fine-grained level. Furthermore, the reliance on regex engines for complexity control can be brittle, potentially introducing performance degradation or stack exhaustion on pathological inputs such as extensive repetitions. On the theoretical side, 2 analyze the formal semantics of different BPE implementations and note its consistency under token-wise truncation. This observation implies that the tokenization of a string prefix remains stable within the full tokenization, hinting at the possibility of incremental processing. However, their work focuses on algebraic properties rather than algorithmic construction, and does not address the challenge of bounding the lookahead required for online updates. In the engineering domain, practical implementations such as the crate bpe in rust-gems ( 9 ) , whose techniques are discussed by 38 , have adopted the Aho–Corasick automaton ( 1 ) for incremental tokenization. The detailed comparison is discussed in

Read the complete text