acceptodds
Under review as a conference paper at ICLR 2027

What Survives a Rewrite? Information Budgets for Inherited Watermarks

Abstract

Watermarked text often reaches a verifier after another model has rewritten it. That model may add a new watermark, but the upstream key reaches it only through the inherited document. We ask what survives such a rewrite. The coupling of old and new text has three information budgets: erased, transmitted, and fresh. A key enters the new text only through the fresh budget and leaves only through the erased one; the inherited key, which cannot enter, is capped by the transmitted budget. A task bounds the fresh budget through the outputs it allows and the erased budget through the inputs each output tolerates, and what every admissible output reveals fixes a retention floor. When fidelity means preserving a statistic , the floor is exactly , attained by conditional resampling that preserves the text distribution. For binary symmetric rewriting, we derive the exact injection optimum for uniform keys of every bit length. Failures cost at most the key alphabet, and a sharp loss bound for nearly exact copying is independent of document length. Finite-alphabet experiments exhibit the optimal operations and strict gaps below the budgets. Controlled experiments on two language models separate task execution from detector survival: Qwen3-4B rewrites all four target facts correctly in reports, while inherited-key detection falls from upstream to in each sampling arm. Paired -document comparisons isolate re-watermarking, and complete three-hop trajectories show that early stopping leaves hop-3 detection counts unchanged.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, watermarking, information theory, text provenance, robustness

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_WnkjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper develops an information-theoretic framework for what survives when a watermarked document is rewritten by an operator that does not hold the original key. It models each downstream transformation as a key-blind operation with three budgets—erased, transmitted, and fresh—showing that a new key can enter only through fresh content, while the inherited key can be retained only through transmitted content and is lost through erasure. It further characterizes how task constraints protect key information via fibers and the “shadow” partition, with exact floors for statistic-preserving tasks and finite-key loss bounds. Experiments on language-model rewriting and factual-report tasks illustrate the separation between task success and inherited-watermark survival.

Critical strengths
  1. The three-budget decomposition (erased, transmitted, fresh) and the key-flow theorem yield sharp caps and explicit gaps for both fresh-key injection and inherited-key retention under key-blind rewrites. This framework unifies copying, paraphrasing, translation, and re-watermarking under one set of identities, and its equality conditions clarify exactly when the caps are attained. It is conceptually simple, technically rigorous, and directly applicable to provenance analysis.
  2. By modeling task fidelity through fibers and the shadow partition, the paper proves that every faithful rewrite protects at least the key information in the task’s shadow
Critical weaknesses
  1. The central theory is not connected to real semantic rewriting. The exact floors and attainment results require a completely specified task relation with computable fibers and shadow, but natural-language fidelity for paraphrase, translation, or summarization is never formalized.
  2. The re-watermarking study fails to reject zero difference—all intervals include zero, and no sign test rejects—which is not evidence of equivalence, yet it is presented as supporting a prediction about removal.
Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Wnkj (1/2)

Response to Reviewer Wnkj (1/2)

Thank you for the review and for describing the framework as "conceptually simple, technically rigorous, and directly applicable to provenance analysis". In short: (W1) retention after real paraphrase is now measured, ≥ 1.27 nats certified while the token detector flags 8/64; (W2) a post-hoc equivalence analysis excludes removal wherever it would be visible. W1 is here, W2 in (2/2).

W1: "The exact floors and attainment results require a completely specified task relation with computable fibers and shadow, but natural-language fidelity for paraphrase, translation, or summarization is never formalized."

The paper deliberately posits no formal relation for paraphrase, translation or summarization (§7.1): fixing one is a modelling choice, just as a rate–distortion function needs a chosen distortion measure. We disagree that the theory is therefore not connected to real semantic rewriting; it reaches it in four ways.

1. The floors need only a necessary condition of fidelity. If every correct paraphrase meets a checkable requirement RR (e.g. keep the named entities), it is RR-faithful, so by Theorem 2(iii) its retention is at least I(K1;τR(Y))I(K_1;\tau_R(Y)), whatever else "paraphrase" means, and this is positive whenever the key shapes that content (E1b); a fuller formalization only raises this floor.

2. Measuring retention needs no formal relation. The paper's inequality (§3, p.4) holds for any test applied to the rewrite and the key: Rret≥d(TPR∥FPR)R_{ret}\ge d(\mathrm{TPR}\Vert \mathrm{FPR}). A task relation is needed for the floors (what must survive), not to measure what did survive. We applied this to real paraphrases and summaries (E1, Qwen3-4B, n=64 each). A verifier holding only the key, A's prompt and A's model regenerates A's text under the true key and 15 decoy keys, and ranks the candidates by similarity to the rewrite:

rewritekey ranked 1st of 16token detector @1%certified retention
paraphrase (plain / race)51/64 / 50/648/64 / 7/64≥ 1.27 / 1.21 nats
summary (plain / race)36/64 / 33/644/64 / 3/64≥ 0.55 / 0.45 nats
3rd successive paraphrase41/64 / 38/644/64 / 7/64≥ 0.76 / 0.63 nats
null (unrelated key's text)13/256 (chance: 16/256)––

If the provider keeps its logged output, paraphrase identification is 64/64; French translation, available only in this logged setting and scored with an English embedder (exploratory), still gives 30–34/64 against 1/64 token detections. We attribute the gap between the settings to regeneration fidelity, which a direct test supports (General response §1b): where regeneration is bit-exact (29 documents, a non-randomized split) they coincide, and elsewhere identification falls with how early it diverges.

This is what Remark 2 implies for semantic rewriting. For a deterministic-key watermark, Rret=MAR_{ret}=M_A (Remark 2), so whatever content a faithful paraphrase keeps also carries the key, even when token-level evidence is largely lost. Word overlap does about as well as the embedding (better on summaries): the evidence is the content the rewrite keeps, which is what MAM_A counts.

3. The paper does contain a formalized natural-language task. The factual-report relation (strict JSON, four exact fields, free narrative wording; §6.3, H.3) is a statistic-preserving relation. Its fibers and shadow are computable: the shadow is the field tuple, and the floor is exactly I(K1;fields)I(K_1;\text{fields}).

  • In the paper the fields are drawn independently of the key, so the floor is 0: a rewrite that depends only on the fields does the task perfectly and erases the key (A.4). Task-only regeneration (§6.3) sees only the parsed fields; its retention is at most what parsing recovers. Qwen's full-context rewrite keeps all four fields in 64/64 with 1/64 token detections; token evidence alone cannot show erasure (E1), so attainment rests on A.4, not on this rewriter (General response §2b).
  • In the new E1b, the watermarked model chooses the fields, so the floor is positive. Field matching then identifies the key in 28/64 and 30/64 rewrites (null 6/64), while token detection is 3/64 and 1/64.

4. Relations with editing tolerance are easy to write, and their floors are strictly positive whenever the key shapes the required content. We will add a worked example [Rev: App. J.3]. The required entities come from a catalogue whose names are more than 2t2t edits apart; each may be misspelled by up to tt edits, and the wording is free. The shadow is then the entity tuple, and the minimum retention is exactly I(K1;entities)I(K_1;\text{entities}). Even a number reported only within ±k\pm k keeps a positive floor (ln⁡20≈3.0\ln 20\approx 3.0 nats for a uniformly key-chosen attendance, k=5k=5; Prop. J.4), and imperfect execution costs only a Fano term.

We will add this discussion to the revised §6.6 and §7.1 [Rev].

(continued in 2/2)

AuthorsOpenReview ↗

Response to Reviewer Wnkj (2/2)

Response to Reviewer Wnkj (2/2)

W2: "The re-watermarking study fails to reject zero difference—all intervals include zero, and no sign test rejects—which is not evidence of equivalence, yet it is presented as supporting a prediction about removal."

The paper states in three places that non-rejection is not equivalence: "This does not establish equivalence" (§6.4, p.8), "does not establish equivalence between the two arms" (G.1, p.28), and "nor show that the arms are equivalent" (H.2, p.33). The revised PDF will replace our phrase "Table 2 tests this prediction" with the test that matches the prediction.

The prediction is equality in distribution: every realization of the same key-averaged channel induces the same joint law of (K1,Y′)(K_1,Y') (A.6), so, under ideal randomness, a distortion-free second watermark cannot change the distribution of any inherited-key statistic. The matching analysis is an equivalence test. It is post hoc: our pre-specified family was the sign test, and the analysis will be labelled post hoc in [Rev: App. K].

In plain terms: if a second watermark removed the first, Llama copies would fall from 189/200 detected to about 2/200; with the second watermark they are at 193/200. Qwen paraphrases would fall from 25/200 to about 2/200; they are at 28/200.

Detection rates (inherited key at 1%, saved Table 2 pairs, 200 documents per cell; paired 90% document-bootstrap CI of race − plain, in percentage points):

cellplain → racerace − plain [90% CI]within ±5within ±10
Qwen copy191 → 1910.0 [0.0, 0.0]yesyes
Qwen paraphrase25 → 28+1.5 [−2.5, +5.5]noyes
Qwen summary10 → 7−1.5 [−4.5, +1.5]yesyes
Llama copy189 → 193+2.0 [0.0, +4.5]yesyes
Llama paraphrase9 → 10+0.5 [−3.0, +4.0]yesyes
Llama summary14 → 8−3.0 [−6.5, +0.5]noyes
pooled438 → 437 of 1200−0.1 [−1.3, +1.3]yesyes

The pooled CI treats pairs as independent, although the three operations share documents; the document-clustered interval is [−1.33, +1.08] points (App. K). Rates are equivalent within ±10 points in 6/6 cells and within ±5 points in 4/6; in the three near-null cells below, the ±10 margin exceeds what complete removal would change, so the informative cells are Llama copy and Qwen paraphrase. The two ±5 exceptions are Qwen paraphrase (upper bound +5.5) and Llama summary (lower bound −6.5; McNemar p = 0.26).

What each cell can detect. Not every cell can show removal:

  • Qwen copy is close to automatic: race and plain scores are exactly tied in 194/200 documents, because copying leaves the second key little fresh budget. Llama copy has 139/200 ties but 61 untied pairs.
  • The informative cells are those where removal would be visible:
    • Llama copy (61 untied pairs). Removal would mean a drop of about 93.5 points toward the 1% null; the CI [0.0, +4.5] contains no drop.
    • Qwen paraphrase. Removal would mean a drop of about 11.5 points; the CI is [−2.5, +5.5].
  • In the other paraphrase and summary cells, the rewrite itself has already removed nearly all token-level evidence of the inherited key (plain-arm detection 4.5–7%, null 1%), so neither metric has much left to compare; the prediction is tested where that evidence remains, in the two cells above.

Mean scores. A post-hoc margin, the larger of 1 nat and 10% of the plain mean, gives score equivalence in 6/6 cells (paired-t TOST, largest p 0.045, Llama copy; Holm-adjusted, all pass); a flat 1 nat alone passes 5/6 (Llama copy, mean 109 nats, fails) and a flat 10% alone 2/6 (App. K). This margin is informative only where the signal exceeds it. In Qwen summary, Llama summary and Llama paraphrase, the plain-arm signal above the null mean (0.38, 0.45 and 0.83 nats) is smaller than the 1-nat margin, so those score tests cannot exclude complete erasure. For this reason we lead with detection rates.

The §6.4 sentence will read: "Table 2 compares the two arms; a post-hoc equivalence analysis (App. K) finds detection rates equivalent within ±10 points in all six cells and within ±5 points in four, and pooled detections of 438 vs 437 of 1200. These margins are informative where complete removal would exceed them, and there removal is excluded: Llama copy changes by +2.0 points [0.0, +4.5] against the 93.5-point drop removal would cause, and Qwen paraphrase by +1.5 [−2.5, +5.5] against an 11.5-point drop."

This point produced App. K; the prediction is now tested by the analysis it calls for. Together with (1/2), this shows that the theory reaches real semantic rewriting through certified lower bounds on retention, and that the re-watermarking prediction now rests on a post-hoc equivalence analysis that excludes removal wherever it would be visible. We are glad to clarify anything before the discussion ends; if these changes resolve your concerns, we would appreciate it if you would reconsider your rating.

Thank you very much for your response.

After careful consideration, I have decided to maintain my score. I remain open to the discussions and decisions of other reviewers.

Reviewer_LAUJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Model A watermarks its text with a secret key. Model B, without the key, then rewrites the text and may add its own watermark. The paper asks how much of A's watermark can survive. Using information theory, it splits a rewrite into what it deletes, what it carries over, and what it adds. The first result says that B's key enters only through the added material and A's key leaves only through the deleted material. So the information about A's key that the rewrite still carries, which the paper calls retention, is at most what it carries over. The second result is a lower bound on retention, which the paper calls a floor. If every acceptable rewrite must reveal some part of the original, such as required facts, the key information in that part always survives. When the task only requires keeping that part, resampling the text conditioned on it erases all other key information, so the floor is tight. Experiments with small open models and Aaronson's watermark (Aaronson, 2023) measure detection after copying, paraphrasing, and other rewrites.

Critical strengths
  1. I think the using theoretical view of understanding how much watermark signal Survives after rewriting itself is an interesting research direction.

  2. The formal results are correct as far as I checked. Each main bound comes with an example where it is tight, or a counterexample when an assumption is dropped. The paper states which results need B to lack A's key. I also like the prediction that, with ideal randomness, a second distortion-free watermark cannot weaken the first on average.

Critical weaknesses

1. The main results formalize intuitive facts and add little new insight.

  • The upper bounds say that a rewrite keeps at most the key information it carries over from the original, and adds at most as much new key information as its new content allows. Both follow directly from the chain rule and the data processing inequality.
  • The construction that reaches the floor, resampling while keeping the required content, is an idealized version of the random-walk attack of Zhang et al. (2023). The bound on what a freely designed key can add is, as the paper notes, a special case of Rassouli & Gündüz (2023).
  • What remains new is the three-way split itself and an exact formula for a uniform key of any length in the simplest one-bit setting. I would like to see one non-obvious prediction that follows from the framework but not from intuition or prior work.

2. The theory does not connect to watermark detection, so the experiments cannot test it.

  • Retention measures information about the key, not what a detector can find. With Aaronson's watermark, the text is fixed once the key and prompt are fixed, so retention equals everything the rewrite reveals about the original. A paraphrase that keeps the story therefore keeps much of the key information in the paper's accounting.
  • Yet on Llama, the mean detector score drops from 109.21 for copies to 1.83 for paraphrases, where 1 means no evidence (Table 2). The paper reads such scores as consistent with its upper bound, but that bound is loose for any meaning-preserving rewrite, so every score fits it. Detection cannot check the floors either, because both only show that retention exceeds some amount.
  • The floor gives no number for paraphrase, summary, or translation, since these tasks have no formal definition of an acceptable output. The experiments' main finding, that a rewrite keeps the facts but loses the watermark, is the known effect of paraphrasing (Kirchenbauer et al., 2023).
Questions for authors
  1. With Aaronson's watermark on A's text, a paraphrase that keeps the story seems to keep much of the key information in your accounting. Is that right, and what must a verifier know, such as A's prompt or model, to detect it?
  2. What does the floor predict about a real rewriter that does not already follow from the random-walk attack of Zhang et al. (2023)? One concrete example would help.

A few smaller suggestions:

  1. If B was fine-tuned on text watermarked with A's key, it can carry that key's signal without ever seeing the key. Models trained on watermarked text inherit the watermark (Gu et al., 2024; Sander et al., 2024). The upper bound on retention can then fail, although the floors still hold. Since deployed keys are usually fixed, this case deserves a paragraph.
  2. Use one model of the key throughout. Table 6 compares the information cost of random token edits with the full entropy of each text, but elsewhere the paper assumes a 63-bit key. Under that assumption, the floor for edited text says nothing after 4.5 random edits, while the detector still flags most edited outputs.
3 comments
AuthorsOpenReview ↗

Response to Reviewer LAUJ (1/3): novelty and non-obvious predictions

Response to Reviewer LAUJ (1/3): novelty and non-obvious predictions

Thank you for checking the proofs and for the precise questions. Your request for "one non-obvious prediction that follows from the framework but not from intuition or prior work" is answered under W1d below; the full new-vs-organized list is in our reply to PTC4 (Q2).

W1a: "Both [upper bounds] follow directly from the chain rule and the data processing inequality."

The proofs are short by design ("short arguments", p.2; "classical information identities", F.2); what is new is the operation model and what it separates:

  • Independence alone controls injection, and key blindness alone controls retention. Each cap fails without its own hypothesis (Remark 1, Example 1).
  • The gap identities are exact, with equality conditions ((5)–(6)), not just inequalities. They give Rret=MAR_{ret}=M_A for every key-blind operation when the upstream scheme is deterministic given its key, as Aaronson's is on fixed hardware (Remark 2).

W1b: "resampling while keeping the required content, is an idealized version of the random-walk attack of Zhang et al. (2023)."

The connection holds for the achievability half, which we will cite explicitly [Rev: §5]. The floor is a converse, which a random walk does not provide:

  • (i) Theorem 2(iii) binds every faithful operation, including one that knows K1K_1 (p.5). Zhang et al. show that a walk can defeat a detector. They do not bound what must survive.
  • (ii) Conditional resampling is idempotent and preserves PYP_Y (A.4); viewed as a within-class walk, it is the endpoint whose stationary law is PY∣TP_{Y\mid T}. The floor says when such a walk erases the key: iff I(K1;τϵ(Y))=0I(K_1;\tau_\epsilon(Y))=0, given common outputs.

W1c: "The bound on what a freely designed key can add is … a special case of Rassouli & Gündüz (2023)."

A.6–A.7 credit that result for JfreeJ_{free}. Prop. 1 is not covered. It fixes the key law to a uniform 2b2^b key, whereas perfect privacy optimizes that law: "the enlargement of the key is permitted because its alphabet and law are optimized; it need not preserve a prescribed key resource" (A.6). Prop. 1 gives the exact price of a prescribed key, 2m[h(1+r2)−(1−r)ln⁡2]≤2ln⁡(5/4)/m\frac2m[h(\tfrac{1+r}2)-(1-r)\ln 2]\le 2\ln(5/4)/m (sharp; A.7), and shows that injection is quadratic, not linear, in δ\delta for every finite key. On "the simplest one-bit setting": the binary channel is where the prescribed-key optimum has a closed form; for general finite channels the optimized-key value is the linear program of A.6, and the budget identities, Theorem 2 and Prop. 2 hold for every finite alphabet.

W1d & Q2: a non-obvious prediction; "What does the floor predict about a real rewriter that does not already follow from the random-walk attack of Zhang et al. (2023)?"

Prediction 1: connectivity does not imply removability.

  • Intuition, and a random-walk argument over the admissible set, suggest that if all inputs are linked by admissible outputs, the key can be washed out.
  • The framework says otherwise. In A.3 (three inputs, two outputs, uniform key), the task graph is connected, so the shadow floor is 0. Yet every faithful operation, even a key-aware one, retains at least 23ln⁡2≈0.46\tfrac23\ln 2\approx 0.46 nats. This is strictly above both the shadow floor (0) and the counting floor (ln⁡32≈0.41\ln\tfrac32\approx 0.41); see Fig. 6b.
  • What decides removability is whether each component has a common admissible output (Theorem 2), not whether the graph is connected.

Prediction 2: under ideal randomness, a distortion-free second watermark cannot change the inherited-key score distribution (§6.4), which you highlight in Strength 2.

  • This contrasts with Bulychev et al. (2026) for images; removal by re-watermarking needs a distorting scheme (§6.4).
  • It is now supported by a post-hoc equivalence analysis rather than non-rejection: detection rates are equivalent within ±10 points in 6/6 cells (±5 in 4/6), and where removal would be visible it is excluded: Llama copy 189 → 193 (paired 90% CI [0.0, +4.5] points) and Qwen paraphrase 25 → 28 ([−2.5, +5.5]). Pooled (pairs treated as independent), detections are 438 vs 437 of 1200 (Wnkj 2/2).

Prediction 3, on a real rewriter: a field-faithful rewrite cannot shed key-chosen content.

  • When Qwen3-4B chooses the four report fields under its key, Theorem 2(iii) says every rewrite that keeps them, even a key-aware one, retains ≥I(K1;T∣X)>0\ge I(K_1;T\mid X) > 0 nats. A random-walk argument bounds no such quantity.
  • Measured (E1b, General response §2): exact field matching identifies the key in 28/64 and 30/64 rewrites (null 6/64), while the token detector flags 3/64 and 1/64.

Further results that intuition does not give: a copy-failure loss independent of document length (0.961 nats for Qwen3-4B's 150/150 exact copies, vs ln⁡263=43.67\ln 2^{63}=43.67), and a finite-key injection gap (0.0823 vs 0.2773 nats at δ=0.2\delta=0.2, with fresh budget 0.5004).

(continued in 2/3)

AuthorsOpenReview ↗

Response to Reviewer LAUJ (2/3): retention and detection

Response to Reviewer LAUJ (2/3): retention and detection

Q1: "a paraphrase that keeps the story seems to keep much of the key information in your accounting. Is that right, and what must a verifier know, such as A's prompt or model, to detect it?"

Yes, by the paper's Remark 2 (p.26): on fixed hardware the race is deterministic given key and prompt, so Rret=MAR_{ret}=M_A for every key-blind operation. We measured how much a verifier can read (E1, General response §1; Qwen3-4B, n=64):

  • Key-only verifier: holds K1K_1, A's prompt and A's model, regenerates A's output under the true key and 15 decoy keys, and ranks them against the rewrite. It identifies the key in 51/64 and 50/64 paraphrases (plain/race), certifying ≥ 1.27 / 1.21 nats (lower bounds, capped at ln 16 = 2.77 by the 15 decoys). The token detector flags 8/64 and 7/64 of the same outputs, certifying 0.05 / 0.03 nats.
  • Logged-output verifier: a provider that keeps its own output identifies the key in 64/64, certifying MA≥2.41M_A\ge 2.41 nats. This resembles retrieval (Krishna et al., NeurIPS 2023); the key-only setting needs no log.

The token detector needs only K1K_1; §6.6 will state this verifier hierarchy [Rev].

W2a: "The theory does not connect to watermark detection … Retention measures information about the key, not what a detector can find."

The link is the inequality at the end of §3 (p.4): any test applied to (Y′,K1)(Y',K_1) gives Rret≥d(TPR∥FPR)R_{ret}\ge d(\mathrm{TPR}\Vert \mathrm{FPR}). Retention upper-bounds what any verifier can read, and each detector certifies a lower bound on it.

  • Table 9 already holds the text, and hence its information, fixed, and on Llama the detector reads 0.95 or 0.00 depending only on its context width.

W2b/W2c: "With Aaronson's watermark, the text is fixed once the key and prompt are fixed" … "the mean detector score drops from 109.21 for copies to 1.83 for paraphrases … that bound is loose for any meaning-preserving rewrite, so every score fits it."

For Aaronson's scheme the retention cap is not loose: it is an equality, Rret=MAR_{ret}=M_A (Remark 2, Q1). What is loose is the token score: it lower-bounds retention, so a drop in it cannot falsify the cap; §6.2 will read "consistent with, though not a test of, the caps" [Rev]. The drop reflects token-level evidence, not retention. On Llama, your example (first 64 documents, not Table 2's 200: means 119.20 for copies and 1.56 for paraphrases, plain arm), paraphrase leaves 1/64 and 4/64 token detections, while key-only identification is 36/64 and 35/64 (chance 4/64), certifying ≥ 0.552 / 0.516 nats, a bound limited by regeneration fidelity (General response §6). Qwen3-4B shows the same pattern (8/64 vs 51/64, Q1).

W2d: "Detection cannot check the floors either, because both only show that retention exceeds some amount."

The attainment statements also make upper predictions, which detection can check:

  • When I(K1;T)=0I(K_1;T)=0, the optimal faithful operation has Rret=0R_{ret}=0, so every detector must read null on its output. Task-only regeneration (§6.3) gives a one-sided check: it sees only parsed fields, so its retention is at most what parsing recovers; detections above the 1% rate would falsify the prediction. It gives 0/64 token detections on Qwen (Llama: 2/64 and 0/64, Table 1), and key-only identification (7/64, 5/64) is not distinguishable from chance (General response §2b).
  • When I(K1;T)>0I(K_1;T) > 0, every field-faithful rewrite, even a key-aware one, keeps TT and hence ≥I(K1;T)\ge I(K_1;T) nats, so matching TT must beat chance. E1b gives 28/64 and 30/64, against a null of 6/64.

W2e: "The floor gives no number for paraphrase, summary, or translation"

By design, the floor is defined relative to a task relation, just as a rate–distortion function is relative to a distortion measure; the paper claims no floor for paraphrase. The measurement needs no relation. The key-only certificate gives numbers for paraphrase (≥ 1.27 / 1.21 nats), summary (≥ 0.55 / 0.45) and the third paraphrase hop (≥ 0.76 / 0.63); exploratory French translation (logged setting, English embedder) gives 30–34/64 against 1/64 token detections (MA≥M_A\ge 0.35–0.48 nats). Where a task specifies content, as in the factual task and E1b, the relation is easy to write, and [Rev: App. J.3] will give relations that tolerate edits.

W2f: "keeps the facts but loses the watermark, is the known effect of paraphrasing (Kirchenbauer et al., 2023)."

The paper cites this token-level loss as known (§2, F.2); what it adds is different:

  • (i) A controlled separation with a formal task metric and full cohorts: Qwen rewrites keep the fields in 64/64 reports with 1/64 detections (38/38 and 0/38 on upstream successes).
  • (ii) Which removal the task permits: the fields are independent of the key (I(K1;T)=0I(K_1;T)=0), so complete removal is attainable without loss of fidelity.
  • (iii) E1: paraphrase removes token-level evidence while key information stays readable (Q1).

(continued in 3/3)

AuthorsOpenReview ↗

Response to Reviewer LAUJ (3/3): fine-tuned rewriters, one key model

Response to Reviewer LAUJ (3/3): fine-tuned rewriters, one key model

S1: "If B was fine-tuned on text watermarked with A's key, it can carry that key's signal without ever seeing the key. … The upper bound on retention can then fail, although the floors still hold."

The revised PDF will add a paragraph [Rev: §3] and the proposition below [Rev: App. J.2], and will cite Gu et al. (2024) and Sander et al. (2024).

The model: B's parameters θB\theta_B may depend on K1K_1 through training data, but B sees the key only through the document and its weights, i.e. Y′⊥K1∣(Y,θB,X)Y'\perp K_1\mid(Y,\theta_B,X). Then:

  • Inflow: I(K1;Y′∣Y)≤I(K1;θB∣Y)I(K_1;Y'\mid Y)\le I(K_1;\theta_B\mid Y), which is zero when θB\theta_B is independent of (K1,Y)(K_1,Y), e.g. off-the-shelf weights.
  • Cap: Rret≤I(K1;θB)+I(Y;Y′∣θB)R_{ret}\le I(K_1;\theta_B)+I(Y;Y'\mid\theta_B). Proof: I(K1;Y′)≤I(K1;Y′,θB)=I(K1;θB)+I(K1;Y′∣θB)I(K_1;Y')\le I(K_1;Y',\theta_B)=I(K_1;\theta_B)+I(K_1;Y'\mid\theta_B), and conditional data processing along K1→Y→Y′K_1\to Y\to Y' given θB\theta_B.
  • Conditional on the deployed model, and with K2⊥(K1,Y,θB)∣XK_2\perp(K_1,Y,\theta_B)\mid X, Theorem 1 holds verbatim with K1K_1's posterior law given θB\theta_B.
  • Floors unchanged: Theorem 2(ii)–(iii), Prop. 2 and (13) never use key blindness (p.5; Remark 1; A.3).

The radioactivity effect is the case I(Y;Y′∣θB)=0I(Y;Y'\mid\theta_B)=0: input-independent generation can still carry up to I(K1;θB)I(K_1;\theta_B); this is the phenomenon Sander et al. observe. Fixed deployed keys make this term relevant, as you note. In our experiments the models are off-the-shelf and keys are per-document from separate streams, so I(K1;θB)=0I(K_1;\theta_B)=0.

S2: "Use one model of the key throughout … Under that assumption, the floor for edited text says nothing after 4.5 random edits, while the detector still flags most edited outputs."

The revised PDF will use K1K_1 uniform on 2632^{63} values throughout [Rev: B.2], so I(Y;K1)≤43.67I(Y;K_1)\le 43.67 nats. The path entropies of Table 6 will be kept only as fresh-randomness diagnostics.

Recomputed Table 6 (E3):

modelfloor vacuous afterdetection at the bracketing rates (1% / 2.5% edits)detector diagnostic (nats)
Llama-3.2-3B2.57 edits0.946 / 0.94612.5 / 12.5
Qwen3-4B2.54 edits0.447 / 0.3405.0 / 3.6
Qwen3-1.7B2.56 edits0.647 / 0.5697.7 / 6.6

The crossing is at about 2.5 edits; 4.5 is the first tabulated row past it. These numbers do not contradict each other:

  • Corollary 3 is a worst-case floor over every faithful operation with that edit budget. That includes key-targeted edits and redaction, which "destroys mlog⁡∣V∣m\log|V| nats in mm edits" (Remark 3).
  • Random substitutions are far from worst case, and for them the exact identity Rret=MAR_{ret}=M_A (Remark 2) still holds.
  • The detector's own binary-KL diagnostic (12.5 nats on Llama, nominal α=10−6\alpha=10^{-6}) is an operation-specific lower bound below 43.67. A vacuous worst-case floor and a positive operation-specific diagnostic coexist.

Re-checking this table also uncovered a bug: the saved Llama "priced" column used the Qwen vocabulary size (151,936 instead of 128,256). This overstated the price by 0.169 nats per edit (e.g. 74.8 → 74.1). The revised Table 6 will correct it; no conclusion changes.

Summary for W1/W2. You asked for a non-obvious prediction about a real rewriter. The framework gives two, both now measured. A paraphrase that defeats token detection still retains key information readable from A's key, prompt and model (Remark 2 and the §3 inequality): ≥ 1.27 nats, against 0.05 nats from the token detector (8/64 detections); your Q1 shaped this result. Every field-keeping rewrite of key-chosen facts retains key information (Theorem 2(iii), a converse no random walk gives): 28/64 and 30/64 identifications against a null of 6/64.

The paper also proves a structural one: connectivity does not imply removability. A.3's connected task forces every faithful operation, even a key-aware one, to retain at least 23ln⁡2\tfrac23\ln 2 nats, which is above both floors. Re-watermarking non-weakening, which you singled out in Strength 2, is now supported by post-hoc equivalence of detection rates (438 vs 437 of 1200).

Presentation. The new §3 opening follows your summary and will read: "A rewrite deletes, carries over and adds information. For a key-blind rewriter, the inherited key survives only in what is carried over, and a new key enters only through what is added. A task protects whatever every acceptable output lets one recover." We will also add a notation table to App. A [Rev].

Changes in the revised PDF for your points: §1 contribution list (W1); §5 Zhang et al. as achievability (W1b); §3 Remark 2 and App. J.1 (W2a); §6.2 wording (W2c); §6.6 (Q1, W2); App. J.2 (S1); B.2 and Table 6 (S2); §3 overview and notation table (Presentation).

We are happy to answer any remaining question before the discussion closes; if these changes resolve your concerns, we would appreciate it if you would reconsider your rating.

Reviewer_PTC4OpenReview ↗
Rating
3
Confidence
4(+1)
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies rewriting by a downstream model that does not know the upstream watermark key and encounters it only through the inherited text. It describes the input-output coupling using erased information, transmitted information, and fresh information: H(Y∣Y′)H(Y\mid Y'), I(Y;Y′)I(Y;Y'), and H(Y′∣Y)H(Y'\mid Y). It derives bounds and exact gaps for new-key injection, inherited-key retention, and information loss. A task's allowed input-output pairs define forward fibers, backward fibers, and connected components called its shadow. These characterize information that task fidelity necessarily preserves. When the entire task requirement is to preserve a statistic TT, conditional resampling attains the exact retention floor I(K1;T)I(K_1;T) while preserving the text marginal. Further results characterize optimal injection for prescribed uniform finite keys on a binary symmetric channel and give a document-length-independent loss bound for nearly exact copying. Finite-alphabet experiments check the information quantities directly, while language-model experiments examine detector evidence and task outcomes.

Critical strengths
  1. The exact task-dependent retention floor gives a useful explanation of watermark removal under fidelity constraints. Theorem 2 identifies the information that a task forces the output to retain. When preserving TT is the complete task requirement, dependence between the key and TT must survive, and conditional resampling removes the remaining dependence while preserving the overall text distribution. Appendix A.3 also gives a case where the shadow bound is strict because a component has no common admissible output. This makes the attainment conditions precise. The result helps distinguish provenance information tied to required content from information carried by freely changeable expression, and is my main reason for supporting acceptance.

  2. The paper combines precise finite-key results with careful measurement. The basic budget bounds use standard information identities, which the authors acknowledge. Proposition 1 goes further by giving the exact injection optimum for a prescribed uniform finite key and a sharp finite-key gap. This shows why available fresh entropy need not be fully usable by a given key resource. The empirical reporting is also careful: Table 2 includes paired intervals and the number of untied comparisons, and does not treat a nonsignificant difference as equivalence. Appendix A.9 explains through a counterexample why local replay is not an exact decomposition of the detector null.

Critical weaknesses
  1. The task bounds have limited operational reach for general natural-language rewriting. The shadow is a connected component of the allowed input-output relation. Small admissible changes can connect a large support through intermediate texts, making the shadow bound zero. Backward-fiber counts can also become too large to provide useful bounds. The exact statistic-preservation result assumes that preserving TT satisfies the entire task, which leaves open tasks with simultaneous requirements on factual accuracy, style, length, or edit distance. The paper recognizes these limits. A concrete language task with a useful, strictly positive guarantee would make the practical scope clearer. I view this as a limitation of applicability rather than a correctness objection.

  2. The direct validation of information removal is concentrated in the finite-alphabet setting. The language-model studies offer a useful distinction between task execution and detector survival, but do not establish how much key information remains. In the factual task, fields are generated independently of the key, so the setup has a zero task-dependent floor. Qwen's 64/64 field success with 1/64 detections therefore does not test a nonzero retention guarantee. Only 10/64 plain rewrites and 11/64 watermarked rewrites satisfy the narrative length requirement, and Appendix H.3 documents unsupported prose despite correct fields. The authors disclose these outcomes and correctly call the metric four-field success. These results illustrate the behavior of the tested detector under a specific task; a stronger connection to retained information would increase the empirical contribution.

Questions for authors
  1. Applicability of the task bounds. Could you give a concrete task relation that allows nonzero editing tolerance and goes beyond unrestricted resampling within a statistic class, while still yielding a useful nonzero shadow or backward-fiber bound? A worked example would clarify how to use the framework when semantic similarity connects many texts.

  2. Precise novelty. The paper already connects its results to the Gács-Körner common part, the privacy funnel, perfect privacy, and conditional-entropy continuity. Could you state more explicitly which results are new and which organize or specialize existing results for inherited watermarking? The prescribed uniform-key optimum and task-constrained attainment results seem central to this distinction.

  3. Theory and language-model measurements. Section 6.1 already validates a nonzero floor using K1=(C,W)K_1=(C,W) and T=CT=C. Is there a language-model task with a checkable nonzero task-key association that could illustrate the relation between retained information and detector power? A small example, or a clearer statement of why the current language-model experiments target detector behavior, would help.

2 comments
AuthorsOpenReview ↗

Response to Reviewer PTC4 (1/2)

Response to Reviewer PTC4 (1/2)

Thank you for the careful review. You asked for "a concrete language task with a useful, strictly positive guarantee": we give one below and test one on an LM (General response §2).

W1 & Q1: "Could you give a concrete task relation that allows nonzero editing tolerance and goes beyond unrestricted resampling within a statistic class, while still yielding a useful nonzero shadow or backward-fiber bound?"

Yes. Both use the factual-report format of §6.3 (full statements: [Rev: App. J.3, §5]).

(a) Entities with typo tolerance: the shadow survives editing.

  • Setup: the report's required entities c=(c1,…,ck)c=(c_1,\dots,c_k) (e.g. organizer, city) come from a catalogue whose names are pairwise more than 2t2t edits apart. The narrative ww is free.
  • Task: Yϵ((c,w))={(c′,w′): d(ci′,ci)≤t ∀i}\mathcal Y_\epsilon((c,w))=\lbrace(c',w'):\ d(c_i',c_i)\le t\ \forall i\rbrace. Each name may be misspelled by up to tt edits, and everything else may be reworded.
  • Shadow: the tt-balls are disjoint, so two inputs share an admissible output iff they have the same cc. Hence τϵ=c\tau_\epsilon=c despite the edits.
  • Floor: every component has the common output (c,w0)(c,w_0), so by Theorem 2 the minimum retention over faithful operations is exactly I(K1;c)I(K_1;c).
  • Comparison: the counting bound is vacuous once wording is rich (NϵN_\epsilon counts every supported wording of one cc). Admissible outputs need not reproduce cc: the tolerance is absorbed because cc can be decoded from any of them, and whatever every admissible output lets one decode is protected.

(b) Numeric tolerance: the shadow collapses, the backward fiber still helps.

  • Setup: attendance A∈{31,…,250}A\in\lbrace 31,\dots,250\rbrace may be reported within ±k\pm k. Chains of admissible outputs connect all values, so the shadow of AA is constant.
  • Bound: with exact fields TeT_e and a report A^\hat A satisfying ∣A^−A∣≤k|\hat A-A|\le k, we have H(A∣A^,Te)≤ln⁡(2k+1)H(A\mid \hat A,T_e)\le\ln(2k{+}1). Hence Rret≥I(K1;Te)+[I(K1;A∣Te)−ln⁡(2k+1)]+R_{ret}\ge I(K_1;T_e)+\big[I(K_1;A\mid T_e)-\ln(2k{+}1)\big]_+.
  • Example: for a uniformly key-chosen attendance and k=5k=5, the second term is ln⁡20≈3.0\ln 20\approx 3.0 nats; the shadow gives 0 for this field.

In (b), whole-text fibers are huge, but on the required field they have size 2k+12k{+}1, and a block-centre report attains the bound (Prop. J.4(c)). The step is general: if each admissible output is consistent with at most rr values of a feature f(Y)f(Y), then Rret≥[I(K1;f(Y))−ln⁡r]+R_{ret}\ge[I(K_1;f(Y))-\ln r]_+, even for key-aware operators. Semantic tolerance enters through rr, not the shadow.

For imperfect execution with failure probability p≤1−1/Lp\le 1-1/L (LL catalogue tuples), A.4's Fano step with the catalogue decoder lowers the floor in (a) by at most h(p)+pln⁡(L−1)h(p)+p\ln(L-1).

(c) The paper already contains one formal natural-language relation. The factual task (strict JSON, four exact fields, free narrative) is a statistic-preserving relation, so its shadow is the field tuple. Its floor is I(K1;fields)=0I(K_1;\text{fields})=0 by design. Theorem 2 therefore says complete removal is attainable without hurting the task (conditional resampling, A.4). Qwen's full-context rewrite keeps all four fields in 64/64 reports with 1/64 token detections (the null level). Attainment rests on that ideal rewrite, not on this rewriter: token evidence and key information come apart (General response §2b). With key-chosen fields (E1b) the floor is positive, and the key is identified well above chance (2/2).

Q2: "state more explicitly which results are new and which organize or specialize existing results"

Organized or specialized from known results:

  • caps via the chain rule and DPI;
  • JfreeJ_{free} (Rassouli & Gündüz, Thm 3);
  • the gap below FAF_A is excess functional information (Li & El Gamal);
  • the shadow is the Gács–Körner common part;
  • the partition optimum is a hard-constraint member of the privacy-funnel family;
  • (13) applies the Alhejji–Smith continuity bound.

New:

  • (i) The key-blind operation model with exact gap identities, and the separation it yields: independence alone controls injection, and key blindness alone controls retention (Remark 1). Hence Rret=MAR_{ret}=M_A for deterministic upstream schemes (Remark 2), which E1 uses to read key information from LM rewrites.
  • (ii) Prop. 1: the exact optimum for a prescribed uniform 2b2^b key, with the sharp gap 2ln⁡(5/4)/m2\ln(5/4)/m and quadratic, not linear, small-noise injection. Perfect privacy, which optimizes the key law, does not cover it.
  • (iii) Theorem 2: a floor binding even key-aware operators, its attainment condition, the PYP_Y-preserving idempotent optimizer, and A.3, where the minimum 23ln⁡2\tfrac23\ln 2 exceeds both floors.
  • (iv) Prop. 2, sharpened by (13): failures are charged to the key alphabet, independently of document length.
  • (v) The re-watermarking prediction, now with (post-hoc) equivalence evidence. This list will go into [Rev: §1].

(continued in 2/2)

AuthorsOpenReview ↗

Response to Reviewer PTC4 (2/2)

Response to Reviewer PTC4 (2/2)

W2 & Q3: "the setup has a zero task-dependent floor … Is there a language-model task with a checkable nonzero task-key association that could illustrate the relation between retained information and detector power?"

Yes (E1b, below); by design, the paper's own factual fields are drawn independently of the key, so its floor is zero. When I(K1;T)=0I(K_1;T)=0, the task requires nothing that carries the key; the token detector reads 1/64, its null, but the key-only test below shows that this rewrite still retains key information through its wording. Measuring retention takes a stronger test. We have now run the task you ask for (E1b, first row: the model chooses the fields, so the association is nonzero and checkable) and, for contrast, the story paraphrase of E1 (General response §§1–2):

test (Qwen3-4B, n=64, plain / race)key identified of 16token detector @1%certified RretR_{ret} (nats)
key-chosen facts, field-preserving rewrite28/64 / 30/64 (null 6/64)3/64 / 1/64≥ 0.29 / 0.35
story paraphrase, key-only verifier51/64 / 50/64 (null 13/256)8/64 / 7/64≥ 1.27 / 1.21

The key-only verifier needs K1K_1, A's prompt and A's model, but no stored output. A provider that keeps its logged output identifies the key in 64/64 paraphrases. General response §1 traces the gap between the two settings to regeneration fidelity, and §1b tests it directly.

These results illustrate the relation you ask about. Retained information and token-detector power come apart under rewriting. The retained part sits in the content the rewrite keeps. It is readable by a verifier that tests dependence on (Y′,K1)(Y',K_1) using A's prompt and model, and the paper's inequality Rret≥d(TPR∥FPR)R_{ret}\ge d(\mathrm{TPR}\Vert \mathrm{FPR}) (§3) turns the identification rate into certified nats.

On the paper's original factual task (floor 0), the same key-only verifier identifies the key from copies in 46/64 and 46/64 (limited by regeneration: 36/36 where the regenerated text reproduces the stored tokens), from fact-preserving rewrites in 35/64 and 36/64, and from task-only regeneration in 7/64 and 5/64 (chance 4/64). The fact-preserving rewrite stays above chance through its wording, so it does not attain the zero floor; task-only regeneration is not distinguishable from chance.

In the key-chosen-facts task, identification is limited by ties, not by lost fields. The model picks a field tuple that a decoy key reproduces 16.7% of the time, with 7.8 distinct tuples per 16 keys. This low diversity also makes the floor H(T∣X)H(T\mid X) small here. The floor binds rewrites that keep all four fields; ours does so in 56–58/64, and the certificate (≥ 0.29 / 0.35 nats) measures its retention directly. A required statistic with more entropy gives a larger guaranteed retention.

Why the original LM experiments target detector behavior: they illustrate what a detector can show. That includes the separation of the two caps (Fig. 4, Table 7), which is an illustration and not a test of the caps, as well as task execution versus survival (Table 1) and the second-watermark prediction (Table 2). The paper keeps detector scores and information separate (§3, Limitations). The new experiments add a direct, certified measurement of retention on LM outputs.

On the narrative diagnostics, we keep the numbers (10/64 and 11/64 within the requested word range; H.3's unsupported details) and the name "four-field success". The formal relation, and hence the floor, concerns the four fields. The narrative constraints are a separate quality check, which we report in full rather than fold into TT.

On simultaneous requirements (W1: accuracy, style, length, edit distance): adding requirements only shrinks each forward fiber Yϵ(y)\mathcal Y_\epsilon(y), so the task graph loses edges, the shadow becomes finer, and the floor I(K1;τϵ(Y))I(K_1;\tau_\epsilon(Y)) can only rise; Theorem 2(iii) applies unchanged. Extra requirements can affect only exact attainment, which needs a common admissible output per component. The minimum retention itself can only rise too, since fewer operations remain faithful; without a common output it can lie strictly above the floor (A.3, where it is 23ln⁡2\tfrac23\ln 2, above both floors). In example (a) of 1/2, a narrative length window keeps (c,w0)(c,w_0) admissible for any in-window w0w_0, so the floor is still attained.

Revisions (in the revised PDF): new §6.6 and [Rev: App. J.1, L] (E1, E1b), [Rev: App. J.3] (worked task relations), [Rev: §1] (contribution list).

The worked examples came directly from your Q1. We would be glad to add anything further before the discussion ends; if the worked examples meet your request for a concrete language task with a strictly positive guarantee, we would appreciate it if you would reconsider your rating.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General response (1/3): what a rewrite keeps, measured on language models

General response (1/3): what a rewrite keeps, measured on language models

We thank all three reviewers. LAUJ found the formal results "correct as far as I checked … Each main bound comes with an example where it is tight". PTC4 called the task floor "a useful explanation of watermark removal under fidelity constraints", and Wnkj called the framework "technically rigorous, and directly applicable to provenance analysis". The shared concern is the link between the theory and LM rewriting (LAUJ-W2, PTC4-Q3, Wnkj-W1). New experiments measure that link directly. They use Qwen3-4B (the paper's checkpoint; Llama-3.2-3B in §6) and the paper's saved rewrites, and no document within these cohorts is excluded (paired cohort: first 64 of 200 documents; three-hop cohort: all 64).

1. After paraphrase, token evidence is mostly gone but key information remains readable (E1).

Under Aaronson's scheme the upstream text is a function of key, prompt and model on fixed hardware, so Remark 2 (p.26) gives Rret=MAR_{ret}=M_A: what a rewrite keeps of the text, it keeps of the key. E1 uses this to read key information from LM rewrites.

The test ranks 16 candidate upstream texts by similarity to the rewrite: one generated under the true key, and 15 under decoy keys from the same key law, with the same prompt and model. If the rewrite were independent of the key, the true key would rank first with probability exactly 1/161/16 in setting (b), by exchangeability. In setting (a) this holds up to a hardware difference between candidates, and the null rows below check it. The detector inequality of §3 then gives d(TPR∥1/16)d(\mathrm{TPR}\Vert 1/16), evaluated at the lower end of the 95% Clopper–Pearson interval. With 15 decoys this is capped at ln⁡16=2.77\ln 16=2.77 nats; the cap grows as ln⁡(M+1)\ln(M{+}1).

We report two verifier settings:

  • (a) Logged-output verifier. The provider keeps the text it generated, as in retrieval-based defenses, and that text is the true candidate. Setting (a) certifies a lower bound on MA=I(Y;Y′)M_A=I(Y;Y'), which upper-bounds RretR_{ret} and equals it when generation is bit-reproducible (Remark 2).
  • (b) Key-only verifier. The verifier holds only K1K_1, A's prompt and A's model, and regenerates all 16 candidates the same way. Setting (b) lower-bounds Rret=I(K1;Y′)R_{ret}=I(K_1;Y') directly.

Key ranked first of 16 (Qwen3-4B, n=64, plain / race):

rewrite(a) logged(b) key-only (bge)(b) certified RretR_{ret}, natstoken detector @1%
paraphrase64/64 / 64/6451/64 / 50/64≥ 1.27 / 1.218/64 / 7/64
3rd successive paraphrase62/64 / 61/6441/64 / 38/64≥ 0.76 / 0.634/64 / 7/64
summary49/64 / 43/6436/64 / 33/64≥ 0.55 / 0.454/64 / 3/64
copy64/64 / 64/6455/64 / 55/64≥ 1.53 / 1.5364/64 / 64/64
null: rewrites of an unrelated key's text (256)13/256 = 0.05113/256 = 0.0510–

Chance is 0.0625. Setting (a) certifies MA≥2.41M_A\ge 2.41 nats for paraphrase.

After paraphrase, the token detector flags 8/64 and 7/64 documents (copies: 64/64), certifying 0.05 / 0.03 nats, while the key-only verifier identifies the key in 51/64 and 50/64, certifying about 1.2 nats. Across the three paraphrase hops, (b) certifies 0.63–0.94 nats. All of these are lower bounds, capped by ln⁡16\ln 16 and by regeneration fidelity.

Why (b) is below (a): regeneration fidelity (tested in §1b). Regeneration in bf16 on GPUs not matched per document to the original ones reproduced A's stored tokens exactly in only 29/128 documents. In those documents (b) coincides with (a) by construction, so they are not separate evidence. In the rest, (b) falls with how early the regeneration diverges. With bge it is 0 when divergence occurs within the first 16 tokens (6 rows per paired operation) and 0.88–1.00 for copy and paraphrase when it occurs after token 96. Even near-exact copies reach only 55/64 under (b). This pattern points to regeneration fidelity, rather than key information lost in the rewrite, as the limiting factor. The split is not randomized, so we tested the explanation directly: regeneration on the original GPU type reproduces all 70 testable of the 99 diverged documents (29 were generated on a GPU type no longer available), and (b) rises to 62/64 and 63/64 for paraphrase (General response 2/3, §1b).

Notes.

  • Word overlap (unigram Jaccard) does as well as bge on paraphrases and better on summaries, though slightly worse on most three-hop cells. In (a) it scores 1.00 on paraphrases and 0.97/0.98 on summaries; in (b), 51/64 and 52/64 on paraphrases and 46/64 and 41/64 on summaries. The key-bearing evidence is the content a rewrite keeps; no semantic model is needed.
  • Setting (a) resembles retrieval-based detection (Krishna et al., NeurIPS 2023). Setting (b) needs no log of A's outputs (only its prompt), and it identifies the key rather than "our output". The framework converts either setting's success rate into certified information.

(continued in 2/3)

AuthorsOpenReview ↗

General response (2/3): which content carries the key, and re-watermarking

General response (2/3): which content carries the key, and re-watermarking

1b. Regeneration fidelity, tested (continuing §1). Of the 99 documents whose key-only regeneration diverged, 70 were generated on GPU types that are still available (A100: 63, H100: 7); regenerated in bf16 on their original GPU type, all 70 reproduce A's tokens exactly. The other 29 were generated on a GPU type that is no longer available and could not be tested. On the paired documents that now reproduce, (b) equals (a): paraphrase and copy are identified in 50 of 50, in both arms. Over all 64 paired documents, including the 14 untested ones, (b) rises to 62/64 and 63/64 for paraphrase (from 51/64 and 50/64) and 64/64 for copy. On the testable documents, regeneration fidelity, not key information lost in the rewrite, was the limiting factor.

2. A language task with a checkable nonzero floor (E1b). As PTC4 notes, the paper's factual fields are drawn independently of the key by design, so I(K1;T)=0I(K_1;T)=0. We now let the watermarked model choose the four fields itself, from the same menu of 132,000 tuples. Then TT is a function of key and prompt, and Theorem 2(iii) gives, per prompt, Rret≥I(K1;T∣X)=H(T∣X)>0R_{ret}\ge I(K_1;T\mid X)=H(T\mid X) > 0 for every rewrite that keeps the four fields. Ours keeps them in 56–58/64, and the last column certifies its retention directly. Rewriter B gets the prompt of the paper's full-context rewrite: "Preserve the input facts exactly and rewrite the narrative in different words".

arm (n=64)all 4 fields keptkey identified by exact field match, of 16 [95% CP]token detector @1%certified (nats)
plain56/6428/64 [0.314, 0.567]3/64≥ 0.29
race58/6430/64 [0.343, 0.598]1/64≥ 0.35
null (unrelated key's report)55/64 of own input6/641/64–

Identification is limited by ties, not by lost fields. The model chooses fields with little diversity: on average 7.8 distinct tuples per 16 keys, plug-in entropy 1.80 nats, and a decoy reproduces the true tuple 16.7% of the time. That low diversity also makes the floor H(T∣X)H(T\mid X) small here. The true key is in the matched set in every rewrite that keeps all four fields (56/64, 58/64); a decoy shares that set in 41/64 and 42/64.

2b. Floor zero vs floor positive on the same report format. Theorem 2 says what the best faithful rewrite can erase. On the paper's factual task the floor is I(K1;fields)=0I(K_1;\text{fields})=0, so complete removal is attainable without changing the fields. Task-only regeneration (§6.3) sees only the parsed fields, so by data processing its retention is at most the key information that parsing recovers, which is 0 if parsing always returns the specified fields; its four-field success is lower (27/64 and 24/64), partly because its input depends on parsing the source. Theorem 2 does not say that any particular full-context rewrite reaches the floor, and 1/64 token detections alone cannot show that it does: E1 shows that token evidence and key information come apart.

We therefore ran the key-only verifier of E1 on the factual reports themselves (Qwen3-4B, n=64, plain / race). Task-only regeneration gives 7/64 and 5/64 (chance 4/64): not distinguishable from chance. The full-context fact-preserving rewrite gives 35/64 and 36/64. Copies give 46/64 and 46/64; this is limited by regeneration, since all 18 misses are documents whose regenerated text does not reproduce the stored tokens (36/36 where it does). For contrast, the story paraphrase of E1 gives 51/64 and 50/64. The fact-preserving rewrite is above chance: it still carries key information through its wording. The zero floor is attainable (by conditional resampling, A.4), but this rewriter does not attain it; its 1/64 token detections show only that token-level evidence is gone.

3. Re-watermarking: equivalence rather than non-rejection (Wnkj-W2; LAUJ Strength 2). The prediction in §6.4 is equality in distribution (A.6), so the matching analysis is an equivalence test. In a post-hoc analysis of detection rates over the saved Table 2 pairs, pooled inherited-key detections are 438/1200 (plain) vs 437/1200 (race), a paired difference of −0.1 points with 90% CI [−1.3, +1.3]. This CI pools pairs as if independent, although the three operations share documents; resampling whole documents gives [−1.33, +1.08] points. Per cell, the rates are equivalent within ±10 points in 6/6 cells and within ±5 points in 4/6. These margins are informative where complete removal would exceed them, and there removal is excluded: Llama copy changes by +2.0 points [0.0, +4.5] against a 93.5-point drop, and Qwen paraphrase by +1.5 [−2.5, +5.5] against 11.5. The full table, the score-based analysis, and what each cell can and cannot detect are in our reply to Wnkj (2/2).

(continued in 3/3)

AuthorsOpenReview ↗

General response (3/3): one key model, theory additions, revisions

General response (3/3): one key model, theory additions, revisions

4. One key model (E3; LAUJ suggestion 2). The revised PDF will use K1K_1 uniform on 2632^{63} values throughout, so I(Y;K1)≤43.67I(Y;K_1)\le 43.67 nats.

  • The worst-case edit floor of Corollary 3 becomes vacuous after 2.57, 2.54 and 2.56 random substitutions (Llama-3.2-3B, Qwen3-4B, Qwen3-1.7B).
  • At the bracketing edit rates the detector still flags 0.946, 0.447/0.340 and 0.647/0.569 of outputs. Its own binary-KL diagnostic (nominal α=10−6\alpha=10^{-6}) is 12.5, 5.0/3.6 and 7.7/6.6 nats.
  • These are consistent. Corollary 3 bounds the worst faithful edit pattern, including redaction (Remark 3); random substitutions are far from worst case.
  • Rechecking Table 6 also uncovered a bug (the Llama column used the Qwen vocabulary size), which the revised PDF will correct (details in our reply to LAUJ, 3/3).

5. Theory additions (statements and proofs will be in [Rev: App. J]):

  • (a) Certified retention (a measurement corollary of the detector inequality): any rank or match test of the true key against MM decoys drawn from the key law certifies Rret≥d(TPR∥1/(M+1))R_{ret}\ge d(\mathrm{TPR}\Vert 1/(M{+}1)) when TPR≥1/(M+1)\mathrm{TPR}\ge 1/(M{+}1), averaged over prompts.
  • (b) Radioactive rewriter (Gu et al., 2024; Sander et al., 2024): Rret≤I(K1;θB)+I(Y;Y′∣θB)R_{ret}\le I(K_1;\theta_B)+I(Y;Y'\mid\theta_B). The floors are unchanged.
  • (c) A task with editing tolerance and a strictly positive floor: catalogue entities more than 2t2t apart, up to tt edits each, free wording. The shadow is the entity tuple, and the floor I(K1;entities)I(K_1;\text{entities}) is attained exactly.
  • (d) An explicit new-vs-organized contribution list.

6. Key-only verification on Llama (LAUJ-W2b/W2c). We ran E1 on Llama-3.2-3B, the model of Table 2's 109.21 vs 1.83 example, on its first 64 paired documents. This subset has its own token-detector means: copy 119.20 / 117.70, paraphrase 1.56 / 1.91 (plain / race; Table 2's numbers are over 200 documents). The token detector flags 60/64 / 62/64 copies and 1/64 / 4/64 paraphrases. The key-only verifier identifies the key in 40/64 / 39/64 copies and 36/64 / 35/64 paraphrases (chance 4/64), certifying ≥ 0.552 / 0.516 nats for paraphrase. Only 2/64 Llama regenerations reproduce the stored tokens, so, as in §1, these key-only numbers are limited by regeneration fidelity.

Revisions. The new experiments apply statements already in the submission (the §3 detector inequality, Remark 2, Theorem 2), and the new propositions are worked instances or extensions of its model; no theorem or proof of the submission changes. We will upload the revised PDF before the discussion closes, with changes marked in blue; the main text grows from 9 to 10 pages. [Rev: X] marks where each item will appear in that PDF, and we will post a note in this thread when it is up. Page numbers we quote refer to the submitted PDF. The revised PDF will contain:

  • New §6.6 with E1 (both verifier settings, the verifier hierarchy, Qwen and Llama), the regeneration test on the original GPU type, E1b and the floor-zero vs floor-positive contrast on the factual task [Rev: §6.6, App. J.1, L] (LAUJ-Q1/W2, PTC4-Q3, Wnkj-W1).
  • Remark 2 in the main text, with the certified-retention proposition [Rev: §3, App. J.1] (LAUJ-W2a).
  • Radioactive-rewriter paragraph and proposition [Rev: §3, App. J.2] (LAUJ suggestion 1).
  • Worked task relations with editing tolerance [Rev: §5, App. J.3] (PTC4-W1/Q1, Wnkj-W1).
  • Zhang et al. (2023) credited for the achievability half [Rev: §5] (LAUJ-W1b).
  • Contribution list, new vs organized [Rev: §1] (LAUJ-W1, PTC4-Q2).
  • Plain-language overview of §3 and a notation table [Rev: §3, App. A] (LAUJ, presentation).
  • §6.2 wording "consistent with, though not a test of, the caps" [Rev: §6.2] (LAUJ-W2c).
  • §6.4 wording and the post-hoc equivalence analysis, with a document-clustered pooled interval [Rev: §6.4, App. K] (Wnkj-W2).
  • Semantic-rewriting discussion [Rev: §6.6, §7.1] (Wnkj-W1).
  • Unified key model and corrected Table 6 [Rev: B.2, Table 6] (LAUJ suggestion 2).
  • Citations of Gu et al., Sander et al. and Krishna et al. [Rev: §2] (LAUJ suggestion 1, LAUJ-Q1).

Individual replies follow. We would be glad to clarify anything before the discussion ends.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.