# A Formal Perspective on Byte-Pair Encoding

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 29 Jun 2023.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing](https://mlsanity.com/paper/1808.06226/) (2018)
- [BLOOM: A 176B-Parameter Open-Access Multilingual Language Model](https://mlsanity.com/paper/2211.05100/) (2022)
- [DialoGPT: Large-Scale Generative Pre-training for Conversational Response Generation](https://mlsanity.com/paper/1911.00536/) (2019)
- [Byte Pair Encoding is Suboptimal for Language Model Pretraining](https://mlsanity.com/paper/2004.03720/) (2020)
- [CCAligned: A Massive Collection of Cross-Lingual Web-Document Pairs](https://mlsanity.com/paper/1911.06154/) (2019)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [A Call for Prudent Choice of Subword Merge Operations in Neural Machine Translation](https://mlsanity.com/paper/1905.10453/) (2019)
- [String Submodular Functions with Curvature Constraints](https://mlsanity.com/paper/1303.3018/) (2013)

## Built on by (most cited first, 30 of 36)

- [MYTE: Morphology-Driven Byte Encoding for Better and Fairer Multilingual Language Modeling](https://mlsanity.com/paper/2403.10691/) (2024)
- [The Foundations of Tokenization: Statistical and Computational Concerns](https://mlsanity.com/paper/2407.11606/) (2024)
- [Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenization](https://mlsanity.com/paper/2508.04796/) (2025)
- [ActionPiece: Contextually Tokenizing Action Sequences for Generative Recommendation](https://mlsanity.com/paper/2502.13581/) (2025)
- [Theoretical Analysis of Byte-Pair Encoding](https://mlsanity.com/paper/2411.08671/) (2024)
- [LLM4VV: Developing LLM-Driven Testsuite for Compiler Validation](https://mlsanity.com/paper/2310.04963/) (2023)
- [Two Counterexamples to Tokenization and the Noiseless Channel](https://mlsanity.com/paper/2402.14614/) (2024)
- [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)
- [The Roots of Performance Disparity in Multilingual Language Models: Intrinsic Modeling Difficulty or Design Choices?](https://mlsanity.com/paper/2601.07220/) (2026)
- [Tokenisation is NP-Complete](https://mlsanity.com/paper/2412.15210/) (2024)
- [Breaking the Tokenizer Barrier: On-Policy Distillation across Model Families](https://mlsanity.com/paper/2606.09456/) (2026)
- [Improving Large Language Model Planning with Action Sequence Similarity](https://mlsanity.com/paper/2505.01009/) (2025)
- [Stop Taking Tokenizers for Granted: They Are Core Design Decisions in Large Language Models](https://mlsanity.com/paper/2601.13260/) (2026)
- [Tokenization as Finite-State Transduction](https://mlsanity.com/paper/2410.15696/) (2024)
- [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)
- [Auditing Pay-Per-Token in Large Language Models](https://mlsanity.com/paper/2510.05181/) (2025)
- [Tokenisation via Convex Relaxations](https://mlsanity.com/paper/2605.22821/) (2026)
- [Membership Inference Attacks on Tokenizers of Large Language Models](https://mlsanity.com/paper/2510.05699/) (2025)
- [UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8](https://mlsanity.com/paper/2511.05578/) (2025)
- [AdaptBPE: From General Purpose to Specialized Tokenizers](https://mlsanity.com/paper/2601.21665/) (2026)
- [Syllabic Agglutinative Tokenizations for Indonesian LLM: A Study from Gasing Literacy Learning System](https://mlsanity.com/paper/2601.11643/) (2026)
- [Decoupling the Benefits of Subword Tokenization for Language Model Training via Byte-level Simulation](https://mlsanity.com/paper/2604.27263/) (2026)
- [A cost minimization approach to fix the vocabulary size in a tokenizer for an End-to-End ASR system](https://mlsanity.com/paper/2406.02563/) (2024)
- [Morphological Typology in BPE Subword Productivity and Language Modeling](https://mlsanity.com/paper/2410.23656/) (2024)
- [Train It and Forget It: Merge Lists are Unnecessary for BPE Inference in Language Models](https://mlsanity.com/paper/2508.06621/) (2025)
- [ByteFlow: Language Modeling through Adaptive Byte Compression without a Tokenizer](https://mlsanity.com/paper/2603.03583/) (2026)
- [Taking Tokenization off the Host for Agentic LLM Serving](https://mlsanity.com/paper/2610.13325/) (2026)
- [Batching BPE Tokenization Merges](https://mlsanity.com/paper/2408.04653/) (2024)

## Abstract (arXiv)

Byte-Pair Encoding (BPE) is a popular algorithm used for tokenizing data in NLP, despite being devised initially as a compression method. BPE appears to be a greedy algorithm at face value, but the underlying optimization problem that BPE seeks to solve has not yet been laid down. We formalize BPE as a combinatorial optimization problem. Via submodular functions, we prove that the iterative greedy version is a frac1σ(boldsymbolμ^star)(1-e^-σ(boldsymbolμ^star))-approximation of an optimal merge sequence, where σ(boldsymbolμ^star) is the total backward curvature with respect to the optimal merge sequence boldsymbolμ^star. Empirically the lower bound of the approximation is ≈ 0.37. We provide a faster implementation of BPE which improves the runtime complexity from Oleft(N Mright) to Oleft(N log Mright), where N is the sequence length and M is the merge count. Finally, we optimize the brute-force algorithm for optimal BPE using memoization.