DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.80

Theoretical Analysis of Byte-Pair Encoding

Authors: László Kozma and Johannes Voderholzer

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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. [Zouhar et al., 2023]. 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.

Cite as

László Kozma and Johannes Voderholzer. Theoretical Analysis of Byte-Pair Encoding. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 80:1-80:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kozma_et_al:LIPIcs.ESA.2026.80,
  author =	{Kozma, L\'{a}szl\'{o} and Voderholzer, Johannes},
  title =	{{Theoretical Analysis of Byte-Pair Encoding}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{80:1--80:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.80},
  URN =		{urn:nbn:de:0030-drops-272166},
  doi =		{10.4230/LIPIcs.ESA.2026.80},
  annote =	{Keywords: byte pair encoding, approximation, hardness, tokenization}
}

Search Results

Documents authored by Voderholzer, Johannes

Theoretical Analysis of Byte-Pair Encoding

Abstract

Cite as

Thanks for your feedback!

Could not send message