Paper deep dive
Towards Anytime-Valid Statistical Watermarking
Baihe Huang, Eric Xu, Kannan Ramchandran, Jiantao Jiao, Michael I. Jordan
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/20/2026, 11:31:27 PM
Summary
The paper introduces 'Anchored E-Watermarking', a novel statistical watermarking framework for Large Language Models (LLMs) that enables anytime-valid inference. Unlike traditional fixed-horizon methods, this approach uses e-values and a test supermartingale to allow for valid early stopping without invalidating Type-I error guarantees. By leveraging an anchor distribution to approximate the target model, the framework optimizes the e-value for worst-case log-growth rate, resulting in a 13-15% reduction in the average token budget required for detection compared to state-of-the-art baselines.
Entities (7)
Relation Signals (5)
Anchored E-Watermarking → enables → Anytime-valid inference
confidence 95% · our framework enables valid, anytime-inference by constructing a test supermartingale
Anchored E-Watermarking → uses → E-value
confidence 95% · In this paper, we bridge this gap by developing the first e-value-based watermarking framework, Anchored E-Watermarking
Anchor Distribution → approximates → Target Model
confidence 90% · By leveraging an anchor distribution to approximate the target model
Supermartingale → guarantees → Type-I Error Control
confidence 90% · constructing a test supermartingale for the detection process... preserve Type-I error guarantees under optional stopping
Anchored E-Watermarking → reduces → Token Budget
confidence 90% · reducing the average token budget required for detection by 13-15% relative to state-of-the-art baselines.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The proliferation of Large Language Models (LLMs) necessitates efficient mechanisms to distinguish machine-generated content from human text. While statistical watermarking has emerged as a promising solution, existing methods suffer from two critical limitations: the lack of a principled approach for selecting sampling distributions and the reliance on fixed-horizon hypothesis testing, which precludes valid early stopping. In this paper, we bridge this gap by developing the first e-value-based watermarking framework, Anchored E-Watermarking, that unifies optimal sampling with anytime-valid inference. Unlike traditional approaches where optional stopping invalidates Type-I error guarantees, our framework enables valid, anytime-inference by constructing a test supermartingale for the detection process. By leveraging an anchor distribution to approximate the target model, we characterize the optimal e-value with respect to the worst-case log-growth rate and derive the optimal expected stopping time. Our theoretical claims are substantiated by simulations and evaluations on established benchmarks, showing that our framework can significantly enhance sample efficiency, reducing the average token budget required for detection by 13-15% relative to state-of-the-art baselines.
Tags
Links
- Source: https://arxiv.org/abs/2602.17608v1
- Canonical: https://arxiv.org/abs/2602.17608v1
Trouble viewing inline? Open PDF directly →
Full Text
96,460 characters extracted from source content.
Expand or collapse full text
Towards Anytime-Valid Statistical Watermarking Baihe Huang * Eric Xu † Kannan Ramchandran ‡ Jiantao Jiao § Michael I. Jordan ¶ Abstract The proliferation of Large Language Models (LLMs) necessitates efficient mech- anisms to distinguish machine-generated content from human text. While statistical watermarking has emerged as a promising solution, existing methods suffer from two critical limitations: the lack of a principled approach for selecting sampling distri- butions and the reliance on fixed-horizon hypothesis testing, which precludes valid early stopping. In this paper, we bridge this gap by developing the first e-value-based watermarking framework, Anchored E-Watermarking, that unifies optimal sampling with anytime-valid inference. Unlike traditional approaches where optional stopping invalidates Type-I error guarantees, our framework enables valid, anytime-inference by constructing a test supermartingale for the detection process. By leveraging an anchor distribution to approximate the target model, we characterize the optimal e-value with respect to the worst-case log-growth rate and derive the optimal expected stopping time. Our theoretical claims are substantiated by simulations and evaluations on es- tablished benchmarks, showing that our framework can significantly enhance sample efficiency, reducing the average token budget required for detection by 13-15% relative to state-of-the-art baselines. 1 Introduction The revolutionary success of Large Language Models (LLMs) at generating human-like texts (Brown et al., 2020; Bubeck et al., 2023; Chowdhery et al., 2023) has raised several societal concerns regarding the misuse of LLM outputs. Unregulated LLM outputs pose risks ranging from the contamination of future training corpora (Shumailov et al., 2023; Das et al., 2024) to the propagation of disinformation (Zellers et al., 2019; Vincent, 2022) and academic misconduct (Jarrah et al., 2023; Milano et al., 2023). Consequently, there is an * baihehuang@berkeley.edu. University of California, Berkeley. † erx@berkeley.edu. University of California, Berkeley. ‡ kannanr@berkeley.edu. University of California, Berkeley. § jiantao@eecs.berkeley.edu. University of California, Berkeley. ¶ jordan@cs.berkeley.edu. University of California, Berkeley. 1 arXiv:2602.17608v1 [cs.LG] 19 Feb 2026 urgent need for reliable detection mechanisms capable of distinguishing LLM-generated text from human-authored content. To address this challenge, Aaronson (2022a) and Kirchenbauer et al. (2023) propose sta- tistical watermarking as a theoretically-grounded method to distinguish machine-generated content from a target distribution. These methods operate by injecting statistical signals into the generated texts in the decoding phase of LLMs. Mechanistically, the watermark generator couples the output tokens by a sequence of pseudorandom seeds. During detection, the detector reconstructs the seeds and performs a hypothesis test to check the dependence between the seeds and the observed tokens. This formulation allows the detection prob- lem to be treated as a rigorous statistical hypothesis test (Huang et al., 2023) where the detection power and sample complexity are governed by the randomness in the target distri- bution. Various designs for the underlying seed distributions have been explored, such as binary (Christ et al., 2023), exponential (Kuditipudi et al., 2023), and Gaussian (Block et al., 2025). Recently, Huang et al. (2025) advanced the concept of using an auxiliary open-source model as an anchor to generate random seeds and coupling them with tokens via speculative decoding (Leviathan et al., 2023). This approach is motivated by the theoretical insight that watermarking achieves the optimal power when the seed distribution approximates the target distribution (Huang et al., 2023). By exploiting the distributional proximity between modern LLMs, anchor-based methods have shown promise in improving both detection efficiency and robustness to removing-attacks (Piet et al., 2023). Empirically, watermarked texts can be detected within short token horizons (< 100tokens) and high success rate (nearly50% under paraphrasing) under various attacks. Despite these successes, state-of-the-art watermarking remains constrained by two fundamental limitations. First, the design of generation and detection schemes lacks a unifying guiding principle. Huang et al. (2025) utilize a hashed green-red-list seed adapted from Kirchenbauer et al. (2023), but this heuristic lacks rigorous justification. What is needed is a characterization of optimal generation and detection schemes under given anchor distributions. Second, there exists a methodological disconnect between generation and detection. While text generation is inherently autoregressive and variable in length, current detection paradigms are fixed-horizon and ad hoc. In practice, for example, a detector may wish to process a stream of tokens and stop as soon as confidence is high. However, with the standard statistical paradigm based on p-values, it is not allowed to continuously monitor the test statistic and decide when to stop based on the current value—this is known as “p-hacking” and it invalidates the Type-I error guarantee. This inability to perform post-hoc sequential analysis severely limits detection efficiency. These gaps highlight a critical research challenge: How can we design provably efficient watermarking schemes leveraging anchor distributions that allow for valid early stopping? In this work, we provide the first formal resolution to this question. We formulate the problem of Anchored E-Watermarking, where both the generator and detector share access to an anchor distributionp 0 , aiming to watermark a family of distributions in theδ-proximity 2 ofp 0 . Departing from classical p-value analysis, we adopt e-values as the central detection paradigm. E-values (Vovk, 1993; Shafer et al., 2011; Vovk & Wang, 2021) are nonnegative random variablesEsatisfyingE H 0 [E]≤ 1under the null. Unlike p-values, e-values arise from supermartingales, and it is therefore possible to preserve Type-I error guarantees under optional stopping based on ongoing analysis of data. We analyze the optimal e-value for watermark detection with respect to the worst-case log-growth rate (Kelly, 1956) and the expected stopping time (Gr ̈ unwald et al., 2020; Waudby-Smith et al., 2025), thus fully characterize the average per-step growth rate of evidence and sample efficiency. Our main theoretical contributions are summarized informally as follows: Theorem 1.1 (Informal version of Theorem 4.1 and Theorem 4.3). The optimal worst-case log-growth rate E H 1 [logE] under the alternative H 1 is given by: J ∗ = h + 1− δ 2 log 1− δ 2 + δ 2 log δ 2(n− 1) , whereh = H(p 0 )is the Shannon entropy of the anchor distributionp 0 andδ > 0is a robustness tolerance parameter. Furthermore, the optimal expected stopping time to achieve a Type-I error α scales as log(1/α) J ∗ . To the best of our knowledge, this work represents the first application of e-values to the domain of statistical watermarking. By enabling valid sequential testing, our framework significantly improves detection efficiency, allowing the system to flag machine-generated text with fewer tokens than fixed-horizon counterparts. With the ability to early-stop, this sequential paradigm enhances robustness against adaptive attacks: because the detector can terminate immediately upon accumulating sufficient evidence, the watermark remains effective even if the attacker perturbs the text heavily in later segments (post-stopping). Consequently, our approach offers a theoretically rigorous and practically superior alterna- tive to existing heuristic detection methods. Through experiments on real watermarking benchmark (Piet et al., 2023), we show that the theoretical scheme implied by Theorem 1.1 achieves consistently higher sample efficiency than state-of-the-art methods, reducing the token consumption by 13-15% across various temperature settings. 1.1 Related works Statistical watermarking. Watermarking offers a white-box provenance mechanism for detecting LLM-generated text (Tang et al., 2023), complementing post-hoc detectors and provenance tools developed for neural text generation (Zellers et al., 2019). Classical digital watermarking and steganography provide a broad toolbox for embedding and extracting imperceptible signals under benign or adversarial channel edits (Cox et al., 2007). Early works in NLP literature studied watermarking and tracing of text via editing or synonym substitutions (Venugopal et al., 2011; Rizzo et al., 2019; Abdelnabi & Fritz, 2021; Yang et al., 2022; Kamaruddin et al., 2018). In contrast, modern statistical (a.k.a. generative) watermarking (Aaronson, 2022a; Kirchenbauer et al., 2023) injects a secret, testable dis- tributional bias into the sampling process, and detects this bias via hypothesis testing on 3 the generated token sequence. A rapidly growing theory studies efficiency and optimality of watermarking tests and encoders: results include finite-sample guarantees, information- theoretic limits, and constructions that are distortion-free or unbiased (Huang et al., 2023; Zhao et al., 2023; Li et al., 2024; Block et al., 2025; Kuditipudi et al., 2023; Hu et al., 2023; Xie et al., 2025). Negative and hardness results highlight fundamental limitations against adaptive or distribution-matching adversaries (Christ et al., 2023; Christ & Gunn, 2024; Golowich & Moitra, 2024), motivating alternative design considerations such as distribution-preserving and public-key schemes (Wu et al., 2023; Liu et al., 2023; Fairoze et al., 2023). Empirical robustness is commonly assessed under paraphrasing, editing and translation, with recent work studying cross-lingual failure modes and defenses (He et al., 2024b), and benchmarks/frameworks such as MarkMyWords and scalable pipelines for watermark evaluation and deployment (Piet et al., 2023; Zhang et al., 2024; Lau et al., 2024; Dathathri et al., 2024). Finally, a complementary line of work leverages semantic structure and auxiliary models to boost detection power under benign distributional structure, including semantic/paraphrastic watermarks and speculative-sampling-based schemes (Ren et al., 2024; Liu & Bu, 2024; Hou et al., 2024b,a; Fu et al., 2024; Huang et al., 2025; Leviathan et al., 2023). Our anchored e-value approach builds on these works by explicitly treating detection as anytime-valid sequential testing (Chen & Wang, 2024), and by allowing model-assisted calibration under distribution shift (Huang et al., 2025; He et al., 2024a, 2025). E-values and sequential hypothesis testing. Sequential hypothesis testing studies infer- ence procedures that remain valid under data-dependent stopping and streaming data (Wald, 1947; Robbins, 1952; Breiman, 1961). Classical likelihood-ratio andp-value based methods can fail under optional stopping or composite hypotheses, motivating the use of nonnegative supermartingales / test martingales whose stopped values are valid evidence measures (Shafer et al., 2011; Vovk & Wang, 2021; Shafer, 2021; Gr ̈ unwald et al., 2020; Ramdas et al., 2023). The resulting e-values and e-processes unify betting scores, likelihood ratios, and (stopped) Bayes factors. Additionally, e-values and e-processes support modular operations such as merging and calibration (Vovk & Wang, 2021; Ramdas & Wang, 2025). This framework has enabled principled notions of power and optimality, including log-/growth-rate criteria and sharp asymptotic rates for broad classes of betting-based tests (Gr ̈ unwald et al., 2020; Waudby-Smith et al., 2025). E-values also interact fruitfully with multiple testing and online testing, yielding e-value analogues of the BH and wealth-based procedures and their extensions to structured settings (Wang & Ramdas, 2022; Ramdas et al., 2017, 2018, 2019). Recent work further broadens the reach of e-values to new ML settings, such as conformal prediction and sequential monitoring of strategic systems (Gauthier et al., 2025, 2026; Aolaritei & Jordan, 2025), and connects e-values to model-assisted efficiency gains via prediction-powered inference (Wasserman et al., 2020; Csillag et al., 2025). Our work draws on these foundations to construct e-values tailored to watermark detection which ensures validity under arbitrary stopping rules and enables sequential evidence accumulation in practical provenance audits. 4 2 Preliminaries 2.1 Statistical watermarking Statistical watermarking for Large Language Models (LLMs) provides a probabilistic framework for distinguishing machine-generated text from human-written text. Unlike post-hoc detection methods that rely on classifiers trained on model artifacts, watermarking actively embeds a statistical signal into the generation process. This signal is designed to be imperceptible to humans yet statistically significant to an algorithmic detector possessing a secret key. Statistical watermarking as a hypothesis testing problem. Formally, statistical water- marking is cast as a hypothesis testing problem. Letqdenote the target distribution over the sample spaceV , and letS represent the space of pseudorandom seeds. The watermark- ing protocol modifies the standard decoding mechanism of the LLM such that the output tokensV ∈Vand the pseudorandom seedsS ∈Sare sampled jointly from a watermarked distributionP W . The detection task seeks to determine if a given observed textvwas generated by the watermarked model:D : V ×S → Watermarked, Unwatermarked. This reduces to testing for independence between the tokensvand the seedssreconstructed via the detector’s key. We define the null and alternative hypotheses as follows (Huang et al., 2023): •Null hypothesisH 0 : The textvis generated independently of the seedss(e.g., by a human or an unwatermarked model). •Alternative hypothesisH 1 : The textvand seedssare sampled from the joint watermarked distributionP W , implying they come from the watermarked model. It is pertinent to distinguish this distributional watermarking approach from classical instance-level watermarking techniques applied to static media, such as images or audio Cox et al. (2007). While classical methods embed a signature into a specific, fixed outcome (post-generation), statistical watermarking modifies the stochastic sampling process itself, ensuring that any realization from the model carries the statistical evidence of its origin without requiring rigid alterations to the final output. Statistical guarantees. A robust watermarking scheme is characterized by its ability to provide three fundamental guarantees. First, to preserve generation quality and ensure watermarked content remains indistin- guishable from ordinary samples, the distance (e.g., KL-divergence) between the water- marked distributionP W and the original target distributionqmust be minimized. Ideally, we seek a scheme that introduces zero distributional shift (Hu et al., 2023). 5 Definition 2.1 (Distortion-free). A watermark is considered distortion-free (or unbiased) if the outcome marginal of the watermarked distributionP W matches the target distributionq. Formally, a distortion-free watermark satisfies: X s∈S P W (A,s) = q(A), ∀A⊆V. Second, it is often required in practice that the detector operates without access to the watermarked distribution since the underlying model’s parameters are generally unknown to the detector. This means that the detection scheme needs to be designed for a family of target distributions in a model-agnostic way (Kuditipudi et al., 2023), leading to the next concept. Definition 2.2 (Model-agnosticity). A watermark is model-agnostic if the seed-marginal of P W is chosen independently of the target distributionq. That is, the distribution of seedsS does not depend on the model’s logits. Third, the reliability of the watermark is quantified by standard statistical error rates. The Type I error (false positive rate) measures the probability of incorrectly identifying non-watermarked text (e.g., human-written) as watermarked. Given the high stakes of false accusations (e.g., in academic integrity), this error must be bounded by a small significance level α: P H 0 (D(V,S) = Watermarked)≤ α. The Type I error (false negative rate) measures the probability that watermarked text fails to be detected. Minimizing this error is equivalent to maximizing the statistical power of the test. For a target error rate β, we require: P H 1 (D(V,S) = Unwatermarked)≤ β. 2.2 Sequential hypothesis testing and e-values Consider a measurable space(Ω,F )and a family of probability distributionsP. We are interested in testing a null hypothesisH 0 : P ∈ P 0 ⊂ Pagainst an alternative H 1 : P ∈P 1 =P 0 . An e-value is a random variable whose expectation is bounded by unity under the null hypothesis (Vovk & Wang, 2021). Definition 2.3 (E-value). A nonnegative random variableEis an e-value forH 0 if for all P ∈P 0 , E P [E]≤ 1. Intuitively, an e-value represents the amount of wealth a gambler would have after betting against the null hypothesis, in a game where the game is fair or unfavorable under H 0 , and starting with an initial wealth of one. On the other hand, ifEbecomes large, this suggests that the null hypothesis is unlikely to be true. 6 Sequential evidence and stopping time guarantees.The primary advantage of e-values lies in their behavior regarding stopping times. In a sequential setting, we are given a filtration(F t ) t≥0 and construct a sequence of e-values(E t ) t≥0 . If(E t ) t≥0 is a nonnegative supermartingale with respect to the null distributions (often called a test martingale), it allows for anytime-valid inference. This property derives from Ville’s inequality, a time- uniform generalization of Markov’s inequality. Theorem 2.4 (Ville’s inequality). Let(E t ) t≥0 be a nonnegative supermartingale with respect to P ∈P 0 such that E 0 ≤ 1. Then for any α∈ (0, 1), P ∃t≥ 0 : E t ≥ 1 α ≤ α. This result guarantees that a researcher can track the e-value process continuously and stop at any data-dependent timeτ(a stopping time) while maintaining Type-I error control. Specifically,E P [E τ ] ≤ 1holds for any stopping timeτ(possibly unbounded), a kind of guarantee which is not available for p-values. 3 Problem Formulation In this section, we formulate the problem of Anchored E-Watermarking. Similar to statistical watermarking, the goal is to embed statistical signals into samples from a target distribution to enable detection. However, in Anchored E-Watermarking, the generator and the detector share access to an anchor distribution that serves as a robust a priori estimate of the target distribution. This setting is common in practice; for example, when watermarking Large Language Models or image generators, the target distribution is known to be human language or natural images, respectively. Consequently, watermarking efficacy can be improved by leveraging this structure. Besides, Anchored E-Watermarking uses e-values for detection, thus enjoying improved efficiency in sequential testing. In the following, we introduce the specific components of Anchored E-Watermarking. Anchor distribution.In the Anchored E-Watermarking framework, we assume that both the generator and the detector share access to an anchor distributionp 0 ∈ ∆(V ), which is in the same probability simplex as the target distributionq. Thisp 0 serves as the best a priori estimate of the target distribution. For instance, in the context of watermarking Large Language Models (LLMs),p 0 could be an open-source, smaller-scale LLM such as Qwen3- 8B (Team, 2025). Leveraging its role as a known reference, we designatep 0 as the marginal distribution for the watermark signal (or random seed), denoted ass. Therefore, the seed spaceSis equal toVin our framework. Throughout the paper, we assumep 0 satisfies the conditioninf v∈V p 0 (v) > δfor a positive robustness tolerance parameterδ. This condition ensuresp 0 has enough randomness as required for watermarking (Aaronson, 2022a) and that the δ-neighborhood defined below is a strict subset of the probability simplex. 7 Target distribution.The target distributionq ∈ ∆(V )represents the desired distribution from which (watermarked) output samplesvare generated. Consistent with the definition of the anchor, we premise thatqremains sufficiently proximal top 0 . Formally, we assumeq resides within the δ-neighborhood of the anchor: Q(p 0 ,δ) =q ∈ ∆(V ) :∥q− p 0 ∥ 1 ≤ δ. Here∥·∥ 1 is theℓ 1 distance and the radiusδ > 0represents a robustness tolerance parameter that controls how the true target distributionqcan deviate from the anchor. This assumption holds for most practical statistical watermarking scenarios; for example, in the LLM domain, high-performing models tend to converge towards the same underlying distribution of natural language, resulting in low statistical divergence between them. Generator. The objective of the generator is to sample an outputvfrom the target distri- butionqwhile embedding a statistical signals. To achieve this, the generator constructs a joint distribution (or coupling)wovervands, subject to the constraint that the marginals recover the target and anchor distributions, respectively. The feasible set of valid couplings is defined as: P (p 0 ,q) = w ∈ ∆(V ×V ) : X s∈V w(v,s) = q(v), X v∈V w(v,s) = p 0 (s) . Note that the generator has access toq, as is common in practice (e.g., when the generator is a service provider). During generation, the system samples the outcomevand the signal sjointly fromw. This procedure ensures that the marginal distribution of the outcomev is unbiased (satisfying Theorem 2.1), while the watermark signal is embedded within the statistical dependency between v and s. E-value. In the detection phase, the detector receives an outcome-signal pair(v,s)and computes an e-valuee(v,s) ≥ 0. The objective is to distinguish between the following hypotheses: H 0 : v and s are sampled independently, H 1 : (v,s) are sampled from the joint coupling w. The detector rejects the null hypothesis ife(v,s) > 1/α. To guarantee a Type-I error rate of at mostα, the expectation of the e-value under the null hypothesis must be bounded by 1. Adhering to the model-agnostic constraint (Theorem 2.2), the scoring functione(·,·) must be defined prior to observing the specific target distributionq. The design of the e-value relies solely on the constraint that the target distribution lies within the anchor’s neighborhood, i.e.,q ∈Q(p 0 ,δ). Consequently, to ensure validity, the e-value must satisfy the expectation bound uniformly across the entire uncertainty setQ: sup q∈Q(p 0 ,δ) E v∼q,s∼p 0 [e(v,s)]≤ 1.(1) We letE denote the set of all nonnegative functions e :V ×V → R satisfying Eq. (1). 8 3.1 Robust log-optimality While the definition of an e-value ensures validity (safety) under the null, it does not guarantee power (growth) under the alternative. To rejectH 0 effectively, we desire the e-value to be large when the data is generated from the alternative distributionH 1 . The standard criterion for selecting an e-value is log-optimality, often referred to as the “Kelly criterion” in the finance literature (Kelly, 1956). This approach seeks to maximize the expected logarithmic growth rate of evidence against the null, under the alternative. For simple hypotheses whereP 0 = PandP 1 = Q, the likelihood ratioe ∗ = dQ dP is log-optimal, such that E Q [loge ∗ ]≥ E Q [loge] for any valid e-value e. In Anchored E-Watermarking, the alternative is defined by the joint couplingwcon- structed by the generator. However, since the target distributionqlies in a setQ(p 0 ,δ) that is unknown to the detector (i.e., the designer of the e-value), we must optimize the worst-case log-growth rate over arbitraryq ∈ Q(p 0 ,δ). This gives rise to the following robust log-optimality problem. Problem 3.1 (Robust log-optimality). An e-valueeis robust log-optimal in Anchored E-Watermarking if it optimizes the following objective: sup e∈E inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· loge(v,s).(2) In this formulation, the objective P w(v,s) loge(v,s) represents the log-growth rate un- der the alternative. The inner maximizationsup w∈P(p 0 ,q) reflects the generator’s optimization of the couplingwgiven knowledge ofq; the minimizationinf q∈Q(p 0 ,δ) enforces robustness against the worst-case target distribution in the family; and the outer maximizationsup e∈E seeks the optimal detector without access to q subject to model-agnosticy (Theorem 2.2). Remark 3.2 (Relationship to growth rate optimality in the worst case (GROW) (Gr ̈ unwald et al., 2020)). GROW studies the worst-case optimal expected capital growth rate under composite nullP 0 and alternativeP 1 : GROW(P 1 ) = sup E∈E(P 0 ) inf θ∈P 1 E P θ [logE], whereE (P 0 )is the set of all valid e-values for the nullP 0 . Therefore, our problem in Eq.(2)can be seen as generalizing GROW into an ‘active’ scenario where a generator (corresponding tosup w∈P(p 0 ,q) ) seeks to maximizes the power after the worst-case hypothesis selectioninf θ∈P 1 . Note that by designing the couplingw, the generator essentially alters the alternative, so our problem can not be reduced to GROW even if the watermark generator is fixed. 9 3.2 Stopping time While Theorem 3.1 addresses the one-step growth rate, it remains to analyze the sample complexity of the framework. In the context of sequential hypothesis testing, sample efficiency is characterized by the stopping timeτ α = infn∈ Z + : W n ≥ log(1/α)under the alternative, where W n = n X t=1 loge(v t ,s t ), is the accumulated wealth process. This quantity represents the number of samples required to reject the null hypothesis. We consider a stochastic processμ(A,G)governed by the interaction between an adversaryA and a generatorG. At each step t∈ Z + : •The adversaryAselectsq t ∈ Q(p 0 ,δ)based on the e-valueeand the history (v 1 ,s 1 ),..., (v t−1 ,s t−1 ); • The generatorGspecifies the joint couplingw t givenq t andp 0 , and draws the sample (v t ,s t )∼ w t . Due to the adaptive nature of the adversary, the outcome sequencev 1 ,v 2 ,...may be generated autoregressively, conditional on previous outcomes. This formulation extends the i.i.d. setting of Huang et al. (2023) to arbitrary dependent distributions. In this setting, we write the stopping time asτ α (e)to highlight the dependence on the e-valuee. In the context of sequential testing (Breiman, 1961; Chugg et al., 2023; Shekhar & Ramdas, 2023; Kaufmann & Koolen, 2021; Waudby-Smith et al., 2025), the expected stopping timeE[τ α ] typically scales linearly withlog(1/α), modulated by an information-theoretic quantity capturing the complexity of the testing problem. Therefore, we are explicitly interested in the following question: Problem 3.3 (Sample efficiency). For any e-valueesatisfying the constraint in Eq.(1), define its sample complexity by SC(e) = sup A inf G lim inf α→0 E μ(A,G) [τ α (e)] log(1/α) . We are interested in identifying the e-value that minimizes this sample complexity. Note that this formulation is stronger than the classical expected stopping time because we allow the adversary to alter the distribution at each time step. This implies that samples are not generated in an i.i.d. fashion, a distinction crucial for applications such as the watermarking of autoregressive language models. 4 Theoretical Results In this section, we answer the questions posed in the previous section. We first derive the optimal detector for the single-step decision problem and then extend this analysis to the 10 sequential setting to characterize the fundamental limit of sample efficiency. Letndenote the cardinality of the sample spaceVande v denote the one-hot vector (i.e., Dirac measure) that assigns mass 1 to v ∈V . 4.1 Optimal log-growth rate We begin by solving the robust log-optimality problem defined in Theorem 3.1. The following theorem provides a closed-form solution for both the optimal e-value and the worst-case-optimal generator behavior. Theorem 4.1 (Log-growth rate). The optimal e-value that solves the objective in Eq.(2)is given by: e ∗ (v,s) = ( 1−δ/2 p 0 (s) ,s = v, δ 2(n−1)p 0 (s) , s̸= v, (3) wheren = |V|. Furthermore, for any target distributionq ∈ Q(p 0 ,δ)decomposed as q = P k i=1 λ i q i whereq i = p 0 + δ 2 · (e v i − e s i ),v i ̸= s i ∈ Vare the extreme points ofQ(p 0 ,δ), the optimizer of the inner maximization problem (the generator’s optimal coupling) is: w ∗ = k X i=1 λ i · δ 2 · (e v i e ⊤ s i − e s i e ⊤ s i ) + diag(p 0 ) .(4) The optimal robust log-growth rate is equal to: J ∗ = h + 1− δ 2 log 1− δ 2 + δ 2 log δ 2(n− 1) ,(5) where the term h = H(p 0 ) is the Shannon entropy of the anchor distribution p 0 . The result in Equation (5) fundamentally express the optimal growth rate of e-values in Anchored E-Watermarking. The first term is the entropy of the anchor distribution, which mathematically formalizes the intuition that watermarking is inherently easier for distribu- tions with high entropy. The second term can be written as−H(ν δ ), the negative entropy of the categorical distributionν δ = (1− δ/2,δ/(2(n− 1)),...,δ/(2(n− 1))) ∈ ∆([n]), which is a decreasing function ofδ. This explicitly characterizes the power-robustness tradeoff determined by the tolerance parameterδ. Written asH(p 0 )− H(ν δ ), the optimal log-growth rate is the achieved information rate of an Additive Noise ChannelY = X⊕ Z where X ∼ p 0 ,Z ∼ ν δ . Remark 4.2 (Relationship to SEAL (Huang et al., 2025)). SEAL proposes to use a smaller language model asp 0 and speculative decoding as the generator. Note that the optimizer of the inner problem given in Eq.(4)is exactly the maximal coupling given by speculative decoding. Therefore, Theorem 4.1 confirms that the choice of generator in Huang et al. (2025) is optimal. However, the optimal detector given by Eq.(3)is different from the detection rule in SEAL: this gap is corroborated by experiments in Section 5.2. 11 4.2 Sample efficiency Having characterized the one-step optimal growth rate, we now analyze the long-term performance of the watermark in a sequential setting. The following theorem connects the log-growth rateJ ∗ to the sample complexity required to reject the null hypothesis against an adaptive adversary. Theorem 4.3 (Expected stopping time). Letμ(A,G)be the stochastic process defined in Theorem 3.3 andτ α (e)be the stopping time under e-valuee. LetJ ∗ be the optimal rate defined in Eq. (5). We have the following bounds on sample efficiency: • Lower bound (converse): For any valid e-value e∈E : sup A inf G lim inf α→0 E μ(A,G) [τ α (e)] log(1/α) ≥ 1 J ∗ . • Upper bound (achievability): For the optimal e-value e ∗ defined in Theorem 4.1: sup A inf G lim inf α→0 E μ(A,G) [τ α (e ∗ )] log(1/α) = 1 J ∗ . Theorem 4.3 establishes1/J ∗ as the fundamental information-theoretic limit of sample complexity for Anchored E-Watermarking. It demonstrates that the e-valuee ∗ derived from the one-step greedy optimization is not only locally optimal but also globally optimal for sequential testing. Crucially, this optimality holds even against an adaptive adversary that can vary the target distribution at every step, provided the distribution remains within the δ-neighborhood of the anchor. Remark 4.4 (Relationship with the rates in Huang et al. (2023)). Huang et al. (2023) shows that the minimum number of samples required to watermark with Type I errorαscales as log(1/α)· log(1/h) h , wherehis the average entropy per token. While our rate log(1/α) h has the same scaling in terms ofα, its dependence on the entropyhis improved. This is because Huang et al. (2023) study an asymptotic regime whereh → 0, while we fix an anchor distribution with lower bounded entropy arising from the condition inf v∈V p(v) > δ. 5 Experiments 5.1 Synthetic experiments In this section, we verify our theoretical results with synthetic experiments on a family of simple target distributions. Here, we consider the two-token case where|V| = 2and for simplicity of notation, we letV =0, 1. Any anchor distribution we consider belongs to a one-parameter Bernoulli family p 0 = p 1− p for p∈ (0, 1). 12 (a) p = 0.2(b) p = 0.5(c) p = 0.75 Figure 1: Simulation of the two-token case for the log growth problem in Eq.(2). Three separate anchor distributions are used each with parameterδ = 0.01. We solve the simplified maxmin problem using the CLARABEL interior point method solver which is run for30 steps. The theoretical optimum is computed as in Eq. (5). Log-growth optimality. We solve the optimization problem in Eq.(2)numerically and compare the objective curve with the theoretical prediction. Withn = 2, the problem can be simplified to the following maxmin problem: sup e X v p 0 (v) loge(v,v) + δ 2 min log e(0, 1) e(1, 1) , log e(1, 0) e(0, 0) subject to the constraint in Eq.(1)withQ(p 0 ,δ)replaced with the set of verticesQ ext (p 0 ,δ) := p 0 ± δ 2 (e 0 − e 1 ). Using the CLARABEL interior point method solver Goulart & Chen (2024), we obtain the results in Fig. 1. We chooseδ = 0.01andp = 0.2, 0.5, 0.75corre- sponding to three separate anchor distributionsp 0 . For eachp 0 , we cold start the IPM solver and run it for30steps with maximum allowed step size0.99. We observe that our numerical solution to Eq.(2)converges to the proposed theoretical value in Eq.(5), hence verifying our theoretical results in the two-token case. Stopping time.In this setting, we simulate sequential testing with the optimal e-valuee ∗ , as in Eq.(3). Following Theorem 4.1, we letA ∗ be the adversary that choosesq t = q ∗ for all tandG ∗ be the generator that selectsw t = w ∗ in response toA ∗ for allt. Under this setting, we simulate the stopping time over severalαvalues to obtain the results in Fig. 2. Here, we choose the parametersδ = 0.1andp = 0.2, 0.5, 0.75. For each anchorp 0 , we compute the correspondingq ∗ ,w ∗ , ande ∗ using the closed-form equations in Theorem 4.1. We select 30values ofαevenly log-spaced from10 −2 to10 −120 . For eachα, we compute10000 stopping-times by generating sequences(V t ,S t ) t≥1 ∼ w ∗ and computing the resulting loge ∗ (V t ,S t ). We then average the stopping times to form an estimate ofE μ(A ∗ ,G ∗ ) [τ α (e ∗ )]. In Fig. 2, we plot our estimates ofE μ(A ∗ ,G ∗ )[τ α (e ∗ )] /(log(1/α))which show that asα↓ 0, the estimates converge to the theoretical rate of1/J ∗ , thereby validating the result in Theorem 4.3. 13 (a) p = 0.2(b) p = 0.5(c) p = 0.75 Figure 2: Simulation of the two-token case for the stopping time problemSC(e ∗ ). We simulate for three different anchor distributionsp 0 = p 1− p withδ = 0.1and estimate average stopping timesE[τ α ]forαvalues ranging from10 −2 to10 −120 . EachE[τ α ]is estimated by simulating10000stopping timesτ α . The plots above display graphs of E[τ α ] log(1/α) with red dashed lines equal to1/J ∗ whereJ ∗ is as in Eq.(5). We observe that convergence to the theoretical optimum is obtained for sufficiently small α. 5.2 Experiments on real data We evaluate the performance of our watermarking scheme in Theorem 4.1 by comparing it with several baselines on a real watermarking task. Setup. We select Llama2-7B-chat (Touvron et al., 2023) with temperature0.7as target distribution (i.e., the model to be watermarked) and Phi-3-mini-128k-instruct (Abdin et al., 2024) as the anchor distribution. We evaluate our watermark using the MARKMYWORDS benchmark (Piet et al., 2023), which is an open-source benchmark designed to evaluate symmetric key watermarking schemes. MARKMYWORDS generates 300 outputs spanning three tasks—book summarization, creative writing, and news article generation—which mimic potential misuse scenarios. Then, watermarked outputs undergo a set of transformations mimicking realistic user pertur- bation or attacks: (1) character-level perturbations (contractions, expansions, misspellings and typos); (2) word-level perturbations (random removal, addition, and swap of words in each sentence, replacing words with synonyms); (3) text-level perturbations (paraphrasing, translating the output to another language and back). Detection is run in a sequential test set- ting with early stopping. For baseline methods, we apply Bonferroni corrections to preserve anytime valid Type-I error guarantees: letp k denote the p-value at time stepk ∈ Z + , reject at the first time p k < α k(k+1) . Results. In this section, we present a comprehensive comparison of our method against these baselines in terms of quality and size. Quality measures the utility of the watermarked text. It is computed using Llama-3 (Dubey et al., 2024) with greedy decoding as a judge model, and ranges from zero to one. Size represents the median number of tokens required to detect the watermark at a given p-value, computed over a range of perturbations listed above. 14 All experiments enforce a Type-I error constraint ofα = 0.02. Lower values indicate higher efficiency. We compare against five state-of-the-art watermarking schemes: “Distribution Shift” (Kirchenbauer et al., 2023), “Exponential” (Aaronson, 2022b), “Binary” (Christ et al., 2023), “Inverse Transform” (Kuditipudi et al., 2023), and “SEAL” (Huang et al., 2025). SchemeQuality (↑)Size (↓) Exponential0.907∞ Inverse Transform0.917734.0 Binary0.919∞ Distribution Shift0.912145.0 SEAL0.90184.5 Theorem 4.10.91972.0 Table 1: Comparison of our e-value-based watermarking scheme in Theorem 4.1 with baselines across quality and size. We report the median over different private keys and perturbation methods. The best result in each category is highlighted in bold.∞size suggests over half of the watermarked generations fail to be detected after perturbation. E-value-based watermarking demonstrates higher efficiency comparing with all baselines. As shown in Table 1, our Anchored E-Watermarking framework significantly outper- forms baseline methods in terms of detection efficiency while maintaining high generation quality. Specifically, our method improves over SEAL, confirming the superiority of the optimal e-value. Furthermore, we achieves nearly2×speed improvement (from145to72.0 tokens) compared to the best non-anchored baseline. Crucially, this efficiency gain does not come at the cost of text quality: the quality score of our method remains competitive with the baselines, demonstrating that E-value-based watermarking offers a superior trade-off between detectability and utility. Due to space constraints, we defer additional experiment results to Appendix D. 6 Discussions We have introduced Anchored E-Watermarking, a novel framework that bridges the gap between optimal sampling and anytime-valid inference in statistical watermarking. By shifting the detection paradigm from p-values to e-values, we addressed the critical limitation of fixed-horizon testing, enabling valid optional stopping without compromising Type-I error guarantees. Moreover, we characterized the optimal e-value with respect to the worst-case log-growth rate and derived the optimal expected stopping time, providing a rigorous foundation for watermarking in the presence of an anchor distribution. Empirically, our results on real- world language models demonstrate that this principled approach translates into substantial 15 gains in efficiency. Our method identifies watermarked content with significantly fewer tokens than state-of-the-art heuristics while preserving generation quality. As the first application of e-values to statistical watermarking, this framework opens new avenues for efficient detection mechanisms, with future works including extension to more flexible anchor distributions or investigating the game-theoretic implications of e-watermarking against incentivized adversaries. References Aaronson, S. My AI safety lecture for UT effective altruism. Shtetl-Optimized: The blog of Scott Aaronson. Retrieved on September, 11:2023, 2022a. URLhttps:// scottaaronson.blog/?p=6823. Aaronson, S. Watermarking GPT outputs. Scott Aaronson, 2022b. URLhttps://w. scottaaronson.com/talks/watermark.ppt. Abdelnabi, S. and Fritz, M. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In 2021 IEEE Symposium on Security and Privacy (SP), p. 121–140. IEEE, 2021. Abdin, M., Aneja, J., Awadalla, H., and et al. Phi-3 technical report: A highly capable language model locally on your phone, 2024. URLhttps://arxiv.org/abs/ 2404.14219. Aolaritei, L. and Jordan, M. I. Stopping rules for stochastic gradient descent via anytime- valid confidence sequences. arXiv preprint arXiv:2512.13123, 2025. doi: 10.48550/arXiv. 2512.13123. URL https://arxiv.org/abs/2512.13123. Block, A., Sekhari, A., and Rakhlin, A. Gaussmark: A practical approach for structural watermarking of language models. arXiv preprint arXiv:2501.13941, 2025. Breiman, L. Optimal gambling systems for favorable games. Fourth Berkeley Symposium on Probability and Statistics, p. 65–78, 1961. Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877–1901, 2020. Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lundberg, S., et al. Sparks of artificial general intelligence: Early experiments with GPT-4. arXiv preprint arXiv:2303.12712, 2023. Chen, C. and Wang, J.-K. Online detection of llm-generated texts via sequential hypothesis testing by betting. arXiv preprint arXiv:2410.22318, 2024. 16 Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1–113, 2023. Christ, M. and Gunn, S. Pseudorandom error-correcting codes. In Annual International Cryptology Conference, p. 325–347. Springer, 2024. Christ, M., Gunn, S., and Zamir, O. Undetectable watermarks for language models. arXiv preprint arXiv:2306.09194, 2023. Chugg, B., Cortes-Gomez, S., Wilder, B., and Ramdas, A. Auditing fairness by betting. Advances in Neural Information Processing Systems, 36:6070–6091, 2023. Cox, I., Miller, M., Bloom, J., Fridrich, J., and Kalker, T. Digital Watermarking and Steganography. Morgan Kaufmann, Burlington, MA, 2 edition, 2007. ISBN 978-0-12- 372585-1. Csillag, D., Struchiner, C. J., and Goedert, G. T. Prediction-powered e-values. arXiv preprint arXiv:2502.04294, 2025. doi: 10.48550/arXiv.2502.04294. URLhttps: //arxiv.org/abs/2502.04294. Accepted at ICML 2025. Das, D., De Langis, K., Martin, A., Kim, J., Lee, M., Kim, Z. M., Hayati, S., Owan, R., Hu, B., Parkar, R., et al. Under the surface: Tracking the artifactuality of llm-generated data. arXiv preprint arXiv:2401.14698, 2024. Dathathri, S., See, A., Ghaisas, S., Huang, P.-S., McAdam, R., Welbl, J., Bachani, V., Kaskasoli, A., Stanforth, R., Matejovicova, T., Hayes, J., Vyas, N., Al-Merey, M., et al. Scalable watermarking for identifying large language model outputs. Nature, 2024. doi: 10.1038/s41586-024-08025-4. URLhttps://w.nature.com/ articles/s41586-024-08025-4. Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. Fairoze, J., Garg, S., Jha, S., Mahloujifar, S., Mahmoody, M., and Wang, M. Publicly- detectable watermarking for language models. arXiv preprint arXiv:2310.18491, 2023. doi: 10.48550/arXiv.2310.18491. URLhttps://arxiv.org/abs/2310.18491. Fu, Y., Xiong, D., and Dong, Y. Watermarking conditional text generation for ai detection: Unveiling challenges and a semantic-aware watermark remedy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, p. 18003–18011, 2024. Gauthier, E., Bach, F., and Jordan, M. I. E-values expand the scope of conformal prediction. arXiv preprint arXiv:2503.13050, 2025. doi: 10.48550/arXiv.2503.13050. URLhttps: //arxiv.org/abs/2503.13050. 17 Gauthier, E., Bach, F., and Jordan, M. I. Betting on equilibrium: Monitoring strategic behavior in multi-agent systems. arXiv preprint arXiv:2601.05427, 2026. doi: 10.48550/ arXiv.2601.05427. URL https://arxiv.org/abs/2601.05427. Golowich, N. and Moitra, A. Edit distance robust watermarks for language models. arXiv preprint arXiv:2406.02633, 2024. Goulart, P. J. and Chen, Y. Clarabel: An interior-point solver for conic programs with quadratic objectives, 2024. Gr ̈ unwald, P., de Heide, R., and Koolen, W. M. Safe testing. In 2020 Information Theory and Applications Workshop (ITA), p. 1–54. IEEE, 2020. He, H., Liu, Y., Wang, Z., Mao, Y., and Bu, Y. Theoretically grounded framework for LLM watermarking: A distribution-adaptive approach. arXiv preprint arXiv:2410.02890, 2024a. doi: 10.48550/arXiv.2410.02890. URLhttps://arxiv.org/abs/2410.02890. He, H., Liu, Y., Wang, Z., Mao, Y., and Bu, Y. Distributional information embedding: A framework for multi-bit watermarking. arXiv preprint arXiv:2501.16558, 2025. doi: 10.48550/arXiv.2501.16558. URL https://arxiv.org/abs/2501.16558. He, Z., Zhou, B., Hao, H., Liu, A., Wang, X., Tu, Z., Zhang, Z., and Wang, R. Can watermarks survive translation? on the cross-lingual consistency of text watermark for large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (ACL), 2024b. URLhttps://aclanthology.org/ 2024.acl-long.226/. arXiv:2402.14007. Hou, A. B., Zhang, J., He, T., Wang, Y., Chuang, Y.-S., Wang, H., Shen, L., Durme, B. V., Khashabi, D., and Tsvetkov, Y. Semstamp: A semantic watermark with paraphras- tic robustness for text generation, 2024a. URLhttps://arxiv.org/abs/2310. 03991. Hou, A. B., Zhang, J., Wang, Y., Khashabi, D., and He, T. k-semstamp: A clustering- based semantic watermark for detection of machine-generated text. arXiv preprint arXiv:2402.11399, 2024b. Hu, Z., Chen, L., Wu, X., Wu, Y., Zhang, H., and Huang, H. Unbiased watermark for large language models. arXiv preprint arXiv:2310.10669, 2023. Huang, B., Zhu, H., Zhu, B., Ramchandran, K., Jordan, M. I., Lee, J. D., and Jiao, J. Towards optimal statistical watermarking. arXiv preprint arXiv:2312.07930, 2023. Huang, B., Zhu, H., Piet, J., Zhu, B., Lee, J. D., Ramchandran, K., Jordan, M., and Jiao, J. Watermarking using semantic-aware speculative sampling: from theory to practice, 2025. URL https://openreview.net/pdf?id=LdIlnsePNt. 18 Jarrah, A. M., Wardat, Y., and Fidalgo, P. Using ChatGPT in academic writing is (not) a form of plagiarism: What does the literature say. Online Journal of Communication and Media Technologies, 13(4):e202346, 2023. Kamaruddin, N. S., Kamsin, A., Por, L. Y., and Rahman, H. A review of text watermarking: theory, methods, and applications. IEEE Access, 6:8011–8028, 2018. Kaufmann, E. and Koolen, W. M. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22 (246):1–44, 2021. Kelly, J. L. A new interpretation of information rate. The Bell System Technical Journal, 35 (4):917–926, 1956. Kirchenbauer, J., Geiping, J., Wen, Y., Katz, J., Miers, I., and Goldstein, T. A watermark for large language models. arXiv preprint arXiv:2301.10226, 2023. Kuditipudi, R., Thickstun, J., Hashimoto, T., and Liang, P. Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15593, 2023. Lau, G. K. R., Niu, X., Dao, H., Chen, J., Foo, C.-S., and Low, B. K. H. Waterfall: A framework for robust and scalable text watermarking and provenance for large language models. arXiv preprint arXiv:2407.04411, 2024. doi: 10.48550/arXiv.2407.04411. URL https://arxiv.org/abs/2407.04411. Leviathan, Y., Kalman, M., and Matias, Y. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, p. 19274–19286. PMLR, 2023. Li, X., Ruan, F., Wang, H., Long, Q., and Su, W. J. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules. arXiv preprint arXiv:2404.01245, 2024. Liu, A., Pan, L., Hu, X., Li, S., Wen, L., King, I., and Yu, P. S. An unforgeable publicly verifiable watermark for large language models. arXiv preprint arXiv:2307.16230, 2023. doi: 10.48550/arXiv.2307.16230. URLhttps://arxiv.org/abs/2307.16230. Liu, Y. and Bu, Y. Adaptive text watermark for large language models. arXiv preprint arXiv:2401.13927, 2024. Milano, S., McGrane, J. A., and Leonelli, S. Large language models challenge the future of higher education. Nature Machine Intelligence, 5(4):333–334, 2023. Piet, J., Sitawarin, C., Fang, V., Mu, N., and Wagner, D. Mark my words: Analyzing and evaluating language model watermarks. arXiv preprint arXiv:2312.00273, 2023. 19 Ramdas, A. and Wang, R. Hypothesis testing with e-values. Foundations and Trends in Statistics, 2025. doi: 10.1561/3600000002. URLhttps://arxiv.org/abs/2410. 23614. arXiv:2410.23614. Ramdas, A., Yang, F., Wainwright, M. J., and Jordan, M. I. Online control of the false discov- ery rate with decaying memory. In Advances in Neural Information Processing Systems, 2017. URL https://arxiv.org/abs/1710.00499. arXiv:1710.00499. Ramdas, A., Zrnic, T., Wainwright, M. J., and Jordan, M. I. SAFFRON: an adaptive algorithm for online control of the false discovery rate. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018. URLhttps://arxiv. org/abs/1802.09098. arXiv:1802.09098. Ramdas, A., Chen, J., Wainwright, M. J., and Jordan, M. I. A sequential algorithm for false discovery rate control on directed acyclic graphs. Biometrika, 106(1):69–86, 2019. doi: 10.1093/biomet/asy066. URLhttps://doi.org/10.1093/biomet/asy066. arXiv:1709.10250. Ramdas, A., Gr ̈ unwald, P., Vovk, V., and Shafer, G. Game-theoretic statistics and safe anytime-valid inference. Statistical Science, 38(4):576–601, 2023. doi: 10.1214/ 23-sts894. Ren, J., Xu, H., Liu, Y., Cui, Y., Wang, S., Yin, D., and Tang, J. A robust semantics- based watermark for large language model against paraphrasing, 2024. URLhttps: //arxiv.org/abs/2311.08721. Rizzo, S. G., Bertini, F., and Montesi, D. Fine-grain watermarking for intellectual property protection. EURASIP Journal on Information Security, 2019:1–20, 2019. Robbins, H. E.Some aspects of the sequential design of experiments.Bulletin of the American Mathematical Society, 58:527–535, 1952. URLhttps://api. semanticscholar.org/CorpusID:15556973. Shafer, G. Testing by betting: A strategy for statistical and scientific communication. Journal of the Royal Statistical Society: Series A, 184(2):407–431, 2021. Shafer, G., Shen, A., Vereshchagin, N., and Vovk, V. Test martingales, bayes factors and p-values. arXiv preprint arXiv:0912.4269, 2011. doi: 10.48550/arXiv.0912.4269. URL https://arxiv.org/abs/0912.4269. Shekhar, S. and Ramdas, A. Nonparametric two-sample testing by betting. IEEE Transac- tions on Information Theory, 70(2):1178–1203, 2023. Shumailov, I., Shumaylov, Z., Zhao, Y., Gal, Y., Papernot, N., and Anderson, R. The curse of recursion: Training on generated data makes models forget. arXiv preprint arXiv:2305.17493, 2023. 20 Tang, R., Chuang, Y.-N., and Hu, X. The science of detecting LLM-generated texts. arXiv preprint arXiv:2303.07205, 2023. Team, Q. Qwen3 technical report, 2025. URLhttps://arxiv.org/abs/2505. 09388. Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023. Venugopal, A., Uszkoreit, J., Talbot, D., Och, F., and Ganitkevitch, J. Watermarking the outputs of structured prediction with an application in statistical machine translation. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, p. 1363–1372, Edinburgh, Scotland, UK., July 2011. Vincent, J. AI-generated answers temporarily banned on coding Q&A site Stack Overflow. The Verge, 5, 2022. Vovk, V. and Wang, R. E-values: Calibration, combination and applications. The Annals of Statistics, 49(3):1736–1754, 2021. Vovk, V. G. A logic of probability, with application to the foundations of statistics. Journal of the Royal Statistical Society Series B: Statistical Methodology, 55(2):317–341, 1993. Wald, A. Sequential Analysis. John Wiley & Sons, New York, 1947. Wang, R. and Ramdas, A. False discovery rate control with e-values. Journal of the Royal Statistical Society: Series B, 84(3):822–852, 2022. URLhttps://academic.oup. com/jrsssb/article/84/3/822/7056146. arXiv:2009.02824. Wasserman, L., Ramdas, A., and Balakrishnan, S. Universal inference. Proceedings of the National Academy of Sciences, 2020. doi: 10.1073/pnas.1922664117. URLhttps: //w.pnas.org/doi/10.1073/pnas.1922664117. arXiv:1912.11436. Waudby-Smith, I., Sandoval, R., and Jordan, M. I. Universal log-optimality for general classes of e-processes and sequential hypothesis tests. arXiv preprint arXiv:2504.02818, 2025. Wu, Y., Hu, Z., Guo, J., Zhang, H., and Huang, H. A resilient and accessible distribution- preserving watermark for large language models. arXiv preprint arXiv:2310.07710, 2023. doi: 10.48550/arXiv.2310.07710. URLhttps://arxiv.org/abs/2310.07710. Xie, Y., Li, X., Mallick, T., Su, W., and Zhang, R. Debiasing watermarks for large language models via maximal coupling. Journal of the American Statistical Association, (just- accepted):1–21, 2025. 21 Yang, X., Zhang, J., Chen, K., Zhang, W., Ma, Z., Wang, F., and Yu, N. Tracing text provenance via context-aware lexical substitution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, p. 11613–11621, 2022. Zellers, R., Holtzman, A., Rashkin, H., Bisk, Y., Farhadi, A., Roesner, F., and Choi, Y. Defending against neural fake news. Advances in Neural Information Processing Systems, 32, 2019. Zhang, R., Hussain, S. S., Neekhara, P., and Koushanfar, F. REMARK-LLM: A robust and efficient watermarking framework for generative large language models. In Proceedings of the 33rd USENIX Security Symposium (USENIX Security 24), 2024. URLhttps: //arxiv.org/abs/2310.12362. arXiv:2310.12362. Zhao, X., Ananth, P., Li, L., and Wang, Y.-X. Provable robust watermarking for AI-generated text. arXiv preprint arXiv:2306.17439, 2023. 22 Notation.Let[n]be a the set1,...,nand∆([n])denote the probability simplex over [n]. For the simplicity of notations, we letV = [n]. LetS n denote the permutation group of1,...,n. For anyσ ∈ S n ,σ i means applying permutationσ i-times. For any matrix M ∈ R n×n , letM (x,y),M (x, :),M (:,y)denote the entry onx-th row andy-th column, the x-th row, and the y-th column respectively. A Proof of Theorem 4.1 Proof. Let R = ( r ∈ R n×n : X s∈V r(v,s) = 1, r(v,s)≥ 0, ∀v,s∈V ) . By Theorem A.7, the original problem is equivalent to J ′ : sup r∈R inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· (logr(v,s)− logp 0 (s)), with r(v,s) = p 0 (s)e(v,s)∈R. Note that X v,s∈V w(v,s)· (− logp 0 (s)) = X s∈V p 0 (s)· (− logp 0 (s)) = H(p 0 ) where H(p 0 ) is the entropy of p 0 . By Theorem A.6, the optimum value of J ′ is equal to (1− δ 2 ) log 1− δ 2 + δ 2 log δ 2(n− 1) , achieved at r ∗ (v,s) = ( 1− δ/2, s = v, δ/(2n− 2), s̸= v, and for anyq ∈ Q(p 0 ,δ)written asq = P k i=1 λ i · q i forq i = p 0 + δ 2 · (e v i − e s i ) , the optimizer of the inner problem is given by k X i=1 λ i · δ 2 · (e v i e ⊤ s i − e s i e ⊤ s i ) + diag(p 0 ) . Therefore, the optimum value of the original problem is equal to (1− δ 2 ) log 1− δ 2 + δ 2 log δ 2(n− 1) + H(p 0 ). In particular, this is achieved at e ∗ (v,s) = ( 1−δ/2 p 0 (s) ,s = v, δ 2(n−1)p 0 (s) , s̸= v, and the optimizer of the inner problem is given in the same way. This completes the proof. 23 A.1 Supporting lemma Lemma A.1 (Diagonal Dominance). LetVbe a the set1,...,n. For any matrixM 0 ∈ R n×n , there exists a permutation matrix P ∈ R n×n such that the following condition holds for any v ∈V and permutation σ ∈ S n : κ v −1 X i=0 (M 0 P )(σ i (v),σ i (v))≥ κ v −1 X i=0 (M 0 P )(σ i (v),σ i+1 (v)).(6) where κ v is the minimum positive integer such that σ κ v (v) = v. Proof. LetP be the set of all permutation matrices and P ∗ = arg sup P∈P tr[M 0 P ]. Then we claim that P ∗ is the permutation matrix s.t. M = M 0 P ∗ satisfying Eq. (6). Denote C =v,σ(v),...,σ κ v −1 (v). Suppose for the sake of contradiction that there exists σ(·) and v such that κ v −1 X i=0 M (σ i (v),σ i (v)) < κ v −1 X i=0 M (σ i (v),σ i+1 (v)).(7) Define permutation ̄σ(u) = ( σ −1 (u), u∈ C, u,u /∈ C. and permutation matrix P ̄σ = e ̄σ(1) ·e ̄σ(n) ⊤ Then we have MP ̄σ = n X i=1 M (:,i)· e ⊤ ̄σ(i) = X i/∈C M (:,i)· e ⊤ ̄σ(i) + X i∈C M (:,i)· e ⊤ ̄σ(i) = M + X i∈C M (:,i)· (e ⊤ ̄σ(i) − e ⊤ i ) = M + κ v −1 X j=0 M (:, ̄σ j (v))· (e ⊤ ̄σ j+1 (v) − e ⊤ ̄σ j (v) ). 24 Notice tr[P ̄σ M ] = tr[M ] + tr[ κ v −1 X j=0 M (:, ̄σ j (v))· (e ⊤ ̄σ j+1 (v) − e ⊤ ̄σ j (v) )] = tr[M ] + tr[ κ v −1 X j=0 M (:, ̄σ j (v))· e ⊤ ̄σ j+1 (v) ]− tr[ κ v −1 X j=0 M (:, ̄σ j (v))· e ⊤ ̄σ j (v) ] = tr[M ] + κ v −1 X j=0 M ( ̄σ j+1 (v), ̄σ j (v))− κ v −1 X j=0 M ( ̄σ j (v), ̄σ j (v)) = tr[M ] + κ v −1 X j=0 M (σ j (v),σ j+1 (v))− κ v −1 X j=0 M (σ j (v),σ j (v)) > tr[M ] where the last inequality follows from Eq. (7). ButP is a group so P ∗ P ̄σ ∈P . This contradicts with the definition of P ∗ . Lemma A.2 (Optimizer of Inner Problem). LetVbe the set1,...,nandp 0 ∈ ∆(V )be a distribution overVsuch thatinf v∈V p 0 (v) > δ. LetM : V ×V 7→ Rbe a matrix that satisfies κ v −1 X i=0 M (σ i (v),σ i (v))≥ κ v −1 X i=0 M (σ i (v),σ i+1 (v))(8) for anyv ∈ V,σ ∈ S n , whereκ v = infk ≥ 1 : σ k (v) = v. Fix distincta,b ∈ Vand define q = p 0 + δ 2 · (e a − e b ). Consider the optimization problem sup w∈P(p 0 ,q) J (w), J (w) := X v,s∈V w(v,s)M (v,s), where P (p 0 ,q) = ( w :V ×V → R + X s∈V w(v,s) = q(v)∀v ∈V, X v∈V w(v,s) = p 0 (s)∀s∈V ) . Then there exists a permutation σ ∈ S n such that w ∗ = δ 2 κ−2 X i=0 e σ i (a) e ⊤ σ i+1 (a) − e σ i+1 (a) e ⊤ σ i+1 (a) + diag(p 0 )(9) is an optimizer of J , where κ is the minimum positive integer such that σ κ (a) = a. 25 Proof. First, we establish existence of an optimizer. Define w feas by w feas (a,b) = δ 2 , w feas (v,v) = ( p 0 (b)− δ 2 , v = b, p 0 (v),v ̸= b, w feas (v,s) = 0,(v,s) /∈(a,b)∪(v,v) : v ∈V. Because inf v p 0 (v) > δ > δ/2, we have w feas ≥ 0. Its row sums satisfy X s w feas (a,s) = p 0 (a) + δ 2 = q(a), X s w feas (b,s) = p 0 (b)− δ 2 = q(b), X s w feas (v,s) = p 0 (v) = q(v), v /∈a,b, and its column sums satisfy X v w feas (v,b) = p 0 (b)− δ 2 + δ 2 = p 0 (b), X v w feas (v,s) = p 0 (s), s̸= b. Thusw feas ∈P (p 0 ,q). The setP (p 0 ,q)is a nonempty bounded polytope, andJis linear, so there exists w (0) ∈ arg sup p∈P(p 0 ,q) J (w). For a feasiblew, letG w be the directed graph on vertex setVwith an edge(v,s) wheneverv ̸= sandw(v,s) > 0. A directed cycle inG w is ak-tuple(v 0 ,...,v k−1 )of distinct vertices, k ≥ 2, such that w(v i ,v i+1 ) > 0, i = 0,...,k− 1, with indices understood modulo k (so v k = v 0 ). Next, we show that for an optimal distribution ̄w, the graphG ̄w has no directed cycles. Fix any feasible w and such a cycle (v 0 ,...,v k−1 ). For ε > 0 define ̃w by ̃w(v i ,v i+1 ) = w(v i ,v i+1 )− ε, i = 0,...,k− 1,(10) ̃w(v i ,v i ) = w(v i ,v i ) + ε,i = 0,...,k− 1,(11) ̃w(x,y) = w(x,y),(x,y) /∈(v i ,v i+1 ), (v i ,v i ) : 0≤ i≤ k− 1. Choose 0 < ε≤inf 0≤i≤k−1 w(v i ,v i+1 ), so that ̃w ≥ 0. 26 Row sums. For each i, X s∈V ̃w(v i ,s) = (w(v i ,v i+1 )− ε) + (w(v i ,v i ) + ε) + X s/∈v i ,v i+1 w(v i ,s) = X s∈V w(v i ,s). All other rows are unchanged, so X s ̃w(v,s) = X s w(v,s) = q(v), ∀v ∈V.(12) Column sums. For each i, X x∈V ̃w(x,v i ) = (w(v i−1 ,v i )− ε) + (w(v i ,v i ) + ε) + X x/∈v i−1 ,v i w(x,v i ) = X x∈V w(x,v i ), where again indices are taken modulo k. All other columns are unchanged, so X v ̃w(v,s) = X v w(v,s) = p 0 (s), ∀s∈V.(13) Thus ̃w ∈P (p 0 ,q). Objective value. Only entries on the cycle and the corresponding diagonals change, hence J ( ̃w)− J (w) = k−1 X i=0 h ̃w(v i ,v i )M (v i ,v i ) + ̃w(v i ,v i+1 )M (v i ,v i+1 )(14) − w(v i ,v i )M (v i ,v i )− w(v i ,v i+1 )M (v i ,v i+1 ) i = ε k−1 X i=0 (M (v i ,v i )− M (v i ,v i+1 )).(15) Letσ ∈ S n be the permutation whose cycle on the setv 0 ,...,v k−1 is(v 0 v 1 ...v k−1 )and which fixes all other vertices. For v = v 0 we have κ v = k and σ i (v 0 ) = v i , σ i+1 (v 0 ) = v i+1 , i = 0,...,k− 1, so by Eq. (8), k−1 X i=0 M (v i ,v i ) = κ v −1 X i=0 M (σ i (v 0 ),σ i (v 0 )) ≥ κ v −1 X i=0 M (σ i (v 0 ),σ i+1 (v 0 )) = k−1 X i=0 M (v i ,v i+1 ).(16) Combining Eq. (15) and Eq. (16) yields J ( ̃w)− J (w)≥ 0.(17) Now start from the optimizerw (0) . IfG w (0) has no directed cycles, set ̄w = w (0) . 27 Otherwise, choose a directed cycle inG w (0) , apply the above transformation with maximalε as chosen above, and obtainw (1) ∈P (p 0 ,q)withJ (w (1) )≥ J (w (0) ). Sincew (0) is optimal, J (w (1) ) = J (w (0) ), sow (1) is also optimal. Moreover, at least one edge of the chosen cycle has w (1) (v i ,v i+1 ) = 0. Iterating this construction, we obtain a sequence of optimal plansw (m) inP (p 0 ,q)in which the set of off-diagonal edges with positive mass strictly decreases whenever there is a directed cycle. Since there are only finitely many off-diagonal entries, this procedure must terminate. We thus obtain an optimal plan ̄w such that G ̄w contains no directed cycle. Define the off-diagonal flow F (v,s) := ( ̄w(v,s), v ̸= s, 0,v = s. For v ∈V define out(v) := X s̸=v F (v,s),in(v) := X u̸=v F (u,v). Using the marginal constraints of ̄w, q(v) = X s ̄w(v,s) = ̄w(v,v) + out(v), p 0 (v) = X u ̄w(u,v) = ̄w(v,v) + in(v), so out(v)− in(v) = q(v)− p 0 (v) = δ 2 , v = a, − δ 2 , v = b, 0, v /∈a,b. (18) Thus F is a nonnegative flow of value δ/2 from a to b on the directed acyclic graph G ̄w . We now decomposeFinto simplea–bpaths. DefineF (0) := Fand proceed inductively. AssumeF (m) is a nonnegative flow fromatobwith balance equation Eq.(18). Since out(a)− in(a) = δ/2 > 0, there existss 1 ̸= awithF (m) (a,s 1 ) > 0. Setv (m) 0 := aand v (m) 1 := s 1 . Supposev (m) 0 = a,...,v (m) j ̸= b are already recursively constructed such that we use Eq. (18) and nonnegativity to obtain for j ≥ 1, in(v (m) j )≥ F (m) (v (m) j−1 ,v (m) j ) > 0. Forv (m) j /∈a,b, Eq.(18)givesout(v (m) j ) = in(v (m) j ) > 0, so there existsv (m) j+1 ̸= v (m) j with F (m) (v (m) j ,v (m) j+1 ) > 0. SinceG ̄w is acyclic and finite, the sequencev (m) 0 ,v (m) 1 ,... cannot visit a vertex twice; hence the process must terminate at a vertex with no outgoing edges. By(18), such a vertex must satisfyout(v)− in(v)≤ 0. Because all intermediate vertices have balance 0, the only possible terminal vertex is b. Thus we obtain a simple path P m+1 : a = v (m) 0 → v (m) 1 →·→ v (m) k m = b. 28 Let α m :=inf 0≤i≤k m −1 F (m) (v (m) i ,v (m) i+1 ) > 0, and define F (m+1) (v,s) := F (m) (v,s)− α m · 1(v,s) = (v (m) i ,v (m) i+1 ) for some i = 0,...,k m − 1. ThenF (m+1) ≥ 0and satisfies the same balance equations Eq.(18), but has strictly smaller total flow P v,s F (m+1) (v,s) = P v,s F (m) (v,s)− α m . Since the total flow is initiallyδ/2and decreases by a positive amount at each step, this procedure terminates after someLsteps withF (L) ≡ 0. Forℓ = 1,...,L, we obtain simple paths P ℓ : a = v ℓ 0 → v ℓ 1 →·→ v ℓ k ℓ = b, ℓ = 1,...,L, and coefficients α ℓ > 0 such that F (v,s) = L−1 X ℓ=0 α ℓ 1(v,s) = (v ℓ i ,v ℓ i+1 ) for some i = 0,...,k ℓ − 1, v ̸= s,(19) L−1 X ℓ=0 α ℓ = δ 2 .(20) Finally, we prove that the optimalG w ∗ contains only a single path and derive the closed form solution w ∗ . For a general feasible w ∈P (p 0 ,q), the column constraints give w(v,v) = p 0 (v)− X u̸=v w(u,v), v ∈V.(21) Thus J (w) = X v w(v,v)M (v,v) + X u̸=v w(u,v)M (u,v) = X v p 0 (v)− X u̸=v w(u,v) ! M (v,v) + X u̸=v w(u,v)M (u,v) = X v p 0 (v)M (v,v) | z =:J 0 + X u̸=v w(u,v) (M (u,v)− M (v,v)).(22) For the optimal plan ̄w, the off-diagonal part is F , so J ( ̄w) = J 0 + X u̸=v F (u,v) (M (u,v)− M (v,v)).(23) For each path P ℓ , define its gain W (P ℓ ) := k ℓ −1 X i=0 M (v ℓ i ,v ℓ i+1 )− M (v ℓ i+1 ,v ℓ i+1 ) .(24) 29 Using the decomposition Eq. (19), we obtain from Eq. (23) J ( ̄w) = J 0 + X u̸=v L X ℓ=1 α ℓ 1(u,v) = (v ℓ i ,v ℓ i+1 ) for some i = 0,...,k ℓ − 1 ! (M (u,v)− M (v,v)) = J 0 + L X ℓ=1 α ℓ k ℓ −1 X i=0 M (v ℓ i ,v ℓ i+1 )− M (v ℓ i+1 ,v ℓ i+1 ) = J 0 + L X ℓ=1 α ℓ W (P ℓ ).(25) By Eq. (20), J ( ̄w) = J 0 + δ 2 L X ℓ=1 θ ℓ W (P ℓ ), θ ℓ := α ℓ δ/2 , θ ℓ ≥ 0, X ℓ θ ℓ = 1.(26) Let W ∗ := supW (P ) : P is a simple directed path from a to b.(27) Since the graph onV is finite, the maximum exists. From Eq. (26) we deduce J ( ̄w)≤ J 0 + δ 2 W ∗ .(28) Now fix an arbitrary simple directed path P : a = u 0 → u 1 →·→ u K = b with distinct vertices u 0 ,...,u K . Define w P by w P := δ 2 K−1 X i=0 e u i e ⊤ u i+1 − e u i+1 e ⊤ u i+1 + diag(p 0 ).(29) We first verify w P ∈P (p 0 ,q). The diagonal entries of w P are w P (u 0 ,u 0 ) = p 0 (u 0 ), w P (u j ,u j ) = p 0 (u j )− δ 2 ,1≤ j ≤ K,(30) w P (v,v) = p 0 (v), v /∈u 0 ,...,u K . Sinceinf v p 0 (v) > δ, we havep 0 (u j )− δ/2 > δ/2 > 0for1≤ j ≤ K; thus all diagonals are nonnegative. Off-diagonal entries are either 0 or δ/2, so w P ≥ 0. For v = u 0 = a, X s w P (a,s) = w P (a,a) + w P (a,u 1 ) = p 0 (a) + δ 2 = q(a). 30 For an internal vertex u j with 1≤ j ≤ K− 1, X s w P (u j ,s) = w P (u j ,u j ) + w P (u j ,u j+1 ) = p 0 (u j )− δ 2 + δ 2 = p 0 (u j ) = q(u j ). For v = u K = b, X s w P (b,s) = w P (b,b) = p 0 (b)− δ 2 = q(b). For v /∈u 0 ,...,u K , the only nonzero entry in row v is the diagonal, so X s w P (v,s) = p 0 (v) = q(v). Thus the row constraints are satisfied. For a vertex u i+1 on the path (with 0≤ i≤ K− 1), X v w P (v,u i+1 ) = w P (u i+1 ,u i+1 ) + w P (u i ,u i+1 ) = p 0 (u i+1 )− δ 2 + δ 2 = p 0 (u i+1 ). For s /∈u 1 ,...,u K , the only nonzero entry in column s is w P (s,s) = p 0 (s), so X v w P (v,s) = p 0 (s). Hence w P ∈P (p 0 ,q). From Eq. (29) and linearity of J , J (w P )− J 0 = δ 2 K−1 X i=0 (M (u i ,u i+1 )− M (u i+1 ,u i+1 )) = δ 2 W (P ),(31) where W (P ) is defined as in Eq. (24) for this path P . Now choose a pathP ∗ attaining the maximum gainW (P ∗ ) = W ∗ in Eq.(27), and set w ∗ := w P ∗ . Then J (w ∗ ) = J 0 + δ 2 W ∗ ≥ J 0 + δ 2 W (P ℓ ) ∀ℓ, ≥ J 0 + δ 2 L X ℓ=1 θ ℓ W (P ℓ ) = J ( ̄w)≥ J (w), ∀p∈P (p 0 ,q),(32) where we used Eq.(26)and Eq.(28)in the last line. Thus,w ∗ is an optimizer ofJover P (p 0 ,q) with only a single path. Write the maximizing path as P ∗ : a = u 0 → u 1 →·→ u K = b. 31 Define a permutation σ ∈ S n by σ(u i ) = u i+1 , i = 0,...,K− 1, σ(u K ) = u 0 , σ(v) = v, v /∈u 0 ,...,u K . Then the orbit of a under σ is a,σ(a),...,σ K (a) = u 0 ,u 1 ,...,u K , andσ K+1 (a) = a, so the minimal positive integerκwithσ κ (a) = aisκ = K + 1. In particular, σ i (a) = u i , i = 0,...,K. Therefore, the definition Eq. (29) of w ∗ can be rewritten as w ∗ = δ 2 K−1 X i=0 e u i e ⊤ u i+1 − e u i+1 e ⊤ u i+1 + diag(p 0 ) = δ 2 κ−2 X i=0 e σ i (a) e ⊤ σ i+1 (a) − e σ i+1 (a) e ⊤ σ i+1 (a) + diag(p 0 ), which is exactly Eq. (9). This completes the proof. Lemma A.3 (Optimizer of Middle Problem). LetVbe a the set1,...,n,p 0 ∈ ∆(V )be a distribution overVsuch thatinf v∈V p 0 (v) > δ, andM :V ×V 7→ Rbe a matrix. Consider the optimization problem J :inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· M (v,s) where Q(p 0 ,δ) = q ∈ ∆(V ) :∥q− p 0 ∥ 1 ≤ δ P (p 0 ,q) = ( w(v,s) : X s w(v,s) = q(v), X v w(v,s) = p 0 (s) ) Then there exists an optimal solution q ∗ of J coming from the set Q ext (p 0 ,δ) := p 0 + δ 2 · (e a − e b ) : a̸= b∈V . Proof.By Theorem C.1,Q ext (p 0 ,δ)is the set of extreme points of the convex polytope Q(p 0 ,δ). DefineJ (q) = sup w∈P(p 0 ,q) P v,s∈V w(v,s)· M (v,s) . We show thatJ (q)is a concave function. Indeed for all q 1 ̸= q 2 , we let w 1 := argsup w∈P(p 0 ,q 1 ) X v,s∈V w(v,s)· M (v,s) w 2 := argsup w∈P(p 0 ,q 2 ) X v,s∈V w(v,s)· M (v,s). 32 We have J ((q 1 + q 2 )/2) =sup w∈P(p 0 ,(q 1 +q 2 )/2) X v,s∈V w(v,s)· M (v,s) ≥ X v,s∈V (w 1 (v,s) + w 2 (v,s))/2· M (v,s) = (J (q 1 ) + J (q 2 ))/2, where the second step is because the feasibility of (w 1 (v,s) + w 2 (v,s))/2: X s (w 1 (v,s) + w 2 (v,s))/2 = (q 1 (v) + q 2 (v))/2. SinceJ (q)is concave over a convex feasible set, its optimizer must be found on the extreme setQ ext (p 0 ,δ). This completes the proof. Lemma A.4 (Optimal Subpaths). LetVbe a the set1,...,n,p 0 ∈ ∆(V )be a distribution overV such that inf v∈V p 0 (v) > δ. Let M :V ×V 7→ R be a matrix that satisfies κ v −1 X i=0 M (σ i (v),σ i (v))≥ κ v −1 X i=0 M (σ i (v),σ i+1 (v)) for anyv ∈ V,σ ∈ S n , whereκ v = infk ≥ 1 : σ k (v) = v. Consider the optimization problem J (q) =sup w∈P(p 0 ,q) X v,s∈V w(v,s)· M (v,s) where P (p 0 ,q) = ( w(v,s) : X s w(v,s) = q(v), X v w(v,s) = p 0 (s) ) . If there existsq = p 0 + δ 2 · (e a −e b )for somea̸= b∈Vandw ∗ q such thatw ∗ q is the optimizer of J (q) and for a permutation σ we have that w ∗ (q) = δ 2 · κ−2 X i=0 (e σ i (a) e ⊤ σ i+1 (a) − e σ i+1 (a) e ⊤ σ i+1 (a) ) + diag(p 0 ), whereκis the minimum positive integer such thatσ κ (a) = a. Then definec := σ i (a)and d := σ i+1 (a)withi < κ, and letq ′ = p 0 + δ 2 · (e c − e d ). We have that thew ∗ (q ′ )that optimizes J (q ′ ) is given by w ∗ (q ′ ) = δ 2 · (e c e ⊤ d − e d e ⊤ d ) + diag(p 0 ). Proof. Letc = σ i (a)andd = σ i+1 (a). Define the local transport term corresponding to the edge (c,d) as: T c,d := δ 2 · (e c e ⊤ d − e d e ⊤ d ). Note that the proposed optimizer for the subproblemJ (q ′ )is given byˆw = diag(p 0 ) + T c,d . 33 We proceed by contradiction. Assume thatˆwis not the optimizer forJ (q ′ ). Then there exists a feasible transport plan ̃w ∈P (p 0 ,q ′ ) such that: X v,s∈V ̃w(v,s)M (v,s) > X v,s∈V ˆw(v,s)M (v,s). By Theorem A.2, ̃w can be chosen to take the form of ̃w = δ 2 ̄κ−2 X i=0 e ̄σ i (c) e ⊤ σ i+1 (c) − e ̄σ i+1 (c) e ⊤ ̄σ i+1 (c) + diag(p 0 ) for some ̄σ ∈ S n and ̄κ = infk : ̄σ k (c) = c. It follows thatinf v∈V ( ̃w− diag(p 0 )) (v,v)≥ −δ/2 and inf v̸=s∈V ( ̃w− diag(p 0 )) (v,s)≥ 0. Substituting ˆw = diag(p 0 ) + T c,d into the inequality, we have: X v,s∈V ( ̃w(v,s)− diag(p 0 ) v,s )M (v,s) > X v,s∈V (T c,d ) v,s M (v,s).(33) Now, consider the global optimizerw ∗ (q). By the hypothesis,w ∗ (q)decomposes into a sum of path segments. We can separate the specific term T c,d from the rest of the path: w ∗ (q) = diag(p 0 ) + δ 2 κ−2 X j̸=i (e σ j (a) e ⊤ σ j+1 (a) − e σ j+1 (a) e ⊤ σ j+1 (a) ) ! | z R +T c,d , whereRrepresents the flow on the path excluding the step fromdtoc. We construct a new global transport planw new by replacing the local stepT c,d inw ∗ (q)with the “better” local flow derived from ̃w: w new := R + ( ̃w− diag(p 0 )). Substituting R = w ∗ (q)− T c,d , we get: w new = w ∗ (q)− T c,d + ̃w− diag(p 0 ). We verify that w new is feasible for the original problem J (q): Since ̃w ∈P (p 0 ,q ′ ), its row sum isq ′ = p 0 + δ 2 (e c −e d ) . The termT c,d also corresponds to a row marginal shift of δ 2 (e c − e d ). Thus,w new preserves the row sums ofw ∗ (q), which equal q. Both ̃wanddiag(p 0 ) + T c,d maintain column sums equal top 0 . Thus,w new maintains the column sums of w ∗ (q), which equal p 0 . Sinceinf v p 0 (v) > δ,inf v T c,d (v,v) ≥ −δ/2, andinf v ( ̃w− diag(p 0 )) (v,v) ≥ −δ/2, we haveinf v w new (v,v) ≥ 0. Furthermore, all off-diagonal entries ofw ∗ (q)− T c,d and ̃w− diag(p 0 ) are non-negative, thus we conclude that w new is non-negative. 34 Finally, we compare the objective value of w new to w ∗ (q): J (w new ) = X v,s (R v,s + ̃w(v,s)− diag(p 0 ) v,s )M (v,s) = X v,s R v,s M (v,s) + X v,s ( ̃w(v,s)− diag(p 0 ) v,s )M (v,s) > X v,s R v,s M (v,s) + X v,s (T c,d ) v,s M (v,s) (by Ineq. 33) = J (w ∗ (q)). We have constructed a feasible solutionw new ∈P (p 0 ,q)with a strictly higher objective value thanw ∗ (q). This contradicts the optimality ofw ∗ (q). Therefore,ˆwmust be the optimizer for J (q ′ ). Corollary A.5 (Equivalence). LetVbe a the set1,...,nandp 0 ∈ ∆(V )be a distribution overV such that inf v∈V p 0 (v) > δ. The following problem sup r inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· logr(v,s) s.t. X s∈V r(v,s) = 1, ∀v ∈V r(v,s)≥ 0, ∀v,s∈V where Q(p 0 ,δ) = q ∈ ∆(V ) :∥q− p 0 ∥ 1 ≤ δ P (p 0 ,q) = ( w(v,s) : X s∈V w(v,s) = q(v), X v∈V w(v,s) = p 0 (s) ) is equivalent to the following problem sup r inf q∈Q ext (p 0 ,δ) sup w∈P flow (p 0 ,q) X v,s∈V w(v,s)· logr(v,s) s.t. X s∈V r(v,s) = 1, ∀v ∈V n−1 X i=0 logr(v,s)(σ i (v),σ i (v))≥ n−1 X i=0 logr(v,s)(σ i (v),σ i+1 (v)), ∀σ ∈ S n , r(v,s)≥ 0, ∀v,s∈V where Q ext (p 0 ,δ) = p 0 + δ 2 · (e a − e b ) : a̸= b∈V P flow (p 0 ,q) = ( δ 2 · κ−2 X i=0 (e σ i (a) e ⊤ σ i+1 (a) − e σ i+1 (a) e ⊤ σ i+1 (a) ) + diag(p 0 ) : a,b∈V,κ = infk ∈ Z + : σ k (a) = a ) 35 Proof. Let R = ( r ∈ R n×n : X s∈V r(v,s) = 1, r(v,s)≥ 0, ∀v,s∈V ) R diag =R∩ ( r : n−1 X i=0 logr(v,s)(σ i (v),σ i (v))≥ n−1 X i=0 logr(v,s)(σ i (v),σ i+1 (v)), ∀σ ∈ S n ) . Combining Theorem A.1, Theorem A.2, and Theorem A.3, we have sup r∈R inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· logr(v,s) = sup r∈R diag inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· logr(v,s) = sup r∈R inf q∈Q ext (p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· logr(v,s) = sup r∈R inf q∈Q ext (p 0 ,δ) sup w∈P flow (p 0 ,q) X v,s∈V w(v,s)· logr(v,s) where the first step uses Theorem A.1 and the fact that permutingVand the columns ofrby the sameσ ∈ S n does not change the objective, the second step uses Theorem A.3, and the last step uses Theorem A.2. This completes the proof. Proposition A.6 (Reformulated Problem). LetVbe a the set1,...,nandp 0 ∈ ∆(V )be a distribution overV such that inf v∈V p 0 (v) > δ. Consider the following problem sup r inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· logr(v,s)(34) s.t. X s∈V r(v,s) = 1, ∀v ∈V(35) r(v,s)≥ 0, ∀v,s∈V where p 0 is a fixed distribution over the sample spaceV such that inf v∈V p 0 (v) > δ, and Q(p 0 ,δ) = q ∈ ∆(V ) :∥q− p 0 ∥ 1 ≤ δ P (p 0 ,q) = ( w(v,s) : X s∈V w(v,s) = q(v), X v∈V w(v,s) = p 0 (s) ) . Then the optimum value is J ∗ = (1− δ 2 ) log 1− δ 2 + δ 2 log δ 2(n− 1) . In particular, this is achieved at r ∗ a,b (v,s) = ( 1− δ/2, s = v, δ/(2n− 2), s̸= v, and for any q ∈Q(p 0 ,δ) written as q = P k i=1 λ i · q i for q i = p 0 + δ 2 · (e v i − e s i )∈Q ext (p 0 ,δ) := p 0 + δ 2 · (e a − e b ) : a̸= b∈V 36 the optimizer of the inner problem is given by k X i=1 λ i · δ 2 · (e v i e ⊤ s i − e s i e ⊤ s i ) + diag(p 0 ) . Proof. By Theorem A.5, WLOG it suffices to considerqin the form ofp 0 + δ 2 · (e a − e b ) fora ̸= b ∈ Vandpwritten as δ 2 · P κ−2 i=0 (e σ i (a) e ⊤ σ i+1 (a) − e σ i+1 (a) e ⊤ σ i+1 (a) ) + diag(p 0 )for σ ∈ S n ,κ = infk ∈ Z + : σ k (a) = a and a,b∈V . Define J (r,w,q) = X v,s∈V w(v,s)· logr(v,s) J ∗ = sup r inf q∈Q ext (p 0 ,δ) sup w∈P flow (p 0 ,q) J (r,w,q) R ∗ =r :inf q∈Q ext (p 0 ,δ) sup w∈P flow (p 0 ,q) J (r,w,q) = J ∗ r ∗ = arg suptr[r] : r ∈ R ∗ . We say a solution ( ̄w, ̄q) is active if ̄w = argsup w∈P flow (p 0 , ̄q) J (r ∗ ,w, ̄q) ̄q = arginf q∈Q ext (p 0 ,δ) sup w∈P flow (p 0 ,q) J (r ∗ ,w,q) J ( ̄w, ̄q) = J ∗ . Fix v ̸= s∈V and consider the perturbation for sufficiently small ε > 0 ̄r(v,v)← r ∗ (v,v) + ε ̄r(v,s)← r ∗ (v,s)− ε ̄r(v ′ ,s ′ )← r ∗ (v ′ ,s ′ ), ∀(v ′ ,s ′ )̸= (v,s). Then ̄r cannot be a valid solution since it has higher trace than r ∗ . It follows that dJ ( ̄r, ̄w, ̄q) dε = ̄w(v,v) r ∗ (v,v) − ̄w(v,s) r ∗ (v,s) ≤ 0, ∀ active ( ̄w, ̄q). Notice that the derivative dJ ( ̄r, ̄w, ̄q) dε must be either • No-transport: ̄w(v,v) = p 0 (v), ̄w(v,s) = 0 so dJ ( ̄r, ̄w, ̄q) dε = p 0 (v) r ∗ (v,v) > 0. • Middle-way: ̄w(v,v) = p 0 (v)− δ/2, ̄w(v,s) = δ/2 so dJ ( ̄r, ̄w, ̄q) dε = p 0 (v)−δ/2 r ∗ (v,v) − δ/2 r ∗ (v,s) . • Transport-start: ̄w(v,v) = p 0 (v), ̄w(v,s) = δ/2 so dJ ( ̄r, ̄w, ̄q) dε = p 0 (v) r ∗ (v,v) − δ/2 r ∗ (v,s) . • Transport-end: ̄w(v,v) = p 0 (v)− δ/2, ̄w(v,s) = 0 so dJ ( ̄r, ̄w, ̄q) dε = p 0 (v)−δ/2 r ∗ (v,v) > 0. Since dJ ( ̄r, ̄w,q) dε < 0, we can rule out the first and last cases. Now we can summarize that for anyv ̸= s ∈ Vwe have either Middle-way: ̄w(v,v) = p 0 (v)− δ/2, ̄w(v,s) = δ/2or 37 Transport-start: ̄w(v,v) = p 0 (v), ̄w(v,s) = δ/2, and in any case p 0 (v)−δ/2 r ∗ (v,v) − δ/2 r ∗ (v,s) ≤ 0 holds. Since p 0 (v) > δ, in either Middle-way or Transport-start case we have 0≥ p 0 (v)− δ/2 r ∗ (v,v) − δ/2 r ∗ (v,s) > δ/2 r ∗ (v,v) − δ/2 r ∗ (v,s) . It follows thatr ∗ (v,v) > r ∗ (v,s). Since this argument holds for allv ̸= s ∈ V,r ∗ must satisfy r ∗ (v,v) > r ∗ (v,s) for all v ̸= s∈V . Next, we show that all active ̄q, ̄wcan be written as ̄q = p 0 + δ 2 · (e v − e s ), ̄w = δ 2 · (e v e ⊤ s − e s e ⊤ s ) + diag(p 0 ) for some v ̸= s∈V . In either Middle-way or Transport-start case, there existsa ̸= b ∈ Vandσ ∈ S n and i∈ Zsuch that ̄q = p 0 + δ 2 · (e a − e b ) andv = σ i (a),s = σ i+1 (a), due to Theorem A.2. By Theorem A.4, with respect to ̄q = p 0 + δ 2 · (e v − e s ) , the optimizer of the inner problem must be written as δ 2 · (e v e ⊤ s − e s e ⊤ s ) + diag(p 0 ) = argsup w∈P flow (p 0 , ̄q) J (r ∗ ,w, ̄q). Since this argument holds for allv ̸= s ∈ V, we establish a one-to-one correspondence between ̄q = p 0 + δ 2 · (e v − e s ) and ̄w = δ 2 · (e v e ⊤ s − e s e ⊤ s ) + diag(p 0 ) for all active ̄q, ̄w. We can now explicitly write: inf q∈Q ext (p 0 ,δ) sup w∈P flow (p 0 ,q) J (r ∗ ,w,q) =inf q∈Q ext (p 0 ,δ) sup w∈P flow (p 0 ,q) X v,s∈V w(v,s)· logr ∗ (v,s) = inf v̸=s∈V X x∈V p 0 (x) logr ∗ (x,x)− δ 2 · (logr ∗ (s,s)− logr ∗ (v,s)) DefineJ (r,v,s) = P x∈V p 0 (x) logr(x,x)− δ 2 · (logr(s,s)− logr(v,s)), we claim that J (r ∗ ,v,s) must be the same for all v ̸= s∈V . Otherwise suppose J (r ∗ , ̄v, ̄s) = sup v,s J (r ∗ ,v,s) > J ∗ . Set ̄r( ̄v, ̄v)← r ∗ ( ̄v, ̄v) + ε ̄r( ̄v, ̄s)← r ∗ ( ̄v, ̄s)− ε ̄r(v ′ ,s ′ )← r ∗ (v ′ ,s ′ ), ∀(v ′ ,s ′ )̸= ( ̄v, ̄s) for sufficiently small ε > 0. Then for any (v ′ ,s ′ )̸= ( ̄v, ̄s) we have dJ ( ̄r,v,s) dε = p 0 (s)− δ/2 r ∗ (s,s) ≥ 0 and thus inf q∈Q ext (p 0 ,δ) sup w∈P flow (p 0 ,q) J (r ∗ ,w,q) =inf v̸=s∈V,(v,s)̸=( ̄v, ̄s) J (r ∗ ,v,s)≥ J ∗ . But tr[ ̄r] > tr[r ∗ ], this is a contradiction. 38 From the last argument, we know that the optimal solution r ∗ is of the form r ∗ a,b (v,s) = ( a, s = v, b, s̸= v, a≥ 0, b≥ 0, a + (n− 1)b = 1, witha > b(strict diagonal dominance). We now optimize over the two parameters(a,b) subject to this constraint: sup a,b Φ(a,b) s.t. a + (n− 1)b = 1, a > 0, b > 0, a > b. straightforward algebra shows the optimal objective value: Φ(a ∗ ,b ∗ ) = (1− δ 2 ) loga ∗ + δ 2 logb ∗ = (1− δ 2 ) log 1− δ 2 + δ 2 log δ 2(n− 1) . attained at a ∗ = 1− δ 2 and b ∗ = δ 2(n−1) . Thus, the optimal value is J ∗ = (1− δ 2 ) log 1− δ 2 + δ 2 log δ 2(n− 1) . This completes the proof. Lemma A.7 (Row Normalization). LetVbe a the set1,...,nandp 0 ∈ ∆(V )be a distribution overV such that inf v∈V p 0 (v) > δ. Consider the problem sup e inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· loge(v,s) s.t. X v,s∈V q(v)p 0 (s)e(v,s)≤ 1, ∀q ∈Q e(v,s)≥ 0, ∀v,s∈V where Q(p 0 ,δ) = q ∈ ∆(V ) :∥q− p 0 ∥ 1 ≤ δ P (p 0 ,q) = ( w(v,s) : X s w(v,s) = q(v), X v w(v,s) = p 0 (s) ) Now define the kernel matrix r :V ×V 7→ R such that each of its entries are defined as r(v,s) = p 0 (s)e(v,s) A(v) , ∀v,s∈V, where A(v) := P s p 0 (s)e(v,s). Then A ∗ (v) = P s p 0 (s)e ∗ (v,s) = 1 at the optimizer e ∗ . Proof. Lete(v,s)be any feasible solution to the optimization problem. We define the scaling factor of e at node v as: A(v) := X s∈V p 0 (s)e(v,s). Since we are maximizing an objective involvingloge(v,s), we can assumee(v,s) > 0 strictly (otherwise the objective is−∞), and consequently A(v) > 0. 39 We can decompose the matrixe(v,s)into a scale-independent ”shape” matrix ̄e(v,s) and the scaling factors A(v) as follows: e(v,s) = A(v)· ̄e(v,s),where ̄e(v,s) = e(v,s) A(v) . By construction, the normalized matrix ̄e satisfies the normalization property: X s∈V p 0 (s) ̄e(v,s) = X s∈V p 0 (s) e(v,s) A(v) = 1 A(v) X s∈V p 0 (s)e(v,s) = 1. Now, let us analyze the constraint given in the problem statement. The condition is: X v,s∈V q(v)p 0 (s)e(v,s)≤ 1, ∀q ∈Q. Substituting the decomposition of e(v,s): X v∈V q(v) X s∈V p 0 (s)e(v,s) ! = X v∈V q(v)A(v)≤ 1, ∀q ∈Q. Next, we substitute the decomposition into the objective function. Using the property that w ∈P (p 0 ,q) implies P s w(v,s) = q(v), we have: X v,s∈V w(v,s) loge(v,s) = X v,s∈V w(v,s) log (A(v)· ̄e(v,s)) = X v,s∈V w(v,s) log ̄e(v,s) + X v,s∈V w(v,s) logA(v) = X v,s∈V w(v,s) log ̄e(v,s) + X v∈V q(v) logA(v). The first term depends only on the normalized shape ̄e, while the second term depends only on the scaling factorsA(v). To maximize the total objective, we must maximize the second term subject to the feasibility constraint derived above. Consider the term P v∈V q(v) logA(v). Since the logarithm is a concave function, we can apply Jensen’s inequality: X v∈V q(v) logA(v)≤ log X v∈V q(v)A(v) ! . From the feasibility constraint, we know that P v∈V q(v)A(v)≤ 1. Therefore: X v∈V q(v) logA(v)≤ log(1) = 0. Thus for every q, sup w∈P(p 0 ,q) X v,s w(v,s) loge(v,s)≤sup w∈P(p 0 ,q) X v,s w(v,s) log ̄e(v,s). And the inequality is strict unless P v q(v)A(v) = 1andA(v)is constant on the support of q. 40 Taking the minimum over q, we conclude: inf q sup p X v,s w(v,s) loge(v,s)≤ inf q sup p X v,s w(v,s) log ̄e(v,s). Equality is achieved if and only ifA(v) = 1for allv ∈V. Thus, for any optimal solution e ∗ , the scaling factors must be set to 1. Consequently: A ∗ (v) = X s∈V p 0 (s)e ∗ (v,s) = 1. B Proof of Theorem 4.3 Proof. We prove the first claim: Letq ∗ andp ∗ be the solution of the problem in Eq.(2)for the e-valuee. Define the adversaryA ∗ that selectsq t ≡ q ∗ for allt∈ Z + . Then Theorem 4.1 implies that sup G E μ(A ∗ ,G) [loge(v t ,s t )] =sup w∈P(p 0 ,q ∗ ) X v,s∈V w(v,s)· loge(v,s) ≤ J ∗ . Applying Theorem B.1, we have inf G lim inf α↓0 E μ(A ∗ ,G) [τ α (e)] log(1/α) = 1 sup w∈P(p 0 ,q ∗ ) P v,s∈V w(v,s)· loge(v,s) ≥ 1 J ∗ . This establishes the first claim. For the e-value given by e ∗ (v t ,s t ) = ( 1−δ/2 p 0 (s t ) ,v t = s t , δ 2(n−1)p 0 (s t ) , v t ̸= s t , Theorem 4.1 implies that inf q∈Q(p 0 ,δ) sup w∈P(p 0 ,q) X v,s∈V w(v,s)· loge ∗ (v,s)≥ J ∗ . It follows that for any adversaryA, there exists a generatorG such that E μ(A,G) [loge ∗ (v t ,s t )]≥ J ∗ , ∀t∈ Z + . Applying Theorem B.2, we have for any adversaryA inf G lim inf α↓0 E μ(A,G) [τ α (e ∗ )] log(1/α) ≤ 1 J ∗ . This establishes the second claim. B.1 Useful results Theorem B.1 (Dynamic robust sample complexity with converging drift). Fix a filtered prob- ability space(Ω,F, (F t ) t≥0 , P). Let(Y t ) t≥1 be a sequence of integrable random variables 41 adapted to (F t ), and define the partial sums S t := t X i=1 Y i , t≥ 1, with the convention S 0 := 0. Assume the following. (A1) (Bounded increments) There exists a constant M ∈ (0,∞) such that |Y t | ≤ Malmost surely for all t≥ 1. In particular, Y t ≤ M almost surely for all t. (A2) (Positive, converging conditional drift) There exists a deterministic sequence(J t ) t≥1 and a constant J inf > 0 such that E Y t F t−1 = J t almost surely for all t≥ 1, and J inf ≤ J t ≤ J sup <∞ for all t≥ 1, for some finite J sup , and moreover J t −→ J ∞ ∈ (0,∞) as t→∞. (A3) (Stopping rule) For each threshold B > 0, define the stopping time τ B := inft≥ 1 : S t ≥ B, with the usual convention inf∅ := +∞. Then for every B > 0 the stopping time τ B is integrable, and as B →∞, E[τ B ] B −→ 1 J ∞ . Equivalently, if we define B α := log(1/α) and τ α := inft≥ 1 : S t ≥ B α , α∈ (0, 1), then lim α↓0 E[τ α ] log(1/α) = 1 J ∞ . Proof.We break the proof into several steps. The argument is self-contained and uses only basic properties of conditional expectation and stopping times. We first establish boundedness ofS τ B on the event thatτ B is finite. For each fixedB > 0, letτ B be as in (A3). Because(Y t )is adapted and the conditionS t ≥ Bdepends only on Y 1 ,...,Y t , τ B is a stopping time with respect to (F t ). By definition of τ B , S τ B ≥ Bon the eventτ B <∞, 42 On the eventτ B < ∞, we haveS τ B −1 < BandY τ B ≤ Mfrom the bounded increments assumption (A1). Hence S τ B = S τ B −1 + Y τ B < B + Monτ B <∞. Combining the two inequalities gives B1 τ B <∞ ≤ S τ B 1 τ B <∞ < (B + M )1 τ B <∞ .(36) Next, we show thatτ B is integrable and obtain a crude upper bound on its expectation that will be used later. For n∈ N define the truncated stopping time τ (n) B := infτ B ,n, which is integrable for each fixed n. On the one hand, S τ (n) B = τ (n) B X t=1 Y t = n X t=1 Y t 1 τ B ≥t , because the sum stops at t = τ B if τ B ≤ n, and otherwise at t = n if τ B > n. Linearity of expectation yields E S τ (n) B = n X t=1 E Y t 1 τ B ≥t .(37) This exchange of summation and expectation is justified becauseY t is bounded a.s. for allt. Now we use the conditional drift assumption (A2). BecauseY t isF t -measurable and F t−1 -adapted, andτ B ≥ t =τ B > t− 1∈F t−1 (by the definition of a stopping time), we have E Y t 1 τ B ≥t = E h 1 τ B ≥t E Y t F t−1 i = E h 1 τ B ≥t J t i = J t P(τ B ≥ t), where in the second line we used (A2), and in the third line we used thatJ t is deterministic. Thus from (37) we obtain E S τ (n) B = n X t=1 J t P(τ B ≥ t).(38) We now lower-bound the right-hand side by using that J t ≥ J inf > 0 for all t: E S τ (n) B ≥ J inf n X t=1 P(τ B ≥ t) = J inf E[τ (n) B ], because n X t=1 P(τ B ≥ t) = n X t=1 E 1 τ B ≥t = E h n X t=1 1 τ B ≥t i = E[τ (n) B ]. Note that,S τ (n) B ≤ B + Mfor alln, because whenever we stop (either at timeτ B or at 43 timenbefore reachingB) we cannot exceedB + Mby the same argument as in(36). Thus E S τ (n) B ≤ B + Mfor all n. We therefore have J inf E[τ (n) B ]≤ B + Mfor all n. Letting n→∞ and using monotone convergence τ (n) B ↑ τ B , we obtain E[τ B ]≤ B + M J inf <∞.(39) In particular, τ B is integrable for every B > 0. Now that we knowτ B is integrable, we can safely expandS τ B as an infinite sum and swap expectation and summation. Indeed, we can write S τ B = τ B X t=1 Y t = ∞ X t=1 Y t 1 τ B ≥t , where the second equality holds because only finitely many terms are non-zero (those with t≤ τ B ). Taking absolute values, ∞ X t=1 |Y t |1 τ B ≥t ≤ ∞ X t=1 M1 τ B ≥t = Mτ B , and E[Mτ B ] <∞ by (39). Therefore the sum is integrable and Fubini’s theorem gives E S τ B = ∞ X t=1 E Y t 1 τ B ≥t .(40) Usingτ B ≥ t∈F t−1 and (A2), we obtain E Y t 1 τ B ≥t = E h 1 τ B ≥t E Y t F t−1 i = E 1 τ B ≥t J t = J t P(τ B ≥ t). Therefore, E S τ B = ∞ X t=1 J t P(τ B ≥ t).(41) Recall from (36) that B ≤ S τ B < B + Monτ B <∞. Since P(τ B <∞) = 1, taking expectations gives B ≤ E S τ B < B + M.(42) Combining (41) and (42) yields the key inequality B ≤ ∞ X t=1 J t P(τ B ≥ t) < B + M.(43) Define the deviation sequence ∆ t := J t − J ∞ , t≥ 1. 44 Then|∆ t |≤ J sup + J ∞ <∞ for all t, and by assumption, ∆ t −→ 0 as t→∞. We rewrite the sum in (43) as ∞ X t=1 J t P(τ B ≥ t) = ∞ X t=1 J ∞ + ∆ t P(τ B ≥ t) = J ∞ ∞ X t=1 P(τ B ≥ t) + ∞ X t=1 ∆ t P(τ B ≥ t).(44) The first sum is simply J ∞ E[τ B ], because ∞ X t=1 P(τ B ≥ t) = ∞ X t=1 E 1 τ B ≥t = E h ∞ X t=1 1 τ B ≥t i = E[τ B ], where the interchange of summation and expectation is justified because ∞ X t=1 1 τ B ≥t = τ B and E[τ B ] <∞. Thus (44) becomes ∞ X t=1 J t P(τ B ≥ t) = J ∞ E[τ B ] + R B ,(45) where we have defined the remainder term R B := ∞ X t=1 ∆ t P(τ B ≥ t). Plugging (45) into (43), we obtain B ≤ J ∞ E[τ B ] + R B < B + M.(46) We now show that R B is negligible compared to B as B →∞. Fix an arbitraryε > 0. By the convergence∆ t → 0, there exists an integerT = T (ε)≥ 1 such that |∆ t |≤ ε for all t≥ T. Also define C := sup 1≤t<T |∆ t | <∞. Split the sum defining R B into the first T − 1 terms and the tail: R B = T−1 X t=1 ∆ t P(τ B ≥ t) + ∞ X t=T ∆ t P(τ B ≥ t). We bound the absolute value of each part separately. For the finite part, T−1 X t=1 ∆ t P(τ B ≥ t) ≤ T−1 X t=1 |∆ t |P(τ B ≥ t)≤ C T−1 X t=1 1 = C(T − 1)≤ CT. 45 For the tail t≥ T , ∞ X t=T ∆ t P(τ B ≥ t) ≤ ∞ X t=T |∆ t |P(τ B ≥ t)≤ ε ∞ X t=T P(τ B ≥ t)≤ εE[τ B ], again using P ∞ t=1 P(τ B ≥ t) = E[τ B ](and dropping the firstT − 1terms only makes the sum smaller). Combining both parts, we have the uniform bound |R B |≤ CT + εE[τ B ] for all B > 0.(47) From (46) we have J ∞ E[τ B ]≥ B− R B .(48) Using R B ≤|R B | together with (47), J ∞ E[τ B ]≥ B− CT − εE[τ B ]. Rearranging, (J ∞ + ε)E[τ B ]≥ B− CT, so E[τ B ]≥ B− CT J ∞ + ε .(49) Similarly, from the upper inequality in (46),−R B ≤|R B |, and (47), J ∞ E[τ B ]−|R B | < B + M=⇒ J ∞ E[τ B ]− CT − εE[τ B ] < B + M, so (J ∞ − ε)E[τ B ] < B + M + CT. Because ε > 0 is arbitrary, we obtain E[τ B ]≤ B + M + CT J ∞ − ε .(50) Now divide both (49) and (50) by B: E[τ B ] B ≥ 1− (CT )/B J ∞ + ε , E[τ B ] B ≤ 1 + (M + CT )/B J ∞ − ε . Letting B →∞ (so that (CT )/B → 0 and (M + CT )/B → 0) gives lim inf B→∞ E[τ B ] B ≥ 1 J ∞ + ε ,lim sup B→∞ E[τ B ] B ≤ 1 J ∞ − ε . Since ε > 0 was arbitrary, we may let ε↓ 0 to obtain lim inf B→∞ E[τ B ] B ≥ 1 J ∞ ,lim sup B→∞ E[τ B ] B ≤ 1 J ∞ . Hence the limit exists and equals 1/J ∞ : lim B→∞ E[τ B ] B = 1 J ∞ . 46 Finally, choosing B = B α := log(1/α) for α∈ (0, 1) yields lim α↓0 E[τ α ] log(1/α) = 1 J ∞ , which completes the proof. Theorem B.2 (Dynamic hitting-time upper bound with converging lower drift). Fix a filtered probability space(Ω,F, (F t ) t≥0 , P). Let(Y t ) t≥1 be a sequence of integrable random variables adapted to (F t ), and define the partial sums S t := t X i=1 Y i , t≥ 1, with the convention S 0 := 0. Assume the following. (A1) (Bounded increments) There exists a constant M ∈ (0,∞) such that |Y t |≤ Malmost surely for all t≥ 1. (A2≥) (Positive, converging lower conditional drift) There exists a deterministic sequence (J t ) t≥1 and constants 0 < J inf ≤ J sup <∞ such that E[Y t |F t−1 ]≥ J t almost surely for all t≥ 1, and J inf ≤ J t ≤ J sup for all t≥ 1, with J t −→ J ∞ ∈ (0,∞) as t→∞. (A3) (Stopping rule) For each threshold B > 0, define the stopping time τ B := inft≥ 1 : S t ≥ B, with the convention inf∅ := +∞. Then for everyB > 0, the stopping timeτ B is integrable. Moreover, for everyε∈ (0,J ∞ ) there exists a finite constant C ε such that E[τ B ]≤ B + M + C ε J ∞ − ε for all B > 0. Consequently, lim sup B→∞ E[τ B ] B ≤ 1 J ∞ . Equivalently, if B α := log(1/α) and τ α := inft≥ 1 : S t ≥ B α , α∈ (0, 1), then lim sup α↓0 E[τ α ] log(1/α) ≤ 1 J ∞ . 47 Proof. Define the deterministic partial sums A t := t X i=1 J i , A 0 := 0, and the excess process Z t := S t − A t = t X i=1 (Y i − J i ), Z 0 := 0. By assumption (A2≥), E[Z t |F t−1 ] = Z t−1 + E[Y t − J t |F t−1 ]≥ Z t−1 a.s., so (Z t ) is a submartingale. For n∈ N define the bounded stopping time τ (n) B := τ B ∧ n. We claim that for every n, S τ (n) B ≤ B + Ma.s. Indeed, onτ B ≤ nwe haveτ (n) B = τ B andS τ B −1 < Bby definition ofτ B , whileY τ B ≤ M a.s., hence S τ B = S τ B −1 + Y τ B < B + M. Onτ B > nwe haveτ (n) B = nandS n < B, so againS τ (n) B < B + M. This proves the claim. Next, we show that E[Z τ (n) B ]≥ 0, or equivalently, E[S τ (n) B ]≥ E[A τ (n) B ]. Since τ (n) B ≤ n, Z τ (n) B = τ (n) B X t=1 (Y t − J t ) = n X t=1 1τ (n) B ≥ t(Y t − J t ). For t≤ n,τ (n) B ≥ t =τ B ≥ t∈F t−1 , since τ B is a stopping time. Therefore, E h 1τ (n) B ≥ t(Y t − J t ) i = E h E h 1τ (n) B ≥ t(Y t − J t )|F t−1 i = E h 1τ (n) B ≥ tE[Y t − J t |F t−1 ] i ≥ 0, where the inequality follows from assumption (A2≥). Summing overt = 1,...,nyields E[Z τ (n) B ]≥ 0. Thus, we have that E[A τ (n) B ]≤ E[S τ (n) B ]≤ B + Mfor all n. 48 SinceJ t ≥ J inf > 0, the sequence(A t )is increasing andA t → ∞ast → ∞. Because τ (n) B ↑ τ B , the monotone convergence theorem yields E[A τ B ] = lim n→∞ E[A τ (n) B ]≤ B + M. Moreover, since A τ B ≥ J inf τ B , J inf E[τ B ]≤ E[A τ B ]≤ B + M, so τ B is integrable. Fix ε∈ (0,J ∞ ). Since J t → J ∞ , there exists N = N (ε) such that J t ≥ J ∞ − ε for all t≥ N. Define the finite constant C ε :=sup 0≤t≤N−1 (J ∞ − ε)t− A t . Then for all t≥ 0, A t ≥ (J ∞ − ε)t− C ε . Applying the bound from in the previous display at the random timeτ B and taking expectations yields E[A τ B ]≥ (J ∞ − ε)E[τ B ]− C ε . Combining this with E[A τ B ]≤ B + M yields (J ∞ − ε)E[τ B ]≤ B + M + C ε , and therefore E[τ B ]≤ B + M + C ε J ∞ − ε . Dividing by B and letting B →∞, then letting ε↓ 0, gives lim sup B→∞ E[τ B ] B ≤ 1 J ∞ . This completes the proof. C Useful Claims Lemma C.1. LetVbe the set1,...,nandp 0 ∈ ∆(V )be a distribution overVsuch that min v∈V p 0 (v) > δ. Define Q(p 0 ,δ) =q ∈ ∆(V ) :∥q− p 0 ∥ 1 ≤ δ ThenQ(p 0 ,δ) is a convex polytope whose vertex set is given by: Q ext (p 0 ,δ) :=p 0 + (e i − e j )· δ/2 : (i,j)∈V ×V,i̸= j. Proof. RecallQ(p 0 ,δ) := q ∈ ∆ n : ∥q − p 0 ∥ ℓ 1 ≤ δ. First, we note thatQ(p 0 ,δ)is the intersection of two convex polytopes, hence it must also be a convex polytope. We claim thatQ(p 0 ,δ) = Conv(Q ext (p 0 ,δ)). Supposeq ∈ Q(p 0 ,δ), then we can write that q i −p i = s i fors i ∈ [−δ/2,δ/2], P s i = 0, and P |s i |≤ δ. Next, suppose for contradiction 49 that s j > δ/2, then P i̸=j s i =−s j and hence, X k |s k |≥|s j | +| X i̸=j s i | > δ, which violates the TV constraint. Now we show: for anyq ∈Q(p 0 ,δ), there exist nonnegative weightsλ ij summing to1 such that q = X i̸=j λ ij p 0 + δ 2 (e i − e j ) . We construct the decomposition as follows: • Let P =i : s i > 0, N =j : s j < 0. • Necessarily P i∈P s i =− P j∈N s j = 1 2 P k |s k |≤ δ/2. • Define nonnegative coefficients α ij for i∈ P, j ∈ N such that X j∈N α ij = s i δ/2 , X i∈P α ij = −s j δ/2 . The existence follows from Hoffman’s circulation theorem. • Then set λ ij = α ij . Summing, p 0 + δ 2 X i̸=j λ ij (e i − e j ) = p 0 + s = q. This shows q lies in the convex hull of the v ij . It is now enough to show that anyv ∈ Q ext (p 0 ,δ)cannot be generated by a convex combination of two distinct points inQ(p 0 ,δ)which will prove thatv ∈ Q ext (p 0 ,δ)is a vertex ofQ(p 0 ,δ)and hence,Q(p 0 ,δ)is generated by the convex hull ofQ ext (p 0 ,δ). Suppose for contradiction that this is the case. Then there existsq,q ′ ∈ Q(p 0 ,δ)and λ∈ (0, 1) such that p 0 + (e i − e j ) δ 2 = λq + (1− λ)q ′ . Let q = p + η δ 2 and q ′ = p + η ′ δ 2 where η ̸= η ′ then we have that e i − e j = λη + (1− λ)η ′ . Then we must have that λη i + (1− λ)η ′ i = 1, λη j + (1− λ)η ′ j =−1, and λη k + (1− λ)η ′ k = 0. But for either of the first two conditions to be true, we must have thatη i = η ′ i = 1and η j = η ′ j =−1Since all elementsη k andη ′ k are bounded in magnitude by1. Furthermore, because|η i | +|η j | = 2, all otherη k = 0(same forη ′ ). Thus,η = η ′ which is the desired contradiction. 50 D Additional Experiments This section summarizes the complete experiment results on the MARKMYWORDS bench- mark (Piet et al., 2023) under three temperature settings (0.3, 0.7, 1.0). For the gener- ation scheme, we follow the hyperparameter configurations in Huang et al. (2025) with K = 20,|Ω h | = 2,δ = 0.3. Table 2 reports generation quality across watermarking schemes. Overall, quality is relatively stable across schemes, and our method achieves quality that is comparable to (and in some cases close to the best among) the baselines at each temperature. Table 3 reports detection size, measuring the average number of tokens needed to detect the watermark under a range of perturbations, where lower is better. Here, our scheme consistently attains the smallest size at every temperature, substantially outperforming prior methods. This indicates that our detector can reliably identify watermarked text using fewer tokens. Together, these results confirm that our e-value-based scheme improves detection efficiency without sacrificing generation quality. Temp.ExponentialInverse TransformBinaryDistribution ShiftSEALTheorem 4.1 0.30.9060.9100.9050.9000.9050.909 0.70.9070.9170.9190.9120.9010.919 1.00.8980.9170.9050.9070.8710.902 Table 2: Quality (↑) across different temperature settings. Best (per temperature) is high- lighted in bold. Temp.ExponentialInverse TransformBinaryDistribution ShiftSEALTheorem 4.1 0.3∞112.5106.097.0 0.7∞734.0∞145.084.572.0 1.0240.5163.5∞317.0133.097.5 Table 3: Size (↓) across different temperature settings. Best (per temperature) is highlighted in bold. 51