1 Introduction↩︎

Byte Pair Encoding (BPE), originally proposed as a data compression technique by [1], has become the de facto tokenization method for modern large language models (LLMs) following its adaptation by [2]. 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 [3] and OpenAI’s tiktoken [4] have become standard components in modern LLM pipelines.

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.

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 [5] 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 (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 (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 18) 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.

1.0.0.1 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 [2] has established itself as the de facto standard for modern LLMs, employed by state-of-the-art architectures such as GPT-5 [6] and Qwen-3 [7]. Despite alternatives like WordPiece [8] used in BERT [9] and Unigram [10] adopted by T5 [11], 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 [3] provides a general-purpose implementation using priority queues, whereas OpenAI’s tiktoken [4] 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, [5] 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 [12], whose techniques are discussed by [13], have adopted the Aho–Corasick automaton [14] for incremental tokenization. The detailed comparison is discussed in Appendix 19. While demonstrating practical utility, these approaches generally lack formal worst-case complexity guarantees.

Our work bridges this gap by providing an incremental algorithm with \(\mathcal{O}(\log^2 t)\) worst-case update time while maintaining strict compatibility with standard BPE.

3 Structural Foundations of Incremental BPE↩︎

In this section, we establish the structural foundations of our algorithm. We first formalize the incremental tokenization problem by explicitly defining the concept of the Last Token and deriving the recursive properties of BPE. We then introduce a normalized representation of the BPE vocabulary to eliminate redundancy. Finally, we construct the Successor Forest and the Suffix-Successor Tree, which organize the search space for incremental tokenization. These structures provide the topological basis for the theoretical properties and search algorithms presented in subsequent sections.

3.1 Preliminaries and Definitions↩︎

Let \(\Sigma\) be a finite alphabet and \(V \subset \Sigma^{+}\) be a finite vocabulary. The vocabulary \(V\) consists of atomic tokens (where \(|t| = 1\)) and non-atomic tokens (where \(|t| > 1\)).

A suffix token of a string \(s\) is defined as any token \(t \in V\) that is a suffix of \(s\).

A token sequence \(\varphi = [t_1, \dots, t_n]\) maps back to the string via detokenization \(\pi(\varphi) = t_1 \dots t_n\).

A dictionary is defined by an ordered list of merge rules \(D = [r_1, r_2, \dots, r_m]\). Each rule \(r_i\) specifies a pair of adjacent tokens \((x, y)\) to be merged into a new token \(z = xy\).

Applying a rule \(r\) to a token sequence \(\varphi\), denoted as \(\mathbb{T}_r(\varphi)\), replaces occurrences of adjacent tokens \(x\) and \(y\) with \(z\) sequentially from left to right.

The full BPE tokenization for a string \(s\) with the dictionary \(D\), denoted as \(\mathbb{T}_D(s)\), is obtained by initially mapping \(s\) to a sequence of characters \(\varphi_0\), and then applying the rules in \(D\) according to their priority: \[\mathbb{T}_D(s) = (\mathbb{T}_{r_m} \circ \dots \circ \mathbb{T}_{r_2} \circ \mathbb{T}_{r_1})(\varphi_0)\] where \(r_1\) represents the highest priority rule.

Note that under this definition, the standard BPE differs from the SentencePiece [15] semantics. Our analysis is formulated under the standard BPE merge semantics. See Appendix 10 for a detailed discussion on the difference between the two tokenization semantics and the method to “properize” merge rules for the standard BPE.

In the remainder of this paper, we omit the subscript \(D\) and write \(\mathbb{T}(s)\) when the dictionary is clear from context.

3.2 Problem Formulation↩︎

3.2.0.1 Prefix Consistency.

Our incremental approach relies on the consistency of BPE tokenization under token-wise truncation. As noted by [5] (Remark 3), a valid BPE tokenization \(\mathbb{T}(\cdot)\) can be freely truncated: the remaining sequence remains the valid tokenization of its corresponding substring.

Intuitively, this lemma holds because each BPE merge step is a boundary elimination process visualized in 4. We provide an independent formal proof in Appendix 11.

This lemma ensures that the tokenization of a growing string can be modeled as extending the previous valid tokenization of some shorter prefix rather than re-computing from scratch.

3.2.0.2 The Last Token.

Based on this consistency, we define the Last Token, denoted as \(\theta(s)\). For any non-empty string \(s\), \(\theta(s)\) is the last token in its BPE tokenization sequence: \(\theta(s) = \operatorname{last}\left(\mathbb{T}\left(s\right)\right)\).

According to the Prefix Consistency lemma (Lemma 1), since removing the last token leaves a valid tokenization sequence for the remaining string prefix, we can express the tokenization recursively: \[\mathbb{T}(s) = \mathbb{T}\left(s_{\mathrm{pre}}\right) \oplus \left[\theta\left(s\right)\right]\] where \(s_{\mathrm{pre}}\) is the string \(s\) with the suffix string of \(\theta(s)\) removed, and \(\oplus\) denotes sequence concatenation.

In terms of complexity, the full-prefix tokenization requires maintaining \(\Theta(|s|)\) states.

3.2.0.3 Prefix Tree of Tokens.

This recursive relationship implies that the tokenizations of all prefixes naturally form a hierarchical structure. Strictly speaking, this structure constitutes a forest, as a tokenization sequence may begin with any valid token. To unify this into a single Prefix Tree of Tokens, we introduce a virtual root representing the tokenization of the empty string \(\varepsilon\), which serves as the shared root for all initial tokens.

While we visualize the space of all prefix tokenizations as this tree, strictly maintaining the explicit structure is unnecessary. Instead, the tokenization for any prefix can be retrieved solely by backtracking using \(\theta(\cdot)\) until the beginning of the string (the virtual root) is reached.

3.2.0.4 Incremental Objective.

Consider an incremental scenario where a character \(c\) is appended to the current string \(s\), resulting in \(s' = s c\). To update the tokenization, we only need to find the value of \(\theta(s')\). The objective is to identify \(\theta(s')\) within the intersection of the set of all suffixes of \(s'\) and the vocabulary \(V\). In the following sections, we introduce the Successor Forest and other structures to efficiently solve this search problem.

3.3 Normalization and Token Hierarchy↩︎

In practice, BPE vocabularies often contain unreachable entries. To facilitate efficient updates, we define a normalized representation. We say a token \(t \in V\) is canonical if \(\mathbb{T}_D(t) = [t]\). The normalized vocabulary \(\mathcal{V}\) consists solely of canonical tokens. Crucially, the determinism of BPE establishes a bijective mapping between non-atomic canonical tokens and the specific merge rules that produce them, which we term canonical rules. The normalized dictionary \(\mathcal{D}\) contains strictly these rules. We show in Appendix 12 that this normalization preserves exact compatibility, i.e., \(\mathbb{T}_\mathcal{D}(s) \equiv \mathbb{T}_D(s)\).

3.3.0.1 Predecessors and Successors.

Based on the bijection above, for every non-atomic \(t \in \mathcal{V}\) produced by the canonical rule \((x, y)\) of \(t\), we define its predecessor \(\operatorname{pre}(t) = x\) and successor \(\operatorname{suc}(t) = y\). As detailed in Appendix 12, the determinism of BPE ensures \(x, y \in \mathcal{V}\). Thus, the vocabulary is closed under these operations, forming the topological basis for the Successor Forest.

3.4 Successor Forest↩︎

Based on the hierarchy, we construct the topological structure for searching \(\theta(\cdot)\). We define the Successor Forest (\(\mathcal{F}_{\operatorname{suc}}\)) as a directed graph \(G = (\mathcal{V}, E)\) where edges point from a token to its successor: \(E = \{ (u, \operatorname{suc}(u)) \mid u \in \mathcal{V}, |u| > 1 \}\). Since edges strictly reduce token length (\(|\operatorname{suc}(u)| < |u|\)), \(G\) is acyclic and forms a forest of trees rooted at atomic tokens.

An example Successor Forest is illustrated in 2.

3.5 Suffix-Successor Tree↩︎

By definition, for any non-atomic token \(u\), \(u = \operatorname{pre}(u) \operatorname{suc}(u)\), which implies \(\operatorname{suc}(u)\) is a proper suffix of \(u\). This property ensures that traversing parents in \(\mathcal{F}_{\operatorname{suc}}\) corresponds to taking proper suffixes.

For a given token \(t \in \mathcal{V}\), we define the Suffix-Successor Tree, denoted as \(\operatorname{SufSucTree}(t)\), as the subgraph of \(\mathcal{F}_{\operatorname{suc}}\) induced by the set of all canonical tokens that are suffixes of \(t\).

Let \(S_t\) be the set of suffix tokens of \(t\) (note that \(t \in S_t\)). If a non-atomic token \(u \in S_t\), then its parent in the forest, \(\operatorname{suc}(u)\), must also be a suffix of \(t\), implying \(\operatorname{suc}(u) \in S_t\). Since all suffixes of \(t\) share the same last character, all paths in this subgraph converge to the unique atomic suffix token of \(t\). Therefore, \(\operatorname{SufSucTree}(t)\) forms a single tree rooted at this atomic token.

This structure organizes all potential candidates for the value of \(\theta(\cdot)\). By identifying further properties on this tree, we can reformulate the incremental tokenization as an efficient tree search problem.

An example Suffix-Successor Tree is highlighted in violet in 2.

4 The Monotonic Path Property↩︎

This section establishes the key property underlying BPE for suffix tokens. For any input string, we will show that the suffix tokens capable of serving as the final token form a single monotonic path in the Suffix-Successor Tree.

4.1 Intuition↩︎

Fix a non-empty string \(s\) and a suffix token \(t\) of \(s\). For \(t\) to be the valid last token \(\theta(s)\), the boundaries around its components \(\operatorname{pre}(t)\) and \(\operatorname{suc}(t)\) are required to survive the merge process before applying the canonical rule of \(t\) (as formalized in Lemma 4 and Lemma 7).

This survival establishes a necessary dual constraint on the merge history:

1. Structural Reachability: \(\operatorname{pre}(t)\) must appear as the rightmost token at some stage during the processing of the prefix, meaning the eventual last token of the prefix must be a descendant of \(\operatorname{pre}(t)\).

2. Procedural Priority: The merge rule forming \(t\) must execute before any rule that would otherwise consume \(\operatorname{pre}(t)\) (specifically, merging it with a left neighbor).

Crucially, these conditions are necessary but not sufficient, since the newly formed token \(t\) may still be involved in subsequent merges before the final tokenization is reached.

Another intuition is that the rightmost token can be viewed as evolving through the tokenization: starting from an atomic token, it is progressively merged with its adjacent token. This process can be viewed as traversing a descendant path in the Successor Forest, until reaching the last token of the final tokenization.

We provide a detailed derivation of this intuition based on the “boundary elimination” logic in Appendix 13.

4.2 Formalization↩︎

We now formalize the intuition from the previous subsection. The following definition establishes a rigorous criterion for determining whether a candidate suffix token \(t\) is compatible with the tokenization of the remaining prefix.

We now assert the main structural theorem of this paper.

We provide the complete proof in Appendix 14. The “if” direction follows directly from the intuition above: along the successor chain of the true last token, both reachability and priority dominance are preserved monotonically.

It is notable that, although the Monotonic Path Property restricts the search space to the Suffix-Successor Tree of the longest suffix token, the Prefix Last-Token Condition itself is evaluated in the global Successor Forest. In particular, for a candidate token \(t\), the condition depends only on the relative position between \(\operatorname{pre}(t)\) and \(\theta(s^{-\operatorname{suc}(t)})\) in the Successor Forest, and does not depend on the membership of \(\operatorname{pre}(t)\) in \(\operatorname{SufSucTree}(t)\).

4.3 Linearization via DFS↩︎

To utilize the Monotonic Path Property to find the last token \(\theta(s)\), it requires an efficient method to verify whether a node \(t \in \operatorname{SufSucTree}(k)\) satisfies the Prefix Last-Token Condition (Definition 1).

For a fixed non-atomic token \(t\), consider the possible values of \(\theta(s^{-\operatorname{suc}(t)})\) that satisfy the condition. This set of valid tokens forms the subtree rooted at \(\operatorname{pre}(t)\) in the Successor Forest dictated by the “Reachability” requirement, excluding the subtrees rooted at any direct child of \(\operatorname{pre}(t)\) whose canonical rule has a priority greater than or equal to that of \(t\), as enforced by the “Priority dominance”.

Let \(\mathcal{C}_t\) be the set described above for a non-atomic token \(t\). If \(t\) is an atomic token, \(\mathcal{C}_t\) is simply defined as an empty set. In this section, we show that membership in \(\mathcal{C}_t\) can be evaluated in \(\mathcal{O}(1)\) time with DFS linearization.

4.3.0.1 DFS Linearization of the Successor Forest.

To linearize the forest topology, we perform a pre-order Depth-First Search (DFS) starting from the atomic tokens. We maintain a global counter that increments exactly once upon entering each node \(u\), assigning it a unique entry timestamp \(\operatorname{dfs\_in}(u)\). We then assign an exit timestamp \(\operatorname{dfs\_out}(u)\) immediately after fully exploring its subtree.

This process establishes a bijection between the nodes and the timestamps. Crucially, it guarantees that the subtree rooted at any node \(u\) corresponds exactly to a contiguous half-open interval \([\operatorname{dfs\_in}(u), \operatorname{dfs\_out}(u))\).

Additionally, when traversing the children of a node \(u\), we visit them in strictly increasing order of their canonical rule priorities (from lowest to highest priority). This deliberate ordering ensures that children with lower priorities are mapped to earlier timestamps, enabling us to efficiently exclude the subtrees of higher-priority children to enforce the “Priority dominance” condition.

4.3.0.2 Valid Interval.

Notably, the set \(\mathcal{C}_t\) corresponds to a contiguous range of timestamps. For each non-atomic canonical token \(t\), we precompute a valid interval \(I_t = [L_t, R_t)\) such that a node \(x \in \mathcal{C}_t\) if and only if \(\operatorname{dfs\_in}(x) \in I_t\). Concretely:

• \(L_t = \operatorname{dfs\_in}(\operatorname{pre}(t))\);

• \(R_t = \operatorname{dfs\_in}(u)\), where \(u\) is the first child of \(\operatorname{pre}(t)\) (in the DFS traversal order) whose canonical rule priority is greater than or equal to that of \(t\). If no such child exists, we set \(R_t = \operatorname{dfs\_out}(\operatorname{pre}(t))\).

The construction above reduces the evaluation of the Prefix Last-Token Condition to an \(\mathcal{O}(1)\) interval membership test.

4.3.0.3 Mutual Exclusion among Siblings.

Finally, it is notable that the valid intervals of sibling nodes in the Suffix-Successor Tree are necessarily disjoint. This is a direct corollary of the Monotonic Path Property (1). If the intervals of two distinct siblings overlapped, there would exist a prefix state for which both siblings satisfy the Prefix Last-Token Condition, implying the existence of valid nodes on two diverging branches. This contradicts the uniqueness of the valid path guaranteed by 1.

Thus, for any two distinct children \(u\) and \(v\) of a node, we have \(I_u \cap I_v = \emptyset\). This mutual exclusion enables the search algorithm to unambiguously identify the correct branch at each step.

5 Incremental Algorithm↩︎

Based on the theoretical foundations established in the previous sections, we now present the incremental algorithm for maintaining the last token \(\theta(s)\). In this section, we first outline the abstract algorithmic framework and its design objectives. We then detail the specific data structures, the Aho–Corasick automaton [14] and Centroid Decomposition, employed to implement each component efficiently.

5.1 Algorithm Framework↩︎

The incremental update problem can be framed as follows: given the current string \(s\), its last token \(\theta(s)\), and a new character \(c\), we aim to compute the new last token \(\theta(sc)\).

Our strategy relies on the structural properties of the search space. First, recall that \(\theta(sc)\) must be a suffix token of the string \(sc\). While there may be many suffix tokens, they are all suffixes of the longest suffix token, denoted as \(\tau(sc)\). Consequently, the Suffix-Successor Tree \(\operatorname{SufSucTree}(\tau(sc))\) defines our search space.

Within this search space, the Monotonic Path Property (1) guarantees that the set of nodes satisfying the Prefix Last-Token Condition forms a single continuous path anchored at the root (the atomic token \(c\)). Since the atomic token is always a valid candidate, this path is never empty. The correct last token \(\theta(sc)\) corresponds to the deepest node of this valid path.

Therefore, the algorithm proceeds in two abstract steps:

1. Search Space Identification: Identify the longest suffix token \(\tau(sc)\) to determine the bounding tree \(\operatorname{SufSucTree}(\tau(sc))\).

2. Path Extension Search: Within \(\operatorname{SufSucTree}(\tau(sc))\), search for the deepest node satisfying the Prefix Last-Token Condition.

To evaluate the Prefix Last-Token Condition during the search, the algorithm requires access to the last tokens of previous prefixes. We abstract this as a history interface \(\mathcal{H}(\ell)\), which returns the last token of the prefix obtained by removing \(\ell\) characters from the end of the current string.

5.2 Search Space Maintenance via Aho–Corasick Automaton↩︎

To identify \(\tau(sc)\), we maintain an Aho–Corasick automaton [14] on \(\mathcal{V}\). We augment the structure by precomputing the search space entry point: for each state \(u\), the annotation is the token \(u\) itself if \(u \in \mathcal{V}\), otherwise it is inherited from \(u\)’s suffix link. This allows retrieving \(\tau(sc)\) in \(\mathcal{O}(1)\) without traversing suffix links. We store the transition table using a persistent square-root tiling (details in Appendix 15) to ensure \(\mathcal{O}(1)\) transition queries with memory efficiency. The annotation at the new state identifies the specific \(\operatorname{SufSucTree}(\cdot)\) for the subsequent search.

5.3 Efficient Search via Centroid Decomposition↩︎

The main challenge is to efficiently locate the deepest valid node within \(\operatorname{SufSucTree}(\tau)\), where \(\tau = \tau(sc)\). Since the tree height can be linear in \(|\tau|\), a naive top-down traversal is inefficient. We solve this by guiding the search using Centroid Decomposition.

For each canonical token \(\tau \in \mathcal{V}\), we precompute a Centroid Search Tree (CST). The CST is a tree of height \(\mathcal{O}(\log |\tau|)\), where each node corresponds to a centroid \(u\) of a weak component in the recursive decomposition of \(\operatorname{SufSucTree}(\tau)\). Crucially, from the perspective of a centroid \(u\), the original tree is split into disjoint weakly connected components: one component containing the parent of \(u\) (the “upward” direction), and several components each containing a child of \(u\) (the “downward” directions).

The search for \(\theta(sc)\) proceeds by traversing this CST. At each step, let \(u\) be the current centroid. We evaluate the Prefix Last-Token Condition for \(u\) by querying the history state \(k = \mathcal{H}(|\operatorname{suc}(u)|)\) and performing the interval check \(\operatorname{dfs\_in}(k) \in I_u\). Based on the Monotonic Path Property, we determine the direction of the valid path’s endpoint:

1. Case 1: \(u\) is invalid (\(\operatorname{dfs\_in}(k) \notin I_u\)). Since the valid path is anchored at the tree root (the atomic token), an invalid node \(u\) implies that the path does not intersect with the subtree of \(\operatorname{SufSucTree}(\tau)\) rooted at \(u\); i.e., the path must be inside the component of the parent. We transition to the CST child corresponding to the component containing \(u\)’s parent (the upward direction).

2. Case 2: \(u\) is valid (\(\operatorname{dfs\_in}(k) \in I_u\)). The node \(u\) lies on the valid path. The target \(\theta(sc)\) is either \(u\) itself or its descendant. To determine if the path extends deeper, we check the children of \(u\) in the original \(\operatorname{SufSucTree}(\tau)\). Recall from 4.3 that the valid intervals of siblings are disjoint. We can thus pre-sort the intervals and perform a binary search over the children to check if any child \(v\) is valid.

   • If a valid child \(v\) exists (i.e., \(\operatorname{dfs\_in}(\mathcal{H}(|u|)) \in I_v\)), the path continues into \(v\)’s subtree. We transition to the CST child corresponding to the component containing \(v\).

   • If no child is valid, then the path ends at \(u\). We conclude \(\theta(sc) = u\) and terminate the search.

5.4 Complexity Analysis↩︎

The worst-case time complexity per byte is dominated by the centroid search.

• Automaton State Update: The optimized automaton transition takes \(\mathcal{O}(1)\) time.

• CST Traversal: The CST height is bounded by \(\mathcal{O}(\log |\tau|)\).

• Decision Step: At each CST node, we perform either a single interval check or a binary search over the children. Since the degree of a node in \(\operatorname{SufSucTree}(\tau)\) is bounded by \(|\tau|\), the binary search takes \(\mathcal{O}(\log |\tau|)\).

Each check involves a history query \(\mathcal{H}(\cdot)\), assumed to be an \(\mathcal{O}(1)\) operation. Combining these factors, the complexity per byte is \(\mathcal{O}(\log^2 |\tau|)\), leading to an overall complexity of \(\mathcal{O}(n \log^2 t)\) for the entire input, where \(t\) is the maximum token length.

6 Eager Output↩︎

The incremental algorithm efficiently maintains the state \(\theta(s)\). Since the sequence of last tokens implicitly encodes the Prefix Tree of Tokens, the full tokenization is typically recovered by backtracking from \(\theta(s)\) to the virtual root.

In a streaming setting, however, incrementality alone does not guarantee streaming output. Thus, the challenge is to identify the initial segment of this backtracking chain that has become invariant, serving as the common ancestry for any future extension of the string.

6.1 The Active Frontier↩︎

The ambiguity of the output stream arises from the uncertainty of which current node in the Prefix Tree of Tokens will serve as the parent for future tokens. When new characters are appended to \(s\), any newly formed last token must attach to the last token of some prefix of \(s\).

The range of such possible attachments is bounded by the maximum suffix length queried during the incremental search, which corresponds to the deepest state reached in the Aho–Corasick automaton. Let \(d(s)\) be the depth of the state reached by the string \(s\) in the Aho–Corasick automaton. Note that this depth corresponds exactly to the length of the longest suffix of \(s\) recognized by the automaton. Since any future token formed must be recognized by the automaton, its length cannot exceed \(d(s)\).

Consequently, the parent of any future token must be the last token of a prefix ending in the interval \([|s| - d(s), |s|]\).

We thus define the set of Parental Candidates, \(\mathcal{P}\), as the set of all last tokens that fall within this interval: \[\mathcal{P} = \{ \theta(s[1 \dots i]) \mid |s| - d(s) \le i \le |s| \}\] where \(s[1 \dots 0]\) indicates the empty string \(\varepsilon\) and \(\theta(\varepsilon)\) is the virtual root of the Prefix Tree of Tokens. The stable output is the common ancestral path shared by all tokens in \(\mathcal{P}\).

6.2 Maintenance Algorithm↩︎

To efficiently identify and emit the stable tokens, we exploit the monotonicity of the window boundaries. Observe that the automaton transition for a new character can increase the state depth by at most 1 (i.e., \(d(sc) \le d(s) + 1\)). Therefore, the start of the window, \(|s| - d(s)\), is monotonically non-decreasing. This guarantees that candidates only “expire” from \(\mathcal{P}\) as the window slides forward; previously expired tokens never re-enter.

Based on this property, we implement a two-pointer algorithm to maintain the set \(\mathcal{P}\) and track the active subgraph in the Prefix Tree of Tokens. Tokens are emitted eagerly once all active paths converge to a single child of the virtual root. The detailed algorithmic steps and complexity analysis are provided in Appendix 16.

While eager output enables streaming, it introduces computational overhead due to maintaining the dynamic subgraph. Therefore, unless otherwise specified, the standard benchmarks presented later utilize the non-eager incremental algorithm.

7 Benchmarks↩︎

We evaluate the end-to-end throughput of our incremental BPE algorithm by integrating it as a drop-in replacement for Hugging Face’s tokenizers and OpenAI’s tiktoken. Since our algorithm is fully compatible with existing pipelines, the benchmarks isolate the effect of replacing the BPE stage alone, without altering segmentation, normalization, or caching behavior.

Detailed experimental setup, dataset composition, and execution strategies are provided in Appendix 17, while the full benchmark results (including eager output) are listed in [tab:detailed-benchmarks].

7.1 Throughput Analysis↩︎

1 reports the speedup factors evaluated on concatenated documents from each dataset.

7.1.0.1 Absence of Pre-tokenization.

The most substantial gains are observed in CodeLlama (up to 3.13\(\times\)), where the BPE processes normalized text without regex-based pre-tokenization. In this regime, the heap-based implementation in tokenizers faces log-linear complexity over the full input length, whereas our algorithm leverages its incremental nature to maintain high throughput.

7.1.0.2 Coarse-Grained Segmentation.

For the Chinese dataset, regex-based pre-tokenization typically yields coarser segments than English due to the specific designs of the regex rules and the characteristics of the language.

This exposes the performance bottlenecks in the original BPE implementation of tiktoken, while our method achieves significant speedups (up to 1.59\(\times\)) by strictly bounding the per-byte processing time.

7.1.0.3 Fine-Grained Segmentation.

For the English dataset, regex rules effectively partition the input into small chunks, where the constant factors of the implementation overhead become dominant. This explains the slight regression of our method observed in some cases.

7.2 Robustness and Eager Output↩︎

7.2.0.1 Pathological Inputs.

We test robustness using inputs constructed by repeating the character ‘a’ \(2^k\) times. As shown in 3 and 7, tiktoken exhibits a characteristic throughput decay consistent with \(\mathcal{O}(n^2)\) complexity.

Our method maintains stable throughput throughout the tests. The other tested tokenizers within the same frameworks exhibit similar trend characteristics to the representative models shown. Notably, specifically for the O200K model as an exception, long inputs trigger errors in the regex stage before BPE.

7.2.0.2 Eager Output Overhead.

We also evaluate our eager output implementation (6). Results in Appendix 17 indicate that eager output introduces an overhead on the order of 10% in end-to-end throughput compared to the non-eager incremental implementation. This overhead stems from the additional bookkeeping required to maintain output states, and can potentially be amortized in systems where tokenization is pipelined with I/O or model inference.

8 Future Work↩︎

While this work demonstrates that the BPE stage itself is fully compatible with streaming input and output, other components in existing pipelines, notably normalization and regex-based pre-tokenization, remain offline-oriented and impede end-to-end streaming execution.

Our profiling results in Appendix 18 indicate that these upstream stages can become computational bottlenecks.

A critical direction for future work is therefore to revisit the design choices of pre-tokenization in light of incremental algorithms with explicit worst-case guarantees.

9 Conclusion↩︎

We introduced a novel algorithm for incremental BPE tokenization with a strict worst-case time complexity of \(\mathcal{O}(n \log^2 t)\). Implemented as a drop-in replacement, the algorithm delivers substantial end-to-end speedups over existing systems and avoids the severe performance degradation on pathological inputs. Beyond performance, our results show that BPE can be made compatible with streaming input and output, enabling optimizations in modern language model systems.

Overall, our approach proves that strict algorithmic worst-case guarantees can translate into practical benefits, paving the way for more robust and responsive LLM pipelines.

Acknowledgements↩︎

This work was supported by the National Natural Science Foundation of China (Nos. 62525601, 62476018) and the Postdoctoral Fellowship Program of CPSF (No. BX20250487).

Impact Statement↩︎

This paper presents work whose goal is to advance the field of machine learning by improving the fundamental algorithmic infrastructure of large language models (LLMs).

9.0.0.1 Energy Efficiency.

Tokenization is a ubiquitous preprocessing step executed trillions of times in modern LLM pipelines. By reducing the algorithmic worst-case time complexity of BPE to \(\mathcal{O}(n \log^2 t)\), utilizing incremental updates for streaming input, and enabling eager emission for streaming output, our approach reduces the computational resources and latency required for processing. This optimization contributes to the broader goal of “Green AI,” potentially lowering the aggregate energy consumption and carbon footprint associated with deploying large-scale language models.

9.0.0.2 System Robustness and Reliability.

Our work specifically addresses performance degradation on pathological inputs, a vulnerability present in some current state-of-the-art tokenizers. By providing strict worst-case execution guarantees, our algorithm mitigates the risk of algorithmic complexity attacks (e.g., Denial-of-Service attacks triggered by carefully crafted input sequences), thereby enhancing the reliability and security of production systems.

We do not foresee any specific negative societal consequences directly stemming from this algorithmic improvement, beyond the general dual-use nature of efficient computing infrastructure.

10 Properizing↩︎

10.1 Semantics Discrepancy↩︎

As discussed by [5], Byte Pair Encoding (BPE) tokenization generally follows one of two distinct operational semantics:

1. Standard BPE Semantics (as defined in 3.1): This approach operates on a fixed priority schedule. It iterates through the merge rules from highest to lowest priority, applying each rule exhaustively across the sequence. Crucially, the process is linear with respect to the rule list: once a priority level is passed, the algorithm never revisits it, regardless of whether subsequent merges create new opportunities for higher-priority rules.

2. SentencePiece Semantics [15]: This approach operates on a dynamic priority queue. At each step, it identifies the adjacent token pair with the global maximum priority in the current sequence. Notably, a merge operation generates at most two new adjacent pairs that may possess even higher priorities. SentencePiece will immediately execute either of the merges, effectively “growing” the token recursively and prioritizing these local expansions over the previous lower-priority global candidates.

To formalize this inconsistency, we adopt the terminology established by [5]. An improper dictionary is defined as one containing merge rules that violate the sequential assumption of the standard BPE. Specifically, if a rule \(r_{l}\) produces a token that creates the context for a strictly higher-priority rule \(r_{h}\), the standard BPE will not execute \(r_{h}\), since the algorithm has strictly proceeded past its priority level. In contrast, SentencePiece would immediately identify \(r_{h}\) as the new global maximum.

To bridge this inconsistency, we propose a method to properize the dictionary: reassigning rule priorities via topological sorting so that the standard BPE’s execution yields results identical to those of SentencePiece. The method is a sufficient construction for properization by reordering the priorities; other constructions may exist to achieve the same goal.

10.2 Dictionary Filtering↩︎

In practice, BPE dictionaries often contain redundant or unreachable rules that are never triggered, even under SentencePiece semantics. To ensure the formalization is well-defined, we restrict our analysis to valid rules prior to properization.

Given the deterministic nature of BPE, we define a merge rule \((x, y) \to z\) as valid if and only if the tokenization of the concatenated string \(xy\) under SentencePiece semantics results in the single token \(z\) itself, and the final applied merge is indeed \((x, y)\). Rules failing this condition are effectively unreachable in any context and are thus discarded.

Crucially, this implies that the mapping from a produced token to its generating rule is unique; no two distinct valid rules result in the same token after filtering.

In the remainder of this section, we assume the dictionary has been filtered to contain solely valid rules. Based on this filtered dictionary, we can now define the dependency structure.

10.3 Growing Tree↩︎

The SentencePiece semantics can be conceptualized as the standard BPE mechanism equipped with additional growing steps. Under this view, a merge operation \((x_0, y_0) \to z_0\) serves as a seed event that may trigger a cascade of immediate high-priority merges due to the greedy strategy.

Specifically, after the seed merge \((x_0, y_0)\), the new token \(z_0\) immediately forms new pairs with its left neighbor \((u_1, z_0)\) and right neighbor \((z_0, v_1)\). If either of these new pairs has a strictly higher priority than the original seed \((x_0, y_0)\), SentencePiece will immediately execute the one with the higher priority. Note that executing one side implicitly invalidates the other, as the central token \(z_0\) is consumed.

This recursive process, denoted as \((x_k, y_k) \to z_k\), repeats until no adjacent pair has a higher priority than the original seed \((x_0, y_0)\). The entire sequence behaves like “growing” outward from the initial seed merge. Note that, since the length of the merged token \(z_k\) strictly increases with each step, no subsequent adjacent pair will possess the exact same priority as the seed.

Consider all possible scenarios of this process. The growing path from a seed extends either to the left or to the right, forming a chain of growing steps. We formalize the collection of all such possible growing steps as the Growing Tree. Specifically, the root is the seed rule, and the child nodes are all valid merge rules that can be triggered by the parent during the growing of the root, distinguished by their growing direction (left or right).

To systematically construct these trees, we analyze the derivation of each valid rule to determine its role (root or child). For any string \(s\), let \(L(s)\) denote the lowest priority among all merge rules involved in the tokenization of \(s\) under SentencePiece semantics. For a valid merge rule \(r: (x, y) \to z\), it inherently holds that \(L(z) \le \min(L(x), L(y))\). We classify the rule \(r\) based on this relationship:

1. Root Rule (\(L(z) < \min(L(x), L(y))\)): The rule \(r\) has a lower priority than any rule contained within its components. Thus, \(r\) is a seed event that initiates a growing process. In the Growing Tree, \(r\) is a root node. Functionally, we treat the root as left-growing, since the rule becomes applicable only after the token \(y\) is generated.

2. Growing Step (\(L(z) = \min(L(x), L(y))\)): The rule \(r\) is triggered by a lower-priority bottleneck within its components. We determine the growing direction as follows:

   • Left-Growing: If \(L(z) = L(y)\), the seed lies within \(y\). Rule \(r\) extends the growing chain to the left. Crucially, this case covers the scenario where \(L(x) = L(y)\). Under SentencePiece semantics, such ties must be resolved as left-growing; otherwise, the necessary right-side token \(y\) would not yet be established to participate in the merge. In the tree, \(r\) is a child of the corresponding rule in \(y\).

   • Right-Growing: If \(L(z) = L(x)\) and \(L(z) < L(y)\), the seed lies within \(x\). Rule \(r\) extends the growing chain to the right. In the tree, \(r\) is a child of the corresponding rule in \(x\).

Since the dictionary is filtered to ensure unique derivations, each merge rule corresponds to at most one parent, ensuring the dependency structure forms a valid forest.

Consequently, the growing process of a seed merge under SentencePiece semantics is equivalent to a greedy search for the deepest applicable path within the Growing Tree rooted at that seed.

10.4 Dependency Graph and Topological Sort↩︎

To simulate SentencePiece semantics using the standard BPE, we need to flatten each Growing Tree into a valid sequential order, by reordering the priorities of rules during growing steps.

However, the growing steps are applied independently for each seed under SentencePiece semantics, while using the standard BPE requires each rule to be applied to the sequence exhaustively. We model the relative order and independence of growing steps as a dependency graph.

1. Tree Edges (Parent \(\to\) Child): Within each Growing Tree, a parent rule must be processed before its children. Although the children originally had higher priorities, in the properized dictionary, we must place them after the parent to ensure the parent exists to trigger them.

2. Sibling Edges (Among the Direct Children): For siblings, during the growing steps, only the highest-prioritized applicable merge is selected. This implies that sibling rules are evaluated strictly in the order of their original priorities. Thus, we add edges from the siblings with higher priority to those with lower priority.

3. Conflict Edges (Right-Growing \(\to\) Left-Growing): A critical inconsistency arises when two growing steps from different trees compete for the same overlapping token. Suppose a left-growing rule \((w, x)\) and a right-growing rule \((y, w)\) both require token \(w\).

   • Under SentencePiece semantics, each growing process runs independently, so the leftmost seed can obtain \(w\) before others.

   • To emulate this deterministically without lookahead, we rely on the left-to-right scan nature of the standard BPE.

   • This imposes the constraint that right-growing nodes must precede left-growing nodes.

   Hence, edges from the right-growing node to the left-growing node obtaining the same token are required.

One can optimize the number of edges via transitive reduction. This simplifies the graph without altering its topological properties.

If the constructed dependency graph is a directed acyclic graph (DAG), a topological sort exists. Deriving the new rule priorities from this topological order yields a properized dictionary. The standard BPE, executing this dictionary linearly, will respect all dependencies of the growing steps and produce output identical to SentencePiece.

10.5 Sufficiency↩︎

10.6 Non-properizable scenarios↩︎

If the graph contains a cycle, the dictionary is non-properizable.

A canonical example is the dictionary [(aa, a), (a, a)] applied to the string “aaaa”.

• SentencePiece: yields [aaa, a].

• The standard BPE: yields [aa, aa], no matter the priorities of the merge rules.

In the dependency graph, (a, a) acts as a root (left-growing) pointing to a right-growing node (aa, a). However, the Conflict Edges would cause a dependency cycle, so it fails to properize.

In our experiments, one non-properizable tokenizer we found is Gemma-3 [16], which contains improper merge rules of multiple newline characters.

11 Proof of the Prefix Consistency↩︎

In this section, we provide the formal proof for Lemma 1. Our proof relies on the inductive properties of the single merge operation visualized in 4.

11.0.0.1 Notation.

Let \(\mathbb{T}_{(u, v)}\) denote the operator for a single BPE merge step that replaces all adjacent occurrences of tokens \((u, v)\) from left to right with the merged token \(w\). Initially, the input string \(s\) is mapped to a sequence of atomic tokens \(\varphi_0\). The full BPE process is a composition of such operators: \(\mathbb{T}= \mathbb{T}_{r_m} \circ \dots \circ \mathbb{T}_{r_1}\), where \(r_1, \dots, r_m\) are the merge rules applied in order.

12 Normalization and Equivalence Details↩︎

In this section, we elaborate on the properties of the normalized representation introduced in 3.3.

12.0.0.1 Canonical Generation and Closure.

For a canonical token \(t\) produced eventually by the rule \((x, y) \to t\), the tokenization of the string \(t\) must conclude with this specific merge. This necessitates that the substrings \(x\) and \(y\) must have been independently tokenized into \(x\) and \(y\) prior to this final merge. Therefore, \(\mathbb{T}(x) = [x]\) and \(\mathbb{T}(y) = [y]\), implying that the predecessor \(\operatorname{pre}(t)=x\) and successor \(\operatorname{suc}(t)=y\) are themselves canonical tokens. This ensures that \(\mathcal{V}\) is closed under decomposition, which is essential for the construction of the Successor Forest.

12.0.0.2 Equivalence.

Normalization does not alter tokenization results for general text. Since non-canonical rules are by definition never triggered in the deterministic BPE tokenization of valid tokens, removing them from the dictionary does not affect the merge process for any input string. Thus, \(\mathbb{T}_\mathcal{D}(s) \equiv \mathbb{T}_D(s)\).

13 Extended Intuition of Monotonic Path: Boundary Elimination↩︎

In this section, we expand on the intuition provided in 4.1 by reasoning about the merge process of the rightmost token.

Fix a non-empty string \(s\) and a suffix token \(t\) of \(s\). Let \(s^{-\operatorname{suc}(t)}\) denote the shorter prefix obtained by removing the suffix \(\operatorname{suc}(t)\) from \(s\). If \(t\) is ever produced as the last token during the merge process, then immediately before applying the canonical rule of \(t\), the tokens \(\operatorname{pre}(t)\) and \(\operatorname{suc}(t)\) must appear consecutively at the end of the current token sequence.

Crucially, at this specific moment, the boundary between \(\operatorname{pre}(t)\) and \(\operatorname{suc}(t)\) remains intact, so the presence of the rightmost token \(\operatorname{suc}(t)\) does not affect any merges that have already occurred to the left of \(\operatorname{pre}(t)\). Therefore, the token sequence obtained by removing the final \(\operatorname{suc}(t)\) coincides with the token sequence produced by the merge process of \(s^{-\operatorname{suc}(t)}\) right before applying the rule of \(t\).

This implies a necessary condition: if \(t\) is to be formed, \(\operatorname{pre}(t)\) must appear as the rightmost token at some stage during the merge process of \(s^{-\operatorname{suc}(t)}\). In terms of the Successor Forest structure, this means that the eventual last token \(\theta(s^{-\operatorname{suc}(t)})\) must be a descendant of \(\operatorname{pre}(t)\) (or \(\operatorname{pre}(t)\) itself).

Additionally, whether this state is reachable depends on rule priorities. If \(\operatorname{pre}(t)\) is not yet the final result \(\theta(s^{-\operatorname{suc}(t)})\), it is destined to be merged with a left neighbor to form a larger token (specifically, one of its children in the Successor Forest, formed by merging it with its left neighbor). For \(t\) to exist, the canonical rule of \(t\) must be applied before this specific merge event occurs.

In summary, the formation of \(t\) is determined by a single critical moment: whether \(\operatorname{pre}(t)\) can persist as the rightmost token of \(s^{-\operatorname{suc}(t)}\) until the canonical rule of \(t\) is applied.

14 Proof of Monotonic Path Property↩︎

In this section, we prove Theorem 1, which characterizes the structure of suffix tokens that satisfy the Prefix Last-Token Condition (Definition 1).

Recall that for a non-empty string \(s\), let \(k\) be the longest canonical suffix token of \(s\), and let \(\operatorname{SufSucTree}(k)\) denote the Suffix-Successor Tree induced by all canonical suffix tokens of \(k\). The theorem asserts that the set of tokens in \(\operatorname{SufSucTree}(k)\) satisfying the Prefix Last-Token Condition forms exactly the unique path from the true last token \(\theta(s)\) to the root of \(\operatorname{SufSucTree}(k)\).

14.1 Proof Overview↩︎

As discussed in 4.1 and Appendix 13, the Prefix Last-Token Condition (Definition 1) can be intuitively understood as the ability of a node \(w\) to “steal” its predecessor \(\operatorname{pre}(w)\) from the last token \(\theta(s^{-\operatorname{suc}(w)})\) of the truncated string.

Claim 1 establishes an upward-closure property: if a node has this stealing capability, then its successor must also have it. Otherwise, the canonicity of the involved tokens would be violated.

Claim 2 addresses the question of uniqueness: whether multiple children of the same successor could simultaneously satisfy the condition. The determinism of the standard BPE merge process, together with strict priority ordering, rules out this possibility.

Claim 3 confirms that the true last token \(\theta(s)\) indeed satisfies the condition. Intuitively, since \(\theta(s)\) is produced by the final merge, it necessarily has the ability to steal \(\operatorname{pre}(\theta(s))\).

Finally, Claim 4 shows that the answer node \(\theta(s)\) cannot be further extended: if it could steal once more, it would not be the last token of the final tokenization of the string.

With these claims, the Monotonic Path Property follows.

14.2 Detailed Proof↩︎

We begin by introducing auxiliary notation and several structural lemmas that will be used throughout the proof.

14.2.0.1 Ancestor Path.

For any canonical token \(x \in \mathcal{V}\), we define \(P(x)\) to be the unique path from \(x\) to the root of the Successor Forest \(\mathcal{F}_{\operatorname{suc}}\), following successor edges. Equivalently, \(P(x)\) consists of \(x\) and all of its ancestors in the Successor Forest.

Since the Successor Forest is acyclic and every non-atomic token has a unique successor, \(P(x)\) is well-defined and totally ordered by ancestry.

14.2.0.2 Rule Priority Convention.

Throughout the proof, we compare merge rules by their execution order in the dictionary: a rule \(r_i\) has higher priority than \(r_j\) (i.e., \(r_i > r_j\)) if and only if \(r_i\) is applied earlier in the standard BPE merge process.

With the above notation and lemmas in place, we now prove Theorem 1 by establishing four structural claims: upward closure, uniqueness, validity of \(\theta(s)\), and maximality.

14.2.0.7 Claim 1 (Upward Closure).

Let \(s\) be a non-empty string and let \(k\) be the longest canonical suffix token of \(s\). For any node \(w \in \operatorname{SufSucTree}(k)\), if \(w\) satisfies the Prefix Last-Token Condition (Definition 1) with respect to \(s\), then its parent \(\operatorname{suc}(w)\) in the Successor Forest (if it exists) also satisfies the Prefix Last-Token Condition.

14.2.0.12 Claim 2 (Uniqueness of the satisfying child).

Let \(s\) be a non-empty string. For any node \(v\), there exists at most one child \(w\) of \(v\) that satisfies the Prefix Last-Token Condition (Definition 1) with respect to \(s\).

14.2.0.13 Claim 3 (The answer node satisfies the condition).

Let \(w = \theta(s)\) be the last token for a non-empty string \(s\) after tokenization. Then \(w\) satisfies the Prefix Last-Token Condition (Definition 1) with respect to \(s\).

14.2.0.16 Claim 4 (The answer node has no children satisfying the condition).

Let \(s\) be a non-empty string. The answer node \(\theta(s)\) has no children that satisfy the Prefix Last-Token Condition (Definition 1) with respect to \(s\).

14.2.0.20 Conclusion of the Proof.

We now conclude the proof of Theorem 1. Claim 1 establishes that the Prefix Last-Token Condition is upward closed along successor edges. Claim 2 shows that for any node, at most one child can satisfy the condition. Claim 3 guarantees that the true last token \(\theta(s)\) does satisfy the condition, while Claim 4 shows that it is maximal and admits no further extension.

Together, these four claims imply that the set of tokens in \(\operatorname{SufSucTree}(t)\) satisfying the Prefix Last-Token Condition forms exactly a single, maximal path from \(\theta(s)\) to the root of the tree. This completes the proof.

15 Square-Root Tiled Transition Table↩︎

In an Aho–Corasick automaton [14], a straightforward implementation stores a full transition array over the alphabet \(\Sigma\) for every state, yielding constant-time transitions at the cost of a large memory footprint.

A key observation is that, for any state, its transition table differs from that of its suffix link only at entries corresponding to outgoing trie edges. This structural locality allows transitions to be shared persistently across states.

We exploit this property using a square-root tiling of the alphabet. The alphabet is partitioned into fixed-size tiles; each state stores references to its tiles, and a tile is duplicated only when a transition within it is modified. As a result, most tiles are shared between a state and its suffix link, while updates remain local to the affected tiles.

This representation preserves \(\mathcal{O}(1)\) transition queries and supports efficient construction, while substantially reducing memory usage in practice.

16 Eager Output Algorithm Details↩︎

Based on the Active Frontier definition in 6.1, we maintain the subgraph of the Prefix Tree of Tokens composed of the nodes in \(\mathcal{P}\) and their ancestors to identify the common ancestral path. The algorithm proceeds as follows:

1. Window Maintenance: We maintain \(\mathcal{P}\) using two pointers. The right pointer adds the new \(\theta(s)\). The left pointer advances to satisfy the bound \(|s| - d(s)\), removing expired tokens, where the function \(d\) is defined in 6.1.

2. Subgraph Tracking: We maintain the nodes in \(\mathcal{P}\) and their ancestors as a dynamic subgraph. For each node in this subgraph, we record the number of its children that are also part of the subgraph.

3. Eager Emission: We maintain the children of the virtual root. If the virtual root has exactly one child \(c\) in the subgraph, it implies that all Parental Candidates (and thus all possible futures) are descendants of the node \(c\). The token represented by \(c\) is therefore stable. We emit the corresponding token, update the virtual root to \(c\), and repeat the check.

Each node in the Prefix Tree of Tokens is inserted into the maintained subgraph exactly once, at the moment when the right pointer includes the corresponding last token into \(\mathcal{P}\). A node may persist in the subgraph even after it ceases to belong to \(\mathcal{P}\), but it will be removed at most once, when it no longer lies on the ancestral path of any active Parental Candidate.

During the advancement of the left pointer, each step removes either one node from the subgraph or performs a constant amount of bookkeeping without removal. Consequently, each node contributes \(\mathcal{O}(1)\) work over the entire execution of the algorithm.

Therefore, the eager output mechanism incurs an amortized \(\mathcal{O}(1)\) time overhead per input update.

17 Detailed Benchmarks↩︎

17.1 Experiment Setup↩︎

All benchmarks were conducted on a bare-metal server equipped with an Intel^® Xeon^® Platinum 8362 CPU @ 2.80GHz. To ensure reproducibility and minimize measurement noise, we applied the following configurations:

• CPU Isolation: Experiments were pinned to a single NUMA node (Node 1) containing 32 physical cores and 128 GB of RAM.

• System Tuning: Hyper-threading (SMT), Turbo Boost, and Address Space Layout Randomization (ASLR) were disabled.

• Concurrency: Tests were executed using 30 parallel workers. Each worker ran as an isolated, single-threaded process that independently loaded the tokenizer and dataset.

To ensure the validity of our results, we verified the correctness of our implementations against baseline methods prior to performance benchmarking. For all benchmarks (tokenizers and tiktoken bindings), we changed the global allocator to mimalloc [17], [18] and fixed seeds for hash functions to guarantee stable and reproducible latency measurements.

17.2 Datasets↩︎

We constructed three representative datasets using specific subsets of publicly available datasets. 2 provides a summary of the dataset statistics.

The specific sampling strategies were as follows:

• English & Chinese: We utilized the first Parquet shard from the standard training split of the Wikipedia dataset (20231101 dump), and employed a strided sampling strategy, extracting every 42nd document for English and every 60th document for Chinese.

• Code: We extracted data from the RedPajama GitHub subset [22], specifically using the file with the filename ““. We selected the first 2,500 documents from this file.

Additionally, for pathological input analysis, we constructed strings consisting of \(2^k\) repetitions of the character ‘a’.

17.3 Tokenizers↩︎

We evaluated a diverse set of tokenizers supported by two major libraries: Hugging Face’s tokenizers and OpenAI’s tiktoken.

17.3.0.1 Hugging Face Models.

3 summarizes the open-source tokenizers selected for our experiments. These models exhibit varying pre-tokenization strategies:

• Regex-Based: The majority of the models (DeepSeek-3.2, GPT-OSS, Llama-3.1, Llama-4, Mistral-3, and Qwen-3) employ regex-based rules to split input text before tokenization.

• Rule-Based: Ouro utilizes a digit-based pre-tokenization, and Gemma-3 employs a rule on space characters.

• None: Notably, CodeLlama applies no pre-tokenization logic.

Regarding the “properness” of dictionaries, the improper merge rules of Llama-3.1 are properized for our benchmarks (see Appendix 10). In contrast, Gemma-3’s merge rules are improper and cannot be properized (see Appendix 10.6).

17.3.0.2 OpenAI Models.

For the tiktoken library, we utilized the standard built-in encoding models. 4 lists the specific models that we used. Note that all tested tiktoken models employ regex-based pre-tokenization.

17.4 Detailed Results↩︎

We report throughput in terms of MiB/s based on the median of multiple execution runs. For each benchmark setting, throughput is computed as the total number of input bytes divided by the sum of the per-document median execution times. This aggregation reflects the effective end-to-end processing rate under repeated, independent tokenization workloads.

We evaluate two input regimes, indicated by the Eval column in [tab:detailed-benchmarks]. In the concat setting, all documents in a dataset are concatenated into a single input stream, separated by newline characters, and tokenized as one continuous sequence. In the per-doc setting, each document is provided to the tokenizer as an independent input, and execution times are measured separately per document before aggregation. The results reported in the main text (1) correspond to the concat setting, while [tab:detailed-benchmarks] provides the full breakdown across both evaluation regimes.

18 Profiling Analysis of Tokenization Pipelines↩︎

To better understand the system-level bottlenecks in existing tokenization pipelines, we profile the execution using Linux perf and visualize the results with inferno [39]. All flame graphs are collected from end-to-end tokenization runs, including normalization, pre-tokenization, and BPE, under the same configurations as the benchmark experiments in the main text.

For clarity of presentation, we apply light post-processing to the raw call stacks. Specifically, we retain only frames corresponding to the tokenization pipeline, truncate excessively deep stacks, and strip type and template information, preserving only function-level symbols and the structural hierarchy of call stacks. These transformations preserve the relative time distribution across pipeline stages while improving readability.

5 presents a representative flame graph for Hugging Face’s tokenizers library with the tokenizer Qwen-3, using our incremental non-eager BPE implementation on the Code dataset. The BPE merge phase itself (tokenize_without_cache) constitutes a minor fraction of the total runtime, highlighting that, in this pipeline, the overall throughput is primarily constrained by non-BPE components.

6 profiles tiktoken (O200K) when replacing its BPE stage with our incremental non-eager implementation on the Code dataset. It highlights that the bottleneck shifts to regex-based pre-tokenization, even when the BPE merge phase itself is asymptotically efficient.

7 profiles the original tiktoken baseline under pathological inputs of increasing length. As the input size grows, the BPE merge phase increasingly dominates the execution time, providing a fine-grained explanation for the throughput trends reported in 3. These pathological inputs are not intended to model realistic workloads, but to isolate and stress-test the asymptotic behavior of the BPE merge stage.

19 Comparison with Other Incremental BPE Implementations↩︎

In this section, we provide a detailed theoretical and empirical comparison between our algorithm and other existing incremental BPE implementations in Rust, specifically those found in the crate bpe of the GitHub repository rust-gems [12].

For the discussion about time and space complexity, let \(\Sigma\) be the size of the alphabet, \(n\) be the input length, \(m\) the vocabulary size, \(t_i\) the length of the \(i\)-th token, and \(t\) the maximum token length.

Within rust-gems, there are three main implementations of BPE as the methods of the structure BytePairEncoding. The encode_via_bitfield method utilizes a binary heap and does not support incremental processing, placing it outside the scope of discussion. The remaining two methods, encode_via_table and encode_via_backtracking, support incremental tokenization and are analyzed in the following.

All empirical tests and evaluations were performed by directly replacing the core BPE implementation in the tiktoken [4] library. The tests were conducted on a Virtual Private Server (VPS), utilizing 8 cores of an Intel^® Xeon^® Gold 6448Y CPU situated on a single NUMA node, alongside a 16 GB slice of RAM.

19.1 Theoretical Time Complexity↩︎

Both encode_via_table and encode_via_backtracking rely on a core underlying function: is_valid_token_pair. This function checks whether two tokens can be placed adjacently, ensuring that applying BPE to their concatenated string yields exactly the same two tokens.

Assuming the “last token” of a string is determined, if a new token can be validly placed adjacent to it, the “last token” of the newly formed string should exactly be this new token.

The validation process takes two tokens, iteratively un-merges either the first token to its successor or the second token to its predecessor according to the rule with the lower priority, and verifies if the token boundary survives. This verification takes \(\mathcal{O}(t)\) time. Although it can be pre-computed or cached to achieve \(\mathcal{O}(1)\) query time, the table will be \(\mathcal{O}(m^2)\), which may not be preferable for production.

19.1.0.1 Method 1: encode_via_table

This method processes the tokenization with an Aho–Corasick automaton. At each step, it iterates through the matching suffix tokens from longest to shortest for the current prefix, validating each suffix token via is_valid_token_pair.

• Complexity: In the “best” case scenario, where the longest match is always the correct last token, it still requires at least one validation per step, yielding a lower bound of \(\Omega(n)\) checks. In the worst case, all suffix tokens must be checked, resulting in \(\mathcal{O}(n t^2)\) time complexity.

• Eager Output: Because this method maintains the prefix tree of tokens essentially, it can theoretically be adapted to support our proposed eager output mechanism.

19.1.0.2 Method 2: encode_via_backtracking

This method employs a greedy strategy. It attempts to find the longest token among the prefixes of the un-tokenized string suffix, verifying it against the currently maintained token sequence via is_valid_token_pair. During the tokenization, it maintains a bit-field to record the positions that cause backtracking to avoid re-computation.

It is notable that the algorithm will backtrack if the current token sequence corresponds to a path from a leaf to the root in the prefix tree of tokens, which indicates no subsequent prefix token will form a valid sequence.

• Complexity: In the “best” case, where the greedy choice is always correct, the validation cost is amortized over the token length, yielding \(\Omega(n)\). However, in the worst case, whenever the algorithm backtracks, it incurs the cost of validating all possible prefix tokens with the last token, yielding \(\mathcal{O}(n t^2)\).

• Eager Output: As the algorithm is greedy, there is no trivial way to apply our eager output mechanism to this implementation.

5 summarizes the complexity of these methods alongside our proposed algorithm. Our method incorporates a simple optimization where we first verify the longest suffix token before traversing the Suffix-Successor Tree, ensuring our “best” case also achieves an \(\Omega(n)\) lower bound.

19.2 Constructed Pathological Case↩︎

To approach the worst-case complexity, we designed an adversarial corner case. This construction deliberately traps algorithms relying on greedy or longest-prefix matching into massive validation and backtracking cycles.

First, to achieve a merge depth of \(K=4096\), we expand the base alphabet from single bytes to 2-byte pairs. To strictly prevent accidental cross-boundary merges, we construct base tokens \(B_1, B_2, \ldots, B_K\) from \(\mathcal{B}\): \[\mathcal{B} = \{(i, j) \mid i, j \in \{0, 1, \dots, 255\}, i < j\}\text{.}\] The structural constraint of \(\mathcal{B}\) guarantees that placing any two base tokens adjacent to each other will not trigger unintended cross-boundary merges.

Next, using these \(K\) distinct base tokens, we construct a sequence \(\mathcal{S}\) of \(4 K\) bytes: \[\mathcal{S} = B_1 \cdots B_K B_K \cdots B_1\text{.}\]

We then strategically assign merge rule priorities to establish the trap: the absolute highest priority is assigned to the rule merging the two identical tokens located exactly at the sequence center, i.e., \((B_K, B_K)\). Subsequently, we inject deep nested merge rules originating from the center towards the two ends, i.e.: \[(B_{K-1}, B_K), (B_{K-2}, B_{K-1} B_K), \ldots \quad\text{and}\quad (B_K, B_{K-1}), (B_K B_{K-1}, B_{K-2}), \ldots\] establishing a merge depth of \(\mathcal{O}(K)\).

The input string is constructed as a concatenation of 128 repetitions of \(\mathcal{S}\). Under this pathological input, our method, with worst-case time complexity guarantees, required 37 ms to tokenize the sequence. In stark contrast, encode_via_table and encode_via_backtracking required 15.3 s and 23.9 s, respectively.

19.3 Space Complexity↩︎

19.3.0.1 Initialization

Our implementation utilizes a Square-Root Tiled Transition Table for \(\mathcal{O}(1)\) transitions (detailed in Appendix 15), requiring \(\Theta(\sqrt{\Sigma})\) space per state. In contrast, rust-gems uses a double-array implementation of Aho-Corasick automata [40], which performs transitions in \(\mathcal{O}(1)\) time and normally requires \(\mathcal{O}(1)\) space per state, but potentially up to \(\mathcal{O}(\Sigma)\) in the worst case.

Additionally, our method requires pre-computing a Centroid Search Tree based on Centroid Decomposition for each Suffix-Successor Tree, leading to an initialization space complexity of \(\mathcal{O}(\sum t_i) = \mathcal{O}(m t)\). rust-gems requires no more than \(\mathcal{O}(m)\) auxiliary space.

19.3.0.2 Tokenization and Eager Output

During standard non-eager tokenization, both our method and the rust-gems implementations require \(\mathcal{O}(n)\) space to record the token sequence.

However, space complexity behavior differs when applying our eager output mechanism. As detailed in 6, the algorithm maintains the state using a two-pointer approach. Token nodes may persist in the state even after they cease to belong to \(\mathcal{P}\), because they lie in the window. Therefore, the space complexity relates to the maximum number of nodes simultaneously maintained by the two-pointer algorithm. While a theoretically safe upper bound is \(\mathcal{O}(\min(n, m t))\), empirical evaluations show that the practical memory footprint is much smaller.

6 demonstrates the maximum number of nodes in the window maintained by the two-pointer algorithm with the datasets described in 2.

19.4 End-to-End Benchmarks↩︎

We evaluated the end-to-end tokenization speeds for rust-gems and ours. The tokenizer model P50K failed to run with rust-gems; thus, it was excluded from the benchmarks.

The median CPU times (in seconds) across standard datasets are presented in 7. The results are also demonstrated as a violin plot in 8. The baseline implementation is the original BPE implementation in tiktoken. Our incremental approach consistently matches or outperforms the backtracking and table-based implementations.

References↩︎