BPE虽无完美算法，但压缩效果至少是最佳方案的三分之一。
Theoretical Analysis of Byte-Pair Encoding
- 从压缩优化角度分析BPE，揭示其理论局限性
- 证明BPE压缩效率最低为最优解的1/3，最高达5/8
- 为BPE在语言模型中的成功提供首个普适性理论解释
字节对编码（BPE）是一种广泛用于子词分词的方法，起源于基于语法的文本压缩。它被应用于机器翻译或大语言模型预训练等任务中，以生成指定大小的词典。目前对BPE的评估多为经验性的，其良好性能背后的原理尚不清晰。本文聚焦于BPE背后的优化问题：寻找能实现最优压缩效用的配对编码。我们证明该问题是APX-完全的，表明其不太可能具有多项式时间近似方案。这以更强的形式回答了Zouhar等人提出的问题。另一方面，我们证明BPE对最优配对编码的压缩效用近似因子在0.333到0.625之间。这些结果旨在解释BPE持续成功的缘由，且据我们所知，是首个对所有输入都成立的关于BPE压缩效用的严格保证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。