Paper deep dive
Selective Disclosure Watermarking for Large Language Models
Xuyang Chen, Xiang Li, Yangxinyu Xie, Qi Long
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 7/7/2026, 5:50:41 PM
Summary
The paper introduces Hierarchical Vocabulary Routing (HeRo), a novel watermarking framework for Large Language Models that enables selective disclosure of embedded metadata. By recursively partitioning the vocabulary into hierarchical layers, HeRo allows verifiers with different authorization levels to decode only corresponding portions of the payload, addressing privacy concerns in existing all-or-nothing multi-bit watermarking schemes while preserving statistical unbiasedness and text quality.
Entities (9)
Relation Signals (7)
Hierarchical Vocabulary Routing (HeRo) → enables → Selective Disclosure
confidence 97% · We propose Hierarchical Vocabulary Routing (HeRo), a watermarking framework that enables selective disclosure of embedded metadata.
Hierarchical Vocabulary Routing (HeRo) → uses → Hierarchical Vocabulary Partitioning
confidence 96% · To this end, we introduce a selective-disclosure watermarking framework based on hierarchical vocabulary partitioning.
Hierarchical Vocabulary Routing (HeRo) → preserves → Statistical Unbiasedness
confidence 95% · We show that the proposed scheme preserves the unbiasedness of the underlying sampling process and thus maintains text quality.
Hierarchical Vocabulary Routing (HeRo) → implementes → Gumbel-Max Sampling
confidence 94% · We instantiate the framework using Gumbel-based watermarking and evaluate detection accuracy, text quality, robustness under representative perturbations, and computational cost.
Hierarchical Vocabulary Routing (HeRo) → improvesupon → Multi-bit Watermarking
confidence 93% · However, current multi-bit watermarking methods do not allow selective disclosure: verifying any part of the watermark requires revealing the entire embedded message.
Green-Red List Scheme → servesasfoundationfor → Multi-bit Watermarking
confidence 92% · Many multi-bit methods build on the Green-Red List paradigm (Kirchenbauer et al., 2023) by making the vocabulary partition message-dependent...
MPAC → uses →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Watermarking methods embed imperceptible and verifiable signals into text generated by large language models (LLMs). Existing approaches include zero-bit schemes for distinguishing synthetic text from human writing and multi-bit schemes for embedding metadata. However, current multi-bit watermarking methods do not allow selective disclosure: verifying any part of the watermark requires revealing the entire embedded message. This lack of control leads to unnecessary information exposure and raises privacy concerns. We propose Hierarchical Vocabulary Routing (HeRo), a watermarking framework that enables selective disclosure of embedded metadata. The method recursively partitions the vocabulary and distributes watermark information across hierarchical layers, so that different verifiers can decode only the portions of the payload corresponding to their access level. We show that the proposed scheme preserves the unbiasedness of the underlying sampling process and thus maintains text quality. Experiments demonstrate that our framework supports fine-grained access control while achieving high detection accuracy and low latency. Code is available at this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2607.05353v1
- Canonical: https://arxiv.org/abs/2607.05353v1
Trouble viewing inline? Open PDF directly →
Full Text
82,993 characters extracted from source content.
Expand or collapse full text
Selective Disclosure Watermarking for Large Language Models Xuyang Chen1 Xiang Li1 Yangxinyu Xie1 Qi Long1 Abstract Watermarking methods embed imperceptible and verifiable signals into text generated by large language models (LLMs). Existing approaches include zero-bit schemes for distinguishing synthetic text from human writing and multi-bit schemes for embedding metadata. However, current multi-bit watermarking methods do not allow selective disclosure: verifying any part of the watermark requires revealing the entire embedded message. This lack of control leads to unnecessary information exposure and raises privacy concerns. We propose Hierarchical Vocabulary Routing (HeRo), a watermarking framework that enables selective disclosure of embedded metadata. The method recursively partitions the vocabulary and distributes watermark information across hierarchical layers, so that different verifiers can decode only the portions of the payload corresponding to their access level. We show that the proposed scheme preserves the unbiasedness of the underlying sampling process and thus maintains text quality. Experiments demonstrate that our framework supports fine-grained access control while achieving high detection accuracy and low latency. Code is available at https://github.com/xuyangc03/hero-watermark. 1 Introduction The widespread adoption of large language models (LLMs) has fundamentally transformed content creation across many domains. Their ability to produce high-quality, human-like text at scale brings substantial benefits, but also introduces serious social risks (Bommasani et al., 2021; Weidinger et al., 2021), including academic dishonesty, harmful content generation, and misinformation (Ranade et al., 2021; Huang and Sun, 2023). Early attempts to distinguish AI-generated text from human writing relied on post-hoc, content-based detectors (Mitchell et al., 2023). However, these methods (e.g., GPTZero, OpenAI’s Detector) have shown limited effectiveness as LLMs continue to improve (Weber-Wulff et al., 2023). At the same time, regulators are increasingly emphasizing provider-side content authentication mechanisms, such as transparency and machine-readable marking requirements in the EU AI Act (The European Parliament and the Council of the European Union, 2024; Laux et al., 2024) and emerging state-level regulations in California (California State Legislature, 2024). Watermarking has emerged as a promising alternative by embedding algorithmically verifiable yet human-imperceptible signals directly into model outputs. A large body of prior work on LLM watermarking (Kirchenbauer et al., 2023; Aaronson and Kirchner, 2024; Zhao et al., 2024; Dathathri et al., 2024) focuses on zero-bit schemes, whose goal is to distinguish LLM-generated text from human writing. While effective for detection, it is essentially a binary classification problem, which is insufficient for many real-world provenance tracking and auditing applications. To address this limitation, multi-bit watermarking methods (Fernandez et al., 2023; Wang et al., 2024; Yoo et al., 2024; Jiang et al., 2025; Feng et al., 2025) allow providers to embed richer metadata into generated text, such as model versions, timestamps, or user and session identifiers. However, existing designs typically do not support partial verification: any party with access to the verification key can recover the entire embedded payload. In practice, this all-or-nothing disclosure creates a fundamental deployment challenge. Many real systems require two conflicting properties: (1) broad verifiability, so that the public can confirm coarse provenance information, and (2) restricted auditing, so that sensitive metadata can be accessed only by authorized parties. For example, a platform moderator may only need to verify that content was produced by a specific provider or model family, whereas a privileged auditor may need access to confidential fields such as internal identifiers or user information (The European Parliament and the Council of the European Union, 2024; California State Legislature, 2024). Without fine-grained access control, providers must choose between full opacity and complete transparency, limiting the practical applicability of existing watermarking schemes. In general, an effective multi-bit watermarking system should satisfy several key requirements. It should preserve generation quality, remain robust to common text perturbations, incur minimal decoding latency, and scale efficiently to large online corpora. Beyond these basic properties, we argue that it should also provide sufficient capacity to encode rich metadata and, crucially, enable selective disclosure: a verifier should recover only the information corresponding to its authorization level, without learning any additional embedded data. To this end, we introduce a selective-disclosure watermarking framework based on hierarchical vocabulary partitioning. The framework organizes the vocabulary into a nested tree structure and composes a base watermarking rule recursively. At the top level, the vocabulary is partitioned to embed a coarse message, and the selected subset is then further partitioned to embed deeper payload layers (see Figure 1 for an illustration). This recursive construction creates a dependency chain in which lower-level payloads are statistically concealed within higher layers. As a result, the framework naturally supports hierarchical verification: a standard verifier can decode only the root-level signal (e.g., detection or coarse provenance), while deeper layers appear as noise, whereas privileged verifiers can resolve nested partitions to recover sensitive metadata. We instantiate the framework using Gumbel-based watermarking and evaluate detection accuracy, text quality, robustness under representative perturbations, and computational cost. Our main contributions are as follows: • We propose a framework for selective-disclosure multi-bit watermarking in LLM decoding, enabling hierarchical verification under different authorization levels. • We provide theoretical guarantees on statistical unbiasedness and formalize selective disclosure by showing that unauthorized parties cannot recover payloads beyond random guessing. • We provide an efficient, batching-friendly GPU implementation and extensive experiments demonstrating strong detectability, text quality preservation, robustness to perturbations, and substantially lower generation/decoding latency than publicly released multi-bit watermarking implementations. 2 Related Work LLM watermarking methods can be categorized by when the watermark is embedded. Post-processing watermarking rewrites already-generated text to inject detectable patterns, e.g., via controlled lexical substitutions such as synonym replacement (Yang et al., 2023; Munyer et al., 2024). In this work we focus on inference-time watermarking, which embeds signals by modifying the sampling procedure during generation to correlate token selection with a secret key. Zero-bit Watermarking. A representative zero-bit watermark is the Green-Red List scheme (Kirchenbauer et al., 2023), which partitions the vocabulary into green and red lists and biases sampling toward green tokens. Detection is performed by testing whether the generated text contains an unusually high fraction of green tokens. Though simple, this watermark distorts the model’s output distribution and can degrade generation quality. A subsequent line of work aims to debias this watermark through reweighting (Hu et al., 2024; Wu et al., 2024; Xie et al., 2025). In parallel, Aaronson and Kirchner (2024); Kuditipudi et al. (2024); Dathathri et al. (2024) propose statistically unbiased sampling procedures that provably preserve the model output distribution while still enabling reliable detection. Robust watermarking designs are further studied in (Kuditipudi et al., 2024; Zhao et al., 2024; Li et al., 2026; Qu et al., 2025). Multi-bit Watermarking. Multi-bit watermarking schemes embed metadata into generated text to meet auditing needs that go beyond binary detection. Many multi-bit methods build on the Green-Red List paradigm (Kirchenbauer et al., 2023) by making the vocabulary partition message-dependent, so that different metadata payloads correspond to different preferred token subsets. Early designs (Fernandez et al., 2023; Qu et al., 2025) construct message-specific green lists by cyclically shifting a keyed vocabulary permutation according to the message. Wang et al. (2024) uses a proxy language model to form higher-quality vocabulary partitions, improving text quality at the cost of additional computation and an extra modeling assumption. MPAC (Yoo et al., 2024) introduces a position allocation technique. Instead of encoding the entire payload at every token, it embeds a message subunit at each position so that different parts of the payload accumulate evidence across the text. This position-allocation viewpoint has been widely adopted by subsequent multi-bit methods. StealthInk (Jiang et al., 2025) and BiMark (Feng et al., 2025) design reweighting mechanisms to achieve statistical unbiasedness, aiming to preserve text quality while retaining watermarking capacity. Metadata Access Control and Selective Disclosure. Despite progress on generation quality, robustness, and payload capacity, granular access control in LLM watermarking has received comparatively little attention. Most existing schemes implicitly assume an all-or-nothing credential model: a verifier either can decode the watermark and recover the full payload or cannot decode anything at all. The closest related direction is designated-detector watermarking (Huang et al., 2024), where cryptographic techniques restrict who can detect the presence of a watermark. Unlike designated-detector watermarking, which controls who can detect a watermark, our goal is selective disclosure: different keys reveal different subsets of the embedded metadata from the same text. To our knowledge, no existing LLM watermarking method provides role-based partial verification of embedded metadata within the same text. Our work formalizes this selective-disclosure requirement and proposes a mechanism that enables hierarchical verification: low-privilege verifiers can validate or decode only coarse information, while deeper payload layers remain statistically concealed without the corresponding authorization. 3 Preliminaries Language Modeling Fundamentals. A language model ℳM is an autoregressive probabilistic model defined over a discrete vocabulary V of size V=||V=|V|. At each generation step, the model predicts the next token based on all preceding tokens. Given a prefix sequence x<t=(x1,…,xt−1)x_<t=(x_1,…,x_t-1), the model produces a logit vector lt∈ℝVl_t ^V at step t. The next-token prediction (NTP) distribution Pℳ(⋅∣x<t)P_M(· x_<t) is obtained by applying the softmax function to these logits: Pℳ(xt=v∣x<t)=exp((lt)v)∑j=1Vexp((lt)j).P_M(x_t=v x_<t)= ((l_t)_v) _j=1^V ((l_t)_j). (1) In standard generation, the next token xtx_t is sampled from this NTP distribution: xt∼Pℳ(⋅∣x<t)x_t P_M(· x_<t). Watermarking via Modified Sampling. Watermarking embeds a discrete payload m (or a metadata message) into generated text by modifying only the token sampling process, while keeping the underlying NTP distribution unchanged. At each generation step t, a pseudo-random function (PRF) A (Goldreich et al., 1986) maps a local context window of size h, xt−h:t−1=(xt−h,…,xt−1)x_t-h:t-1=(x_t-h,…,x_t-1), together with a secret key ξ, to a pseudorandom vector ζt=(xt−h:t−1,ξ)∈ℝV _t=A(x_t-h:t-1,ξ) ^V. The next token is generated by a (deterministic) sampling function S: xt=(Pℳ(⋅∣x<t),ζt).x_t=S(P_M(· x_<t), _t). (2) Multi-bit Payloads and Position Allocation. In multi-bit watermarking, the payload m is represented as a sequence of message segments m=(m1,…,mK)m=(m_1,…,m_K). Following the position-allocation strategy of MPAC (Yoo et al., 2024), a rule p(t)∈1,…,Kp(t)∈\1,…,K\ specifies which segment is embedded at generation step t, so that token xtx_t encodes only the single segment mp(t)m_p(t) rather than the full payload m. For example, if the total payload has 24 bits and each allocated position carries 2 bits, then the payload is divided into K=12K=12 segments, and the position-allocation rule assigns these segments to generation steps. During detection, the detector applies a function m^=(x,ξ) m=D(x,ξ) to recover the embedded payload from a generated x. Definition 3.1 (Statistical Unbiasedness). A watermarking scheme is statistically unbiased if, conditioned on any prefix x<tx_<t, the marginal distribution of each generated token v∈v equals the original NTP distribution: ℙζt((Pℳ(⋅∣x<t),ζt,m)=v)=Pℳ(xt=v∣x<t),P_ _t\! (S(P_M(· x_<t), _t,m)=v )=P_M(x_t=v x_<t), where the probability is taken over the randomness induced by the secret key. Statistical Unbiasedness. We require the watermarking scheme to be statistically unbiased (see Definition 3.1), so that watermarking preserves the model’s NTP distribution and does not degrade generation quality. A canonical example of an unbiased sampling rule is Gumbel-Max sampling in Definition 3.2. We use it as a convenient sampling rule to illustrate our framework. Definition 3.2 (Gumbel-Max Sampling). The pseudorandom variable ζt _t is defined as ζt=(Ut,v)v∈ _t=(U_t,v)_v , where Ut,v∼i.i.d.Uniform(0,1)U_t,v i.i.d. Uniform(0,1). This construction assigns independent uniform randomness to each candidate token. The next token is selected as xt=argmaxv∈(lt)v−log(−log(Ut,v)).x_t= _v (l_t)_v- (- (U_t,v)). 4 Methodology Figure 1: Hierarchical vocabulary routing on a toy vocabulary of size V=16V=16 with a chunking schedule K=(K1)=(4)K=(K_1)=(4). At stage ℓ=1 =1, the current candidate set (blue) is partitioned into K1=4K_1=4 contiguous chunks (dotted connectors). Using the level-1 key table ξ(1)ξ^(1) and message m(1)m^(1), the sampler draws a chunk (solid arrows) and restricts the candidate set to the selected chunk (green). After the routing stage, the final token (black) is sampled from the remaining candidates using key table ξ(2)ξ^(2) and message m(2)m^(2). Overview. In this section, we introduce our watermarking method. The key idea is to embed information by guiding the token sampling process through a hierarchical partition of the vocabulary. Starting from the full vocabulary, we progressively refine the partition and select a smaller subset of candidate tokens at each stage. The choice of which subset to refine is controlled by pseudorandomness derived from a secret key and is tied to a specific segment of the payload. By repeating this process across multiple layers, the method embeds a multi-bit message while preserving the original sampling distribution. A Two-Layer Example. Figure 1 illustrates the procedure using a two-layer construction. Consider a two-level payload (m(1),m(2))(m^(1),m^(2)). At the first layer, the vocabulary is partitioned into K1=4K_1=4 disjoint chunks, each assigned an aggregated probability equal to the sum of the original next-token probabilities of the tokens it contains. Equivalently, each chunk can be viewed as a “meta-token,” and a sampling step is performed over these chunks according to their aggregated probabilities. The pseudorandomness used in this step is obtained from the entry corresponding to m(1)m^(1) in the first key table (1) ξ^(1), i.e., (1)(m(1)) ξ^(1)(m^(1)). Once a chunk is selected, the same procedure is applied recursively within the selected chunk to embed m(2)m^(2): the chunk is further partitioned, aggregated probabilities are computed, and sampling is performed again using pseudorandomness (2)(m(2)) ξ^(2)(m^(2)) determined by the next message segment. Because each selection step samples according to the appropriate (aggregated or conditional) probability distribution, the overall procedure remains statistically unbiased, and the final sampled token follows the original NTP distribution. 4.1 General L-Layer Generation Algorithm 1 Generation via HeRo at step t 0: Payload (m(1),…,m(L))(m^(1),…,m^(L)), NTP distribution Pt(⋅)=Pℳ(⋅∣x<t)P_t(·)=P_M(· x_<t), context window x(t−h):(t−1)x_(t-h):(t-1), sampling function S, PRF A, key tables (ℓ)ℓ=1L\ ξ^( )\_ =1^L, chunking schedule (K1,…,KL−1)(K_1,…,K_L-1) 0: Sampled token xtx_t 1: Offset o←0o← 0 and current chunk size v←Vv← V 2: for ℓ=1 =1 to L−1L-1 do 3: Partition [o,o+v)=∪i=1Kℓi(ℓ)[o,o+v)= _i=1^K_ C^( )_i into KℓK_ contiguous chunks 4: wi(ℓ)←∑x∈i(ℓ)Pt(x)w_i^( )← _x ^( )_iP_t(x) for i=1,…,Kℓi=1,…,K_ 5: Normalize (w1(ℓ),…,wKℓ(ℓ))(w_1^( ),…,w_K_ ^( )) to obtain a probability distribution over the KℓK_ chunks 6: Identify the secret key ξ←(ℓ)(m(ℓ))ξ← ξ^( )(m^( )) 7: Get pseudorandom vector ζt(ℓ)←(x(t−h):(t−1),ξ)ζ^( )_t (x_(t-h):(t-1),ξ) 8: Sample the next chunk st,ℓ←((wi(ℓ))i=1Kℓ,ζt(ℓ))s_t, ((w_i^( ))_i=1^K_ ,ζ^( )_t) 9: Update offset o and chunk size v according to the selected chunk st,ℓ(ℓ)C^( )_s_t, 10: end for 11: Identify the secret key ξ←(L)(m(L))ξ← ξ^(L)(m^(L)) 12: Get pseudorandom ζt(L)←(x(t−h):(t−1),ξ)ζ^(L)_t (x_(t-h):(t-1),ξ) 13: Sample index st,L←(Pt|[o,o+v),ζt(L))s_t,L (P_t|_[o,o+v),ζ^(L)_t) 14: return xt←o+st,Lx_t← o+s_t,L Now, we describe how to embed an L-level payload into generated text using hierarchical vocabulary routing. The routing structure is specified by a chunking schedule K=(K1,…,KL−1)K=(K_1,…,K_L-1), where KℓK_ denotes the number of partitions (chunks) at routing stage ℓ . The sampler starts from the full vocabulary (0)=C^(0)=V and proceeds through L sequential stages, repeatedly refining the candidate set until a single token is selected. Earlier stages make coarse routing decisions over large vocabulary regions, while later stages refine the decision within the selected region; each routing decision carries one level of payload information. The full procedure is summarized in Algorithm 1. Stages ℓ=1,…,L−1 =1,…,L-1 (Chunk Routing). At routing stage ℓ , the current candidate chunk (ℓ−1)C^( -1) is partitioned into KℓK_ contiguous chunks (line 3 in Algorithm 1) (1(ℓ),2(ℓ),…,Kℓ(ℓ))=Partition((ℓ−1)),(C^( )_1,C^( )_2,…,C^( )_K_ )=Partition(C^( -1)), with sizes differing by at most one.111Suppose v,k∈ℕ+v,k ^+ and v=ak+rv=ak+r, where 0≤r<k0≤ r<k, we have v=a(k−r)+(a+1)rv=a(k-r)+(a+1)r. This means we can always partition a large chunk into small chunks with max difference size one: k−rk-r chunks with size a and r chunks with size a+1a+1. We then coarse-grain the token distribution by aggregating probabilities within each chunk, which yields a categorical distribution over the KℓK_ chunks (line 4–5). Using the pseudorandom variable ζ(ℓ)ζ^( ) associated with the payload component m(ℓ)m^( ), we apply the sampling function S to select a chunk (ℓ)=sℓ(ℓ)C^( )=C^( )_s_ and restrict the candidate set to the selected chunk (line 8). Stage ℓ=L =L (Final Token Sampling). After L−1L-1 routing decisions, we obtain a final candidate chunk (L−1)C^(L-1). We treat each token in this chunk as a separate category and sample the final token xtx_t from the newly normalized distribution restricted to this subset, guided by the last-level payload m(L)m^(L). Each generated token induces a nested path of vocabulary subsets: =(0)⊃(1)⊃⋯⊃(L−1)⊃(L)=xt,V=C^(0) ^(1)⊃… ^(L-1) ^(L)=\x_t\, where the routing decision at stage ℓ is controlled by the level-ℓ message component. The following theorem formalizes that this hierarchical sampling procedure preserves the original NTP distribution. Theorem 4.1 (Statistical Unbiasedness). The hierarchical routing sampler is statistically unbiased: the final sampled token xtx_t follows the original NTP distribution. 4.2 Decoding Multi-Level Payload Algorithm 2 Message Decoding via HeRo 0: Generated sequence x=(x1,…,xT)x=(x_1,…,x_T), vocabulary size V, context window size h, PRF A, evidence function EvEv, key tables (ℓ)ℓ=1L\ ξ^( )\_ =1^L, chunking schedule (K1,…,KL−1)(K_1,…,K_L-1) 0: Decoded payload (m^(1),…,m^(L))( m^(1),…, m^(L)) 1: Stage 1: per-token evidence 2: for t=h+1t=h+1 to T do 3: Recover the chunk-index path (st,1,…,st,L)(s_t,1,…,s_t,L) from xtx_t 4: for ℓ=1 =1 to L do 5: for a=0a=0 to 2bℓ−12^b_ -1 do 6: ζt(ℓ)(a)←(x(t−h):(t−1),(ℓ)(a))ζ^( )_t(a) \! (x_(t-h):(t-1),\, ξ^( )(a) ) 7: Et(ℓ)(a)←Ev(ζt(ℓ)(a),st,ℓ)E^( )_t(a) \! (ζ^( )_t(a),\,s_t, ) 8: end for 9: end for 10: end for 11: Stage 2: aggregate evidence and decode each level 12: for ℓ=1 =1 to L do 13: Decode m^(ℓ) m^( ) from the per-token evidences Et(ℓ)(a)t,a\E^( )_t(a)\_t,a 14: end for 15: return (m^(1),…,m^(L))( m^(1),…, m^(L)) The decoding procedure follows the reverse logic of generation (Algorithm 2). Given a generated sequence x=(x1,…,xT)x=(x_1,…,x_T), the decoder processes each token position independently and infers, from the token identity alone, the hierarchical routing decisions made during generation. Concretely, the deterministic partition rule maps each token xtx_t to a unique sequence of routing indices st,ℓ=1L\s_t, \_ =1^L. For ℓ=1,…,L−1 =1,…,L-1, the index st,ℓ∈1,…,Kℓs_t, ∈\1,…,K_ \ records the selected chunk at routing stage ℓ . At the final stage, we equivalently treat each token in the last selected chunk as a singleton chunk, so st,Ls_t,L again denotes a chunk index. This sequence serves as the observable footprint of the hierarchical routing process. We now describe the decoding procedure more formally. Fix a level ℓ , a party with access to the level-ℓ key table (ℓ) ξ^( ) computes the pseudorandom variable for each candidate message value a∈0,…,2bℓ−1a∈\0,…,2^b_ -1\ as ζt(ℓ)(a)=(x(t−h):(t−1),(ℓ)(a)).ζ^( )_t(a)=A\! (x_(t-h):(t-1),\, ξ^( )(a) ). The decoder then combines ζt(ℓ)(a)ζ^( )_t(a) with the observed chunk index st,ℓs_t, to form a per-token evidence value Et(ℓ)(a)=Ev(ζt(ℓ)(a),st,ℓ).E^( )_t(a)=Ev\! (ζ^( )_t(a),\,s_t, ). The evidence function EvEv is designed so that for an incorrect candidate a≠m(ℓ)a≠ m^( ), Et(ℓ)(a)E^( )_t(a) follows a known null distribution, while the true message produces stochastically larger evidence. Aggregating the evidence across token positions (e.g., by summation) yields a score for each candidate message, and the decoded payload at level ℓ is given by m^(ℓ)=argmaxa∈0,…,2bℓ−1Agg(Et(ℓ)(a)). m^( )= _a∈\0,…,2^b_ -1\Agg (\E^( )_t(a)\ ). Example 1. As a concrete example, we use Gumbel-Max sampling as the sampling rule S in this work. For routing stages ℓ<L <L, the pseudorandom variable ζt(ℓ)(a)=(Ut,i)i=1Kℓζ^( )_t(a)=(U_t,i)_i=1^K_ consists of KℓK_ i.i.d. Uniform(0,1)Uniform(0,1) random variables, which are used to sample the next chunk from the partition (1(ℓ),2(ℓ),…,Kℓ(ℓ))(C^( )_1,C^( )_2,…,C^( )_K_ ). At the final stage ℓ=L =L, the same construction applies to the last selected chunk. The evidence function is the Aaronson score used for detection (Aaronson and Kirchner, 2024): Ev(ζ,s)=−log(1−ζ(s)),Ev(ζ,s)=- \! (1-ζ(s) ), where ζ(s)ζ(s) denotes the s-th entry of the vector ζ. Finally, we simply set Agg(Et(ℓ)(a))=∑tEt(ℓ)(a)Agg (\E^( )_t(a)\ )= _tE^( )_t(a). Without access to the level-ℓ key table (ℓ) ξ^( ), a verifier cannot reproduce the pseudorandom variables corresponding to the true message value m(ℓ)m^( ). As a result, the per-token evidence Et(ℓ)(a)a\E^( )_t(a)\_a is statistically indistinguishable across candidate messages, and decoding at level ℓ reduces to random guessing. The following theorem formalizes this selective disclosure property. Theorem 4.2 (Selective Disclosure). Fix a disclosure level k∈1,…,Lk∈\1,…,L\. Consider a verifier that possesses only the key tables (1),…,(k) ξ^(1),…, ξ^(k). Then, for any ℓ>k >k, the verifier cannot decode m(ℓ)m^( ) beyond random guessing. 4.3 Computational Complexity Analysis We analyze the computational cost of generation and decoding for a single generation step t. Throughout, we assume that Gumbel-Max sampling is used at all routing stages. Generation. At step t, each routing stage ℓ∈1,…,L−1 ∈\1,…,L-1\ partitions the current candidate set into KℓK_ contiguous chunks and computes their probability masses pii=1Kℓ\p_i\_i=1^K_ . This can be implemented efficiently by first computing the prefix-sum (CDF) Ft(u)=∑v≤uPt(v)F_t(u)= _v≤ uP_t(v) in O(V)O(V) time. Each chunk mass can then be obtained using two CDF queries, yielding an O(Kℓ)O(K_ ) cost per stage. Under Gumbel-Max sampling, drawing a chunk index from a KℓK_ -way categorical distribution also takes O(Kℓ)O(K_ ) time. After L−1L-1 routing stages, the remaining candidate set has size approximately V/∏ℓ=1L−1KℓV/ _ =1^L-1K_ , and sampling the final token costs O(V/∏ℓ=1L−1Kℓ)O\! (V/ _ =1^L-1K_ ). Overall, the per-step generation complexity is O(V+∑ℓ=1L−1Kℓ+V/∏ℓ=1L−1Kℓ)=O(V)O (V+ _ =1^L-1K_ +V/ _ =1^L-1K_ )=O(V). In practice, we implement generation in a batched manner to improve wall-clock throughput. The additional overhead introduced by watermarking is negligible compared to the model forward pass, since our complexity depends only on the vocabulary size, which remains essentially constant across scales within each model family (see Table D.1 in Appendix D.1). Decoding. Decoding operates solely on the generated text and the key tables. At each level ℓ , the decoder evaluates 2bℓ2^b_ candidate message values. Under Gumbel-Max sampling, the evidence function Ev(ζ,s)Ev(ζ,s) can be computed without reconstructing the full pseudorandom vector ζ, as it requires only the random variate ζs _s associated with the observed token index s. By using a counter-based pseudorandom number generator (Salmon et al., 2011), this computation takes O(1)O(1) time and O(1)O(1) memory per candidate. As a result, the total per-step decoding complexity is O(∑ℓ=1L2bℓ).O\! ( _ =1^L2^b_ ). 5 Experiments Considered Watermarks. We evaluate the Hierarchical Vocabulary Routing framework instantiated with Gumbel-Max sampling. We consider both single-level and two-level hierarchical payload configurations in the main text. The two-level configuration enables selective disclosure by separating public verification (first level) from private auditing (second level) using different secret keys. The single-level configuration does not provide hierarchical access control and therefore serves as an internal baseline. We additionally compare against prior multi-bit watermarking methods, including MPAC (Yoo et al., 2024), StealthInk (Jiang et al., 2025), and BiMark (Feng et al., 2025). We further investigate deeper hierarchies (up to 8 levels) and report the results in Appendix E.3. Models and Datasets. We conduct experiments using Llama2-7B (Touvron et al., 2023). For text generation, we use the C4 realnewslike dataset (Raffel et al., 2020), which contains formal journalistic content, and the OpenGen dataset (Krishna et al., 2023), which covers conversational and creative text. From each dataset, we sample 1,000 documents and truncate a fixed number of initial tokens to form generation prompts. We report results on C4 in the main text, with additional results on OpenGen provided in Appendix E.1 and Appendix E.2. Evaluation Metrics. We evaluate watermarking schemes along five dimensions. Selective disclosure is assessed by comparing decoding outcomes across authorization levels. Detectability is measured by bit-level message decoding accuracy. Text quality is quantified using perplexity (PPL). Efficiency is reported as wall-clock generation and decoding time. Robustness is evaluated by decoding accuracy under random replacement and roundtrip translation. 5.1 Selective Disclosure Evaluation To evaluate selective disclosure, we consider two-level hierarchical payloads, where the first level is treated as public and the second as private. This setting induces two verifier capabilities: (i) Full authorization: the verifier holds secret keys for both levels and can decode both payloads and (i) Public-only authorization: the verifier holds only the public secret key and can decode the public payload, while private payload decoding is no better than random guessing. Figure 2: Bit accuracy as a function of the number of first-layer chunks K1K_1: public payload accuracy (solid), private payload accuracy for fully authorized verifiers (dashed) and private payload accuracy under public-only authorization (dotted). We fix the total payload size at 24 bits and compare three per-level allocations: (1,1)(1,1), (2,1)(2,1), and (2,2)(2,2). Figure 2 illustrates a clear trade-off between public and private decoding accuracy for the fully authorized verifier. As the number of public chunks K1K_1 increases, more signal is allocated to the public level, leading to improved and eventually saturated public decoding accuracy. Conversely, private decoding accuracy decreases as less signal remains available for the private level. This trade-off is best balanced at K1=20K_1=20, which we adopt in subsequent experiments. Finally, we verify the selective-disclosure guarantee by showing that a public-only verifier achieves approximately chance-level accuracy (≈50%≈ 50\%) on the private payload across all settings (see dotted line in Figure 2), consistent with Theorem 4.2. 5.2 Detectability and Text Quality Detection Accuracy. Table 1: Comparison of bit accuracy (B.Acc.↑ ) and median perplexity (PPL) for Llama2-7B generations on C4 across payload sizes (12, 24, 36, and 48 bits). Results are computed over 200 generated tokens. MPAC is parameterized by (b,δ)(b,δ), where δ denotes the bias added to green-token logits; StealthInk by (b)(b); BiMark by (d)(d), where d is the number of probability reweighting steps; and our method by HeRoL(b1,…,bL)HeRo^L(b_1,…,b_L) with bℓb_ bits of payload allocated at level ℓ . Watermark S.D. 12 Bits 24 Bits 36 Bits 48 Bits B.Acc.↑ PPL B.Acc.↑ PPL B.Acc.↑ PPL B.Acc.↑ PPL w/o — — 4.31 — 4.31 — 4.31 — 4.31 MPAC (1, 2.0) — 0.954 4.69 0.876 4.71 0.840 4.69 0.800 4.64 MPAC (2, 2.0) — 0.959 4.78 0.882 4.76 0.835 4.75 0.802 4.75 StealthInk (1) — 0.934 4.36 0.845 4.33 0.805 4.32 0.769 4.32 StealthInk (2) — 0.843 4.27 0.748 4.31 0.731 4.33 0.687 4.37 BiMark (5) — 0.866 4.31 0.767 4.28 0.731 4.26 0.702 4.33 BiMark (10) — 0.914 4.25 0.827 4.32 0.788 4.30 0.746 4.31 BiMark (20) — 0.961 4.21 0.894 4.32 0.852 4.29 0.812 4.26 HeRo1 (2) — 0.993 4.32 0.966 4.28 0.933 4.31 0.901 4.33 HeRo1 (3) — 0.997 4.31 0.981 4.33 0.953 4.29 0.919 4.32 HeRo2 (1,1) ✓ 0.950 4.31 0.880 4.31 0.831 4.32 0.798 4.33 HeRo2 (2,1) ✓ 0.970 4.30 0.904 4.28 0.856 4.27 0.823 4.32 HeRo2 (2,2) ✓ 0.975 4.30 0.925 4.36 0.873 4.30 0.833 4.28 We evaluate detection accuracy across watermarking methods. Our method is denoted by HeRo, with HeRo1(b1)HeRo^1(b_1) and HeRo2(b1,b2)HeRo^2(b_1,b_2) representing single-level and two-level configurations, respectively. Table 1 reports bit-level decoding accuracy under a fixed generation budget of 200 tokens for total payload sizes m∈12,24,36,48m∈\12,24,36,48\. Across all payload sizes, our method consistently achieves stronger detectability than MPAC, StealthInk, and BiMark. In particular, the single-level configuration HeRo1HeRo^1 achieves near-perfect decoding at moderate payload sizes (24 and 36 bits) and remains highly accurate even at 48 bits. The two-level configuration HeRo2HeRo^2 exhibits a modest accuracy reduction relative to HeRo1HeRo^1, while still matching or outperforming prior multi-bit baselines at the same total payload size. Importantly, HeRo2HeRo^2 additionally supports selective disclosure (Section 5.1) while maintaining strong detectability. Figure 3 further shows that decoding accuracy improves with longer generations for all methods, and that our method achieves higher accuracy with fewer generated tokens. Figure 3: Comparison of bit accuracy for multi-bit watermarking methods as a function of token budget when embedding a 24-bit payload. Text Quality Preservation. Figure 4: Violin plots of perplexity (PPL) for Llama2-7B generations on C4, comparing multi-bit watermarking methods with the unwatermarked baseline (w/o). Results are computed over 200 generated tokens. Figure 4 visualizes the PPL distributions. The distribution under our method closely overlaps with the unwatermarked baseline, whereas MPAC exhibits a noticeable shift toward higher perplexity values, implying a large quality degradation. 5.3 Computational Efficiency We measure wall-clock latency for both watermark embedding during generation and message decoding. We benchmark our implementation against publicly released codebases for MPAC and BiMark. Figure 5: Generation latency under batched inference for Llama2-7B generations on C4 with a 24-bit payload. Top: per-token generation latency (ms/token). Bottom: relative overhead over the non-watermarked baseline (w/o). Batch size denotes the number of prompts processed concurrently. Generation Latency. Real-world LLM services typically process multiple requests concurrently and rely on batching to improve GPU utilization and amortize overhead. We generate 1,000 continuations with a 24-bit embedded payload, and vary the generation batch size in 1,4,16,32,64\1,4,16,32,64\. For each method, we report per-token generation latency, computed as total elapsed generation time divided by the number of generated tokens. Figure 5 summarizes the results of generation latency. The top panel reports absolute per-token latency (ms/token), while the bottom panel shows relative overhead compared to the baseline. Our implementation naturally supports batched inference and incurs only a small and stable overhead (approximately 4–5%) over the non-watermarked baseline across all batch sizes, with a mild decreasing trend as batch size increases. In contrast, MPAC and BiMark exhibit substantial overhead across all batch sizes, and their overhead does not diminish with batching, reflecting limited batching support in the released implementations. Message Decoding Latency. Fast decoding is important for large-scale auditing settings, where messages must be recovered from large text corpora. During message decoding, the embedded payload m is recovered from the generated text. We measure wall-clock decoding time and report average latency in μs/token /token over approximately 400,000 tokens using Llama2-7B tokenizer. Table 2 shows decoding latency as a function of the number of texts processed per batch. Our decoding procedure is compatible with standard batched execution and achieves substantially lower decoding latency than the baselines, with additional speedups as batch size increases. In contrast, the publicly released implementations of MPAC and BiMark perform decoding on a per-text basis and are CPU-based. We thus invoke their decoding procedures independently for each example in the batch, which does not yield meaningful speedups as batch size increases. Table 2: Decoding latency (μs/token /token) using Llama2-7B tokenizer. Values are averaged over approximately 400,000 tokens. Watermark Batch Size 1 4 16 32 64 MPAC (2, 2.0) 488.13 479.30 491.43 489.15 480.43 BiMark (20) 130.43 130.22 130.68 131.63 133.23 HeRo1 (3) 7.75 2.43 1.66 1.57 1.44 HeRo2 (2,2) 10.34 3.08 1.85 1.59 1.48 5.4 Robustness Analysis Table 3: Bit accuracy (B.Acc.↑ ) under attacks on C4 using Llama2-7B with a 24-bit payload and 200 generated tokens. REP: random replacement; INS: random insertion; DEL: random deletion; RT: roundtrip translation; DIPPER: paraphrasing attacks with controllable lexical and order diversity. Watermark REP INS DEL RT DIPPER 0.05 0.1 0.2 0.05 0.1 0.2 0.05 0.1 0.2 (20,0) (0,20) (20,20) MPAC (2, 2.0) 0.809 0.739 0.622 0.814 0.754 0.648 0.827 0.766 0.663 0.650 0.669 0.794 0.646 StealthInk (2) 0.677 0.620 0.552 0.684 0.630 0.559 0.690 0.643 0.575 0.569 0.582 0.665 0.573 BiMark (20) 0.833 0.768 0.658 0.838 0.778 0.677 0.845 0.793 0.692 0.687 0.703 0.817 0.691 HeRo1 (3) 0.949 0.898 0.752 0.952 0.906 0.782 0.958 0.920 0.798 0.780 0.800 0.931 0.778 HeRo2 (2,2) 0.871 0.800 0.677 0.868 0.809 0.707 0.879 0.825 0.710 0.707 0.723 0.848 0.701 We evaluate robustness under a wide range of perturbation strategies. For random replacement (REP), random insertion (INS), and random deletion (DEL), a fraction p∈0.05,0.1,0.2p∈\0.05,0.1,0.2\ of tokens are randomly substituted, inserted, or deleted, respectively, where larger values correspond to more aggressive corruption. Roundtrip translation (RT) translates the watermarked text from English to French and back using OPUS-MT models (Tiedemann and Thottingal, 2020). We also evaluate paraphrasing attacks via DIPPER (Krishna et al., 2023) under three configurations of lexical diversity and order diversity: (20,0),(0,20),(20,20)(20,0),\,(0,20),\,(20,20), where the two parameters control the degree of lexical substitution and sentence reordering, respectively. Table 3 reports bit accuracy under perturbation strategies for a 24-bit payload. For random replacement (REP), insertion (INS), and deletion (DEL), decoding accuracy consistently decreases as the corruption rate p increases. Roundtrip translation (RT) produces degradation comparable to the strongest random perturbation setting (p=0.2p=0.2). Under DIPPER paraphrasing, accuracy degrades as lexical and order diversity increases. Across all perturbation settings, our framework consistently achieves the highest decoding accuracy among the evaluated methods, indicating stronger preservation of recoverable watermark signals under text corruption. 6 Discussion This work introduces a hierarchical watermarking framework for selective metadata disclosure in LLM-generated text. We provide theoretical guarantees for selective disclosure and evaluate the framework under both single-level and multi-level payload configurations. Our experiments demonstrate strong selective disclosure performance, robustness to common text perturbations, and favorable detectability-quality trade-offs. Moreover, under a fixed generation budget, we observe an inherent trade-off between selective disclosure and detectability. Formally characterizing this trade-off and identifying its fundamental limits remain open problems, which we leave for future work. Acknowledgements We thank Weijie Su for helpful discussions and valuable feedback on this work. References S. Aaronson and H. Kirchner (2024) Watermarking gpt outputs, 2023. URL https://scottaaronson. blog. Cited by: §1, §2, Example 1. S. Agarwal, L. Ahmad, J. Ai, S. Altman, A. Applebaum, E. Arbus, R. K. Arora, Y. Bai, B. Baker, H. Bao, et al. (2025) gpt-oss-120b & gpt-oss-20b model card. arXiv preprint arXiv:2508.10925. Cited by: §D.1. R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill, et al. (2021) On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258. Cited by: §1. California State Legislature (2024) SB 942: California AI transparency act. Note: https://leginfo.legislature.ca.gov/faces/billNavClient.xhtml?bill_id=202320240SB942Approved September 19, 2024; Chapter 291, Statutes of 2024 Cited by: §1, §1. S. Dathathri, A. See, S. Ghaisas, P. Huang, R. McAdam, J. Welbl, V. Bachani, A. Kaskasoli, R. Stanforth, T. Matejovicova, et al. (2024) Scalable watermarking for identifying large language model outputs. Nature 634 (8035), p. 818–823. Cited by: §1, §2. X. Feng, H. Zhang, Y. Zhang, L. Y. Zhang, and S. Pan (2025) BiMark: unbiased multilayer watermarking for large language models. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §1, §2, §5. P. Fernandez, A. Chaffin, K. Tit, V. Chappelier, and T. Furon (2023) Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), p. 1–6. Cited by: §1, §2. Z. Fu, W. Lam, A. M. So, and B. Shi (2021) A theoretical analysis of the repetition problem in text generation. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, p. 12848–12856. Cited by: Appendix D. O. Goldreich, S. Goldwasser, and S. Micali (1986) How to construct random functions. Journal of the ACM (JACM) 33 (4), p. 792–807. Cited by: §3. Z. Hu, L. Chen, X. Wu, Y. Wu, H. Zhang, and H. Huang (2024) Unbiased watermark for large language models. In The Twelfth International Conference on Learning Representations, Cited by: Appendix D, §2. Y. Huang and L. Sun (2023) FakeGPT: fake news generation, explanation and detection of large language models. arXiv preprint arXiv:2310.05046. Cited by: §1. Z. Huang, G. Zeng, X. Mu, Y. Wang, and Y. Yu (2024) Multi-designated detector watermarking for language models. arXiv preprint arXiv:2409.17518. Cited by: §2. Y. Jiang, C. Wu, M. K. Boroujeny, B. Mark, and K. Zeng (2025) StealthInk: a multi-bit and stealthy watermark for large language models. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: Appendix D, §1, §2, §5. J. Kirchenbauer, J. Geiping, Y. Wen, J. Katz, I. Miers, and T. Goldstein (2023) A watermark for large language models. In Proceedings of the 40th International Conference on Machine Learning, p. 17061–17084. Cited by: §1, §2, §2. K. Krishna, Y. Song, M. Karpinska, J. Wieting, and M. Iyyer (2023) Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense. Advances in Neural Information Processing Systems 36, p. 27469–27500. Cited by: §5, §5.4. R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang (2024) Robust distortion-free watermarks for language models. Transactions on Machine Learning Research. Note: External Links: ISSN 2835-8856, Link Cited by: §2. W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. Gonzalez, H. Zhang, and I. Stoica (2023) Efficient memory management for large language model serving with PagedAttention. In Proceedings of the 29th ACM Symposium on Operating Systems Principles, p. 611–626. Cited by: §D.2. J. Laux, S. Wachter, and B. Mittelstadt (2024) Trustworthy artificial intelligence and the European Union AI act: On the conflation of trustworthiness and acceptability of risk. Regulation & Governance 18 (1), p. 3–32. Cited by: §1. X. Li, F. Ruan, H. Wang, Q. Long, and W. J. Su (2026) Robust detection of watermarks for large language models under human edits. Journal of the Royal Statistical Society Series B: Statistical Methodology 88 (2), p. 491–515. External Links: ISSN 1369-7412, Document, Link, https://academic.oup.com/jrsssb/article-pdf/88/2/491/64342452/qkaf056.pdf Cited by: §2. E. Mitchell, Y. Lee, A. Khazatsky, C. D. Manning, and C. Finn (2023) DetectGPT: zero-shot machine-generated text detection using probability curvature. In Proceedings of the 40th International Conference on Machine Learning, ICML’23. Cited by: §1. T. Munyer, A. A. Tanvir, A. Das, and X. Zhong (2024) DeepTextMark: a deep learning-driven text watermarking approach for identifying large language model generated text. IEEE Access 12, p. 40508–40520. Cited by: §2. W. Qu, W. Zheng, T. Tao, D. Yin, Y. Jiang, Z. Tian, W. Zou, J. Jia, and J. Zhang (2025) Provably robust multi-bit watermarking for AI-generated text. In 34th USENIX Security Symposium (USENIX Security 25), p. 201–220. Cited by: §2, §2. C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y. Zhou, W. Li, and P. J. Liu (2020) Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res. 21 (1). External Links: ISSN 1532-4435 Cited by: §5. P. Ranade, A. Piplai, S. Mittal, A. Joshi, and T. Finin (2021) Generating fake cyber threat intelligence using transformer-based models. In 2021 International Joint Conference on Neural Networks (IJCNN), p. 1–9. Cited by: §1. J. K. Salmon, M. A. Moraes, R. O. Dror, and D. E. Shaw (2011) Parallel random numbers: as easy as 1, 2, 3. In Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, p. 1–12. Cited by: §4.3. The European Parliament and the Council of the European Union (2024) Regulation (EU) 2024/1689 of the European Parliament and of the Council of 13 June 2024 Laying Down Harmonised Rules on Artificial Intelligence (Artificial Intelligence Act). Note: https://eur-lex.europa.eu/eli/reg/2024/1689/oj/eng Cited by: §1, §1. J. Tiedemann and S. Thottingal (2020) OPUS-MT – building open translation services for the world. In Proceedings of the 22nd Annual Conference of the European Association for Machine Translation, A. Martins, H. Moniz, S. Fumega, B. Martins, F. Batista, L. Coheur, C. Parra, I. Trancoso, M. Turchi, A. Bisazza, J. Moorkens, A. Guerberof, M. Nurminen, L. Marg, and M. L. Forcada (Eds.), Lisboa, Portugal, p. 479–480. External Links: Link Cited by: §5.4. H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, et al. (2023) Llama 2: open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288. Cited by: §D.1, §5. L. Wang, W. Yang, D. Chen, H. Zhou, Y. Lin, F. Meng, J. Zhou, and X. Sun (2024) Towards codable watermarking for injecting multi-bits information to LLMs. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1, §2. D. Weber-Wulff, A. Anohina-Naumeca, S. Bjelobaba, T. Foltỳnek, J. Guerrero-Dib, O. Popoola, P. Šigut, and L. Waddington (2023) Testing of detection tools for AI-generated text. International Journal for Educational Integrity 19 (1), p. 1–39. Cited by: §1. L. Weidinger, J. Mellor, M. Rauh, C. Griffin, J. Uesato, P. Huang, M. Cheng, M. Glaese, B. Balle, A. Kasirzadeh, et al. (2021) Ethical and social risks of harm from language models. arXiv preprint arXiv:2112.04359. Cited by: §1. Y. Wu, Z. Hu, J. Guo, H. Zhang, and H. Huang (2024) A resilient and accessible distribution-preserving watermark for large language models. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. Cited by: §2. Y. Xie, X. Li, T. Mallick, W. Su, and R. Zhang (2025) Debiasing watermarks for large language models via maximal coupling. Journal of the American Statistical Association 120 (551), p. 1424–1436. Cited by: §2. J. Xu, X. Liu, J. Yan, D. Cai, H. Li, and J. Li (2022) Learning to break the loop: analyzing and mitigating repetitions for neural text generation. Advances in Neural Information Processing Systems 35, p. 3082–3095. Cited by: Appendix D. A. Yang, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Li, D. Liu, F. Huang, H. Wei, H. Lin, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Lin, K. Dang, K. Lu, K. Bao, K. Yang, L. Yu, M. Li, M. Xue, P. Zhang, Q. Zhu, R. Men, R. Lin, T. Li, T. Xia, X. Ren, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Wan, Y. Liu, Z. Cui, Z. Zhang, and Z. Qiu (2024) Qwen2.5 technical report. arXiv preprint arXiv:2412.15115. Cited by: §D.1. X. Yang, K. Chen, W. Zhang, C. Liu, Y. Qi, J. Zhang, H. Fang, and N. Yu (2023) Watermarking text generated by black-box language models. arXiv preprint arXiv:2305.08883. Cited by: §2. K. Yoo, W. Ahn, and N. Kwak (2024) Advancing beyond identification: multi-bit watermark for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), p. 4031–4055. Cited by: §1, §2, §3, §5. G. Yu, J. S. Jeong, G. Kim, S. Kim, and B. Chun (2022) Orca: a distributed serving system for transformer-based generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), p. 521–538. Cited by: §D.2. S. Zhang, S. Roller, N. Goyal, M. Artetxe, M. Chen, S. Chen, C. Dewan, M. Diab, X. Li, X. V. Lin, et al. (2022) OPT: open pre-trained transformer language models. arXiv preprint arXiv:2205.01068. Cited by: §D.1. X. Zhao, P. V. Ananth, L. Li, and Y. Wang (2024) Provable robust watermarking for AI-generated text. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1, §2. Appendix A Proof of Theorem 4.1 We prove that at any generation step t, the hierarchical routing sampler preserves the original next-token probability (NTP) distribution PtP_t over the full vocabulary V. The hierarchical sampler first routes through a sequence of nested partitions and then samples a token from the final selected chunk. Hierarchical chunks. Fix a step t and let Pt(⋅)=Pℳ(⋅∣x<t)P_t(·)=P_M(· x_<t) be the model’s NTP distribution on V, so ∑x∈Pt(x)=1 _x P_t(x)=1. The sampler begins with the full vocabulary (0)=C^(0)=V. For each routing stage ℓ∈1,…,L−1 ∈\1,…,L-1\, the current candidate set (ℓ−1)C^( -1) is partitioned into KℓK_ contiguous disjoint chunks by a deterministic rule: (1(ℓ),…,Kℓ(ℓ))=Partition((ℓ−1)),(C^( )_1,…,C^( )_K_ )=Partition(C^( -1)), satisfying ⋃i=1Kℓi(ℓ)=(ℓ−1) and i(ℓ)∩j(ℓ)=∅(i≠j). _i=1^K_ C^( )_i=C^( -1) and C^( )_i ^( )_j= \ (i≠ j). The aggregated probability mass of chunk i at stage ℓ is wi(ℓ)=∑x∈i(ℓ)Pt(x).w^( )_i= _x ^( )_iP_t(x). Chunk selection. At routing stage ℓ , the sampler treats the KℓK_ chunks 1(ℓ),…,Kℓ(ℓ)C^( )_1,…,C^( )_K_ as meta-tokens and draws an index st,ℓ∈1,…,Kℓs_t, ∈\1,…,K_ \ according to ℙ(st,ℓ=i∣(ℓ−1))=wi(ℓ)∑x∈(ℓ−1)Pt(x)=∑x∈i(ℓ)Pt(x)∑x∈(ℓ−1)Pt(x).P(s_t, =i ^( -1))= w^( )_i _x ^( -1)P_t(x)= _x ^( )_iP_t(x) _x ^( -1)P_t(x). The candidate set is then restricted to the selected chunk: (ℓ)=st,ℓ(ℓ).C^( )=C^( )_s_t, . Final token selection. After L−1L-1 routing stages, the sampler holds a final chunk (L−1)C^(L-1) and draws the token xtx_t from PtP_t restricted to this set: ℙ(xt=v∣(L−1))=Pt(v)∑x∈(L−1)Pt(x)for v∈(L−1).P(x_t=v ^(L-1))= P_t(v) _x ^(L-1)P_t(x) v ^(L-1). We now show the marginal distribution of the output satisfies ℙ(xt=v)=Pt(v)P(x_t=v)=P_t(v) for every token v∈v . Proof of Theorem 4.1. Fix a token v∈v . Because the partition rule is deterministic, v determines a unique nested chunk path through the hierarchy. For each ℓ∈1,…,L−1 ∈\1,…,L-1\, let iℓ(v)∈1,…,Kℓi_ (v)∈\1,…,K_ \ be the unique index with v∈iℓ(v)(ℓ)v ^( )_i_ (v) and write (ℓ):=iℓ(v)(ℓ)C^( ):=C^( )_i_ (v) for the unique chunk containing v at stage ℓ . Define the routing event Rv:=⋂ℓ=1L−1st,ℓ=iℓ(v).R_v:= _ =1^L-1\s_t, =i_ (v)\. Sampling v requires the sampler to follow this path, so xt=v⊆Rv\x_t=v\ R_v. Therefore, ℙ(xt=v)=ℙ(xt=v∣Rv)ℙ(Rv).P(x_t=v)=P(x_t=v R_v)P(R_v). Routing factor. At stage ℓ , the chunk containing v has aggregated mass wiℓ(v)(ℓ)=∑x∈(ℓ)Pt(x).w^( )_i_ (v)= _x ^( )P_t(x). Thus ℙ(Rv) (R_v) =∏ℓ=1L−1ℙ(st,ℓ=iℓ(v)|⋂j=1ℓ−1st,j=ij(v)) = _ =1^L-1P\! (s_t, =i_ (v)\, |\, _j=1 -1\s_t,j=i_j(v)\ ) =∏ℓ=1L−1wiℓ(v)(ℓ)∑x∈(ℓ−1)Pt(x) = _ =1^L-1 w^( )_i_ (v) _x ^( -1)P_t(x) =∏ℓ=1L−1∑x∈(ℓ)Pt(x)∑x∈(ℓ−1)Pt(x) = _ =1^L-1 _x ^( )P_t(x) _x ^( -1)P_t(x) =∑x∈(L−1)Pt(x), = _x ^(L-1)P_t(x), where the last equality follows from telescoping together with (0)=C^(0)=V and ∑x∈Pt(x)=1 _x P_t(x)=1. Final-stage factor. Conditioned on RvR_v, the final candidate set is (L−1)C^(L-1), so ℙ(xt=v∣Rv)=ℙ(xt=v∣(L−1))=Pt(v)∑x∈(L−1)Pt(x).P(x_t=v R_v)=P(x_t=v ^(L-1))= P_t(v) _x ^(L-1)P_t(x). Multiplying the two factors, we obtain ℙ(xt=v)=Pt(v).P(x_t=v)=P_t(v). Because v is arbitrary, we prove the final marginal of xtx_t matches the original NTP distribution. ∎ Appendix B Proof of Theorem 4.2 Fix a level ℓ>k >k, a verifier without access to (ℓ) ξ^( ) can only observe the generated sequence x and the authorized key tables (1),…,(k) ξ^(1),…, ξ^(k). The verifier has no statistical way to distinguish which candidate is used at generation time, as formalized by the following assumption. Assumption B.1. Conditioned on the observed sequence x and the authorized tables (1),…,(k) ξ^(1),…, ξ^(k), the random vector (T(ℓ)(0),…,T(ℓ)(2bℓ−1)) (T^( )(0),…,T^( )(2^b_ -1) ) is exchangeable with respect to permutations of the candidate index set 0,…,2bℓ−1\0,…,2^b_ -1\. Equivalently, for any permutation π of 0,…,2bℓ−1\0,…,2^b_ -1\, (T(ℓ)(0),…,T(ℓ)(2bℓ−1))=(T(ℓ)(π(0)),…,T(ℓ)(π(2bℓ−1))). (T^( )(0),…,T^( )(2^b_ -1) )\ d=\ (T^( )(π(0)),…,T^( )(π(2^b_ -1)) ). We now prove that exchangeability implies chance-level decoding at the bit level. For a bℓb_ -bit message a∈0,…,2bℓ−1a∈\0,…,2^b_ -1\, we let br(a)b_r(a) denote the r-th bit of a. Let m^(ℓ) m^( ) be any decoder output based on (x,(1),…,(k))(x, ξ^(1),…, ξ^(k)), and b^r=br(m^(ℓ)) b_r=b_r( m^( )). Lemma B.2. Assume m(ℓ)m^( ) is uniform on 0,…,2bℓ−1\0,…,2^b_ -1\. Under Assumption B.1, for any decoder, ℙ[b^r=br(m(ℓ))]=12,∀r∈1,…,bℓ.P [ b_r=b_r(m^( )) ]= 12, ∀ r∈\1,…,b_ \. Proof. Fix r∈1,…,bℓr∈\1,…,b_ \. Let S0=a:br(a)=0S_0=\a:b_r(a)=0\ and S1=a:br(a)=1S_1=\a:b_r(a)=1\, we have |S0|=|S1|=2bℓ−1|S_0|=|S_1|=2^b_ -1. Because m(ℓ)m^( ) is uniform over 0,…,2bℓ−1\0,…,2^b_ -1\, br(m(ℓ))b_r(m^( )) is uniform on 0,1\0,1\. Consider the permutation πr(a) _r(a) that flips the r-th bit of a, i.e., br(πr(a))=1−br(a)b_r( _r(a))=1-b_r(a) for all a. By Assumption B.1, we have (T(ℓ)(0),…,T(ℓ)(2bℓ−1))=(T(ℓ)(πr(0)),…,T(ℓ)(πr(2bℓ−1))). (T^( )(0),…,T^( )(2^b_ -1) )\ d=\ (T^( )( _r(0)),…,T^( )( _r(2^b_ -1)) ). Applying any decoder rule ϕ(⋅)φ(·) to the above expression, it follows that m^(ℓ)=ϕ(T(ℓ)(0),…,T(ℓ)(2bℓ−1)) m^( )=φ(T^( )(0),…,T^( )(2^b_ -1)) has the same distribution as ϕ(T(ℓ)(πr(0)),…,T(ℓ)(πr(2bℓ−1)))φ(T^( )( _r(0)),…,T^( )( _r(2^b_ -1))). Thus br(m^(ℓ))b_r( m^( )) is equal in distribution to 1−br(m^(ℓ))1-b_r( m^( )), we have ℙ[b^r=0]=ℙ[b^r=1]=1/2P[ b_r=0]=P[ b_r=1]=1/2. Because br(m(ℓ))b_r(m^( )) is uniform, we prove ℙ[b^r=br(m(ℓ))]=12.P[ b_r=b_r(m^( ))]= 12. ∎ Proof of Theorem 4.2. For any ℓ>k >k, by applying Lemma B.2 to each bit position r=1,…,bℓr=1,…,b_ , we prove the chance-level decoding accuracy of unauthorized verifiers. ∎ Appendix C Detailed Algorithms We present the algorithms instantiated with Gumbel-Max sampling. Algorithm C.1 expands Algorithm 1 to show the full generation pipeline, and Algorithm C.2 expands Algorithm 2 to show the full decoding pipeline. Algorithm C.1 HeRo Generation Instantiated with Gumbel-Max Sampling 0: Language model ℳM, initial prefix x≤hx_≤ h, generation length T, context window size h, PRF A, key tables (ℓ)ℓ=1L\ ξ^( )\_ =1^L, chunking schedule (K1,…,KL−1)(K_1,…,K_L-1), full payload m=(m1,…,mK)m=(m_1,…,m_K), position key ξpos _pos 0: Generated token sequence x=(xh+1,…,xT)x=(x_h+1,…,x_T) 1: Initialize context history ℋ←∅H← 2: for t=h+1t=h+1 to T do 3: Query ℳM on the current prefix to obtain Pt(⋅)=Pℳ(⋅∣x<t)P_t(·)=P_M(· x_<t) 4: if x(t−h):(t−1)∈ℋx_(t-h):(t-1) then 5: Sample xt∼Ptx_t P_t 6: Append xtx_t to the running prefix 7: continue 8: else 9: ℋ←ℋ∪x(t−h):(t−1)H ∪\x_(t-h):(t-1)\ 10: end if 11: ζt(pos)←(x(t−h):(t−1),ξpos) _t^(pos) (x_(t-h):(t-1),\, _pos) 12: kt←randint(ζt(pos),K)k_t ( _t^(pos),K) position allocation 13: (mkt(1),…,mkt(L))←mkt(m_k_t^(1),…,m_k_t^(L))← m_k_t 14: Set offset o←0o← 0, current chunk size v←Vv← V 15: for ℓ=1 =1 to L−1L-1 do 16: Partition [o,o+v)[o,\,o+v) into KℓK_ contiguous chunks 1(ℓ),…,Kℓ(ℓ)C_1^( ),…,C_K_ ^( ) 17: wi(ℓ)←∑x∈i(ℓ)Pt(x)w_i^( )← _x _i^( )P_t(x) for i=1,…,Kℓi=1,…,K_ 18: ξ←(ℓ)(mkt(ℓ))ξ← ξ^( )(m_k_t^( )) 19: ζt(ℓ)←(x(t−h):(t−1),ξ) _t^( ) (x_(t-h):(t-1),\,ξ) 20: Use ζt(ℓ) _t^( ) as the PRNG seed to generate (Ut,i(ℓ))i=1Kℓ(U_t,i^( ))_i=1^K_ with Ut,i(ℓ)∼i.i.d.Uniform(0,1)U_t,i^( ) i.i.d. Uniform(0,1) 21: st,ℓ←argmaxilogwi(ℓ)−log(−logUt,i(ℓ))s_t, ← _i\; w_i^( )- (- U_t,i^( )) 22: Update o,vo,v to the range of st,ℓ(ℓ)C_s_t, ^( ) 23: end for 24: ξ←(L)(mkt(L))ξ← ξ^(L)(m_k_t^(L)) 25: ζt(L)←(x(t−h):(t−1),ξ) _t^(L) (x_(t-h):(t-1),\,ξ) 26: Use ζt(L) _t^(L) as the PRNG seed to generate (Ut,j(L))j=0v−1(U_t,j^(L))_j=0^v-1 with Ut,j(L)∼i.i.d.Uniform(0,1)U_t,j^(L) i.i.d. Uniform(0,1) 27: st,L←argmaxj=0,…,v−1logPt(o+j)−log(−logUt,j(L))s_t,L← _j=0,…,v-1\; P_t(o+j)- (- U_t,j^(L)) 28: xt←o+st,Lx_t← o+s_t,L 29: Append xtx_t to the running prefix 30: end for 31: return x=(xh+1,…,xT)x=(x_h+1,…,x_T) Algorithm C.2 HeRo Decoding Instantiated with Gumbel-Max Sampling 0: Batch of generated sequences x(1),…,x(B)x^(1),…,x^(B), vocabulary size V, context window size h, PRF A, key tables (ℓ)ℓ=1L\ ξ^( )\_ =1^L, chunking schedule (K1,…,KL−1)(K_1,…,K_L-1), bits per level (b1,…,bL)(b_1,…,b_L), position key ξpos _pos, number of segments K 0: Decoded payloads m^(1),…,m^(B) m^(1),…, m^(B) 1: Convert the batch into decoding pairs (x(t−h):(t−1),xt)t=h+1T\(x_(t-h):(t-1),\,x_t)\_t=h+1^T, where each pair contains one context window and the corresponding next token 2: Stage 1: compute token-level evidence 3: Reconstruct position allocation ktt=h+1T\k_t\_t=h+1^T in parallel from x(t−h):(t−1)t=h+1T\x_(t-h):(t-1)\_t=h+1^T using ξpos _pos 4: for ℓ=1 =1 to L−1L-1 do 5: Compute st,ℓt=h+1T\s_t, \_t=h+1^T in parallel by locating each token xtx_t in the level-ℓ chunk partition 6: end for 7: Compute st,Lt=h+1T\s_t,L\_t=h+1^T in parallel from the final selected chunk 8: for ℓ=1 =1 to L do 9: for a=0a=0 to 2bℓ−12^b_ -1 do 10: ξ←(ℓ)(a)ξ← ξ^( )(a) 11: Compute Ut(ℓ)(a)t=h+1T\U_t^( )(a)\_t=h+1^T in parallel, where Ut(ℓ)(a)←[(x(t−h):(t−1),ξ)]st,ℓU_t^( )(a)← [A(x_(t-h):(t-1),\,ξ) ]_s_t, 12: Compute Et(ℓ)(a)t=h+1T\E_t^( )(a)\_t=h+1^T in parallel, where Et(ℓ)(a)←−log(1−Ut(ℓ)(a))E_t^( )(a)←- (1-U_t^( )(a)) 13: end for 14: end for 15: Stage 2: aggregate evidence and decode the message 16: for ℓ=1 =1 to L do 17: for a=0a=0 to 2bℓ−12^b_ -1 do 18: Compute Scorei,k(ℓ)(a)Score^( )_i,k(a) by summing Et(ℓ)(a)E_t^( )(a) over all pairs from sequence x(i)x^(i) with kt=k_t=k, for all i=1,…,Bi=1,…,B and k=1,…,Kk=1,…,K in parallel 19: end for 20: Compute m^i,k(ℓ)←argmaxaScorei,k(ℓ)(a) m_i,k^( )← _a\;Score^( )_i,k(a) for all i=1,…,Bi=1,…,B and k=1,…,Kk=1,…,K in parallel 21: end for 22: Set m^(i)←((m^i,1(1),…,m^i,1(L)),…,(m^i,K(1),…,m^i,K(L))) m^(i)← (( m_i,1^(1),…, m_i,1^(L)),…,( m_i,K^(1),…, m_i,K^(L)) ) for each i=1,…,Bi=1,…,B 23: return m^(1),…,m^(B) m^(1),…, m^(B) Appendix D Experiment Details All experiments are run on the NVIDIA A40 GPU with 48 GB memory. For model generation configuration, we set the temperature to 1.01.0, while keeping other decoding hyperparameters (e.g., top-p and top-k) as the model defaults. We use a context window of size h=4h=4 to derive the watermark seed from the recent h tokens and a secret key. The seed used to generate pseudorandom variables is determined by the key and the current h-gram context. Repetition is commonly observed in neural text generation [Fu et al., 2021, Xu et al., 2022]. If the model revisits an h-gram that has appeared earlier in the same generation, watermarking may reuse the same seed and produce repetition loops. To mitigate this issue, we apply a context masking strategy during generation, i.e., we skip watermarking at the positions where the current h-gram has occurred previously. This avoids embedding at positions that would introduce redundant and correlated signals, which may hurt rather than help detection. Context masking therefore removes low-quality embedding positions rather than reducing useful signals. Empirically, detectability remains high under this strategy, consistent with similar approaches adopted in prior watermarking work [Hu et al., 2024, Jiang et al., 2025]. Row-Wise Seeded Uniform RNG. Watermarking requires generating pseudorandom variables with context-dependent seeds, which vary across sequences and time steps in a batch. To support efficient batched inference, we implement a CUDA kernel that generates uniform random variates with row-wise seeds using cuRAND’s Philox state. For efficient decoding, we further provide an indexed variant that returns a single uniform variate per row at a specified vocabulary index, avoiding generating the full vocabulary-length vector when only one entry is needed. D.1 Model Size vs. Vocabulary Size Family Model Release date Params Vocab size OPT OPT-125M 2022-05-03 125M 50,272 OPT OPT-350M 2022-05-03 350M 50,272 OPT OPT-1.3B 2022-05-03 1.3B 50,272 OPT OPT-2.7B 2022-05-03 2.7B 50,272 OPT OPT-6.7B 2022-05-03 6.7B 50,272 OPT OPT-13B 2022-05-03 13B 50,272 OPT OPT-30B 2022-05-03 30B 50,272 OPT OPT-66B 2022-05-03 66B 50,272 OPT OPT-175B 2022-05-03 175B 50,272 Llama 2 Llama-2-7B 2023-07-18 7B 32,000 Llama 2 Llama-2-13B 2023-07-18 13B 32,000 Llama 2 Llama-2-70B 2023-07-18 70B 32,000 Qwen2.5 Qwen2.5-0.5B 2024-09-19 0.5B 151,936 Qwen2.5 Qwen2.5-1.5B 2024-09-19 1.5B 151,936 Qwen2.5 Qwen2.5-3B 2024-09-19 3B 151,936 Qwen2.5 Qwen2.5-7B 2024-09-19 7B 152,064 Qwen2.5 Qwen2.5-14B 2024-09-19 14B 152,064 Qwen2.5 Qwen2.5-32B 2024-09-19 32B 152,064 Qwen2.5 Qwen2.5-72B 2024-09-19 72B 152,064 gpt-oss gpt-oss-20b 2025-08-05 21B 201,088 gpt-oss gpt-oss-120b 2025-08-05 117B 201,088 Table D.1: Representative LLM families at different parameter scales, with tokenizer vocabulary sizes and release dates. Parameter counts grow by orders of magnitude, while vocabulary size remains nearly constant within each family. Table D.1 reports parameter counts, model vocabulary sizes, and release dates for representative LLM families: OPT [Zhang et al., 2022], Llama 2 [Touvron et al., 2023], Qwen2.5 [Yang et al., 2024], and gpt-oss [Agarwal et al., 2025]. Within each model family, the vocabulary size stays nearly constant across model scales, while the number of parameters grows by orders of magnitude. D.2 Batching Strategy In our computational efficiency experiments (Section 5.3), we measure latency under static batching, where all sequences in a batch are padded to the same length and processed synchronously. We choose this setting to ensure a fair comparison against open-source baselines, which are typically implemented using standard deep learning frameworks without specialized inference optimizations. We acknowledge that modern LLM serving systems often employ continuous batching (e.g., vLLM [Kwon et al., 2023] and Orca [Yu et al., 2022]) to reduce padding overhead and improve throughput. An optimized integration with continuous batching is not explored here and we leave it as future work. Appendix E Full Experiment Results E.1 Detectability Figure E.1: Comparison of bit accuracy for multi-bit watermarking methods as a function of token budget when embedding a 24-bit payload. Table E.1: TPR (↑ ) at target false positive rates (10−2,5⋅10−3,10−3,5⋅10−410^-2,5· 10^-3,10^-3,5· 10^-4) for Llama2-7B generations on C4 using HeRo2 (2,2) across payload sizes (12, 24, 36, and 48 bits). Results are computed over 200 generated tokens. FPR 12 Bits 24 Bits 36 Bits 48 Bits 10−210^-2 0.997 0.995 0.997 0.995 5⋅10−35· 10^-3 0.996 0.995 0.997 0.993 10−310^-3 0.989 0.988 0.985 0.972 5⋅10−45· 10^-4 0.982 0.981 0.984 0.961 This section provides the full detectability results to complement the main text analysis in Section 5.2. Table E.1 reports the true positive rate (TPR) achieved by HeRo2 (2,2) for Llama2-7B generations on C4 across payload sizes (12, 24, 36, and 48 bits) at several target false positive rates (FPR). Our method achieves strong detection performance under stringent FPR constraints, which suggests reliable identification with 200 tokens. Tables E.2–E.4 summarize bit-level decoding accuracy for Llama2-7B on both C4 and OpenGen datasets, under generation lengths of 200 and 400 tokens and payload sizes of 12, 24, 36, and 48 bits. Across settings, the same trends observed in the main text persist: HeRo1HeRo^1 attains strong (often near saturated) decoding accuracy at moderate payload sizes, while HeRo2HeRo^2 exhibits a modest reduction relative to HeRo1HeRo^1 yet remains competitive with or better than prior multi-bit baselines at the same total payload size. Figure E.1 plots decoding accuracy as a function of the generation length for a 24-bit payload. In addition to the configurations shown in the main paper, we include a broader set of hyperparameter settings for a more comprehensive comparison. Table E.2: Comparison of bit accuracy (B.Acc.↑ ) and median perplexity (PPL) for Llama2-7B generations on C4 across payload sizes (12, 24, 36, and 48 bits). Results are computed over 400 generated tokens. Watermark S.D. 12 Bits 24 Bits 36 Bits 48 Bits B.Acc.↑ PPL B.Acc.↑ PPL B.Acc.↑ PPL B.Acc.↑ PPL w/o — — 4.16 — 4.16 — 4.16 — 4.16 MPAC (1, 2.0) — 0.987 4.55 0.950 4.57 0.917 4.56 0.882 4.49 MPAC (2, 2.0) — 0.987 4.65 0.957 4.65 0.920 4.62 0.886 4.59 StealthInk (1) — 0.976 4.13 0.920 4.13 0.882 4.10 0.845 4.12 StealthInk (2) — 0.925 4.05 0.843 4.12 0.817 4.15 0.767 4.18 BiMark (5) — 0.934 4.14 0.850 4.12 0.807 4.12 0.773 4.17 BiMark (10) — 0.970 4.08 0.911 4.13 0.866 4.10 0.829 4.10 BiMark (20) — 0.989 4.03 0.956 4.05 0.923 4.08 0.892 4.08 HeRo1 (2) — 0.998 4.14 0.992 4.13 0.980 4.13 0.963 4.12 HeRo1 (3) — 0.998 4.10 0.994 4.10 0.986 4.14 0.974 4.14 HeRo2 (1,1) ✓ 0.982 4.11 0.943 4.13 0.904 4.13 0.869 4.11 HeRo2 (2,1) ✓ 0.989 4.13 0.960 4.14 0.931 4.13 0.900 4.14 HeRo2 (2,2) ✓ 0.991 4.16 0.970 4.17 0.940 4.10 0.912 4.10 Table E.3: Comparison of bit accuracy (B.Acc.↑ ) and median perplexity (PPL) for Llama2-7B generations on OpenGen across payload sizes (12, 24, 36, and 48 bits). Results are computed over 200 generated tokens. Watermark S.D. 12 Bits 24 Bits 36 Bits 48 Bits B.Acc.↑ PPL B.Acc.↑ PPL B.Acc.↑ PPL B.Acc.↑ PPL w/o — — 3.96 — 3.96 — 3.96 — 3.96 MPAC (1, 2.0) — 0.944 4.40 0.861 4.40 0.823 4.42 0.781 4.31 MPAC (2, 2.0) — 0.948 4.43 0.859 4.37 0.819 4.39 0.782 4.39 StealthInk (1) — 0.912 3.86 0.820 3.91 0.787 3.94 0.747 3.94 StealthInk (2) — 0.812 3.84 0.728 3.95 0.716 3.97 0.671 4.00 BiMark (5) — 0.853 3.92 0.751 3.90 0.721 3.89 0.694 3.98 BiMark (10) — 0.898 3.91 0.800 3.90 0.767 3.89 0.733 3.85 BiMark (20) — 0.944 3.85 0.875 3.83 0.832 3.91 0.798 3.90 HeRo1 (2) — 0.986 3.88 0.949 3.92 0.906 3.96 0.878 3.93 HeRo1 (3) — 0.991 3.94 0.967 3.99 0.933 3.97 0.899 3.90 HeRo2 (1,1) ✓ 0.929 3.91 0.858 3.89 0.813 3.92 0.778 3.94 HeRo2 (2,1) ✓ 0.952 3.96 0.887 3.92 0.834 3.88 0.799 3.89 HeRo2 (2,2) ✓ 0.962 3.95 0.898 3.86 0.850 3.99 0.810 3.92 Table E.4: Comparison of bit accuracy (B.Acc.↑ ) and median perplexity (PPL) for Llama2-7B generations on OpenGen across payload sizes (12, 24, 36, and 48 bits). Results are computed over 400 generated tokens. Watermark S.D. 12 Bits 24 Bits 36 Bits 48 Bits B.Acc.↑ PPL B.Acc.↑ PPL B.Acc.↑ PPL B.Acc.↑ PPL w/o — — 3.70 — 3.70 — 3.70 — 3.70 MPAC (1, 2.0) — 0.977 4.08 0.930 4.14 0.891 4.14 0.855 4.04 MPAC (2, 2.0) — 0.979 4.16 0.933 4.14 0.897 4.09 0.864 4.20 StealthInk (1) — 0.956 3.63 0.889 3.65 0.852 3.69 0.820 3.69 StealthInk (2) — 0.884 3.56 0.814 3.65 0.784 3.74 0.741 3.74 BiMark (5) — 0.914 3.64 0.822 3.64 0.784 3.62 0.759 3.63 BiMark (10) — 0.956 3.63 0.876 3.59 0.837 3.66 0.800 3.58 BiMark (20) — 0.975 3.53 0.932 3.51 0.900 3.61 0.869 3.59 HeRo1 (2) — 0.992 3.60 0.979 3.68 0.958 3.65 0.939 3.65 HeRo1 (3) — 0.994 3.61 0.989 3.63 0.972 3.68 0.954 3.68 HeRo2 (1,1) ✓ 0.964 3.59 0.912 3.61 0.875 3.64 0.842 3.64 HeRo2 (2,1) ✓ 0.976 3.66 0.941 3.65 0.900 3.64 0.870 3.64 HeRo2 (2,2) ✓ 0.985 3.63 0.945 3.59 0.916 3.68 0.876 3.61 E.2 Perplexity We provide the complete perplexity (PPL) results corresponding to Section 5.2. Specifically, we report the distribution of PPL for Llama2-7B generations on C4 and OpenGen datasets, varying the watermark payload size in 12,24,36,48\12,24,36,48\ bits and the evaluation length in 200,400\200,400\ generated tokens. For each configuration, we compare the unwatermarked baseline (w/o) against a comprehensive set of multi-bit watermarking methods, including additional hyperparameter settings beyond those presented in the main paper. Figures E.2–E.17 summarize the results using violin plots. Figure E.2: Violin plots of perplexity (PPL) for Llama2-7B generations on C4 under multi-bit watermarking methods with a 12-bit payload and the unwatermarked baseline (w/o), computed over 200 generated tokens. Figure E.3: Violin plots of perplexity (PPL) for Llama2-7B generations on C4 under multi-bit watermarking methods with a 24-bit payload and the unwatermarked baseline (w/o), computed over 200 generated tokens. Figure E.4: Violin plots of perplexity (PPL) for Llama2-7B generations on C4 under multi-bit watermarking methods with a 36-bit payload and the unwatermarked baseline (w/o), computed over 200 generated tokens. Figure E.5: Violin plots of perplexity (PPL) for Llama2-7B generations on C4 under multi-bit watermarking methods with a 48-bit payload and the unwatermarked baseline (w/o), computed over 200 generated tokens. Figure E.6: Violin plots of perplexity (PPL) for Llama2-7B generations on C4 under multi-bit watermarking methods with a 12-bit payload and the unwatermarked baseline (w/o), computed over 400 generated tokens. Figure E.7: Violin plots of perplexity (PPL) for Llama2-7B generations on C4 under multi-bit watermarking methods with a 24-bit payload and the unwatermarked baseline (w/o), computed over 400 generated tokens. Figure E.8: Violin plots of perplexity (PPL) for Llama2-7B generations on C4 under multi-bit watermarking methods with a 36-bit payload and the unwatermarked baseline (w/o), computed over 400 generated tokens. Figure E.9: Violin plots of perplexity (PPL) for Llama2-7B generations on C4 under multi-bit watermarking methods with a 48-bit payload and the unwatermarked baseline (w/o), computed over 400 generated tokens. Figure E.10: Violin plots of perplexity (PPL) for Llama2-7B generations on OpenGen under multi-bit watermarking methods with a 12-bit payload and the unwatermarked baseline (w/o), computed over 200 generated tokens. Figure E.11: Violin plots of perplexity (PPL) for Llama2-7B generations on OpenGen under multi-bit watermarking methods with a 24-bit payload and the unwatermarked baseline (w/o), computed over 200 generated tokens. Figure E.12: Violin plots of perplexity (PPL) for Llama2-7B generations on OpenGen under multi-bit watermarking methods with a 36-bit payload and the unwatermarked baseline (w/o), computed over 200 generated tokens. Figure E.13: Violin plots of perplexity (PPL) for Llama2-7B generations on OpenGen under multi-bit watermarking methods with a 48-bit payload and the unwatermarked baseline (w/o), computed over 200 generated tokens. Figure E.14: Violin plots of perplexity (PPL) for Llama2-7B generations on OpenGen under multi-bit watermarking methods with a 12-bit payload and the unwatermarked baseline (w/o), computed over 400 generated tokens. Figure E.15: Violin plots of perplexity (PPL) for Llama2-7B generations on OpenGen under multi-bit watermarking methods with a 24-bit payload and the unwatermarked baseline (w/o), computed over 400 generated tokens. Figure E.16: Violin plots of perplexity (PPL) for Llama2-7B generations on OpenGen under multi-bit watermarking methods with a 36-bit payload and the unwatermarked baseline (w/o), computed over 400 generated tokens. Figure E.17: Violin plots of perplexity (PPL) for Llama2-7B generations on OpenGen under multi-bit watermarking methods with a 48-bit payload and the unwatermarked baseline (w/o), computed over 400 generated tokens. E.3 Study of Hierarchy Depth To study how hierarchy depth affects detection performance and generation quality, we evaluate bit accuracy and perplexity under four configurations: HeRo1(8), HeRo2(4,4), HeRo4(2,2,2,2), and HeRo8 with eight 1-bit levels. Here, HeRo(b1,⋯,bL)L^L(b_1,·s,b_L) denotes an L-level hierarchy in which the ℓ -th layer discloses bℓb_ bits. As shown in Table E.5, detection generally becomes more difficult as the hierarchy becomes deeper. We observe that the performance gap across settings becomes smaller as the token budget increases. More broadly, the performance depends jointly on the hierarchy depth and the partition structure across levels, and there remains room to further optimize deeper configurations. Table E.6 reports perplexity across all settings. The PPL remains very close to that of text generated without watermarking, indicating that increasing the number of hierarchical divisions does not degrade generation quality. This is consistent with the statistical unbiasedness of our framework, which preserves the original sampling distribution. Table E.5: Bit accuracy (↑ ) under different hierarchy depths, evaluated with generation lengths of 200 and 400 tokens. Watermark n=200n=200 n=400n=400 HeRo(8)1^1(8) 0.997 0.998 HeRo(4,4)2^2(4,4) 0.997 0.998 HeRo(2,2,2,2)4^4(2,2,2,2) 0.963 0.988 HeRo(1,1,1,1,1,1,1,1)8^8(1,1,1,1,1,1,1,1) 0.860 0.919 Table E.6: Perplexity under different hierarchy depths, evaluated with generation lengths of 200 and 400 tokens. Watermark n=200n=200 n=400n=400 w/o 4.31 4.16 HeRo(8)1^1(8) 4.26 4.13 HeRo(4,4)2^2(4,4) 4.31 4.15 HeRo(2,2,2,2)4^4(2,2,2,2) 4.31 4.15 HeRo(1,1,1,1,1,1,1,1)8^8(1,1,1,1,1,1,1,1) 4.30 4.13 Appendix F Watermarking Examples Text Message Prompt: I first met Amanda Vickery ten years ago - her book, ’The Gentleman’s Daughter’ had just been published, and she gave an interview to our local paper. Something about the interview made me think she would be good on the radio - her liveliness and her sense of fun came across, even in a print interview. I was right - when I called her, and we met for coffee, I realised that her warmth and her quick wit Ground Truth Public message: 110 110 110 111 Private message: 100 001 111 011 Without Watermark: were the perfect match for radio. And I didn’t realise, at that point, that she was a TV historian too - not just a historian, in fact, but a TV historian. Her programmes have made her a star on the BBC. I am delighted that Amanda has written a book - as a star TV historian, she has a lot of fans, but her book is a chance to get to know her as a historian. She writes beautifully - it’s like she’s been on our radio programmes, talking to you. It’s as if she’s just popped round to chat about her life and work. I like that kind of historian - someone who is engaging, passionate, and who writes well. I’m looking forward to reading this book. I can’t resist giving you a quote from Amanda: ’I love reading, and I don’t see myself giving up the habit for anything…’ So I reckon she’s the right person to write this book. She really does love her subject - and that shows. I have already read it, and enjoyed every word. If you want to be reminded of Amanda Vickery on Woman’s Hour, there is a link below: The Gentleman’s Daughter Amanda Vickery - A Short Introduction - part 1 Woman’s Hour - Amanda Vickery Mary Beard writes about the history of feminism, and the BBC’s ’The Vagina Monologues’ Posted at 12:57 PM in Books, History, Interviews — Permalink — Comments (0) The 21st February marks the 100th anniversary of the first women voting in Britain. Decoded: Public message: 111 110 010 110 Private message: 000 011 101 100 HeRo2(1,1): were the perfect match for radio. We decided we should make a show, and the next day we were off and recording in the park. This is the first interview that I ever did for Woman’s Hour - and it was my first experience of interviewing on the radio. I had never met Amanda before, and I was nervous that she would think that I had no clue about what I was talking about. It helped enormously that she was so full of energy, and that she was so funny. I learned that, when interviewing for the radio, it is better to be yourself - and I also learned how to put questions in a way that makes the interviewee think that they are asking them! Amanda and I recorded the Woman’s Hour show in London, but we did a lot of the pre-interview on the phone. Amanda is not a woman who sits still, and she had to be at the BBC while I was in my office at work, but we were able to set up the recording and make sure it worked by chatting on the phone, and then we got together for an hour at the end of the day, with a glass of wine, to finish the editing, before taking it over to the studio. Amanda was a joy to work with - she was open to the ideas we suggested, but she was also full of her own ideas, and she also had the wisdom to know when I should be in charge. When we finished, I felt that we had done a good interview, and that I could go on and do more. I am glad that I did. I have worked with many actors on the radio, but not so many who have also done interviews on TV. Decoded: Public message: 100 111 110 111 Private message: 100 101 111 011 Table F.1: Watermarked text samples for a 24-bit payload. The prompt row shows the ground-truth public/private message. Decoded messages are reported for each generation, with incorrect bits highlighted in red.