{"id":"62f751e1-3317-4334-8594-7c8dc4553813","arxiv_id":"2411.13868","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Tr-GoF is a truncated goodness-of-fit test that provably achieves the optimal detection boundary for Gumbel-max watermarks under human edits, without knowing the edit level or model probabilities.","lead":"Statisticians propose a new test, Tr-GoF, that detects AI text watermarks even after humans edit the text. The method provably keeps detecting the signature while needing no knowledge of how much editing occurred.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Edited-token pivots are not µ0 when edits are content-dependent (e.g., synonym substitution), so Assumption 4.1(b) fails and the claimed q+2p=1 boundary may not hold for the real editing process the title addresses.","rationale":"The reader's weakest-assumption identification is in the right place: Assumption 4.1(b) is the bridge from the mathematical model to real human editing. I agree partially, and I sharpen the failure mode: it is not only clustering or residual signal in edited tokens, but the fact that content-dependent edit rules (like the paper's WordNet synonym substitution) make the edited token a function of the original watermarked token, which is itself a function of the pseudorandom vector ζt. Hence the edited pivot is not µ0 even when edits are applied independently per position. I verified this with a two-token swap example where the edited pivot has CDF 2r−r². This is a concrete, load-bearing weakness because Lemma A.2, the Hellinger bounds, the HC/Tr-GoF empirical-process argument, and the efficiency-rate proof all rely on the exact conditional-mixture identity. The paper's theorems are not internally inconsistent under the stated assumption; the concern is external validity. I do not see a need to reject: the mathematical framework is coherent, the code is available, and the experiments provide genuine support for the method's practical robustness. However, acceptance should be conditional on either justifying Assumption 4.1(b) for realistic edit models or demonstrating that the phase boundary and efficiency claims persist under content-dependent edits. The Remark 4.2 reversal and the sketched hars case in Corollary 4.1 are additional fixable issues, but they are secondary to the model-misspecification concern.","tokens_in":52359,"tokens_out":15233,"duration_ms":164280,"concrete_test":"Settle the misspecification with a minimal analytical check and a boundary simulation. First, set |W|=2 with P=(1/2,1/2), generate Gumbel-max pivots, and apply an edit rule that replaces the observed token by the other token without changing the m-window. Directly compute the distribution of Yt at edited positions: it equals 2r−r², not U(0,1), which falsifies Assumption 4.1(b) for content-dependent edits. Then, to test whether the central boundary survives, simulate the Tr-GoF test under this swap-edit model with εn=n^{−p}, Δn=n^{−q} at parameter pairs near the claimed boundary, e.g., (p,q)=(0.3,0.4), for n=10^3,10^4,10^5. If the sum of Type I and Type II errors does not vanish inside q+2p<1, the optimality claim is model-dependent and does not extend to the paper's own synonym-style edit protocol.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Assumption 4.1(b) states that an edited token is drawn independently of the pseudorandom vector ζt, making its pivot exactly µ0 and giving the clean conditional mean in Lemma A.2: E1[h(Yt)|Ft−1] = (1−εn)E0h + εnE1,Pt h. But the paper's own real-text edit protocol—WordNet synonym substitution—chooses the replacement as a function of the original watermarked token wt = S(Pt, ζt). When the preceding m-window is unedited, ζt is unchanged for the edited position, so the replacement token w' is a function of ζt, not independent of it. The pivot Yt = U_{t,w'} is therefore not uniform. A minimal analytical counterexample: for |W|=2 with P=(1/2,1/2) and an edit rule that swaps the observed token to the other one, P(Yt≤r | edited) = 2r−r², not r. More generally, conditioning on the event that a given token won the Gumbel-max race imposes upper bounds on the other coordinates, biasing the edited token's chosen coordinate downward. Consequently the mixture in (4) is misspecified: the 'noise' component of edited tokens is not µ0 but a distribution that can deviate at the relevant threshold r=Δn by order Δn². This deviation enters the Hellinger and empirical-process calculations in Theorems 4.1–4.3 and Theorem 4.5, so the optimality boundary q+2p=1 is established only for an edit process that is independent of the visible watermarked text. The Discussion itself acknowledges that human edits often cluster (Section 7), but the more fundamental issue is that even independent, per-position content-dependent substitutions break the pivotal-independence assumption. The mathematical theorems are internally consistent under Assumption 4.1; the load-bearing gap is the translation of that assumption to the paper's stated object, 'robust detection under human edits.'","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies detection of the Gumbel-max watermark when LLM-generated text may have been edited by humans. It models edits as a per-token Bernoulli mixture: with probability εn a token retains its watermark signal, and otherwise it behaves as pure noise with pivot statistic drawn from µ0. Under an asymptotic regime with watermark fraction εn ≍ n^{-p} and NTP singularity Δn ≍ n^{-q}, the paper proves that the optimal detection boundary is q+2p=1, that the proposed truncated goodness-of-fit test (Tr-GoF) attains this boundary adaptively without knowing p, q, εn, or the NTP distributions, and that sum-based detection rules are limited to the suboptimal boundary q+p=1/2. In the constant-edit regime, the paper further claims that Tr-GoF achieves the optimal P∆-efficiency rate. The theoretical results are supplemented by simulations and experiments on OPT-1.3B and Sheared-LLaMA-2.7B, including random, adversarial, and roundtrip-translation edits.","tokens_in":52672,"tokens_out":10782,"duration_ms":98446,"significance":"If the results hold as stated, this is a substantial contribution to the statistical theory of LLM watermark detection. The paper gives a concrete phase transition, a parameter-free test that provably reaches it, and a rigorous explanation of why additive scoring rules are fragile under edits. The proofs are theorem-driven rather than fit to simulations, the simulation boundaries in Figures 6 and 7 align with the theory, and the source code is publicly available. The main value is the demonstration that a goodness-of-fit statistic can be adaptively optimal in a sparse mixture setting with autoregressive, time-varying signal distributions. The scope of these guarantees, however, depends on the mixture assumption for human edits, and that assumption is the main point of concern.","major_comments":[{"comment":"The load-bearing assumption is that each edited token is independent of the pseudorandom vector ζt, so its pivot is exactly µ0. This is contradicted by the paper's own WordNet synonym-substitution protocol in Supplementary C.1. When the m-token context preceding position t is unedited, the verifier's recomputed ζt equals the original pseudorandom vector used to generate the token, and a replacement chosen as a synonym of the watermarked token is a function of that vector. For |W|=2 with P=(1/2,1/2), swapping the observed token to the other one yields P(Yt≤r | edited)=2r−r² rather than r. Consequently the mixture in Eq. (4) does not describe the actual edited-token distribution under content-dependent edits, and the clean conditional-mixture identity in Lemma A.2, on which Theorems 4.1–4.5 rely, is misspecified. The q+2p=1 boundary and the optimality of Tr-GoF are therefore proved for an edit process that is independent of the visible watermarked text, not for the editing process featured in the title and experiments. The authors should either prove that the stated results are insensitive to this dependence, add a misspecification analysis, or explicitly restrict the theoretical claims.","section":"Assumption 4.1(b) / Eq. (4) / Lemma A.2"},{"comment":"The relaxed-assumption statement in Remark 4.2 is inverted relative to the appendix. The main text says merging follows from q+2p>1 with P1:n⊂P∆n and separation from q+2p<1 with P1:n⊂Pc∆n, while the appendix's restated Theorem 4.2 and the proof in Section A.2 use the opposite inclusions: merging is proved for P1:n⊂Pc∆n and separation for P1:n⊂P∆n. Since P∆n is the class with Δ(Pt)≥Δn, the appendix version is the correct one for a signal that strengthens with Δn. Please correct Remark 4.2 so that the main text and appendix agree.","section":"Remark 4.2 / Appendix Theorem 4.2"}],"minor_comments":[{"comment":"In the paragraph on edit tolerance limits, 'reported in Figure 1' should read 'reported in Table 1'.","section":"Section 6.3"},{"comment":"The formula in footnote 4 is garbled; the displayed lower bound on q should be written cleanly as q ≥ log(|W|/(|W|-1)) / log n to be readable.","section":"Section 5.3 / footnote 4"},{"comment":"The optimal-efficiency result is stated for s∈(0,1) and c+_n=0, but the surrounding text and Figure 4 present it as a property of Tr-GoF generally; please state these restrictions wherever the result is summarized.","section":"Theorem 4.5"},{"comment":"The sentence beginning 'Among ∆ ∈ 0.1, 0.2, 0.3' is grammatically incomplete; please revise.","section":"Section 6.1"},{"comment":"The notation 'ew' in the pseudocode should be 'w'; the current typesetting appears to come from an unresolved LaTeX macro.","section":"Algorithm 2"}],"recommendation":"major_revision","confidential_remarks":"The core mathematical development under Assumption 4.1 appears sound, and the paper is a strong contribution if the model-scope gap can be addressed. The editor may wish to ask for a precise statement of which editing processes satisfy Assumption 4.1(b) and a discussion of whether the phase boundary is robust to content-dependent editing. The Remark 4.2 inversion is easy to fix but should not remain in a published version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you need to know: the paper proves something real and useful. Under a per-token edit-mixture model, Tr-GoF hits the information-theoretic boundary q+2p=1, and sum-based rules provably stop at q+p=1/2. The proof is built from explicit Hellinger computations and empirical-process bounds; the simulations match the predicted phase transition. This is the first work I know that pins down the sparse-regime detectability boundary for the Gumbel-max watermark under edits.\n\nWhat is new: the boundary itself, the proof that sum-based statistics are suboptimal, and the adaptive optimality of a truncated phi-divergence GoF test that works without knowing p, q, epsilon, or the NTP distributions. That is a solid contribution, not an incremental one. The appendices are serious—they generalize Hellinger tensorization for the autoregressive dependence and give explicit lemmas. The paper ships code, and the OPT/LLaMA experiments are reproducible in spirit.\n\nThe main soft spot is Assumption 4.1(b). It models an edit as a draw from P_t independent of the pseudorandom vector. Real edits are usually functions of the visible token, which is itself a function of that vector. Even a simple synonym substitution that picks among alternatives based on context creates dependence between the replacement and zeta_t; the stress-test example shows the pivot CDF under edit becomes 2r−r^2, not r. So the mixture's \"noise\" component is not mu_0, and the q+2p=1 boundary is proven for an editing process that ignores the watermarked text. That is a real gap between the mathematical model and the title's \"human edits.\" It does not invalidate the theorems, but it limits what they license about real-world robustness. The authors should state this limitation plainly rather than leaving it implicit.\n\nAlso, Remark 4.2 in the main text swaps the roles of P_Delta and its complement relative to the appendix proof. It is clearly a typo, but as printed it misstates the direction of the relaxation and will confuse readers. Minor point: the hars case in Corollary 4.1 is \"analyzed similarly\" and omitted; that is acceptable given Proposition A.1, but a referee should ask for the details.\n\nWho is this for: statisticians working on watermark detection and sparse mixture testing, and anyone who wants to understand why sum-based detectors fail under edits. The paper deserves a serious referee. The formal results are new, checkable, and the central claim holds up under its own assumptions. I would send it to review with a request to fix the remark and add an explicit discussion of content-dependent edits.","headline":"A real phase-transition result for robust watermark detection, with a clean adaptive test, once you accept the mixture model—but the edit model is narrower than the title suggests.","tokens_in":53341,"tokens_out":3867,"would_cite":true,"duration_ms":36186,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F03","62F05","62G10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a truncated goodness-of-fit test reaches the information-theoretic detection boundary for Gumbel-max watermarks under human edits, without knowing the edit level or the token distributions.","keywords":["watermark detection","large language models","human edits","mixture model","goodness-of-fit test","Higher Criticism","sparse mixture detection","adaptive optimality"],"falsifier":"Take a watermarked text, delete or replace a contiguous 5% block of tokens rather than editing tokens at random, and keep replacements semantically close; at parameter values near the boundary such as $p=0.3$, $q=0.4$, observe whether Tr-GoF's Type I plus Type II error still tends to zero as $n$ grows. Under the paper's Bernoulli-mixture model it must; if the block-edit alternative is the true one, the stated boundary need not hold.","tokens_in":52085,"feed_emoji":"🔍","tokens_out":6817,"duration_ms":93290,"temperature":0.7,"pith_summary":"This paper asks when a watermark embedded in LLM-generated text can still be detected after humans edit the text. It models editing as a Bernoulli mixture: each token either keeps its watermark signal with probability $\\epsilon_n$ or becomes pure noise. In the regime where both the surviving-signal fraction and the signal strength shrink polynomially ($\\epsilon_n \\asymp n^{-p}$ and $\\Delta_n \\asymp n^{-q}$), the paper proves a phase boundary $q+2p=1$: below it detection is asymptotically possible, above it impossible. Tr-GoF, a truncated goodness-of-fit test, attains this boundary adaptively, while sum-based score tests only reach $q+p=1/2$. So one parameter-free test matches the detectability limit that an impractical likelihood-ratio test would need full knowledge of the edit rate and the token distributions to achieve.","feed_headline":"Tr-GoF hits the optimal detection limit for edited LLM text","feed_subtitle":"A parameter-free goodness-of-fit test beats sum-based detectors, matching the q+2p=1 boundary without knowing the edit level.","key_machinery":"The central object is the truncated goodness-of-fit statistic $S^+_n(s) = \\sup_{r\\in[p^+,1)} K^+_s(F_n(r),r)$, where $F_n$ is the empirical CDF of the p-values $p_t=1-Y_t$, $Y_t$ is the pivotal statistic attached to token $t$, and $K_s$ is the $\\phi_s$-divergence between two Bernoulli distributions. The truncations exclude the smallest p-values and keep only the region where the empirical CDF exceeds the null CDF, removing the heavy-tail outliers that would otherwise dominate the statistic. At $s=2$ the statistic is exactly Higher Criticism, and the paper shows it grows like $n^{1/2-p-q/2}$ under the alternative while only reaching $\\log\\log n$ under the null, which is what pins the boundary $q+2p=1$.","core_discovery":"On its own terms, the discovery is that robust watermark detection reduces to a sparse-mixture detection problem on pivotal statistics, and that the optimal boundary is reached by comparing the empirical CDF of the p-values against the uniform null CDF instead of accumulating scores. Theorem 4.3 states that when $q+2p<1$, the Tr-GoF statistic with any truncation constant $c^+_n \\le 1/n$ and $s \\in [-1,2]$ drives both Type I and Type II error to zero without knowledge of $p$, $q$, $\\epsilon_n$, or the next-token distributions. Theorem 4.4 states that any sum-based rule built from a parameter-free non-decreasing score function has detection boundary only $q+p=1/2$. Theorem 4.5 states that in the constant-edit regime Tr-GoF attains the optimal $\\mathcal{P}_\\Delta$-efficiency $D_{\\mathrm{KL}}(\\mu_0, (1-\\epsilon)\\mu_0 + \\epsilon \\mu_{1,P^\\star_\\Delta})$, again without knowing $\\epsilon$ or $\\Delta$.","pith_inferences":["The truncation strategy should transfer to other watermark decoders whose pivotal statistics have a known null distribution, since the CDF comparison treats the decoder as a black box once pivots are defined.","If real edits are clustered rather than per-token independent, the true alternative is autocorrelated and the boundary $q+2p=1$ may no longer be the right description; estimating the watermark fraction or exploiting spatial edit structure could recover some of the loss.","Because the impossibility direction of Theorem 4.2 is an upper bound over all tests, the boundary $q+2p=1$ is plausibly information-theoretic for the Gumbel-max watermark, not just a property of p-value-based methods.","In deployment, the tuning-free form suggests setting $s=2$ (Higher Criticism) with a Monte-Carlo threshold as a drop-in robust detector; the main cost is computing the pseudorandom pivots, which the detector already needs."],"forward_implications":["Below the boundary $q+2p=1$, Tr-GoF separates watermarked from human-written text with both error probabilities tending to zero, and it does so without tuning to the problem.","Separating at the optimal boundary requires abandoning sum-based statistics: every parameter-free non-decreasing score rule is confined to $q+p=1/2$ in the sparse regime.","When the edit fraction and token-distribution regularity are constant, Tr-GoF reaches the optimal exponential decay rate of Type II error, matching the least-favorable benchmark without knowing $\\epsilon$ or $\\Delta$.","Empirically, on open-source LLMs, Tr-GoF keeps Type I error controlled and achieves lower Type II error than baselines at low temperature, with the largest edit-tolerance limits in substitution, insertion, and deletion experiments."],"supporting_citations":[{"why":"Supplies the pivotal-statistic framework, the definition of P-efficiency, and the least-favorable score benchmark that Tr-GoF is compared against.","marker":"[47]"},{"why":"Introduces the Gumbel-max watermark and the sum-based h_ars detector that Tr-GoF is designed to beat under edits.","marker":"[1]"},{"why":"Defines Higher Criticism, the sparse-mixture detection problem, and adaptive optimality whose boundary logic the paper carries over.","marker":"[18]"},{"why":"Provides the phi-divergence goodness-of-fit statistics and the null limiting distribution that the truncation in Tr-GoF is built from.","marker":"[37]"},{"why":"Supplies the robust watermarking setup, the h_log score, and the experimental protocol used for evaluation.","marker":"[45]"},{"why":"Represents the sum-based detection family with h_log and random-edit robustness that Theorem 4.4 proves suboptimal.","marker":"[22]"}],"fun_headline_variants":["Optimal watermark detection without knowing edit rates","Tr-GoF: robust watermark detection under heavy edits","Edit-proof watermark detection for LLMs","Tr-GoF test outruns sum-based detectors for LLM watermarks","Statistical edge: Tr-GoF beats sum rules on edited text"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that each edited token is pure noise and each unedited token keeps its watermark independently with the same probability $\\epsilon_n$; if human edits arrive in blocks or leave contextual traces in the pseudorandom statistics, the data are no longer the Bernoulli mixture the theorems assume.","fun_headline_variants_meta":{"raw":{"variants":["Optimal watermark detection without knowing edit rates","Tr-GoF: robust watermark detection under heavy edits","Edit-proof watermark detection for LLMs","Tr-GoF test outruns sum-based detectors for LLM watermarks","Statistical edge: Tr-GoF beats sum rules on edited text"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000214,"raw_usage":{"total_tokens":1477,"prompt_tokens":1049,"completion_tokens":428,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":665,"completion_tokens_details":{"reasoning_tokens":347}},"tokens_in":665,"tokens_out":428,"duration_ms":4219,"temperature":1.0,"reasoning_tokens":347,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:48:07.131504+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a watermarked text, delete or replace a contiguous 5% block of tokens rather than editing tokens at random, and keep replacements semantically close; at parameter values near the boundary such as $p=0.3$, $q=0.4$, observe whether Tr-GoF's Type I plus Type II error still tends to zero as $n$ grows. Under the paper's Bernoulli-mixture model it must; if the block-edit alternative is the true one, the stated boundary need not hold.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the pivotal-statistic framework, the definition of P-efficiency, and the least-favorable score benchmark that Tr-GoF is compared against."},{"cited_title":"Robust distortion- free watermarks for language models.Transactions on Machine Learning Research, 2024","cited_arxiv_id":null,"evidence_quote":"Supplies the robust watermarking setup, the h_log score, and the experimental protocol used for evaluation."}],"review_version":1}