Source-linked AI summary

Optimal Watermark Localization in Mixed-Source Large Language Model Texts

Jose H. Blanchet, T. Tony Cai, Xiang Li, Hao Liu, Qi Long, Weijie J. Su

arXiv:2608.14906v1stat.MEcs.CLcs.LGstat.ML

TL;DR

Mixed-source LLM text can retain watermark evidence at only some token positions, but when that evidence can be localized remains unclear. This paper formulates localization as token-level multiple testing and shows discovery is harder than detection, while SPOT achieves the optimal discovery boundary.

  • Problem

    When mixed-source text retains watermark evidence only at some positions, it remains unclear when token-level localization is statistically possible.

    Source: §1 · p. 2
  • Method

    The paper models localization as multiple testing with pivotal statistics and develops SPOT, an adaptive thresholding method using an estimated surviving watermark fraction.

    Source: §1.1 · p. 3
  • Results

    Discovery is strictly harder than global detection, consistent classification is impossible for coordinatewise rules, and SPOT attains the optimal discovery boundary with near-optimal power.

    Source: §1.1 · pp. 4–5, §4.3 · p. 15
  • Takeaways & Limitations

    Global watermark detection can succeed in regimes where no coordinatewise rule can reliably locate even one surviving watermark position.

    Source: §4.3 · p. 15

    SPOT’s fraction-estimation step can become a practical bottleneck at low temperatures, and the current procedure is batch-based.

    Source: §7 · p. 25

Abstract

from arXiv · show

Watermarking provides a principled way to authenticate text generated by large language models (LLMs). In practice, however, the final text may be mixed-source, with watermark evidence surviving at only a subset of token positions after rewriting, insertion, deletion, or paraphrasing. Although prior work has studied global detection of watermark signals, when such signals can be localized remains unclear. We formulate watermark localization as a token-level multiple-testing problem based on pivotal statistics, with a latent indicator recording whether watermark dependence survives at each position. Under an asymptotic regime indexed by exponents for signal sparsity, next-token concentration, and effective-vocabulary growth, we derive a sharp boundary for global detection and phase transitions for discovery and classification within the class of coordinatewise pivot-based localization rules. We show that discovery is strictly harder than detection and that consistent classification is impossible across the parameter regime within this class. We then develop an adaptive thresholding method that does not require knowledge of the exponents or time-varying next-token distributions, but uses a data-driven estimate of the surviving watermark fraction. The method attains the optimal discovery boundary and near-optimal discovery power relative to homogeneous pivot-based rules. Simulations support the theoretical phase transitions, while experiments on model-generated texts demonstrate practical localization performance under common edit mechanisms.

1 Introduction

The paper develops a statistical framework for localizing watermark evidence that survives edits in mixed-source LLM text, addressing limitations of aggregate detection. It characterizes when detection, discovery, and classification are possible and introduces an adaptive method for optimal watermark discovery.

1 Introduction

  • Watermark localization identifies which token positions retain watermark evidence after rewriting, insertion, deletion, or paraphrasing, providing finer attribution and review information than document-level detection.The task is motivated by partially generated, collaboratively written, or substantially revised documents where aggregate conclusions are too coarse.Source: §1 · p. 2

1.1 Our Contributions

  • The paper formulates localization as token-level multiple testing using pivotal statistics with a known null law, and establishes phase transitions for detection, discovery, and classification under heterogeneous mixed-source text.Survival indicators distinguish positions whose watermark dependence remains from those where editing erases it; discovery is strictly harder than global detection, while consistent classification is impossible for coordinatewise pivot-based rules.Source: §1.1 · pp. 3–4
  • SPOT adaptively scans pivotal-statistic tails and controls estimated false discoveries, achieving the discovery boundary without knowing sparsity, concentration, vocabulary-growth exponents, or time-varying NTP distributions.It uses a data-driven estimate of the surviving watermark fraction and has near-optimal discovery power relative to homogeneous pivot-based procedures; experiments show better localization than baseline [61] under substitution, insertion, and deletion.Source: §1.1 · p. 5

1.2 Related Work

  • Unlike prior detection, change-point, and online-localization methods [26] [27] [61], this work derives sharp statistical limits and adaptive optimality for heterogeneous watermark localization.Its multiple-testing perspective connects to sparse signal discovery, while tail-count calibration avoids estimating unobserved, position-specific alternative laws.Source: §1.2 · pp. 5–6

2 Preliminaries

The preliminaries define watermark localization as recovering watermark-preserving positions from an edited final text and formulate it through pivotal statistics. They also introduce the Gumbel-max watermark as the analytically tractable example underlying the later localization analysis.

Watermarking protocol

  • The verifier analyzes only the final edited text to identify positions whose watermark signals survived user revision, without access to the original prompt, unedited output, or model parameters [22] [53].The protocol comprises watermark embedding, possible human editing, and localization by the verifier.Source: §2 · p. 6

Watermark embedding

  • Watermark embedding couples each generated token to a reproducible secret-key pseudorandom variable while an unbiased decoder preserves the token marginal distribution [52] [60].At position t, the decoder applies the next-token distribution and pseudorandom variable generated from local context and the shared key.Source: §2 · p. 6

Pivotal statistics for watermark evidence

  • Pivotal statistics distinguish human-written or edited positions from watermark-preserving positions because they follow a known null distribution under independence and a local-distribution-dependent alternative otherwise [24].The verifier reconstructs the pseudorandom sequence from the final text and shared key, reducing localization to a multiple-testing problem.Source: §2 · pp. 6–7

The Gumbel-max watermark

  • The Gumbel-max watermark provides explicit pivotal distributions: independent tokens yield Y_t ~ U(0,1), whereas watermark-generated tokens produce stochastically larger pivots according to the local NTP distribution.This explicit null-versus-alternative structure motivates its use for deriving sharp localization limits.Source: §2 · p. 7

3 Method

The method formulates watermark localization as token-level decisions on pivotal statistics with latent indicators for surviving watermark dependence. SPOT adaptively scans pivotal-statistic tails, estimating false-discovery levels from the surviving watermark fraction despite heterogeneous, time-varying NTP distributions.

3.1 Problem Formulation

  • Watermark localization identifies the signal set I of positions whose watermark dependence survives editing, distinguishing it from the non-watermarking set N.Each pivotal statistic follows the known null law μ0 when dependence is erased and a local alternative μ1,Pt when it survives, represented by latent θt ∈ {0,1}.Source: §3.1 · pp. 7–8
  • The paper restricts localization rules to coordinatewise measurable decisions δt = ϕt(Yt), producing a discovery set of positions declared watermark-preserving.This turns robust watermark detection into a token-level multiple decision problem; the formulation is motivated by Li et al..Source: §3.1 · p. 8

3.2 Our Method: SPOT

  • SPOT declares positions with unusually large F0(Yt), equivalently small null p-values, as discoveries and selects a threshold by scanning τ(u) = 1 − n^-u.It estimates the null contribution using the surviving-fraction estimate ε̂n and observed empirical tail mass, forming T̂n(u) as a proxy for mFDR.Source: §3.2 · p. 8
  • SPOT chooses the smallest scanned threshold whose estimated false-discovery level is at most λn − ηn, maximizing discoveries among thresholds passing the reliability check.The slack ηn guards against random fluctuations, while tail probabilities avoid direct density estimation under heterogeneous, time-varying NTP distributions; the method is related to Cai and Sun.Source: §3.2 · pp. 8–9

4 Theoretical Guarantees

This section formalizes watermark localization through a latent token-level survival model and criteria for detection, discovery, and classification. It derives phase transitions and theoretical guarantees for local rules, including the impossibility of classification and the adaptive detection and discovery performance of Tr-GoF and SPOT.

4.1 General Assumptions

  • The latent indicator θ_t records whether watermark dependence survives editing, yielding a token-level null-versus-signal structure for pivotal statistics.Surviving positions use the watermarked decoder and remain coupled with pseudorandomness, whereas edited positions retain the same marginal NTP distribution but are independent of it; the surviving fraction is ε_n up to constant factors.Source: §4.1 · p. 10
  • The asymptotic difficulty regime uses p for surviving-signal sparsity, q for NTP concentration, and α for effective-vocabulary tail growth.The method itself does not require knowing these exponents; they characterize theoretical difficulty through ε_n ≍ n^-p and the dominant–core–light vocabulary decomposition.Source: §4.1 · p. 11

4.2 Performance Measures

  • Global detection is document-level, whereas discovery controls mFDR while finding at least one surviving position, and classification additionally requires MDR to vanish.The hierarchy separates detecting whether signal exists anywhere from localizing signal positions and recovering nearly all watermark-preserving positions.Source: §4.2 · pp. 12–13

4.3 Statistical Limits and Phase Transitions

  • Detection is possible exactly when p + q < 1 and 2p + q < 1 + α, while outside this region the null and alternative distributions merge asymptotically.Vocabulary-tail growth expands the detectable region by contributing aggregate low-probability evidence; when α = 0, the boundary reduces to the fixed-vocabulary result of Li et al..Source: §4.3 · p. 14
  • Under Assumptions 4.1–4.3, discovery is achievable if p < α and p + q < 1, but impossible if p ≥ α or p + q > 1; with fixed vocabulary (α = 0), it is impossible.Source: §4.3 · p. 15
  • Discovery is strictly harder than detection because detection can aggregate weak evidence, whereas discovery must reliably identify an individual surviving position.Thus, detectable-but-undiscoverable regimes exist; increasing α strengthens both tasks by enlarging the light set, while the gap disappears only partially and discovery remains impossible at α = 0.Source: §4.3 · p. 15, Figure 4 · p. 16
  • Classification is impossible for every p, q ∈ [0, 1] and α ∈ [0, 1) within the local decision-rule class.Some surviving positions can produce weak evidence indistinguishable from nulls, forcing a choice between missing signals and selecting too many nulls.Source: §4.3 · pp. 15–16
  • Classification is impossible because surviving watermark dependence does not imply pivotal statistics are separated from the null, unlike sufficiently large mean shifts in Gaussian mixtures.Watermark pivotal statistics are typically bounded, so null and alternative laws may substantially overlap even when dependence survives.Source: §4.3 · p. 16

4.4 Adaptive Optimality

  • SPOT achieves discovery throughout the discoverable region without knowing p, q, α, or the next-token distributions P1:n.It scans data-selected tail thresholds and estimates the surviving watermark fraction; under the theorem’s conditions, discovery holds when p < α, p + q < 1, and the grid covers p + q.Source: §4.4 · pp. 16–17
  • Tr-GoF achieves global detection whenever max{p + q, 2p + q −α} < 1, without requiring fixed vocabulary.The method truncates the empirical pivotal-statistic distribution before comparing it with the null law µ0.Source: §4.4 · p. 16
  • SPOT achieves a constant fraction of the largest expected number of true discoveries among homogeneous pivot-based rules under the same false positive constraint.This establishes near-oracle discovery power beyond merely attaining the discovery boundary.Source: §4.4 · p. 17
  • The homogeneous benchmark matches practical verifier information because verifiers observe pivotal statistics but not next-token distributions, editing indicators, or hidden generation states.Fully time-varying and history-dependent rules are excluded because they may use unavailable information or incomparable position-specific tuning.Source: §4.4 · p. 18

5 Simulations

Simulations verify the predicted discovery phase transition and illustrate SPOT’s adaptive behavior. The experiments model surviving watermark signals, time-varying next-token distributions, and dependent survival indicators before evaluating empirical discovery boundaries.

5.1 Experimental Setup

  • The simulations set ε_n = 0.5n^-p, Δ_n = n^-q, α ∈ {0, 0.25, 0.5, 0.75}, and |W_n| = 2 + ⌊n^α⌋ under independent pseudorandom sampling.This implementation corresponds to r = 0 in Assumption 4.2 and isolates the statistical structure of localization.Source: §5.1 · p. 18
  • Next-token distributions vary through a stationary two-state Markov chain with persistence 0.95, while independent Markov survival indicators have mean ε_n and typically occur in short bursts.Given (P_t, θ_t), pivotal statistics follow the null law μ_0 when θ_t = 0 and the watermark-induced alternative μ_1,P_t when θ_t = 1.Source: §5.1 · pp. 18–19

5.2 Discovery Boundary and Empirical Phase Transitions

  • Discovery error combines marginal false discovery rate control with the probability of making no discovery, so smaller values indicate better discovery performance.SPOT tunes λ_n = C/log n over calibration grids for visualizing one- and two-dimensional empirical phase transitions.Source: §5.2 · p. 19
  • SPOT’s low-error region aligns with the theoretical discovery wedge p < α and p + q < 1, with sharper transitions as n increases.For fixed q = 0.4, the transition occurs at p⋆(0.4; α) = min{α, 0.6}; for fixed p = 0.6, it occurs near q = 0.4 when α > 0.6, while α ≤ 0.6 remains non-discoverable.Source: §5.2 · pp. 19–20, Figure 7 · p. 20

6 Open-source Model Experiments

Experiments on OPT-1.3B under controlled random, adversarial, and roundtrip edits show that SPOT generally matches or outperforms AOL, especially at moderate and high temperatures. Lower-temperature plug-in degradation is linked to inaccurate surviving-fraction estimation, while SPOT-plugin remains computationally efficient.

6.1 Experiment Setup

  • The experiments generate 400-token OPT-1.3B continuations from 1000 C4 news-like documents, apply repeated-context masking, and evaluate temperatures T ∈{0.3, 0.5, 0.7, 1}.Ground-truth preservation requires the current token and preceding five-token context to occur contiguously in the original sequence; evaluation reports TPR, IoU, and FPR.Source: §6.1 · pp. 20–21

6.2 Localization Performance

  • Random edits vary substitution, insertion, and deletion rates, adversarial edits target the strongest watermark signals, and roundtrip translation provides a practical transformation.Methods are compared using SPOT-oracle, SPOT-plugin, and AOL under matched empirical-FPR constraints.Source: §6.2 · pp. 21, 23, §6.1 · p. 21
  • At T = 1, both SPOT-oracle and SPOT-plugin outperform AOL in IoU and TPR under random, adversarial, and roundtrip edits.At T = 0.7, SPOT remains comparable or better, while SPOT-oracle is generally stronger than the plug-in variant at lower temperatures.Source: Figure 8 · p. 22, §6.2 · pp. 22–24, Table 1 · p. 23
  • Under random edits, increasing edit fractions reduce IoU, but SPOT’s TPR remains nearly flat at the same false-positive constraint.The stable TPR indicates recovery of a similar proportion of surviving watermark-preserving locations despite stronger edits.Source: §6.2 · p. 22, Figure 8 · p. 22
  • At lower temperatures, SPOT-plugin degrades mainly because the surviving-fraction estimator becomes inaccurate, whereas SPOT-oracle remains competitive with AOL.The estimator’s relative RMSE often approaches or exceeds one at T = 0.5 and T = 0.3.Source: §6.2 · pp. 23–24, Table 2 · p. 24
  • Conditional on shared pivot recomputation, SPOT-plugin takes 0.005–0.008 seconds per sample versus 0.009–0.016 seconds for AOL.Pivot recomputation dominates total verification time, so SPOT’s improved localization does not add computational overhead.Source: §6.2 · p. 25, Table 3 · p. 25

7 Discussion

The paper formulates mixed-source watermark localization as token-level multiple testing, characterizes limits for detection, discovery, and classification, and introduces SPOT, which achieves optimal discovery boundaries without known asymptotic exponents or time-varying token distributions. It also identifies open directions involving fraction estimation, structured recovery, online procedures, and non-token-level watermarks.

Main contributions

  • SPOT achieves the optimal discovery boundary and near-optimal discovery power among natural local rules, while simulations and real-LLM experiments support its theoretical and practical performance.The framework shows discovery is harder than global detection, and consistent classification is impossible for coordinatewise pivot-based rules.Source: §7 · p. 25

Open directions

  • Fraction estimation can bottleneck localization at low temperatures, motivating methods that avoid a separate estimate and online thresholds that adapt as text composition changes.The current batch procedure uses Li et al. [26] to estimate the surviving watermark fraction globally before selecting the threshold.Source: §7 · p. 25
  • Although coordinatewise rules cannot consistently classify tokens, block-like source structure [27] or region-level targets may enable stronger recovery guarantees using information across positions.The model permits frequent switching between watermark-preserving and null states, making exact token-level recovery especially demanding.Source: §7 · p. 26
  • Extending localization theory beyond token-level watermarks requires redefining the localization unit and null-versus-signal formulation for sentences, spans, or semantic embeddings [14] [39] [17].For Gumbel-max and other token-level schemes, extension is relatively direct when valid position-wise pivotal statistics exist.Source: §7 · p. 26

Supplementary Material · A An Example of a Generation–Editing Process · B Proof for Theoretical Guarantees

The supplementary material constructs a finite-memory generation–editing model that verifies the paper’s assumptions and supplies proofs for the theoretical guarantees. It also characterizes mixing, watermark-survival runs, and the pivotal-statistic mixture law used in those proofs.

A An Example of a Generation–Editing Process

  • A finite-memory state summary with exogenous editing innovations models dependence between generation and editing while satisfying Assumptions 4.1 and 4.3.The construction represents generation through X_t and editing through θ_t, driven by fresh i.i.d. innovations.Source: A An Example of a Generation–Editing… · pp. 32–33
  • The joint state S_t=(X_t,θ_t) is a time-homogeneous Markov chain, although the marginal editing process need not be Markov.The marginal process fails to be Markov when future editing depends on generation-state history beyond θ_t.Source: A An Example of a Generation–Editing… · p. 33
  • Under bounded survival probabilities and a uniform Doeblin condition, the model satisfies cε_n≤P(θ_t=1|F_{t−1})≤Cε_n and has exponentially decaying strong-mixing coefficients.The mixing bound is α_Ḡ(k)≤2(1−η)^k.Source: A An Example of a Generation–Editing… · pp. 33–34
  • Replacing exact survival exogeneity with bounded survival probabilities changes threshold constants but leaves detection, discovery, and classification exponents unchanged.The exact condition is recovered when c=C=1.Source: A An Example of a Generation–Editing… · p. 34
  • The Doeblin condition yields exponential tails for consecutive surviving-watermark runs, while the longest run across n positions is typically of order log n.Thus the model permits occasional longer bursts but excludes heavy-tailed or polynomially long persistent regimes.Source: A An Example of a Generation–Editing… · p. 34

Supplementary Material

  • The supplementary material organizes technical verification and proofs for the paper’s theoretical guarantees, retaining auxiliary lemmas and their proofs for transparent validation.The proof appendix follows the main-text result order and uses the dominant–core–light decomposition from Assumption 4.2.Source: B Proof for Theoretical Guarantees · p. 34

B Proof for Theoretical Guarantees

  • The proof appendix derives the watermarked-component pivotal-statistic law [24] and embeds it in a conditional mixture model under the observed pivotal-statistic history.For Gumbel–max pivots, the null law is uniform on (0,1), while the effective mixture weight satisfies cε_n≤π̄_t≤Cε_n.Source: B Proof for Theoretical Guarantees · pp. 34–35

B.1 Proof of Theorem 4.1: Detection boundary

The proof combines autoregressive Hellinger-affinity reduction with dominant–core–light vocabulary estimates to establish the sharp detection boundary. It shows that the null and alternative laws merge when max{p + q, 2p + q − α} > 1, while total variation tends to one in the complementary detectable regimes.

Proof strategy

  • The proof reduces joint detection to accumulated one-step Hellinger affinities and derives their scale uniformly over admissible next-token distributions.It uses conditional mixture representations, autoregressive affinity recursion, and dominant–core–light second-moment estimates, with analogous almost-sure conditional bounds.Source: §B.1 · pp. 35, 36, 37, 41

Detectable regime

  • In the complementary regimes, total variation satisfies TV(ρ0, ρ1) → 1, so the likelihood-ratio test has vanishing total Type I and Type II error.The argument selects a one-step sequence an with n a_n → ∞ and applies the autoregressive Hellinger reduction to obtain asymptotic separation.Source: §B.1 · pp. 36–38

Merging regime

  • The null and alternative laws merge whenever max{p + q, 2p + q − α} > 1.The proof separately controls the accumulated Hellinger terms for p > α and 0 < p ≤ α, yielding the two components of the boundary.Source: §B.1 · p. 36

Hellinger estimates

  • The cited passages establish a quadratic Hellinger scale and show that for p < α, γ_n n^α → ∞ yields h(Z) ≳ Z on An, while p = α gives h(Z) ≳ 1.Source: §B.1 · pp. 40–41

B.2 Proof of Theorem 4.2: Discovery boundary

The proof identifies discovery as possible when p < α and p + q < 1, using a right-tail threshold rule, and impossible when p + q > 1 or p ≥ α. It reduces all coordinatewise local rules to right-tail thresholds and derives the signal-tail behavior underlying these phase transitions.

Auxiliary lemmas

  • Every local rule is reduced to a coordinatewise right-tail threshold, while the signal tail scales as n^-u + n^-q for u < α + q and n^(α-u) thereafter.The reduction preserves null rejection probability and improves signal rejection probability; the tail bounds hold uniformly over admissible next-token distributions.Source: §B.2 · pp. 42, 46

Proof of Theorem 4.2

  • Under the cited argument, the probability of making at least one discovery tends to one, establishing the possibility part.Source: §B.2 · p. 43
  • If p + q > 1, any rule achieving discovery would have vanishing expected true and false discoveries, contradicting the requirement of discovering at least one signal.The argument uses EFPδ = o(ETPδ), bounds ETPδ, and then applies Markov’s inequality to show P(|Sδ| ≥ 1) → 0.Source: §B.2 · p. 44
  • If p ≥ α, signal rejection probabilities are uniformly dominated by n^α times the threshold level, forcing the false-discovery ratio away from zero.Consequently, mFDRδ cannot vanish, so no local rule achieves discovery in this regime.Source: §B.2 · p. 44

B.3 Proof of Theorem 4.3: Impossibility of classification

The proof shows that any local rule achieving classification would require nearly all watermark coordinates to be true discoveries while making false discoveries negligible, but both conditions are contradictory for q > 0 and q = 0.

Proof setup

  • By Lemma B.11, ETPδ = (1 + o(1))E|I| and EFPδ = o(E|I|); by Lemma B.8, it suffices to consider right-tail threshold rules δt = 1{Yt > 1 −an,t}, with 0 ≤an,t ≤1.Source: §B.3 · p. 48

Case q > 0

  • For q > 0, the signal-tail bound forces An ≳ n to obtain enough true discoveries, implying EFPδ ≳ n and contradicting the required negligible false-discovery rate.The contradiction holds in both sparse and dense cases because classification requires EFPδ = o(E|I|), with E|I| ≍ nεn or ≍ n.Source: §B.3 · p. 48

Case q = 0

  • For q = 0, a uniform signal-mass lower bound limits true discoveries to (1 − η⋆ + o(1))E|I|, contradicting the near-complete discovery requirement.Classification implies An = o(E|I|), making the additional term CεnAn negligible.Source: §B.3 · p. 48

B.4 Proof of Theorem 4.4: Adaptive optimality for global detection

The proof establishes valid null calibration because the truncated Jager–Wellner statistic is O(log log n) under H0. Under H1, carefully chosen tail points yield detectable excesses whose divergence exceeds the null critical order, so Type II error vanishes.

Null calibration

  • Under H0, the truncated statistic is bounded by the untruncated Jager–Wellner statistic and is at most order log log n with high probability.This establishes the required Type I error control using the null p-value calibration and Jager–Wellner’s bound.Source: §B.4 · pp. 49, 51

Alternative regimes

  • In the regime p < α, choosing r_n = n^−(p+q−η) makes the empirical upper-tail excess asymptotically order n^−(p+q), while concentration renders fluctuations negligible.The choice is valid when p + q < 1, which is the detection condition in this regime.Source: §B.4 · p. 50
  • In the regime p ≥ α, choosing r_n = n^−(α+q) likewise produces an excess at least order n^−(p+q), with negligible stochastic fluctuation under 2p + q − α < 1.The selected tail point lies inside the scan range because the detection condition implies α + q < 1.Source: §B.4 · p. 50

Power conclusion

  • Across both regimes, nK+_2(F_n(r_n), r_n) diverges in probability, and local divergence comparison transfers this growth to the scanned statistic, eliminating Type II error.The scanned statistic therefore exceeds the null critical order log log n with probability tending to one.Source: §B.4 · p. 51

B.5 Proof of Theorem 4.5: Adaptive optimality for discovery · B.6 Proof of Theorem 4.6: Near-optimal number of discoveries

The proofs show that SPOT’s data-driven threshold tracks the oracle crossing, yielding vanishing mFDR and discovery with probability tending to one. They further establish that SPOT achieves a constant-factor optimal number of true discoveries among homogeneous local rules.

B.5 Proof of Theorem 4.5: Adaptive optimality for discovery

  • Uniform tail-count concentration and proxy stability let SPOT’s empirical false-discovery proxy approximate the oracle proxy across its exponent grid.The proof proceeds by controlling empirical tail counts, transferring accuracy to the proxy, and localizing the oracle crossing before transferring it to SPOT.Source: §B.5 · pp. 52–53
  • Under p < α and p + q < α + q, the selected exponent satisfies bun ∈(p + q, α + q) with probability tending to one.This localization places the adaptive threshold in the regime where the oracle calibration applies.Source: §B.5 · p. 53
  • To control the data-dependent exponent, the proof sandwiches SPOT between deterministic comparison thresholds on a good event whose complement has probability o(n−1).This permits application of fixed-exponent tail bounds while making the exceptional event’s contribution negligible.Source: §B.5 · p. 53
  • SPOT has ETPδSPOT →∞ and ETPδSPOT/EFPδSPOT →∞, so mFDRδSPOT →0 and its discovery set is nonempty with probability tending to one.The proof concludes P(|SδSPOT| ≥1) →1, establishing discovery under the adaptive rule.Source: §B.5 · p. 55
  • The oracle crossing occurs at u = p + q + log log n/log n + O(1/log n), with grid discretization adding at most Δu,n.The same expansion holds when the target level varies within [λn/2, 2λn].Source: §B.5 · pp. 56–57

B.6 Proof of Theorem 4.6: Near-optimal number of discoveries

  • For any homogeneous rule satisfying mFDRδ ≤ λn, monotone likelihood-ratio rearrangement reduces the benchmark analysis to right-tail threshold rules.The proof relates null rejection mass to false positives and uses the mFDR constraint to upper-bound true discoveries.Source: §B.6 · p. 57
  • SPOT achieves a constant-factor optimal number of true discoveries among homogeneous local rules while maintaining its false-discovery bound.The comparison combines an upper bound for every benchmark rule with SPOT’s lower bound ETPδSPOT ≳ n1−p−q+o(1).Source: §B.6 · p. 57

C Additional Details for the Simulation Studies · D Details and Additional Results of Language Model Experiments · D.1 Additional Experimental Details

The supplementary studies specify simulation processes that reproduce the paper’s theoretical mixture model and report phase transitions consistent with the predicted discovery boundary. Real-LLM experiments detail watermarking, editing, label construction, and false-positive-controlled evaluation procedures.

C Additional Details for the Simulation Studies

  • Simulations use temporally heterogeneous dominant–core–light NTP distributions driven by a persistent two-state regime process while preserving the theoretical asymptotic exponents.The regime chain has persistence ρ_Z = 0.95, and each regime can vary token decompositions and probability constants while remaining within the assumed regime.Source: C Additional Details for the… · p. 58
  • Survival indicators are generated by an independent two-state Markov chain initialized at stationarity, with P(θt = 1) = εn, yielding exactly εn watermark-preserving positions and short bursts.Source: C Additional Details for the… · p. 58
  • The pivotal-statistic simulator samples null pivots from µ_0 and alternative pivots from scalar selected-token probability levels, exactly realizing the mixture model used in theory.For watermark-preserving positions, it draws w_t ∼ P_t and U_t ∼ Unif(0, 1), then sets Y_t = U_tP_t,w_t.Source: C Additional Details for the… · p. 59
  • For α = 0.25, empirical discovery transitions align with the predicted boundary, whereas discovery remains difficult across displayed ranges for α = 0.Figure 9 averages 200 Monte Carlo trials, with sharper transitions as n increases for α = 0.25.Source: C Additional Details for the… · p. 59, Figure 9 · p. 59

D.1 Additional Experimental Details

  • Real-LLM watermarking uses a five-token context hash with repeated-context masking, sampling directly from the temperature-scaled NTP distribution when masking suppresses watermarking.This follows the 1-sequence repeated-context masking strategy of Dathathri et al. and uses the hash function from [60].Source: §D.1 · p. 60
  • Experiments generate 400-token OPT-1.3B continuations from 1,000 realnewslike C4 examples after retaining 50-token prompts from sufficiently long truncated sequences.The retained examples have truncated length at least 450, and tokenization uses a truncation length of 2028.Source: §D.1 · p. 60
  • Post-edit labels mark a position as watermark-preserving only when its local block of length m + 1 remains contiguous in the original watermarked sequence.Edited text is decoded, re-tokenized, and padded or truncated to the verifier’s target length, matching how pseudorandomness is reconstructed from the preceding m tokens.Source: §D.1 · p. 60
  • Localization methods are compared under empirical FPR constraints by selecting the calibration value with the largest IoU among those meeting each target FPR level.The evaluation reports empirical FPR, TPR, and IoU across random edits, adversarial edits, and roundtrip translation.Source: §D.1 · p. 60

D.2 Additional Details for Compared Methods

This section details SPOT-plugin’s estimation of the surviving watermark fraction, AOL’s adaptive online localization baseline, and threshold calibration for fair comparison. It also explains the exclusion of SeedBS because of low accuracy and prohibitive runtime.

  • SPOT-plugin estimates the surviving watermark fraction ε_n from observed pivotal statistics using Li et al.’s [26] optimal fraction estimator and an auxiliary fully watermarked sample.The estimator models the statistics as (1 − ε_n)F_0 + ε_nF_1, estimates the alternative law empirically, and numerically solves the resulting estimating equation.Source: §D.2 · pp. 60–61
  • AOL transforms each pivotal statistic into a Gumbel score, applies Aligator smoothing from multiple random circular starts, averages the fitted values, and labels positions exceeding threshold ζ.The averaged fitted values form the localization scores used for token-level decisions.Source: §D.2 · p. 61
  • For fixed empirical FPR constraints, thresholds are swept over predetermined grids for AOL and SPOT, with each method evaluated by its best feasible IoU.The optimal parameter for each method lies inside its tuning grid, indicating that the grids provide sufficient tuning coverage.Source: §D.2 · p. 61
  • SeedBS [27] is excluded because experiments found low accuracy and prohibitive runtime.Source: §D.2 · p. 61

D.3 Additional Results

Additional results show that SPOT-oracle and SPOT-plugin generally match or outperform AOL across random edit mechanisms, FPR levels, and temperatures, with stronger performance at higher temperatures. TPR at fixed empirical FPR is the primary localization metric, while IoU provides a complementary, stricter overlap measure.

Evaluation metrics

  • TPR is the primary controlled-error metric because it measures recovered watermark-preserving locations under fixed empirical FPR, whereas IoU gives a stricter complementary overlap assessment.IoU penalizes missed and extra selected locations, can depend on the size of the true watermark-preserving set, and may partially penalize false positives again after FPR control.Source: §D.3 · p. 61

Random edit mechanisms

  • Across random substitution, insertion, and deletion, SPOT-oracle and SPOT-plugin generally outperform or remain competitive with AOL under varying target FPR levels.At T = 1, results cover target FPR levels 0.01, 0.03, 0.06, and 0.09 using TPR and IoU; corresponding T = 0.7 results are also reported.Source: §D.3 · pp. 61–62, Figure 10 · p. 62, Figure 11 · p. 63

Temperature comparisons

  • At T = 0.7, SPOT’s advantage over AOL remains visible but is smaller, and absolute localization performance is lower than at T = 1.The lower-temperature setting provides weaker usable watermark evidence, making localization more difficult.Source: §D.3 · p. 62, Figure 12 · p. 64, Figure 13 · p. 65
  • SPOT-oracle is stable across temperatures, while SPOT-plugin performs well with accurate fraction estimates and both methods are strongest relative to AOL at higher temperatures.These trends are reported across IoU and TPR under empirical FPR constraints λ ∈{0.04, 0.07}.Source: §D.3 · p. 62, Table 4 · p. 66, Table 5 · p. 66
Loading 2608.14906v1…