arXiv cs.CL· Nicklas Nidh\"ogg·· 12 小时前AI 评分24
有限可验证分词：为每个 Tokenizer 提供有限状态验证器的可判定性
Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier
AI 导读
论文提出“有限可验证分词”概念：若一个作用于标记串（字节+边界位）的有限自动机能恰好接受某分词策略自身的所有分词结果，则该策略有限可验证。在此假设下，窗口能否认证 token 边界、边界间隙是否有界、掩码是否保持生成可完成、两个策略是否等价这四个问题均变为可判定。该策略类严格介于在线可扫描策略与正则域策略之间，且对流水线常用的组合、限制、拆分和字节回退并集封闭，munch 库实现了全部六项判定。
正文 · AI 翻译
摘要：一种分词策略为每个字节串至多指定一种分词方式。当标记字符串（字节与边界位配对）上的有限自动机恰好接受该策略自身的分词结果时，称该策略是有限可验证的。该自动机评判一个提议的分词，而无需计算出一个分词。本文展示了这一假设能带来什么。四个在实践中靠经验法则解决的问题变得可判定：一个窗口是否证明了一个词元边界、边界间隙是否有界、一个掩码是否使生成保持可完成，以及两个策略是否等价。后三个问题分别特化了有限性、共可达性和单值转换器的等价性。第一个问题细化了编码理论中的同步切分，另外两个问题则询问一个经认证的切分，或一个词表的所有切分，是否能让每一片段单独扫描。该类严格位于在线可扫描策略与具有正则定义域的策略之间，其内部前沿是 Choffrut 的，并且可在多项式时间内判定。标记是保长的，因此该类恰好是有理分词策略，是一种范式而非限制，而判定所需的是一个提供的验证器。该类在流水线所用的运算下封闭：带标签阶段的复合、限制、拆分，以及字面策略的字节回退并集。每个复合体都继承这六个判定，并且证书在四个定律下在阶段之间转移。在有理、单射、几乎必然停机的有限状态源下，加权切片的每个质量都是精确有理数，期望长度为正时的每个速率也是如此。最大匹配词法分析、规范字节对编码和双模式 WordPiece 实例化了该接口，而 munch 库实现了全部六个判定。每个定理都带有可执行检查，每个报告的统计量都是程序自身的输出。
| 评论： | 36 页，1 幅图，2 张表。工件：此 https URL。该库和分词器实例的模块、门控和记录都在工件中，并附带一个验证器，它运行每个模块，并将每个报告的计数与其所依据的输出行对应起来。与 arXiv:2608.03473、arXiv:2608.09761、arXiv:2609.10600 和 arXiv:2610.08854 配套。 |
| 主题： | 形式语言与自动机理论（cs.FL）；计算与语言（cs.CL）；编程语言（cs.PL） |
| 引用为： | arXiv:2610.30168 [cs.FL] |
| （或 arXiv:2610.30168v1 [cs.FL] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.30168 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Nicklas Nidhögg [查看电子邮件]
[v1]
2026 年 10 月 16 日星期五 18:17:30 UTC（69 KB）
来源：arXiv cs.CL · arxiv.org