A Unified Framework for LLM Watermarks Thibaud Gloaguen, Robin Staab, Nikola Jovanović, Martin Vechev Abstract LLM watermarks allow tracing AI-generated texts by inserting a detectable signal into their generated content. Recent works have proposed a wide range of watermarking algorithms, each with distinct designs, usually built using a bottom-up approach. Crucially, there is no general and principled formulation for LLM watermarking. In this work, we show that most existing and widely used watermarking schemes can in fact be derived from a principled constrained optimization problem. Our formulation unifies existing watermarking methods and explicitly reveals the constraints that each method optimizes. In particular, it highlights an understudied quality-diversity-power trade-off. At the same time, our framework also provides a principled approach for designing novel watermarking schemes tailored to specific requirements. For instance, it allows us to directly use perplexity as a proxy for quality, and derive new schemes that are optimal with respect to this constraint. Our experimental evaluation validates our framework: watermarking schemes derived from a given constraint consistently maximize detection power with respect to that constraint. 1 Introduction Large Language Model (LLM) watermarking algorithms modify the sampling procedure of the underlying LLM to introduce a detectable signal in the generated text [ 18 ] . Importantly, prior watermarking works have proposed a range of seemingly unrelated approaches [ 18 , 8 , 1 , 20 , 6 ] for how to modify the sampling procedure. Usually, given a specific motivation (e.g., distortion-freeness or power), they first propose a new watermark design, prove that it satisfies some (theoretical) properties, and experimentally validate it. As a result, it becomes difficult to compare existing watermarking schemes at a fundamental level, relate them to one another, or design new methods in a principled manner. This work: In this work, we address this issue by introducing a new unified framework for LLM watermarking. In particular, we show that the construction of a watermarking algorithm can be phrased as a constrained optimization problem: the goal is to maximize the detectability of the inserted watermark signal, while limiting its impact on the quality of the generated text. By formalizing and analyzing this optimization problem, we find that a number of popular schemes (e.g., Red-Green watermarks, AAR/KTH, SynthID) can be formulated as solutions to our optimization problem when instantiated with specific constraints. Importantly, the explicit nature of the constraints in our framework further allows us to better understand and relate existing schemes and provides a principled approach to the design of new, more powerful ones. As we show in our empirical evaluation, our framework provides a natural and practical way to design and instantiate powerful schemes tailored to specific constraints such as quality preservation. Lastly, our framework allows us to theoretically identify and experimentally validate a previously understudied fundamental trade-off in LLM watermarks: quality-diversity-power, i.e., the trade-off between the quality of the watermarked text, the output diversity under the watermarking scheme, and the overall watermarking signal strength. Figure 1 : Overview of Our Framework. We find that most prior watermarks can be viewed from the following angle ( left ): given a next-token probability distribution p and token scores g , pseudorandomly sampled from G , they compute a watermarked probability distribution q(g) . A text is considered watermarked if the sum of pseudorandom scores is above a given threshold. Therefore, we frame watermarking as a constrained optimization problem ( middle ): maximizing the expected score while controlling the watermark distortion. In particular, the constraint balances the watermark quality and diversity. This formulation captures most existing prior watermarks, and enables designing new optimal schemes with respect to a given constraint ( right ). Main contributions Our main contributions are: • We formulate LLM watermarking as a general and principled constrained optimization problem ( Section 3 ). • We show that our framework captures a number of prior watermarking algorithms ( Section 4.1 ). • We instantiate novel watermark schemes that are optimal with respect to a particular objective ( Section 4.2 ). • We empirically show how each scheme (including those from prior work) is optimal with respect to its specific constraint ( Section 5.1 ), validate the newly derived schemes ( Section 5.2 ), and measure the quality–diversity–power trade-off ( Section 5.3 ). Our code is available here . 2 Background and Related Work We now introduce the necessary background on LLM watermarks, including all relevant related work. We defer specific details of each watermarking scheme to Appendix B . LLM Watermarks The goal of LLM watermarks is to insert a detectable signal in the text generated by the LLM. At each generation step, watermarks use a hash of the previously generated context to seed a pseudorandom number generator and attribute a pseudorandom score to each token in the vocabulary. We call this the hashing mechanism. Using those sampled pseudorandom scores, the sampling mechanism modifies the original next-token probability distribution provided by the model into a watermarked next-token probability distribution. The next token is then sampled according to the watermarked distribution. Then, given a text, the watermark detector reconstructs the pseudorandom score for each token in the text and computes a p-value. The p-value represents the probability of observing such a result or a more extreme one under the assumption that the sequence was sampled independently of the scores. In other words, if the text is human-generated, the respective scores are random and the p-value will be high: the text is not watermarked. By contrast, it is statistically unlikely that many tokens have consistently high scores, allowing us to deduce that such texts are watermarked. Importantly, the detector should be model-free , i.e., computing the p-value should not require access to the model and should be computationally efficient. Indeed, most practical scenarios assume that detection is run at internet scale, where computational efficiency is required. Watermark Sampling Mechanisms Prior works have proposed a variety of sampling mechanisms, trying to balance power with impact on quality. Popular approaches include Kirchenbauer et al. 2023 , which biases the logits of the next-token distribution according to binary scores, Dathathri et al. 2024 leverages tournament sampling to favor higher scoring tokens, Aaronson 2023 deterministically samples the highest scoring token according to the logarithm of the next-token probability distribution and a Gumbel score, Kuditipudi et al. 2024 , Christ et al. 2024 use inverse-transform sampling, and Wu et al. 2023 , Chen et al. 2025 reweight the next-token distribution according to the scores’ ranking. While those sampling mechanisms are seemingly unrelated, our work shows that most of them can be derived from a unified family of constrained optimization problems ( Section 4.2 ). Optimal Watermark Design Several prior works have attempted to design LLM watermarks, or some of their components, from a theoretical perspective. For the hashing mechanism, Hou et al. 2024 , Ren et al. 2024 , Kodama et al. 2025 propose using a semantic-aware hash to increase the watermark detectability after paraphrasing, and Zhou et al. 2024 , Shen et al. improve the resilience of the hashing mechanism against spoofing attacks. Huang et al. 2023 , Li et al. 2025b , Li et al. 2025a study the watermark detector to find the shape of the optimal detector with respect to the test power. More closely related to our work, Wouters 2023 , Tsur et al. 2025b study the sampling mechanism that consists of an exponential tilting of the next-token probability distribution with binary scores (a similar setting to Kirchenbauer et al. 2023 ) and find a closed-form formula to compute the watermarked distribution that maximizes power under a log-likelihood constraint. Gloaguen et al. 2025b frames Red-Green watermarks as a constrained optimization problem to derive a watermarking rule for diffusion language models. Tsur et al. 2025a frame watermarking as an optimal transport problem, from which they derive distortion-free schemes that deterministically (according to the pseudorandom scores and p ) sample each token, recovering the watermarking scheme from Aaronson 2023 . Lastly, He et al. 2024 jointly optimize the detector and the sampling mechanism, yielding a powerful yet non-robust watermark. Based on their theoretical insights, they instantiate a distortion-free scheme that introduces dependence between the score and the next-token distribution. Unlike our approach, existing theoretical frameworks focus solely on finding optimal components for specific LLM watermarks and therefore are not capable of capturing and extending a wide range of existing watermarking schemes. 3 Our Framework In this section, we describe our unified framework for LLM watermarks, illustrated in Figure 1 , and motivate its design. Table 1 : Overview of Our Framework We summarize which constraints correspond to which watermarks, including prior works and the novel watermarks introduced in Section 4 . We highlight in light green the novel schemes introduced in this work. We recall that p is the model next-token probability distribution, G the random variable representing the pseudorandom token scores, g the sampled token scores (via the hashing mechanism), and q the watermarked probability distribution. For SynthID, we chain m constrained optimization problems corresponding to the m tournament layers and let q^{(0)}=p . Given that, in this work, we do not extend the SynthID algorithm directly, we use the same algorithm as the one from [ 8 ] . All the algorithms are presented in Appendix B . Scheme Red-Green AAR/KTH \chi^{2} SynthID PPL (Hard) PPL (Soft) Constraint \text{KL}(q(g)||p) \text{KL}(\mathbb{E}_{G}[q(G)]||p) \chi^{2}(q(g),p) \{\chi^{2}(q^{(i)}(g),q^{(i-1)}(g))\}_{i=1,\dots,m} (p-q(g))\cdot\log p (p-\mathbb{E}_{G}[q(G)])\cdot\log p G Distribution Bernoulli Gumbel Binomial Binomial Binomial Binomial Algorithm Algorithm 1 Algorithm 2 Algorithm 4 Dathathri et al. 2024 Algorithm 5 Algorithm 7 Setting We recall the main components of watermarks ( Figure 1 , left): the hashing mechanism to compute pseudorandom scores, the sampling mechanism that, given the next-token probability distribution, computes a watermarked probability distribution, and the detector that, given a text, assesses whether it is watermarked. Our goal is to design a principled sampling mechanism, given a fixed hashing mechanism and a fixed detector. Let \Sigma be the finite vocabulary, p\in\Delta(\Sigma) be the next-token probability distribution, G the random variable representing the pseudorandom scores with \mathbb{G}\subset\mathbb{R}^{|\Sigma|} as support, and g\sim G a sample from G computed from the context via the hashing mechanism. At every generation step, we want to find a watermarked probability distribution q(g) such that later, without knowledge of p , we can distinguish whether a sequence of tokens was sampled from p or q(g) . Optimization Objective A priori, finding such a distribution q(g) is a complex task. If our detection can depend on p and q(g) , the Neyman–Pearson lemma provides a formula for the best possible detector. Hence, finding q(g) can be simplified to maximizing the power of this optimal detector. However, in practice, we want model-free detection ( Section 2 ), i.e., the detector should depend on neither p nor q(g) . From He et al. 2024 , we know that an optimal model-free detector is intractable. In the literature, popular schemes often use the sum of individual token scores as their detection statistic. This suggests that, at each generation step, to maximize the power of the detector one should sample the next-token with the highest possible score. In our notation, this corresponds to solving q^{*}(g)=\argmax_{q\in\Delta(\Sigma)}\mathbb{E}_{\Omega\sim q}[g_{\Omega}]\coloneq\argmax_{q\in\Delta(\Sigma)}g\cdot q. (1) Solving Equation 1 for all g\in\mathbb{G} is then equivalent to solving for all q:\mathbb{G}\rightarrow\Delta(\Sigma) , q^{*}=\argmax_{q:\mathbb{G}\rightarrow\Delta(\Sigma)}\mathbb{E}_{G}[G\cdot q(G)]. (2) Adding Constraints Yet, purely optimizing Equation 2 gives a trivial solution: for all g , q^{*}(g) corresponds to greedy sampling according to the scores g . This is clearly undesirable, as such a watermark would ignore and thus heavily distort the original next-token distribution p , leading to low-quality generations. We therefore introduce a constraint to Equation 2 that controls how distortionary the watermark can be. With this, our watermark framework becomes \displaystyle q^{*}= \displaystyle\argmax_{q:\mathbb{G}\rightarrow\Delta(\Sigma)}\quad\mathbb{E}_{G}[G\cdot q(G)] (3) \displaystyle\text{s.t. }\forall g\in\mathbb{G},\quad D\left(q(g),\mathbb{E}_{G}[q(G)],p\right)\leq\varepsilon. The constraint D\colon\Delta(\Sigma)^{3}\rightarrow\mathbb{R} allows to capture both distortion given a fixed g through q(g) , and distortions in expectation through \mathbb{E}_{G}[q(G)] . For instance, we can choose as D a KL constraint \text{KL}(q(g)||p) or a distortion-free constraint \text{KL}(\mathbb{E}_{G}[q(G)]||p) . With our framework, as we show in Section 4 , designing a watermarking sampling mechanism now becomes equivalent to choosing a meaningful metric D and then solving Equation 3 . Hard and Soft Constraints We define D such that it depends on both q(g) and \mathbb{E}_{G}[q(G)] . We consider imposing a constraint on q(g) as a hard constraint , as the watermark cannot significantly distort the probability distribution given a fixed g . Likewise, imposing a constraint on \mathbb{E}_{G}[q(G)] is a soft constraint . A single instantiation of q(g) can heavily distort the distribution, but on average, the constraint holds. This means that, in practice, there are two different kinds of distortions when it comes to watermarking. We find in Section 5.3 that soft-constraint watermarks are more powerful and better preserve quality, but exhibit very low diversity. In particular, we show in Theorem D.5 that (optimal) watermarks with only soft constraints are necessarily deterministic (i.e., given a fixed prompt, the watermarked LLM always samples the same text). In contrast, hard constraints tend to better preserve diversity at the cost of quality. Interestingly, although the separation of hard and soft constraints is not strictly necessary in our framework, we found that all existing watermarking schemes from Section 4.1 can be expressed using only one of the two. This explicit separation provides a novel and more principled perspective on the watermark quality-diversity-power trade-off. Penalized Formulation In practice, solving the constrained optimization problem from Equation 3 at each generation step can prove to be too costly. Hence, for practical reasons, most schemes from Section 4 actually correspond to the penalized version of the optimization problem, \displaystyle\argmax_{q:\mathbb{G}\rightarrow\Delta(\Sigma)}\mathbb{E}_{G}\!\left[G\!\cdot\!q(G)-\frac{1}{\delta}D\left(q(G),\mathbb{E}_{G}[q(G)],p\right)\right]\!. (4) With the penalized version, assuming the existence of an interior point, the shape of the optimal solution q^{*} is the same as the constrained one: for all \varepsilon>0 , there exists \delta\in\mathbb{R}_{+} such that Equation 3 and Equation 4 have the same solution. Hence, the penalized version corresponds to parametrizing the scheme with \delta instead of \varepsilon . For clarity and consistency, in Section 4 when we instantiate a watermark sampling mechanism, we parametrize it by \varepsilon if we solve the constrained formulation ( Equation 3 ) in practice, and by \delta if we solve the penalized formulation ( Equation 4 ). 4 Applying our Framework In this section, we show how our unified framework naturally describes both existing and new schemes, as illustrated in Figure 1 (right). In Section 4.1 , we show how our framework captures some popular schemes from the literature and even allows us to extend them. For instance, AAR/KTH, which are widely seen as fixed sampling schemes, can be seen as solutions to Equation 3 with a distortion-free constraint, or a tournament layer in SynthID can be seen as a solution to Equation 3 with a \chi^{2} -distance constraint. At the same time, in Section 4.2 , we show how to instantiate entirely novel schemes given particular requirements. We summarize all our results in Table 1 and defer all proofs to Appendix D . 4.1 Capturing Existing Watermarking Sampling Mechanisms We now demonstrate how some of the most popular sampling mechanisms from prior works [ 18 , 1 , 20 , 8 ] can be derived and extended when instantiated with a specific constraint. Red-Green Watermarks One of the most prominent schemes in the literature is the Red-Green watermark (KGW) from Kirchenbauer et al. 2023 . At each step t , the Red-Green watermark pseudo-randomly partitions the vocabulary into a set of \gamma|\Sigma| green tokens and the red tokens. Then, it adds a constant \delta>0 to the logits of tokens in the green set, effectively boosting the probability of green tokens. The detector thresholds the number of green tokens in a text to determine whether it is watermarked. To capture Red-Green watermarks, we let the entries of G be correlated Bernoulli random variables, ensuring it has exactly \gamma|\Sigma| ones. Then, we use the following constraint, \forall g\in\mathbb{G},\,D_{\text{R-G}}(q(g),\mathbb{E}_{G}[q(G)],p):=\text{KL}(q(g)||p). (5) Given \delta>0 as the penalization constant, we show in Theorem D.1 that the solution to our optimization problem from Equation 4 is given by \forall g\in\mathbb{G},\,q_{\text{R-G}}(g)\propto p\exp(\delta g). (6) In the logit space, we have, up to an additive constant, \forall g\in\mathbb{G},\,\log q_{\text{R-G}}(g)=\log p+\delta g. (7) This expression exactly matches the Red-Green watermark algorithm described above: if a token u\in\Sigma is green ( g_{u}=1 ), we add \delta to its logit. Hence, we have shown that Red-Green watermarks can be naturally derived from our framework as solutions to Equation 4 using a (hard) KL constraint, and we find in practice ( Section 5.1 ) that Red-Green watermarks are indeed Pareto-optimal with respect to the detectability–KL constraint trade-off. At the same time, because Red-Green watermarks only use a hard constraint, i.e., the constraint depends only on q(g) and not on the distribution of G . Hence, as we show in Theorem D.1 , Equation 6 is the solution of Equation 4 with the constraints from Equation 5 for any distribution of G . This allows defining new watermarking schemes that we evaluate in Section C.2 . AAR and KTH Watermarks Both Aaronson 2023 and Kuditipudi et al. 2024 (EXP-edit) used the Gumbel-max trick to build a distortion-free watermark. They associate with each token i.i.d. Gumbel scores and sample the next token as the argmax of the Gumbel scores and the token probability. In expectation over the Gumbel scores, such sampling is distributed exactly as the original probability. To capture AAR, we use a soft-constraint with the entries of G being i.i.d. Gumbel random variables, for all g\in\mathbb{G} , D_{\text{AAR}}(q(g),\mathbb{E}_{G}[q(G)],p):=\text{KL}(\mathbb{E}_{G}[q(G)]||p). (8) Given \varepsilon=0 (i.e., enforcing distortion-freeness), Theorem D.3 gives us the following solution \forall u\in\Sigma,q_{\text{AAR}}(g)_{u}:=\mathbbm{1}\{u=\argmax_{v\in\Sigma}(g_{v}+\log p_{v})\}. (9) This is exactly the AAR/KTH watermark, which our framework recovers when enforcing the distortion-free constraint with Gumbel scores G . This also shows that, when using Gumbel scores with sum-based detectors, AAR/KTH are the most powerful distortion-free schemes. Importantly, with Equation 8 and \varepsilon>0 , our framework extends AAR/KTH to a (more powerful) distortionary variant. Indeed, we show in Theorem D.3 that, when using D_{\text{AAR}} , we obtain the following sampling mechanism: q_{\text{AAR}}(g)_{u}:=\mathbbm{1}\left\{u=\argmax_{v\in\Sigma}\left(g_{v}+\frac{1}{1+\delta}\log p_{v}\right)\right\}, (10) where u\in\Sigma and \delta\geq 0 . We evaluate this extension in Section 5 , and find it to be a powerful distortionary scheme. Our framework also generalizes the AAR/KTH mechanism to any distribution of G . For instance, when using a log-normal distribution for G , it directly corresponds to the HeavyWater scheme [ 25 ] , originally derived using optimal transport. Indeed, in Theorem D.3 , we find that the resulting sampling mechanisms for any G are always pseudo-deterministic but lack a closed form: they require solving |\Sigma| equations that depend on the distribution of G . With an equality constraint ( \varepsilon=0 ), this is exactly the optimal transport problem introduced in Tsur et al. 2025a . Hence, setting \varepsilon\geq 0 also extends the schemes from Tsur et al. 2025a with a distortionary version. SynthID Another prominent watermarking scheme is SynthID [ 8 ] , which uses m -layer tournament sampling as a watermark sampling mechanism. To capture the base m=1 layer tournament, we use i.i.d. Bernoulli scores G and a \chi^{2} distance as a constraint, D_{\chi^{2}}(q(g),\mathbb{E}_{G}[q(G)],p):=\sum_{u\in\Sigma}\frac{\left(q(g)_{u}-p_{u}\right)^{2}}{p_{u}}. (11) Given \varepsilon small enough, Theorem D.8 shows that the solution is given by q_{\text{1 layer}}(g):=p(1+(g-p\cdot g)). (12) This corresponds to the vectorized 1-layer tournament sampling formula derived in Dathathri et al. 2024 . To capture the m -layer tournament, we show in Theorem D.8 that it directly corresponds to chaining the optimization problem m times, each time using the \chi^{2} constraint with respect to the previous solution. This formulation intuitively offers a new perspective on why increasing the number of tournament layers m improves the watermark strength: at each layer of the tournament, we reapply the \chi^{2} watermark. \chi^{2} Watermark With Equation 11 , we can also extend the 1-layer tournament beyond the SynthID formulation. In particular, with arbitrary \varepsilon\geq 0 and given any g\in\mathbb{G} , we find in Theorem D.6 that the sampling mechanism corresponding to the \chi^{2} constraint is given by \forall u\in\Sigma,q^{*}(g)_{u}=p_{u}[1+\delta(g_{u}+\mu)]_{+} (13) where \mu\in\mathbb{R} is chosen to satisfy the simplex constraint, \delta\geq 0 , and [\,\cdot\,]_{+} is the positive part function. This offers a new approach to distortionary 1-layer tournament sampling. In SynthID, greater power can be obtained at the cost of increased distortion by increasing the number of candidates per tournament. However, this only allows power to be increased in discrete steps. By contrast, in Equation 13 , increasing \delta increases power while trading off distortion in a continuous manner. We evaluate this scheme using binomial scores in Section 5 . Figure 2 : Comparison of the Detectability–Constraint Trade-off. We compare the trade-off between watermark detectability (TPR@1) and different constraints (KL divergence ( left ), \chi^{2} distance ( middle ), and soft PPL ( right )). We find that, for each constraint, the corresponding scheme has the best detectability-constraint trade-off. Responses are 200 -token-long replies by Llama3.1-8B with temperature 0.7 and 1000 prompts from ELI5. We highlight above each subplot the scheme derived from the plot constraint. 4.2 Designing Optimal Watermarking Schemes Given Specific Constraints Next we show how to design optimal watermarking sampling mechanisms using our proposed framework with respect to specific constraints. As long as computing the solution to Equation 3 is efficient, one can choose any constraints on the simplex as D , e.g., the total variation distance or the Hellinger distance. To highlight the practicality of our framework, we propose two new schemes, one hard- and one soft-constrained, where the constraints specifically target the watermarked text quality. We find in Section 5.2 that those new schemes indeed have a superior detectability-quality trade-off than prior works. Perplexity As a Distance The per-token perplexity (PPL) is defined as the exponential of the information entropy. It measures how surprising it is that a given token has been sampled. The perplexity of a sequence of tokens is the average of the individual token perplexities. In the broader NLP literature, and in the watermarking field in particular, it has been used as a proxy to measure the quality impact of a watermark [ 18 , 8 ] . Notably, our framework allows us to directly use the perplexity (measured according to the original model probability p ) as a constraint when designing watermarking sampling mechanisms. Specifically, we introduce both a hard-constraint and a soft-constraint variant, for all g\in\mathbb{G} , \displaystyle D_{\text{Hard PPL}}:=(p-q(g))\cdot\log p (14) \displaystyle D_{\text{Soft PPL}}:=(p-\mathbb{E}_{G}[q(G)])\cdot\log p. (15) Hard PPL Constraint Given \varepsilon\geq 0 , finding the watermark sampling mechanism using the hard PPL constraint is equivalent to solving the following optimization problem \displaystyle q^{*}= \displaystyle\argmax_{q:\mathbb{G}\rightarrow\Delta(\Sigma)}\quad\mathbb{E}_{G}[G\cdot q(G)] (16) \displaystyle\text{s.t.}\,\forall g\in\mathbb{G},D_{\text{Hard PPL}}\left(q(g),\mathbb{E}_{G}[q(G)],p\right)\leq\varepsilon. This is a linear programming problem that, while no closed-form solution exists, can be solved efficiently using standard solvers. In particular, given g\in\mathbb{G} , the optimal distribution q^{*}(g) is almost deterministic: the optimal solution is the barycenter of two Dirac distributions and hence of support at most 2 . This result is intuitive: if one wants to minimize the PPL of a sequence of tokens, one simply has to do greedy sampling. An intuitive way to solve the optimization problem in Equation 16 is to order the tokens according to their probability p . There exists a rank r>0 such that deterministically sampling any token below this rank satisfies the constraint. If the maximum of G is reached in this subset, we sample this token. Otherwise, find the best combination of a token below and a token above the threshold that maximizes the power. We evaluate this scheme in Section 5 , and find that it is a powerful scheme with high diversity. Soft PPL Constraint With the soft PPL constraint, we show in Theorem D.5 that, because we are only constraining \mathbb{E}_{G}[q(G)] , the solution q^{*}(G) is a Dirac distribution. Specifically, we show in Theorem D.9 that we have \exists\lambda\!\in\mathbb{R},\forall u\!\in\Sigma,q^{*}\!(g)_{u}=\!\argmax_{v\in\Sigma}(g_{v}\!+\!\lambda(\varepsilon)\log p_{v}), (17) where \lambda(\varepsilon) is the unique solution to \mathbb{E}_{G}[q^{*}(G)\cdot\log p]=p\cdot\log p-\varepsilon . Interestingly, when G is composed of i.i.d. Gumbel random variables and \varepsilon=0 , then \lambda(0)=1 , which is exactly the AAR/KTH sampling mechanism. While in general, the feasible set of distortion-free constrained watermarks is contained in the set of soft PPL constrained watermarks, with i.i.d. Gumbel random variables the solution coincides. For other distributions, however, there is no closed-form solution for \lambda(\varepsilon) , requiring a root-finding algorithm to approximate \lambda(\varepsilon) . While this makes the watermark itself more expensive, our framework remains consistent: Our evaluation in Section 5 shows that this scheme outperforms all other schemes in the detectability-quality trade-off. 5 Evaluation In this section, we experimentally validate our framework. In Section 5.1 , we show that schemes derived from a constraint D are Pareto-optimal with respect to D . For instance, when measuring TPR@1 with respect to the (hard) KL constraint we find that Red-Green watermarks are indeed Pareto-optimal. In Section 5.2 , we show that both the new schemes introduced in Section 4 have a state-of-the-art detectability-quality trade-off compared to prior works. Lastly, in Section 5.3 , we confirm the fundamental quality-diversity-power trade-off highlighted in Section 3 by introducing a new experimental procedure tailored to measure this trade-off explicitly. Figure 3 : Comparison of the Detectability–Quality Trade-off. We compare the trade-off between watermark detectability (TPR@1) and text quality (log PPL) for different constraint instantiations and for different \varepsilon . The left figure shows the hard constraints and the right one shows the soft constraints. The dashed line corresponds to the log PPL of the unwatermarked replies. Responses are 200-token-long replies by Llama3.1-8B with temperature 0.7 and 1000 prompts from ELI5. 5.1 Optimality with Respect to the Constraint Next, we experimentally validate our unified framework. Specifically, we demonstrate that a watermarking mechanism designed using a given constraint is Pareto-optimal with respect to that constraint. Overall, our approach enables the straightforward design of high-performing watermarks tailored to a specific metric of interest, such as distortion-freeness or perplexity. Experimental Setup Unless stated otherwise, our experiments use Llama3.1-8B with temperature 0.7 . For each watermark sampling mechanism, we defer the exact hyperparameters (e.g., score distribution, detection algorithm, and hashing mechanism) to Appendix A . We generate, with each watermark and varying watermark strength parameters, a thousand replies to questions from the ELI5 [ 10 ] dataset. Each reply is 200 tokens long. For each scheme, we measure the TPR at 1% FPR, and, for each generated token, the constraint (e.g., KL divergence, \chi^{2} distance) between the original and watermarked next-token probability distributions, which we then average over the sequences. We detail the exact procedure in Section C.1 . To measure \mathbb{E}_{G}[q(G)] with soft constraints, we use a Monte Carlo approximation with 128 samples. Results Figure 2 shows the constraint-detectability trade-off for the KL constraint, the \chi^{2} constraint, and the soft-PPL. We defer the other constraints from Section 5 to Section C.1 . Our results show that, as predicted by our framework, Red-Green watermarks are Pareto-optimal for the KL constraint, the \chi^{2} scheme is optimal for the \chi^{2} constraint, and the soft-PPL scheme is optimal for the soft-PPL constraint. This result shows that our framework allows the principled construction of powerful schemes with respect to a specific constraint, and correctly captures which specific constraints watermarks from prior work optimize. 5.2 Detectability-Quality Trade-off We next explore the detectability-quality trade-off of the different watermarks presented in Section 4 . Importantly, we show that the extensions of existing schemes (distortionary AAR/KTH, distortionary 1-layer tournament) and the newly proposed PPL-constrained schemes outperform prior work. Notably, our soft PPL scheme achieves a state-of-the-art detectability-quality trade-off, confirming that the soft PPL constraint is a practical proxy for watermark quality. Experimental Setup We use the same experimental setup as in Section 5.1 . As a proxy for quality, we measure the average text perplexity using Qwen3-30B , and in Section C.4 we use LLM benchmark accuracy. Additionally, we show some watermarked text examples in Appendix E , and we ablate this experiment on Ministral-3-14B in Section C.3 . Results In Figure 3 we show the detectability-quality trade-off for all watermarks from Section 4 , explicitly differentiating between hard-constraint watermarks (left) and soft-constraint watermarks (right). For hard-constraint watermarks, both the Red-Green watermark and the \chi^{2} watermark have a similar detectability-quality trade-off. The hard-PPL watermark exhibits higher detectability in the low-distortion regime. For soft-constraint watermarks, at \varepsilon=0 (i.e., when the log PPL of the watermarked model matches that of the unwatermarked model), the soft-PPL scheme outperforms AAR/KTH, which itself outperforms SynthID. Indeed, both SynthID and AAR/KTH satisfy the distortion-free constraint. Yet, under the assumptions from Section 4.1 (i.e., using i.i.d. Gumbel entries for G ), AAR/KTH is the optimal sampling mechanism among all distortion-free schemes. For the soft-PPL scheme, we specifically chose the constraint to maximize the watermark detectability-quality trade-off, which is why it outperforms both schemes. Importantly, this result is not due to overfitting our quality metric (log PPL): as we find in Section C.4 , when using LLM benchmark accuracy as a proxy for quality, the soft-PPL scheme still outperforms both AAR/KTH and SynthID. In the distortionary case, where the PPL of the watermarked model exceeds that of the unwatermarked one, we find that the ordering remains similar. In particular, this implies that our extension of AAR/KTH enables greater flexibility by trading distortion for better watermark detectability. Importantly, these results highlight that our framework not only captures popular prior watermarks. It also allows for the principled incorporation of relevant watermarking constraints when designing new and powerful schemes. Figure 4 : Diversity–Quality Trade-off at Fixed TPR. We compare the trade-off between watermark impact on diversity (Self-BLEU) and quality ( \log PPL) given a fixed TPR@1 of 0.95 . A high self-BLEU score corresponds to a low output diversity. The error bars correspond to the standard deviation and the dotted gray line shows the correlation. The PPL and TPR@1 are measured over 1,000 prompts from ELI5 ( Section 5.2 ), while the diversity is measured with the procedure described in Section 5.3 . We find that, given a fixed power, diversity and quality are negatively correlated. 5.3 Impact on Diversity Next, we investigate how different watermarking methods affect output diversity. Although prior work [ 13 ] suggested that watermarks, especially distortion-free schemes, may reduce diversity, this effect has not been rigorously evaluated. We propose a new experimental protocol to quantify the impact of watermarking on LLM output diversity. Our results show that soft-constrained watermarks substantially reduce diversity, whereas hard-constrained watermarks are able to retain it to a larger extent. Measuring Watermark Diversity As in Section 5.2 , we use Llama3.1-8B with temperature 0.7 . The effect of a watermark on diversity, as noted in Gloaguen et al. 2025a , is to reduce the number of unique outputs given a fixed prompt. This means that, in order to measure the watermark’s impact on diversity, we need to sample the model multiple times using the same prompt. If the watermark negatively impacts diversity, we expect a higher number of repetitions within the generated answer sequences. In the limit, with AAR/KTH, given a fixed prompt the sampling is deterministic and all the generated sentences are exactly the same: the watermark exhibits low diversity. We therefore propose the following experimental setup. Given a dataset of prompts \{x_{i}\}_{i} , for each prompt, we sample the model N times, computing the self-BLEU score [ 2 ] for that prompt. Self-BLEU scores are between 0 and 1 and measure the n-gram repetition between texts. In our setting, a high self-BLEU score means that, for a given prompt, the multiple generations have very similar n-grams. To smooth out the effect of the prompt itself (some prompts might naturally lead to low-diversity text), we then average all self-BLEU scores. In practice, we use 100 prompts from the ELI5 dataset and sample the model N\coloneq 100 times per prompt, yielding a total of 10{,}000 samples. For each sample, we generate 200 tokens, using the trigram self-BLEU score with uniform weights. Watermarks Diversity-Quality Trade-off Figure 4 shows the impact on diversity and quality of different watermarks given a fixed TPR@1. In particular, as predicted by our framework, we find that there is a negative correlation between diversity and quality: given a fixed power, some schemes prioritize diversity over quality and vice versa. In particular, soft-constrained schemes (AAR/KTH and PPL (Soft)) have particularly low diversity (i.e., high self-BLEU scores) but also the highest quality. This confirms the theoretical derivation from Section 3 : at a fixed power, there is a fundamental trade-off between watermark quality and diversity. More generally, this suggests that to measure the impact of distortion-free watermarks it is also necessary to evaluate the watermark behavior under repetition of the same prompt (a similar finding to Wu et al. 2025 ), and not only assume that distortion-free implies no actual distortion. 6 Conclusion and Limitations Our work shows that most existing watermarks can be seen as instances of a unified constrained optimization problem. As confirmed by our evaluation, our framework makes three contributions: (i) it provides a principled way to interpret prior watermarks, (ii) it allows us to practically instantiate powerful new schemes tailored to specific watermarking requirements, and lastly (iii) it provides a novel perspective on the quality-diversity-power trade-off in watermarks. Limitations Our work makes two key assumptions when constructing the optimization problem. First, we restrict the optimization to the token level rather than the sequence level. Second, we deliberately optimize only the watermark sampling mechanism and do not jointly optimize the detector. While these assumptions make the optimization tractable and enable us to capture and extend a wide range of watermarking schemes, there may exist jointly optimized approaches that achieve better overall watermarking performance. Lastly, we note that there exists a range of watermarking algorithms (such as fully cryptographic watermarks) that are not captured by our framework. Impact Statement This paper presents a unified framework for LLM watermarking, which allows us to better understand existing schemes and design new ones. Better-understood and better-tuned watermarks could support provenance, auditing, and mitigation of large-scale AI-generated text misuse. Nonetheless, while LLM watermarks in general, and our framework in particular, are designed to mitigate false positives, they should not be used as sole evidence in major decisions. Appendix A Experimental Details In this section, we detail the hyperparameters used for our experiments in Section 5 . Watermark Hyperparameters For Red-Green watermarks, we used as a score distribution a Bernoulli distribution with parameter \gamma=0.5 . For AAR/KTH, we used a Gumbel distribution with parameters (0,1) . For SynthID, we used a 30 -layer tournament with Bernoulli g -values of parameter 0.5 . Lastly, for the \chi^{2} watermark, the hard PPL watermark, and the soft PPL watermark, we used a binomial distribution with parameters (30,0.5) . For the hashing mechanism, we use for all schemes the SumHash hashing scheme from Kirchenbauer et al. 2023 with the four previous tokens as the context. For detection, for Red-Green watermarks we used a binomial test, for AAR/KTH a Kolmogorov–Smirnov test between the observed score distribution and the Gumbel CDF, for SynthID we used a binomial test, and lastly for \chi^{2} watermarks and both PPL watermarks, we also used a binomial test. For all tests, following the guidelines from Fernandez et al. 2023 , we removed all (context, token) duplicates prior to the statistical test. Sampling Hyperparameters For generating replies, we used the instruct version of Llama3.1-8B with a temperature of 0.7 and 16 -bit quantization. We also used top- k with k=50 and constrained the model to generate 200 -token-long replies. For measuring perplexity, we use the instruct version of Qwen3-30B with a temperature of 1.0 and 8 -bit quantization. Appendix B Algorithms In this section, we examine the different sampling mechanisms for the watermarks introduced in Section 4 . We recall that, as explained in Section 3 , we use \varepsilon as a scheme parameter when it corresponds to the constrained formulation ( Equation 3 ) and \delta when it corresponds to the penalized formulation ( Equation 4 ). B.1 Red-Green watermarks Algorithm 1 Red-Green Watermark Sampling Mechanism 0: Next-token probability p , watermark strength \delta , current scores g\in\mathbb{R}^{|\Sigma|} . 1: q\leftarrow p\exp(\delta g) 2: q\leftarrow\frac{1}{||q||_{1}}q \triangleright Normalization 3: return: q B.2 AAR/KTH watermarks Algorithm 2 AAR/KTH Watermark Sampling Mechanism 0: Next-token probability p , watermark strength \delta , current scores g\in\mathbb{R}^{|\Sigma|} . 1: i\leftarrow\argmax(g+\frac{1}{1+\delta}\log p) 2: q_{i}\leftarrow 1 3: \forall u\neq i,\,q_{u}\leftarrow 0 4: return: q B.3 Chi2 watermark Algorithm 3 Compute Optimal Shift \mu 0: Next-token probability p , watermark strength \delta , current scores g\in\mathbb{R}^{|\Sigma|} . 1: Sort indices \pi such that g_{\pi_{1}}\geq g_{\pi_{2}}\geq\dots\geq g_{\pi_{|\Sigma|}} 2: Initialize active support \mathcal{S}\leftarrow\emptyset 3: for i=1 to |\Sigma| do 4: \mathcal{S}\leftarrow\mathcal{S}\cup\{\pi_{i}\} 5: \mu\leftarrow\frac{1-\sum_{j\in\mathcal{S}}p_{j}(1+\delta g_{j})}{\delta\sum_{j\in\mathcal{S}}p_{j}} 6: if \delta\mu\geq-1-\delta g_{\pi_{i}} then 7: return: \mu 8: end if 9: end for 10: return: \mu Algorithm 4 \chi^{2} Watermark Sampling Mechanism 0: Next-token probability p , watermark strength \delta , current scores g\in\mathbb{R}^{|\Sigma|} . 1: \mu\leftarrow\text{Compute\_mu}(p,\delta,g) 2: q\leftarrow p[1+\delta(g+\mu)]_{+} 3: return: q B.4 PPL watermarks Algorithm 5 PPL (Hard) Watermark Sampling Mechanism 0: Next-token probability p , watermark strength \varepsilon , current scores g\in\mathbb{R}^{|\Sigma|} . 1: q\leftarrow\text{Solve\_LP}(\argmax_{x\in\Delta(\Sigma)}x\cdot g,\text{ s.t. }-x\cdot\log p\leq-p\cdot\log p+\varepsilon) \triangleright Use convex-hull solver 2: return: q Algorithm 6 PPL (Soft) Constraint 0: Next-token probability p , watermark strength \varepsilon , current scores g\in\mathbb{R}^{|\Sigma|} . 0: \beta 1: i\leftarrow\argmax(g+\beta\log p) 2: return: \log p_{i}-p\cdot\log p+\varepsilon Algorithm 7 PPL (Soft) Watermark Sampling Mechanism 0: Number of Monte Carlo samples n . 0: Next-token probability p , watermark strength \varepsilon , current scores g\in\mathbb{R}^{|\Sigma|} , distribution G . 1: g_{1},\dots,g_{n}\leftarrow\text{Sample}(G) \triangleright We sample once at the beginning 2: \beta\leftarrow\text{Find\_root}(\sum_{i=1}^{n}\text{PPL\_Constraint}(p,\varepsilon,g_{i})) \triangleright We use a bisection solver. 3: i\leftarrow\argmax(g+\beta\log p) 4: q_{i}\leftarrow 1 5: \forall u\neq i,\,q_{u}\leftarrow 0 6: return: q Appendix C Additional Evaluation In this section, we include additional ablation experiments to complement our main experiments from Section 5 . In Section C.1 , we extend Section 5.1 to the soft KL constraint and the hard PPL constraint. In Section C.2 , we ablate the effect of the score distribution G on each of the watermarks from Section 4 . In Section C.3 , we confirm the results from Section 5.2 using Ministral-3-14B . Lastly, in Section C.4 , we show the quality–detectability trade-off of each of the watermarks from Section 4 using LLM benchmark accuracy as a proxy for quality. C.1 Ablation on Measuring Optimality With Respect to the Constraint Here, we extend the experiments from Section 5.1 to include the missing constraints, namely the hard PPL constraint from Equation 14 and the soft KL constraint from Equation 8 . Figure 5 : Additional Detectability–Constraint Trade-off We compare the trade-off between watermark detectability (TPR@1) and different constraints (KL divergence between \mathbb{E}_{G}[q(G)] and p ( left ), and hard PPL ( right )). Responses are 200-token-long replies by Llama3.1-8B with temperature 0.7 and 1000 prompts from ELI5. Figure 6 : Watermarks’ Trade-offs for Different Score Distributions. For each watermark, we compare the trade-off between watermark detectability (TPR@1) and its respective constraint ( left ), and between watermark detectability and perplexity ( right ) for different score distributions G . The gray dashed line corresponds to the unwatermarked perplexity. Responses are 200-token-long replies by Llama3.1-8B with temperature 0.7 and 1000 prompts from ELI5. Experimental Setup We follow the same experimental setup as in Section 5.1 . In particular, for each scheme, we measure the constraint between the original and watermarked next-token probability distributions, and we average it over the sequences. This means that, given n sequences of length L and the corresponding score matrices G^{(1)},\dots,G^{(n)}\in\mathbb{R}^{L\times|\Sigma|} and LLM probability distributions p^{(1)},\dots,p^{(n)}\in\Delta(\Sigma)^{L} , we actually measure \frac{1}{n}\sum_{i=1}^{n}\frac{1}{L}\sum_{t=1}^{L}D\Big(q(p^{(i)}_{t},G^{(i)}_{t}),\,\mathbb{E}_{G^{\prime}}\big[q(p^{(i)}_{t},G^{\prime})\big],\,p^{(i)}_{t}\Big)\approx\mathbb{E}_{p,G}\Bigg[D\Big(q(p,G),\,\mathbb{E}_{G^{\prime}}\big[q(p,G^{\prime})\big],\,p\Big)\Bigg] where we explicitly show the dependence of q on p . For the hard PPL metric in particular, because it is linear with respect to q , this means that in practice we measure the soft PPL metric. A second limitation of our comparison is that not all schemes use the same distribution for G . This means that the objective and the detector are not the same; it also means that there is no guarantee that a scheme optimized for a given distribution of G outperforms (in terms of the constraint-quality trade-off) another scheme that is not derived from this particular constraint but uses a different distribution for G . Results Figure 5 illustrates both of these limitations. For the KL divergence between the expected watermark distribution and the next-token distribution, we see that AAR, despite being derived from this constraint, is not optimal. This is because, unlike most other schemes, AAR uses the Gumbel distribution for G , while other schemes use either the binomial distribution or the Bernoulli distribution. For the hard PPL scheme, similarly, we find that it does not appear to be optimal in Figure 5 . This is because, in practice, we can only measure the expected constraint. For the PPL constraint, the expected hard PPL constraint corresponds exactly to the soft PPL constraint, hence we find that Figure 5 (right) and Figure 2 (right) are very similar. C.2 Ablation on the Score Distribution Here, we ablate the score distribution G . For all the schemes from Section 4 except AAR/KTH and SynthID, there is no fundamental restriction on which distribution to choose for G . Yet, our framework does not indicate which score distribution to choose to maximize power: in the optimization problem from Equation 3 , the distribution is treated as a constant. This means that we have to find experimentally which distribution is best to maximize the detectability–constraint trade-off for each watermark. Experimental Setup We follow closely the experimental setup from Section 5.1 . Specifically, for each scheme, we measure its respective constraint between the original and watermarked next-token probability distributions, and we average it over the sequence. We also measure the perplexity (computed with Qwen3-30B ) to evaluate the detectability–quality trade-off. Each scheme is evaluated with 6 different distributions for the token scores G : Bernoulli with success 0.5 , binomial with parameters (30,0.5) , Gumbel with parameters (0,1) , lognormal with parameters (0,1) , normal with parameters (0,1) , and uniform over [0,1] . Results Figure 6 shows for each scheme the different trade-offs when using various score distributions. In particular, we find that for hard-constraint watermarks, the choice of the score distribution has almost no influence. For all the distributions tested, the resulting watermarks had similar trade-offs. One exception is the \chi^{2} watermark with a Bernoulli distribution, where we find that increasing the distortion beyond a threshold leads to catastrophic failures of the watermarking scheme. This is why we only show low distortions for the \chi^{2} watermark with a Bernoulli distribution in Figure 6 . For soft-constraint watermarks, we evaluate the soft PPL scheme in Figure 6 . We find that, in this case, the choice of the distribution G has a significant influence on the quality–detectability trade-off. Specifically, the heavier the tail of the distribution, the lower the performance of the scheme. Interestingly, this is the opposite behavior from what Tsur et al. 2025a observed when extending the AAR scheme to non-Gumbel distributions. This suggests that there is no single best distribution that works for all watermarking schemes. Figure 6 also highlights an interesting result for the soft PPL watermark. As stated in Theorem D.9 , Algorithm 7 only holds for continuous distributions (otherwise, to enforce the constraint in addition to \beta one must find the tie-breaking rule). Hence, we see that using Algorithm 7 with a Bernoulli distribution leads to a more distortionary watermark than expected. C.3 Evaluation on Ministral-3-14B In this section, we reproduce the experiments from Section 5.2 using Ministral-3-14B instead of Llama3.1-8B to ensure that the newly proposed watermarks generalize to models of different sizes and from different families. Figure 7 : Comparison of the Detectability–Quality Trade-off. We compare the trade-off between watermark detectability (TPR@1) and text quality (log PPL) for different constraint instantiations and for different \varepsilon . The left figure shows the hard constraints and the right one shows the soft constraints. The dashed line corresponds to the log PPL of the unwatermarked replies. Responses are 200-token-long replies by Ministral-3-14B with temperature 0.7 and 1000 prompts from ELI5. Results Figure 7 shows the detectability-quality trade-off for all watermarks from Section 4 , with hard-constraint watermarks on the left and soft-constraint watermarks on the right. We find that, for all watermarks except SynthID, the results are very similar to Figure 3 . In particular, this means that our framework is model-agnostic and can be applied to most LLMs. Regarding SynthID, we find that at higher distortion levels (not represented in Figure 7 ), model quality significantly deteriorates. C.4 Measuring Detectability-Quality Trade-off with LLM Benchmarks In this section, we extend the experiments from Section 5.2 by measuring the detectability-quality trade-off with LLM benchmark accuracy rather than perplexity. We find that, even when quality is measured through benchmark accuracy, our soft-PPL schemes outperform all prior work. Figure 8 : Comparison of the Detectability-Quality Trade-off. We compare the trade-off between watermark detectability (TPR@1) and text quality (LLM benchmark accuracy) for different constraint instantiations and for different \varepsilon . The left figure shows the hard constraints and the right one shows the soft constraints. The dashed line corresponds to the average accuracy of the unwatermarked model. Responses are 200-token-long replies by Ministral-3-14B with temperature 0.7 and 1000 prompts from ELI5. The benchmark accuracy is averaged over HumanEval, MBPP and GSM8K. Experimental Setup To measure TPR@1, we follow the experimental setup from Section 5.2 . For LLM benchmarks, we measure accuracy on three benchmarks with long answers, namely two coding tasks, HumanEval [ 4 ] and MBPP [ 3 ] , and one math task, GSM8K [ 7 ] . We use the LM Evaluation Harness framework from Gao et al. 2024 . For generating the benchmark answers, we use a temperature of 0.7 and Llama3.1-8B . Results Figure 8 shows the detectability-quality trade-off, using LLM benchmark accuracy as a proxy for quality, for all watermarks from Section 4 , with hard-constraint watermarks on the left and soft-constraint watermarks on the right. We draw a similar conclusion as in Section 5.2 : both the scheme extensions derived from our framework as well as the novel schemes outperform prior work. In particular, the soft-PPL scheme maximizes the detectability-quality trade-off across all schemes evaluated. Appendix D Proofs We follow the notation from the main text: G denotes the (context-dependent) score random vector with support \mathbb{G} , g\in\mathbb{G} a realization, and q(g)\in\Delta(\Sigma) the corresponding watermarked distribution. D.1 Red-Green Watermarks Here we formalize and then prove the different results established with respect to Red-Green watermarks. In particular, we show that KL constraints ( Equation 5 ) indeed lead to the Red-Green watermark sampling mechanism ( Theorem D.1 ). We also extend our framework with the penalized optimization problem Theorem D.2 . The penalized optimization problem is exactly the Red-Green watermark from Kirchenbauer et al. 2023 , where the scheme is parametrized by a strength parameter \delta . With the constrained version, the parameter \delta is only implicitly defined and depends on \varepsilon and p . Theorem D.1 . Let p\in\Delta(\Sigma) have full support, let g\in\mathbb{G} be non-constant, and let \varepsilon>0 . Consider \displaystyle q^{*}(g)\in\argmax_{q(g)\in\Delta(\Sigma)}\quad \displaystyle g\cdot q(g) subject to \displaystyle\mathrm{KL}(q(g)\|p)\leq\varepsilon, where \mathrm{KL}(q(g)\|p)=\sum_{u\in\Sigma}q(g)_{u}\log\frac{q(g)_{u}}{p_{u}} with the convention 0\log 0=0 . Define, for \delta\geq 0 , q_{\delta}(g)_{u}\;:=\;\frac{p_{u}e^{\delta g_{u}}}{Z_{g}(\delta)},\qquad Z_{g}(\delta):=\sum_{v\in\Sigma}p_{v}e^{\delta g_{v}}, and let M(g):=\arg\max_{u\in\Sigma}g_{u},\qquad\varepsilon_{\max}(g):=-\log\Big(\sum_{u\in M(g)}p_{u}\Big). Then: 1. If 0<\varepsilon<\varepsilon_{\max}(g) , there exists a unique \delta\in(0,\infty) such that \mathrm{KL}(q_{\delta}(g)\|p)=\varepsilon . Moreover, the optimizer is unique and equals q^{*}(g)=q_{\delta}(g) , i.e. q^{*}(g)\propto p\,e^{\delta g}. 2. If \varepsilon\geq\varepsilon_{\max}(g) , the distribution q_{\infty}(g)_{u}:=\frac{p_{u}\mathbf{1}\{u\in M(g)\}}{\sum_{v\in M(g)}p_{v}} is optimal. Proof. Fix g\in\mathbb{G} . The problem is a convex optimization problem maximizing a linear function over a convex set (the KL-divergence ball). We introduce a Lagrange multiplier \lambda\geq 0 for the inequality constraint \mathrm{KL}(q(g)\|p)-\varepsilon\leq 0 and a multiplier \nu\in\mathbb{R} for the simplex constraint \sum_{u}q(g)_{u}=1 . The Lagrangian is: \mathcal{L}(q(g),\lambda,\nu)=-\sum_{u\in\Sigma}q(g)_{u}g_{u}+\lambda\left(\sum_{u\in\Sigma}q(g)_{u}\log\frac{q(g)_{u}}{p_{u}}-\varepsilon\right)+\nu\left(\sum_{u\in\Sigma}q(g)_{u}-1\right). Note that we minimize -\mathcal{L} to maximize the objective. Taking the derivative with respect to q(g)_{u} and setting it to zero: \frac{\partial\mathcal{L}}{\partial q(g)_{u}}=-g_{u}+\lambda\left(\log\frac{q(g)_{u}}{p_{u}}+1\right)+\nu=0. Rearranging for q(g)_{u} : \lambda\log\frac{q(g)_{u}}{p_{u}}=g_{u}-\nu-\lambda\implies q(g)_{u}=p_{u}\exp\left(\frac{g_{u}-\nu-\lambda}{\lambda}\right). (18) If \lambda=0 , equation Equation 18 implies g_{u}=\nu for all u where q(g)_{u}>0 , which contradicts the assumption that g is non-constant. Thus, we must have \lambda>0 . Let \delta\coloneqq 1/\lambda\in(0,\infty) . Absorbing the normalization constants into a factor 1/Z_{g}(\delta) , we obtain the form: q_{\delta}(g)_{u}=\frac{p_{u}e^{\delta g_{u}}}{Z_{g}(\delta)},\quad\text{where }Z_{g}(\delta)=\sum_{v\in\Sigma}p_{v}e^{\delta g_{v}}. By the Karush-Kuhn-Tucker (KKT) conditions, specifically complementary slackness, we require \lambda(\mathrm{KL}(q_{\delta}(g)\|p)-\varepsilon)=0 . Since \lambda>0 , we must have \mathrm{KL}(q_{\delta}(g)\|p)=\varepsilon , unless the constraint is inactive at the global maximum of the objective over the simplex (Case 2). Let \psi_{g}(\delta)\coloneqq\mathrm{KL}(q_{\delta}(g)\|p) . We analyze the behavior of \psi_{g}(\delta) : • As \delta\to 0 , q_{\delta}(g)\to p , so \psi_{g}(0)=0 . • As \delta\to\infty , the mass of q_{\delta}(g) concentrates on the set M(g)=\argmax_{u}g_{u} . Specifically, q_{\delta}(g)\to q_{\infty}(g) , where q_{\infty}(g)_{u}=\frac{p_{u}\mathbf{1}\{u\in M(g)\}}{\sum_{v\in M(g)}p_{v}} . • The limit of the KL divergence is: \lim_{\delta\to\infty}\psi_{g}(\delta)=\sum_{u\in M(g)}\frac{p_{u}}{\sum_{v\in M(g)}p_{v}}\log\left(\frac{p_{u}/\sum_{v\in M(g)}p_{v}}{p_{u}}\right)=-\log\left(\sum_{v\in M(g)}p_{v}\right)=\varepsilon_{\max}(g). • The derivative is \psi_{g}^{\prime}(\delta)=\delta\operatorname{Var}_{U\sim q_{\delta}(g)}(g_{U}) . Since g is non-constant, the variance is positive, so \psi_{g}(\delta) is strictly increasing. Case 1: 0<\varepsilon<\varepsilon_{\max}(g) . Since \psi_{g}(0)=0 , \lim_{\delta\to\infty}\psi_{g}(\delta)=\varepsilon_{\max}(g) , and \psi_{g} is continuous and strictly increasing, there exists a unique \delta\in(0,\infty) such that \psi_{g}(\delta)=\varepsilon . This \delta satisfies the KKT conditions, making q_{\delta}(g) the unique optimizer. Case 2: \varepsilon\geq\varepsilon_{\max}(g) . The unconstrained maximum of the linear function g\cdot q(g) over the probability simplex \Delta(\Sigma) occurs at the vertices corresponding to M(g) . Among distributions supported on M(g) , q_{\infty}(g) minimizes the KL divergence to p (it is the projection of p onto the face defined by M(g) ). Since \mathrm{KL}(q_{\infty}(g)\|p)=\varepsilon_{\max}(g)\leq\varepsilon , q_{\infty}(g) is feasible. Since it achieves the global maximum of the objective function g\cdot q(g) , it is optimal. ∎ Theorem D.2 . Let p\in\Delta(\Sigma) have full support, let g\in\mathbb{G} be non-constant, and let \delta>0 . Consider \displaystyle q^{*}(g)\in\argmax_{q(g)\in\Delta(\Sigma)}\quad \displaystyle g\cdot q(g)-\frac{1}{\delta}\mathrm{KL}(q(g)\|p), We then have, q^{*}(g)\propto p\,e^{\delta g}. Proof. Fix g\in\mathbb{G} . We formulate the Lagrangian \mathcal{L}(q(g),\nu) for the optimization problem, introducing a multiplier \nu for the normalization constraint \sum_{u}q(g)_{u}=1 : \mathcal{L}(q(g),\nu)=\sum_{u\in\Sigma}q(g)_{u}g_{u}-\frac{1}{\delta}\sum_{u\in\Sigma}q(g)_{u}\ln\frac{q(g)_{u}}{p_{u}}-\nu\left(\sum_{u\in\Sigma}q(g)_{u}-1\right). The first-order optimality condition with respect to q(g)_{u} is given by setting the derivative to zero: \frac{\partial\mathcal{L}}{\partial q(g)_{u}}=g_{u}-\frac{1}{\delta}\left(\ln\frac{q(g)_{u}}{p_{u}}+1\right)-\nu=0. Rearranging the terms yields: \ln\frac{q(g)_{u}}{p_{u}}=\delta g_{u}-(1+\delta\nu)\implies q(g)_{u}=p_{u}e^{\delta g_{u}}e^{-(1+\delta\nu)}. Since e^{-(1+\delta\nu)} is a constant scaling factor independent of u (determined by the constraint \sum_{u}q(g)_{u}=1 ), we conclude that q^{*}(g)_{u}\propto p_{u}e^{\delta g_{u}}. ∎ D.2 AAR/KTH Watermarks Here we formalize and then prove the different results established with respect to AAR/KTH watermarks. We first show the shape of the optimal solution when using soft-KL constraints with any score distribution ( Theorem D.3 ), and then establish the extended watermark mechanism of AAR/KTH ( Section 4.1 ) when using a Gumbel distribution ( Theorems D.3 and D.4 ). Lastly, we show that for soft-constrained watermarks with a continuous score distribution, the optimal solution is deterministic ( Theorem D.5 ), which theoretically demonstrates the lack of diversity in soft-constrained schemes observed in Section 5.3 . Theorem D.3 . Let p\in\Delta(\Sigma) have full support, let G be a random vector with support \mathbb{G}\subseteq\mathbb{R}^{|\Sigma|} and i.i.d. coordinates from a law \mathcal{L} , and let \varepsilon\geq 0 . Consider the optimization problem \displaystyle q^{*}\in\argmax_{q:\mathbb{G}\to\Delta(\Sigma)}\quad \displaystyle\mathbb{E}\big[G\cdot q(G)\big] (19) subject to \displaystyle D_{\mathrm{KL}}\big(\mathbb{E}[q(G)]\|p\big)\leq\varepsilon, (20) where D_{\mathrm{KL}}(r\|p)=\sum_{u\in\Sigma}r_{u}\log\frac{r_{u}}{p_{u}} . Then there exists a vector \tau\in\mathbb{R}^{|\Sigma|} and a measurable tie-breaking function T:\mathbb{G}\times\Sigma\to[0,1] such that an optimal solution is given by q^{*}(G)_{u}\;=\;\begin{cases}1&\text{if }\{u\}=M(G,\tau),\\ T_{u}(G)&\text{if }u\in M(G,\tau)\text{ and }|M(G,\tau)|>1,\\ 0&\text{otherwise},\end{cases} (21) where M(G,\tau) denotes the set of maximizing indices: M(G,\tau)=\argmax_{v\in\Sigma}\big(G_{v}+\tau_{v}\big). The tie-breaking weights satisfy \sum_{u\in M(G,\tau)}T_{u}(G)=1 for all G , and T,\tau are chosen such that D_{\mathrm{KL}}(\mathbb{E}[q^{*}(G)]\|p)=\varepsilon (unless \tau=0 is feasible). In particular, if G has i.i.d. standard Gumbel coordinates, there exists \alpha\in[0,1] such that an optimal solution is given by \forall u\in\Sigma,\qquad q^{*}(G)_{u}\;=\;\mathbbm{1}\Big\{u\in\arg\max_{v\in\Sigma}\big(G_{v}+\alpha\log p_{v}\big)\Big\}, and \alpha is chosen so that \mathrm{KL}(\mathbb{E}[q^{*}(G)]\|p)=\varepsilon if feasible, else \alpha=0 . Proof. Let d=|\Sigma| and write indices as u\in\Sigma . Set r\;=\;\mathbb{E}[q(G)]\in\Delta(\Sigma). We can rewrite Equation 19 as \displaystyle\max_{q,r}\quad \displaystyle\mathbb{E}\big[G\cdot q(G)\big] (22) s.t. \displaystyle\mathbb{E}[q(G)]=r, (23) \displaystyle\mathrm{KL}(r\|p)\leq\varepsilon, (24) \displaystyle q(G)\in\Delta(\Sigma)\quad\text{for almost every $G$.} (25) The feasible set is convex and admits a Slater point, namely q(G)\equiv p (so r=p and \mathrm{KL}(p\|p)=0<\varepsilon ), hence strong duality and KKT conditions hold. Shape of an optimizer. Introduce \lambda\in\mathbb{R}^{d} as dual variable for Equation 23 and \mu\geq 0 for Equation 24 . The Lagrangian is \mathcal{L}(q,r,\lambda,\mu)=\mathbb{E}\big[G\cdot q(G)\big]+\lambda\cdot(\mathbb{E}[q(G)]-r)-\mu\big(\mathrm{KL}(r\|p)-\varepsilon\big), which we rewrite as \mathcal{L}(q,r,\lambda,\mu)=\mathbb{E}\big[(G+\lambda)\cdot q(G)\big]-\lambda\cdot r-\mu\big(\mathrm{KL}(r\|p)-\varepsilon\big). (26) For fixed (\lambda,\mu,r) , maximizing Equation 26 over q subject to Equation 25 separates over G : \sup_{q}\mathcal{L}(q,r,\lambda,\mu)=-\lambda\cdot r-\mu\big(\mathrm{KL}(r\|p)-\varepsilon\big)+\mathbb{E}\Big[\sup_{q(G)\in\Delta(\Sigma)}(G+\lambda)\cdot q(G)\Big]. (27) For any g\in\mathbb{G} , \sup_{q\in\Delta(\Sigma)}(g+\lambda)\cdot q=\max_{v\in\Sigma}(g_{v}+\lambda_{v}), and the supremum is attained by any q supported on the maximizers. Let (\lambda^{*},\mu^{*}) be an optimal dual pair and define M(G,\lambda^{*})\;=\;\arg\max_{v\in\Sigma}\big(G_{v}+\lambda^{*}_{v}\big). By strong duality, there exists a primal optimizer q^{*} that attains the supremum in Equation 27 for (\lambda^{*},\mu^{*}) . Thus, for almost every G , q^{*}(G) is supported on M(G,\lambda^{*}) . Choose a measurable tie-breaking function T:\mathbb{G}\times\Sigma\to[0,1] such that T_{u}(G)=0\quad\text{if }u\notin M(G,\lambda^{*}),\qquad\sum_{u\in M(G,\lambda^{*})}T_{u}(G)=1, and, whenever M(G,\lambda^{*})=\{u\} is a singleton, we set T_{u}(G)=1 . Then, with \tau=\lambda^{*} , q^{*}(G)_{u}\;=\;\begin{cases}1&\text{if }\{u\}=M(G,\tau),\\ T_{u}(G)&\text{if }u\in M(G,\tau)\text{ and }|M(G,\tau)|>1,\\ 0&\text{otherwise},\end{cases} which is exactly the form in Equation 21 . Let q^{0}(G)_{u}\propto\mathbbm{1}\Big\{u\in\arg\max_{v\in\Sigma}G_{v}\Big\} a solution of the unconstrained problem, and r^{0}=\mathbb{E}[q^{0}(G)] . If D_{\mathrm{KL}}(r^{0}\|p)\leq\varepsilon , then q^{0} is feasible for Equation 19 and, being optimal for the unconstrained problem, is also optimal for the constrained one; we may take \tau=0 . Otherwise D_{\mathrm{KL}}(r^{0}\|p)>\varepsilon , so the KL constraint is active at any optimum by KKT/complementary slackness. Thus there exists an optimal pair (q^{*},r^{*}) with D_{\mathrm{KL}}(r^{*}\|p)=\varepsilon , and by the previous paragraph q^{*} has the form Equation 21 for some \tau and measurable tie-breaking rule T . This proves the first part of the theorem. Gumbel case. Assume now that G has i.i.d. standard Gumbel coordinates. For any \tau\in\mathbb{R}^{d} , define q^{\tau}(G)_{u}\;=\;\mathbbm{1}\Big\{u=\arg\max_{v\in\Sigma}\big(G_{v}+\tau_{v}\big)\Big\},\qquad r(\tau)_{u}\;=\;\mathbb{E}[q^{\tau}(G)_{u}]. (28) The Gumbel-max trick gives r(\tau)_{u}\;=\;\frac{e^{\tau_{u}}}{\sum_{v\in\Sigma}e^{\tau_{v}}},\qquad u\in\Sigma. (29) Fix \tau and write Z_{v}=\tau_{v}+G_{v} . For each realization of G , \max_{v}Z_{v}=\sum_{u\in\Sigma}Z_{u}\,q^{\tau}(G)_{u}=G\cdot q^{\tau}(G)+\tau\cdot q^{\tau}(G). Taking expectations and denoting r=r(\tau) , \mathbb{E}\big[G\cdot q^{\tau}(G)\big]=\mathbb{E}\big[\max_{v}Z_{v}\big]-\tau\cdot r. (30) From the computation of the distribution of Z^{*}=\max_{v}Z_{v} , \mathbb{E}\big[\max_{v}Z_{v}\big]=\gamma+\log\Big(\sum_{v\in\Sigma}e^{\tau_{v}}\Big), (31) where \gamma is the Euler-Mascheroni constant. Combining Equation 30 and Equation 31 , \mathbb{E}\big[G\cdot q^{\tau}(G)\big]=\gamma+\log\Big(\sum_{v}e^{\tau_{v}}\Big)-\tau\cdot r. (32) Yet, we have \tau\cdot r=\sum_{u}r_{u}\log r_{u}+\log\Big(\sum_{v\in\Sigma}e^{\tau_{v}}\Big). (33) Substituting Equation 33 into Equation 32 yields \mathbb{E}\big[G\cdot q^{\tau}(G)\big]=\gamma-\sum_{u\in\Sigma}r_{u}\log r_{u}=\gamma+H(r), where H(r):=-\sum_{u}r_{u}\log r_{u} is the Shannon entropy. Thus, in the Gumbel case, optimizing Equation 19 over q is equivalent to optimizing over r=\mathbb{E}[q(G)] : \displaystyle\max_{r\in\Delta(\Sigma)}\quad \displaystyle H(r) (34) s.t. \displaystyle\mathrm{KL}(r\|p)\leq\varepsilon. (35) Introduce multipliers \lambda\geq 0 for Equation 35 and \beta\in\mathbb{R} for \sum_{u}r_{u}=1 . The Lagrangian is \mathcal{J}(r,\lambda,\beta)=-\sum_{u}r_{u}\log r_{u}-\lambda\left(\sum_{u}r_{u}\log\frac{r_{u}}{p_{u}}-\varepsilon\right)+\beta\left(\sum_{u}r_{u}-1\right). (36) Assuming r_{u}>0 , stationarity in r_{u} gives -(\log r_{u}+1)-\lambda\big(\log(r_{u}/p_{u})+1\big)+\beta=0,\qquad u\in\Sigma. Thus r_{u}=e^{C}p_{u}^{\alpha}, where \alpha:=\frac{\lambda}{1+\lambda}\in[0,1),\qquad C:=\frac{\beta-(1+\lambda)}{1+\lambda}. (37) Normalization \sum_{u}r_{u}=1 fixes e^{C} , and we obtain the family r_{u}^{*}(\alpha)=\frac{p_{u}^{\alpha}}{\sum_{v\in\Sigma}p_{v}^{\alpha}},\qquad\alpha\in[0,1). (38) Note that r^{*}(0) is the uniform distribution on \Sigma , and r^{*}(1)=p . The map \alpha\mapsto\mathrm{KL}(r^{*}(\alpha)\|p) is continuous, with \mathrm{KL}\big(r^{*}(0)\|p\big)=\mathrm{KL}(\mathrm{Unif}\|p),\qquad\mathrm{KL}\big(r^{*}(1)\|p\big)=0. Hence: • If \varepsilon\geq\mathrm{KL}(\mathrm{Unif}\|p) , the KL constraint is slack and the unconstrained maximizer of H(r) is the uniform distribution r^{*}(0) , corresponding to \alpha=0 . • If 0\leq\varepsilon\leq\mathrm{KL}(\mathrm{Unif}\|p) , there exists (by continuity) some \alpha\in[0,1] such that \mathrm{KL}\big(r^{*}(\alpha)\|p\big)=\varepsilon, and the constraint is active at the optimum. For any optimal solution r^{*} of Equation 34 – Equation 35 , the softmax bijection Equation 29 allows us to realize r^{*} as r(\tau) for some \tau . From Equation 38 , we have \log r_{u}^{*}(\alpha)=\alpha\log p_{u}+\text{const},\qquad u\in\Sigma. Hence, we see that \tau_{u} can be chosen of the form \tau_{u}=\alpha\log p_{u}+c,\qquad u\in\Sigma, for some constant c\in\mathbb{R} . Adding a constant to all coordinates of \tau does not change the argmax in Equation 28 , so without loss of generality we may take c=0 , that is, \tau_{u}=\alpha\log p_{u},\qquad u\in\Sigma. Combining this with Equation 28 yields q^{*}(G)_{u}=\mathbbm{1}\Big\{u=\arg\max_{v\in\Sigma}\big(G_{v}+\alpha\log p_{v}\big)\Big\}, for some \alpha\in[0,1] chosen as above. This completes the proof. ∎ Theorem D.4 . Let p\in\Delta(\Sigma) have full support, let G be a random vector with support \mathbb{G}\subseteq\mathbb{R}^{|\Sigma|} and i.i.d. coordinates from a Gumbel distribution, and let \delta>0 . Consider \displaystyle q^{*}\in\argmax_{q:\mathbb{G}\to\Delta(\Sigma)}\quad \displaystyle\mathbb{E}\big[G\cdot q(G)\big]-\frac{1}{\delta}\mathrm{KL}\big(\mathbb{E}[q(G)]\|p\big), where \mathrm{KL}(r\|p)=\sum_{u\in\Sigma}r_{u}\log\frac{r_{u}}{p_{u}} . Then, we have \forall u\in\Sigma,\qquad q^{*}(G)_{u}\;=\;\mathbbm{1}\Big\{u\in\arg\max_{v\in\Sigma}\big(G_{v}+\frac{1}{1+\delta}\log p_{v}\big)\Big\}. Proof. The proof is similar to that of Theorem D.3 . In Equation 36 , instead of being a Lagrangian variable, \lambda is explicitly given as \lambda=\frac{1}{\delta} . This then gives, in Equation 37 , \alpha=\frac{1}{1+\delta} . Thus, we have that, \forall u\in\Sigma,\qquad q^{*}(G)_{u}\;=\;\mathbbm{1}\Big\{u\in\arg\max_{v\in\Sigma}\big(G_{v}+\frac{1}{1+\delta}\log p_{v}\big)\Big\}, which completes the proof. ∎ Theorem D.5 . Let p\in\Delta(\Sigma) , let G be a random vector with support \mathbb{G}\subseteq\mathbb{R}^{|\Sigma|} and i.i.d. coordinates from a continuous law \mathcal{L} with finite first-order moment, and let \varepsilon\geq 0 . Consider \displaystyle q^{*}\in\argmax_{q:\mathbb{G}\to\Delta(\Sigma)}\quad \displaystyle\mathbb{E}\big[G\cdot q(G)\big] subject to \displaystyle D\big(\mathbb{E}[q(G)],p\big)\leq\varepsilon, where D:\Delta(\Sigma)\times\Delta(\Sigma)\rightarrow\mathbb{R} . Then, if the problem is feasible, there exists an optimal solution with support of size 1 . Proof. Let q be any optimal solution. Let X\in\Sigma be a random variable corresponding to the sampled token, and define \forall g\in\mathbb{G},\ \forall u\in\Sigma,\quad\mathbb{P}[X=u\mid G=g]=q_{u}(g). Then the objective rewrites as \mathbb{E}[G\cdot q(G)]=\mathbb{E}[G_{X}], and the average output distribution is the marginal of X , r(q)_{u}\coloneqq\mathbb{E}[q_{u}(G)]=\mathbb{P}[X=u],\quad u\in\Sigma. The law of G is atomless since its coordinates are i.i.d. from a continuous law. By the Dvoretsky-Wald-Wolfowitz purification theorem [ 9 ] applied to g\mapsto q(g) and the finite family of integrable functions (g,u)\mapsto g_{u}\quad\text{and}\quad(g,u)\mapsto\mathbf{1}\{u=v\},\ v\in\Sigma, there exists a measurable function f:\mathbb{G}\to\Sigma such that, with X^{\prime}=f(G) , \mathbb{E}[G_{X^{\prime}}]=\mathbb{E}[G_{X}]\quad\text{and}\quad\mathbb{P}[X^{\prime}=u]=\mathbb{P}[X=u],\ \forall u\in\Sigma. Define q^{\prime}:\mathbb{G}\to\Delta(\Sigma) by q^{\prime}(g)=e_{f(g)} , so that q^{\prime}(G) has support of size 1 almost surely. Then \mathbb{E}[G\cdot q^{\prime}(G)]=\mathbb{E}[G_{X^{\prime}}]=\mathbb{E}[G_{X}]=\mathbb{E}[G\cdot q(G)], and \mathbb{E}[q^{\prime}(G)]_{u}=\mathbb{P}[X^{\prime}=u]=\mathbb{P}[X=u]=\mathbb{E}[q(G)]_{u},\quad u\in\Sigma. Hence D(\mathbb{E}[q^{\prime}(G)],p)=D(\mathbb{E}[q(G)],p)\leq\varepsilon , so q^{\prime} is feasible and optimal. This proves the existence of an optimal solution with support of size 1 . ∎ D.3 Chi2 Watermarks Here we formalize and then prove the various results established for the one-layer SynthID and \chi^{2} watermark. In particular, we first establish the general watermark sampling mechanism for the \chi^{2} watermark in Theorem D.6 , and show in Theorem D.7 how it reduces to the 1-layer SynthID tournament in some specific cases. Theorem D.6 . Let p\in\Delta(\Sigma) have full support, let g\in\mathbb{G} , and let \varepsilon>0 . Consider \displaystyle q^{*}(g)\in\argmax_{q(g)\in\Delta(\Sigma)}\quad \displaystyle g\cdot q(g) subject to \displaystyle\sum_{u\in\Sigma}\frac{(q(g)_{u}-p_{u})^{2}}{p_{u}}\leq\varepsilon. Then there exists \delta,\mu\in\mathbb{R} such that, \forall u\in\Sigma,q^{*}(g)_{u}=p_{u}[1+\delta(g_{u}+\mu)]_{+} where [x]_{+}\coloneq\max(0,x) , \mu is chosen such that \sum_{u\in\Sigma}q^{*}(g)_{u}=1 , and \delta is chosen such that \sum_{u\in\Sigma}\frac{(q^{*}(g)_{u}-p_{u})^{2}}{p_{u}}=\varepsilon if feasible, else the greedy solution is feasible. Proof. We introduce a Lagrange multiplier \lambda\geq 0 for the inequality constraint \sum_{u\in\Sigma}\frac{(q_{u}-p_{u})^{2}}{p_{u}}=\varepsilon , a multiplier \mu\in\mathbb{R} for the simplex constraint \sum_{u}q_{u}=1 and \nu\in\mathbb{R}^{|\Sigma|}_{+} for the positivity constraints. The Lagrangian is: \mathcal{L}(q,\lambda,\mu)=-\sum_{u\in\Sigma}q_{u}g_{u}+\lambda\left(\sum_{u\in\Sigma}\frac{(q_{u}-p_{u})^{2}}{p_{u}}-\varepsilon\right)-\mu\left(\sum_{u\in\Sigma}q_{u}-1\right)-\sum_{u\in\Sigma}\nu_{u}q_{u}. Note that we minimize -\mathcal{L} to maximize the objective. Taking the derivative with respect to q_{u} and setting it to zero: \frac{\partial\mathcal{L}}{\partial q_{u}}=-g_{u}+2\lambda\frac{(q_{u}-p_{u})}{p_{u}}-\mu-\nu_{u}=0. Rearranging for q_{u} : q_{u}=p_{u}\left(1+\frac{1}{2\lambda}(g_{u}+\mu+\nu_{u})\right). In particular, we have \forall u\in\Sigma,-q_{u}\nu_{u}=0 with \nu_{u}\geq 0 , which means that, q_{u}=p_{u}\left[1+\frac{1}{2\lambda}(g_{u}+\mu)\right]_{+}. By letting \delta=\frac{1}{2\lambda} we find the shape from Theorem D.6 . ∎ Theorem D.7 . Let p\in\Delta(\Sigma) have full support, let g\in\mathbb{G} , and let \delta>0 . Consider \displaystyle q^{*}(g)\in\argmax_{q(g)\in\Delta(\Sigma)}\quad \displaystyle g\cdot q(g)-\frac{1}{2\delta}\sum_{u\in\Sigma}\frac{(q(g)_{u}-p_{u})^{2}}{p_{u}}. Then there exists \mu\in\mathbb{R} such that, \forall u\in\Sigma,q^{*}(g)_{u}=p_{u}[1+\delta(g_{u}+\mu)]_{+} where \mu is chosen such that \sum_{u\in\Sigma}q^{*}(g)_{u}=1 . In particular, if \delta\leq\frac{1}{\max_{u\in\Sigma}g_{u}-\min_{u\in\Sigma}g_{u}} , then we have \forall u\in\Sigma,q^{*}(g)_{u}=p_{u}(1+\delta(g_{u}-p\cdot g)) Proof. The derivation of the general form is identical to the first part of Theorem D.6 , where \delta is treated as a fixed parameter rather than a Lagrange multiplier. To prove the second part, assume that the non-negativity constraints are inactive, i.e., for all u\in\Sigma , 1+\delta(g_{u}+\mu)\geq 0 . Summing the probability mass constraint \sum q_{u}=1 implies: \sum_{u\in\Sigma}p_{u}[1+\delta(g_{u}+\mu)]=1\implies 1+\delta(p\cdot g+\mu)=1. Since \delta>0 , this yields \mu=-p\cdot g . Substituting this back into the solution gives the candidate form q^{*}(g)_{u}=p_{u}(1+\delta(g_{u}-p\cdot g)) . We must strictly verify that this candidate satisfies the non-negativity assumption, i.e., \forall u\in\Sigma,\quad 1+\delta(g_{u}-p\cdot g)\geq 0\iff\delta(p\cdot g-g_{u})\leq 1. The tightest constraint occurs when p\cdot g-g_{u} is maximized, which corresponds to g_{u}=\min_{v}g_{v} . Thus, we require \delta\leq\frac{1}{p\cdot g-\min_{v}g_{v}} . Observing that p\cdot g\leq\max_{v}g_{v} , we have: p\cdot g-\min_{v}g_{v}\leq\max_{v}g_{v}-\min_{v}g_{v}. Therefore, the condition \delta\leq\frac{1}{\max_{u}g_{u}-\min_{u}g_{u}} is sufficient to guarantee feasibility. ∎ D.4 SynthID Watermark In this part, we extend our framework to capture the SynthID watermark. In particular, we show that SynthID with m-layer tournament corresponds to chaining m optimization problems with \chi^{2} constraints. Theorem D.8 . Let p\in\Delta(\Sigma) have full support, let m\in\mathbb{N} , let g^{(1)},\dots,g^{(m)}\in\{0,1\}^{|\Sigma|} . Consider the chained optimization problems over q^{(1)},\dots,q^{(m)}\in\Delta(\Sigma) , q^{(i)}\in\argmax_{q\in\Delta(\Sigma)}\quad g^{(i)}\cdot q-\frac{1}{2}\sum_{u\in\Sigma}\frac{(q_{u}-q^{(i-1)}_{u})^{2}}{q^{(i-1)}_{u}}. with q^{(0)}\coloneq p . Then, we have that the family defined by, \forall i\in\{1,\dots,m\},\forall u\in\Sigma,q^{(i)}_{u}=q^{(i-1)}_{u}(1+(g^{(i)}_{u}-q^{(i-1)}_{u}\cdot g^{(i)})) is an optimal solution. Proof. Simply proceed by induction. For each step i , Theorem D.7 holds, since we have \delta=1\leq\frac{1}{1-0} . ∎ D.5 PPL Watermarks Here, in Theorem D.9 , we formalize and then prove the watermark sampling mechanism established for the soft PPL watermark. For the hard PPL watermark, the resulting constrained optimization problem is a linear programming problem and thus all results stated in Section 4.2 are standard results from the linear programming literature. Theorem D.9 . Let p\in\Delta(\Sigma) have full support, let G be a random vector with support \mathbb{G}\subseteq\mathbb{R}^{|\Sigma|} and i.i.d. coordinates from a continuous law \mathcal{L} , and let \varepsilon\geq 0 . Consider the optimization problem \displaystyle q^{*}\in\argmax_{q:\mathbb{G}\to\Delta(\Sigma)}\quad \displaystyle\mathbb{E}\big[G\cdot q(G)\big] subject to \displaystyle(p-\mathbb{E}_{G}[q(G)])\cdot\log p\leq\varepsilon. Then, an optimal solution is given by \forall g\in\mathbb{G},q^{*}(g)=\arg\max(g_{i}+\lambda\log p_{i}), where \lambda is chosen such that (p-\mathbb{E}_{G}[q(G)])\cdot\log p=\varepsilon if feasible, else \lambda=0 . Proof. By Theorem D.5 , there exists an optimal solution q with support of size 1 a.s., i.e. there is a measurable f:\mathbb{G}\to\Sigma such that q(g)=e_{f(g)},\qquad\forall g\in\mathbb{G}. We now solve the problem over such deterministic q . We introduce a Lagrange multiplier \lambda\geq 0 for the constraint. The Lagrangian is \displaystyle\mathcal{L}(q,\lambda) \displaystyle=\mathbb{E}[G\cdot q(G)]-\lambda\big((p-\mathbb{E}[q(G)])\cdot\log p-\varepsilon\big) (39) \displaystyle=\mathbb{E}\big[(G+\lambda\log p)\cdot q(G)\big]-\lambda\big(p\cdot\log p-\varepsilon\big). (40) For fixed \lambda , the term in Equation 40 is maximized by f_{\lambda}(g)\in\arg\max_{i\in\Sigma}\big(g_{i}+\lambda\log p_{i}\big). If the unconstrained maximizer (corresponding to \lambda=0 ) already satisfies (p-\mathbb{E}[q^{0}(G)])\cdot\log p\leq\varepsilon , then \lambda=0 . Otherwise the constraint is active at the optimum, so \lambda>0 and (p-\mathbb{E}[e_{f_{\lambda}(G)}])\cdot\log p=\varepsilon. This concludes the proof. ∎ Appendix E Watermarked Text Examples This section presents a sample user prompt together with the corresponding watermarked responses. We also report the associated p-values and perplexity scores, where perplexity is computed using Qwen3-30B . The formatting of the LLM response has been lightly edited for readability. Each response is 200 tokens long. User Prompt Why can’t we just taste candy or Sweets and then spit it out to avoid its unhealthy attributes? What makes us swallow it to get satisfaction? AAR, \,p=7.4e-5 , \,PPL=4.8 You’re right that our brains are wired to enjoy the taste of sweets, but there are several reasons why we tend to swallow them, even though we know they’re unhealthy. Here are a few possible explanations: 1. Evolutionary adaptations : For millions of years, humans relied on sugar-rich foods like fruits and berries for energy and survival. As a result, our brains developed a preference for sweet tastes, which signaled the presence of energy-rich compounds. In many cases, it was beneficial to consume these foods and store the energy for later use. Our brains haven’t fully adjusted to the modern environment, where sugary foods are abundant but not necessarily necessary for survival. 2. Reward processing : Sugar activates the brain’s reward centers, releasing feel-good chemicals like dopamine, endorphins, and opiids. These sensations create a strong psychological association between sweetness and pleasure, reinforcing the behavior of consuming sugary foods. Our brains are wired to seek out experiences that stimulate these reward pathways, even if Chi2, \,p=0.0 , \,PPL=5.7 You’re right that it would be simpler if our body automatically spat out foods that aren’t beneficial to us, but that’s not how our digestive system is designed. Here are a few reasons why: 1. Evolutionary design: The human body has an amazing ability to adapt and learn, but it’s based on the principle of survival and reproduction. Our digestive system has evolved over millions of years to process a wide range of foods, including those that are high in sugar and other energy-rich nutrients. These foods were once scarce, so our bodies were designed to rapidly absorb their nutrients for energy. This allowed our ancestors to survive and thrive in times of scarcity. 2. The role of the brain: Our brain plays a significant role in controlling what we eat and how our body processes it. The pleasure and satisfaction we experience when eating something sweet, like candy, is mediated by a system KGW, \,p=0.0 , \,PPL=6.4 You’re right that we can choose to spit out candy or sweets if we know they’re unhealthy. However, the reason we often can’t help but swallow and enjoy these treats is deeply rooted in human psychology, neuroscience, and biology. Here are some possible explanations: 1. Evolutionary history : Throughout human evolution, sweet tastes were a signal of nutrient-dense foods that were scarce and valuable. Our brains evolved to associate sweet tastes with pleasure and reward, encouraging us to consume them and gain energy. In modern times, we still respond to sweet tastes as a cue for pleasure, but our diets no longer match the evolutionary landscape. 2. Dopamine release : When we eat something sweet, our brains release dopamine, a neurotransmitter associated with pleasure, reward, and motivation. This release can be intense and immediate, making it difficult to resist the desire to consume more. 3. Conditioned response : We often learn to associate certain foods, including sweets, with pleasure and satisfaction PPL (Hard), \,p=1.1e-9 , \,PPL=7.4 It’s indeed intriguing as to why our brains would lead us to consume sweets, knowing their potential harm, and yet, we can’t help but crave them. There are several biological, psychological, and historical reasons behind this phenomenon. Biological reasons: 1. Evolutionary legacy: In the past, sweets were rare and often associated with high-calorie energy sources, making them valuable for survival. Our brains were adapted to consume these energy-dense foods to store fat for potential famines. This instinctual response has been retained, although no longer necessary in modern times with an abundance of food available. 2. Dopamine release: Consuming sweets and other pleasurable foods triggers the release of dopamine, a neurotransmitter associated with pleasure signaling. The brain’s reward system is activated due to the combination of sugar, fat, and other nutrients releasing dopamine, leading a craving for more. 3. Lingering taste after spittle: Some studies indicate even a small amount PPL (Soft), \,p=1.4e-3 , \,PPL=5.4 You’re right that it would be ideal if we could just taste sweets and spit them out, avoiding the negative effects of high sugar and calorie intake. However, the process of eating and swallowing is complex, and it’s influenced by both physiological and psychological factors. Here are some reasons why we tend to swallow sweets: 1. Evolutionary origins: In the past, eating sweet-tasting foods indicated the presence of energy-rich carbohydrates, which were essential for survival. Our ancestors would consume these foods to sustain themselves, especially during times of scarcity. This evolutionary adaptation has been passed down through generations, making us more likely to associate sweet tastes with energy and satisfaction. 2. Brain chemistry: When we eat sweets, they activate the brain’s reward centers, releasing feelgood hormones like dopamine. This triggers a sense of pleasure and satisfaction, which can lead to overconsumption. The brain’s reward system is designed to reinforce behaviors that provide energy and survival benefits, making us more likely to repeat them SynthID, \,p=0.0 , \,PPL=13.9 You’re right that it’d seem logical to just taste and spit out candy or sweets to avoid their potential negative effects on our health. However, our bodies have complex neurological and physiological mechanisms that play a significant role in our eating behavior. Here are some reasons why we tend to swallow the candy and experience the satisfaction we’re talking about: 1. Evolutionary mechanisms : Throughout history, our brains were designed to respond quickly to available energy sources, like sugary or fatty foods, as these were essential for survival. In the case of sweets, our brain is programmed to respond strongly to glucose (sugar), releasing the neurotransmitter dopamine in the process. This associative reward network drives us to repeat behaviors associated with pleasure, making us reach out for those sweet treats again. 2. Familiar texture and taste : When you put something pleasant in your mouth, the sensory experience is unique in several ways: It satisfies your sweet tooth by releasing dopamine in your brain. Our brains are set up to