BlockBPE: Parallel BPE Tokenization

• URL: http://arxiv.org/abs/2507.11941v1
• Date: Wed, 16 Jul 2025 06:12:41 GMT
• Title: BlockBPE: Parallel BPE Tokenization
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tokenization is a critical preprocessing step in large language model pipelines, yet widely-used implementations remain CPU-bound and suboptimal for batch inference workflows on GPU. We present BlockBPE, a parallel GPU implementation of byte-pair encoding (BPE) that achieves near linear-time complexity under realistic assumptions and is optimized for high-throughput, batch inference. Unlike existing Rust-based tokenizers such as HuggingFace Tokenizers or OpenAI's tiktoken-whose runtimes are dominated by Regex pre-tokenization and exhibit $O(n \log n)$ runtime-BlockBPE eliminates the Regex pre-tokenization which leads to small loss in generation quality, but enables highly parallelized token merges within thread blocks, reducing overall complexity to $O(nd)$ where $d \ll n$. On high-batch inference workloads, BlockBPE achieves up to 2x higher throughput than tiktoken and 2.5x over HuggingFace Tokenizers.

Related papers

• Incremental BPE Tokenization [12.857819598120676]
  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.
  arXiv  Detail & Related papers  (2026-05-29T04:04:32Z)
• Faster Superword Tokenization [10.08525888469663]
  We present a two-phase BoundlessBPE that separates first-phase learning of regular merges from second-phase learning of supermerges.<n>For each of BoundlessBPE, SuperBPE, and BPE, we open-source both a reference Python implementation and a fast Rust implementation.
  arXiv  Detail & Related papers  (2026-04-06T21:43:48Z)
• GPUTOK: GPU Accelerated Byte Level BPE Tokenization [0.0]
  We build a GPU-based byte-level BPE tokenizer that follows GPT-2's merge rules.<n>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.<n>On WikiText103 sequences up to 131k tokens, the optimized tokenizer produces the same longest inputs, is about 1.7x faster than tiktoken and about 7.6x faster than the HuggingFace GPT-2 tokenizer.
  arXiv  Detail & Related papers  (2026-03-03T04:48:28Z)
• Peek2: A Regex-free implementation of pretokenizers for Byte-level BPE [0.0]
  Peek2 is a drop-in replacement for cl100k-like pretokenizers used in GPT-3, LLaMa-3, and Qwen-2.5.<n>It delivers a $ 1.11times $ improvement in overall throughput across the entire Byte-level BPE encoding process.
  arXiv  Detail & Related papers  (2026-01-09T15:05:09Z)
• 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)
• Learning to Parallel: Accelerating Diffusion Large Language Models via Learnable Parallel Decoding [21.609237262034636]
  Autoregressive decoding in large language models (LLMs) requires $mathcalO(n)$ sequential steps for $n$ tokens.<n>We propose Learning to Parallel Decode (Learn2PD), a framework that trains a lightweight and adaptive filter model to predict, for each token position, whether the current prediction matches the final output.<n>This learned filter approximates an oracle parallel decoding strategy that unmasks tokens only when correctly predicted.
  arXiv  Detail & Related papers  (2025-09-29T17:59:54Z)
• Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization [62.35048154917945]
  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)
• Pre$^3$: Enabling Deterministic Pushdown Automata for Faster Structured LLM Generation [32.84102573817514]
  Existing methods parse LR(1) grammars into a pushdown automaton (PDA)<n>We propose Pre$3$ that exploits deterministic pushdown automata (DPDA)<n>Pre$3$ can be seamlessly integrated into standard LLM inference frameworks.
  arXiv  Detail & Related papers  (2025-06-04T12:30:30Z)
• SpecPipe: Accelerating Pipeline Parallelism-based LLM Inference with Speculative Decoding [33.55718885446209]
  We introduce SpecPipe, which fills the pipeline with speculative tokens step-by-step.<n>By maximizing the hardware utilization, SpecPipe decodes one token per pipeline step ideally.<n>We implement SpecPipe-DB with dynamic workloads by SpecPipe-DB for single- and multi-request inference.
  arXiv  Detail & Related papers  (2025-04-05T08:31:10Z)
• A partition cover approach to tokenization [27.78022124795594]
  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)
• A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention [43.211427581302715]
  We propose Hierarchically Pruned Attention (HiP) to increase context length in large language models.<n>HiP reduces the time complexity of the attention mechanism to $O(T log T)$ and the space complexity to $O(T)$, where $T$ is the sequence length.<n>We show that HiP significantly reduces both prefill and decoding latencies, as well as memory usage, while maintaining high-quality generation with minimal degradation.
  arXiv  Detail & Related papers  (2024-06-14T08:32:45Z)
• Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [19.167604927651073]
  Auto-regressive decoding of Large Language Models (LLMs) results in significant overheads in their hardware performance. We propose a novel parallel prompt decoding that requires only $0.0002$% trainable parameters, enabling efficient training on a single A100-40GB GPU in just 16 hours. Our approach demonstrates up to 2.49$times$ speedup and maintains a minimal memory overhead of just $0.0004$%.
  arXiv  Detail & Related papers  (2024-05-28T22:19:30Z)
• SkipDecode: Autoregressive Skip Decoding with Batching and Caching for Efficient LLM Inference [17.947904697850433]
  We present SkipDecode, a token-level early exit method for batch inferencing and KeyValue caching. It overcomes prior constraints by setting up singular-level exit point for every token in a batch at each sequence position. It also guarantees a monotonic decrease in exit points, thereby eliminating the need to recompute KV Caches for preceding tokens.
  arXiv  Detail & Related papers  (2023-07-05T19:59:09Z)
• 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)
• H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models [110.06476624089679]
  We introduce a novel approach for implementing the KV cache which significantly reduces its memory footprint. Our approach is based on the observation that a small portion of tokens contributes most of the value when computing attention scores. We propose Heavy Hitter (H$$O), a KV cache eviction policy that dynamically retains a balance of recent and H$$ tokens.
  arXiv  Detail & Related papers  (2023-06-24T20:11:14Z)
• Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Verification [151.62491805851107]
  We develop $beta$-CROWN, a bound propagation based verifier that can fully encode per-neuron splits. $beta$-CROWN is close to three orders of magnitude faster than LP-based BaB methods for robustness verification. By terminating BaB early, our method can also be used for incomplete verification.
  arXiv  Detail & Related papers  (2021-03-11T11:56:54Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.