arXiv cs.CL· L\'aszl\'o Kozma, Johannes Voderholzer·· 12 小时前AI 评分18
BPE 的理论分析：字节对编码的压缩效用优化问题被证明为 APX-complete
Theoretical Analysis of Byte-Pair Encoding
AI 导读
研究者证明 BPE 底层的最优配对编码优化问题是 APX-complete，不太可能存在多项式时间近似方案，这以更强形式回答了 Zouhar 等人近期提出的问题。
正文 · 原文
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.
On the positive side, we show that BPE approximates the compression utility of the optimal pair encoding to a worst-case factor between $1/3$ and $(1-e^{-2})/2 \approx 0.4324$. 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.
| Comments: | Extended version of ESA 2026 paper. Changes in v2: (1) an upper bound of ~0.4324 on the approximation ratio of BPE, improving the earlier 0.625, and (2) a modified proof of Claim 5, fixing an inaccuracy in v1 |
| Subjects: | Data Structures and Algorithms (cs.DS); Computation and Language (cs.CL) |
| Cite as: | arXiv:2411.08671 [cs.DS] |
| (or arXiv:2411.08671v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2411.08671 arXiv-issued DOI via DataCite |
Submission history
From: László Kozma [view email]
[v1]
Wed, 13 Nov 2024 15:04:02 UTC (24 KB)
[v2]
Fri, 30 Oct 2026 18:26:29 UTC (258 KB)
来源：arXiv cs.CL · arxiv.org