arXiv CSopen access

Watermarkable Multi-Draft Speculative Sampling via Poisson Processes

· arxiv_cs

arXiv CS · Papers · License: Open Access

cryptography cybersecurity privacy security

cryptography, security, privacy, cybersecurity

WATERMARKABLE M ULTI -D RAFT S PECULATIVE S AMPLING VIA P OISSON P ROCESSES Yanxiao Liu1,⋆ , Sicheng Wan2,⋆ , Zhan Gao1 , and Deniz Gündüz1 Imperial College London, 2 University of Washington, ⋆ equal contribution

arXiv:2609.21858v1 [cs.CR] 18 Sep 2026

A BSTRACT Large language models (LLMs) have achieved state-of-the-art performance across a wide range of tasks, motivating two important aspects of deployment: inference efficiency and output provenance, which can be tackled by speculative sampling and watermarking, respectively. However, recent works have shown that combining these two goals is highly nontrivial and can be potentially impossible. In this work, we develop a novel multi-draft speculative sampling algorithm based on Poisson processes that improves the frontier of this fundamental trade-off. The proposed algorithm has strong sampling efficiency on its own and, more interestingly, is naturally watermarkable: we can embed an unbiased watermark without degrading speculative acceptance. Moreover, our algorithm is based on an exact list-couplingwithout-communication scheme, which yields a drafter invariance property that benefits both sampling and watermarking. It is the first multi-draft, drafter-invariant speculative sampling scheme that maintains both watermark strength and sampling efficiency, and we experimentally verify its strong performance in both aspects.

I NTRODUCTION

Large language models (LLMs) have become a central component of modern generative AI, achieving strong performance in dialogue, reasoning, code generation, and open-ended content creation. Their probabilistic nature based on autoregressive sampling enables them to generate diverse responses (Brown et al., 2020; Grattafiori et al., 2024; Singh et al., 2025). However, as LLM-generated text becomes increasingly fluent and difficult to distinguish from human-written content, concerns about accountability, provenance, misuse, and intellectual property have attracted increasing attention (Wu et al., 2025). For instance, ChatGPT-generated scientific abstracts are hard for human reviewers to distinguish from human-generated ones, yet they may contain fabricated data (Shumailov et al., 2024). Hence, watermarking has become an important, and potentially necessary, tool for tracing the provenance of LLM-generated text by embedding statistical signals into the sampling process while preserving output quality (Kirchenbauer et al., 2023; Aaronson and Kirchner, 2023; Kuditipudi et al., 2023). For instance, reflecting its growing importance, Anthropic recently announced that future Claude models will generate text with embedded watermarks (Anthropic, 2026). Apart from provenance, the efficiency of autoregressive generation is another bottleneck in the system pipeline. Speculative sampling (also known as decoding), has emerged as a promising approach to accelerate content generation without changing the output distribution of the target model (Chen et al., 2023; Leviathan et al., 2023). However, speculative sampling is not independent of watermarking. On the contrary, recent works (Hu and Huang, 2024; He et al., 2026) show that combining the two is highly nontrivial: in (Hu and Huang, 2024), a “no-go” theorem was proved, showing that one cannot embed a watermark without degrading the performance of speculative sampling, thereby establishing a fundamental trade-off between watermark strength and speculative sampling efficiency. He et al. (2026) recently improves this trade-off by considering alternative watermark metrics. In this work, we ask the following question: can we design a watermarkable speculative sampling scheme that further improves the trade-off (Hu and Huang, 2024; He et al., 2026) by increasing speculative sampling efficiency without compromising watermark detectability? We answer this question in the affirmative: we design a novel multi-draft speculative sampling algorithm that achieves strong acceleration performance, can naturally embed unbiased watermark, and, more importantly, has watermark strength that does not degrade as the sampling efficiency 1

increases.1 Our multi-draft construction relies on Poisson processes (Maddison, 2016; Li and Anantharam, 2021) and yields a list-coupling without communication scheme, which endows our algorithm with a drafter-invariance property (Daliri et al., 2025; Rowan et al., 2025) that becomes more desirable and essential in the context of watermarking. Our contributions are two-fold: • Multi-draft speculative sampling: We design a novel multi-draft speculative sampling algorithm that generates and verifies multiple draft continuations. Our scheme uses desirable properties of Poisson processes, which naturally yield a drafter invariance property (Daliri et al., 2025). Compared with (Rowan et al., 2025), which has been shown to outperform other existing methods, we theoretically prove that our acceptance rates are higher and empirically demonstrate better acceleration performance across multiple models and datasets. • Efficiency-preserving watermarking: Besides desirable sampling efficiency, our algorithm is naturally watermarkable with the use of Poisson processes, which can embed a recoverable statistical signal while maintaining the distribution unbiased. By building the watermark directly into the sampling procedure through keyed randomness, we maintain watermark strength while preserving sampling efficiency, thereby improving the trade-off frontier identified in (Hu and Huang, 2024) and achieving better overall performance.

R ELATED W ORKS

LLM Decoding and Speculative Sampling. Standard autoregressive decoding methods, including top-k sampling (Radford et al., 2019; Fan et al., 2018), nucleus sampling (Holtzman et al., 2020), and the permute-and-flip decoder (Zhao et al., 2025a), generate tokens sequentially; and therefore, suffer from the inherent latency of one target-model call per token (Stern et al., 2018). Speculative sampling (Chen et al., 2023; Leviathan et al., 2023) addresses this bottleneck by using a smaller draft model to propose several future tokens, while the larger target model verifies the proposed continuations in parallel. The efficiency gain depends on how well the draft distribution matches the target distribution. Recent works further improve this paradigm through optimal-transport-based token selection (Sun et al., 2023), tree-based inference and verification (Miao et al., 2024), and multi-draft architectures (Khisti et al., 2025; Rowan et al., 2025). It can also be used to accelerate diffusion models (De Bortoli et al., 2025; Bullo et al., 2026). Watermarking. LLM watermarking aims to embed detectable statistical signals into generated text while preserving fluency and utility. Early logit-bias methods pseudorandomly select green-list tokens and detect the resulting bias by hypothesis testing (Kirchenbauer et al., 2023), while later works improve robustness, accessibility, and probability balance (Wu et al., 2023; Giboulot and Furon, 2024; Park et al., 2026). A parallel line studies unbiased watermarking, where the sampler maintains the distribution while correlating the output with secret randomness (Kuditipudi et al., 2023; Hu et al., 2023; Christ et al., 2024). They connect watermarking to information theory (Moulin and O’Sullivan, 2003) and statistics, including detection power, false-positive control, optimal tests, and couplings (Li et al., 2025; He et al., 2025; Tsur et al., 2025). Related works include robust or multi-bit attribution (Zhao et al., 2023; Boroujeny et al., 2024; Qu et al., 2025), and efficient identification of watermarked segments (Zhao et al., 2025b). In recent works (Hu and Huang, 2024; He et al., 2026) an inevitable trade-off between speculative sampling and watermarking has been discussed. Poisson Functional Representation (PFR). PFR is a sampling scheme introduced in (Li and El Gamal, 2018), with related Poisson process constructions also discussed by Maddison et al. (2014); Maddison (2016). It selects a sample from a target distribution through a Poisson process and a proposal distribution, and has been applied to information theory settings (Li and Anantharam, 2021; Khisti et al., 2024; Liu and Li, 2024; 2025; Liu et al., 2026) and machine learning (He et al., 2024; Liu et al., 2024; Zhou et al., 2026; Flamich et al., 2026). It can be extended to list-coupling (Li and Anantharam, 2021) by the mapping theorem (Last and Penrose, 2017) of Poisson process, and achieves the best known bound on coupling without communication (Daliri et al., 2025). Notations. xi:j denotes the sequence xi , xi+1 , . . . , xj , and we let x:j := x1:j . P ≪ Q denotes that probability measure P is absolutely continuous with respect to Q. The logarithm is on base 2. 1 Our multi-draft scheme does not contradict the inevitable trade-off (Hu and Huang, 2024): it still applies for a fixed number of drafts. We improve the trade-off along an additional dimension, namely, the number of drafts.

S PECULATIVE S AMPLING

We first briefly review the technical background of speculative sampling (Chen et al., 2023; Leviathan et al., 2023; Sun et al., 2023; Rowan et al., 2025). Given volcabulary V and a context x:t := (x1 , x2 , . . . , xt ), an autoregressive language model Mb generates the next token by sampling from the conditional distribution Mb (·|x:t ) under temperature sampling (Ackley et al., 1985; Ficler and Goldberg, 2017). Speculative sampling accelerates this process by introducing a smaller and cheaper draft model Ms , which proposes several candidate tokens before the target model verifies them. Given a prefix x:t , one iteration of the speculative sampling consists of the following three stages: 1. Draft Stage. The draft model Ms sequentially samples L candidate tokens x̃t+1 , . . . , x̃t+L . For each position i = 1, . . . , L, we record the draft distribution Ms (·|x:t , x̃t+1:t+i−1 ). 2. Computation Stage. Conditioned on the drafted context, the target model Mb evaluates the corresponding conditional distributions, potentially in parallel: Mb (·|x:t ), Mb (·|x:t , x̃t+1 ), . . . , Mb (·|x:t , x̃t+1:t+L ), 3. Selection Stage. By the distributions Ms and Mb , we accept the longest prefix of the drafted tokens until the first rejection, and a correction token is sampled from a specific residual distribution. If all L drafts are accepted, one more token from the target is sampled. The acceptance-correction procedure ensures that the generated tokens follow exactly the same distribution as direct autoregressive sampling, i.e., improving decoding efficiency does not change the target law. The exactness is achieved via a recursive token-level maximal coupling (Algorithm 1), where we use P, Q to denote the target and draft distributions, respectively, and achieve X Pr(X = Y ) = min(P (x), Q(x)) = 1 − ∥P − Q∥TV , x∈V

i.e., the closer P and Q are, the higher the probability that the draft token will be accepted. Together with the extra sampled token, there could be at most L + 1 tokens generated in each iteration, and therefore, the speedup is up to (L + 1) times if the decoding time of the draft model is negligible. Kobus and Gündüz (2025) proposed a new sampling scheme (Algorithm 2) based on exponential random variables, which, together with the token probabilities, determine the scores assigned to the tokens. The token with the smallest score wins the race and follows the desired distribution. Algorithm 1: Token-level sampling (Sun et al., 2023; Chen et al., 2023; Leviathan et al., 2023) Input: Target and draft distribution P, Q; X ∼ Q. Compute the residual Pres : for any x ∈ V, P (x) − min{P (x), Q(x)} P Pres (x) = . 1 − y min{P (y), Q(y)} Sample U ∼ Unif(0, 1) if U ≤ min (1, P (X)/Q(X)) : return Y = X // Accept return Y ∼ Pres // Correction

Algorithm 2: Token-level sampling by exponential race (Kobus and Gündüz, 2025) Input: Target and draft distribution P, Q. for i ∈ V do Ei ∼ Exp(1) X ← arg mini∈V Ei /Q(i) Y ← arg mini∈V Ei /P (i) if X = Y : return Y = X // Accept return Y // Correction

WATERMARKABLE S PECULATIVE S AMPLING

We first present a single-draft version for illustration. Our use of Poisson processes naturally embeds the watermark into the sampling process via pseudorandomness. The formal multi-draft scheme, which further accelerates autoregressive generation without compromising watermark strength, will be presented in Section 5. Before proceeding, we first introduce two key components of our scheme. 4.1

U NBIASED WATERMARK

A good watermark should be detectable from the generated text while preserving output quality. Unbiased schemes use pseudorandomness to couple tokens with secret keys, so that the watermark can be detected through statistical tests without significantly altering the marginal distribution. 3

Suppose P̃ is a base distribution over V, an unbiased watermark is a decoding rule such that, for each seed ζ, it induces a watermarked distribution P̃ζ , which preserves P̃ after averaging over the seed, Eζ [P̃ζ (v)] = P̃ (v),

∀v ∈ V.

The Gumbel watermark (Aaronson and Kirchner, 2023), which uses the Gumbel-max trick (Gumbel, 1954) and lets the seed ζ determine the Gumbel noise, is unbiased, and we leverage a similar idea for our scheme. Let ut (·|x, yt−1 ) : V → R be a real-valued function (a.k.a. logits) that encodes the model’s preferences on words and T be the temperature, the softmax sampling is equivalent to yt = argmaxy∈V ut (y) T + Gt (y), Gt (y) ∼ Gumbel(0, 1) i.i.d for each t, y, where the Gumbel noise can be generated by Gumbel(0, 1) ∼ − log(log(1/Unif([0, 1]))). A random rt ∼ (Unif([0, 1]))|V| can be represented by Gt (y) = − log(−log(rt (y))). We can replace Unif([0, 1]) by a pseudo-random function rt (y) = Fyt−m:t−1 ,k (y) with prefix length m, and employ yt = argmaxy∈V ut (y) T − log(− log(rt (y))). (1) Conditioned on a secret key k, rt (y) is a deterministic function, but over the distribution of k, rt (y) is computationally indistinguishable from samples drawn from a truly i.i.d. uniform distribution. Pn The detector has the key k and computes the watermark score t=m+1 − log 1 − rt (yt ) . If y1:n is unwatermarked, the expected score is n − m; otherwise, it is larger and the watermark is detected. Our algorithm relies on Poisson processes and also incorporates the use of pseudo-random functions. 4.2

P OISSON F UNCTIONAL R EPRESENTATION (PFR)

We leverage a scheme called PFR (Li and El Gamal, 2018); related works are discussed in Section 2. iid

Definition 4.1 (PFR). Let (Ti )i ∼ PP(1) be a Poisson process of rate 1, independent of Zi ∼ ν for i = 1, 2, . . .. (Zi , Ti )i is a Poisson process of intensity measure Q × λ[0,∞) , where λ[0,∞) is the Lebesgue measure over [0, ∞). Fix distribution P over Z such that P ≪ Q. PFR selects the point −1 Z = ZK where K := argmini Ti · dP /dQ(Zi ) . (2) Remark 4.2. By drawing a sequence (Zi )i from the reference distribution Q and a sequence of times (Ti )i , the PFR selects a sample following the target distribution P . The sample Zi with the smallest Ti only follows Q; to obtain a sample from P exactly, we inflate the time by factor (dP /dQ(Zi ))−1 . 4.3

WATERMARKABLE S PECULATIVE S AMPLING VIA P OISSON P ROCESSES

Core idea. We unify watermarking and speculative sampling through a keyed Poisson coupling. Every emitted token is target-distributed, while the draft model only controls how many such samples are emitted. The watermarking is performed at the coupling level, rather than through a post-hoc reweighting of marginals. This allows our scheme to stay efficient when embedding watermark. 2 Algorithm 3 is a sketch of our single-draft speculative sampling with watermark, see a detailed implementation in Algorithm 9. Fixing a Poisson process Πk by key k; with context c, we denote the labeled Poisson process and the sample selected by PFR by G(k, c) and PFR(P̄ (·|c), Π), respectively. Note that for discrete LLM target distributions, as we prove in Appendix A.1, PFR reduces to the exponential race (Kobus and Gündüz, 2025). However, Poisson processes become useful, and even necessary, when we extend to the multi-draft version, where we generate multiple samples that all follow the target distribution, by the mapping theorem (Last and Penrose, 2017) for Poisson processes. He et al. (2026) used a different watermark metric to improve the trade-off frontier. In comparison, our scheme is robust across different watermark measurements, as we consider various scores (Aaronson and Kirchner, 2023; Hu and Huang, 2024; Li et al., 2025; Lattimore, 2026) in Appendix E, which makes our scheme directly comparable to existing watermarking schemes. We use Aaronson’s score (Aaronson and Kirchner, 2023) in the main section, which is introduced as follows. 2 The Maintain Watermark Strength scheme (Hu and Huang, 2024) shares the same spirit; see Figure 1. Nevertheless, our scheme can be extended to the multi-draft version in Section 5, achieving further acceleration.

Algorithm 3: Watermarkable Speculative Sampling via Poisson Processes (Simplified) Given :lookahead K, output length N , initial prompt w1:n , Poisson generator G, secret key k while n < N do h ← w1:n ; L ← min{K, N − n}; accepted ← true; for s = 1 to L do cs ← h ∥ w̃1:s−1 ; Πs ← G(k, cs ) // keyed Poisson for watermark w̃s ← PFR(Q(·|cs ), Πs ) for s = 1 to L do // evaluation in parallel ys ← PFR(P (·|cs ), Πs ); as ← 1 {ys = w̃s }; wn+1 ← ys ; n ← n + 1; if as = 0 : accepted ← false and break // later draft contexts are invalid if accepted and n < N : // all draft tokens accepted Π⋆ ← G(k, w1:n ) // keyed Poisson source wn+1 ← PFR(P (·|w1:n ), Π⋆ ); n ← n + 1 // bonus

If the output of key k is w1:N and n0 is the initial prompt length, the detector evaluates the scored positions T := {n0 + 1,. . ., N }. For t ∈ T , let ct := w:t−1 be the prefix before position t, and the detector regenerates Πt := G(k, ct ). For each v ∈ V, let rt (v) := exp(−µ(v)τt (v)) be the induced uniform value where τt (v) ∼ Exp(µ(v)) is the first arrival time of v in Πt , and the detector computes X SA := − log(1 − rt (wt )), (3) t∈T P whose expectation is E[SA ] ≥ |T | + (π 2 /6 − 1) t∈T E[H(P (·|w:t−1 ))]. If the sequence is not generated with k, the observed wt is independent of Πt , rt (wt ) ∼ Unif[0, 1] and E[SA ] = |T |. At-a-Glance Experimental Validation. We use Figure 1 to illustrate how our algorithm improves the trade-off by increasing sampling efficiency without degrading watermark strength.

Figure 1: The trade-off between watermark and efficiency on existing methods (Hu and Huang, 2024): Vanilla Speculative Sampling (VSpS), Maintain Watermark Strength (MWS), and Maintain Sampling Efficiency (MSE), and our algorithms (PFR, and multi-draft MPFR that is presented in Section 5). For both PFR (lower-left) and MPFR (upper), we embed watermark (measured by Average Negative Log P-value Per Token (ANLPPT)) without degrading the Average Accepted Tokens Per Step (AATPS). This figure uses Qwen2.5-7B-Instruct and Qwen2.5-0.5B-Instruct as the target and draft, respectively, on dataset CNN _ DAILYMAIL. Experiments on more models and datasets are shown in Appendix D.

4.4

D RAFTER I NVARIANCE

Conventional speculative sampling suffers from a major disadvantage (Daliri et al., 2025): when the small drafter model Md changes, e.g., because of a model update, the tokens generated by the large model may also change due to the coupling (Algorithm 1). In autoregressive language models, this can be even more problematic, since users usually do not want the model output to change under a fixed random seed: stable models allow the output to be reliably reproduced for use, testing, and debugging. Based on the coupling without communication (Bavarian et al., 2016; Li and El Gamal, 2018), drafter invariant sampling has recently been studied (Daliri et al., 2025). It refers to the case where, conditioned on the shared randomness R and the context x:t , and potentially other things, the outputprefix law does not depend on the draft model. Let Y1:τ , Ye1:τ denote the output sequences from different drafter models in block τ , we define the following notion. Definition 4.3. The algorithm A is said to be stopping-time drafter invariant if, for every stopping time value τ0 in the support of τ , every 1 ≤ j ≤ τ0 , and every output prefix y1:j , we have P Y1:j = y1:j R, x:t , τ = τ0 = P Ye1:j = y1:j R, x:t , τe = τ0 . Proposition 4.4. Our Algorithm 3 is stopping-time drafter invariant. The proof can be found in Appendix C.1.1. The stopping-time drafter invariance is not satisfied by most existing schemes, e.g., SpecTr (Sun et al., 2023), SpecInfer (Miao et al., 2024), and also (Rowan et al., 2025, Algorithm 2). Intuitively, a stronger notion of drafter invariance helps watermarking but degrades sampling efficiency. The original definition, referred to as the “strong drafter invariance” (Daliri et al., 2025), was shown to have degraded sampling efficiency (Rowan et al., 2025), in where the authors hence proposed a “conditional drafter invariance” that also conditions on the realized draft sequence. We propose the stopping-time drafter invariance that is weaker than the former to admit a better sampling efficiency, but stronger than the latter and more suitable for watermarking. The conditioning on τ is intentional: it separates the role of the drafter in determining the length of the current speculative block from its role in determining the content of the emitted tokens. Thus, the drafter is allowed to affect the stopping time, and hence the sampling efficiency, but once this stopping time is fixed, the law of every emitted prefix is governed by the target-side randomness and does not depend on the full realized draft sequence. In watermarking, such invariance is important. A watermark is usually tied to pseudorandomness and is detected from the final output sequence, while speculative sampling introduces an additional ambiguity: an emitted token may come from the draft, the target correction, or the bonus, which affects the watermark statistic, and is one reason behind the no-go trade-off in (Hu and Huang, 2024) and the use of acceptance-side information in (He et al., 2026). However, a watermark detector typically observes only the final tokens and the secret key, not the realized draft sequence or acceptance-side information. Stopping-time drafter invariance is hence better aligned with watermarking: changing the drafter may affect the stopping time and the efficiency, but conditional on the block length, it does not introduce draft-specific dependence into the target-keyed token prefix. This makes the watermark directly tied to the target-side keyed randomness and leads to a more reproducible provenance signal. Moreover, (He et al., 2026) proposed a new watermark metric that improves the trade-off between watermark strength and sampling efficiency (Hu and Huang, 2024); see, e.g., (He et al., 2026, Figure 1). However, their analysis relies on the maximal coupling probability P(X = Y ) = 1 − ∥P − Q∥TV for coupling X ∼ P, Y ∼ Q (Thorisson, 2000; Den Hollander, 2012). In contrast, the best matching probability under no-communication coupling is fundamentally different: P(X = Y ) ≤ (1 − ∥P − Q∥TV )/(1 + ∥P − Q∥TV ). (4) Thus, enforcing drafter invariance may appear to fundamentally reduce sampling efficiency. We argue, however, that this loss is not inevitable: by using Poisson processes, we derive a multi-draft, drafter-invariant extension that greatly improves the token acceptance rate, as elaborated as follows.

WATERMARKABLE M ULTI -D RAFT S PECULATIVE S AMPLING

We now extend our Algorithm 3 to multi-draft speculative sampling, by a multi-sample generalization of PFR built on the mapping theorem for Poisson processes (Li and Anantharam, 2021). 6

(b)

We use Mt and Md to denote the target and draft language models with 1 ≤ b ≤ B. They induce (b) conditional distributions Mt (·|x:t ) and Md (·|x:t ), which give the probability of the next token given the current context x:t , usually denoted by c. In multi-draft speculative sampling (Miao et al., 2024; Sun et al., 2023; Khisti et al., 2025; Rowan et al., 2025), at each context c, we generate a list of (1) (B) B proposal drafts, often i.i.d. in practice (Rowan et al., 2025; Sun et al., 2023) from Md , . . . , Md . These proposal drafts induce a depth-L speculative tree rooted at the current prefix, which is then verified in parallel with Mt . At each step, if at least one of the B candidate tokens is accepted, the first accepted token will be appended to the final output; otherwise, the verification procedure stops. The output is Y1:τ , where τ is the number of accepted tokens plus one. −1 dP The PFR (Definition 4.1) selects a sample Z̃P from (Zi )i that has the smallest score Ti · dQ (Zi ) , where (Ti )i ∼ PP(1), and it follows the target distribution P . To get B samples, multi-sample PFR (MPFR) selects samples with the smallest, second smallest, and so on up to the B-th smallest scores: iid

Z̃P (1), Z̃P (2), . . . , Z̃P (B) ∼ P,

(5)

where the exactness follows (Li and Anantharam, 2021); see Appendix A.3 for the formal definition and implementation. For multi-draft speculative sampling, we use B i.i.d. drafts from a model Md , and at each sampling step we consider P := Mt (·|x:t ) as the target distribution and Q := Md (·|x:t ) as the proposal distribution. Note that we consider identical proposals (Sun et al., 2023) in this section, but our framework can also be generalized to non-identically distributed proposals (Rowan et al., 2025), which is deferred to Appendix B.4. Our scheme is sketched in Algorithm 4; see Algorithm 10 for details. The core idea is as follows. To implement a multi-draft algorithm, Algorithm 4 uses context-indexed mapped Poisson processes. Starting from the root prefix h = w1:n , we build a depth-ℓ speculative tree, where each occupied context c is assigned a keyed source Π(c) and generates ν(c) drafts from Q(·|c) via MPFR. We then compute the target-side sample MPFR(P, Π(c), 1) for every c and emit tokens by following the unique realized target path, continuing as long as the current target winner belongs to the draft set. Importantly, the Poisson process is indexed by contexts rather than by drafter identities, and thus MPFR works in a way that makes the emitted tokens tightly tied to the prefix and the secret key, which helps watermark detection. In comparison, (Rowan et al., 2025) uses draft-indexed algorithms, keeps a set of currently viable draft indices, and chooses the next emitted token using only the active drafts. This is a natural implementation, but the active set makes the next emitted token depend on the realized draft sequences, causes the output to retain hidden dependence on draft-side trajectories, and hence only satisfies their conditional drafter invariance, but not stopping-time drafter invariance (Definition 4.3). Theorem 5.1. The acceptance probability of at least one token at the current step satisfies X B P(accept) ≥ 1 − P (i) P (i) (P (i) + Q(i)) .

(6)

i∈V

The proof is in Appendix B, where we also give a generalized version that accounts for the number of active drafts, and demonstrate our advantages over the existing schemes (Rowan et al., 2025).

E XPERIMENTS

We evaluate whether our algorithms improve the empirical frontier between sampling efficiency and watermark detectability, while preserving generation quality. The headline configuration uses Qwen2.5-7B-Instruct as the target and Qwen2.5-0.5B-Instruct as the drafter on CNN/DAILY M AIL. Other model-dataset cells, full per-L and per-B tables, and ablation details are deferred to Appendix D. Baselines. We compare against four families of methods, all run in a common harness with the same prompts, decoding parameters, and watermark key. (i) Watermark-only reference. BASIC UWM is autoregressive Gumbel-style unbiased watermarking without speculation (Aaronson and Kirchner, 2023); it sets the watermark-strength ceiling. (ii) Speculation-only reference. VS P S 7

Algorithm 4: Watermarkable Multi-Draft Speculative Sampling (Simplified) Given :lookahead L, number of homogeneous drafts B, output length N , target model P , draft model Q, initial prompt w1:n , keyed source generator G, and secret key k while n < N do h ← w1:n ; ℓ ← min{L, N − n} // root context of current block initialize root context h with multiplicity B for s = 1 to ℓ do // build context tree up to depth ℓ for each currently occupied context c do Π(c) ← G(k, c) // keyed Poisson source for watermark generate ν(c) drafts by Q(·|c) using MPFR(Q(·|c), Π(c), ·) // Eq.(5) merge equal draft tokens into child contexts and update their multiplicities compute target-side sample y(c) = MPFR(P (·|c), Π(c), 1) for every c // in parallel c⋆ ← h; accepted ← true for s = 1 to ℓ do emit the target token y(c⋆ ) and append it to the output if y(c⋆ ) ∈ / D(c⋆ ) : // D(c⋆ ) contains distinct draft tokens at c accepted ← false and break // first rejection ends the block if n = N : break c⋆ ← c⋆ ∥ y(c⋆ ) // move to the next realized context if accepted and n < N : emit one bonus token by MPFR(P (·|c⋆ ), G(k, c⋆ ), 1)

Table 1: Multi-draft results on Qwen2.5-7B-Instruct and Llama-3.1-8B-Instruct on CNN/DAILY M AIL and ELI5, L = 4. We report the average accepted tokens per step (AATPS) and token rate (TR). The better result between MPFR and GLS for each setting with the same B is in bold. Each cell is computed over the 1000 prompts and 3 different seeds. See more detailed data in Appendix D.4. Qwen-CNN/DM

Qwen-ELI5

Llama-CNN/DM

Llama-ELI5

Decoder

AATPS

MPFR MPFR MPFR MPFR

2 4 6 8

2.797 3.123 3.294 3.409

25.11 27.50 28.50 29.13

2.563 2.918 3.109 3.235

23.57 26.46 27.81 28.73

3.459 3.784 3.935 4.034

37.44 40.20 41.71 42.04

3.103 3.455 3.635 3.749

34.29 37.79 39.59 39.76

GLS GLS GLS GLS

2 4 6 8

2.803 3.109 3.272 3.384

24.78 27.12 27.84 28.62

2.523 2.850 3.039 3.156

22.73 25.60 27.01 28.09

3.431 3.741 3.894 3.987

36.79 39.31 40.51 39.87

3.080 3.408 3.588 3.700

33.72 37.11 39.12 39.37

denotes vanilla speculative sampling without watermark (Leviathan et al., 2023), and the multidraft list-coupling scheme I NVARIANT of Rowan et al. (2025); these set the efficiency ceiling. (iii) Trade-off frontier. MWS /MSE of Hu and Huang (2024) are the two endpoints of the no-go trade-off, and MSE-P SEUDO is the pseudorandom-r variant of He et al. (2026) that improves the trade-off via an alternative watermark metric. (iv) Ours. PFR (single-draft) and MPFR (multi-draft); PFR-N OWM is PFR with the keyed source replaced by an unkeyed Poisson source, isolating the cost of watermarking from the cost of Poisson coupling. Metrics. Following (Hu and Huang, 2024; He et al., 2026) we separate three concerns. Efficiency: AATPS; see other measures in appendix. Detectability: ANLPPT, the average negative log p-value per token under three score variants U / Li / PL (Aaronson and Kirchner, 2023; Li et al., 2025; Lattimore, 2026) (see Appendix E); and TPR@1%FPR, calibrated on non-watermarked generations. Quality: per-token log-perplexity (LPPL) under the target model, used as an unbiasedness audit; we also report ROUGE-L when references are available. 8

Figure 2: Detection and robustness to drafter substitution. (a) TPR@1%FPR versus detection token budget Teval at the default drafter. PFR and MPFR match the strong-watermark references BASIC -UWM and MWS, and outperform MSE/MSE-P SEUDO. (b) TPR@1%FPR under drafter substitution: the target, watermark key, and prompts are fixed and only the drafter is swapped. PFR drifts by < 1 point, whereas MSE drifts by 12–22 points and MSE-P SEUDO by 6–11 points. Single-draft efficiency-watermark frontier. Figure 1 plotted every method in the (AATPS, ANLPPT-U) plane sweeping L ∈ {1, 2, 3, 4}. The prior speculative watermarking baselines (MWS, MSE, MSE-P SEUDO) exhibit the expected trade-off. PFR dominates both Pareto endpoints at every L. Crucially, PFR and PFR-N OWM have nearly identical AATPS, confirming that the watermark is embedded at the coupling level. Other model/dataset results are tested in Appendix D.3. Multi-draft scaling. We compare MPFR with the I NVARIANT decoder by Rowan et al. (2025) at lookahead L=4 and draft counts B ∈ {2, 4, 6, 8} on the headline cell. Across all values of B, MPFR achieves AATPS comparable to INVARIANT, with only small cell-dependent deviations, while delivering substantially larger ANLPPT-U. The watermark signal is itself stable across B (∆ANLPPT ≤ 0.001), and the per-token detection signal does not dilute as additional drafts are added. Full per-cell numbers across the four (TARGET, DATASET) cells, all three ANLPPT variants, and the LPPL audit column are in Appendix D.4 (Tables 10-13). Detection at a fixed false-positive rate. ANLPPT measures average evidence per token; TPR@1%FPR measures operational detectability under a calibrated false-positive budget. Figure 2(a) shows TPR@1%FPR versus token budget Teval at the default drafter. PFR and MPFR track the strong-watermark references BASIC -UWM and MWS, while MSE and MSE-P SEUDO are uniformly weaker. MSE-P SEUDO improves over MSE but still falls below our methods, confirming that target-side keyed coupling preserves detector-visible evidence without degrading efficiency. Drafter-substitution ablation. We test whether the watermark signal is stable to the drafter changes. We vary only the drafter along scale and temperature: D0 (Qwen2.5-0.5B-Instruct, T =1.0, default), D1 (Qwen2.5-1.5B-Instruct, T =1.0), D2 (Qwen2.5-0.5B-Instruct, T =0.5), D3 (Qwen2.5-0.5BInstruct, T =1.5). Figure 2(b) shows that our method (PFR) has at most 1 percentage point of TPR drift across D0 –D3 at Teval ∈ {64, 128}, whereas MSE drifts by 12–22 points and MSE-P SEUDO by 6–11 points. The generation quality (LPPL and ROUGE-L) is verified in Appendix D.5. C ONCLUDING R EMARKS AND L IMITATIONS We designed a novel drafter-invariant, multi-draft speculative sampling algorithm that is watermarkable, improves the trade-off between watermarking and sampling efficiency (Hu and Huang, 2024), and achieves a strong acceleration. We use experiments to verify its strong performance in both aspects. However, a fundamental characterization of the trade-off among target-draft communication, watermark strength, and speculative sampling efficiency remains unclear. Moreover, the current implementation involves substantial coupling and watermark bookkeeping, which slightly slows down the algorithm and may be avoided in the future to further accelerate our algorithms. 9

R EFERENCES Scott Aaronson and H Kirchner. Watermarking of large language models. In Large Language Models and Transformers Workshop at Simons Institute for the Theory of Computing, 2023. David H Ackley, Geoffrey E Hinton, and Terrence J Sejnowski. A learning algorithm for boltzmann machines. Cognitive science, 9(1):147–169, 1985. Anthropic. How claude’s text watermark works. https://www.anthropic.com/news/ claude-text-watermark, August 2026. Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L Rivest, and Madhu Sudan. Optimality of correlated sampling strategies. arXiv preprint arXiv:1612.01041, 2016. Massieh Kordi Boroujeny, Ya Jiang, Kai Zeng, and Brian Mark. Multi-bit distortion-free watermarking for large language models. arXiv preprint arXiv:2402.16578, 2024. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877–1901, 2020. Marcello Bullo, Yanxiao Liu, Öykü Sıla Güner, Arpan Mukherjee, and Deniz Gündüz. Accelerating diffusion sampling via speculative draft trees. arXiv preprint, 2026. URL https://arxiv. org/abs/2609.17691. Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Jean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318, 2023. Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1125–1139. PMLR, 2024. Majid Daliri, Christopher Musco, and Ananda Theertha Suresh. Coupling without communication and drafter-invariant speculative decoding. In 2025 IEEE International Symposium on Information Theory (ISIT), pages 1–6. IEEE, 2025. Valentin De Bortoli, Alexandre Galashov, Arthur Gretton, and Arnaud Doucet. Accelerated diffusion models via speculative sampling. arXiv preprint arXiv:2501.05370, 2025. Frank Den Hollander. Probability theory: The coupling method. Lecture notes available online (http://websites. math. leidenuniv. nl/probability/lecturenotes/CouplingLectures. pdf), 3, 2012. Angela Fan, Mike Lewis, and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, pages 889–898, 2018. Angela Fan, Yacine Jernite, Ethan Perez, David Grangier, Jason Weston, and Michael Auli. Eli5: Long form question answering. In Proceedings of the 57th annual meeting of the association for computational linguistics, pages 3558–3567, 2019. Jessica Ficler and Yoav Goldberg. Controlling linguistic style aspects in neural language generation. In Proceedings of the Workshop on Stylistic Variation, pages 94–104, 2017. Gergely Flamich, Oykü Sıla Güner, Yanxiao Liu, and Deniz Gündüz. Scalable differentially private data compression via diffusion and stochastic codes. arXiv preprint arXiv:2607.03392, 2026. Eva Giboulot and Teddy Furon. Watermax: breaking the llm watermark detectability-robustnessquality trade-off. Advances in Neural Information Processing Systems, 37:18848–18881, 2024. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, et al. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. Emil Julius Gumbel. Statistical theory of extreme values and some practical applications: a series of lectures, volume 33. US Government Printing Office, 1954. 10

Jiajun He, Gergely Flamich, and José Miguel Hernández-Lobato. Accelerating relative entropy coding with space partitioning. Advances in Neural Information Processing Systems, 37:75791–75828, 2024. Weiqing He, Xiang Li, Tianqi Shang, Li Shen, Weijie Su, and Qi Long. On the empirical power of goodness-of-fit tests in watermark detection. arXiv preprint arXiv:2510.03944, 2025. Weiqing He, Xiang Li, Li Shen, Weijie Su, and Qi Long. Improving the trade-off between watermark strength and speculative sampling efficiency for language models. In International Conference on Learning Representations (ICLR), 2026. Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. In International Conference on Learning Representations (ICLR), 2020. Zhengmian Hu and Heng Huang. Inevitable trade-off between watermark strength and speculative sampling efficiency for language models. Advances in Neural Information Processing Systems, 37: 55370–55402, 2024. Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. arXiv preprint arXiv:2310.10669, 2023. Ashish Khisti, Arash Behboodi, Gabriele Cesa, and Pratik Kumar. Unequal message protection: Oneshot analysis via poisson matching lemma. In 2024 IEEE International Symposium on Information Theory (ISIT). IEEE, 2024. Ashish Khisti, M Reza Ebrahimi, Hassan Dbouk, Arash Behboodi, Roland Memisevic, and Christos Louizos. Multi-draft speculative sampling: Canonical decomposition and theoretical limits. In International Conference on Learning Representations (ICLR), 2025. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International conference on machine learning, pages 17061–17084. PMLR, 2023. Szymon Kobus and Deniz Gündüz. Speculative sampling via exponential races. In Findings of the Association for Computational Linguistics: ACL 2025, pages 18189–18204, 2025. Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15593, 2023. Günter Last and Mathew Penrose. Lectures on the Poisson process, volume 7. Cambridge University Press, 2017. Tor Lattimore. Refined detection for gumbel watermarking. arXiv preprint arXiv:2603.30017, 2026. Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning (ICML), pages 19274–19286. PMLR, 2023. Cheuk Ting Li and Venkat Anantharam. A unified framework for one-shot achievability via the Poisson matching lemma. IEEE Transactions on Information Theory, 67(5):2624–2651, 2021. Cheuk Ting Li and Abbas El Gamal. Strong functional representation lemma and applications to coding theorems. IEEE Transactions on Information Theory, 64(11):6967–6978, 2018. Cheuk Ting Li et al. Channel simulation: Theory and applications to lossy compression and differential privacy. Foundations and Trends® in Communications and Information Theory, 21(6): 847–1106, 2024. Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie J Su. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules. The Annals of Statistics, 53(1):322–351, 2025. Yanxiao Liu and Cheuk Ting Li. One-shot information hiding. In 2024 IEEE Information Theory Workshop (ITW), pages 169–174. IEEE, 2024. 11

Yanxiao Liu and Cheuk Ting Li. One-shot coding over general noisy networks. IEEE Transactions on Information Theory, 71(11):8346–8357, 2025. Yanxiao Liu, Wei-Ning Chen, Ayfer Özgür, and Cheuk Ting Li. Universal exact compression of differentially private mechanisms. Advances in Neural Information Processing Systems, 37: 91492–91531, 2024. Yanxiao Liu, Sepehr Heidari Advary, and Cheuk Ting Li. Nonasymptotic oblivious relaying and variable-length noisy lossy source coding. IEEE Transactions on Information Theory, 72(6): 4555–4564, 2026. Chris J Maddison. A Poisson process model for Monte Carlo. Perturbation, Optimization, and Statistics, pages 193–232, 2016. Chris J Maddison, Daniel Tarlow, and Tom Minka. A* sampling. Advances in Neural Information Processing Systems, 27, 2014. Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, et al. Specinfer: Accelerating large language model serving with tree-based speculative inference and verification. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, pages 932–949, 2024. Pierre Moulin and Joseph A O’Sullivan. Information-theoretic analysis of information hiding. IEEE Transactions on information theory, 49(3):563–593, 2003. Shinwoo Park, Hyejin Park, Hyeseon Ahn, and Yo-Sub Han. Watermod: Modular token-rank partitioning for probability-balanced llm watermarking. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 32683–32691, 2026. Wenjie Qu, Wengrui Zheng, Tianyang Tao, Dong Yin, Yanze Jiang, Zhihua Tian, Wei Zou, Jinyuan Jia, and Jiaheng Zhang. Provably robust multi-bit watermarking for {AI-generated} text. In 34th USENIX Security Symposium (USENIX Security 25), pages 201–220, 2025. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019. Joseph Rowan, Buu Phan, and Ashish Khisti. List-level distribution coupling with applications to speculative decoding and lossy compression. Advances in Neural Information Processing Systems, 38, 2025. Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Nicolas Papernot, Ross Anderson, and Yarin Gal. Ai models collapse when trained on recursively generated data. Nature, 631(8022):755–759, 2024. Aaditya Singh, Adam Fry, Adam Perelman, Adam Tart, Adi Ganesh, Ahmed El-Kishky, Aidan McLaughlin, Aiden Low, AJ Ostrow, Akhila Ananthram, et al. Openai gpt-5 system card. arXiv preprint arXiv:2601.03267, 2025. Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems, 31, 2018. Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems, 36:30222–30242, 2023. Lucas Theis and Noureldin Y Ahmed. Algorithms for the communication of samples. In International Conference on Machine Learning (ICML), pages 21308–21328. PMLR, 2022. Hermann Thorisson. Coupling, stationarity, and regeneration. Probability and its Applications, 2000. Dor Tsur, Carol Xuan Long, Claudio Mayrink Verdun, Hsiang Hsu, Haim Permuter, and Flavio P Calmon. Optimized couplings for watermarking large language models. arXiv preprint arXiv:2505.08878, 2025. 12

Junchao Wu, Shu Yang, Runzhe Zhan, Yulin Yuan, Lidia Sam Chao, and Derek Fai Wong. A survey on llm-generated text detection: Necessity, methods, and future directions. Computational Linguistics, 51(1):275–338, 2025. Yihan Wu, Zhengmian Hu, Junfeng Guo, Hongyang Zhang, and Heng Huang. A resilient and accessible distribution-preserving watermark for large language models. arXiv preprint arXiv:2310.07710, 2023. Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai-generated text. arXiv preprint arXiv:2306.17439, 2023. Xuandong Zhao, Lei Li, and Yu-Xiang Wang. Permute-and-flip: An optimally stable and watermarkable decoder for LLMs. In International Conference on Learning Representations, (ICLR), 2025a. Xuandong Zhao, Chenwen Liao, Yu-Xiang Wang, and Lei Li. Efficiently identifying watermarked segments in mixed-source texts. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 6304–6316, 2025b. Chuqin Zhou, Xiaoyue Ling, Yunuo Chen, Jincheng Dai, Guo Lu, and Wenjun Zhang. Dualrepresentation image compression at ultra-low bitrates via explicit semantics and implicit textures. arXiv preprint arXiv:2602.05213, 2026.

M ORE ON PFR AND R ELATED W ORKS

A.1

PFR FOR D ISCRETE D ISTRIBUTIONS

It is known that the general PFR (Li and El Gamal, 2018; Li and Anantharam, 2021) reduces to the use of exponential random variables (Li and El Gamal, 2018; Liu and Li, 2025) in the case of simulating discrete distributions, which is similar to the Gumbel-max trick (Gumbel, 1954) used for speculative sampling (Kobus and Gündüz, 2025). In (Li et al., 2024), it is discussed how to extend the discrete case to the general case. However, the other direction, namely reducing the general case to the discrete case, has not been discussed in the literature, to the best of the authors’ knowledge. To make the paper self-contained, we provide formal statements and proofs for this direction. The first define the exponential functional representation (EFR) as follows (also see (Li and El Gamal, 2018; Liu and Li, 2025)). Let Z be a finite or countably infinite set, and let P be a distribution on Z. Let (Ez )z∈Z be independent Exp(1) random variables. With the convention that Ez /P (z) = +∞ whenever P (z) = 0, define Ez ZEFR := arg min . (7) z∈Z P (z) As proved in Appendix A.2, EFR is equivalent to the Gumbel-max trick. In the following, we prove that PFR reduces to EFR in the discrete case, i.e., when the target and proposal distributions are discrete. Theorem A.1. Let Z be a finite or countably infinite set. Let Q and P be distributions on Z such that P ≪ Q. Write qz := Q(z), pz := P (z), z ∈ Z. The PFR considers a Poisson process (Zi , Ti )i≥1 −1 dP on Z × [0, ∞) with intensity measure Q × λ[0,∞) , and T̃i = Ti dQ (Zi ) . For each z with qz > 0, define the first arrival time of symbol z by Sz := inf{Ti : Zi = z},

(8)

Ez := qz Sz .

(9)

and define For z with qz = 0, define Ez to be an arbitrary independent Exp(1) random variable, independent of everything else. Then the random variables (Ez )z∈Z are independent Exp(1) random variables, and the PFR output satisfies ZPFR = arg min T̃i = arg min i

z∈Z

Ez = ZEFR pz

a.s.,

(10)

where we use the convention that Ez /pz = +∞ if pz = 0. Proof. For z ∈ Z and t ≥ 0, define Nz (t) := #{i : Ti ≤ t, Zi = z}. Since (Zi , Ti )i≥1 is a Poisson process with intensity measure Q × λ[0,∞) , for each z with qz > 0, the process (Nz (t))t≥0 is a Poisson process with rate qz . Moreover, for distinct symbols z1 , . . . , zm , the processes (Nz1 (t))t≥0 , . . . , (Nzm (t))t≥0 are independent, because they count disjoint subsets of the underlying Poisson process. Therefore, for z with qz > 0, the first arrival time Sz = inf{t : Nz (t) ≥ 1} satisfies P(Sz > s) = P(Nz (s) = 0) = e−qz s , Thus Sz ∼ Exp(qz ). Hence Ez = qz Sz ∼ Exp(1). 14

s ≥ 0.

The independence of the Poisson counting processes for different symbols implies that the random variables (Ez )z:qz >0 are independent. For symbols with qz = 0, we have pz = 0 because P ≪ Q, and these symbols can never be selected by PFR. Defining independent Exp(1) variables Ez for those symbols therefore does not change the output. Hence the full family (Ez )z∈Z is independent and identically distributed as Exp(1). It remains to show that the PFR selection rule reduces to the EFR selection rule. Since P ≪ Q, for every z with pz > 0, we also have qz > 0, and dP pz (z) = . dQ qz Therefore, for every index i with Zi = z and pz > 0, −1 qz pz = Ti . T̃i = Ti qz pz Taking the minimum over all Poisson points with mark z, we get qz Ez qz inf Ti inf T̃i = = Sz = . i:Zi =z i:Zi =z pz pz pz If pz = 0, then dP/dQ(z) = 0 whenever qz > 0, and hence T̃i = Ti

−1 dP (z) = +∞ dQ

for every Poisson point with mark z. This agrees with the EFR convention Ez = +∞. pz If qz = 0, then also pz = 0, and no Poisson point has mark z almost surely, so such a symbol is irrelevant in both constructions. Thus, inf T̃i = inf i

inf T̃i = inf

z∈Z pz

z∈Z i:Zi =z

Moreover, the minimizer is unique almost surely. Indeed, for every z with pz > 0, Ez ∼ Exp(pz ), pz and these variables are independent. Since exponential random variables are continuous, ties have probability zero. Therefore, almost surely, ZPFR = ZK = arg min z∈Z

A.2

Ez = ZEFR . pz

R ELATION BETWEEN PFR AND G UMBEL -M AX T RICK

As discussed in (Zhao et al., 2025a), the Gumbel Watermark (Aaronson and Kirchner, 2023) is based on ut (y) yt = argminy∈V + Gt (y) T 15

where G(y) ∼ Gumbel(0, 1) i.i.d. for each t and y. Here, we show that it is equivalent to the PFR in the discrete case. Recall Gumbel(0, 1) ∼ − log log(1/Unif[0, 1]) . We calculate

ut (y) + Gt (y) y∈V T ut (y) iid d = arg max − log Zt (y) Zt (y) ∼ Exp(1), Gt (y) = − log Zt (y) y∈V T = arg max − log Zt (y)e−ut (y)/T

yt = arg max

y∈V

= arg min Zt (y)e−ut (y)/T y∈V

= arg min

Zt (y)

y∈V exp(ut (y)/T )

Zt (y) y∈V wt (y) Zt (y) = arg min , y∈V Pt (y)

= arg min

wt (y) := exp(ut (y)/T )

where the last equality is because Pt (y) := P ′wt (y) ′ and scaling by a positive constant doesn’t y ∈V wt (y ) change the argmin.

A.3

M APPED P OISSON P ROCESS

A.3.1

D EFINITIONS

Definition A.2 (Mapped Poisson Process (Li and Anantharam, 2021)). Let (Ti )i be a Poisson process iid

of rate 1, independent of Zi ∼ Q for i = 1, 2, . . .. Let iP,1 , iP,2 , . . . ∈ N be a sequence of distinct −1 S∞ dP dP integers such that j=1 iP,j = i : dQ is sorted in (Zi ) > 0 and TiP,j dQ (ZiP,j ) j∈N ascending order with arbitrary tie-breaking.3 For j ∈ N and suppose P is the target distribution, we denote n o −1 dP := ZiP,j , TiP,j (Zi ) Z̃P (j), T̃ (j) . (11) dQ P,j j∈N j∈N Give a positive n o integer B, the mapped Poisson Process selects the first B samples in Z̃P (j), T̃ (j) . j∈N

Proposition A.3. By the mapping theorem (Last and Penrose, 2017), Z̃P (j), T̃ (j) j∈N is a Poisson process with intensity measure P × λR≥0 where R≥0 to denote nonnegative real numbers, and therefore we have iid

Z̃P (1), Z̃P (2), . . . ∼ P. A.3.2

D IRECT I MPLEMENTATIONS

We can implement the MPFR just like (Theis and Ahmed, 2022) for PFR, as follows:

Note a tie occurs with probability 0.

(12)

Algorithm 5: Finite implementation of the B-sample mapped PFR Given :target distribution P , proposal distribution Q, likelihood ratio r = dP/dQ, number of samples B, and a constant w > 0 such that 1/r(u) ≥ w Q-a.s. on {r(u) > 0} Return :B samples from P H←∅ // H stores the current B smallest-score candidates t ← 0; i ← 1 while |H| < B or max(s,j,z)∈H s > tw do Sample Ei ∼ Exp(1) and set t ← t + Ei // Poisson process Sample Zi ∼ Q if r(Zi ) > 0 : Si ← t/r(Zi ) else Si ← +∞ if |H| < B : Insert (Si , i, Zi ) into H else if Si < max(s,j,z)∈H s : Remove an element (s⋆ , j ⋆ , z ⋆ ) ∈ H satisfying s⋆ = max(s,j,z)∈H s Insert (Si , i, Zi ) into H i←i+1 Sort the elements of H as (Si1 , i1 , Zi1 ), . . . , (SiB , iB , ZiB ) so that Si1 ≤ Si2 ≤ · · · ≤ SiB . return (Zi1 , . . . , ZiB ) A.3.3

P ROOF OF C ORRECTNESS

We then prove that the implementation of Algorithm 5 is correct. Theorem A.4. Let P ≪ Q be probability measures on a Polish space U, and let r := dP/dQ. Let iid

Z1 , Z2 , . . . ∼ Q and let 0 < T1 < T2 < · · · be the arrival times of a unit-rate Poisson process, independent of (Zi )i≥1 . Define Ti /r(Zi ), r(Zi ) > 0, Si := +∞, r(Zi ) = 0. Assume that there exists w > 0 such that 1/r(u) ≥ w

Q-a.s. on {r(u) > 0}.

Fix B ∈ N. Consider the algorithm that scans the candidates in the order i = 1, 2, . . ., keeps the B smallest observed scores, and stops at the first time n such that the current B-th smallest observed score is at most Tn w. Then the algorithm terminates almost surely after finitely many iterations. Moreover, at termination, the retained candidates are exactly the B smallest-score candidates among the infinite sequence. Consequently, the returned marks are distributed as eP (1), . . . , U eP (B)), (U the first B points of the mapped Poisson process with respect to P , and hence are i.i.d. according to P. Proof. Let ΠQ := {(Zi , Ti ) : i ≥ 1}. iid

Since 0 < T1 < T2 < · · · are the arrival times of a unit-rate Poisson process and Z1 , Z2 , . . . ∼ Q are independent marks, ΠQ is a Poisson point process on U × R≥0 with intensity measure Q × λ, where λ denotes the Lebesgue measure on R≥0 . Consider the measurable mapping Φ : U × R≥0 → U × R≥0 , 17

Φ(u, t) = u,

t r(u)

on the set {u : r(u) > 0}. Points with r(u) = 0 are assigned score +∞ and hence never appear among the finite mapped arrival times. For any nonnegative measurable function g on U × R≥0 , we have Z Z ∞ Z Z ∞ t t g u, dt Q(du) = g u, dt Q(du) r(u) r(u) U 0 {r>0} 0 Z Z ∞ g(u, s)r(u) ds Q(du) = {r>0}

Z Z ∞ =

g(u, s) ds P (du). U

Therefore, by the mapping theorem for Poisson point processes, the mapped point process ΠP := {(Zi , Si ) : i ≥ 1, r(Zi ) > 0} ,

Si :=

Ti , r(Zi )

is a Poisson point process on U × R≥0 with intensity measure P × λ. Let Si1 < Si2 < · · · be the increasing ordering of the finite scores in ΠP . Since the time-marginal intensity of ΠP is λ, the ordered times Si1 , Si2 , . . . are the arrival times of a unit-rate Poisson process. Moreover, conditional on these arrival times, the associated marks are independent with common distribution P . Hence d

(Zi1 , Zi2 , . . .) = (U1 , U2 , . . .), iid

where U1 , U2 , . . . ∼ P . In particular, (Zi1 , . . . , ZiB ) are exactly the first B points of the mapped Poisson process with respect to P , and they are i.i.d. according to P . It remains to show that the finite algorithm stops safely and terminates almost surely. After observing candidates 1, . . . , n, let Sn,(B) denote the B-th smallest value among S1 , . . . , Sn , whenever at least B finite scores have been observed. By construction, the algorithm keeps the B smallest observed scores, so the largest score retained by the algorithm is exactly Sn,(B) . Suppose the algorithm stops at time n. Then Sn,(B) ≤ Tn w. For every future candidate m > n, we have Tm > Tn . If r(Zm ) = 0, then Sm = +∞, so such a candidate cannot improve the current list. If r(Zm ) > 0, then by the assumption 1/r(u) ≥ w Q-a.s., Sm =

Tm 1 = Tm ≥ Tm w > Tn w ≥ Sn,(B) . r(Zm ) r(Zm )

Thus every future score is strictly larger than the current B-th smallest observed score. Therefore no future candidate can enter the set of the global B smallest scores. Hence, when the algorithm stops, the retained candidates are exactly the global B smallest-score candidates among the infinite sequence. Finally, we prove almost sure finite termination. Since ΠP is a Poisson point process with intensity P × λ, its first B mapped arrival times are finite almost surely. Let SiB denote the B-th smallest mapped score, and let N0 := max{i1 , . . . , iB }. Then N0 < ∞ almost surely. After the algorithm has processed candidates 1, . . . , N0 , it has already observed the true global first B mapped candidates, so the largest retained score is SiB . Since Tn → ∞

almost surely, 18

and since w > 0, there exists an almost surely finite random index N ≥ N0 such that TN w ≥ SiB . At time N , the algorithm therefore satisfies the stopping condition SN,(B) = SiB ≤ TN w. Thus the algorithm terminates almost surely after finitely many iterations. Combining the safe stopping argument with the mapped Poisson process argument, the algorithm returns exactly (Zi1 , . . . , ZiB ), which are the first B points of the mapped Poisson process with respect to P . Consequently, the returned samples are i.i.d. according to P . A.4

A BETTER FINITE - SUPPORT MPFR IMPLEMENTATION

The proposal-scanning implementation in Appendix A.3.2 can be slow in finite-vocabulary LLM decoding. Its stopping rule depends on a lower bound on the likelihood ratio, which can be very small when a rare token has small proposal probability but non-negligible target probability. In our experiments, the logits are processed by temperature and top-k truncation, so the resulting distribution has finite support of size at most K. In this setting, we can simulate the relevant Poisson clocks directly and avoid proposal scanning altogether. Let P be a distribution on a finite vocabulary U, and define AP := {u ∈ U : P (u) > 0}. For each u ∈ AP , let Gu,j :=

j X

Eu,m ,

j ≥ 1,

m=1

where the Eu,m ’s are independent Exp(1) random variables. We associate to (u, j) the mappedPoisson score Gu,j Su,j := . P (u) The first B MPFR samples are the labels of the B smallest scores among {Su,j : u ∈ AP , j ≥ 1}. Since no token can contribute more than B arrivals among the first B total arrivals, it is enough to generate j = 1, . . . , B for every u ∈ AP . Theorem A.5 (Exactness of direct finite-support MPFR). Let P be a distribution on a finite set U. The output (U(1) , . . . , U(B) ) of Algorithm 6 consists of B independent samples from P . That is, for every (u1 , . . . , uB ) ∈ U B , P{U(1) = u1 , . . . , U(B) = uB } =

B Y

P (ub ).

b=1

Proof. For each u ∈ AP , the sequence (Gu,j )j≥1 is the arrival process of a unit-rate Poisson process. Therefore, Gu,j P (u) j≥1 is a Poisson process on R+ with rate P (u), since Gu,j # j: ≤ t = #{j : Gu,j ≤ P (u)t} P (u) is Poisson with mean P (u)t. The processes corresponding to different tokens are independent. Their superposition is therefore a marked Poisson process on R+ × U with intensity measure dt ⊗ P. 19

Algorithm 6: Direct finite-support implementation of B-sample MPFR Given :finite distribution P on U, number of samples B, and keyed source Π Return :B samples from P AP ← {u ∈ U : P (u) > 0} H←∅ // candidate triples (S, u, j) for each u ∈ AP do G←0 for j = 1 to B do Generate Eu,j ∼ Exp(1) from Π G ← G + Eu,j S ← G/P (u) Insert (S, u, j) into H Let (S(1) , U(1) , J(1) ), . . . , (S(B) , U(B) , J(B) ) be the B elements of H with smallest scores, ordered by increasing score return (U(1) , . . . , U(B) )

P Equivalently, the total arrival rate is u∈AP P (u) = 1, and the marks of the ordered arrivals are independent with common distribution P . Algorithm 6 constructs the first B candidate arrivals of each token clock. This is sufficient because among the first B arrivals of the superposed process, no individual token clock can contribute more than B arrivals. Hence the B smallest elements in H are exactly the first B arrivals of the superposed marked Poisson process, and their labels are B independent samples from P . We now describe the batched speculative decoding implementation. For a context c, let Pk (·|c) and Qk (·|c) denote the processed target and draft distributions after applying the same logits processing, such as temperature and top-k truncation. The draft side builds a tree of candidate continuations using Algorithm 6 with Qk . The target side then evaluates all contexts needed for verification in a batched manner and uses the same MPFR clocks with Pk to follow the realized target path. This batching changes only the order and grouping of model evaluations, not the sampling law. Theorem A.6 (Exactness of batched-target direct-top-k MPFR decoding). Assume that for every context c, the keyed source Πk (c) provides independent exponential clocks across tokens and local arrival indices, and that the sources {Πk (c)}c are independent across distinct contexts. Then Algorithm 7 generates exactly from the autoregressive model with transition kernel Pk (·|c). That is, for every finite sequence u1 , . . . , um , P{Wn+1 = u1 , . . . , Wn+m = um } =

m Y

Pk (ut |w1:n , u1 , . . . , ut−1 ).

t=1

Proof. Fix a context c. By Theorem A.5, Y (c) = MPFR(Pk (·|c), Πk (c), 1) has distribution Pk (·|c). The draft samples generated from Qk (·|c) may use the same keyed clocks, and hence are coupled with Y (c), but this does not change the marginal distribution of Y (c). Let Ct := (w1:n , Wn+1 , . . . , Wn+t−1 ) be the random context before generating Wn+t . The event {Ct = c} is determined by the keyed sources associated with strict prefix contexts of c. By the assumed independence across contexts, Πk (c) is independent of this event. Therefore, conditional on Ct = c, Wn+t = Y (c) ∼ Pk (·|c), and hence P{Wn+t = u|Ct = c} = Pk (u|c). 20

Algorithm 7: Batched-target direct-top-k MPFR speculative sampling Given :lookahead L, number of drafts B, output length N , target model P , draft model Q, prompt w1:n , key k while n < N do h ← w1:n , ℓ ← min{L, N − n} C0 ← {h} and ν(h) ← B // context multiplicities // Draft tree construction for s = 1 to ℓ do Cs ← ∅ for each c ∈ Cs−1 do Generate (X1 (c), . . . , Xν(c) (c)) ← MPFR(Qk (·|c), Πk (c), ν(c)). Let D(c) be the set of distinct tokens among these samples for each u ∈ D(c) do m(c, u) ← |{i : Xi (c) = u}| Add c∥u to Cs ν(c∥u) ← ν(c∥u) + m(c, u) // Batched target evaluation Compute the processed target distributions Pk (·|c) for all contexts c∈

ℓ [

s=0

using batched target-model forward passes for each such context c do Generate Y (c) ← MPFR(Pk (·|c), Πk (c), 1). // Follow the realized target path c⋆ ← h, accepted ← true for s = 1 to ℓ do Emit Y (c⋆ ) and append it to the output if Y (c⋆ ) ∈ / D(c⋆ ) : accepted ← false break // first rejection ends the block if n = N : break c⋆ ← c⋆ ∥Y (c⋆ ) if accepted and n < N : Emit the precomputed bonus token Y (c⋆ )

Applying the chain rule gives P{Wn+1 = u1 , . . . , Wn+m = um } m Y = P{Wn+t = ut |Wn+1 = u1 , . . . , Wn+t−1 = ut−1 } =

t=1 m Y

Pk (ut |w1:n , u1 , . . . , ut−1 ).

t=1

Thus the generated sequence has exactly the desired autoregressive law. Finally, batched target evaluation only changes the computational order of deterministic model evaluations. It does not change the context-indexed MPFR clocks or the resulting samples Y (c), so it does not change the output distribution. This implementation removes the proposal-scanning overhead by simulating the token-wise Poisson clocks directly. For support size at most K, producing B MPFR samples requires KB exponential variables followed by a top-B selection. The batched target implementation further reduces the number of target-model calls: instead of verifying the realized path sequentially with roughly one target forward pass per generated token, it evaluates the contexts in a speculative block together and extracts all logits needed for verification. If a block emits BE tokens on average, the target-forward cost per emitted token is reduced from approximately 1 to approximately 1/BE, while preserving the exact target marginal distribution.

T HEORETIC G UARANTEES

B.1

P ROOF OF T HEOREM 5.1

Proof. The proof is based on the Poisson matching lemma (Li and Anantharam, 2021). Let pi := P (i) and qi := Q(i) for i ∈ V. Let Y := Z̃P (1) and X (b) := Z̃Q (b) for b = 1, . . . , B be generated from the same mapped Poisson process, and define the token-level acceptance event n o At := Y ∈ {X (1) , . . . , X (B) } , which is the acceptance event. Apply the (Li and Anantharam, 2021, Lemma 3) with j = 1 and k = B. Conditioned on Y = Z̃P (1) = i, the event Act is exactly the event that the first mapped P -sample does not appear among the first B mapped Q-samples. Hence −1 !B B pi pi c P(At |Y = i) ≤ 1 − 1 + = . qi pi + qi Taking complements gives P(At |Y = i) ≥ 1 −

pi pi + qi

Finally, average over Y ∼ P : P(At ) =

pi P(At |Y = i) ≥

i∈V

pi 1 −

i∈V

pi pi + qi

B # .

For B = 1, this simplifies to 1−

X i∈V

B.2

X pi qi p2i = . pi + qi pi + q i i∈V

C OMPARISON WITH (ROWAN ET AL ., 2025) ON ACCEPTANCE P ROBABILITY

We compare our token-level acceptance probability with the token-level acceptance probability from (Rowan et al., 2025) in two levels, and we prove that in each level our algorithm’s acceptance probability is strictly better. 22

B.2.1 We first prove a stronger version of Theorem 5.1, but not as clean as it. Theorem B.1. Let P be the target distribution and Q be the draft distribution on a finite vocabulary V. Assume first that P (i), Q(i) > 0 for all i ∈ V. For each i ∈ V, define X Q(j) P (j) αi := P (i) − . Q(i) P (i) + j∈V

If the target token is generated as ŨP (1) and the B draft tokens are generated as ŨQ (1), . . . , ŨQ (B) from the same underlying Poisson process, then the acceptance probability of at least one token satisfies B X αi . (13) P(accept) ≥ 1 − P (i) 1 + αi i∈V

Proof. Let the target token be Y := ŨP (1), and let the B draft tokens be Xb := ŨQ (b),

b = 1, . . . , B.

The acceptance event is accept = {Y ∈ {X1 , . . . , XB }}. Conditioning on Y = i, the failure event is {Y ∈ / {X1 , . . . , XB }}. By the exact j = 1 tail formula in the generalized Poisson matching lemma, B αi P(Y ∈ / {X1 , . . . , XB } | Y = i) ≤ , 1 + αi where X Q(j) P (j) − . αi = P (i) Q(i) P (i) + j∈V

Therefore, P(accept|Y = i) ≥ 1 −

αi 1 + αi

B .

Averaging over Y ∼ P gives P(accept) =

P (i)P(accept|Y = i)

i∈V

B # αi ≥ P (i) 1 − 1 + αi i∈V B X αi =1− P (i) . 1 + αi X

i∈V

This proves (13). Moreover, 1−

X i∈V

P (i)

αi 1 + αi

B ≥1−

X i∈V

Thus (13) strictly improves the weaker bound X P(accept) ≥ 1 − P (i) i∈V

P (i)

P (i) P (i) + Q(i)

B .

whenever the inequality in (14) is strict. We then show above Theorem B.1 is tighter than (Rowan et al., 2025, Proposition 2). 23

(14)

Theorem B.2. Let P be the target distribution and Q be the draft distribution on a finite vocabulary V. Write pi := P (i), qi := Q(i), i ∈ V, and assume first that pi , qi > 0 for all i ∈ V. For each i ∈ V, define X qj pj αi := pi − . qi pi + j∈V

Let LPML := 1 −

i∈V

αi 1 + αi

be the acceptance lower bound obtained from the exact j = 1 tail formula of the generalized Poisson matching lemma. Let LLML :=

X i∈V

j∈V

max

pj qj pi , qi

+ (B − 1) pji

be the lower bound in Eq. (3) of the list matching lemma, written in the same target–draft notation. Then LPML ≥ LLML . Moreover, if B > 1 and P ̸= Q, then LPML > LLML . Proof. The proof is based on the Poisson matching lemma (Li and Anantharam, 2021). Let Y := Z̃P (1) and X (b) := Z̃Q (b) for b = 1, . . . , B be generated from the same mapped Poisson process. By the mapping theorem, Z̃Q (1), Z̃Q (2), . . . are i.i.d. according to Q, and Z̃P (1) ∼ P . Define the token-level acceptance event n o At := Y ∈ {X (1) , . . . , X (B) } . Apply the exact j = 1 tail formula of the generalized Poisson matching lemma with the first distribution equal to P and the second distribution equal to Q. Conditioned on Y = Z̃P (1) = i, the event Act is the event that the first mapped P -sample does not appear among the first B mapped Q-samples. Hence B αi c P(At |Y = i) ≤ , 1 + αi where αi = pi

X qj j∈V

−

pj pi

. +

Taking complements gives P(At |Y = i) ≥ 1 −

αi 1 + αi

B .

Finally, averaging over Y ∼ P gives P(At ) =

pi P(At |Y = i)

i∈V

B # αi ≥ pi 1 − 1 + αi i∈V B X αi =1− pi = LPML . 1 + αi "

i∈V

We now rewrite the LML bound in terms of the same quantities αi . For each fixed i ∈ V, X X pj qj pi pi max , = max pj , qj pi qi qi j∈V j∈V " # X pi = pj + qj − pj qi + j∈V X qj pj − = 1 + pi qi pi + j∈V

= 1 + αi . Therefore, X pj qj pj 1 + αi 1 max , + (B − 1) = + (B − 1) pi qi pi pi pi

j∈V

B + αi . pi

Thus Eq. (3) of the list matching lemma can be written as X B LLML = pi . B + αi i∈V

It remains to compare the two expressions term by term. For every α ≥ 0, we claim that B α B 1− ≥ . 1+α B+α If α = 0, both sides are equal to 1. If α > 0, the inequality is equivalent to B α α ≤ , 1+α B+α or equivalently B 1 B 1+ ≥1+ . α α This follows immediately from the binomial theorem: B B X B 1 B B −m α ≥1+ . 1+ =1+ + α α m=2 m α

Hence, for each i ∈ V, " pi 1 −

αi 1 + αi

B # ≥ pi

B . B + αi

Summing over i ∈ V yields LPML ≥ LLML . Finally, suppose B > 1 and P ̸= Q. We show that the inequality is strict. If αi = 0 for every i ∈ V, then for every i, j ∈ V, pj qj ≤ . qi pi Equivalently, qj qi ≤ . pj pi Since this holds for every pair (i, j), all ratios qi /pi must be equal to a common constant. Because both P and Q are probability distributions, this constant must be 1, and hence P = Q, a contradiction. Therefore, when P ̸= Q, there exists at least one i such that αi > 0. 25

For B > 1 and α > 0, the binomial expansion above is strict: B 1 B 1+ >1+ . α α Hence

B B α > . 1− 1+α B+α Applying this to an index i with αi > 0 gives a strict term in the sum. Therefore

LPML > LLML . This completes the proof. B.2.2 We then show the clean version, Theorem 5.1, is already tighter than (Rowan et al., 2025, Eq. (4)). Theorem B.3. Let P be the target distribution and Q be the draft distribution on a finite vocabulary V. Write pi := P (i), qi := Q(i), i ∈ V. Assume first that pi , qi > 0 for all i ∈ V. Define X pi B LPML,weak := 1 − pi pi + q i i∈V

and LLML,rel :=

i∈V

pi 1+ Bqi

−1 =

i∈V

Bqi . pi + Bqi

Then LPML,weak ≥ LLML,rel . Moreover, if B > 1, then the inequality is strict. Proof. The proof is based on the Poisson matching lemma (Li and Anantharam, 2021). Let Y := Z̃P (1) and let X (b) := Z̃Q (b), b = 1, . . . , B, be generated from the same mapped Poisson process. Define the token-level acceptance event n o At := Y ∈ {X (1) , . . . , X (B) } . Applying the relaxed Poisson matching bound with j = 1 and k = B, conditioned on Y = Z̃P (1) = i, gives −1 !B B pi pi c P(At |Y = i) ≤ 1 − 1 + = . qi pi + qi Taking complements yields P(At |Y = i) ≥ 1 −

pi pi + qi

B .

Averaging over Y ∼ P gives P(At ) =

pi P(At |Y = i)

i∈V

B # pi ≥ pi 1 − pi + qi i∈V B X pi =1− pi = LPML,weak . pi + qi X

i∈V

We now compare this lower bound with the relaxed version of the list matching lemma. In the notation of the list matching lemma paper, the proposal distribution is denoted by p and the target distribution by q. Since here we use P for the target and Q for the draft, their relaxed conditional bound, Eq. (4), becomes −1 pi Bqi P(At |Y = i) ≥ 1 + = . Bqi pi + Bqi Thus the corresponding unconditional relaxed LML bound is X Bqi . LLML,rel = pi pi + Bqi i∈V

It remains to compare the two conditional terms. Let pi ri := . qi Then 1−

pi pi + q i

=1−

ri 1 + ri

B ,

whereas

Bqi B = . pi + Bqi B + ri Hence it suffices to prove that, for every r > 0, B B r ≥ . 1− 1+r B+r Equivalently, r 1+r

1 1+ r

≤

r . B+r

Since r > 0, this is equivalent to

≥1+

B . r

This follows from the binomial theorem: B B X 1 B B −m B 1+ =1+ + r ≥1+ . m r r r m=2 Therefore, for each i ∈ V, 1−

pi pi + qi

B ≥

Bqi . pi + Bqi

Multiplying by pi and summing over i ∈ V gives LPML,weak ≥ LLML,rel . Finally, if B > 1, then for every r > 0, B X B m=2

r−m > 0.

Thus the above inequality is strict for every i with pi , qi > 0. Under full support, all such terms have positive weight pi , and hence LPML,weak > LLML,rel . This completes the proof. 27

B.3

G ENERALIZED T HEORETIC G UARANTEE AND P ROOF

Theorem B.4. Consider the exact draft-indexed active-set version of multi-draft speculative sampling with total draft count B. Fix a current decoding step t, and let St ⊆ {1, . . . , B} be the active set before sampling the next token. Write Jt := |St |. Let the current realized context be ct , and similarly (t) (t) define Pt := Mt (·|ct ), Qt := Md (·|ct ). For i ∈ V, write pi := Pt (i) and qi := Qt (i). Then the token-level acceptance probability at step t satisfies    ! Jt !Jt (t) −1 (t) X (t)  X (t) p p  i i  =1− P(At |ct , St ) ≥ pi 1 − 1 − 1 + (t) pi . (t) (t) q p + qi i∈V i∈V i i In particular, at the first step of each speculative block one has Jt = B, so !B (t) X (t) pi P(At |ct ) ≥ 1 − pi . (t) (t) pi + qi i∈V Proof. Conditioned on the realized context ct and the active set St , the exact active-set algorithm uses only the Jt active draft streams for both target-side selection and acceptance. Inactive drafts do not participate in the current-step minimum and therefore do not affect the current-step coupling. Hence, after conditioning on (ct , St ), the current step is identical to the setting of Theorem 5.1 with the number of drafts equal to Jt . Applying Theorem 5.1 with B replaced by Jt gives !Jt (t) X (t) pi . P(At |ct , St ) ≥ 1 − pi (t) (t) pi + qi i∈V At the first step of a speculative block, all drafts are active, so Jt = B, which yields the final claim. B.4

E XTENSION OF T HEOREM B.1 TO NON - IDENTICALLY DISTRIBUTED PROPOSALS

Proposition B.5. Let P be the target distribution on a finite vocabulary V, and let Q1 , . . . , QB be B proposal distributions. Write pi := P (i),

i ∈ V, b ∈ [B].

qb,i := Qb (i),

Assume first that pi , qb,i > 0 for all i and b. For each i ∈ V and b ∈ [B], define X qb,j pj (b) αi := pi − . qb,i pi + j∈V

Then there exists a common-randomness coupling such that Y ∼ P , X (b) ∼ Qb for each b ∈ [B], the proposals X (1) , . . . , X (B) are mutually independent, and B h i X Pr Y ∈ {X (1) , . . . , X (B) } Y = i ≥

B h i X X Pr Y ∈ {X (1) , . . . , X (B) } ≥ pi

(15)

(16)

(b) b=1 B + αi

Consequently,

i∈V

(b) b=1 B + αi

Proof. The proof is based on the Poisson matching lemma (Li and Anantharam, 2021). The main difference from the identical-proposal case is that there is no single proposal ordering when the proposal laws are Q1 , . . . , QB . We therefore augment the sample space by a block label. Define e := V × [B], V 28

and introduce the augmented target and proposal distributions pi e b (i, ℓ) := 1{ℓ = b}qb,i . Pe(i, b) := , Q B Let (Y, J) := Z̃Pe (1), (X (b) , b) := Z̃Qeb (1), b = 1, . . . , B, e × R≥0 . By the mapping theorem, be generated from the same underlying Poisson process on V e (Y, J) ∼ P , and hence Y ∼ P and J is uniform on [B] and independent of Y . Also, for each b, e b , so X (b) ∼ Qb . Since the laws Q e b are supported on disjoint blocks, the corresponding (X (b) , b) ∼ Q proposal samples are mutually independent. Fix i ∈ V. Define the acceptance event n o A := Y ∈ {X (1) , . . . , X (B) } . For each b ∈ [B], let n o Ab := (Y, J) = (X (b) , b) . SB Then A ⊇ b=1 Ab , and the events A1 , . . . , AB are pairwise disjoint because they occur in different blocks. Therefore, P(A|Y = i) ≥

B X

P(Ab |Y = i)

b=1

B X

P(J = b|Y = i)P(Ab |Y = i, J = b)

b=1

B i 1 X h Pr Z̃Pe (1) = Z̃Qeb (1) Z̃Pe (1) = (i, b) . B

(17)

b=1

We now apply the exact j = 1 tail formula in the generalized Poisson matching lemma to the pair e b ). Conditioned on Z̃ e (1) = (i, b), the local PML parameter is (Pe, Q P ! B X X e b (j, ℓ) Pe(j, ℓ) Q (b) α ei := Pe(i, b) − e b (i, b) Q Pe(i, b) + ℓ=1 j∈V pi X qb,j pj = − B qb,i pi + j∈V

(b) αi

Hence h i Pr Z̃Pe (1) = Z̃Qeb (1) Z̃Pe (1) = (i, b) ≥ 1 −

(b)

α ei

(b) 1+α ei

(b)

B + αi

Substituting this into (17) gives B

P(A|Y = i) ≥

X 1 X B 1 = . (b) (b) B B+α B+α b=1

b=1

This proves (15). Averaging over Y ∼ P gives (16).

D RAFTER I NVARIANCE

C.1

D EFINITIONS

For a speculative sampling algorithm A with target model Mt , draft model Md , shared randomness R and context x:t , let Y1:τ denote the emitted output sequence of A in the current speculative block. 29

Definition C.1 ((Daliri et al., 2025)). The algorithm A is said to be strongly drafter invariant if for every 1 ≤ j ≤ τ , P Y1:j = y1:j R, x:t = P Ye1:j = y1:j R, x:t . Definition C.2 ((Rowan et al., 2025)). The algorithm A is said to be conditional drafter invariant if for every 1 ≤ j ≤ τ , letting X1:L := X1:L (Md ) denote the length-L draft sequence by Md , we have e1:L = x1:L . P Y1:j = y1:j R, x:t , X1:L = x1:L = P Ye1:j = y1:j R, x:t , X C.1.1

P ROOF OF P ROPOSITION 4.4

We rephrase Proposition 4.4 to a more detailed version as follows. Proposition C.3 (Stopping-time drafter invariance). Let τ denote the number of tokens emitted in one speculative block of Algorithm 3. Fix the initial prompt h := w1:n and the shared randomness R := { G(k, c) : c is any context }. Define the target-side PFR chain recursively by Z1 := PFR P (·|h), G(k, h) , and for s ≥ 2, Zs := PFR P (·|h∥Z1:s−1 ), G(k, h∥Z1:s−1 ) . Then, for any stopping-time value τ0 and every 1 ≤ j ≤ τ0 , Y1:j = Z1:j almost surely on the event {τ = τ0 }. Equivalently, for every output prefix y1:j , P Y1:j = y1:j R, h, τ = τ0 = 1{Z1:j = y1:j }. e In particular, for any two draft models Q and Q, P Y1:j = y1:j R, h, τ = τ0 = P Ye1:j = y1:j R, h, τe = τ0 , so Algorithm 3 is stopping-time drafter invariant in the sense of Definition 4.3. Proof. Fix (R, h) and a stopping-time value τ0 . We first show by induction on s that, on the event {τ ≥ s}, Ys = Zs . For s = 1, the first context is c1 = h. Hence Y1 = PFR P (·|c1 ), G(k, c1 ) = PFR P (·|h), G(k, h) = Z1 . Now suppose s ≥ 2 and that Yr = Zr holds on {τ ≥ r} for all r = 1, . . . , s − 1. On the event {τ ≥ s}, the block has reached step s, so the first s − 1 draft tokens were accepted. Therefore w̃1:s−1 = Y1:s−1 . By the induction hypothesis, on {τ ≥ s} we also have Y1:s−1 = Z1:s−1 , and hence cs = h∥w̃1:s−1 = h∥Y1:s−1 = h∥Z1:s−1 . Thus, Ys = PFR P (·|cs ), G(k, cs ) = PFR P (·|h∥Z1:s−1 ), G(k, h∥Z1:s−1 ) = Zs . This completes the induction. Now let 1 ≤ j ≤ τ0 . On the event {τ = τ0 } we have τ ≥ j, so the above induction gives Y1:j = Z1:j almost surely on {τ = τ0 }. Therefore, P Y1:j = y1:j R, h, τ = τ0 = 1{Z1:j = y1:j }. Since the right-hand side depends only on (R, h, τ0 ) and not on the draft model, the same conditional e conditioned on τe = τ0 . This is exactly stopping-time drafter law holds for any other draft model Q invariance. 30

C.2

M ULTI -D RAFT D RAFTER INVARIANCE (1)

(B)

For multi-draft speculative sampling scheme A with target model Mt , draft models Md , . . . , Md , (b) (b) context x:t , shared randomness R and b ∈ [B], let X1:L := X1:L (Md ) denote the length-L draft (b) sequence by Md and Y1:τ denote the emitted output sequence of A in the current speculative block. Definition C.4 (Strong drafter invariance). The algorithm A is drafter invariant if for every 1 ≤ j ≤ τ , every initial context x:t , every realization of the shared randomness R, and every output prefix y1:j , n o n o P Y1:j = y1:j R, x:t = P Ye1:j = y1:j R, x:t , for any two choices of draft models (1)

(B)

Md , . . . , M d

and

f(1) , . . . , M f(B) . M d d

Definition C.5 (Conditional drafter invariance). We say that the algorithm is conditionally drafter invariant if, for every 1 ≤ j ≤ τ , every initial context x:t , every realization of the shared randomness (1) (B) R, every draft sequences x1:L , . . . , x1:L , and every output prefix y1:j , n o (1) (1) (B) (B) P Y1:j = y1:j R, x:t , X1:L = x1:L , . . . , X1:L = x1:L n o e (1) = x(1) , . . . , X e (B) = x(B) , = P Ye1:j = y1:j R, x:t , X 1:L 1:L 1:L 1:L for any two choices of draft models (1)

(B)

Md , . . . , Md

and

f(1) , . . . , M f(B) . M d d

That is, conditioned on the shared randomness, the initial context, and the realized draft sequences, the conditional law of the emitted output prefix does not depend on which draft models generated those sequences. Definition C.6 (stopping time drafter invariance). Consider a speculative sampling algorithm with (1) (B) target model Mt , draft models Md , . . . , Md , initial context x:t , shared randomness R, and block output Y1:τ , where τ is the number of emitted tokens in the current speculative block. We say that the algorithm is stopping time drafter invariant if, for every 1 ≤ j ≤ τ , every initial context x:t , every realization of the shared randomness R, every block length value τ0 , and every output prefix y1:j , n o P Y1:j = y1:j R, x:t , τ = τ0 n o = P Ye1:j = y1:j R, x:t , τe = τ0 , for any two choices of draft models (1)

(B)

Md , . . . , M d

and

f(1) , . . . , M f(B) . M d d

That is, conditioned on the shared randomness, the initial context, and the realized block length, the conditional law of the emitted output prefix does not depend on the draft models.

E XPERIMENT D ETAILS AND F ULL R ESULTS

This appendix expands the main-text evaluation along the two axes that mirror the contributions of Section 1: (i) the single-draft regime (B=1), where we certify that our keyed Poisson sampler preserves acceptance and quality while carrying watermark signal; and (ii) the multi-draft regime (B>1), where we extend the unbiasedness/strength guarantees to larger B and benchmark sampling efficiency against the list-coupling scheme of Rowan et al. (2025). 31

D.1

S ETUP

Models. We use two target/drafter pairs that span the two model families used in the prior watermark and list-coupling literature. The headline configuration follows Rowan et al. (2025): target Qwen2.5-7B-Instruct with drafter Qwen2.5-0.5B-Instruct. For instruction-following diagnostics we additionally use lmsys/vicuna-7b-v1.5 paired with the small same-family drafter double7/vicuna-68m; the FastChat v1.1 chat template is injected explicitly because the released checkpoint does not ship a chat_template attribute. All models run in float16 on a single NVIDIA H100 GPU. Datasets. We evaluate on two tasks chosen to match the coverage of prior work: CNN/DAILY M AIL (summarization, prompted with the System:/INPUT:/OUTPUT: template of Hu and Huang (2024)) and ELI5 (open-ended explanation, Fan et al. (2019)). Each cell uses n=1000 prompts. Sampling parameters. Unless stated otherwise we use topk =50, topp =1.0, temperature T =1.0, and max_new_tokens=128. The watermark key is fixed across all runs so that detection is deterministic. Sweeps. For single-draft we sweep lookahead L ∈ {1, 2, 3, 4}, matching Hu and Huang (2024). For multi-draft we fix L=4 and sweep draft counts B ∈ {2, 4, 6, 8}, matching Rowan et al. (2025). Each (MODEL, DATASET, DECODER, L, B) configuration is run with multiple independent seeds; tables in Appendices D.3–D.4 report mean ± std across the 1000 prompts of the cell. Baselines. We adopt the four-family taxonomy used in the main text (Section 6). For convenience we restate the role of each baseline: • Quality anchor — BASIC -UWM: autoregressive Gumbel-style unbiased watermarking with no speculation. Provides the LPPL reference and the watermark-strength ceiling. • Speculation-only references — VS P S (Leviathan et al., 2023) at B=1, and the I NVARIANT (InvariantMultiDraftStrategy) of Rowan et al. (2025) at B>1. These set the efficiency ceiling. • Trade-off frontier — MWS and MSE (Hu and Huang, 2024), plus MSE-P SEUDO, the dual-key pseudorandom-r variant of He et al. (2026). These mark the Pareto frontier we aim to circumvent. • Ours — PFR (single-draft), MPFR (multi-draft), and the unwatermarked variant PFRN OWM. Metrics. We restate the three metric families used in the main text. Efficiency. AATPS (average accepted tokens per step) and Token rate in tokens/s. The latter is hardware-dependent and is reported only as a diagnostic. Detectability. ANLPPT — the average negative log p-value per token — under three score variants: ANLPPT-U (Aaronson and Kirchner, 2023; Hu and Huang, 2024), ANLPPTLi (Li et al., 2025), and ANLPPT-PL (Lattimore, 2026). We additionally report TPR@1%FPR based on the Aaronson Gamma-tail test (Appendix D.5, “Detection statistic”). Quality. LPPL (per-token log-perplexity under the target), reported as an audit column. We require LPPL parity with BASIC -UWM to certify unbiasedness, and we do not optimise against this metric. Reproducibility. The exact (seed, MODEL, DATASET, DECODER, L, B) configurations, software versions (torch, transformers, attention kernel), GPU model, and per-seed result files are released with the paper. D.2

P ROMPT TEMPLATES

For all instruction-tuned targets we apply the model’s native chat template via the HuggingFace apply_chat_template interface. The Vicuna-v1.5 release ships without a chat_template attribute, so we explicitly inject the FastChat v1.1 template before tokenization. 32

CNN/DailyMail (summarization). [ {"role": "system", "content": "You are a helpful assistant."}, {"role": "user", "content": "Summarize the following article in 3-5 sentences:\n\n" + article[:1500]} ] The article is truncated to 1500 characters before tokenization. ELI5 (open-ended QA). [ {"role": "system", "content": "You are a helpful assistant."}, {"role": "user", "content": "Please explain like I’m five:\n\n" + question} ] For each prompt the model generates up to 128 new tokens under the sampling parameters of Appendix D.1. The watermark key is fixed across all runs. D.3

S INGLE - DRAFT EXPERIMENTS : FULL RESULTS

Goal. Hu and Huang (2024) prove that, under speculative sampling, any unbiased reweighting scheme must give up either watermark strength (MSE-style) or acceptance rate (MWS-style); their Theorem 3.1 forbids schemes that strictly improve both axes simultaneously. We claim that our Poisson-process construction sidesteps the trade-off. Protocol. We follow Hu and Huang (2024): the same metric battery (AATPS, ANLPPT, LPPL) and the same lookahead range L ∈ {1, 2, 3, 4}. We evaluate on Qwen2.5-7B-Instruct/0.5B and on vicuna-7b-v1.5/vicuna-68m, on both CNN/DAILY M AIL and ELI5. On top of the Hu–Huang decoder set we add (i) our PFR sampler, (ii) the unwatermarked variant PFR-N OWM, (iii) BASIC -UWM as the unbiasedness anchor, and (iv) the pseudorandom-r variant MSE-P SEUDO of He et al. (2026). Headline figure. Figure 1 (in Section 4) plots every method as a curve in the (AATPS, ANLPPT-U ) plane sweeping L on the headline cell. Figures 3–5 report the same plot on the remaining three cells. PFR dominates the MWS/MSE Pareto frontier on every cell: at every L it sits both higher (greater detection signal) and to the right (greater acceptance) than the trade-off baselines. Unbiasedness audit. We report LPPL under the target model as an empirical audit of whether the keyed Poisson coupling introduces a measurable likelihood shift. PFR matches BASIC -UWM in LPPL within statistical noise, as shown in the final column of Tables 2–5. Together with the AATPS and ANLPPT results, this supports our empirical claim that coupling-level watermarking preserves both acceptance behavior and detector-visible signal; the exact marginal guarantee follows from the PFR construction. Per-cell tables. Tables 2–5 report all metrics per (L, DECODER) for the four (TARGET, DATASET) cells. Each cell reports mean ± std across the 1000 prompts of the cell. D.4

M ULTI - DRAFT EXPERIMENTS : FULL PER - CELL RESULTS

Setup. The main-text multi-draft paragraph (Section 6, “Multi-draft scaling”) summarises a single representative cell (Qwen2.5-7B-Instruct × CNN/DAILY M AIL). Here we extend the 33

Figure 3: Single-draft (AATPS, ANLPPT-U) frontier on Qwen2.5-7B-Instruct / Qwen2.5-0.5BInstruct × ELI5. PFR dominates MWS/MSE simultaneously on both axes; attaching the watermark does not decrease AATPS.

Figure 4: Single-draft (AATPS, ANLPPT-U) frontier on Vicuna-7B-v1.5 / Vicuna-68m × CNN/DAILY M AIL. PFR dominates MWS/MSE simultaneously on both axes; attaching the watermark does not decrease AATPS.

Figure 5: Single-draft (AATPS, ANLPPT-U) frontier on Vicuna-7B-v1.5 / Vicuna-68m × ELI5. PFR dominates MWS/MSE simultaneously on both axes; attaching the watermark does not decrease AATPS.

Table 2: Single-draft results on Qwen2.5-7B-Instruct / Qwen2.5-0.5B-Instruct × CNN/DAILY M AIL. Each cell: mean ± std across 1000 prompts. L

Method

AATPS

Token rate

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.641 ± 0.070 1.623 ± 0.075 1.625 ± 0.072 1.642 ± 0.070 1.621 ± 0.072 1.641 ± 0.072

33.353 ± 2.815 33.229 ± 1.944 32.147 ± 2.161 33.321 ± 1.706 20.578 ± 2.645 20.136 ± 2.952 20.703 ± 2.420

0.048 ± 0.035 0.003 ± 0.005 0.002 ± 0.006 0.051 ± 0.036 0.023 ± 0.021 0.049 ± 0.035 0.033 ± 0.028

0.035 ± 0.029 0.003 ± 0.006 0.003 ± 0.006 0.036 ± 0.030 0.016 ± 0.017 0.034 ± 0.029 0.023 ± 0.023

0.051 ± 0.036 0.003 ± 0.006 0.002 ± 0.006 0.053 ± 0.038 0.025 ± 0.023 0.052 ± 0.036 0.035 ± 0.029

0.473 ± 0.134 0.477 ± 0.136 0.474 ± 0.140 0.470 ± 0.143 0.472 ± 0.136 0.475 ± 0.133 0.475 ± 0.138

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 2.055 ± 0.147 2.014 ± 0.151 2.016 ± 0.154 2.056 ± 0.149 2.012 ± 0.155 2.053 ± 0.150

33.353 ± 2.815 29.399 ± 2.693 30.119 ± 2.438 29.746 ± 2.374 16.954 ± 2.182 17.915 ± 2.679 17.768 ± 2.415

0.048 ± 0.035 0.002 ± 0.006 0.002 ± 0.005 0.051 ± 0.036 0.016 ± 0.017 0.048 ± 0.035 0.030 ± 0.026

0.035 ± 0.029 0.002 ± 0.006 0.003 ± 0.005 0.036 ± 0.030 0.012 ± 0.014 0.034 ± 0.028 0.022 ± 0.021

0.051 ± 0.036 0.002 ± 0.006 0.002 ± 0.005 0.053 ± 0.038 0.018 ± 0.019 0.052 ± 0.036 0.033 ± 0.028

0.473 ± 0.134 0.482 ± 0.139 0.474 ± 0.140 0.471 ± 0.143 0.475 ± 0.139 0.473 ± 0.134 0.481 ± 0.143

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 2.327 ± 0.228 2.270 ± 0.228 2.272 ± 0.225 2.330 ± 0.228 2.262 ± 0.222 2.337 ± 0.232

33.353 ± 2.815 26.272 ± 2.968 26.709 ± 2.682 25.999 ± 2.742 13.453 ± 1.603 16.187 ± 2.509 14.933 ± 2.118

0.048 ± 0.035 0.002 ± 0.006 0.002 ± 0.006 0.051 ± 0.036 0.015 ± 0.017 0.048 ± 0.035 0.029 ± 0.026

0.035 ± 0.029 0.002 ± 0.006 0.002 ± 0.006 0.037 ± 0.030 0.011 ± 0.014 0.034 ± 0.028 0.021 ± 0.022

0.051 ± 0.036 0.003 ± 0.006 0.002 ± 0.005 0.053 ± 0.038 0.017 ± 0.018 0.051 ± 0.036 0.032 ± 0.027

0.473 ± 0.134 0.481 ± 0.141 0.474 ± 0.140 0.472 ± 0.144 0.476 ± 0.140 0.474 ± 0.134 0.480 ± 0.138

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 2.513 ± 0.288 2.439 ± 0.292 2.446 ± 0.286 2.525 ± 0.298 2.432 ± 0.287 2.499 ± 0.287

33.353 ± 2.815 23.229 ± 3.176 23.285 ± 2.840 23.075 ± 2.755 12.623 ± 1.893 13.592 ± 2.213 13.494 ± 1.934

0.048 ± 0.035 0.002 ± 0.006 0.002 ± 0.005 0.050 ± 0.036 0.014 ± 0.016 0.048 ± 0.035 0.029 ± 0.026

0.035 ± 0.029 0.002 ± 0.005 0.002 ± 0.005 0.036 ± 0.030 0.010 ± 0.013 0.034 ± 0.028 0.021 ± 0.021

0.051 ± 0.036 0.002 ± 0.006 0.002 ± 0.006 0.053 ± 0.038 0.016 ± 0.017 0.052 ± 0.036 0.031 ± 0.027

0.473 ± 0.134 0.475 ± 0.134 0.474 ± 0.142 0.471 ± 0.144 0.479 ± 0.145 0.475 ± 0.132 0.481 ± 0.141

Table 3: Single-draft results on Qwen2.5-7B-Instruct / Qwen2.5-0.5B-Instruct × ELI5. Each cell: mean ± std across 1000 prompts. L

Method

AATPS

Token rate

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.593 ± 0.060 1.567 ± 0.061 1.570 ± 0.062 1.595 ± 0.060 1.565 ± 0.063 1.593 ± 0.062

26.132 ± 1.924 32.090 ± 1.889 33.046 ± 1.405 33.213 ± 1.487 18.218 ± 2.022 20.177 ± 2.688 19.553 ± 2.107

0.100 ± 0.045 0.002 ± 0.005 0.002 ± 0.004 0.104 ± 0.048 0.048 ± 0.030 0.102 ± 0.047 0.068 ± 0.038

0.072 ± 0.039 0.002 ± 0.005 0.002 ± 0.004 0.075 ± 0.039 0.032 ± 0.024 0.075 ± 0.040 0.049 ± 0.032

0.104 ± 0.046 0.002 ± 0.005 0.002 ± 0.004 0.107 ± 0.049 0.053 ± 0.032 0.106 ± 0.048 0.071 ± 0.039

0.696 ± 0.141 0.701 ± 0.133 0.703 ± 0.139 0.699 ± 0.134 0.704 ± 0.135 0.700 ± 0.137 0.703 ± 0.145

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.948 ± 0.116 1.890 ± 0.118 1.895 ± 0.125 1.956 ± 0.126 1.888 ± 0.121 1.951 ± 0.118

26.132 ± 1.924 27.350 ± 2.434 28.719 ± 1.782 28.851 ± 1.937 14.867 ± 1.179 16.985 ± 2.208 24.767 ± 2.016

0.100 ± 0.045 0.002 ± 0.005 0.002 ± 0.005 0.104 ± 0.048 0.036 ± 0.024 0.102 ± 0.046 0.062 ± 0.034

0.072 ± 0.039 0.002 ± 0.005 0.002 ± 0.004 0.075 ± 0.039 0.024 ± 0.020 0.074 ± 0.039 0.043 ± 0.028

0.104 ± 0.046 0.002 ± 0.004 0.002 ± 0.004 0.107 ± 0.049 0.040 ± 0.026 0.105 ± 0.047 0.066 ± 0.036

0.696 ± 0.141 0.701 ± 0.136 0.698 ± 0.137 0.699 ± 0.134 0.704 ± 0.140 0.700 ± 0.142 0.706 ± 0.136

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 2.159 ± 0.175 2.074 ± 0.167 2.084 ± 0.174 2.164 ± 0.175 2.071 ± 0.169 2.169 ± 0.172

26.132 ± 1.924 23.619 ± 2.707 24.315 ± 2.065 24.675 ± 2.059 13.359 ± 2.005 14.243 ± 1.924 21.339 ± 2.086

0.100 ± 0.045 0.002 ± 0.004 0.002 ± 0.004 0.104 ± 0.049 0.030 ± 0.023 0.100 ± 0.046 0.061 ± 0.034

0.072 ± 0.039 0.002 ± 0.004 0.002 ± 0.005 0.075 ± 0.041 0.020 ± 0.019 0.073 ± 0.040 0.043 ± 0.028

0.104 ± 0.046 0.002 ± 0.003 0.002 ± 0.004 0.107 ± 0.049 0.035 ± 0.025 0.104 ± 0.047 0.064 ± 0.035

0.696 ± 0.141 0.706 ± 0.139 0.710 ± 0.139 0.697 ± 0.135 0.705 ± 0.135 0.698 ± 0.138 0.709 ± 0.133

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 2.294 ± 0.220 2.187 ± 0.204 2.196 ± 0.214 2.292 ± 0.220 2.184 ± 0.208 2.302 ± 0.214

26.132 ± 1.924 17.142 ± 3.485 21.512 ± 2.145 21.319 ± 2.212 13.200 ± 2.021 11.570 ± 1.496 18.298 ± 1.942

0.100 ± 0.045 0.002 ± 0.005 0.002 ± 0.004 0.104 ± 0.048 0.029 ± 0.021 0.101 ± 0.046 0.060 ± 0.033

0.072 ± 0.039 0.002 ± 0.005 0.002 ± 0.005 0.075 ± 0.041 0.019 ± 0.017 0.073 ± 0.039 0.042 ± 0.028

0.104 ± 0.046 0.002 ± 0.004 0.002 ± 0.004 0.107 ± 0.049 0.033 ± 0.024 0.105 ± 0.047 0.063 ± 0.035

0.696 ± 0.141 0.705 ± 0.137 0.703 ± 0.138 0.698 ± 0.134 0.701 ± 0.136 0.696 ± 0.141 0.705 ± 0.132

Table 4: Single-draft results on Vicuna-7B-v1.5 / Vicuna-68m × CNN/DAILY M AIL. Each cell: mean ± std across 1000 prompts. L

Method

AATPS

Token rate

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.557 ± 0.086 1.544 ± 0.088 1.550 ± 0.090 1.557 ± 0.088 1.547 ± 0.091 1.555 ± 0.088

37.058 ± 0.848 48.890 ± 3.439 37.027 ± 5.064 38.256 ± 6.092 45.513 ± 4.490 30.814 ± 4.078 27.597 ± 2.405

0.021 ± 0.024 0.002 ± 0.006 0.002 ± 0.006 0.022 ± 0.024 0.009 ± 0.013 0.022 ± 0.024 0.015 ± 0.018

0.016 ± 0.019 0.003 ± 0.006 0.003 ± 0.006 0.017 ± 0.019 0.007 ± 0.011 0.017 ± 0.020 0.012 ± 0.016

0.022 ± 0.025 0.002 ± 0.006 0.002 ± 0.005 0.023 ± 0.025 0.010 ± 0.015 0.023 ± 0.026 0.016 ± 0.018

0.274 ± 0.190 0.275 ± 0.167 0.269 ± 0.121 0.272 ± 0.128 0.269 ± 0.123 0.276 ± 0.192 0.279 ± 0.118

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.888 ± 0.179 1.857 ± 0.178 1.866 ± 0.183 1.876 ± 0.186 1.858 ± 0.181 1.877 ± 0.182

37.058 ± 0.848 53.865 ± 5.770 40.154 ± 5.953 42.639 ± 7.272 46.276 ± 7.794 31.588 ± 5.453 29.023 ± 4.118

0.021 ± 0.024 0.002 ± 0.006 0.003 ± 0.005 0.022 ± 0.024 0.007 ± 0.010 0.022 ± 0.024 0.015 ± 0.018

0.016 ± 0.019 0.002 ± 0.006 0.003 ± 0.006 0.017 ± 0.019 0.006 ± 0.009 0.016 ± 0.020 0.012 ± 0.015

0.022 ± 0.025 0.002 ± 0.006 0.003 ± 0.005 0.023 ± 0.025 0.007 ± 0.011 0.023 ± 0.025 0.015 ± 0.020

0.274 ± 0.190 0.268 ± 0.129 0.273 ± 0.123 0.272 ± 0.127 0.268 ± 0.131 0.278 ± 0.193 0.273 ± 0.127

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 2.076 ± 0.254 2.044 ± 0.259 2.056 ± 0.263 2.076 ± 0.260 2.043 ± 0.258 2.062 ± 0.257

37.058 ± 0.848 53.835 ± 7.463 42.513 ± 7.326 41.813 ± 7.586 38.713 ± 8.338 28.960 ± 4.759 32.256 ± 6.945

0.021 ± 0.024 0.002 ± 0.006 0.003 ± 0.006 0.022 ± 0.024 0.006 ± 0.009 0.021 ± 0.024 0.015 ± 0.019

0.016 ± 0.019 0.003 ± 0.006 0.003 ± 0.006 0.017 ± 0.019 0.005 ± 0.008 0.016 ± 0.020 0.012 ± 0.016

0.022 ± 0.025 0.002 ± 0.005 0.002 ± 0.006 0.023 ± 0.025 0.006 ± 0.010 0.022 ± 0.026 0.015 ± 0.020

0.274 ± 0.190 0.276 ± 0.212 0.274 ± 0.128 0.272 ± 0.127 0.266 ± 0.118 0.277 ± 0.191 0.277 ± 0.125

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 2.194 ± 0.324 2.159 ± 0.326 2.177 ± 0.323 2.220 ± 0.330 2.163 ± 0.319 2.183 ± 0.317

37.058 ± 0.848 53.940 ± 8.237 40.083 ± 7.877 41.800 ± 9.355 32.730 ± 6.784 27.253 ± 4.410 33.007 ± 6.806

0.021 ± 0.024 0.002 ± 0.005 0.002 ± 0.005 0.022 ± 0.023 0.005 ± 0.008 0.021 ± 0.024 0.014 ± 0.018

0.016 ± 0.019 0.002 ± 0.005 0.002 ± 0.005 0.017 ± 0.019 0.005 ± 0.008 0.016 ± 0.019 0.011 ± 0.015

0.022 ± 0.025 0.002 ± 0.005 0.002 ± 0.005 0.023 ± 0.025 0.006 ± 0.009 0.023 ± 0.025 0.014 ± 0.018

0.274 ± 0.190 0.271 ± 0.120 0.268 ± 0.117 0.272 ± 0.127 0.264 ± 0.119 0.277 ± 0.191 0.277 ± 0.121

Table 5: Single-draft results on Vicuna-7B-v1.5 / Vicuna-68m × ELI5. Each cell: mean ± std across 1000 prompts. L

Method

AATPS

Token rate

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.410 ± 0.063 1.399 ± 0.063 1.397 ± 0.065 1.415 ± 0.062 1.399 ± 0.064 1.416 ± 0.063

38.536 ± 1.896 46.306 ± 3.178 33.636 ± 4.757 35.231 ± 5.397 44.719 ± 3.192 26.309 ± 3.816 28.987 ± 4.863

0.060 ± 0.040 0.002 ± 0.005 0.003 ± 0.006 0.061 ± 0.043 0.020 ± 0.020 0.060 ± 0.041 0.040 ± 0.030

0.044 ± 0.033 0.003 ± 0.005 0.003 ± 0.007 0.045 ± 0.038 0.014 ± 0.017 0.044 ± 0.034 0.029 ± 0.025

0.062 ± 0.042 0.002 ± 0.005 0.002 ± 0.005 0.063 ± 0.042 0.022 ± 0.022 0.062 ± 0.042 0.042 ± 0.031

0.507 ± 0.152 0.511 ± 0.150 0.509 ± 0.152 0.513 ± 0.162 0.509 ± 0.147 0.507 ± 0.151 0.504 ± 0.152

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.589 ± 0.104 1.562 ± 0.103 1.558 ± 0.106 1.587 ± 0.105 1.560 ± 0.109 1.593 ± 0.110

38.536 ± 1.896 47.569 ± 3.837 34.678 ± 4.452 34.425 ± 4.996 33.648 ± 4.994 23.481 ± 2.014 28.595 ± 4.733

0.060 ± 0.040 0.003 ± 0.006 0.002 ± 0.005 0.061 ± 0.043 0.012 ± 0.014 0.060 ± 0.040 0.040 ± 0.032

0.044 ± 0.033 0.003 ± 0.006 0.002 ± 0.005 0.044 ± 0.038 0.009 ± 0.012 0.043 ± 0.034 0.029 ± 0.027

0.062 ± 0.042 0.003 ± 0.006 0.002 ± 0.006 0.063 ± 0.042 0.014 ± 0.016 0.062 ± 0.042 0.041 ± 0.032

0.507 ± 0.152 0.509 ± 0.146 0.505 ± 0.147 0.513 ± 0.162 0.509 ± 0.147 0.510 ± 0.157 0.509 ± 0.152

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.670 ± 0.134 1.624 ± 0.132 1.626 ± 0.130 1.671 ± 0.136 1.626 ± 0.136 1.666 ± 0.134

38.536 ± 1.896 45.003 ± 5.451 31.214 ± 4.662 35.694 ± 5.835 26.134 ± 3.956 22.536 ± 2.127 28.611 ± 4.748

0.060 ± 0.040 0.003 ± 0.006 0.002 ± 0.005 0.062 ± 0.043 0.011 ± 0.014 0.059 ± 0.040 0.037 ± 0.028

0.044 ± 0.033 0.002 ± 0.005 0.002 ± 0.005 0.045 ± 0.038 0.008 ± 0.012 0.043 ± 0.033 0.027 ± 0.023

0.062 ± 0.042 0.002 ± 0.006 0.002 ± 0.005 0.063 ± 0.042 0.012 ± 0.015 0.061 ± 0.041 0.039 ± 0.029

0.507 ± 0.152 0.513 ± 0.157 0.506 ± 0.149 0.515 ± 0.162 0.499 ± 0.145 0.508 ± 0.152 0.505 ± 0.148

BASIC -UWM VS P S PFR-N OWM PFR MSE MWS MSE-P SEUDO

1.000 ± 0.000 1.697 ± 0.152 1.656 ± 0.145 1.656 ± 0.146 1.700 ± 0.154 1.651 ± 0.149 1.703 ± 0.155

38.536 ± 1.896 43.287 ± 5.333 28.914 ± 4.147 32.316 ± 5.921 23.993 ± 3.469 22.198 ± 3.679 26.004 ± 4.603

0.060 ± 0.040 0.002 ± 0.005 0.002 ± 0.005 0.062 ± 0.043 0.011 ± 0.014 0.059 ± 0.039 0.037 ± 0.030

0.044 ± 0.033 0.002 ± 0.006 0.002 ± 0.005 0.045 ± 0.038 0.008 ± 0.012 0.043 ± 0.033 0.027 ± 0.024

0.062 ± 0.042 0.002 ± 0.005 0.002 ± 0.005 0.063 ± 0.042 0.012 ± 0.015 0.062 ± 0.041 0.039 ± 0.031

0.507 ± 0.152 0.510 ± 0.152 0.503 ± 0.149 0.515 ± 0.162 0.514 ± 0.150 0.509 ± 0.153 0.508 ± 0.147

evaluation to the 2×2 matrix {Qwen2.5-7B-Instruct, Vicuna-7B-v1.5} × {CNN/DAILY M AIL, ELI5}, using the target/drafter pairs Qwen2.5-7B-Instruct/Qwen2.5-0.5B-Instruct and lmsys/vicuna-7b-v1.5/double7/vicuna-68m. Each cell uses n=1000 prompts, lookahead L=4, and draft counts B ∈ {2, 4, 6, 8}, with the sampling parameters of Appendix D.1. Decoders. MPFR is our keyed multi-draft Poisson sampler; I NVARIANT is the unwatermarked InvariantMultiDraftStrategy of Rowan et al. (2025) run in the same harness on the same prompt set. The two decoders share the draft/verify mechanism and differ only in whether the per-context watermark key is applied. Per-cell tables. Tables 10–13 report all quality and watermark-strength metrics per (decoder, B). Columns: AATPS, token rate in tokens/s (TR), ANLPPT-{U, Li, PL}, and LPPL. The corresponding TPR-vs-Teval curves are reported in Figure 6 of Appendix D.5. Table 6: Multi-draft results on Qwen2.5-7B-Instruct × CNN/DAILY M AIL, L=4. Decoder

AATPS

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

MPFR MPFR MPFR MPFR I NVARIANT I NVARIANT I NVARIANT I NVARIANT

2 4 6 8 2 4 6 8

2.797 ± 0.001 3.123 ± 0.002 3.294 ± 0.003 3.409 ± 0.002 2.803 ± 0.007 3.109 ± 0.008 3.272 ± 0.010 3.384 ± 0.012

25.11 ± 0.22 27.50 ± 0.31 28.50 ± 0.49 29.13 ± 0.59 24.78 ± 0.14 27.12 ± 0.20 27.84 ± 0.60 28.62 ± 0.54

0.051 ± 0.001 0.051 ± 0.001 0.050 ± 0.001 0.051 ± 0.002 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000

0.036 ± 0.001 0.036 ± 0.001 0.036 ± 0.001 0.036 ± 0.001 0.003 ± 0.000 0.002 ± 0.000 0.002 ± 0.000 0.003 ± 0.000

0.053 ± 0.001 0.053 ± 0.001 0.053 ± 0.001 0.053 ± 0.002 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000

0.474 ± 0.002 0.474 ± 0.002 0.474 ± 0.001 0.474 ± 0.002 0.483 ± 0.005 0.484 ± 0.003 0.481 ± 0.000 0.476 ± 0.004

Speculative-acceptance parity. Within each cell, MPFR remains close to INVARIANT in AATPS across B ∈ {2, 4, 6, 8}, with small deviations in both directions depending on the model–dataset cell. This indicates that the target-side keyed-race construction does not introduce a systematic per-step acceptance penalty. Token rate is reported as a hardware- and implementation-dependent diagnostic, 37

Table 7: Multi-draft results on Qwen2.5-7B-Instruct × ELI5, L=4. Decoder

AATPS

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

MPFR MPFR MPFR MPFR I NVARIANT I NVARIANT I NVARIANT I NVARIANT

2 4 6 8 2 4 6 8

2.563 ± 0.007 2.918 ± 0.008 3.109 ± 0.005 3.235 ± 0.010 2.523 ± 0.004 2.850 ± 0.010 3.039 ± 0.004 3.156 ± 0.009

23.57 ± 0.15 26.46 ± 0.25 27.81 ± 0.35 28.73 ± 0.49 22.73 ± 0.22 25.60 ± 0.26 27.01 ± 0.32 28.09 ± 0.36

0.104 ± 0.001 0.104 ± 0.001 0.103 ± 0.001 0.104 ± 0.002 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000

0.075 ± 0.001 0.076 ± 0.001 0.075 ± 0.001 0.075 ± 0.002 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000

0.108 ± 0.001 0.108 ± 0.001 0.107 ± 0.001 0.108 ± 0.001 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000

0.705 ± 0.001 0.706 ± 0.000 0.705 ± 0.000 0.706 ± 0.001 0.747 ± 0.005 0.736 ± 0.002 0.728 ± 0.002 0.728 ± 0.002

Table 8: Multi-draft results on Llama-3.1-8B-Instruct × CNN/DAILY M AIL, L = 4. Mean ± std over 3 random seeds, 1000 prompts each. The drafter is Llama-3.2-1B-Instruct, the official distillation of the target sharing the same tokenizer. Decoder

AATPS

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

MPFR MPFR MPFR MPFR

2 4 6 8

3.459 ± 0.015 3.784 ± 0.013 3.935 ± 0.005 4.034 ± 0.005

37.44 ± 0.57 40.20 ± 0.28 41.71 ± 0.30 42.04 ± 0.81

0.058 ± 0.001 0.058 ± 0.000 0.058 ± 0.000 0.058 ± 0.001

0.041 ± 0.000 0.041 ± 0.000 0.041 ± 0.000 0.041 ± 0.000

0.061 ± 0.001 0.062 ± 0.001 0.061 ± 0.001 0.061 ± 0.001

0.514 ± 0.002 0.514 ± 0.003 0.514 ± 0.003 0.514 ± 0.003

I NVARIANT I NVARIANT I NVARIANT I NVARIANT

2 4 6 8

3.431 ± 0.005 3.741 ± 0.007 3.894 ± 0.007 3.987 ± 0.010

36.79 ± 0.37 39.31 ± 0.29 40.51 ± 0.25 39.87 ± 0.66

0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000

0.514 ± 0.003 0.508 ± 0.001 0.507 ± 0.001 0.505 ± 0.003

since it also reflects batching, hashing, and watermark-bookkeeping overhead beyond acceptance behavior. Stability of the watermark signal across B. ANLPPT-U, ANLPPT-Li, and ANLPPT-PL for MPFR remain within ±0.001 across B ∈ {2, 4, 6, 8} on every cell of Tables 10–13. The per-token detection signal therefore does not dilute with the number of drafts, in contrast to naive multi-draft watermarking, which would re-introduce the efficiency–detectability trade-off of Hu and Huang (2024) at the multi-draft level. Distortion-free audit. LPPL of MPFR outputs falls within ±0.013 nats/token of I NVARIANT on every cell. This empirical audit is consistent with the exact marginal-preservation guarantee of the MPFR construction and indicates that the watermark does not introduce a measurable shift in target-model log-perplexity in the multi-draft regime. D.5

D RAFTER - SUBSTITUTION ABLATION : FULL RESULTS

Drafter conditions. D0 : Qwen2.5-0.5B-Instruct at T =1.0 (default). D1 : Qwen2.5-1.5B-Instruct at T =1.0 (3× scale, model swap). D2 : Qwen2.5-0.5B-Instruct at T =0.5 (sharper drafter). D3 : Qwen2.5-0.5B-Instruct at T =1.5 (more diffuse drafter). The target temperature, watermark key, and all other parameters are held fixed across D0 –D3 . Detection statistic. For the Aaronson Gamma-tail test, the per-token score is st = − log(1 − Ut ), where Ut is the per-token uniform P recovered from the watermark code. Under the no-watermark null, the cumulative score ST = t≤T st is Gamma(T, 1); we declare detection at FPR= α when PrH0 [Gamma(T, 1) > ST ] ≤ α, computed via the regularised upper incomplete gamma. We report α=1% throughout. Full detection across models and datasets. Figure 6 extends the default-drafter detection comparison of Figure 2(a) to all four (TARGET, DATASET) cells of the main 2×2 result. In every cell, PFR/MPFR (ours) coincide with the strong-watermark ceiling defined by autoregressive BASIC UWM and MWS, while MSE and MSE-P SEUDO (He et al., 2026) are uniformly weaker. The size of the gap is dataset-dependent — largest on CNN/DAILY M AIL, smallest on the longer-form ELI5 where every scheme approaches saturation by Teval =128 — but the ranking is invariant. This 38

Table 9: Multi-draft results on Llama-3.1-8B-Instruct × ELI5, L = 4. Mean ± std over 3 random seeds, 1000 prompts each. Decoder

AATPS

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

MPFR MPFR MPFR MPFR

2 4 6 8

3.103 ± 0.006 3.455 ± 0.010 3.635 ± 0.001 3.749 ± 0.002

34.29 ± 0.35 37.79 ± 0.38 39.59 ± 0.43 39.76 ± 0.80

0.135 ± 0.001 0.135 ± 0.002 0.135 ± 0.002 0.135 ± 0.001

0.099 ± 0.001 0.099 ± 0.001 0.099 ± 0.001 0.098 ± 0.000

0.139 ± 0.001 0.139 ± 0.002 0.139 ± 0.002 0.139 ± 0.001

0.811 ± 0.004 0.812 ± 0.003 0.812 ± 0.005 0.811 ± 0.004

I NVARIANT I NVARIANT I NVARIANT I NVARIANT

2 4 6 8

3.080 ± 0.011 3.408 ± 0.006 3.588 ± 0.008 3.700 ± 0.008

33.72 ± 0.60 37.11 ± 0.12 39.12 ± 0.31 39.37 ± 0.58

0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000 0.002 ± 0.000

0.803 ± 0.003 0.794 ± 0.004 0.795 ± 0.008 0.790 ± 0.003

Table 10: Multi-draft results on Qwen2.5-7B-Instruct × CNN/DAILY M AIL, L=4. Decoder

AATPS

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

MPFR MPFR MPFR MPFR I NVARIANT I NVARIANT I NVARIANT I NVARIANT

2 4 6 8 2 4 6 8

2.799 3.124 3.298 3.410 2.804 3.114 3.275 3.387

23.18 24.89 25.39 25.17 25.03 26.63 26.79 26.38

0.052 0.052 0.052 0.053 0.003 0.002 0.002 0.002

0.037 0.037 0.037 0.037 0.003 0.002 0.003 0.003

0.055 0.055 0.055 0.055 0.002 0.002 0.002 0.002

0.475 0.474 0.476 0.476 0.487 0.481 0.482 0.479

confirms that the detection-strength conclusion drawn from the anchor cell in Figure 2(a) is not specific to a single (TARGET, DATASET) pair. Pairwise ROUGE-L under drafter substitution. For each prompt p and decoder d we have one realised output token sequence per drafter condition. We compute ROUGE-L F1 over each pair (Di , Dj ) of drafter conditions on these token sequences, then report the per-prompt minimum over the six pairs (worst pair) averaged across prompts (Table 15). An unbiased verify rule that depends only on the target logits and the watermark key produces identical sequences across all drafters, so this quantity should approach 1.

M ORE ON WATERMARK

In this section, we discuss different watermarks that are related to our scheme. E.1

G UMBEL WATERMARK

We use a common notation for the scored positions throughout this subsection. Let T := {m + 1, . . . , n} and M := |T | = n − m. For each t ∈ T , let rt : V → (0, 1) be the keyed random function, and define Ut := rt (wt ), At := − log(1 − Ut ). Aaronson’s Gumbel watermark score (Aaronson and Kirchner, 2023) is X X SA := At = − log(1 − rt (wt )). t∈T

t∈T

Under the null hypothesis, i.e., when y1:n is not generated from the watermarked model, the variables (Ut )t∈T are independent Unif(0, 1) random variables. Hence (At )t∈T are independent Exp(1) random variables, and E [SA ] = M. If y1:n is generated from the Gumbel-watermarked model, then 2 X π E [SA ] ≥ M + −1 E Entropy pt (·) , 6 t∈T

Table 11: Multi-draft results on Qwen2.5-7B-Instruct × ELI5, L=4. Decoder

AATPS

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

MPFR MPFR MPFR MPFR I NVARIANT I NVARIANT I NVARIANT I NVARIANT

2 4 6 8 2 4 6 8

2.563 2.919 3.111 3.237 2.519 2.852 3.043 3.158

22.38 24.48 25.54 25.83 23.18 25.75 27.11 27.96

0.104 0.104 0.105 0.105 0.002 0.002 0.002 0.002

0.076 0.076 0.076 0.076 0.002 0.002 0.002 0.002

0.108 0.107 0.108 0.108 0.002 0.002 0.002 0.002

0.704 0.703 0.706 0.704 0.750 0.733 0.730 0.725

Table 12: Multi-draft results on Vicuna-7B-v1.5 × CNN/DAILY M AIL, L=4. Decoder

AATPS

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

MPFR MPFR MPFR MPFR I NVARIANT I NVARIANT I NVARIANT I NVARIANT

2 4 6 8 2 4 6 8

2.422 2.664 2.803 2.899 2.478 2.690 2.831 2.925

52.10 48.28 44.44 40.76 58.15 53.12 48.41 44.01

0.022 0.022 0.022 0.022 0.002 0.002 0.002 0.002

0.017 0.017 0.017 0.017 0.002 0.002 0.003 0.002

0.022 0.023 0.023 0.023 0.002 0.002 0.002 0.002

0.270 0.271 0.270 0.270 0.287 0.286 0.283 0.288

Table 13: Multi-draft results on Vicuna-7B-v1.5 × ELI5, L=4. Decoder

AATPS

ANLPPT-U

ANLPPT-Li

ANLPPT-PL

LPPL

MPFR MPFR MPFR MPFR I NVARIANT I NVARIANT I NVARIANT I NVARIANT

2 4 6 8 2 4 6 8

1.889 2.133 2.278 2.377 1.884 2.108 2.248 2.361

45.89 47.43 47.42 46.42 50.29 53.42 55.08 56.00

0.058 0.058 0.058 0.059 0.002 0.002 0.002 0.003

0.043 0.042 0.042 0.043 0.002 0.002 0.003 0.003

0.061 0.061 0.062 0.062 0.002 0.002 0.002 0.002

0.504 0.504 0.503 0.504 0.555 0.552 0.546 0.539

where pt = Softmax(ut /T ) and the entropy is measured in nats. Since SA ∼ Gamma(M, 1) under the null hypothesis, the corresponding p-value is Γ(M, SA ) pA = P Gamma(M, 1) ≥ SA = , Γ(M ) where Γ(M ) is the gamma function and Γ(M, SA ) is the upper incomplete gamma function. The Average Negative Log P-value Per Token (ANLPPT) for Aaronson’s score is 1 ANLPPTA := − log pA . M Following the U -score framework (Hu and Huang, 2024), one may instead aggregate the keyed uniforms directly: X SU := Ut . t∈T

Under the null hypothesis, Ut ∼ Unif(0, 1). Since for U ∼ Unif(0, 1), eλ − 1 E eλU = , λ we have E eλSU =

λ ≥ 0,

λ M e −1 . λ 40

Figure 6: Full detection across (TARGET, DATASET) cells. TPR@1%FPR (Aaronson Gammatail) versus detection token budget Teval at the default drafter D0 , for the seven schemes plotted in Figure 2(a). Each panel is one cell of the main 2×2 result: target ∈ {Qwen2.5-7B-Instruct, Vicuna7B-v1.5} × dataset ∈ {CNN/DAILY M AIL, ELI5}. PFR/MPFR (ours) match the strong-watermark ceiling (BASIC -UWM, MWS) in every cell, while MSE and MSE-P SEUDO are uniformly weaker. The empirical H0 (no-watermark) floor sits near the nominal 1% FPR, calibrating the test. Table 14: Output quality. LPPL↓ under target. ROUGE-L↑ vs. gold highlights. AATPS↑ accepted target tokens per step. Single-draft baselines

Multi-draft (B=4)

Metric

VS P S PFR-N OWM BASIC -UWM MSE MWS MSE-P SEUDO

PFR

LPPL↓ ROUGE-L↑ AATPS↑

0.474 0.219 2.51

0.465 0.223 2.46

0.469 0.222 2.46

0.472 0.223 1.00

0.470 0.221 2.53

0.475 0.223 2.43

0.477 0.219 2.52

I NVARIANT MPFR 0.484 0.222 3.12

0.474 0.222 3.13

Chernoff’s bound gives eλ − 1 pU ≤ inf exp M log − λSU , λ≥0 λ

and the corresponding ANLPPT is ANLPPTU := − E.2

1 log pU . M

C ONNECTION TO D ELTAG UMBEL R EWEIGHTING

We now relate the above notation to the DeltaGumbel reweighting rule used in (Hu and Huang, 2024). For each scored position t ∈ T , let Pt := P (· | w:t−1 ) be the target next-token distribution. Define gt (v) := − log − log rt (v) , 41

v ∈ V.

Table 15: Output stability under drafter substitution. Pairwise ROUGE-L F1 between the realised token sequences across each (Di , Dj ) pair, per-prompt minimum averaged over prompts. An unbiased verify rule produces identical sequences across all drafters, so ROUGE-L → 1. Decoder

min-pair mean ROUGE-L

BASIC -UWM (no drafter, vacuous bound) PFR (ours) MWS

1.000 0.990 0.922

PFR-N OWM (no wm) MSE-P SEUDO MSE VS P S (no wm)

0.436 0.426 0.406 0.394

Then (gt (v))v∈V are independent standard Gumbel random variables. The DeltaGumbel rule selects a⋆t := arg max {log Pt (v) + gt (v)} . v∈V

Equivalently, for a fixed key, the reweighted distribution at position t is the point mass Qt := Rgt (Pt ) = δa⋆t . The likelihood-agnostic U -score of (Hu and Huang, 2024) is Ut := exp − exp(−gt (wt )) . By the definition of gt , this is exactly Ut = rt (wt ). Therefore, Aaronson’s per-token score is a deterministic transform of the DeltaGumbel U -score: At = − log(1 − rt (wt )) = − log(1 − Ut ). Thus SA =

At =

t∈T

− log(1 − Ut ).

t∈T

In particular, if the full vector (Ut )t∈T is retained, then Aaronson’s score can be computed exactly from the U -scores, and conversely Ut = 1 − exp(−At ). However, the aggregate statistics X

and

t∈T

− log(1 − Ut )

t∈T

are not equivalent in general, since they apply different nonlinear transformations before aggregation. E.3

WATERMARK S CORE BY (L I ET AL ., 2025)

The score of Li et al. (2025) is also computed from the same pivot rt (wt ). For a parameter ∆, define 1 k∆ := , q∆ := 1 − k∆ (1 − ∆). 1−∆ Their per-token score is 1−q∆ ∆ h⋆gum,∆ (r) = log k∆ r 1−∆ + 1{q∆ > 0}r q∆ , and the corresponding statistic is SLi,∆ :=

h⋆gum,∆ (rt (wt )).

t∈T

We now discuss another watermark score for Aaronson’s Gumbel Watermark, proposed by (Li et al., 2025), which is a statistically optimal score function for the Gumbel watermark under a class-dependent efficiency criterion. We introduce their result using our notation as follows. Their Gumbel pivot is exactly Ytgum := rt (wt ). Under the null hypothesis, Ytgum ∼ Unif[0, 1]. Under the Gumbel-watermarked alternative, conditional on Pt := P (·|w:t−1 ), the pivot satisfies X

PH1 (Ytgum ≤ r|Pt ) =

Pt (v)r1/Pt (v) ,

r ∈ [0, 1],

v∈V

where terms with Pt (v) = 0 are omitted. Aaronson’s original score corresponds to the per-token score function hA (r) := − log(1 − r), so that X

SA =

hA (rt (wt )).

t∈T

In contrast, Li et al. (Li et al., 2025) consider the distribution class P∆ := P : max P (v) ≤ 1 − ∆ v∈V

and derive the optimal Gumbel score 1−q∆ ∆ h⋆gum,∆ (r) = log k∆ r 1−∆ + 1{q∆ > 0}r q∆ , where k∆ :=

1 , 1−∆

q∆ := 1 − k∆ (1 − ∆).

The corresponding statistic in our notation is X SLi,∆ := h⋆gum,∆ (rt (wt )). t∈T

This score is the log-likelihood ratio associated with the least-favorable distribution ⋆ P∆ = (1 − ∆, . . . , 1 − ∆, q∆ , 0, . . . , 0), {z } | k∆ times

with the q∆ term omitted when q∆ = 0. Therefore, h⋆gum,∆ is not the same as Aaronson’s original score hA . Indeed, hA (r) → ∞ as r ↑ 1, whereas h⋆gum,∆ (r) → log (k∆ + 1{q∆ > 0})

as r ↑ 1.

Thus, Li et al.’s score and Aaronson’s original score are based on the same Gumbel pivot rt (wt ), but they lead to different cumulative detection statistics. 43

E.4

WATERMARK S CORE BY (L ATTIMORE , 2026)

Lattimore (2026) proposed a refined detector for the Gumbel watermark based on a truncated power-law score. In our notation, the same Gumbel pivot is t∈T.

rt (wt ), Instead of Aaronson’s original per-token score

hA (r) := − log(1 − r), Lattimore (Lattimore, 2026) considers n o √ hPL,ϵ (r) = min ϵ−1/2 , (1 − r)−1/2 − (2 − ϵ), and the corresponding statistic is SPL,ϵ := Here the centering term 2 −

√

hPL,ϵ (rt (wt )).

t∈T

ϵ is chosen so that, under the null hypothesis, U ∼ Unif[0, 1].

E[hPL,ϵ (U )] = 0,

Thus, under the null and assuming independence across the scored positions, E[SPL,ϵ ] = 0. Both SPL,ϵ and Aaronson’s statistic SA =

hA (rt (wt ))

t∈T

are model-agnostic statistics based on the same Gumbel pivot rt (wt ). However, they are not equivalent. In particular, hA (r) → ∞ as r ↑ 1, whereas √ hPL,ϵ (r) ≤ ϵ−1/2 − (2 − ϵ) is bounded because of the truncation. Therefore, Lattimore’s truncated power-law score and Aaronson’s original score use the same keyed randomness, but lead to different cumulative detection statistics.

A LGORITHM I MPLEMENTATION

Algorithm 8: Compute Aaronson score, exact null p-value, and ANLPPT for keyed PFR watermark Input :output sequence w1:N , prompt length n0 , labeler Λ, secret key k, reference measure µ Output :Aaronson score SA , p-value pA , ANLPPT ANLPPTA and M = |T | SA ← 0 M ←0 for t = n0 + 1 to N do ct ← w:t−1 ℓt ← Λ(ct ) Πt ← G(k, ℓt ) // recover keyed uniform value for the observed token wt τt (wt ) ← F IRSTA RRIVAL(wt , Πt , µ) rt ← exp(−µ(wt )τt (wt )) SA ← SA − log(1 − rt ) M ←M +1 end // Under H0 , SA ∼ Gamma(M, 1) pA ← Γ(M, SA )/Γ(M ) 1 ANLPPTA ← − M log pA 44

Algorithm 9: Watermarkable Speculative Sampling via Poisson Processes Input :lookahead K, output length N , target model family P , draft model family Q, initial prefix w1:n , common reference measure µ on Z such that P (·|c), Q(·|c) ≪ µ for all contexts c, labeler Λ, secret key k while n < N do h ← w1:n // freeze block-start prefix L ← min{K, N − n} for s = 1 to L // draft L tokens from shared PFR sources do cs ← h ∥ w̃1:s−1 ℓs ← Λ(cs ) // includes repeated-context masking if used Πs ← G(k, ℓs ) w̃s ← PFR(Q(·|cs ), Πs , µ) end if n + L < N : cL+1 ← h ∥ w̃1:L end // Prepare target-side evaluations for c1 , . . . , cL and, if needed, cL+1 in parallel accepted ← true // Verify each draft token using the same shared Poisson source for s = 1 to L do ys ← PFR(P (·|cs ), Πs , µ) wn+1 ← ys ; n ← n + 1 // emit the target PFR winner if ys ̸= w̃s : accepted ← false break // correction: later draft contexts are invalid end end if accepted and n < N : ℓL+1 ← Λ(cL+1 ) ΠL+1 ← G(k, ℓL+1 ) wn+1 ← PFR(P (·|cL+1 ), ΠL+1 , µ) n←n+1 // bonus token end end

Algorithm 10: Watermarkable Multi-Draft Speculative Sampling (Formal) Given :lookahead L, number of drafts B, output length N , target model P , draft model Q, initial prompt w1:n , keyed Poisson source generator G, and secret key k while n < N do h ← w1:n ; ℓ ← min{L, N − n} C0 ← {h}; ν(h) ← B // root context; all B homogeneous drafts start here for s = 1 to ℓ do Cs ← ∅ for c ∈ Cs−1 do Π(c) ← G(k, c) // context-indexed keyed source shared by draft and target at context c for i = 1 to ν(c) do w̃(c, i) ← MPFR(Q(·|c), Π(c), i) D(c) ← {w̃(c, 1), . . . , w̃(c, ν(c))} // distinct next-token proposals from context c for u ∈ D(c) do ν(c ∥ u) ← { i ∈ {1, . . . , ν(c)} : w̃(c, i) = u } // how many drafts move to child context c∥u Cs ← Cs ∪ { c ∥ u } for c ∈ C0 ∪ · · · ∪ Cℓ−1 do // compute target-side winner at every internal context y(c) ← MPFR(P (·|c), Π(c), 1) // target-side mapped-Poisson winner at context c c⋆ ← h; accepted ← true // start following the unique realized target path from the root for s = 1 to ℓ do as ← 1{y(c⋆ ) ∈ D(c⋆ )} // accept if the target winner is among the drafts at the current context wn+1 ← y(c⋆ ); n ← n + 1 // emit the target-side token, not a draft token if as = 0 : accepted ← false and break // first rejection ends the speculative block if n = N : break c⋆ ← c⋆ ∥ y(c⋆ ) // move to the next realized context if accepted and n < N : // if all ℓ steps were accepted, emit one extra target token Π⋆ ← G(k, c⋆ ) wn+1 ← MPFR(P (·|c⋆ ), Π⋆ , 1) n←n+1 // bonus token

Record · ID 1006782 · SHA-256 79adb8ad8cd4c8e0
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.