# Theoretical Analysis of Byte-Pair Encoding

arXiv: https://arxiv.org/abs/2411.08671 · HTML: https://mlsanity.com/paper/2411.08671/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 36 references that are in the map.
- First posted on arXiv 13 Nov 2024.

## Builds on (most cited first, 6 of 6)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Between words and characters: A Brief History of Open-Vocabulary Modeling and Tokenization in NLP](https://mlsanity.com/paper/2112.10508/) (2021)
- [Tokenizer Choice For LLM Training: Negligible or Crucial?](https://mlsanity.com/paper/2310.08754/) (2023)
- [Tokenization Is More Than Compression](https://mlsanity.com/paper/2402.18376/) (2024)
- [A Formal Perspective on Byte-Pair Encoding](https://mlsanity.com/paper/2306.16837/) (2023)

## Built on by (most cited first, 16 of 16)

- [Causal Estimation of Tokenisation Bias](https://mlsanity.com/paper/2506.03149/) (2025)
- [Is Your LLM Overcharging You? Tokenization, Transparency, and Incentives](https://mlsanity.com/paper/2505.21627/) (2025)
- [Evaluating Tokenizer Performance of Large Language Models Across Official Indian Languages](https://mlsanity.com/paper/2411.12240/) (2024)
- [Tokenisation is NP-Complete](https://mlsanity.com/paper/2412.15210/) (2024)
- [Unified Multimodal Understanding via Byte-Pair Visual Encoding](https://mlsanity.com/paper/2506.23639/) (2025)
- [A Partition Cover Approach to Tokenization](https://mlsanity.com/paper/2501.06246/) (2025)
- [Tokenisation over Bounded Alphabets is Hard](https://mlsanity.com/paper/2511.15709/) (2025)
- [Tokenisation via Convex Relaxations](https://mlsanity.com/paper/2605.22821/) (2026)
- [PerCache: Predictive Hierarchical Cache for RAG Applications on Mobile Devices](https://mlsanity.com/paper/2601.11553/) (2025)
- [Skill Reuse as Compression in Agentic RL](https://mlsanity.com/paper/2605.31509/) (2026)
- [KunlunBaize: LLM with Multi-Scale Convolution and Multi-Token Prediction Under TransformerX Framework](https://mlsanity.com/paper/2503.04784/) (2025)
- [Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-service](https://mlsanity.com/paper/2506.06446/) (2025)
- [A Multi-head-based architecture for effective morphological tagging in Russian with open dictionary](https://mlsanity.com/paper/2604.02926/) (2026)
- [Understanding Secret Leakage Risks in Code LLMs: A Tokenization Perspective](https://mlsanity.com/paper/2604.17814/) (2026)
- [Objective vs. Search: Decomposing What Makes a Good Tokeniser](https://mlsanity.com/paper/2609.19145/) (2026)
- [Tracing Morphology, Semantics, and Divergence in Language Acquisition](https://mlsanity.com/paper/2610.19041/) (2026)

## Abstract (arXiv)

Byte-Pair Encoding (BPE) is a widely used method for subword tokenization, with origins in grammar-based text compression. It is employed in a variety of language processing tasks such as machine translation or large language model (LLM) pretraining, to create a token dictionary of a prescribed size. Most evaluations of BPE to date are empirical, and the reasons for its good practical performance are not well understood. In this paper we focus on the optimization problem underlying BPE: finding a pair encoding that achieves optimal compression utility. We show that this problem is APX-complete, indicating that it is unlikely to admit a polynomial-time approximation scheme. This answers, in a stronger form, a question recently raised by Zouhar et al. On the positive side, we show that BPE approximates the compression utility of the optimal pair encoding to a worst-case factor between 0.333 and 0.625. Our results aim to explain the ongoing success of BPE and are, to our knowledge, the first rigorous guarantees on its compression utility that hold for all inputs.