PaperlayerView exact revision on arXiv

Source-linked AI summary

Token-Level Attribution of Multi-Mode LLM Watermarks: Optimal Rule and Belief Weighting

Rui Zhou, Licheng Zhao, Chao Shen, Wenqiang Pu

arXiv:2610.23601v1cs.CReess.SPstat.AP

TL;DR

Multi-mode attribution must label tokens in documents that mix watermarked modes and unwatermarked spans, while allocating a shared Type I error budget. The paper derives a prior-weighted optimal rule and proposes BLADE, which estimates mode priors and alternative densities. BLADE has higher correct-label power than the compared detectors across the evaluated settings.

  • Problem

    Token-level attribution must distinguish retained watermarks from null tokens and assign the correct mode, while the mode prior can direct the Type I error budget toward likely modes.

    Source: C. Prior-Weighted Attribution Problem · p. 4, A. Structure of the Optimal Rule · p. 4

  • Method

    The optimal rule thresholds the largest prior-weighted alternative density, and BLADE estimates the mode prior from neighboring pivots and alternative density from reference token probabilities.

    Source: §I · p. 2

  • Results

    BLADE attains higher correct-label power than the compared detectors across candidate counts, substitution rates, generation temperatures, and generator models.

    Source: §I · p. 2, §VII · p. 11

  • Takeaways & Limitations

    The optimal rule allocates the Type I error budget across modes, and BLADE approaches its power as its prior and density estimation errors vanish.

    Source: B. Calibration and Budget Allocation · p. 5, §VII · p. 10

Abstract

from arXiv · show

A watermark verifier may hold many modes, i.e., secret keys, and a document may mix spans of different modes with unwatermarked text. Directly reporting the mode with the largest pivotal statistic (pivot) inflates the Type I error, and restoring the nominal level reduces power as candidate modes are added. We formulate token-level multi-mode attribution for the Gumbel-max watermark as maximizing correct-label power under a Type I error constraint given a mode prior. We show that the optimal rule reports the mode with the largest prior-weighted alternative density and rejects when this density exceeds one common threshold. Based on this rule, we propose the Belief-weighted Likelihood Attribution with Density Estimation (BLADE) detector. It estimates the mode prior from neighboring pivots and the alternative density from reference token probabilities. Under a conditional product model of the pivots, it keeps the exact Type I error. We further show that BLADE approaches the optimal rule as its prior and density estimates improve, with a sharp coefficient on the density error. On OPT-1.3B and other open-weight large language models, BLADE attains higher correct-label power than the compared detectors across candidate counts, token-substitution rates, generation temperatures and generator models.

I. INTRODUCTION

The paper extends Gumbel-max watermark detection from one key and whole-text decisions to token-level attribution across modes in mixed documents. It derives a prior-weighted optimal rule and proposes BLADE, while introducing the single-token pivot test that underlies the approach.

A. Gumbel-Max Watermarking and the Single-Token Test

  • For Gumbel-max watermarking, the verifier tests whether a keyed pivot is uniform for unwatermarked text or stochastically larger for watermarked text.The watermark preserves the next-token distribution in expectation over pseudorandomness; the single-mode level-α test has power 1 − FH(1 − α).Source: §I · p. 1, A. Gumbel-Max Watermarking and the… · pp. 2–3

I. INTRODUCTION

  • Multi-mode attribution labels each token as unwatermarked or assigns it to the mode that generated it, accounting for mixed spans and watermarks lost through editing.Neighboring tokens usually share a mode, providing evidence for attribution; earlier BW weighting used a heuristic rather than an optimality criterion.Source: §I · pp. 1–2
  • The optimal rule maximizes prior-weighted correct-label power under a Type I error constraint, reporting the mode with the largest prior-weighted alternative density above a common threshold.Under the uniform product null, the threshold divides the Type I error budget among modes and bounds misattribution.Source: §I · p. 2
  • BLADE estimates the mode prior from neighboring pivots and the alternative density from reference token probabilities, retaining exact Type I error under the conditional product model.Its loss relative to the optimum is bounded in terms of prior and density estimation errors, with a sharp coefficient on density error.Source: §I · p. 2
  • BLADE achieves higher correct-label power than calibrated Max-Pivot, Local-Count weighting, and BW across candidate counts, substitution rates, temperatures, and generator models.It also keeps Type I error near nominal on human-written and edited text.Source: §I · p. 2

B. Alternative Distribution of the Pivot

The section characterizes the watermarked pivot distribution through the selected token's probability and sets up attribution as a token-level test over candidate modes. It also specifies the null and mode-specific alternatives used for that test.

B. Alternative Distribution of the Pivot

  • The watermarked pivot distribution depends on the generator through the selected token's probability, and its density is nondecreasing and continuous.The model FH(x) = x^d in is the special case where the selected-token probability is constantly 1/d.Source: B. Alternative Distribution of the Pivot · p. 3
  • At temperature 1.0 and α = 0.05, the single-token rule detects 42.0% of watermarked tokens; higher temperatures typically lower selected-token probability and shift the watermarked pivot curves.A selected-token probability near 1 yields a nearly uniform, hard-to-detect pivot, while lower probabilities concentrate pivots near 1.Source: B. Alternative Distribution of the Pivot · p. 3

A. Token-Level Hypothesis Test

  • The active mode is latent but locally persistent, and attribution counts a detection as successful only when it assigns the true mode.Pivots are independent at positions whose context windows have not occurred earlier, under the stated assumption.Source: A. Token-Level Hypothesis Test · p. 3
  • At each position, the verifier computes a pivot for every candidate mode and tests a null of independent uniform pivots against mode-specific alternatives.A watermark not retained at a token is treated as null even within a watermarked span; positions with repeated context windows are masked as unassessed.Source: A. Token-Level Hypothesis Test · p. 3

B. Competition Cost of Max-Pivot

Max-Pivot’s competition across modes can raise Type I error and reduce correct-label power; the optimal rule instead uses mode priors to select and threshold a weighted alternative density.

B. Competition Cost of Max-Pivot

  • For large K under the stated simple alternative, Max-Pivot’s Type I error approaches 1 and its correct-label power is approximately d/K; calibrated Max-Pivot’s power is approximately αd/K.Calibration restores Type I error to α but costs an additional factor α in correct-label power.Source: B. Competition Cost of Max-Pivot · p. 4
  • At α = 0.05, Max-Pivot’s Type I error rises from 9.8% at K = 2 to 80.6% at K = 32; calibrated Max-Pivot retains 26% and 3.4% of known-mode power at K = 4 and K = 32.The passage attributes the loss to missing mode information, since the single-mode test knowing the generating mode does not incur it.Source: B. Competition Cost of Max-Pivot · p. 4

C. Prior-Weighted Attribution Problem

  • The attribution problem maximizes prior-weighted correct-label power subject to a token-level Type I error constraint, with the prior representing the likely mode of a retained watermark.The objective is equivalent to the probability of reporting the true mode, conditional on a watermark being retained.Source: C. Prior-Weighted Attribution Problem · p. 4

A. Structure of the Optimal Rule

  • The optimal rule reports the mode with the largest prior-weighted alternative density and rejects when that score exceeds a common threshold.Its score-based threshold structure differs from Max-Pivot’s threshold on the largest pivot.Source: A. Structure of the Optimal Rule · p. 4
  • With equal priors and a common density, the optimal rule becomes calibrated Max-Pivot; with a known generating mode, it becomes the Oracle single-mode test.These are the two extremes of mode information, and their power gap measures the potential gain from mode information.Source: A. Structure of the Optimal Rule · p. 4

B. Calibration and Budget Allocation

The optimal rule calibrates a common score threshold through the null distribution, splitting the Type I error budget across modes and bounding wrong-mode reports.

B. Calibration and Budget Allocation

  • The calibration equation links per-mode levels through the common threshold, shifting budget toward more likely modes and giving no budget to modes whose weighted density cannot reach the threshold.For a common density, a lower-prior mode receives a smaller level.Source: B. Calibration and Budget Allocation · p. 5
  • The verifier can calibrate without solving for the threshold: it rejects when the null CDF of the observed score exceeds 1 − α.The null CDF is evaluated at the observed score and compared with 1 − α.Source: B. Calibration and Budget Allocation · p. 5

C. Control of Misattribution

  • At α = 0.05, the optimal rule’s misattribution rate is at most 5.13%, controlled by the same Type I error budget.The per-mode levels bound wrong-mode reports without a separate constraint in the optimization problem.Source: C. Control of Misattribution · p. 5

V. FROM THE OPTIMAL RULE TO PRACTICAL DETECTORS

The practical detectors estimate the unknown prior and alternative densities using neighboring pivots and reference data; conditional independence of neighboring evidence preserves exact calibration for these estimates.

V. FROM THE OPTIMAL RULE TO PRACTICAL DETECTORS

  • The optimal rule requires unknown mode priors and alternative densities, motivating practical detectors that estimate these quantities and analyze their power and complexity.BW uses neighboring pivots for a prior estimate and a heuristic score, while BLADE refines both components.Source: §V · p. 5

A. Neighboring Evidence and Calibration

  • Under the conditional product model, prior estimates and increasing working scores formed from neighboring evidence and independent reference data preserve exact conditional Type I error, regardless of their accuracy.The estimates’ errors affect power, not calibration.Source: A. Neighboring Evidence and Calibration · p. 6

B. The BW Detector / 1) Prior Estimate:

  • BW estimates the mode prior from neighboring pivots with a working Markov chain that models local persistence and excludes a null state.Its forward–backward prior estimate excludes the target position’s evidence, as required for calibration.Source: B. The BW Detector · p. 6, 1) Prior Estimate · p. 6

2) Working Score:

BW uses an inverse-p-value working score and a closed-form calibrated rule; BLADE instead estimates alternative densities from reference token probabilities and uses them as evidence.

2) Working Score:

  • BW substitutes the reciprocal null p-value, h(r) = (1 − r)^−1, for the alternative density, but h is a working score rather than an integrable density.Its increase with the pivot makes it usable in the optimal rule’s score structure.Source: 2) Working Score · p. 6

3) Decision Rule:

  • BW selects the mode maximizing belief-weighted h and rejects when the score’s null CDF exceeds 1 − α, yielding conditional calibration.The choice of h provides closed-form per-mode levels and a closed-form null CDF.Source: 3) Decision Rule · p. 6

C. The BLADE Detector

  • BLADE replaces BW’s heuristic score with an alternative-density estimate and estimates the prior using a working chain that includes a null state.The density estimate also serves as evidence in the prior-estimation chain.Source: C. The BLADE Detector · p. 6

1) Density Estimate:

  • BLADE estimates a common working density from an offline reference sample of selected-token probabilities under the generator’s sampling distribution.The provider supplies the sample independently of the scored document; the estimate is computed once and does not depend on token position.Source: 1) Density Estimate · pp. 6–7

2) Prior Estimate:

BLADE estimates mode beliefs from neighboring pivots and alternative densities from reference tokens, then applies a prior-weighted likelihood rule. Its estimation-error analysis bounds power loss and shows convergence to the optimum as both error terms vanish.

2) Prior Estimate:

  • A working (K + 1)-state Markov chain uses neighboring pivots to estimate each position’s probability of being unwatermarked or belonging to a mode.For watermarked modes, the evidence uses likelihood ratios based on retention probability θ and the estimated alternative density; the target position’s own evidence is excluded from its neighboring-evidence estimate.Source: 2) Prior Estimate · p. 7

3) Decision Rule:

  • BLADE selects the mode with the largest estimated prior-weighted density and rejects when its calibrated null-CDF score exceeds 1 − α.The rule substitutes estimated priors and densities into the optimal rule; its threshold is computed from the conditional null CDF.Source: 3) Decision Rule · p. 7

D. Effect of Estimation Errors on BLADE

  • 0.4: In the toy case, exact power loss stays below the density-error bound for every displayed D, and both approach 0.4 as D grows.The setup uses K = 2, α = 0.05, and an exact prior estimate; Fig. 3 compares the exact loss with the bound.Source: Figure 3 · p. 8, D. Effect of Estimation Errors on BLADE · p. 8
  • The power-loss bound separates prior-estimation error from density-estimation error, with the density error weighted by the mode prior.The bound uses the final prior estimate and compares BLADE’s power with the optimal value.Source: D. Effect of Estimation Errors on BLADE · pp. 7–8
  • When the reference-sample error and reference-mixture mismatch both vanish, BLADE’s correct-label power tends to the optimal value.For an i.i.d. reference sample, the reference-sample error tends to zero almost surely as sample size grows.Source: D. Effect of Estimation Errors on BLADE · p. 8

E. Computational Complexity

The experiments compare attribution detectors on mixed-source text and assess both calibration and correct-label power. All detectors remain near the nominal Type I error across the tested candidate counts and null populations, while BLADE has the highest mean correct-label power among the practical detectors across the tested conditions.

E. Computational Complexity

  • O(nK log G) time and O(nK + G) working memory: BLADE’s tabulated density and inverse queries yield these per-document costs.For fixed G, both BLADE and BW scale linearly in document length n and candidate count K.Source: E. Computational Complexity · p. 8

VI. NUMERICAL EXPERIMENTS

  • BLADE has the highest mean correct-label power among practical detectors as candidate count, substitution rate, temperature, and generator model vary.Fig. 5 plots correct-label power against K at 20% substitution.Source: §VI · p. 8, Figure 5 · p. 9

A. Experimental Protocol

  • The evaluation uses mixed documents interleaving four 50-token watermarked spans with five 40-token unwatermarked spans, with substitutions used to edit watermarked tokens.Candidate count and substitution rate are varied across 42 layouts; temperature and generator model are varied on eight paired layouts.Source: A. Experimental Protocol · p. 8

B. Type I Error

  • 4.88%–5.19%: On human-written text, detector Type I error rates fall in this range; on edited text, mean rates range from 4.80% to 5.06%.BLADE’s edited-text means lie between 4.92% and 5.04%, with no systematic inflation as candidate count increases.Source: Figure 4 · p. 9, B. Type I Error · p. 9

C. Correct-Label Power

Across candidate counts, substitution rates, temperatures, and tested generator models, BLADE has the highest mean correct-label power among practical detectors. The mode-weight illustration shows BLADE sustaining support within watermarked spans, while the conclusion reports Type I error near nominal.

1) Candidate Count:

  • At K = 32, BLADE reaches 37.6% correct-label power, versus 31.5% for BW, 25.0% for Local-Count, and 14.7% for Max-Pivot.Its power changes by 4.7 percentage points from K = 4 to K = 32, compared with 8.1 points for BW.Source: 1) Candidate Count · p. 9, Figure 6 · p. 10

2) Substitution Rate:

  • BLADE leads the practical detectors at all nine substitution rates, and its gain over BW reaches 6.3 points at 24% substitution.Without substitution, BLADE nearly matches the Oracle at 44.3% versus 44.4%; the gain over BW remains 4.9 points at 32% substitution.Source: 2) Substitution Rate · p. 9, Figure 6 · p. 10

3) Generation Temperature:

  • BLADE has the highest mean correct-label power at every temperature, rising from 19.1% to 59.8%, with gains over BW of 1.6–7.4 points.The Oracle rises from 31.9% to 63.8%, narrowing its gap with BLADE from 12.7 to 3.9 points.Source: 3) Generation Temperature · p. 10, Figure 7 · p. 10

4) Generator Model:

  • Across the four tested generator models, BLADE has the highest mean correct-label power, gaining 3.7–6.1 percentage points over BW without hyperparameter retuning.Only the density estimate is re-estimated for each model.Source: 4) Generator Model · p. 10, Figure 8 · p. 10

D. Mode-Weight Illustration

  • On one document, BLADE gives more sustained mode support within watermarked spans, particularly Mode 2, and transitions more gradually near span boundaries.Among 42 retained, unmasked tokens, the mean true-mode weight is 90.1% for BLADE and 79.8% for BW.Source: D. Mode-Weight Illustration · p. 10, Figure 9 · p. 11

VII. CONCLUSION

  • BLADE achieves the highest mean correct-label power among practical detectors across candidate counts, substitution rates, generation temperatures, and four generator models, while keeping Type I error near nominal.The conclusion reports these results for experiments on mixed documents.Source: §VII · p. 11

APPENDIX A PROOFS OF FACTS 1 AND 2

The appendix analyzes Max-Pivot under a common alternative and proves the optimal weighted-density rule by choosing labels and then calibrating its rejection region.

APPENDIX A PROOFS OF FACTS 1 AND 2

  • With τ = 1−α, Max-Pivot’s Type I error approaches 1 as K grows; with τ = (1−α)^(1/K), it equals α, while correct-label power is approximately αd/K.The setup assumes independent uniform pivots under the null and FH,j(x) = x^d for every mode.Source: Appendix A · p. 11

APPENDIX B PROOF OF THEOREM 1

  • For a fixed rejection region, the power-maximizing label is arg max_j q_t,j f_j(r_j) almost everywhere.The proof then chooses a size-α rejection region by thresholding the largest prior-weighted alternative density at a common threshold.Source: Appendix B · pp. 11–12

DENSITY TERM

The density-term analysis bounds BLADE’s loss relative to the optimum using errors in its estimated inputs, then shows the density-error coefficient is sharp in a constructed example.

DENSITY TERM

  • With exact calibration, both the optimal rule and BLADE are feasible under the same conditional uniform null, so the power loss is nonnegative.The estimated-input rule maximizes weighted correct-label power computed with the estimated prior and density.Source: DENSITY TERM · p. 12
  • As the estimated reference density converges almost surely pointwise, its L1 error converges to zero.The argument uses finite expected reference-sample quantities, Fubini’s theorem, and Scheffé’s lemma.Source: DENSITY TERM · p. 12
  • In the constructed large-vocabulary example, the optimum tends to 0.4585 while BLADE’s rule has power 0.0585, so the loss and density-error term both tend to 0.4.This establishes sharpness of the density coefficient for that example.Source: DENSITY TERM · p. 12

APPENDIX D EXPLICIT THRESHOLD COMPUTATION

The appendix computes BLADE’s threshold by solving its calibration equation, with a bisection procedure and an upper-endpoint decision that preserves the Type I error bound.

APPENDIX D EXPLICIT THRESHOLD COMPUTATION

  • Bisection brackets the threshold using the calibration function and returns an upper endpoint whose conditional Type I error is at most α.The stated guarantee requires excluding target pivots from the estimated prior, but not accurate estimates of the prior or mode densities.Source: Appendix D · pp. 12–13
  • The experiment implementation tabulates log density on 4,001 grid nodes, interpolates density and inverse queries, and runs 60 bisection steps in log c.It uses the upper endpoint of the final interval for the decision.Source: Appendix D · p. 13
  • With interpolation and caps, the decision changes only the levels, and conditional Type I error remains at most α.Source: Appendix D · p. 13
Loading 2610.23601v1…