mlsanityData to 14 Oct 2026

A Formal Perspective on Byte-Pair Encoding

arXiv 2306.16837 ↗First posted 29 Jun 2023cs.CL math.OCcited by 36

Not on the map. Why?

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.

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

10 of 22 references.

References · 10

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,918
  3. 2018SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processingcited by 1,989
  4. 2022BLOOM: A 176B-Parameter Open-Access Multilingual Language Modelcited by 1,984
  5. 2019DialoGPT: Large-Scale Generative Pre-training for Conversational Response Generationcited by 842
  6. 2020Byte Pair Encoding is Suboptimal for Language Model Pretrainingcited by 192
  7. 2019CCAligned: A Massive Collection of Cross-Lingual Web-Document Pairscited by 136
  8. 2022Submodularity In Machine Learning and Artificial Intelligencecited by 38
  9. 2019A Call for Prudent Choice of Subword Merge Operations in Neural Machine Translationcited by 30
  10. 2013String Submodular Functions with Curvature Constraintscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 10; 2025: 12; 2026: 13.

36 papers.

Sort:

By area:

  1. 2024MYTE: Morphology-Driven Byte Encoding for Better and Fairer Multilingual Language Modelingcited by 40
  2. 2024The Foundations of Tokenization: Statistical and Computational Concernscited by 22
  3. 2025Parity-Aware Byte-Pair Encoding: Improving Cross-lingual Fairness in Tokenizationcited by 20
  4. 2025ActionPiece: Contextually Tokenizing Action Sequences for Generative Recommendationcited by 18
  5. 2024Theoretical Analysis of Byte-Pair Encodingcited by 16
  6. 2023LLM4VV: Developing LLM-Driven Testsuite for Compiler Validationcited by 15
  7. 2024Two Counterexamples to Tokenization and the Noiseless Channelcited by 13
  8. 2025Is Your LLM Overcharging You? Tokenization, Transparency, and Incentivescited by 13
  9. 2024Evaluating Tokenizer Performance of Large Language Models Across Official Indian Languagescited by 11
  10. 2026The Roots of Performance Disparity in Multilingual Language Models: Intrinsic Modeling Difficulty or Design Choices?cited by 11
  11. 2024Tokenisation is NP-Completecited by 10
  12. 2026Breaking the Tokenizer Barrier: On-Policy Distillation across Model Familiescited by 9
24 more
  1. 2025Improving Large Language Model Planning with Action Sequence Similaritycited by 7
  2. 2026Stop Taking Tokenizers for Granted: They Are Core Design Decisions in Large Language Modelscited by 6
  3. 2024Tokenization as Finite-State Transductioncited by 5
  4. 2025A Partition Cover Approach to Tokenizationcited by 5
  5. 2025Tokenisation over Bounded Alphabets is Hardcited by 5
  6. 2025Auditing Pay-Per-Token in Large Language Modelscited by 4
  7. 2026Tokenisation via Convex Relaxationscited by 4
  8. 2025Membership Inference Attacks on Tokenizers of Large Language Modelscited by 3
  9. 2025UTF-8 Plumbing: Byte-level Tokenizers Unavoidably Enable LLMs to Generate Ill-formed UTF-8cited by 3
  10. 2026AdaptBPE: From General Purpose to Specialized Tokenizerscited by 3
  11. 2026Syllabic Agglutinative Tokenizations for Indonesian LLM: A Study from Gasing Literacy Learning Systemcited by 2
  12. 2026Decoupling the Benefits of Subword Tokenization for Language Model Training via Byte-level Simulationcited by 2
  13. 2024A cost minimization approach to fix the vocabulary size in a tokenizer for an End-to-End ASR systemcited by 1
  14. 2024Morphological Typology in BPE Subword Productivity and Language Modelingcited by 1
  15. 2025Train It and Forget It: Merge Lists are Unnecessary for BPE Inference in Language Modelscited by 1
  16. 2026ByteFlow: Language Modeling through Adaptive Byte Compression without a Tokenizercited by 1
  17. 2026Taking Tokenization off the Host for Agentic LLM Servingcited by 1
  18. 2024Batching BPE Tokenization Mergescited by 0
  19. 2025Tokenization Multiplicity Leads to Arbitrary Price Variation in LLM-as-a-servicecited by 0
  20. 2025Evaluating Subword Tokenization Techniques for Bengali: A Benchmark Study with BengaliBPEcited by 0
  21. 2026Tokenization and Morphological Fidelity in Uralic NLP: A Cross-Lingual Evaluationcited by 0
  22. 2026Narrating For You: Prompt-guided Audio-visual Narrating Face Generation Employing Multi-entangled Latent Spacecited by 0
  23. 2026Mr3D-VL: A generalist vision language foundation model for Multiparametric 3D Magnetic Resonance Imagingcited by 0
  24. 2026To Each Language Its Tokenizer: Modular Tokenizers for Efficient Multilingual LLMscited by 0