{"id":"9029760d-c7d6-4eda-be7f-3a32916bb669","arxiv_id":"2505.08878","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For one-shot token watermarking with a min-entropy constraint, the authors derive a closed-form max-min detection rate and show that a correlated channel with balanced random partitions achieves it.","lead":"This paper analyzes a mathematical limit for watermarking text generated by large language models, focusing on how to hide one token at a time. It proposes a correlated channel watermark that keeps the text's probability distribution unchanged while still allowing a detector to recognize generated text with a provable detection rate.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's optimality relies on an unproven assertion that the balanced permutation class minimizes E[g(Q*_lambda,B_m)] for all k and lambda; Appendix A.9 only proves this for k=2 on restricted lambda intervals.","rationale":"The reader's weakest_assumption identifies exactly the gap I find most load-bearing: the appendix computes E[g] for the balanced class but does not establish that this class minimizes E[g] among all permutation classes. My reading of Appendix A.9 confirms that optimality is argued only for k=2 in two lambda intervals; the general k case and lambda < 1/3 are asserted without proof. Since Theorem 3 is the paper's central optimality result and the closed-form R*_d(lambda) depends on selecting the optimal class, this is not a cosmetic omission. I find no independent evidence that would rehabilitate the claim: there is no machine-checked proof, and the numerical plots in Figure 3 compare the balanced class against Bernoulli sampling, not against all possible classes. The zero-perception coupling construction, Proposition 2, and the fixed-partition detection formulas appear internally sound, and the empirical comparisons suggest the scheme works well, but those do not establish optimality. A conditional acceptance is appropriate: the authors should either supply a proof of balanced-class optimality for general k and lambda, or restate Theorem 3 as a characterization of the balanced-class scheme rather than the global max-min optimum. I do not see grounds for rejection, because the gap is fillable and the rest of the paper is informative, but the claim as printed overreaches its proof.","tokens_in":29462,"tokens_out":11727,"duration_ms":120099,"concrete_test":"For a small case, enumerate all integer compositions n_1+...+n_k=m with k=3, m=12, and for a grid of lambda values (e.g., lambda = 0.1, 0.2, 0.25, 0.4, 0.6), compute E[g(q*_lambda, B_m)] for each composition using the hypergeometric expression analogous to Eq. (48), summing over colors s rather than assuming equal n_s. If the balanced composition n_s = m/k does not give the minimum for every lambda, Theorem 3 is false as stated. If balanced is always minimal, the test still does not replace a proof, but it would indicate the missing step is likely true and the verdict can remain conditional pending a rigorous argument.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim in Theorem 3 is that the max-min detection probability R*_d(lambda) in Eq. (10) is achieved by uniform sampling over the balanced permutation class, where each of the k colors appears exactly m/k times. The proof in Appendix A.9 correctly reduces the optimization to minimizing E[g(q*_lambda, B_m)] over permutation classes (Eqs. 40-42), but it never proves that the balanced class is the minimizing class for general k and lambda. For k=2 the paper supplies explicit case analyses for 1/2 <= lambda < 1 and 1/3 <= lambda < 1/2 (Eqs. 58-61). For lambda < 1/3 and for all k > 2, no argument rules out a permutation class with unequal color counts. The worst-case distribution q*_lambda has t = floor(1/lambda) entries of mass lambda and one residual entry of mass 1 - t*lambda; the residual entry has different mass from the others, so symmetry does not force equal counts. If some non-balanced class yields a smaller E[g], then Eq. (10) is not the true max-min optimum, Corollary 1 is unsupported in general, and the 'optimal coupling' narrative of the paper loses its main theoretical footing. The empirical sections and the zero-perception construction may still stand, but the central optimality theorem is the load-bearing result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies one-shot LLM watermarking as a hypothesis-testing problem with side information. The authors formulate a max-min detection probability over randomized partitions of the vocabulary under a min-entropy constraint on the worst-case token distribution, propose the 'correlated channel' (CC) scheme, and claim a closed-form optimal detection rate R*_d(λ) given in Eq. (10), achieved by uniform sampling over the balanced permutation class. They also provide a simpler Bernoulli-sampling approximation with O(1/m) error, a sequential extension bound, and experiments on synthetic data and the WaterBench LLM benchmark. The paper is clearly written and includes code.","tokens_in":29717,"tokens_out":5288,"duration_ms":51107,"significance":"If the optimality theorem were fully proven, the paper would provide a fundamental single-token detection limit within the considered restricted test class and show that a zero-perception scheme can attain it. The formulation is clean, the max-min analysis is parameter-free (no fitted constants), and the closed-form expressions are useful for benchmarking practical watermarks. However, the central optimality claim currently rests on an unproven assertion about the balanced permutation class, so the theoretical contribution is not yet established at the level claimed.","major_comments":[{"comment":"The proof of Theorem 3 reduces the max-min problem to selecting a permutation class that minimizes E[g(q*_λ,B_m)] (Eq. (42)), but it computes E[g] only for the balanced class (Eq. (49)) and proves optimality of that class only for k=2 in the restricted ranges 1/2≤λ≤1 and 1/3≤λ<1/2 (Eqs. (58)-(61)). For k>2, and for λ<1/3 with k=2, no argument rules out a permutation class with unequal color counts yielding a smaller E[g]. Since Eq. (10) and Corollary 1 assert the balanced class achieves the optimum for all k and λ, this is a load-bearing gap: if a non-balanced class is better, R*_d(λ) in Eq. (10) is not the max-min detection rate and the optimality narrative of the central theorem is unsupported. The authors should either supply a complete proof of the balanced-class optimality (e.g., via a swap/majorization argument across color counts) or restrict the claim of the theorem accordingly.","section":"Appendix A.9, Eqs. (40)-(49)"},{"comment":"In the reduction following Eq. (42), the text states that it is sufficient to select a b uniformly over the permutation class 'that maximizes 1/|B_i| Σ_{b∈B_i} g(q*_λ,b)'. The min over w in Δ_K of a linear function in Eq. (42) is attained at the vertex corresponding to the class with the minimum average of g, not the maximum. If this is a typo, it should be corrected; as written, the proof appears to optimize the wrong objective when choosing the balanced class.","section":"Appendix A.9, Eq. (42)"}],"minor_comments":[{"comment":"The line 'As m→∞, R*_d(λ)→3/4 − m/4' should read '3/4 − λ/4'; the main text's subsequent statement that the penalty equals λ/4 is correct, so the appendix expression appears to be a typo.","section":"Appendix A.9, after Eq. (59)"},{"comment":"Sections A.11 and A.12 contain identical proofs of Proposition 4; one of the two copies should be removed.","section":"Appendix A.11 and A.12"},{"comment":"The caption says 'We compare C with two values of k and RG with two values of δ'; this should read 'We compare CC with two values of k'.","section":"Table 1 caption"},{"comment":"The notation for the optimal distribution P*_Bm and the distinction between 'uniform sampling over the balanced permutation class' and 'i.i.d. Bernoulli sampling' is introduced informally; a formal definition of the distribution underlying the expectation in Eq. (10) would improve readability.","section":"Section 3.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be a good fit for the journal if the authors can supply a complete proof of Theorem 3. The gap is in the core theorem, so a major revision is appropriate. I would also ask the authors to double-check the sign in the reduction in A.9 and the appendix typo in the limiting expression."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper has a real contribution in the zero-perception correlated-channel watermark and the fixed-partition detection formulas, but the headline Theorem 3—the closed-form max-min detection rate—rests on an unproven assertion that balanced permutation classes are optimal for all k and λ. I agree with the stress-test: the gap is real.\n\nWhat is actually new: the one-shot minimax formulation under a min-entropy constraint, the reduction of detection to a maximum-coupling problem between side information and partition output, the explicit balanced-class detection formula, and the O(1/m) approximation for i.i.d. Bernoulli sampling via de Finetti. The CC scheme itself is honestly attributed to [17], so the novelty is in the analysis, not the channel. The zero-perception construction is clean, and Proposition 3's closed form for Rd in terms of TV(PY, PS) is genuinely useful.\n\nThe main soft spot is Theorem 3. In Appendix A.9, the authors correctly reduce the max-min problem to minimizing an average of g over permutation classes, but they only compute the value for the balanced class and then assert it is the minimizer. The proof of optimality is a case analysis for k=2 on two λ intervals; for λ < 1/3 and for k > 2 there is no argument ruling out non-balanced classes. The residual mass 1 - tλ in the worst-case distribution breaks symmetry, so symmetry does not force balanced counts. This is load-bearing: Corollary 1 and the 'optimal coupling' framing depend on it. Either prove the balanced class minimizes that expectation (maybe via a Schur-convexity argument) or restate Theorem 3 as the detection rate for the balanced class, which is a valid lower bound.\n\nA second, smaller issue: Section 6 claims that with k=3 the CC detector 'matches or exceeds' red-green d=1 on all tasks. Table 1 shows the opposite on three datasets—Knowledge Understanding, Knowledge Memorization, and LCC. That empirical overstatement should be corrected.\n\nThe math is otherwise careful. There are no fitted parameters, the attribution to prior work is honest, and the code is released. I would not desk-reject it, but I would send it back with a request to either close the optimality gap or weaken the claim. It is a good candidate for a serious referee, especially for an information-theory or security venue.","headline":"The CC watermark and fixed-partition analysis are solid, but Theorem 3's balanced-class optimality is asserted, not proven, for general k and λ.","tokens_in":30256,"tokens_out":4718,"would_cite":true,"duration_ms":46409,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A17","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper derives a closed-form limit for single-token LLM watermark detection under worst-case token distributions, and proves that a zero-perception coupled random-partition scheme, the Correlated Channel watermark, attains it.","keywords":["LLM watermarking","one-shot watermarking","detection-perception trade-off","correlated channel watermark","min-entropy constraint","hypothesis testing with side information","randomized vocabulary partition","max-min detection"],"falsifier":"Take a small instance, say $m = 12$ tokens with $k = 3$ colors, pick $\\lambda$ strictly between $1/3$ and $1/2$, and compare the balanced class $(4,4,4)$ against unbalanced classes such as $(6,3,3)$ and $(8,2,2)$ by evaluating the formula (48) for $\\mathbb{E}[g(Q^*_\\lambda, B_m)]$ in each class; any unbalanced class with a smaller value refutes the optimality half of Theorem 3. The same verdict can be reached numerically by solving the max-min problem (6) directly over the finitely many extreme distributions $\\{Q : \\lVert Q\\rVert_\\infty \\le \\lambda\\}$ for small $m$ and $k$ and checking whether $R^*_d(\\lambda)$ is actually attained.","tokens_in":29247,"feed_emoji":"🎯","tokens_out":13159,"duration_ms":112106,"temperature":0.7,"pith_summary":"This paper aims to pin down the fundamental limit of single-token watermarking of large-language-model output: under a worst-case next-token distribution whose peak probability is at most $\\lambda$, the best detection rate for an indicator-style detector that sees only shared side information and a randomized vocabulary partition takes a closed form. The claimed optimum is attained by the Correlated Channel (CC) watermark, which couples uniform side information with a random balanced partition of the vocabulary and, averaged over the side information, leaves the next-token distribution unchanged (zero perception). If the claim holds, the per-token cap of about $3/4$ for binary side information is a hard limit rather than a defect of any particular scheme, and the small per-token gains compound exponentially across a generated sequence.","feed_headline":"One-token watermark limit found: worst-case detection rate in closed form","feed_subtitle":"A zero-perception 'correlated channel' scheme provably hits the 3/4 per-token worst-case cap with binary side info.","key_machinery":"The load-bearing object is the correlated channel: an optimal coupling between the uniform side information $S \\sim \\mathrm{Unif}([k])$ and the random partition variable $Y = f(X, B_m)$ that maximizes the acceptance probability $\\Pr(S = Y)$, constructed through the dual representation of total variation and reducing to a Z-channel when $k = 2$. Its job is to convert a public random assignment of colors to tokens ($B_m$, shared by watermarker and detector) into a private signal: the distribution of $Y$ is coupled to $S$ so that detector and watermarker agree on the color far more often than chance, while the marginal over tokens is untouched. This mechanism delivers zero perception ($\\mathbb{E}_S[Q_{X|S}] = Q_X$), collapses the detection probability to the closed form $R_d = 1 - \\frac{1}{2k} - \\frac{1}{2}\\mathrm{TV}(P_Y, P_S)$, and reduces the whole design problem to choosing the distribution of $B_m$; Theorem 3 then solves that choice in the max-min sense with the balanced permutation class.","core_discovery":"The paper's central claim is Theorem 3: for a vocabulary of $m$ tokens, side information uniform over $k$ values, and the min-entropy constraint $\\lVert Q_X\\rVert_\\infty \\le \\lambda$ (equivalently, $H_\\infty(Q_X) \\ge -\\log\\lambda$), the optimal max-min one-shot detection probability is $R^*_d(\\lambda) = 1 - \\frac{1}{2k} - \\frac{1}{4}\\mathbb{E}[g(Q^*_\\lambda, B_m)]$, where the expectation is taken over $B_m$ sampled uniformly from the balanced permutation class (each of the $k$ colors appears exactly $m/k$ times) and $Q^*_\\lambda$ is the extreme worst-case token distribution with $t = \\lfloor 1/\\lambda \\rfloor$ entries equal to $\\lambda$, one entry equal to $1-t\\lambda$, and the rest zero. The scheme that achieves this, the Correlated Channel watermark, couples the shared side information $S$ with the partition label $Y = f(X, B_m)$ so as to maximize $\\Pr(S = Y)$; for $k=2$ this optimal coupling is the Z-channel, and the detector simply announces 'watermarked' when $S = f(A, B_m)$. The paper further claims that this test is equivalent to the likelihood-ratio test at threshold $1$, that the scheme has zero perception in the sense $\\mathbb{E}_S[Q_{X|S}] = Q_X$, and that sampling the partition i.i.d. Bernoulli$(1/k)$ is near-optimal with approximation error at most $2k\\lceil 1/\\lambda \\rceil/m$.","pith_inferences":["A natural extension the paper does not work out is the asymmetric-prior regime $\\pi_0 \\ne \\pi_1$: Proposition 1 carries the factor $\\gamma = \\pi_1/\\pi_0$ into the detection expression, and a max-min version of the balanced-partition argument would plausibly give closed forms $R^*_d(\\lambda, \\gamma)$ interpolating between random guessing and the $\\gamma = 1$ values.","The construction reads as a zero-perception single-token embedding result: choosing $k$ colors effectively encodes $\\log_2 k$ bits of shared randomness per token, so the balanced-class optimization doubles as a capacity statement for invisible single-token watermarks, a connection the paper leaves implicit.","Because the worst-case distributions $Q^*_\\lambda$ are exactly the extreme points of the min-entropy polytope, Theorem 3 could serve as the atomic step of a fully adversarial sequential analysis in which the adversary picks the worst distribution at every position; Proposition 4 already moves that way under an i.i.d. assumption."],"forward_implications":["With binary side information ($k=2$) the worst-case single-token detection probability is capped at $3/4$ no matter how the vocabulary is partitioned, so any practical detector must spread its gains across many tokens rather than chase a higher per-token rate.","Because the approximation error of i.i.d. Bernoulli$(1/k)$ sampling is $O(1/m)$, real vocabularies of roughly 100,000 tokens can sample partitions simply and stay within a negligible distance of the balanced-class optimum.","The zero-perception property means detection power is bought without shifting the expected next-token distribution, which the paper's language-model experiments show as lower perplexity than the tilting red-green scheme at comparable or better detection statistics.","The sequential extension has a binomial test statistic with known null probability $1/k$ per token, so false-positive rates can be controlled without any access to the underlying token distribution.","Larger $k$ raises the single-token ceiling, but the gain diminishes as $k$ grows and depends on $m$ being divisible by $k$; when it is not, the balanced class does not exist and detection degrades."],"supporting_citations":[{"why":"Defines the red-green watermark, the distortion-based baseline the CC scheme is compared against in both synthetic and LLM experiments.","marker":"[5]"},{"why":"Introduces error-correcting-code watermarks built on correlated channels, the structure the CC construction uses and extends with optimal one-shot randomization.","marker":"[17]"},{"why":"Supplies the inf-representation of total variation used in Proposition 2 to construct the optimal coupling between side information and partition label.","marker":"[40]"},{"why":"Provides the finite-exchangeable-sequences (de Finetti) bound that yields the order-1/m approximation error for Bernoulli partition sampling in Theorem 4.","marker":"[42]"},{"why":"Analyzes optimal statistical watermarking with known token distribution, the contrast that motivates the paper's unknown-distribution max-min setting.","marker":"[33]"},{"why":"Characterizes universal Type-II error for token-level watermark detectors, a competing objective the paper distinguishes from worst-case mean detection.","marker":"[10]"}],"fun_headline_variants":["Optimal watermark coupling found for one-shot LLM text","Closed-form detection rate for worst-case LLM watermark","Z-channel coupling hits worst-case watermark detection limit","Min-entropy-constrained watermarking: optimal coupling solved","Correlated channel watermark provably optimal under min-entropy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The closed-form optimum assumes that for every number of colors $k$ and every allowed peak probability $\\lambda$, the best choice of partition randomness is the balanced permutation class in which each color appears exactly $m/k$ times; the appendix establishes this optimality only for $k = 2$ over restricted ranges of $\\lambda$, so for general $k$ an unbalanced permutation class could in principle perform better, and that would invalidate the claimed closed-form maximum.","fun_headline_variants_meta":{"raw":{"variants":["Optimal watermark coupling found for one-shot LLM text","Closed-form detection rate for worst-case LLM watermark","Z-channel coupling hits worst-case watermark detection limit","Min-entropy-constrained watermarking: optimal coupling solved","Correlated channel watermark provably optimal under min-entropy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000204,"raw_usage":{"total_tokens":1471,"prompt_tokens":1112,"completion_tokens":359,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":728,"completion_tokens_details":{"reasoning_tokens":281}},"tokens_in":728,"tokens_out":359,"duration_ms":3823,"temperature":1.0,"reasoning_tokens":281,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:47:00.349038+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small instance, say $m = 12$ tokens with $k = 3$ colors, pick $\\lambda$ strictly between $1/3$ and $1/2$, and compare the balanced class $(4,4,4)$ against unbalanced classes such as $(6,3,3)$ and $(8,2,2)$ by evaluating the formula (48) for $\\mathbb{E}[g(Q^*_\\lambda, B_m)]$ in each class; any unbalanced class with a smaller value refutes the optimality half of Theorem 3. The same verdict can be reached numerically by solving the max-min problem (6) directly over the finitely many extreme distributions $\\{Q : \\lVert Q\\rVert_\\infty \\le \\lambda\\}$ for small $m$ and $k$ and checking whether $R^*_d(\\lambda)$ is actually attained.","supporting_citations":[{"cited_title":"Information Theory: From Coding to Learning","cited_arxiv_id":null,"evidence_quote":"Supplies the inf-representation of total variation used in Proposition 2 to construct the optimal coupling between side information and partition label."},{"cited_title":"Finite exchangeable sequences","cited_arxiv_id":null,"evidence_quote":"Provides the finite-exchangeable-sequences (de Finetti) bound that yields the order-1/m approximation error for Bernoulli partition sampling in Theorem 4."}],"review_version":1}