# Incremental BPE Tokenization

Source: [Incremental BPE Tokenization](<https://www.sota2.com/research/paper/6a1d11d9dbd7150506f83d7b>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-06-02T05:00:05.014Z

Authors: Shenghu Jiang, Ruihao Gong

Published: 2026-05-29T04:04:32.000Z

## Abstract

We propose a novel algorithm for incremental Byte Pair Encoding (BPE) tokenization. The algorithm processes each input byte in worst-case $\\mathcal{O}(\\log^2 t)$ time, leading to an overall complexity of $\\mathcal{O}(n \\log^2 t)$, where $n$ is the input length and $t$ is the maximum token length. The algorithm incrementally maintains BPE tokenization results for every prefix of the input text, implementing the standard BPE merge procedure defined by a fixed set of merge rules. This enables efficient partial tokenization in streaming settings. Functioning as a drop-in replacement for standard BPE, our approach achieves a speedup of up to ${\\sim}3\\times$ over Hugging Face's tokenizers, and demonstrates significant latency reductions over OpenAI's tiktoken on pathological inputs. We further introduce an eager output algorithm that enables streaming output, emitting tokens as soon as token boundaries are determined during incremental tokenization. Overall, our results demonstrate that BPE tokenization can be performed incrementally with strong worst-case guarantees, while providing practical latency benefits in modern large language model pipelines. Code: https://github.com/ModelTC/mtc-inc-bpe

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Incremental BPE Tokenization on English](<https://www.sota2.com/research/sota/incremental-bpe-tokenization-on-english.md>): Incremental BPE Tokenization; English; Median End-to-end CPU Time (s): 0.925.

- [Incremental BPE Tokenization on Chinese](<https://www.sota2.com/research/sota/incremental-bpe-tokenization-on-chinese.md>): Incremental BPE Tokenization; Chinese; End-to-end CPU Time (s): 0.815.

- [Incremental BPE Tokenization on Code](<https://www.sota2.com/research/sota/incremental-bpe-tokenization-on-code.md>): Incremental BPE Tokenization; Code; End-to-end CPU Time (s): 1.369.

- [BPE Tokenization on English](<https://www.sota2.com/research/sota/bpe-tokenization-on-english.md>): BPE Tokenization; English; Speedup Factor: 3.13.

- [BPE Tokenization on Chinese](<https://www.sota2.com/research/sota/bpe-tokenization-on-chinese.md>): BPE Tokenization; Chinese; Speedup Factor: 1.59.

- [BPE Tokenization on Code](<https://www.sota2.com/research/sota/bpe-tokenization-on-code.md>): BPE Tokenization; Code; Speedup Factor: 2.88.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2605.30813>)

[PDF](<https://arxiv.org/pdf/2605.30813.pdf>)
