arXiv:2610.08854 · v2
Certified Splitting: Decidability and Anchor Supply for Maximal-Munch Tokenization
摘要
A certificate is a window of bytes with an origin inside it such that, wherever the window occurs in a completely tokenizable input, the token covering the window's final byte begins at that origin. Certification is decided from the token set alone, and a certificate's occurrences mark where work may soundly begin. This paper decides certification and applies it to cuts, edits and audits. It is decided two ways, online with a completeness cutoff for literal vocabularies and offline through an armed-run verifier for arbitrary regular token sets. Either route, under a declared window budget, yields the anchor inventory, with a counterexample on each refutation. Cutting a completely tokenizable input at certified anchors and scanning the chunks independently reproduces the sequential segmentation, with no speculation or fixup pass. A tokenizability-preserving byte substitution moves boundaries only strictly between the certified anchors witnessed in the unchanged bytes on either side of it. For tokens of length at most L, an edit at p moves no boundary at or below p - L + 1. Cutting at every occurrence of a delimiter is sound exactly when it occurs only at token starts, and cutting after every occurrence exactly when it occurs only at token ends. Two instruments follow. The anchor-free span of a finite certified inventory is decided bounded or not with its exact supremum, three for the UTF-8 shape; and a differential auditor decides whether two token sets place different boundaries on an input both tokenize, with a differing input. Every theorem carries an executable check. Every measurement is a named program's output or arithmetic on such outputs, and each program ships with the paper or is pinned by commit in the munch library. That library's threaded scanner splits the archived campaign corpus at certified anchors and reproduces the sequential boundary stream byte for byte.
作者备注：34 pages, 7 tables. v2: credits window decidability to Karttunen, scopes the splitting, delimiter and newline claims to the theorems, proves bounded token length necessary but not sufficient for a bounded anchor-free span, aligns its terms with the series, cites Lassez 1976. Artifact: https://doi.org/10.5281/zenodo.23708363 . Companion to arXiv:2608.03473, arXiv:2608.09761 and arXiv:2609.10600