{"id":"fea8e930-d7fe-400b-91b6-d2afcfdf0405","arxiv_id":"2509.21160","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"WISER is a linear-time, provably consistent algorithm that localizes multiple watermarked segments in mixed-source texts by treating pivot statistics as an epidemic change-point sequence.","lead":"This paper introduces WISER, an algorithm that finds which parts of a mixed human-AI text were watermarked by a language model. It models watermarked segments as epidemic change-points in a sequence of pivot statistics, runs in linear time, and comes with finite-sample error guarantees.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Lemma 2.2 requires i.i.d. ζ_t, which Assumption 2.1 does not state and hashing-based watermarks do not satisfy; the theory's coverage of the experimental setting is unproven.","rationale":"The reader's weakest assumption (Assumption 3.1: minimum segment length and separation) is a real limitation, but it is an explicit condition of the theorem, so the paper is internally consistent about it. A more load-bearing concern is that the proof of the i.i.d. null pivot property (Lemma 2.2) silently assumes ζ_t are i.i.d. and independent of the text history, a condition not stated in Assumption 2.1. Standard implementations of the watermarking schemes used in the experiments rely on hashing, where ζ_t is a deterministic function of the preceding tokens and a secret key; under such schemes the ζ_t sequence is not i.i.d. and the conditional pivot law may not equal L(Y). The paper itself concedes in Appendix A and §5 that the general hashing/human-edit setting is non-trivial and left for future work. Because the block threshold Q and the binomial counting in Proposition 5 require the null block sums to be i.i.d., the proof of Theorem 3.2 does not yet cover the practical, hashing-based schemes that motivate the paper's robustness claims. This does not mean the algorithm is wrong; the experiments suggest it works well, and the theory may be valid in the secret-key setting. The verdict should remain CONDITIONAL, with an added condition that the paper either strengthen Assumption 2.1 to include the i.i.d. structure of ζ_t and explicitly restrict the theoretical claims to that setting, or extend the proofs to hashing-based watermarks.","tokens_in":30789,"tokens_out":19358,"duration_ms":172695,"concrete_test":"Simulate unwatermarked (human-generated) token sequences under the exact hash-based Red-Green watermark used in §4 (e.g., context length m as in Kirchenbauer et al., 2024). Compute the empirical distribution of the maximum block sum over blocks of size b=⌈√n⌉ and compare it with the i.i.d.-based α-quantile used for Q in Theorem 3.2. If the empirical false-positive rate of the first-stage block selection differs from α by more than a small tolerance (e.g., 20% relative error), then the i.i.d. pivot assumption behind Lemma 2.2 is violated, and the theory does not cover the experimental setting.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central guarantee (Theorem 3.2) is built on Lemma 2.2, which asserts that null pivot statistics {Y_t}_{t∈S} are i.i.d. The proof (Appendix D.3) states 'the key ζ_t that are i.i.d.' and uses the pivot law L(Y) for the conditional law of Y_t given ω_{1:t}. Assumption 2.1 only says ω_t and ζ_t are independent given ω_{1:(t-1)}; it does not say the conditional law of ζ_t given history equals the pivot law, nor that ζ_t are independent across t. For hashing-based watermarking (the standard Red-Green scheme in §4 and the human-edit setup in Appendix A), ζ_t = A(ω_{(t-m):(t-1)}, Key) is a deterministic function of previous tokens, so the ζ_t are generally dependent and their conditional laws vary. Appendix A admits the general m setting 'requires specific attention,' and §5 lists human-edit robustness as future work. If Lemma 2.2 fails, the block-level null distribution used to choose Q in Theorem 3.2 is not i.i.d., and Steps 1–2 of the proof (including Proposition 5's binomial count of exceedances) no longer apply. Thus the claimed 'complete theoretical guarantees' are currently established only for a setting with genuinely i.i.d. secret ζ_t, not for the hashing-based schemes used in the experiments.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper frames watermark localization in LLM-generated text as an epidemic change-point problem. The authors introduce pivot statistics for unwatermarked tokens and model watermarked segments as intervals where the mean of h(Y_t) is elevated by at least d (Assumption 2.2). They propose WISER, which performs block-level thresholding with a quantile Q of the null maximum block sum, discards short selected runs, enlarges the remaining intervals, estimates the signal strength dtilde from the enlarged intervals, and then applies a localized version of the single-segment estimator of Eq. (3.1) inside restricted search windows. Theorem 3.1 gives an O_P(dtilde^{-1}) boundary error for a single segment, and Theorem 3.2 gives consistency for multiple segments under minimum length/separation and a cumulant condition (3.2). Experiments on Gumbel, Inverse Transform, Red-Green, and Permute-and-Flip watermarks with several LLMs report higher IOU/F1/MRI and lower runtime than Aligator, SeedBS-NOT, and Waterseeker.","tokens_in":31175,"tokens_out":12734,"duration_ms":108422,"significance":"If the theoretical claims were fully established for the schemes tested, this would be a useful contribution: WISER is simple, runs in O(n), accommodates multiple segments, and the paper provides detailed proofs, extensive benchmarks, and a sensible modified Rand index. The finite-sample probability bounds and the explicit discussion of tuning parameters are strengths. However, the central i.i.d. pivot-statistics lemma (Lemma 2.2) is proved only under a stronger assumption than Assumption 2.1, and the hash-based watermarking used in the experiments produces dependent key variables. Until that gap is closed or the claims are restricted, the 'complete theoretical guarantees' advertised in Section 1.1 are not established for the empirical setting. The significance is therefore conditional on a fixable but load-bearing re-scoping or a new dependence analysis.","major_comments":[{"comment":"The assertion that {Y_t}_{t in S} are i.i.d. is not a consequence of Assumption 2.1. Assumption 2.1 only states that for an unwatermarked token, omega_t and zeta_t are independent conditional on omega_{1:t-1}; it does not state that the zeta_t are i.i.d. or independent of the history. The proof in Appendix D.3 explicitly uses 'the key zeta_t that are i.i.d.' and the pivot law L(Y) as the conditional law given omega_{1:t}. For the hash-based watermarking used in Section 4 and Appendix A, zeta_t = A(omega_{(t-m):(t-1)}, Key) is a deterministic function of previous tokens, so the conditional laws vary and the zeta_t are dependent. Consequently the i.i.d. null block sums used to select Q, the binomial count in Proposition 5, and the martingale-difference property of epsilon_t in the proof of Theorem D.1 (around Eqs. (D.4)-(D.7)) are not justified for those schemes. The theory currently covers only the case of genuinely i.i.d. secret keys whose distribution does not depend on the text history; please either prove the needed statements under a suitable dependence condition (e.g., a conditional pivot-law bound) or explicitly restrict the theoretical claims and present the Section 4 results as empirical evidence outside the proven regime.","section":"Section 2.1, Lemma 2.2 and Appendix D.3"},{"comment":"Theorem 3.2 assumes that the null distribution of the pivot statistics is absolutely continuous with respect to Lebesgue measure. The paper does not verify this for the Red-Green and Inverse Transform watermarking setups used in the experiments, where the natural score functions are bounded and potentially lattice-valued (e.g., green-token counts). If the null law is discrete, the calibration condition P0(max_k S_k > Q)=alpha and the exceedance-count argument in Proposition 5 require a different treatment. Please either state which pivot statistics h(Y) are used for each scheme and verify the absolute continuity assumption, or extend the result to discrete laws (or to a suitable smoothing argument).","section":"Theorem 3.2 and Appendix C"},{"comment":"Condition (3.2) is the main quantitative control on the watermarked distribution used in Theorem 3.2, but it is not verified for any of the schemes in Appendix B; the Donsker-Varadhan remark is heuristic and does not establish the inequality for Gumbel or Inverse Transform watermarks. Since Section 1.1 claims 'complete theoretical guarantees in the most general case,' the paper should either verify (3.2) for the examples or state it as an unverified condition limiting the theorem's scope. Relatedly, Assumption 3.1 excludes adjacent or shorter-than-C0 n^{1/2+gamma'}/log n segments, so the 'most general case' phrasing overstates the coverage of Theorem 3.2.","section":"Condition (3.2) and Assumption 3.1"}],"minor_comments":[{"comment":"Assumption 3.1 uses d(I_k, I_{k-1}) for k=1, but the distance d is defined only for two disjoint intervals in Section 3.2; please define d(I_1, I_0) explicitly (e.g., as infinity or as the distance from the segment to the text boundary).","section":"Assumption 3.1"},{"comment":"After choosing rho=(8 nu)^{-1}, the argument yields d >= 2 rho dtilde only with possible equality; to match the strict inequality d > 2 rho dtilde used in the proof, choose a slightly smaller rho, for instance rho=(16 nu)^{-1}.","section":"Step 3 of the proof of Theorem D.2"},{"comment":"The title contains the apparent fragment 'REGION-A'; also Appendix C.1.3 spells 'meta-Ilama' instead of 'Meta-Llama'.","section":"Title and Appendix C.1.3"},{"comment":"Equation (3.2) writes E_{1,p}[exp(-theta X)] with a lowercase p; please use P to match the class notation used elsewhere.","section":"Equation (3.2)"},{"comment":"The apparent circularity of estimating dtilde from screened intervals is addressed in Step 3 of the proof of Theorem D.2, where dtilde is shown to concentrate in [tau d, 4 nu d]; the main unresolved issue is not circularity but the i.i.d. assumption underlying the screening stage. The introduction's 'complete theoretical guarantees' phrasing should be tempered to acknowledge the limitations stated in Appendix A and Section 5.","section":"Sections 1 and 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is potentially publishable after the i.i.d. assumption gap is addressed. I would not require new experiments, but the theoretical claims must be scoped to the provable regime and the assumptions verified for the experimental watermarks. Please also check whether the authors' claim of being the first with complete guarantees overlooks recent work on hash-based dependence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the epidemic change-point framing is a good bridge and the multi-segment consistency theorem is new, but there is a real gap between the theory and the experiments. Lemma 2.2 claims the null pivot statistics are i.i.d.; Assumption 2.1 does not deliver that for hashing-based watermarks like Red-Green, which is exactly what the experiments use. That is the main thing to know.\n\nWhat is genuinely new: WISER is a block-screen-then-refine algorithm, and Theorem 3.2 gives finite-sample error bounds and consistency for multiple watermarked segments in O(n) time. That is a real advance over Aligator, SeedBS-NOT, and Waterseeker, which either lack guarantees or are slower. The numerical work is thorough—four watermarking schemes, six model sizes, several metrics—and WISER wins clearly. The modified Rand Index is a legitimate fix for the asymmetry problem.\n\nThe soft spots are in proportion. The i.i.d. issue is not minor. In the proof of Lemma 2.2 (Appendix D.3) they say the ζ_t are i.i.d., but Assumption 2.1 only states conditional independence of ω_t and ζ_t given the past. For hashing schemes—including the Red-Green setup in Section 4 and the human-edit discussion in Appendix A—ζ_t is a deterministic function of the previous m tokens, so the ζ_t are dependent and the null pivot statistics are generally not i.i.d. The paper itself admits in Appendix A that the general m setting \"requires specific attention.\" That means the quantile Q and Proposition 5's binomial count, which are load-bearing in Theorem 3.2, are not justified for the experiments. The claim of \"complete theoretical guarantees\" is too strong as written. The absolute-continuity assumption is another technical condition, but that is a lesser issue. The data-driven dtilde step is actually handled: they prove concentration in [τd, 4νd], so the self-reference is not fatal.\n\nWho this is for: researchers in watermarking and change-point analysis. It deserves serious peer review. The right path is to have the authors either extend the theory to dependent ζ_t (hard) or explicitly restrict the consistency theorem to schemes with fresh independent secrets per token—like the Gumbel setup—and present the hashed case as an empirical finding plus future work. With that scope fix, the paper is solid.","headline":"Strong algorithm and a new multi-segment consistency bound, but the i.i.d. pivot assumption doesn't cover the hashing schemes used in the experiments; fix the scope and this is publishable.","tokens_in":31645,"tokens_out":3634,"would_cite":true,"duration_ms":32866,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62G10","62G20","62M10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Treating watermarked spans as epidemic change-points, WISER provably localizes them all in linear time.","keywords":["watermark segmentation","epidemic change-points","large language models","pivot statistics","multiple change-point detection","linear-time algorithm","mixed-source text","consistency guarantees"],"falsifier":"Run WISER on synthetic mixed texts with $n$ growing, two watermarked segments of length $\\lfloor C_0 n^{1/2+\\gamma'}/\\log n \\rfloor$ separated by the same order, block length $b = \\lceil\\sqrt{n}\\rceil$, watermark strength $d$ fixed, and $Q$ the $0.95$-quantile of the null maximum block sum. If the empirical frequency of $\\{\\hat K=K$ and boundary error below $M_\\epsilon/d\\}$ does not approach at least $0.95$ as $n$ grows, then one of Assumption 3.1, the cumulant condition (3.2), or the elevated-alternatives assumption fails and the theorem's prediction is contradicted.","tokens_in":30608,"feed_emoji":"🧩","tokens_out":12489,"duration_ms":96572,"temperature":0.7,"pith_summary":"This paper claims that locating watermarked segments in mixed human-machine text is the same statistical problem as detecting an epidemic change-point: inside a watermarked stretch the pivot statistics of tokens shift upward, and outside it they return to baseline. On that footing it proposes WISER, a block-screening, discarding, enlargement, and local re-estimation pipeline that runs in $O(n)$ time and, under minimum-length and separation conditions, simultaneously finds the number of watermarked segments and estimates their boundaries. The main theorem says that with block length proportional to $\\sqrt{n}$ and a threshold set to the $\\alpha$-quantile of the null maximum block sum, the probability that WISER returns the true segment count and boundaries within error $M_\\epsilon/d$ approaches at least $1-\\epsilon$ as text length grows. Because existing segmentation methods are slow and lack guarantees, a provable linear-time localizer would make watermark localization practical for long documents and across watermarking schemes.","feed_headline":"WISER provably finds all watermarked segments in one pass","feed_subtitle":"Machine-generated patches are treated as temporary mean shifts; boundary error shrinks as watermark strength grows.","key_machinery":"The machinery is the epidemic change-point estimator for irregular signals, applied to pivot statistics $X_t = h(Y_t)$, where a pivot statistic is a score function of the token and the watermark key whose law is the same for every token when no watermark is present. Watermarked tokens are assumed to raise the mean of $X_t$ by at least $d$ over the unwatermarked level $\\mu_0$, while the mean inside the segment may vary. The paper adapts an existing change-point estimator for non-constant means to the epidemic setting as the interval minimizing the sum of $(X_k - \\mu_0 - \\rho\\tilde d)$ outside the interval, and proves its boundary error is controlled by the signal strength. WISER wraps this estimator in a blocking stage: partition into about $\\sqrt{n}$ blocks, keep blocks whose sums exceed the $\\alpha$-quantile of the null maximum, discard connected components shorter than $c\\sqrt{n}\\log n$, enlarge survivors, and restrict each local estimator to a search window of width about $\\sqrt{n}$. The block-level scan bypasses arbitrary dependence among watermarked pivot statistics, which is why the consistency proof uses cumulant-generating-function bounds and an envelope argument rather than standard change-point inequalities.","core_discovery":"The central claim is that watermark segmentation can be solved by an epidemic change-point estimator adapted to irregular signals, giving the first $O(n)$ algorithm with consistency guarantees for multiple watermarked intervals. For a single segment, the estimator that minimizes the biased out-of-interval sum has boundary error $O(1/\\tilde d)$, where $\\tilde d$ is a chosen signal-strength parameter, and $O(1/\\tilde d^2)$ under local sub-Gaussianity. For multiple segments, WISER partitions the text into about $\\sqrt{n}$ blocks and keeps only those whose pivot-sum exceeds the $\\alpha$-quantile of the null maximum block sum; it then discards short spurious clusters, enlarges the survivors, estimates the signal strength, restricts each search to a local window, and re-runs the single-segment estimator. Theorem 3.2 says that under an elevated-alternatives assumption, a cumulant-gap condition, and a minimum-length and separation assumption, the estimated number of segments equals the true $K$ and each estimated boundary differs from the truth by at most $M_\\epsilon/d$ with probability at least $1-\\epsilon$ in the limit. Thus stronger watermarks yield sharper boundaries, and the number of segments need not be known in advance.","pith_inferences":["If the epidemic reading is right, any signal whose mean is elevated only on intervals, not just watermarks, could be segmented by the same blocking-plus-local-refinement pipeline; machine-generated spans detected by perplexity or log-rank scores without a secret key are a natural candidate.","Because the theorem controls boundary error, the total length of the union of estimated segments should consistently estimate the watermark proportion, connecting WISER to proportion-estimation problems in mixed AI-human text.","The paper's asymmetry critique implies that comparisons relying only on the Rand Index may overstate methods that return overly large watermarked regions; future evaluations should report a modified index such as MRI.","A stress test on segments shorter than the $C_0 n^{1/2+\\gamma'}/\\log n$ threshold is not covered by the guarantee; a multi-scale block choice might extend the pipeline, but that is an open possibility rather than a claim of the paper."],"forward_implications":["A long mixed-source document can be scanned for all machine-generated stretches in one pass, since WISER runs in $O(n)$ time.","The user does not need to specify the number of watermarked segments; the estimated count matches the true count with probability approaching 1 under the theorem's conditions.","Boundary error shrinks as watermark strength $d$ grows, so stronger watermarks give both easier detection and more precise localization.","The same pivot statistics that power detection tests are enough for localization, so WISER applies across Gumbel, inverse-transform, red-green, and permute-and-flip watermarking schemes.","The single-segment rate $O(1/\\tilde d)$, sharpened to $O(1/\\tilde d^2)$ under local sub-Gaussianity, quantifies how choosing a larger signal-strength parameter $\\tilde d$ trades off against boundary accuracy."],"supporting_citations":[{"why":"Supplies the irregular-signal change-point estimator whose epidemic adaptation is the local workhorse of WISER.","marker":"Kley et al. (2024)"},{"why":"Establishes the pivot-statistic framework and the elevated-alternatives separation that turns watermarked tokens into mean shifts.","marker":"Li et al. (2025a)"},{"why":"Prior segmentation method SeedBS-NOT; provides the baseline and the only previous theoretical result WISER generalizes.","marker":"Li et al. (2024b)"},{"why":"Waterseeker baseline; two-stage detector whose sliding-window false positives WISER's blocking stage is designed to avoid.","marker":"Pan et al. (2025)"},{"why":"Red-green watermarking scheme and WinMax baseline; supplies one of the empirical watermark models and comparison methods.","marker":"Kirchenbauer et al. (2024)"},{"why":"Aligator baseline; reinforcement-learning segmentation method whose fragmented detections WISER compares against.","marker":"Zhao et al. (2024b)"},{"why":"Inverse-transform watermarking scheme used in the benchmark experiments, with the separation constant $d = \\Delta/3$ in the appendix.","marker":"Kuditipudi et al. (2024)"},{"why":"Permute-and-flip watermarking scheme used as another benchmark in the numerical comparisons.","marker":"Zhao et al. (2025)"}],"fun_headline_variants":["WISER pinpoints watermarked segments in one pass","Epidemic change-points localize watermarks in linear time","WISER locates watermarked segments with error guarantees","WISER: fast and provable watermark segmentation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee depends on each true watermarked segment being at least about $n^{1/2+\\gamma'}/\\log n$ tokens long and separated from neighbouring segments by at least the same length; shorter or adjacent watermarked spans fall outside the theorem, and the paper offers no fallback guarantee for them.","fun_headline_variants_meta":{"raw":{"variants":["WISER pinpoints watermarked segments in one pass","Epidemic change-points localize watermarks in linear time","WISER locates watermarked segments with error guarantees","WISER: fast and provable watermark segmentation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000781,"raw_usage":{"total_tokens":3488,"prompt_tokens":1018,"completion_tokens":2470,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":634,"completion_tokens_details":{"reasoning_tokens":2402}},"tokens_in":634,"tokens_out":2470,"duration_ms":15794,"temperature":1.0,"reasoning_tokens":2402,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:47:11.434015+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run WISER on synthetic mixed texts with $n$ growing, two watermarked segments of length $\\lfloor C_0 n^{1/2+\\gamma'}/\\log n \\rfloor$ separated by the same order, block length $b = \\lceil\\sqrt{n}\\rceil$, watermark strength $d$ fixed, and $Q$ the $0.95$-quantile of the null maximum block sum. If the empirical frequency of $\\{\\hat K=K$ and boundary error below $M_\\epsilon/d\\}$ does not approach at least $0.95$ as $n$ grows, then one of Assumption 3.1, the cumulant condition (3.2), or the elevated-alternatives assumption fails and the theorem's prediction is contradicted.","supporting_citations":[{"cited_title":"Change-point analysis with irregular signals","cited_arxiv_id":null,"evidence_quote":"Supplies the irregular-signal change-point estimator whose epidemic adaptation is the local workhorse of WISER."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Waterseeker baseline; two-stage detector whose sliding-window false positives WISER's blocking stage is designed to avoid."},{"cited_title":"On the reliability of watermarks for large language models","cited_arxiv_id":null,"evidence_quote":"Red-green watermarking scheme and WinMax baseline; supplies one of the empirical watermark models and comparison methods."},{"cited_title":"Robust distortion-free watermarks for language models","cited_arxiv_id":null,"evidence_quote":"Inverse-transform watermarking scheme used in the benchmark experiments, with the separation constant $d = \\Delta/3$ in the appendix."},{"cited_title":"Permute-and-flip: An optimally stable and watermarkable decoder for LLM s","cited_arxiv_id":null,"evidence_quote":"Permute-and-flip watermarking scheme used as another benchmark in the numerical comparisons."}],"review_version":1}