{"id":"89811583-80a3-4b82-9712-1abedaf0e308","arxiv_id":"2505.06827","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Random-walk attacks against text watermarks fail to remove the mark in most cases once human-rated text quality is preserved, calling the practical force of the WITS impossibility result into question.","lead":"This paper tests, with real attacks, the theoretical claim that any AI-text watermark can be erased by random rewrites. It finds the rewrites rarely remove the watermark without hurting text quality: attacks succeed about a quarter of the time, and only a tenth under human review.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The slow-mixing conclusion rests on a lineage distinguisher that is never calibrated against a known-mixed baseline; without that control, 100% traceability does not establish failure to mix.","rationale":"The reader's weakest assumption identifies the same load-bearing gap: the RQ1 anti-mixing conclusion depends on an uncalibrated lineage distinguisher and never measures mixing time or spectral gap. I agree with that assessment. The concern is concrete: the 100% traceability result is consistent with slow mixing, but it is also consistent with a biased or miscalibrated classifier and with disconnected high-quality islands (which the paper itself discusses in Section 5). The paper's other contributions—the oracle benchmark (RQ2) and the direct attack-success measurements (RQ3)—are substantive and independently plausible, so the paper should not be rejected. However, the headline claim that 'mixing is slow' and the direct empirical refutation of KA1 are not yet supported. A calibration control would settle the interpretation. The internal SIR/KGW label inconsistency in Tables 3 and 5 is a separate correctness issue that should be fixed, but it does not change the overall average ASR and is not the most load-bearing concern. The human-review sample is small, but the raw 26.1% ASR already undercuts the strongest theoretical attack prediction even before quality adjustment. Therefore the appropriate verdict remains CONDITIONAL, unchanged from the reader's report.","tokens_in":27536,"tokens_out":14502,"duration_ms":158901,"concrete_test":"Run the exact SimpleDistinguisher pipeline (best-of-2 with swapped A/B order and escalation to GPT-4o/o3) on a control set where C is an independent same-prompt generation from M, with no causal lineage to either A or B, using the same prompt pairs as RQ1. A calibrated two-hypothesis test should classify C at chance or abstain; if the pipeline attributes C to A or B at rates significantly above 50%, the 100% traceability of attacked texts cannot be interpreted as evidence of slow mixing. As a secondary check, on a small finite text space where the transition matrix can be enumerated, compute tmin(ε) exactly, sample from the stationary distribution, and measure the distinguisher's accuracy on those samples; if accuracy exceeds 1/2 + ε, the estimator is miscalibrated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The RQ1 claim that random walks do not mix (contradicting KA1) is inferred solely from a forced-choice lineage distinguisher: after up to 500-1000 perturbations, Llama/GPT/o3 can always pick which of two starting texts a perturbed text came from. Formally, if after t steps the distributions from starts A and B were both within small total-variation distance of the stationary distribution π, then any classifier on balanced A/B trials would have accuracy at most 1/2 + ε_TV. So 100% accuracy would indeed imply the chain is far from stationarity, but only if the classifier is an accurate, unbiased estimator of this distance. The paper never calibrates the distinguisher: there is no control with independent same-prompt texts that have no causal lineage to either A or B, no control with samples known to come from π, and no estimate of mixing time or spectral gap. The forced-choice setup can produce high 'accuracy' even on unlabeled inputs if the LLM uses content similarity or positional/style priors; the test unit also aggregates ~10 autocorrelated samples along a single walk, and a single wrong sample fails the test, making 100% across 4,555 tests extremely sensitive to any source-imbalance or leakage in prompt construction. The paper's own Section 5 discussion of disconnected high-quality 'islands' offers an alternative explanation for persistent traceability that is not about slow mixing within an irreducible component. Thus the central pillar 'mixing is slow' is not established; at best the results give a lower bound on the number of steps needed for these specific P oracles, which does not refute rapid mixing for a WITS-style adversary with a larger budget or a better-calibrated oracle. This is fixable but load-bearing: without RQ1, the headline 'slow mixing' and the direct contradiction of KA1 lose their main evidence, leaving RQ2/RQ3 as evidence of oracle imperfection and current attack weakness rather than a fundamental practical barrier.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper empirically tests two assumptions behind the random-walk watermark-removal attack of Zhang et al. (WITS): KA1, that the perturbation chain mixes rapidly, and KA2, that an automated quality oracle reliably guides edits. Using three watermarking schemes (KGW, SIR, Adaptive), seven perturbation oracles, a forced-choice lineage distinguisher, and human quality annotations, the paper reports three main findings: (i) 100% of 4,555 lineage tests remain traceable after hundreds of perturbations, interpreted as slow mixing; (ii) the best quality oracle attains an overall F1 of only 77.4%; and (iii) average final attack success is 26.1%, dropping to 10.5% after human quality review. The paper concludes that practical barriers make watermarking far more robust than the WITS impossibility result suggests.","tokens_in":27877,"tokens_out":8934,"duration_ms":89374,"significance":"If the empirical conclusions hold, the paper is a useful practical counterpoint to WITS-style mixing-time theory, and it contributes the Sandcastles human-annotated perturbation dataset plus a systematic oracle benchmark. The RQ3 measurements are concrete and falsifiable, and the human-review correction of ASR is a valuable step beyond prior evaluations. However, the RQ1 inference from the lineage distinguisher to formal mixing time is uncalibrated, and Table 3 appears to swap the SIR and KGW labels; as a result, the per-scheme quantitative claims need correction before the paper's central narrative can be fully accepted.","major_comments":[{"comment":"The lineage distinguisher is used as a proxy for the formal ε_dist-mixing time of Definition 2.1, but it is never calibrated against a known-mixed baseline, against independent unlinked texts, or against samples drawn from a stationary distribution. Perfect forced-choice traceability of a perturbed text to one of two starting texts does not by itself imply that total-variation distance to stationarity is large: a classifier can achieve high accuracy from content or style priors, from leakage in prompt construction, or from persistent topic cues, as the NASA/Artemis example in Appendix C.1 illustrates. Moreover, the paper's own Section 5 'islands' argument predicts persistent traceability when irreducibility fails, which is a different failure from slow mixing within an irreducible chain. Without an estimate of the spectral gap or mixing time, or at least a control with texts that have no causal lineage to either starting point, the conclusion that 'mixing is slow and KA1 is contradicted' is not established.","section":"§4.1, Definition 2.1"},{"comment":"The SIR and KGW rows appear to be swapped between Table 3 and Table 5. Table 5 reports the SIR watermarked mean as 0.28 and the KGW mean as 5.32, while Table 3 assigns µw0=5.32 and breakpoint 1.27 to rows labeled SIR and µw0=0.28 and breakpoint 0.21 to rows labeled KGW. Because SIR and KGW have different detection-score scales and the paper draws per-scheme conclusions (for example, 'SIR Sentence Q-ASRfin=48.56' and 'Adaptive remains resistant'), this label swap affects load-bearing per-watermark claims and must be corrected, with all dependent statements re-checked.","section":"Table 3 vs. Table 5 / Appendix B.3"},{"comment":"The attack filters candidate mutations with InternLMOracle using a relative acceptance rule — a score within a 0.46 deviation of the original text — not the absolute quality threshold q on Q(x,y) that defines the WITS graph G≥q_x. Consequently, the executed random walk is not necessarily the same walk whose stationary distribution the WITS theorem analyzes, and the low ASR and Q-ASR figures may reflect this mismatch plus oracle errors rather than a failure of the theoretical attack. The paper should either instantiate a WITS-style absolute-threshold acceptance rule or explicitly argue that the relative rule is the intended practical version of KA2, and it should state how the 0.46 threshold was chosen.","section":"§4.2–§4.3, Definition A.5"},{"comment":"Section 5 argues that reducibility may fail because of high-quality 'islands,' which would prevent convergence to a unique stationary distribution altogether. The RQ1 traceability result is therefore ambiguous between two different explanations — slow mixing in an irreducible chain versus non-irreducibility — and cannot by itself 'contradict KA1' without separating these cases. A concrete test would be to start multiple walks from texts within the same apparent component and measure whether traceability to arbitrary starts decays, or to estimate a lower bound on the spectral gap for a manageable subgraph; the paper currently provides neither.","section":"§5 / §4.1"}],"minor_comments":[{"comment":"Each reported test aggregates roughly ten autocorrelated samples from one walk and fails if any single sample is misclassified; please report per-sample accuracy and test-level confidence intervals in addition to the 100% over 4,555 tests.","section":"§4.1, Table 1"},{"comment":"The Q-ASRfin estimates are based on very small human-review counts, sometimes 0, 1, or 2 reviewed texts per row; please report confidence intervals or exact binomial intervals so the reader can see the uncertainty around figures such as 'no fairly evaluated attack succeeding more than half the time.'","section":"Table 3 and Table 13"},{"comment":"The text describes the top oracle's performance as '77% accuracy,' but Table 2 reports Overall F1; please use F1 consistently to avoid conflating precision, recall, and accuracy.","section":"§4.2, Table 2"},{"comment":"There are typos in the table headers: 'Watermarkered' should be 'Watermarked' and 'autoamated' should be 'automated.'","section":"Table 5, Table 13"},{"comment":"The statement that 'the best floating-point oracle' is InternLMOracle is not fully justified in the main text; the selection from the 150-step human comparison is only described in Appendix E.4, so please summarize the selection criterion and its uncertainty in the main body.","section":"§4.2"},{"comment":"The attack-success criterion of being below µuw + 2σuw is reasonable but arbitrary; the threshold-sensitivity figures in Appendix G.1 are helpful, and the main text should state that the headline ASR numbers use the 2σ operating point.","section":"§4.3"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about RQ1 lands: the lineage distinguisher is uncalibrated, and Section 5's 'islands' argument makes the interpretation ambiguous between slow mixing and non-irreducibility. I would accept a revision that reframes RQ1 as a traceability result, adds calibration controls or a mixing-time estimate, and corrects the Table 3 label swap. The RQ3 measurements and the human-review adjustment are useful even if RQ1 is toned down."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi — you should know two things. First, this paper is the strongest empirical stress-test of the WITS impossibility result I've seen: new benchmark, human-validated attacks, and numbers that make the 'watermarks are doomed' narrative look shaky in practice. Second, their headline 'mixing is slow' is inferred from a proxy that is never calibrated, so the theoretical refutation of KA1 is weaker than they claim. The practical attack results stand on their own, though.\n\nWhat's actually new: the Sandcastles dataset of 795 human-annotated perturbations, the lineage-distinguisher test (4,555 trials, 100% traced by an o3-mini escalation chain), and a systematic attack benchmark across 3 watermarks × 7 mutators. The ASR numbers (26.1% final, 10.5% after human review) are new measurements and are policy-relevant. They also honestly discuss the irreducibility 'islands' caveat in Section 5, which most empirical papers wouldn't.\n\nThe load-bearing weakness is RQ1. 100% lineage traceability implies the chain is far from stationarity only if the distinguisher is an unbiased estimator of total-variation distance. No control with known-mixed texts, no spectral gap estimate, no mixing-time bound. The forced-choice setup with ~10 autocorrelated samples per test and a single-sample failure criterion could produce 100% from side information or prompt leakage. Their own islands discussion offers a rival explanation. So read RQ1 as 'these specific P oracles don't visibly mix in budget', not as a refutation of KA1. Also Table 3 swaps SIR/KGW labels relative to Table 5 — fixable but currently confusing. The human-review Q-ASR uses tiny samples (often 1–20 texts per cell) and treats a 0-reviewed cell as 0% success, which is noisy. However, these don't sink RQ2/RQ3; the headline 'attacks don't reliably remove watermarks while preserving quality' survives because it is directly measured.\n\nThis is a paper for the watermarking and AI-security crowd, and for anyone relying on WITS to argue strong watermarking is hopeless. It deserves a serious referee: the instruments are worth publishing, the flaws are fixable, and the empirical attack results are a genuine contribution even if the mixing conclusion needs rework. I'd send it to review, and would use it in my own reading group.","headline":"A serious empirical challenge to the WITS impossibility result that deserves referee time, but the slow-mixing claim is not yet proven and needs calibration work.","tokens_in":28508,"tokens_out":2605,"would_cite":true,"duration_ms":25435,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Random-walk attacks remove AI text watermarks only about 10% of the time once humans verify quality.","keywords":["AI text watermarking","random-walk attacks","mixing time","quality oracles","LLM watermark robustness","human evaluation","text perturbation","impossibility result"],"falsifier":"Take a text-perturbation chain small enough to compute its actual mixing time (or with a known fast-mixing transition operator), run the paper's lineage distinguisher on samples drawn before and after that mixing time, and check whether traceability falls to chance once the chain has mixed; if it does not, the distinguisher is not a valid proxy for slow mixing, and the KA1 refutation collapses.","tokens_in":27346,"feed_emoji":"🛡️","tokens_out":16749,"duration_ms":145902,"temperature":0.7,"pith_summary":"Recent theory on 'watermarking in the sand' says any text watermark can be erased by a random walk of small quality-preserving edits, provided the walk mixes rapidly and an automated quality oracle guides it reliably. This paper tests both assumptions across three watermarking schemes and seven perturbation operators, and finds both fail in practice. Perturbed texts remain traceable to their starting text 100% of the time after hundreds of edits; the best automated quality oracle still misclassifies about one edit in five; and the average attack removes the watermark 26.1% of the time, dropping to 10.5% when human reviewers first confirm that text quality was actually preserved. If these results hold, the practical force of the theoretical impossibility result is much weaker than it looks, and watermarking remains a viable defense until attackers can mix text faster or judge quality better.","feed_headline":"Random-walk attacks erase text watermarks just 10% of the time","feed_subtitle":"The theoretical case against watermarking assumes fast mixing and perfect quality checks; real attacks have neither.","key_machinery":"The argument is carried by an empirical stand-in for the formal random-walk object: the graph $G^{\\ge q}_x$ of high-quality responses to a prompt, whose edges are weighted by a perturbation oracle $\\mathcal{P}$ and filtered by a quality threshold $q$. Instead of measuring the spectral gap (infeasible at this graph size), the paper uses a lineage distinguisher—an LLM shown two candidate starting texts and a mutated text, asked to name the origin—on the premise that a well-mixed walk should make this choice no better than chance. It also builds the Sandcastles benchmark, 795 human-annotated perturbations, to score how reliably automated oracles preserve quality, and then runs full attacks on KGW, SIR, and Adaptive watermarks guided by the best locally hosted oracle. The pivotal numbers are ASRfin, the fraction of attacks that push the detection score below the unwatermarked threshold, and Q-ASRfin, the same fraction after human adjudication that quality was preserved.","core_discovery":"The paper's central discovery is that the two assumptions behind the WITS impossibility theorem—rapid mixing and reliable quality guidance—do not hold for the watermarks, mutators, and oracles tested. A lineage distinguisher built from Llama-3.1-70B with escalation to GPT-4o and o3-mini-high correctly identified the origin of every one of 4,555 perturbed texts, including after 500 sentence-level mutations, so the random walks never lost memory of their starting points. The best automated quality oracle, a fine-tuned GPT-4o, reached an F1 score of 77.4%, meaning nearly one edit in five was misjudged. Final attack success averaged 26.1% across perturbation strategies; after human reviewers filtered out degraded outputs, the quality-controlled success rate fell to 10.5%, and no fairly evaluated attack succeeded more than half the time. The paper concludes that slow mixing and imperfect quality control make watermarking far harder to remove than the theoretical model suggests.","pith_inferences":["Because the slow-mixing evidence was collected with local, token-to-sentence-scale mutators, a mutator that makes large, context-aware jumps between stylistic regions could mix faster and partially restore the WITS-style impossibility; the paper's own discussion of disconnected 'islands' of high-quality text suggests this route is open.","The lineage distinguisher could be reused as a forensic audit tool: if 100% traceability holds after hundreds of edits, even heavily rewritten text may carry recoverable provenance signals.","If quality-preserving text does form disconnected islands, watermark designers could deliberately steer watermarked outputs toward isolated regions of the text space, turning a theoretical vulnerability into a structural defense.","The reversal of 'verification is easier than generation' implies that improvements in automated quality judgment—better reward models or reasoning models—are the key variable that would decide whether the theoretical attack ever becomes practical."],"forward_implications":["For the tested watermarking schemes, a random-walk attack is not the near-certain eraser the impossibility theorem describes: an attacker must either accept a low success rate or tolerate text that human readers judge degraded.","Watermark designs can exploit the measured asymmetry: Adaptive, which concentrates its signal in high-entropy tokens, held every word-level and entropy-word attack to 0% quality-controlled success.","Attack evaluations that omit human quality review will overstate success substantially; in this study the average success rate fell by 59.52% when human review was added.","Theoretical attack models should treat the quality oracle as a fallible component whose errors compound over many steps rather than as a perfect gate.","Automated quality metrics that reward surface fluency can improve even as human-judged quality drops, so they are not a reliable substitute for human evaluation in watermark attack studies."],"supporting_citations":[{"why":"Supplies the impossibility theorem and the two key assumptions (fast mixing and reliable quality oracle) that the paper sets out to test.","marker":"(Zhang et al., 2024)"},{"why":"Defines the KGW red-green watermark, one of the three schemes attacked.","marker":"(Kirchenbauer et al., 2023)"},{"why":"Defines the SIR semantic-invariant watermark, the second scheme attacked.","marker":"(Liu et al., 2024a)"},{"why":"Defines the Adaptive watermark, the most resistant scheme in the paper's attack results.","marker":"(Liu and Bu, 2024)"},{"why":"Provides the InternLM reward model used as the quality oracle guiding the full attacks.","marker":"(Cai et al., 2024)"},{"why":"Supplies the arena-human-preference prompt pool from which the Sandcastles quality benchmark was sampled.","marker":"(Chiang et al., 2024)"},{"why":"Provides the Llama-3.1 models used for text generation, mutation, and lineage classification.","marker":"(Dubey et al., 2024)"},{"why":"Provides T5-XL, which powers the SpanMutator, the paper's closest reproduction of the WITS perturbation oracle.","marker":"(Raffel et al., 2019)"},{"why":"Provides the DIPPER paraphrase model behind the DocumentMutator attack.","marker":"(Krishna et al., 2023)"}],"fun_headline_variants":["Watermarks survive random-walk attacks 90% of the time","Slow mixing and flawed quality checks make watermarks hard to erase","Watermark removal succeeds only 10% when humans check quality","Random-walk attacks fail 90% of the time on human-checked texts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The conclusion that mixing is slow rests on treating an LLM's ability to trace a mutated text back to one of two originals, in 100% of tests, as evidence that the random walk has not approached its stationary distribution; the paper never directly measures the mixing time or calibrates the distinguisher against the formal definition.","fun_headline_variants_meta":{"raw":{"variants":["Watermarks survive random-walk attacks 90% of the time","Slow mixing and flawed quality checks make watermarks hard to erase","Watermark removal succeeds only 10% when humans check quality","Random-walk attacks fail 90% of the time on human-checked texts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000644,"raw_usage":{"total_tokens":2965,"prompt_tokens":955,"completion_tokens":2010,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":1934}},"tokens_in":571,"tokens_out":2010,"duration_ms":14655,"temperature":1.0,"reasoning_tokens":1934,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:32:37.891272+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a text-perturbation chain small enough to compute its actual mixing time (or with a known fast-mixing transition operator), run the paper's lineage distinguisher on samples drawn before and after that mixing time, and check whether traceability falls to chance once the chain has mixed; if it does not, the distinguisher is not a valid proxy for slow mixing, and the KA1 refutation collapses.","supporting_citations":[],"review_version":1}