Linguistics-Aware Non-Distortionary LLM Watermarking¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/Shinwoo-Park/luna_watermark
Area: LLM Safety
Keywords: LLM watermarking, non-distortionary sampling, POS context entropy, linguistics-aware, model-free detection
TL;DR¶
LUNA leverages normalized next-tag entropy estimated offline from an external corpus to quantify local syntactic choice, dynamically steering prefix-measurable binary tournament depths to simultaneously guarantee single-token non-distortion, fully model-free auditing, and typological adaptivity across diverse languages.
Background & Motivation¶
As large language models are increasingly deployed across high-impact multilingual applications ranging from creative writing to automated news generation, establishing verifiable provenance, regulatory attribution, and disinformation defenses has emerged as a fundamental societal requirement. Decoding-time statistical watermarking embeds keyed signals into autoregressive generations to distinguish machine outputs from human writing. A deployment-ready watermark must jointly fulfill three foundational desiderata: single-token non-distortion under the random-key model (where the marginal next-token distribution strictly matches the unwatermarked base distribution, as in EXP or SynthID-Text) to safeguard generation fidelity; model-free verification (enabling platforms and public auditors to verify provenance using only the generated text, tokenizer, and secret key, without model logits or surrogate networks, as in KGW); and context adaptivity (allocating watermarking strength based on the capacity afforded by local contexts, as in SWEET or EWD). However, existing adaptive non-distortionary schemes extract capacity signals directly from target model-side predictive uncertainty, tying verification to expensive and non-public model forward passes.
This fundamental tension is substantially exacerbated in multilingual environments. Natural languages exhibit profound typological divergence across morphology, constituent order, word segmentation, and orthography. Fixed-capacity allocation ignores how local grammatical constraints govern token options. For instance, in analytic English, encountering the part-of-speech sequence "DET + ADJ" (e.g., "a quiet ...") tightly confines the subsequent slot almost deterministically to a NOUN, leaving virtually zero grammatical choice. Conversely, in agglutinative Korean, a morpheme context ending with an object case marker ("NNG + JKO") can freely precede a verb, an adverbial phrase, or an adnominal clause, spreading probability over diverse functional categories. Applying a static sampling depth or relying on model-side introspection either injects unnatural artifacts into rigid syntactic positions or breaks third-party auditability.
LUNA's core insight is that local grammatical flexibility is an intrinsic, structural invariant of natural language rather than a manifestation of specific neural network weights, meaning it can be stably and objectively estimated offline from a generic part-of-speech annotated corpus. Core idea: estimate normalized next-tag entropy offline from an external corpus to capture local syntactic choice, and map this signal into prefix-measurable tournament depths during decoding, achieving single-token non-distortion, typological adaptivity, and model-free verification without model forward passes.
Method¶
Overall Architecture¶
The end-to-end pipeline of LUNA (Linguistics-Aware Non-Distortionary LLM Watermarking) comprises three decoupled phases: offline linguistic uncertainty calibration, prefix-measurable tournament decoding, and model-free hypothesis testing. During calibration, LUNA processes a held-out multilingual corpus (CulturaX) to compute normalized Shannon entropy tables over POS \(n\)-grams. During text generation, the base language model provides base next-token distribution \(p_t\), while the linguistic branch inspects the prefix POS context \(c_t\), queries the empirical entropy table with deterministic order-backoff to obtain \(\lambda(c_t)\), and discretizes it into an \(m_t\)-layer tournament depth; an \(m_t\)-layer probability-rescaled knockout tournament then updates candidate probabilities before sampling token \(x_t\). During detection, a third-party auditor reconstructs the exact depth and weighting schedule from the surface text using the same tokenizer, tagger, entropy table, and secret key, computing an analytical standardized score.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Prefix Context x<t & Base Distribution pt"] --> B["Normalized Next-Tag POS Entropy Estimation<br/>Corpus Calibration & Order Backoff"]
B --> C["Prefix-Measurable Three-Tier Depth Scheduling<br/>Quantization via 25th/75th Percentiles"]
C --> D["Single-Token Non-Distortionary Tournament Sampling<br/>Layer-wise Probability Rescaling & History Safeguard"]
D --> E["Generated Watermarked Token xt"]
E --> F["Dual-Weighted Model-Free Detection Scoring<br/>POS-Span Alignment & Analytical Standardized Z-Score"]
Key Designs¶
1. Normalized Next-Tag POS Entropy Estimation: Syntactic Flexibility Metric with Order Backoff
To decouple watermarking capacity from target-model weights while providing an auditable linguistic prior, LUNA computes the conditional uncertainty of part-of-speech transitions from external corpora. For a given language \(L\), let \(c\) denote a POS context of order \(r\) (consisting of the trailing \(r-1\) tags). Let \(S_{L,c}\) denote the observed support of next tags in the calibration split, with support cardinality \(K_{L,c} = |S_{L,c}|\), and let \(\hat{P}_L(q' \mid c)\) represent the empirical transition probability to tag \(q'\). LUNA defines the raw Shannon entropy \(H_L(c) = -\sum_{q' \in S_{L,c}} \hat{P}_L(q' \mid c) \log_2 \hat{P}_L(q' \mid c)\), and normalizes it by the maximum attainable entropy \(\log_2 K_{L,c}\) onto \([0, 1]\):
Values close to 0 signify near-deterministic grammatical continuations (e.g., following a determiner), while values approaching 1 reflect highly diffuse, syntactically open positions. To counter empirical sparsity for higher-order contexts, LUNA implements deterministic order-backoff: beginning at primary order \(k_{\text{primary}}\) (typically 3 or 4), it returns the precomputed table value only if the empirical occurrence count meets a frequency threshold \(N_L(c) \ge \nu\); otherwise, it cascades down to lower orders, returning default uninformative value \(\lambda_{\text{def}} = 0.5\) if no supported context exists.
2. Prefix-Measurable Three-Tier Depth Scheduling: Capacity Adaptation Preserving Marginals
Once local uncertainty \(\lambda(c_t)\) is determined, the central mathematical requirement is establishing prefix-measurability: tournament depth \(m_t\) must depend strictly on the historical prefix \(x_{<t}\) and be finalized prior to sampling \(x_t\), ensuring conditional independence from the random watermark key bits at position \(t\). LUNA maps continuous entropy \(\lambda(c_t)\) into a discrete three-tier depth schedule calibrated using frequency-weighted 25th and 75th percentiles \((\tau_1, \tau_2)\) from the calibration corpus:
The default depth configuration sets \((m_{\min}, m_{\text{mid}}, m_{\max}) = (5, 15, 30)\). Low-entropy positions receive shallow tournaments (\(m_t = 5\)), strictly bounding perturbation where syntax is brittle, whereas high-entropy positions scale to deep tournaments (\(m_t = 30\)) to accumulate strong statistical signal. To prevent degenerative loops in autoregressive decoding, LUNA incorporates a repeated-context safeguard: maintaining a sliding window of recent context hashes (size \(|H|=30\)), it immediately falls back to unwatermarked base sampling from \(p_t\) whenever a hash collision occurs.
3. Single-Token Non-Distortionary Tournament Sampling: Layer-wise Probability Rescaling
Conditioned on scheduled depth \(m_t\), LUNA implements a mathematically equivalent probability-rescaling formulation of the binary knockout tournament. For token \(v \in V\) at layer \(\ell \in \{1, \dots, m_t\}\), keyed pseudo-random functions generate binary bits \(G_{t,v}^{(\ell)} \in \{0, 1\}\) distributed as independent \(\text{Bernoulli}(1/2)\). Starting from initial base distribution \(q_t^{(0)}(v) = p_t(v)\), layer \(\ell\) computes the conditional expectation across the active vocabulary:
Candidate probabilities are then rescaled via:
The final token is sampled from the terminal distribution \(x_t \sim q_t^{(m_t)}\). Under the standard random-key assumption, taking expectation over the watermark key gives \(\mathbb{E}[G_{t,v}^{(\ell)}] = 1/2\) and \(\mathbb{E}[\mu_t^{(\ell)}] = 1/2\). By the tower property of conditional expectation, \(\mathbb{E}_{G^{(\ell)}}[q_t^{(\ell)}(v) \mid q_t^{(\ell-1)}] = q_t^{(\ell-1)}(v)\). Inductively across all \(m_t\) layers, \(\mathbb{E}_G[q_t^{(m_t)}(v)] = p_t(v)\), rigorously proving single-token marginal preservation \(\mathbb{E}_G[\Pr(x_t = v \mid x_{<t}, G)] = p_t(v)\).
4. Dual-Weighted Model-Free Detection Scoring: Analytical Standardized Z-Score
Verification operates entirely without language model weights, forward passes, or surrogate logits. The detector parses the observed token sequence \(x\), aligns POS tags to token spans, and reconstructs identical context histories, \(\lambda(c_t)\), and depths \(m_t\) across all valid positions \(t \in I\). At each position, the detector tallies the centered layer-wise keyed scores:
To optimize statistical test power, LUNA weights each position by its linguistic entropy, setting \(\omega_t = \lambda(c_t)\). Under the null hypothesis of unwatermarked text (or an incorrect secret key), each centered bit has variance \(1/4\). The normalized test statistic aggregates across valid positions:
By the central limit theorem, \(Z\) converges to a standard normal distribution \(\mathcal{N}(0, 1)\), allowing the verifier to make high-confidence attribution decisions against threshold \(\gamma\) without querying any neural model.
Loss & Training¶
LUNA is entirely training-free and requires no gradient updates or model fine-tuning. The sole precomputed artifact is the language-specific normalized entropy table \(\lambda\). Calibration leverages 20,000 held-out passages per language from CulturaX filtered to 300โ4000 characters, strictly disjoint from evaluation prompts. Dedicated deterministic POS taggers are maintained across calibration, generation, and detection: spaCy for English and German, HanLP (CTB9) for Chinese, Kiwi (Sejong) for Korean, SudachiPy (UniDic mode A) for Japanese, and CAMeL Tools (PATB) for Arabic. Generation follows standard evaluation settings: temperature \(\tau = 0.7\), Top-\(p = 0.95\), no Top-\(k\) cap, generating 200โ256 tokens per prompt on an NVIDIA RTX 3090 GPU.
Key Experimental Results¶
Main Results¶
Evaluation spans six typologically diverse languages across two domains (Wikipedia and News), creating 12 distinct language-by-domain benchmarks comprising 6,000 total evaluation instances. LUNA is benchmarked against eight baselines: KGW, EWD, SWEET, MorphMark, STELA, GumbelSoft, EXP, and budget-matched SynthID-Text (\(B = \mathbb{E}[2^{m_t}] \approx 2^{28}\), running a near-constant depth-28 schedule). Quality shifts are measured against unwatermarked counterparts using Qwen2.5-1.5B as the neutral cross-lingual reference evaluator across five complementary metrics: median perplexity shift \(|\Delta\text{PPL}_{\text{med}}|\), Self-BLEU shift \(|\Delta\text{SBLEU}|\), Distinct-1 shift \(|\Delta\text{Dist1}|\), token surprisal shift \(|\Delta\text{Surp}|\), and predictive entropy shift \(|\Delta\text{Entr}|\).
| Method | AUROC | TPR@5% FPR | \(|\Delta\text{PPL}_{\text{med}}|\) | 95% Bootstrap CI | \(|\Delta\text{SBLEU}|\) | \(|\Delta\text{Dist1}|\) | \(|\Delta\text{Surp}|\) | \(|\Delta\text{Entr}|\) | | :--- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | KGW | 0.9982 | 0.9952 | 1.290 | [0.625, 2.133] | 0.0063 | 0.0106 | 0.1357 | 0.0789 | | EWD | 0.9990 | 0.9972 | 1.115 | [0.554, 1.820] | 0.0063 | 0.0101 | 0.1186 | 0.0645 | | SWEET | 0.9985 | 0.9950 | 0.915 | [0.474, 1.482] | 0.0050 | 0.0068 | 0.0989 | 0.0589 | | MorphMark | 0.9902 | 0.9643 | 0.425 | [0.158, 0.734] | 0.0024 | 0.0052 | 0.0442 | 0.0275 | | STELA | 0.9982 | 0.9953 | 1.182 | [0.620, 1.911] | 0.0065 | 0.0114 | 0.1250 | 0.0711 | | GumbelSoft | 0.9899 | 0.9778 | 1.202 | [0.485, 2.112] | 0.0575 | 0.0653 | 0.1473 | 0.1370 | | EXP | 0.9876 | 0.9777 | 1.310 | [0.509, 2.286] | 0.0711 | 0.0728 | 0.1659 | 0.1640 | | SynthID-Text | 0.9972 | 0.9928 | 0.463 | [0.219, 0.751] | 0.0040 | 0.0062 | 0.0514 | 0.0396 | | LUNA (Ours) | 0.9959 | 0.9868 | 0.045 | [0.022, 0.073] | 0.0016 | 0.0029 | 0.0054 | 0.0116 |
Ablation Study¶
To isolate the exact causal mechanisms driving performance, LUNA is compared against three targeted controls: 1. LUNA vs STELA: Evaluates the non-distortionary tournament sampler against distortionary green-list logit bias given the identical POS-entropy prior; 2. LUNA vs SynthID-Text: Evaluates the linguistic scheduling mechanism against uniform/pseudo-random scheduling within the identical binary tournament backbone at equal candidate budgets; 3. LUNA vs SynthID-Text-Entropy: Evaluates external corpus-derived POS entropy against internal target model-side predictive entropy within the identical tournament framework.
| Comparison | \(\Delta\text{AUROC}\) | \(\Delta\text{TPR@5\%}\) | \(|\Delta\text{PPL}_{\text{med}}|\) Factor | \(|\Delta\text{SBLEU}|\) Factor | \(|\Delta\text{Dist1}|\) Factor | \(|\Delta\text{Surp}|\) Factor | \(|\Delta\text{Entr}|\) Factor | | :--- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | LUNA vs STELA | -0.0023 | -0.0085 | 26.41ร | 4.07ร | 3.96ร | 22.99ร | 6.12ร | | LUNA vs SynthID-Text | -0.0013 | -0.0060 | 10.35ร | 2.53ร | 2.15ร | 9.45ร | 3.41ร | | LUNA vs SynthID-Text-Entropy | -0.0001 | -0.0007 | 1.76ร | 1.59ร | 0.92ร | 1.69ร | 1.70ร |
Key Findings¶
- Comprehensive Quality Dominance: LUNA achieves the lowest distortion on all five evaluated quality dimensions, reducing median perplexity shift by \(9.5\times\) relative to the closest baseline (0.045 vs. 0.425 for MorphMark). Its 95% bootstrap confidence interval \([0.022, 0.073]\) strictly decouples from all baseline intervals, whose lowest bound starts at 0.158. Geometric mean quality preservation gains over baselines range from \(3.5\times\) (MorphMark) and \(4.8\times\) (SynthID-Text) to \(9.3\times\) (KGW) and \(26.9\times\) (EXP).
- Exclusive Residency in the Operational Sweet Spot: Defining the practical deployment sweet spot as simultaneously achieving \(\text{AUROC} > 0.99\) and \(|\Delta\text{PPL}_{\text{med}}| < 0.1\), LUNA enters this regime in 9 out of 12 benchmark settings. Across all 8 baselines, only MorphMark enters in 2 settings, while all remaining methods fail entirely (0/12).
- Corpus Linguistic Entropy Outperforms Model Entropy: While SynthID-Text-Entropy achieves near-identical detection (gap \(\le 0.0007\)), it requires full forward model passes during verification, which eliminates model-free auditing. Moreover, LUNA achieves \(1.59\times\) to \(1.76\times\) lower shift across four of five quality metrics, demonstrating that corpus-level syntactic constraints guide capacity to safer insertion points than model-side predictive uncertainty.
- Typological Divergence in Threshold Spreads: The frequency-weighted percentile spread \(\tau_2 - \tau_1\) directly mirrors linguistic typology: agglutinative Korean (0.244) and verb-second fusional German (0.229) exhibit the widest uncertainty variation, isolating Chinese (0.111) and templatic Arabic (0.065) yield narrower spreads. Nevertheless, LUNA's adaptive thresholding preserves top-tier quality even in Arabic, reaching sweet-spot criteria across both domains.
Highlights & Insights¶
- Decoupling Capacity Allocation from Model Weights: LUNA uncovers that syntactic variability is an inherent linguistic property rather than a neural artifact. Storing capacity priors in an explicit, versioned, and publicly auditable \(\lambda\) table transforms watermark adaptation from opaque model introspection into a transparent governance artifact.
- Prefix-Measurable Mathematical Elegance: By conditioning binary knockout depth exclusively on preceding tokens, LUNA preserves theoretical single-token non-distortion while unlocking dynamic depth modulation, avoiding the rigidity of fixed-depth tournaments in grammatically constrained slots.
- Multi-Axis Cross-Typology Validation: The benchmark protocol rigorously stresses analytical, isolating, agglutinative, fusional, and templatic languages across news and encyclopedia domains, establishing an empirical gold standard for multilingual provenance research.
Limitations & Future Work¶
- Syntactic Proxy Granularity: Part-of-speech context entropy models local grammatical latitude but overlooks deeper semantic equivalence, discourse transitions, pragmatic registers, and stylistic constraints. Future work could integrate dependency grammar or lightweight semantic embedding caches.
- Reliance on Linguistic Preprocessing Tools: Model-free detection requires deterministic POS analyzers (e.g., spaCy, HanLP, Kiwi, SudachiPy). Tokenization errors or tagger domain shifts in low-resource or code-switching environments could disrupt depth alignment, necessitating robust soft-matching protocols.
- Scope of Distributional Invariance: Theorem 1 guarantees single-step marginal invariance under the random-key model; it does not guarantee multi-step joint sequence equivalence under a realized static key, nor does it guarantee theoretical invariance under aggressive paraphrasing or translation attacks.
Related Work & Insights¶
- vs. KGW / EWD / SWEET: Classical logit-biasing schemes modify output token distributions and degrade generation fluency, with EWD and SWEET requiring target-model forward passes during verification. LUNA ensures strict single-token marginal preservation via binary tournaments while maintaining zero-model verification overhead.
- vs. STELA: STELA introduced corpus-estimated POS indeterminacy to watermarking, but applied it to scale distortionary green-list logit biases. LUNA channels this linguistic prior into non-distortionary tournament sampling, reducing perplexity degradation by \(26.4\times\).
- vs. SynthID-Text: SynthID-Text pioneered binary knockout tournaments but deploys fixed or pseudo-random depth schedules ignorant of syntactic context. LUNA equips tournament sampling with linguistic adaptability, delivering a \(10.35\times\) quality improvement at the identical expected tournament budget.
Rating¶
- Novelty: โญโญโญโญโญ First framework combining corpus-derived normalized syntactic entropy with prefix-measurable non-distortionary tournament sampling.
- Experimental Thoroughness: โญโญโญโญโญ Rigorous evaluation across 6 typological languages, 2 domains, 8 baselines, 5 quality metrics, and controlled ablations with bootstrap statistics.
- Writing Quality: โญโญโญโญโญ Outstanding clarity, coherent theoretical proofs, and compelling typological narrative.
- Value: โญโญโญโญโญ Resolves the long-standing trilemma between quality preservation, detection power, and model-free third-party verification for multilingual LLM provenance.