{"id":"746a3221-f81a-44fa-a31e-82102af54c89","arxiv_id":"2506.05502","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A message-dependent token-reweighting method embeds multi-bit provenance data into LLM output while preserving the expected output distribution.","lead":"StealthInk hides a multi-bit watermark (such as a user ID, timestamp, or model ID) inside text generated by a large language model, while keeping the text's statistical distribution unchanged on average. It could let providers trace AI-generated text to a specific user without degrading text quality or making the watermark easy to forge.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.3 assumes independent ciphers across queries; Algorithm 1 resets history per query, so repeated same-prompt, same-message queries reuse the same first-token permutation, and the timestamp defense is unproven and likely fails at query counts far below the 100,000 claimed.","rationale":"The reader's weakest_assumption identifies exactly this gap: K-shot stealthiness requires independent ciphers across queries, and StealthInk does not enforce it. I agree. The paper's own Appendix F admits the distortion for same-time queries and defends only by an untested practical-impossibility claim. The proof of Theorem 4.4 (per-token unbiasedness) is recoverable despite a flawed uniform-x_i statement, because the required property is symmetry of x_i about (1-p_i)/2, which holds for uniformly random permutations; so the core single-token construction is not the weakest point. The load-bearing weakness is the K-shot theorem's hypothesis versus the algorithm's per-query history. This is addressable by either maintaining a global history (which the paper rejects due to key exhaustion) or by proving a K-shot guarantee that incorporates message randomness with a quantitative bound on the number of same-timestamp queries an attacker needs. Until then, the advertised 'provably stealthy' claim is overstated. The reader's CONDITIONAL verdict remains appropriate; no verdict change is needed.","tokens_in":26614,"tokens_out":13432,"duration_ms":152907,"concrete_test":"Fix a prompt, a user ID, and a timestamp so the embedded message M is constant. Generate N responses (e.g., N=100, 500, 2000) from the watermarked LLM following Algorithm 1, and record first-token frequencies. Estimate P_O for the same prompt from many unwatermarked generations. Run a chi-square goodness-of-fit test (or likelihood-ratio test) comparing the observed first-token counts to P_O. If the test rejects at N=500 or N=2000, the same-prompt same-message distribution is detectably distorted, contradicting K-shot stealthiness at query counts far below 100,000. As a control, repeat with M varying across queries (different timestamps); the test should not reject.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central formal guarantee is Theorem 4.3, which states that K-shot stealthiness holds if the sequence of ciphers θ^k is independent across queries. Algorithm 1 maintains hist only within a single response; when the same prompt is submitted again, the first texture key (derived from the prompt's last h tokens) is identical, so the first-token permutation is identical whenever the embedded message M is the same. Thus the independence assumption is violated deterministically. The paper's remedy is to randomize M via timestamp bits (Section 4.2, Appendix F), but Theorem 4.3's proof at Eq. (8) uses E_{θ^k}[P_W^{M^k}] = P_O for a fixed message; it does not use E_{M^k}[P_W^{M^k}] for a fixed θ^k, and in general E_M[P_W^M(·|θ)] ≠ P_O for a fixed permutation. Appendix F concedes that if queries share the same timestamp, the first-token distribution is distorted, calling a 100,000-query attack 'practically impossible.' This quantitative claim is untested: with m=1 the red list has probability mass ~1/2, so even a few hundred samples from the same-prompt, same-message distribution will show zero counts for tokens that P_O says are probable, and a goodness-of-fit test against the known P_O should reject. The K-shot stealthiness guarantee therefore does not hold for the deployed algorithm as stated; the formal claim is conditional on an idealized independence the system does not provide.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"StealthInk proposes a multi-bit watermarking scheme for LLMs that reweights token probabilities based on a vocabulary permutation, a message-dependent red list, and a doubling operation on a complementary interval. The central formal claims are (i) per-token unbiasedness: for each random permutation, the expected watermarked token distribution equals the original model's distribution (Theorem 4.4), and (ii) K-shot stealthiness: over multiple prompt-response pairs with independent ciphers, the joint watermarked distribution matches the original (Theorem 4.3). The paper also derives a relation between minimum detectable text length and equal error rate, and reports experiments on text quality, spoofing resistance, detectability, and robustness against copy-paste and paraphrasing attacks. The empirical results show that StealthInk achieves AUC around 0.98 and bit accuracy around 0.92 for 24-bit messages in 300 tokens, while maintaining low perplexity relative to some prior multi-bit schemes.","tokens_in":26948,"tokens_out":9278,"duration_ms":107783,"significance":"If the central claims held in their full generality, StealthInk would be a valuable contribution: it combines multi-bit embedding with a distribution-preserving reweighting rule, and it provides an explicit lower-bound analysis relating capacity to the equal error rate. The per-token unbiasedness proof via the symmetry of the intervals A and B is elegant and appears to be exact rather than dependent on the Gaussian approximation used elsewhere. The empirical study is reasonably broad, covering text quality, detection, spoofing, and editing attacks, and the paper honestly discusses limitations such as low entropy and paraphrasing robustness. However, the load-bearing K-shot stealthiness guarantee is proven only under an independence assumption that the deployed encoder violates, and the paper's practical defense against the resulting attack is an unproven assertion about attacker timing. These gaps currently prevent the paper from substantiating its advertised 'preserves the original text distribution' property over repeated queries.","major_comments":[{"comment":"The security assertion in Section 4.2 and Appendix F that an attacker would need about 100,000 same-prompt, same-timestamp queries to detect the first-token distortion is not supported by any analysis. With m=1, the red list has probability mass roughly 1/2 under P_O; a goodness-of-fit test comparing the empirical first-token distribution to the known P_O over a few hundred repeated queries should already reject, because half the vocabulary is assigned zero probability. The paper provides no sample-complexity bound or experiment for this scenario, and Appendix F itself concedes that if queries share the same timestamp, 'a bunch of tokens' probabilities are 0.' Thus the 'practically impossible' claim is an unsupported quantitative assertion, and the gap between the theorem's assumption and the algorithm's behavior cannot be dismissed as an unrealistic attack.","section":"Section 4.2 / Algorithm 1 vs. Theorem 4.3"}],"minor_comments":[{"comment":"In the H=2 row for the Dolly dataset, the AUC value '09491' appears to be a typo for '0.9491'.","section":"Table 3"},{"comment":"The right-hand side of Eq. (1) is written as a product over P_O(x^k | a^k), but the left-hand side is an expectation of the joint watermarked distribution; the notation would be clearer if the definition explicitly stated that the expectation equals the product of the unwatermarked marginals.","section":"Definition 4.2"},{"comment":"The discussion of the lower PPL for StealthInk in Table 4 attributes the difference to filtering of low-probability tokens and to outliers in the non-watermarked texts. The statement that 'some non-watermarked responses exhibit extremely high PPL ... which raises their median' is statistically incorrect, as the median is insensitive to outliers; the authors should provide a more careful finite-sample explanation or show statistical significance for the PPL convergence in Appendix J.","section":"Section 6.2 / Table 4"},{"comment":"The sentence 'the same texture key should not repeat for watermarking' is potentially misleading because hist is per query; the text should clarify that this rule applies only within a single query attempt, which is the cause of the K-shot independence gap discussed above.","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid piece of engineering with an elegant per-token unbiasedness argument, but the central K-shot stealthiness claim is not supported for the algorithm as implemented. The authors should either modify Algorithm 1 to ensure genuinely independent ciphers across queries (e.g., by incorporating a per-query nonce into the PRF seed, with the nonce recoverable by the detector through the embedded message), or they must weaken the formal claims in the abstract and Section 4 to reflect the conditional nature of the guarantee. The Appendix F defense should be replaced or supplemented with a rigorous sample-complexity analysis if the same-prompt repeated-query security is to be claimed. I would not recommend rejection, because the per-token unbiasedness result and the empirical comparisons are valuable and the K-shot gap appears fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"StealthInk is a serious attempt to get multi-bit payloads into the stealthy watermarking framework. The core construction—message-dependent red-list reweighting with per-token unbiasedness in expectation—is new and cleanly proved (Theorem 4.4). The experiments are reasonably thorough, the comparison to MPAC and Qu et al. is fair, and the theoretical minimum-length analysis is a useful addition.\n\nThe main soft spot is the K-shot stealthiness claim. Theorem 4.3 requires independent ciphers across queries, but Algorithm 1 resets its history per response. The same prompt with the same message will reuse the same first-token permutation, so the independence assumption is violated deterministically. The paper's answer is to randomize the message with timestamp bits, but that defense is not proved, and the \"100,000 queries at the same millisecond is practically impossible\" claim is hand-wavy. With m=1, the red list covers half the probability mass, so a few hundred same-time queries would suffice to detect zero-count tokens. This is a real gap between the formal guarantee and the deployed algorithm. The paper does flag it in Appendix F, which is honest, but it doesn't fix the theorem.\n\nA second, softer issue is the PPL discrepancy. The paper argues that the lower PPL of watermarked text is finite-sample variance and converges away. The tables do show the gap shrinking with longer texts, so it may not be a fundamental violation, but the explanation is not fully convincing, and a statistical test on PPL could be a detection vector not addressed in the experiments.\n\nAlso, no code is provided and the tables lack error bars, which makes it harder to assess the robustness of the empirical claims.\n\nAll that said, this is a solid paper for the watermarking subfield. The per-token unbiasedness machinery is genuinely new, and the experimental setup is careful. The K-shot gap is addressable—either by proving the timestamp-randomized version or by weakening the claim to match the algorithm. I'd send it to peer review, with a request to tighten the stealthiness theorem and provide code.","headline":"Genuinely new multi-bit extension of stealthy watermarking, but the K-shot stealthiness guarantee is conditional on independence the algorithm doesn't provide.","tokens_in":27490,"tokens_out":7426,"would_cite":true,"duration_ms":70985,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"StealthInk claims to embed multi-bit provenance messages into LLM-generated text while provably preserving the original token distribution, carrying 24-bit payloads with about 92% bit accuracy in 300 tokens and resisting watermark-forgery…","keywords":["LLM watermarking","multi-bit watermark","stealthy or unbiased watermark","text provenance","distribution-preserving reweighting","watermark spoofing","AI-generated text detection","red-list token reweighting"],"falsifier":"Set the timestamp and user metadata bits to a fixed value, submit the same prompt to the watermarked model tens of thousands of times, and compare the empirical first-token distribution with the unwatermarked model's first-token distribution for that prompt. If the distributions differ by more than sampling error — in particular, a cluster of tokens appearing near zero frequency where the red list saturates the early vocabulary positions — then the unconditional stealthiness claim fails and the guarantee holds only because messages vary in practice.","tokens_in":26396,"feed_emoji":"🖋️","tokens_out":12466,"duration_ms":127142,"temperature":0.7,"pith_summary":"StealthInk proposes a way to stamp AI-generated text with a multi-bit message — user ID, timestamp, model ID — without measurably changing the distribution of what the model writes. The paper's central claim is that a token-reweighting rule can delete some candidate tokens and double others at each position while keeping the expected output distribution identical to the unwatermarked model's. If this holds, a provider can trace text back to a specific user and moment, and an attacker who studies the output statistics cannot tell watermarked from clean text, which blocks the known watermark-forgery attack. The paper proves the expected-preservation property in Theorem 4.4, derives a token-count lower bound for detection at a fixed equal error rate, and reports an AUC near 0.98 with bit accuracy near 0.92 for 24-bit messages in 300 tokens, at text quality close to the unwatermarked baseline. The motivation is that zero-bit watermarks only answer \"was this AI-written?\", while provenance data answers who wrote it, with which model, and when.","feed_headline":"24-bit ID stamps ride inside AI text unseen","feed_subtitle":"StealthInk embeds provenance data while preserving token distribution: ~92% bit accuracy in 300 tokens.","key_machinery":"The load-bearing object is the reweighting function $F_k(\\theta, M, P_O)$ in Eq. (5): with the vocabulary permuted by $\\theta$, the message $M$ fixes a red-list interval of length $\\gamma = 2^{-m}$ whose token probabilities are zeroed, and a complementary interval whose probabilities are doubled, with four cases depending on where the cumulative probabilities $\\alpha$ and $\\beta$ sit relative to 0.5. The construction is chosen so that for every token the expected probability over the random permutation equals the original probability, which is exactly the paper's definition of a stealthy multi-bit watermark (Definition 4.1). This expected-preservation identity is what makes the decoder's red-list counting statistically valid and what denies an attacker any distributional signal to forge. Around this core, StealthInk adds the position-allocation method of MPAC to spread a message sequence across token chunks, and a per-query history log that keeps successive ciphers independent as Theorem 4.3 requires.","core_discovery":"On its own terms, the paper establishes that multi-bit watermarking need not distort the language model's output distribution. For each token position, StealthInk orders the vocabulary by a pseudorandom permutation $\\theta$ seeded with the watermark key and the recent n-gram context, and the message chunk $M$ selects an interval of that permutation of length $\\gamma = 2^{-m}$; tokens in that interval are the 'red list' and get probability zero, tokens in a mirror interval get doubled probability, and a four-case rule (Eq. 5) fixes the intervals so that the expected reweighted distribution, averaged over $\\theta$, equals the original $P_O$. Theorem 4.4 states this unbiasedness for every i.i.d. permutation, and Theorem 4.3 extends it to $K$ query-response pairs when the ciphers are independent. The decoder maps each token to a message position, counts tokens in each candidate red list, picks the message minimizing that count, and runs a z-test over the recovered message sequence. The paper also derives a lower bound on tokens needed for a target equal error rate, finding that splitting a payload across many single-bit positions is more token-efficient than packing bits into fewer positions, and that repeated texture keys substantially raise the token requirement. Empirically, with 24 bits in 300 tokens it reports bit accuracy around 0.92, AUC around 0.98, near-baseline perplexity, and the lowest forged-text detection rates under a spoofing attack compared with MPAC and the schemes of Qu et al. and Fernandez et al.","pith_inferences":["Operationally, the guarantee rides on the message changing between queries: the per-query timestamp bits are what make repeated identical prompts produce different red lists. A deployment that freezes or strips those metadata bits would silently revert to a detectable watermark, so the paper's defense against the same-message attack is a deployment discipline rather than a theorem.","The red-list counting decoder only needs the text and the key, so the same machinery should transfer to structured outputs (code, JSON, and other constrained decoding) and to streaming generation, where positions and chunk boundaries are known to both encoder and decoder.","The paper's own Appendix M says low-entropy contexts — where $\\alpha$ and $\\beta$ fall in the overlapping Cases 3 and 4 — weaken detection; a practical calibration would map per-position output entropy to achievable bit accuracy, giving deployers a rule for when 24-bit payloads are feasible."],"forward_implications":["With the watermark key, a verifier can extract userID, timestamp, and modelID from text alone, needing neither the generating model's API nor the original prompt, which makes forensic traceability fast and cheap.","Because the watermarked and clean distributions coincide in expectation, the stealing/spoofing attack that exploits n-gram distribution gaps mostly fails: on the evaluated Dolly-CW prompts only about 29% of forged texts are flagged at a 10% false-positive rate, versus about 70% for MPAC and about 98% for the Qu et al. scheme under the FNR = $10^{-3}$ setting.","The equal-error-rate lower bound guides capacity: distributing unit capacity across positions (more chunks, fewer bits each) needs fewer tokens for the same detection reliability, and keeping the repetition rate $p$ of texture keys low is what lets StealthInk hold its token requirement down where global-history schemes degrade over time.","Text quality stays close to the unwatermarked model on perplexity, BLEU, BERTScore, and ROUGE, whereas the compared distribution-shifting schemes trade quality for detectability; StealthInk instead pays a detectability cost at short lengths, catching up to MPAC as token count grows (e.g., comparable TPR at 400 tokens where MPAC reaches it at 200)."],"supporting_citations":[{"why":"Supplies the definition of a stealthy (unbiased) zero-bit watermark that StealthInk extends to the multi-bit setting.","marker":"(Hu et al., 2024)"},{"why":"Dipmark: the stealthy reweighting scheme whose per-query history mechanism and structure StealthInk adapts, and a quality/stealthiness baseline.","marker":"(Wu et al., 2024)"},{"why":"The original green-list logit-bias watermark that StealthInk's unbiased reweighting is designed to replace.","marker":"(Kirchenbauer et al., 2023)"},{"why":"MPAC: supplies the position-allocation scheme for spreading a message across chunks and is the main multi-bit detectability baseline.","marker":"(Yoo et al., 2024)"},{"why":"A multi-bit watermark via cyclic vocabulary shifts and error-correction coding; the strongest detectability baseline whose distribution distortion StealthInk avoids.","marker":"(Qu et al., 2024)"},{"why":"Defines the watermark-stealing/spoofing threat model and attack that stealthiness is meant to resist.","marker":"(Jovanovi´c et al., 2024)"},{"why":"Prior distortion-free multi-bit watermarking; marks the robustness gap StealthInk tries to close.","marker":"(Kordi Boroujeny et al., 2024)"},{"why":"Supplies the sampling-without-replacement moment formulas used in the proof that the reweighting is unbiased.","marker":"(Cohran, 1977)"}],"fun_headline_variants":["Multibit watermark embeds IDs in AI text without altering distribution","StealthInk hides provenance data in LLM output, no API access needed","Watermark packs 24-bit IDs into text with near-zero distribution change","Multibit watermark embeds userID, timestamp, modelID in AI text"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"K-shot stealthiness (Theorem 4.3) requires the vocabulary permutations across separate queries to be independent, but StealthInk keeps no global history, so identical prompts carrying the same message (same user ID and timestamp) reuse the same permutation; the paper's defense — that timestamps make messages vary and that flooding queries within one millisecond is impractical (Section 4.2, Appendix F) — is an assumption about attacker timing, not a proven property, so a determined attacker who forces identical messages can detectably distort the first-token distribution.","fun_headline_variants_meta":{"raw":{"variants":["Multibit watermark embeds IDs in AI text without altering distribution","StealthInk hides provenance data in LLM output, no API access needed","Watermark packs 24-bit IDs into text with near-zero distribution change","Multibit watermark embeds userID, timestamp, modelID in AI text"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001161,"raw_usage":{"total_tokens":4849,"prompt_tokens":1030,"completion_tokens":3819,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":646,"completion_tokens_details":{"reasoning_tokens":3739}},"tokens_in":646,"tokens_out":3819,"duration_ms":30308,"temperature":1.0,"reasoning_tokens":3739,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:22:27.819516+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set the timestamp and user metadata bits to a fixed value, submit the same prompt to the watermarked model tens of thousands of times, and compare the empirical first-token distribution with the unwatermarked model's first-token distribution for that prompt. If the distributions differ by more than sampling error — in particular, a cluster of tokens appearing near zero frequency where the red list saturates the early vocabulary positions — then the unconditional stealthiness claim fails and the guarantee holds only because messages vary in practice.","supporting_citations":[{"cited_title":"A watermark for large language models","cited_arxiv_id":null,"evidence_quote":"The original green-list logit-bias watermark that StealthInk's unbiased reweighting is designed to replace."},{"cited_title":"Watermark stealing in large language models","cited_arxiv_id":null,"evidence_quote":"Defines the watermark-stealing/spoofing threat model and attack that stealthiness is meant to resist."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the sampling-without-replacement moment formulas used in the proof that the reweighting is unbiased."}],"review_version":1}