Related papers: Incremental BPE Tokenization

Incremental BPE Tokenization

URL: http://arxiv.org/abs/2605.30813v1
Date: Fri, 29 May 2026 04:04:32 GMT
Title: Incremental BPE Tokenization
Abstract summary: We propose a novel algorithm for incremental Byte Pair.<n>Model (BPE) tokenization.<n>We demonstrate significant latency reductions over OpenAI's tiktoken on pathological inputs.
Score: 12.857819598120676
License: http://creativecommons.org/licenses/by/4.0/
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

Related papers

Tokenisation via Convex Relaxations [14.99534435778172]
Tokenisation is an integral part of the current NLP pipeline.<n>We formulate tokeniser construction as a linear program and solve it using convex optimisation tools.<n>We find ConvexTok consistently improves intrinsic tokenisation metrics and the bits-per-byte (BpB) achieved by language models.
arXiv Detail & Related papers (2026-05-21T17:59:56Z)
DNATokenizer: A GPU-First Byte-to-Identifier Tokenizer for High-Throughput DNA Language Models [0.0]
DNATok is a GPU-first tokenization system that replaces general-purpose string processing with byte lookup table (LUT)-based identifier streaming and an overlapped host-to-device (H2D)/compute pipeline.<n>DNATok achieves 84-95x higher encoding throughput than optimized Hugging Face baselines and up to 1.9x higher H2D throughput.
arXiv Detail & Related papers (2026-01-09T05:08:17Z)
Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization [53.22544362024936]
Tokenization is the first -- and often least scrutinized -- step of most NLP pipelines.<n>Standard algorithms for learning tokenizers rely on frequency-based objectives.<n>We introduce Parity-aware Byte Pair.<n>We find empirically that Parity-aware BPE leads to more equitable token counts across languages.
arXiv Detail & Related papers (2025-08-06T18:14:43Z)
BlockBPE: Parallel BPE Tokenization [0.0]
BlockBPE is a parallel GPU implementation of byte-pair encoding (BPE)<n>It achieves near linear-time complexity under realistic assumptions.<n>On high-batch inference workloads, BlockBPE achieves up to 2x higher throughput than tiktoken and 2.5x over HuggingFace Tokenizers.
arXiv Detail & Related papers (2025-07-16T06:12:41Z)
A Partition Cover Approach to Tokenization [24.595558878756787]
Tokenization is a process of encoding strings into tokens of a fixed vocabulary size.<n>Byte-Pair corpora (BPE) formulates the tokenization problem as a compression problem and tackles it by performing sequences of merges.<n>We show that GreedTok outperforms BPE and Unigram on compression and achieves a covering score comparable to GreedWMC.
arXiv Detail & Related papers (2025-01-08T17:07:07Z)
Batching BPE Tokenization Merges [55.2480439325792]
BatchBPE is an open-source pure Python implementation of the Byte Pair algorithm. It is used to train a high quality tokenizer on a basic laptop.
arXiv Detail & Related papers (2024-08-05T09:37:21Z)
Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
arXiv Detail & Related papers (2024-06-07T12:07:16Z)
Scaffold-BPE: Enhancing Byte Pair Encoding for Large Language Models with Simple and Effective Scaffold Token Removal [58.29382184006158]
We propose Scaffold-BPE, which incorporates a dynamic scaffold token removal mechanism by parameter-free, computation-light, and easy-to-implement modifications to the original BPE method. On extensive experiments across language modeling and even machine translation, Scaffold-BPE consistently outperforms the original BPE.
arXiv Detail & Related papers (2024-04-27T07:12:07Z)
Tokenization and the Noiseless Channel [71.25796813073399]
Good tokenizers lead to emphefficient channel usage, where the channel is the means by which some input is conveyed to the model. In machine translation, we find that across multiple tokenizers, the R'enyi entropy with $alpha = 2.5$ has a very strong correlation with textscBleu: $0.78$ in comparison to just $-0.32$ for compressed length.
arXiv Detail & Related papers (2023-06-29T10:32:09Z)
A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
Byte-Pair imation (BPE) is a popular algorithm used for tokenizing data in NLP, despite being devised initially as a compression method. We provide a faster implementation of BPE which improves the runtime complexity from $mathcalOleft(N Mright)$ to $mathcalOleft(N log Mright)$, where $N$ is the sequence length and $M$ is the merge count.
arXiv Detail & Related papers (2023-06-29T10:29:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.