arXiv cs.CL· Nicklas Nidh\"ogg·· 10 小时前AI 评分31
字节对编码的左侧涟漪：为每个词典给出可认证的回看范围
The Left Ripple of Byte-Pair Encoding: Certified Lookbehind for Every Dictionary
AI 导读
该论文为任意词典判定字节对编码（BPE）的“起源半径”，即左侧前置字符串能改变覆盖跨度的最大距离，并用半径证书在词典规模的多项式时间内完成计算。半径无限当且仅当存在一个周期词具有两种无公共边界的规范铺砌；在 Berglund 等人的排序条件下，这等价于某条规则 (t, t) 在自身阶段出现两个相邻副本。
正文 · AI 翻译
摘要：Berglund 和 van der Merwe 形式化了字节对编码，并界定了在末尾追加字符串能在多大程度上改变分词结果，但留下了相反的问题未解决：在左侧前置字符串能在多大程度上改变分词结果，哪些字典会使这种涟漪效应无限，以及当其为有限时能否高效计算？我们针对每个字典回答了全部三个问题。原点半径，即前置操作能改变覆盖区间的程度，通过半径证书来判定，该证书由两个自动机运行序列的乘积给出，该自动机猜测最终 token，判定时间为关于字典写出长度的多项式时间；当且仅当一个周期词具有两个无公共边界的规范铺砌时，原点半径为无限。在它们的排序条件下，当且仅当某条规则 (t, t) 在其自身阶段发现其两个副本相邻时，原点半径为无限，且这样的规则会使任何字典变为无限。有限半径使得从半径读出的每个宽度窗口都有一个切割，且当且仅当这样的切割稠密时半径有限。token 机对每个字典都完备，且分词是次序列的，这扩展了 Berglund、Martens 和 van der Merwe 在每条规则一遍的条件下对真字典所证明的结果。流式分词器在每个符号之后恰好输出那些不会被任何后续内容改变的 token，时间为多项式时间，回答了 Dalirrooyfard 和 Ye 的一个问题。标签测度（token 序列的编辑距离）的有界性同样对每个字典在多项式时间内判定，且在排序条件下，在 m 条规则的字典上，一次编辑所引起的最大距离渐近地介于 m^2/10 和 m^2/2 之间。GPT-2 的合并表包含 244 个有效自配对，因此其原点半径从第四十二次合并起为无限，而 cl100k、o200k 和 Llama 3 的原点半径从它们的第一次合并起即为无限。每个测量数字都是其程序的输出，未执行的内容均被指明。
| 评论： | 87 页，13 张表。工件：此 https URL。程序及其输出位于工件中，并附有一个验证器，可重新运行每个程序，并将每个报告的数字与其所依据的输出行进行核对。与 arXiv:2608.03473、arXiv:2608.09761、arXiv:2609.10600、arXiv:2610.08854 和 arXiv:2610.30168 配套。 |
| 主题： | 形式语言与自动机理论 (cs.FL)；计算与语言 (cs.CL)；数据结构与算法 (cs.DS)；编程语言 (cs.PL) |
| 引用为： | arXiv:2611.13061 [cs.FL] |
| （或 arXiv:2611.13061v1 [cs.FL] 为此版本） | |
| https://doi.org/10.48550/arXiv.2611.13061 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Nicklas Nidhögg [查看电子邮件]
[v1]
2026 年 11 月 9 日星期一 17:48:27 UTC（152 KB）
来源：arXiv cs.CL · arxiv.org