BPE 子词分词的理论分析

论文证明 BPE 优化问题 APX-complete，并给出最坏情况近似保证。

资讯摘要

论文对 Byte-Pair Encoding（BPE）子词分词所依赖的优化问题给出理论分析，证明寻找最优压缩效用的 pair encoding 是 APX-complete，因而不太可能存在多项式时间近似方案，这以更强形式回答了 Zouhar 等人近期提出的问题。作者同时给出正面结果：BPE 的压缩效用在最坏情况下可达到最优 pair encoding 的 1/3 至 (1-e⁻²)/2≈0.4324 倍，并称这是首个对所有输入都成立的严格保证。

要点速读

1. 论文证明 BPE 底层的最优 pair encoding 问题是 APX-complete，不太可能存在多项式时间近似方案。
2. 作者报告 BPE 在最坏情况下对最优压缩效用的近似比介于 1/3 与 (1-e⁻²)/2≈0.4324 之间。
3. 作者称这是首个对所有输入都成立的 BPE 压缩效用严格保证。

中文摘要由 AI 根据公开来源生成，可能存在理解偏差；具体能力、数字、开放时间等信息请以原文为准。
采集于 2026/11/4 08:00:28（北京时间）。 arXiv 日期为本次公告时间，论文初次投稿日期请查看原文版本记录。