Pith. sign in

REVIEW 3 major objections 6 minor 25 references

TRACE is the first watermark for LLM-agent trajectories that is distortion-free in its actions, self-synchronizing under deletion, and unconditionally invariant under rewriting.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-10 08:02 UTC pith:L2RNU4XD

load-bearing objection Solid dual-channel agent watermark that actually matches a realistic log-holding adversary; theorems and experiments line up, with two stated soft premises that do not sink the main claims. the 3 major comments →

arxiv 2607.08400 v1 pith:L2RNU4XD submitted 2026-07-09 cs.CR cs.AIcs.LG

TRACE: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories

Zheng Gao , Xiaoyu Li , Xiaoyan Feng , Jiaojiao Jiang , Yang Song , Yulei Sui , Zhenchang Xing , Liming Zhu This is my paper
classification cs.CR cs.AIcs.LG
keywords agent watermarkingLLM agentstrajectory attributiondistortion-free watermarkdeletion robustnessrewrite invariancebehavioral provenancereseller threat model
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

When LLM agents reach users through resellers, provenance is judged from trajectory logs that the reseller itself stores, meters, and can edit. Existing agent watermarks put one signal under one keying on that log, so pruning steps desynchronizes a position key and rewriting content erases a content key. TRACE answers by superposing two watermarks with complementary carriers and keys: a selection channel that chooses which action is taken, keyed on local content via a distortion-free exponential race that leaves the agent's distribution exactly unchanged, so detection resynchronizes after deletions; and a tally channel that sets how many records each decision group holds, keyed only on the log's skeleton, which rewriting cannot touch. The paper proves each decision buys signal worth at least half its entropy and deterministic decisions buy none, and that erasing both channels forces skeleton edits plus, for obliviously targeted attacks, corruption of a constant fraction of groups. On ToolBench and ALFWorld the scheme matches unwatermarked success rates, keeps the tally channel exactly fixed under rewriting of any strength, and keeps the selection channel detectable under 70% step deletion.

Core claim

A trajectory has room for two watermarks whose vulnerable surfaces are orthogonal: a content-keyed selection channel that is distortion-free and self-synchronizing under deletion (blast radius one), and a position-keyed tally channel that is unconditionally invariant under every rewriting attack. Silencing both at once is expensive: any attack that moves the tally statistic must edit the skeleton, and any obliviously targeted attack that suppresses the selection statistic must corrupt a constant fraction of the very actions the resold service depends on.

What carries the argument

Complementary two-channel embedding: the selection channel samples the winner of a content-keyed exponential race over the candidate action set (preserving the agent's exact distribution), while the tally channel appends a context-neutral redundant record under a skeleton-keyed target count of 1 or 2.

Load-bearing premise

The verifier must recover the true admissible action sets at each decision from the environment rather than from the reseller-edited log; if those sets cannot be trusted independently, the selection channel cannot be replayed.

What would settle it

On long-horizon trajectories, an informed rewriter that also deletes observations drives both selection and tally z-statistics below threshold without reducing task success and without skeleton mismatches against the provider's execution record.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Attribution of agent trajectories remains possible against an adversary who owns the evidence, provided both channels are used together.
  • Distortion-free behavioral watermarking must pool short or low-entropy trajectories: each decision contributes at least half its entropy, and deterministic decisions contribute nothing.
  • A single rewriting pass erases single-signal baselines while leaving TRACE's tally channel exactly unchanged.
  • Only the joint high-deletion, high-rewriting corner can silence both detectors, and that corner already destroys the resold service.
  • Skeleton edits required to kill the tally channel are exposed by a log/execution consistency audit against the provider's execution record.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same content-versus-structure complementary binding may transfer to other sequential decision logs, such as robotic telemetry or multi-agent interaction traces.
  • Deployments that cannot attest environment action spaces at audit time lose half the dual guarantee, so signed or attested action spaces become a practical complement.
  • Score-adaptive attackers that target high-signal groups by realized winners could beat the constant-fraction lower bound; measuring that adaptive rate is an open empirical test.
  • Extending the tally channel beyond binary counts of 1 or 2 could raise detection power while still adding only log volume, not tool calls.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. TRACE proposes a two-channel behavioral watermark for LLM-agent trajectories under a reseller threat model in which the adversary has full read/write access to the trajectory log used for attribution. The selection channel embeds a content-keyed, distortion-free exponential race over admissible actions so that the agent's action distribution is exactly preserved (Theorem 5.1) and detection resynchronizes after deletions (Proposition D.9). The tally channel embeds a skeleton-keyed {1,2} group-count pattern via context-neutral redundant records and is proved unconditionally invariant under every rewriting attack that preserves the tag sequence (Theorem 5.3). The paper proves an entropy lower bound on selection-channel signal (Theorem 5.2), exact finite-sample nulls for both detectors, and a joint-erasure cost theorem (Theorem 5.4). On ToolBench and ALFWorld, TRACE matches unwatermarked success rates, yields large selection z on long horizons, remains detectable under 70% deletion, and keeps the tally channel fixed under an informed LLM rewriter of any strength.

Significance. The reseller threat model—attribution against the party that lawfully holds and may edit the evidence—is the right security setting for agent provenance and is under-addressed by prior single-signal agent watermarks. Superposing complementary content-keyed and skeleton-keyed channels is a clean design principle with structural rather than purely empirical robustness guarantees. Distortion-freeness via the race lemma, the digamma/trigamma entropy bound, exact Gamma/Binomial nulls, and rewrite invariance as an identity are genuine technical contributions; the LLM rewriter is a useful new attack instance. If the claims hold under the stated threat model, TRACE is a strong candidate for the first agent watermark that is simultaneously distortion-free, deletion-self-synchronizing, and rewrite-invariant, with a joint-erasure lower bound that prices laundering as product corruption.

major comments (3)
  1. [Theorem 5.4(b), Remark D.12, Abstract] Theorem 5.4(b) and Remark D.12: the joint-erasure lower bound on the selection channel assumes the corrupted set is chosen obliviously of realized selection scores. The reseller threat model (Section 3.2) grants full read access to the log before editing, so a score-adaptive attacker who targets high-φ groups is inside the model. The abstract and takeaway of Theorem 5.4 state that erasing both channels forces constant-fraction corruption; that claim is proved only for the oblivious subclass. Either bound (or empirically stress-test) the score-adaptive rate, or restate the abstract/Section 5.4 takeaway to match the theorem's hypothesis so the central joint-erasure claim is not oversold.
  2. [Definition 3.4, Section 3.2–3.3, Section 7] Definition 3.4 and Section 7: selection-channel detection requires the verifier to recompute environment-supplied candidate sets B_i and the executed action stream independently of the reseller-released log. The threat model places these outside the rewrite/deletion surface by fiat, but many realistic resale deployments proxy tools and environments. If B_i cannot be recovered at audit time, half of the dual-channel guarantee collapses. The paper should specify operational conditions under which B_i is available (e.g., public tool catalogs, provider-side execution records) and state more explicitly that the tally channel alone still attributes under pure rewriting when B_i is unavailable.
  3. [Section 6.4, Figures 5–6, Tables 11–17] Section 6.4 and Figures 5–6: deletion, rewriting, and combined-attack sweeps (including TPR@1%FPR tables) are reported primarily on ToolBench. ALFWorld supplies the headline selection z≈100 and long-horizon single-trajectory attribution, but the orthogonal failure of the two channels under the reseller's two moves is not shown on that benchmark. A compact ALFWorld attack ablation (even at a subset of (r,q) cells) would confirm that the dual-channel prediction is not short-trajectory-specific and would better support the claim that only the joint high-deletion/high-rewrite corner silences both detectors.
minor comments (6)
  1. [Figure 3, Section 3.2] Figure 3 and Algorithms 1–2 are clear; consider adding a one-line note in the figure caption that the detector may also regroup from the provider-side execution stream (log/execution consistency audit), since that is load-bearing for Theorem 5.4(a).
  2. [Table 2, Section 6.2, Table 8] Table 2 reports Trace steps including redundant records; the decomposition in Section 6.2 and Table 8 is helpful—cross-reference Table 8 from the main utility paragraph so readers do not misread the step overhead as agent work.
  3. [Section 6.1 Metrics, Algorithm 2] The combined detector in experiments uses max(z1,z2) with θ=2, while Algorithm 2 uses min(p1,p2)≤α/2. A short note that the normal-approximation rule is the practical counterpart of the exact union-bound test would avoid confusion.
  4. [Proposition 3.3, Appendix B] Proposition 3.3 is immediate from Definition 3.2; stating it as a proposition is fine, but a parenthetical 'immediate' would set expectations for the dependency map in Appendix B.
  5. [Section 2] Related work on image watermarks (Tree-Ring, SLICE, etc.) is thoughtfully connected; a one-sentence pointer to authenticated logging / TEEs as complementary rather than competing mechanisms already appears in Section 2—consider elevating that sentence slightly so the architectural placement is visible early.
  6. [Section 4.2, Lemma D.3, Appendix E] Minor notation: p0=1/2 is exact for k_i∈{1,2} baselines (Lemma D.3); Appendix E's note on conservative tails for heavy-observation baselines is easy to miss—mention it once in Section 4.2.

Circularity Check

0 steps flagged

No significant circularity: TRACE's core guarantees are structural design identities and independent digamma/race proofs, not fitted targets or self-citation chains.

full rationale

The load-bearing claims do not reduce to their inputs by construction in the Pith sense. Distortion-freeness (Thm 5.1) is the standard exponential-race / Gumbel-max identity (Lemma D.1) applied to the agent action set; the sampler is defined independently of the detection statistic, and Pr[b_i=b]=P_i[b] is a genuine equality, not a fit. The entropy lower bound (Thm 5.2) is a proved scalar inequality on the digamma function (via Lemma D.7 and the conditional generalized-exponential law of Lemma D.4), with equality only at point masses; experiments report measured z-scores that accumulate at the predicted per-group rate, not quantities forced by fitting the bound. Rewrite invariance of the tally (Thm 5.3) is an identity once the channel is keyed only on the skeleton and rewriting is defined to preserve the skeleton (Def 3.7, Prop 3.3)—this is transparent security construction, not a smuggled prediction or renaming of an empirical pattern. Deletion self-synchronization (Prop D.9) follows from content keying with a memory-one window; joint-erasure cost (Thm 5.4) is a lower bound under an explicit obliviousness hypothesis (Remark D.12 leaves the adaptive case open). Self-citations (Gao et al. 2026a/b) appear only as modality analogies in related work and are not load-bearing for any theorem. Detection threshold θ=2 and RG hyperparameters are experimental knobs, not theoretical inputs. The paper is self-contained against its stated threat model and external benchmarks; score 0 is the honest finding.

Axiom & Free-Parameter Ledger

3 free parameters · 5 axioms · 3 invented entities

The central dual-channel claims rest on standard cryptographic idealization of the DRBG, domain facts about agent logs (skeleton vs content, environment-supplied action sets), and a few design-level definitions (context-neutral redundant records, memory-one content window). No physical constants or large fitted scales drive the theorems; experimental thresholds affect reported TPR tables, not the identities in Theorems 5.1 and 5.3.

free parameters (3)
  • detection threshold θ
    Experiments threshold pooled z at θ=2 (and TPR@1% uses Gaussian 2.326); this is a chosen operating point for reported detection tables, not a fitted physical constant, but reported attack success depends on it.
  • RG baseline (γ=0.5, δ=2.0)
    Red–green comparison arm hyperparameters chosen by hand; affect only baseline utility/detection, not TRACE theorems.
  • combined FPR split α/2
    Union-bound combination of the two exact p-values; conventional multiple-testing choice.
axioms (5)
  • domain assumption Ideal pseudorandomness of DRBG values across distinct nonces (Assumption 3.5)
    Standard PRF idealization used for exact null laws, independence of channels, and deletion/rewrite analysis throughout §5 and Appendix D.
  • standard math Skeleton (tag sequence) alone determines group boundaries and counts k_i (Proposition 3.3 / Definition 3.2)
    Immediate from the decision-boundary grouping definition; load-bearing for rewrite invariance of the tally channel.
  • domain assumption Reseller cannot re-execute the agent; executed action stream and environment-supplied B_i are outside the editable log
    Threat model §3.2–3.3; without it the adversary could regenerate unmarked trajectories or forge decisions.
  • ad hoc to paper Context-neutral redundant records append without changing decision-relevant context or invoking tools (Definition 4.1)
    Design premise that makes the tally channel utility-neutral; depends on logging formats admitting such records (admissibility rate η).
  • ad hoc to paper Corrupted group set in joint-erasure bound is chosen independently of realized selection scores (Theorem 5.4(b))
    Necessary for the constant-fraction lower bound; score-adaptive attacks left open in Remark D.12.
invented entities (3)
  • Selection channel (content-keyed distortion-free exponential race over behaviors) independent evidence
    purpose: Embed a deletion-self-synchronizing watermark in which action is chosen without changing the agent's distribution.
    Engineering construct transplanting Kuditipudi-style races from tokens to agent actions; not a physical entity. Independent evidence is the proved null/alternative laws and empirical z-scores.
  • Tally channel (skeleton-keyed {1,2} group-count pattern via context-neutral redundant records) independent evidence
    purpose: Embed a rewrite-invariant watermark in how many records each decision group holds.
    Design construct whose invariance is definitional given skeleton keying; empirical pin of z_2 under LLM rewriting supports it.
  • LLM rewriter (informed, plausibility-preserving rewrite attack) independent evidence
    purpose: Strongest practical instance of the rewriting class for evaluation.
    Attack model introduced by the paper; falsifiable via the published prompt and substitution protocol.

pith-pipeline@v1.1.0-grok45 · 42121 in / 3730 out tokens · 87221 ms · 2026-07-10T08:02:42.826676+00:00 · methodology

0 comments
read the original abstract

LLM agents reach users through resellers, who may rebrand a developer's agent or substitute a cheaper model. When provenance is disputed, attribution rests on the trajectory log (the record of tool calls, observations, and executed actions, not the model's reasoning), which the reseller stores and processes to meter usage. A watermark must therefore survive an adversary with full read/write access to the very evidence it is detected from; existing agent watermarks do not, as their attribution is read straight off that log. We present TRACE, to our knowledge the first agent watermark that is distortion-free in its action choices, self-synchronizing under deletion, and unconditionally invariant under rewriting. Deletion desynchronizes a position-derived key and rewriting alters content, so a deletion-robust key must come from content and a rewrite-robust key from position, and no single key serves both. A trajectory, however, has room for two watermarks. TRACE superposes a selection channel that sets which action is chosen, keyed on local content with a distortion-free sampler, so the agent's distribution is provably unchanged and detection resynchronizes after deletions, and a tally channel that sets how many records each decision group holds, keyed on the log's skeleton alone, which no rewriting can touch. We prove this behavioral watermark's signal is bought with decision entropy, each decision paying at least half its entropy and deterministic decisions nothing, and that erasing both channels forces the reseller to corrupt the trajectories it resells. On ToolBench and ALFWorld, TRACE matches the unwatermarked agent's success rate while its selection channel reaches detection scores near z = 100 on long-horizon trajectories, stays detectable under 70% step deletion, and keeps a tally channel exactly unchanged under LLM rewriting of any strength.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 11 internal anchors

  1. [1]

    Watermarking of large language models

    Scott Aaronson and H Kirchner. Watermarking of large language models. InLarge language models and transformers workshop at Simons Institute for the Theory of Computing, volume 2023,

    work page 2023

  2. [2]

    Hidden in the noise: Two-stage robust watermarking for images

    Kasra Arabi, Benjamin Feuer, R Teal Witter, Chinmay Hegde, and Niv Cohen. Hidden in the noise: Two-stage robust watermarking for images. InInternational Conference on Learning Representations, volume 2025, pages 61271–61304, 2025a. KasraArabi,RTealWitter,ChinmayHegde,andNivCohen. Seal: Semanticawareimagewatermarking. InProceedings of the IEEE/CVF Internat...

    work page 2025

  3. [3]

    AlanChan, CarsonEzell, MaxKaufmann, KevinWei, LewisHammond, HerbieBradley, EmmaBluemke, Nitarshan Rajkumar, David Krueger, Noam Kolt, Lennart Heim, and Markus Anderljung

    URLhttps://api.semanticscholar.org/ CorpusID:6345601. AlanChan, CarsonEzell, MaxKaufmann, KevinWei, LewisHammond, HerbieBradley, EmmaBluemke, Nitarshan Rajkumar, David Krueger, Noam Kolt, Lennart Heim, and Markus Anderljung. Visibility into ai agents.Proceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency,

    work page 2024

  4. [4]

    BiMark: Unbiased Multilayer Watermarking for Large Language Models

    Xiaoyan Feng, He Zhang, Yanjun Zhang, Leo Yu Zhang, and Shirui Pan. Bimark: Unbiased multilayer watermarking for large language models.arXiv preprint arXiv:2506.21602,

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    Zheng Gao, Xiaoyu Li, Zhicheng Bao, Xiaoyan Feng, and Jiaojiao Jiang

    URL https://api.semanticscholar.org/CorpusID:7812384. Zheng Gao, Xiaoyu Li, Zhicheng Bao, Xiaoyan Feng, and Jiaojiao Jiang. Breaking semantic-aware watermarks via llm-guided coherence-preserving semantic injection. InProceedings of the ACM Web Conference 2026, pages 8569–8572, 2026a. Zheng Gao, Yifan Yang, Xiaoyu Li, Xiaoyan Feng, Haoran Fan, Yang Song, a...

    work page arXiv 2026

  6. [6]

    Samuel Gunn, Xuandong Zhao, and Dawn Song

    URLhttps://api.semanticscholar.org/CorpusID: 17064126. Samuel Gunn, Xuandong Zhao, and Dawn Song. An undetectable watermark for generative image models. InInternational Conference on Learning Representations, volume 2025, pages 6612–6637,

    work page 2025

  7. [7]

    org/CorpusID:118877852

    URLhttps://api.semanticscholar. org/CorpusID:118877852. Abe Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang, Lingfeng Shen, BenjaminVanDurme, DanielKhashabi, andYuliaTsvetkov. Semstamp: Asemanticwatermark with paraphrastic robustness for text generation. InProceedings of the 2024 Conference of the North American Chapter of the ...

    work page 2024

  8. [8]

    Unbiased watermark for large language models

    20 Trace: A Two-Channel Robust Attribution Watermark via Complementary Embeddings for LLM-Agent Trajectories Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. InInternational Conference on Learning Representations, volume 2024, pages 45408–45436,

    work page 2024

  9. [9]

    Agent Guide: A Simple Agent Behavioral Watermarking Framework

    Kaibo Huang, Zipei Zhang, Zhongliang Yang, and Linna Zhou. Agent guide: A simple agent behavioral watermarking framework.arXiv preprint arXiv:2504.05871,

    work page internal anchor Pith review Pith/arXiv arXiv

  10. [10]

    AgentMark: Utility-Preserving Behavioral Watermarking for Agents

    Kaibo Huang, Jin Tan, Yukun Wei, Wanling Li, Zipei Zhang, Hui Tian, Zhongliang Yang, and Linna Zhou. Agentmark: Utility-preserving behavioral watermarking for agents.arXiv preprint arXiv:2601.03294,

    work page internal anchor Pith review Pith/arXiv arXiv

  11. [11]

    Watermark Stealing in Large Language Models

    Nikola Jovanović, Robin Staab, and Martin Vechev. Watermark stealing in large language models. arXiv preprint arXiv:2402.19361,

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    On the reliability of watermarks for large language models

    John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. InInternational Conference on Learning Representations, volume 2024, pages 49660–49704,

    work page 2024

  13. [13]

    Robust Distortion-free Watermarks for Language Models

    Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models.arXiv preprint arXiv:2307.15593,

    work page internal anchor Pith review Pith/arXiv arXiv

  14. [14]

    AgentBench: Evaluating LLMs as Agents

    Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Yuxian Gu, Han Ding, Kai Men, Kejuan Yang, Shudan Zhang, Xiang Deng, Aohan Zeng, Zhengxiao Du, Chenhui Zhang, Shengqi Shen, Tianjun Zhang, Sheng Shen, Yu Su, Huan Sun, Minlie Huang, Yuxiao Dong, and Jie Tang. Agentbench: Evaluating llms as agents.ArXiv, abs/2308.03688,

    work page internal anchor Pith review Pith/arXiv arXiv

  15. [15]

    Watermarking LLM Agent Trajectories

    URLhttps://api.semanticscholar.org/CorpusID:204937530. Wenlong Meng, Chen Gong, Terry Yue Zhuo, Fan Zhang, Kecen Li, Zheng Liu, Zhou Yang, Chengkun Wei, and Wenzhi Chen. Watermarking llm agent trajectories.arXiv preprint arXiv:2602.18700,

    work page internal anchor Pith review Pith/arXiv arXiv

  16. [16]

    Toolllm: Facilitating large language models to master 16000+ real-world apis

    Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang, Bill Qian, et al. Toolllm: Facilitating large language models to master 16000+ real-world apis. In International Conference on Learning Representations, volume 2024, pages 9695–9717,

    work page 2024

  17. [17]

    Can AI-Generated Text be Reliably Detected?

    Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can ai-generated text be reliably detected?arXiv preprint arXiv:2303.11156,

    work page internal anchor Pith review Pith/arXiv arXiv

  18. [18]

    ALFWorld: Aligning Text and Embodied Environments for Interactive Learning

    Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew J. Hausknecht. Alfworld: Aligning text and embodied environments for interactive learning.ArXiv, abs/2010.03768,

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  19. [19]

    LiwenWang,ZongjieLi,YuchongXie,ShuaiWang,DongdongShe,WeiWang,andJuergenRahmel

    URLhttps://api.semanticscholar.org/CorpusID:222208810. LiwenWang,ZongjieLi,YuchongXie,ShuaiWang,DongdongShe,WeiWang,andJuergenRahmel. On protectingagenticsystems’intellectualpropertyviawatermarking.arXivpreprintarXiv:2602.08401,

    work page arXiv

  20. [20]

    ReAct: Synergizing Reasoning and Acting in Language Models

    Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models.arXiv preprint arXiv:2210.03629,

    work page internal anchor Pith review Pith/arXiv arXiv

  21. [21]

    Advancing beyond identification: Multi-bit watermark for large language models

    KiYoon Yoo, Wonhyuk Ahn, and Nojun Kwak. Advancing beyond identification: Multi-bit watermark for large language models. InProceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 4031–4055,

    work page 2024

  22. [22]

    Provable Robust Watermarking for AI-Generated Text

    Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai-generated text.arXiv preprint arXiv:2306.17439,

    work page internal anchor Pith review Pith/arXiv arXiv

  23. [23]

    exactly, the one-sided𝑝-value is the regularized upper incomplete Gamma function𝑄(𝑛, 𝑋 1), and 𝑧1 ⇒ N (0,1)as𝑛→ ∞. Proof. Under 𝐻0 the producer holds no information aboutkey1, so by Assumption 3.5 the value𝑟𝑏𝑖 at therealized(deduplicated)evaluationpoint (ctx𝑖, 𝑏𝑖) isuniformon (0, 1), independentlyacrossgroups. Then 𝜑𝑖 ∼Exp( 1), and the remaining claims ar...

    work page 1999

  24. [24]

    By Theorem 5.2, 𝜇𝑖 ≥1+ ¯ℎ/2

    +𝛾 . By Theorem 5.2, 𝜇𝑖 ≥1+ ¯ℎ/2. By Lemma D.4 and the law of total variance, Var[𝜑𝑖]=𝔼 𝑏 Var[𝜑𝑖 |𝑏] +Var 𝑏 𝑔(𝑝 𝑏) ≤ 𝜋2 6 + 𝑔(𝑝 ∗) −𝑔(1) 2 4 =𝜎 2 ∗ , where the second term uses Popoviciu’s inequality [Popoviciu, 1935] for the random variable𝑔(𝑝 𝑏𝑖) ∈ [𝑔( 1), 𝑔(𝑝 ∗)]=[ 1, 𝜓(1/𝑝∗ +

    work page 1935

  25. [25]

    As this holds for every value of(𝜏, 𝑋 2), 𝑝1 is independent of(𝜏, 𝑋 2), and in particular of𝑝2, which is a function of(𝑛, 𝑋 2)

    (the probability integral transform). As this holds for every value of(𝜏, 𝑋 2), 𝑝1 is independent of(𝜏, 𝑋 2), and in particular of𝑝2, which is a function of(𝑛, 𝑋 2). The 𝑧-scores are not in general independent marginally, as both standardize by the same random𝑛=𝑛(𝜏) ; the dependence vanishes only at the 𝑝-value level. The union bound, which uses no indepe...

    work page 1925