{"id":"6eb0eff4-34d7-4cf9-bc48-cb30032a26dc","arxiv_id":"2506.15975","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Using the same watermark statistic for both detection and user ID inflates false positives as user count grows; Dual Watermarking separates the two and reduces false positives.","lead":"This paper shows that when one watermark is used both to detect AI-generated text and to identify which user generated it, the chance of falsely accusing ordinary text keeps growing as the number of users grows. It proposes splitting the watermark into separate detection and identification parts, which cuts false accusations while staying accurate.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Fixed-FNR claim is not derived and experiments do not match it; reported FPR advantage may be threshold artifact.","rationale":"The reader's weakest_assumption names the random-oracle independence assumption first and the missing fixed-FNR derivation second. I agree with the second part and treat it as the load-bearing concern: the paper's theorems compare fixed-threshold upper bounds, not matched-FNR operating points, so the quantitative claim that FKE's FPR grows as FNR is held constant is not actually proven. The experiments compound this by tuning thresholds per watermark ratio to maximize accuracy rather than fixing FNR, so the reported FPR gap may reflect threshold placement rather than a property of the method. I do not elevate the random-oracle assumption to the main concern because the qualitative max-over-K false-positive growth is robust to dependence: the maximum of K score statistics shifts upward under mild conditions even if the scores are not independent, and the experimental results would still be informative. The proposed concrete test, comparing FKE, DW, and HDW at matched FNR across K, directly settles whether the central claim holds. Since the paper already received a CONDITIONAL verdict and this concern is addressable by rerunning the evaluation at matched operating points, I do not recommend changing the verdict.","tokens_in":26354,"tokens_out":10773,"duration_ms":120296,"concrete_test":"On the evaluation set, for K=20,50,100,200,500,1000,2000, tune tau_k (and tau_d for DW/HDW) on the development set to achieve a fixed FNR (e.g., 1% and 5%) on watermarked text, then report FPR and TPR on the test set at those operating points; also compute ROC AUC for each method. Additionally, replace the Chernoff bounds in Figure 1 with exact Gamma tail probabilities and plot FKE and DW exact FPR at the same FNR. If FKE's matched-FNR FPR does not increase with K, or DW does not dominate FKE, the central claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that FKE's false positive rate grows with key capacity \"provided the False Negative Ratio is held constant\" (Sec. 1), and that DW/HDW reduce FPR at any FNR. No theorem establishes this. Theorem 1 bounds Pr(max_xi S_k(xi) >= tau_k) for a fixed tau_k; Theorem 2 bounds DW's FPR for a fixed tau_d; Theorem 3 multiplies the two. None of these relate thresholds across methods at matched FNR, and the bounds are Chernoff upper bounds that are extremely loose in the plotted regime (e.g., for T'=100, tau_d=1.6, the bound is about 0.33 while the true Gamma tail is negligible). Comparing upper bounds therefore does not show DW dominates FKE at equal FNR. The experiments also do not fill the gap: thresholds are grid-searched per watermark ratio to maximize Accu-I (App. A.10), not set to hold FNR constant. At a fixed FPR operating point, a detector would raise tau_k with log K; whether FPR then grows with K at fixed FNR is exactly the unproven claim. If at matched FNR FKE's FPR is flat or lower than DW's, the proposed advantage is a threshold artifact.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies LLM watermarking schemes that simultaneously support detection (is this text machine-generated?) and identification (which user/key generated it?). It identifies a 'false detection problem': when the same per-token scores are reused both to embed a user key and to decide whether text is watermarked (termed Full Key Encoding, FKE), the maximum over K candidate keys makes unwatermarked text increasingly likely to exceed a fixed detection threshold as K grows. The paper formalizes this via Chernoff-style false-positive bounds (Theorems 1–3), proposes Dual Watermarking (DW) and Hybrid Dual Watermarking (HDW), which allocate separate token subsets to detection and identification statistics, and reports experiments on Guanaco-7b/Alpaca with both distribution-based and dictionary-based backbones showing lower FPR and comparable accuracy for DW/HDW relative to FKE.","tokens_in":26562,"tokens_out":7261,"duration_ms":77800,"significance":"If the central claim holds, this is a practically important observation for multi-user LLM watermarking: a naive combination of detection and identification can degrade detection reliability as the user base grows, and a simple token-splitting fix can mitigate it. The theoretical analysis is largely parameter-free, built on standard exponential/Gamma facts and a random-oracle view of the hash function, and the experiments include a dev/test split, key-capacity scaling, robustness attacks, and domain-specific datasets. The main gap is that the paper's headline claim about behavior 'at constant FNR' is not actually established: Theorems 1–3 bound FPR at fixed thresholds, and the experiments tune thresholds to maximize accuracy rather than to hold FNR fixed. The contribution is therefore plausible and likely correct in spirit, but the current manuscript overstates what is proven and what the experiments demonstrate.","major_comments":[{"comment":"The motivating claim is that FKE's false positive rate grows with key capacity 'provided the False Negative Ratio is held constant,' but Theorem 1 bounds the false positive probability only for a fixed threshold tau_k. No theorem or corollary analyzes how tau_k must move with K to keep FNR constant, nor proves that the FPR growth survives at matched FNR. (A short argument would help: for watermarked text the statistic is the maximum over the correct key and K-1 wrong keys, so a threshold calibrated at K=1 gives a constant FNR bound for all K; the paper should state this explicitly and then verify that the FPR growth at that fixed threshold is the relevant comparison.) As written, the theory does not support the phrase 'at any FNR' used in the introduction and in Section 4.1.","section":"Section 1 and Section 4.1, Theorem 1"},{"comment":"The comparison between FKE and DW/HDW is made by plotting or tabulating the Chernoff upper bounds at the same numerical threshold (tau=1.6). Upper bounds that are very loose in the displayed regime (e.g., the DW bound is around 0.33 at T=100 while the true Gamma tail is negligible) do not establish that DW's actual FPR is lower than FKE's at equal FNR. The plots demonstrate dominance of one bound over another, not dominance of the actual false positive rates under matched operating points. The paper should either derive a comparison at matched FNR or add experiments that calibrate thresholds on watermarked text to a target FNR and then measure FPR on unwatermarked text.","section":"Figure 1, Table 4, Section A.9"},{"comment":"The key-capacity experiment does not state whether the same thresholds are used across all K or whether thresholds are retuned per K (or per watermark ratio, as described in Appendix A.10). If thresholds are retuned to maximize Accu-I at each K, the observed FPR increase for FKE (0.178 at K=20 to 0.295 at K=2000) could be partly a threshold-artifact rather than the K-dependent phenomenon of Theorem 1. The authors should report the threshold-setting procedure and, ideally, show FPR as a function of K with fixed thresholds and with thresholds calibrated to a constant FNR. Without this, the empirical claim that DW/HDW outperform FKE 'at any FNR' is not directly supported.","section":"Section 5.2, Table 2"}],"minor_comments":[{"comment":"There are numerous typos and inconsistent labels: 'a analysis' (Conclusion), 'origional' and 'walues' (Appendix A.8 and Figure 2 caption), 'DWI' vs 'DW' in tables and figures, and 'Multibit' as both 'Multi-bit' and 'Multibit'. A careful proofread is needed.","section":"Throughout"},{"comment":"The y-axis labels in Figures 14 and 15 say 'FPR' but the plotted values (roughly 0.75–0.98) look like accuracy values; the captions say 'scores' without specifying the metric. Please fix the labels or the captions.","section":"Figures 14 and 15"},{"comment":"The paper repeatedly invokes FNR as the quantity held constant in the motivating claim, but FNR is never reported in any experiment. Given the central role of the matched-FNR claim, reporting FNR (or the accuracy on watermarked-only subsets) would substantially clarify the empirical picture.","section":"Section 5"},{"comment":"The statement that the hash-based encoding is 'naturally robust to deletion or insertion' is too strong, since changing surrounding tokens changes subsequent hash keys; the insertion/deletion experiments actually show degradation. Please soften the claim or qualify it as robustness to small local edits.","section":"Section 3.3"},{"comment":"The independence between S_d and max_xi S_k(xi) used in the proof is asserted without explicitly stating the conditioning on the observed token sequence (which fixes the indicator values d_i). For unwatermarked text this independence follows from the random-oracle assumption, but the theorem statement should state the assumption that the token subsets are fixed or condition on d_i.","section":"Section 4.1, Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"The core observation—that taking a maximum over K keys inflates the null distribution and hence the false positive rate—is correct and potentially valuable. My main concern is that the paper's theoretical results and experiments do not currently match the 'constant FNR' claim, and the comparison of loose upper bounds at arbitrary thresholds is not a substitute. I believe this is fixable within the manuscript's scope by adding a matched-FNR analysis and experiments, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zihao and Chris have a real observation: if the same score is used both to detect watermarks and to identify which user key produced them, the max-over-K operation inflates the false positive rate as the number of users grows. That is true, and it has not been clearly stated in the watermarking literature. The fix, reserving separate token pools for detection and identification, is simple and plausible, and the key-capacity experiment (Table 2) shows FKE's FPR rising with K while HDW's stays roughly flat. The theory is elementary but correct under the random-oracle hash assumption: null scores are Gamma, so the maximum over K keys shifts upward. The paper is honest about its setup and gives useful bounds, even though the bounds are loose Chernoff tails. Where I part company is the constant-FNR claim. The introduction says the false detection problem manifests 'provided the False Negative Ratio is held constant.' The theorems do not establish that. Theorem 1 fixes the threshold and shows the FPR bound grows with K. That is a different statement. To keep FNR fixed, the threshold would have to move with K, and the paper never analyzes that offset. The experiments do not fill the gap either: thresholds are selected to maximize accuracy on a dev set, not to match FNR across methods. So the reported FPR advantage of DW/HDW over FKE could partly be a threshold artifact. I do not think the central idea is wrong; the key-capacity trend is visible even without matched FNR, but the strong claim needs either a proof or a matched-operating-point experiment. Two smaller issues. First, the empirical section does not release code or data, which hurts reproducibility. Second, the PKE baseline is underpowered because it throws away half the tokens, so the DW-vs-PKE comparison does not isolate the effect of avoiding the max operation. The paper should also acknowledge that the random-oracle assumption is an idealization; a non-uniform hash could weaken the bounds. Bottom line: this is a useful, honest paper that pinpoints a real failure mode and offers a plausible remedy. It deserves peer review, with the expectation that the authors tighten the constant-FNR claim and add a matched-FNR comparison. Researchers working on multi-user LLM watermarking should read it, and I would cite it for the false detection problem.","headline":"A real, previously under-stated failure mode with a clean fix, but the strong constant-FNR claim needs proof or a matched-operating-point experiment.","tokens_in":730,"tokens_out":755,"would_cite":true,"duration_ms":43513,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that watermarking schemes that reuse the same statistics for detecting AI-generated text and identifying the user become systematically worse at avoiding false positives as the supported user count grows, and that…","keywords":["LLM watermarking","false detection problem","dual watermark","identification watermark","false positive rate","Gumbel-Max trick","key capacity","text provenance"],"falsifier":"Take a corpus of human-written text, run the FKE detector with $K=1$ and $K=2000$ at a threshold fixed by a chosen false-negative rate, and measure the false-positive rate on the corpus; if the FPR does not rise with $K$, the theorem's mechanism is not operating, and the same experiment with a hash family known to produce correlated scores across keys would test whether the random-oracle assumption is load-bearing.","tokens_in":26115,"feed_emoji":"🛡️","tokens_out":6165,"duration_ms":54383,"temperature":0.7,"pith_summary":"The paper targets a reliability failure in LLM watermarking: when one scheme both detects machine-generated text and identifies which user's key generated it, the detection decision is made by taking the maximum score over all candidate keys. The authors prove that as the number of keys $K$ grows, unwatermarked text is increasingly likely to clear the detection threshold; their bound is $\\Pr(\\max_{\\xi} S_k(\\xi) \\ge \\tau_k) \\le 1 - (1 - \\exp(T(\\tau_k(1/e - 1) + 1)))^K$, which rises with $K$. They attribute this to reusing the identification statistic for detection, and propose Dual Watermark (DW), which saves a separate set of tokens purely for detection, and Hybrid Dual Watermark (HDW), which uses both signals. On distribution-based and dictionary-based backbones, the proposed schemes keep detection accuracy while cutting the false positive ratio substantially, matching the theoretical bounds. A reader should care because false positives accuse humans of being machines, and the failure only gets worse as a service scales to more users.","feed_headline":"False watermark alarms grow with user keys; splitting signals fixes it","feed_subtitle":"A theoretical bound shows false positives rise with user count; a dual-token watermark keeps detection reliable at scale.","key_machinery":"The object that carries the argument is the score statistic $S_k(\\xi) = -\\frac{1}{T}\\sum_i \\ln(1 - u_{i,x_i}(\\xi))$, computed from uniform random variables recovered by hashing preceding tokens together with a candidate key; for unwatermarked text each term is exponential with rate 1, so $S_k$ is Gamma$(T, 1/T)$, and taking the maximum over $K$ keys inflates the tail. The proposed machinery is a hash-based decision function $d_i$ that deterministically labels each token as either a detection token or an identification token, so the detection score $S_d$ and the key scores $S_k(\\xi)$ are built from disjoint token sets; the Gumbel-Max equivalence of the underlying sampler justifies treating the recovered variables as independent uniform draws under the null. The key work of this machinery is to decouple the maximum over keys from the detection decision, which is what makes the false-positive bound independent of $K$.","core_discovery":"The central claim is that Full Key Encoding (FKE)—the standard way of combining detection and identification, where every token encodes the key and the maximum key score is thresholded—has a false-positive probability that grows with key capacity $K$. Concretely, the paper proves $$\\Pr\\left(\\max_{\\xi} S_k(\\xi) \\ge \\tau_k\\right) \\le 1 - \\left(1 - \\exp\\left(T\\left(\\tau_k\\left(\\frac{1}{e}-1\\right)+1\\right)\\right)\\right)^{K},$$ so for fixed text length $T$ and threshold $\\tau_k$, the false-alarm risk rises as $K$ grows; the same qualitative failure appears in dictionary-based multi-bit watermarking, where the maximum over blocks turns a binomial statistic into a Gumbel one. The proposed Dual Watermark instead allocates a fraction $r_d$ of tokens to a detection-only score and the rest to key identification, making the false-positive bound independent of $K$, while Hybrid Dual Watermark additionally requires the key-score maximum to clear a threshold, giving a bound that dominates FKE for $K > 1$. Experiments across 20 to 2000 keys show FKE's false positive ratio rising with $K$ while HDW stays roughly flat.","pith_inferences":["Theorems 1-3 bound a fixed-threshold false-positive rate; the paper's motivating 'constant false-negative ratio' claim would require extending the analysis to thresholds that adapt during tuning, which the appendix shows depends on the fraction of watermarked text in the dataset.","The same decoupling principle—never let a maximum over a growing candidate set feed a detection decision—likely applies beyond watermarks to plagiarism screening, biometric matching, and other forensic tasks where 'is this signal present?' is answered by searching a large database.","A natural next step, not explored in the paper, is to make $r_d$, the detection-token fraction, adapt to text length and key capacity; the appendix's numerical bound (DW wins for $K$ above roughly 15-115 depending on $r_d$ and $T$) suggests a simple rule for when the dual split pays off.","Tests with concrete hash families would map how much slack the random-oracle assumption provides: if real hashes introduce correlations across keys, the $K$-growth of FKE's false positives and the $K$-independence of DW could both be weaker than the bounds claim."],"forward_implications":["At a fixed detection threshold, the false-positive probability for full-key encoding grows with the supported user count, so a service that scales users without redesigning its watermark will see more human-written text flagged as machine-generated.","Dual Watermark's false-positive bound does not depend on $K$, so detection reliability can stay stable as the user base grows, at the cost of a slight drop in identification accuracy because fewer tokens carry the key.","Hybrid Dual Watermark dominates full-key encoding whenever $K > 1$ and coincides with it when $K = 1$, giving a strict improvement in the false-positive regime with no loss of identification accuracy in the comparison setting.","Dictionary-based multi-bit watermarking also exhibits the false-detection problem: the max over blocks shifts the statistic toward a Gumbel distribution, so its false-positive rate grows with message length; applying the dual-token split restores stability."],"supporting_citations":[{"why":"Supplies the distribution-based FKE backbone: Gumbel-Max watermarking with per-key score statistics, which the paper extends and analyzes.","marker":"[Fernandez et al., 2023]"},{"why":"The dictionary-based multi-bit backbone whose max-over-blocks statistic the paper shows follows a Gumbel distribution.","marker":"[Yoo et al., 2023a]"},{"why":"Introduces the Gumbel-trick watermark whose score construction and Gumbel-Max equivalence underpin Theorems 1-3.","marker":"[Aaronson and Kirchner, 2023]"},{"why":"Red-green list dictionary watermarking whose multi-bit extension is the basis of the dictionary-based analysis.","marker":"[Kirchenbauer et al., 2023b]"},{"why":"Cited for the claim that false positives in watermark detection are considerably more critical than false negatives.","marker":"[Liu et al., 2023a]"},{"why":"Used alongside Liu et al. to justify why the false-detection problem matters in practice.","marker":"[Giboulot and Teddy, 2024]"},{"why":"Supplies the extreme-value distribution theory used to identify the Gumbel behavior of max statistics.","marker":"[Gumbel, 1954]"}],"fun_headline_variants":["False watermark alarms scale with users; dual encoding stops it","Dual watermark keeps false positives flat as user count grows","Splitting detection and ID watermarks kills false alarms","Capacity breeds false watermark alarms; split keys decouple"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bounds assume the hash function behaves like a random oracle, so that for unwatermarked text the recovered scores are independent uniform random variables across every candidate key and across the two token partitions; if real hashes introduce correlations, the $K$-growth of FKE's false positives and the $K$-independence of DW could both be weaker than claimed.","fun_headline_variants_meta":{"raw":{"variants":["False watermark alarms scale with users; dual encoding stops it","Dual watermark keeps false positives flat as user count grows","Splitting detection and ID watermarks kills false alarms","Capacity breeds false watermark alarms; split keys decouple"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001348,"raw_usage":{"total_tokens":5470,"prompt_tokens":937,"completion_tokens":4533,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":4467}},"tokens_in":553,"tokens_out":4533,"duration_ms":32337,"temperature":1.0,"reasoning_tokens":4467,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:30:06.347144+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a corpus of human-written text, run the FKE detector with $K=1$ and $K=2000$ at a threshold fixed by a chosen false-negative rate, and measure the false-positive rate on the corpus; if the FPR does not rise with $K$, the theorem's mechanism is not operating, and the same experiment with a hash family known to produce correlated scores across keys would test whether the random-oracle assumption is load-bearing.","supporting_citations":[],"review_version":1}