A Linguistics-Aware LLM Watermarking via Syntactic Predictability

AI summary

Overview

Research area: Natural Language Processing — LLM watermarking, text provenance, and detection of machine-generated text, with a cross-linguistic (English, Chinese, Korean) focus.

Technical level: Advanced. The paper formalizes linguistic indeterminacy using conditional Shannon entropy over part-of-speech n-grams and derives a weighted z-score detection statistic.

Scope (one sentence): The paper introduces STELA (Structurally-Tethered Entropy-based Linguistic wAtermarking), a watermarking framework that adapts watermark strength to the syntactic predictability of the text so that detection can be performed without access to any model logits.

What This Paper Is About

Existing adaptive watermarking methods such as SWEET and EWD modulate watermark strength using token-level entropy computed from the language model's logits, which means detection also requires those logits — blocking public, third-party verification. STELA instead uses a model-independent signal: the conditional entropy of POS n-grams estimated from human-written corpora, which measures how grammatically constrained the current context is. The goal is to preserve text quality by weakening the watermark where grammar is forced, and to boost detectability by strengthening it where linguistic choices are abundant, while keeping detection model-free.

Key Contributions

1. A model-independent notion of linguistic indeterminacy. The paper defines λ(c_t), the normalized conditional entropy of the next POS tag given the preceding k−1 POS tags, estimated from human-written corpora. Unlike token entropy, this signal requires no access to model logits at any stage.

2. A fully adaptive insertion-and-detection scheme. STELA sets an adaptive bias δ'_t = δ · λ(c_t) during insertion (Equation 6) and weights each token's contribution to the detection statistic by w_t = λ(c_t) (Equation 8), producing a weighted z-score (Equation 9). Table 1 frames this as the first method combining adaptive weighting on both insertion and detection with a model-free detection framework.

3. Cross-typological validation. Experiments span analytic English, isolating Chinese, and agglutinative Korean, using three LLMs of similar scale (0.5B–1B parameters): Llama-3.2-1B, Qwen3-0.6B, and HyperCLOVAX-SEED-Text-0.5B.

4. An analysis of how the watermark distributes across word categories. The paper shows the z-score contribution of content versus function words tracks each language's typology, and shows robustness to synonym substitution and to a Dipper paraphrase attacker.

Main Findings

• Highest average detection performance per model. Table 2 reports that STELA achieves the highest average detection performance across the three languages for each of the three LLMs; the abstract states STELA surpasses prior methods in detection robustness.

• Strongest gains on Chinese and Korean. STELA secures the top TPR@5%FPR and Best F1 for Chinese and Korean across all tested LLMs. Examples: with Qwen-3 on Chinese, STELA reaches 0.996 TPR@5%FPR / 0.994 Best F1; with Llama-3.2 on Korean, 0.950 / 0.954; with HyperCLOVA on Korean, 0.960 / 0.960.

• With HyperCLOVA, STELA leads in all three languages. Reported figures are English 0.988 / 0.975, Chinese 0.932 / 0.942, Korean 0.960 / 0.960 (TPR@5%FPR / Best F1).

• English is the narrowest margin. With Llama-3.2 on English, STELA records 0.938 / 0.953 versus KGW's 0.950 / 0.963; the paper describes English as where "the performance margin is narrower" while STELA remains highly competitive.

• Text quality is comparable to baselines. Perplexity (measured with Llama-3.2-3B as an external reference model) for STELA appears statistically comparable to baselines. In an LLM-as-Judge pairwise blind A/B test, STELA was preferred or tied over KGW in 52.5% of 1,000 comparisons.

• Context length should follow typology. In the ablation on POS context size k, English is near-optimal at k = 2 and remains stable, while Chinese and Korean improve with k = 4.

• Robustness to tagset granularity. Using the coarser universal dependencies (UD) tagset, STELA still achieves high detection rates across all three languages. Language-specific tagsets improve performance, especially for Korean. Estimated mean indeterminacy E[λ(c_t)] is lower for language-specific tagsets than universal ones: English 0.575 vs 0.686, Chinese 0.523 vs 0.643, Korean 0.475 vs 0.647.

• The watermark lands where each grammar permits. For a representative model per language, the z-score contribution splits almost evenly in English between content words (43.1%) and function words (43.7%), while content words dominate in Chinese (67.1%) and Korean (74.4%).

• Resilience to synonym substitution. Under a WordNet synonym replacement attack with substitution rates from 10% to 50%, all models maintain a Best F1 above 0.85.

• Resilience to neural paraphrasing. Against the Dipper paraphrase attacker with lexical diversity L ∈ {10, 20, 40, 50} on English texts from Llama-3.2, Best F1 is 0.953 with no attack, 0.862 at L = 10, 0.869 at L = 20, 0.813 at L = 40, and 0.825 at L = 50.

• Model-free detection confirmed by design. Because the insertion and detection signals both come from a precomputed POS n-gram lookup table, the detector needs only a lightweight POS analyzer, not LLM logits.

Methodology in Plain English

The researchers first build a reference table for each language describing how predictable a POS tag is given the previous few POS tags. They estimate these conditional distributions from human-written corpora, sampling 10,000 documents from each of two corpora per language: the English Wikipedia subset and OpenWebText2 for English; the Chinese Wikipedia subset and Chinese C4 for Chinese; Korean C4 and KOREAN-WEBTEXT for Korean. They average the conditional probabilities from the two sources to reduce single-source bias, and tag with spaCy (Penn Treebank) for English, HanLP (Penn Chinese Treebank) for Chinese, and Kiwi (Sejong) for Korean. Normalizing the conditional entropy by log K_c_t yields λ(c_t), which approaches 1 when many grammatical options are plausible and 0 when syntax is tightly constrained.

Watermark insertion then follows the KGW recipe of splitting the vocabulary into green and red lists at each step, but replaces the fixed bias δ with δ · λ(c_t). Detection mirrors KGW: replicate the green lists, then compute a z-score — except the count is now a weighted sum, with each token's weight equal to λ(c_t) for its context, and the null-hypothesis expectation and variance derived from those weights.

Experiments use 500 randomly sampled instances per task: WritingPrompts for English creative story continuation, THUCNews for Chinese news continuation, and the Korean subset of Oscar for Korean web text continuation; the Chinese and Korean tasks use the first three sentences as prompts. All baselines are implemented through the open-source MarkLLM toolkit with γ = 0.5, δ = 2.0 for KGW, EWD, and SWEET, δ = 1.3 for MorphMark, and generation temperature 0.7. To keep the comparison fair, STELA's base strength is calibrated as δ = 2.0 / E[λ(c_t)], with E[λ(c_t)] estimated at 0.575 for English, 0.523 for Chinese, and 0.475 for Korean. Evaluation uses TPR@5%FPR, Best F1, and perplexity.

Why This Matters

Impact on research. The paper reframes the quality-versus-detectability trade-off: instead of treating the model's transient uncertainty as the reference signal, it treats the intrinsic syntactic structure of the language as the reference. That shift from model-specific to language-universal grounding is what makes public auditability possible, and it opens a route to watermarks that are interpretable in linguistic terms — the authors describe this as harmonizing AI systems with the foundational principles of human language. It also extends watermarking research beyond English by testing three typologically distinct languages.

Real-world applications:

• Regulatory compliance: the paper cites the EU AI Act requirement that providers make outputs of general-purpose AI models clearly identifiable, and positions STELA as a governance tool for that obligation.
• Platform content moderation: detecting machine-generated text that could be used for convincing disinformation at scale.
• Publishing and journalism verification: third parties could verify provenance with only a public hash function and a POS analyzer, without holding the model.
• Multilingual deployments: organizations operating in typologically different languages (as tested: English, Chinese, Korean) can apply the same framework rather than a separate method per language.

Industry relevance. Because detection needs no logits, a party auditing text does not need the model weights, the provider's cooperation, or access to proprietary inference infrastructure — an important practical property for third-party auditors, regulators, and downstream platforms. The method also runs on small models (0.5B–1B parameters), suggesting feasibility outside frontier-scale settings.

Future Directions

• Robustness to tagging errors. The method's effectiveness depends on the reliability of the POS tagger; tagging errors during detection may distort contextual reconstruction and cause missed watermark signals, so the paper calls for methods that enhance robustness against tagging inaccuracies.
• Richer quality evaluation. Current quality assessment relies on perplexity, which may not capture grammatical correctness, stylistic naturalness, or semantic coherence; the paper calls for more comprehensive metrics designed for watermarking's nuanced impact.
• Domain-adaptive predictability models. The λ signal is estimated from reference corpora, so when the generated text's domain diverges substantially from the corpus domain the weighting scheme may become suboptimal.
• Typological and low-resource coverage. The study covers analytic, isolating, and agglutinative types but not fusional or polysynthetic systems, and its dependence on high-quality POS taggers makes low-resource settings a pressing challenge; the universal dependencies results suggest a possible path, though effectiveness may be diminished where tagger performance is inherently low.
• Stronger adversarial resistance. Synonym substitution and Dipper paraphrasing were tested; heavier or structurally more aggressive attacks remain an open question, since the paper's testing of Dipper covered a single representative configuration (English texts generated by Llama-3.2).

Target Audience

Researchers working on LLM watermarking, text provenance, and AI-generated-text detection; NLP practitioners who need third-party-verifiable detection without model access; industry engineers and compliance teams addressing AI-output transparency requirements such as the EU AI Act; and computational linguists interested in how typological properties (analytic, isolating, agglutinative) shape the design of language technologies. Readers need comfort with information-theoretic entropy, n-gram statistics, and hypothesis testing to follow the method fully.

Authors’ abstract

As large language models (LLMs) continue to advance rapidly, reliable governance tools have become critical. Publicly verifiable watermarking is particularly essential for fostering a trustworthy AI ecosystem. A central challenge persists: balancing text quality against detection robustness. Recent studies have sought to navigate this trade-off by leveraging signals from model output distributions (e.g., token-level entropy); however, their reliance on these model-specific signals presents a significant barrier to public verification, as the detection process requires access to the logits of the underlying model. We introduce STELA, a novel framework that aligns watermark strength with the linguistic degrees of freedom inherent in language. STELA dynamically modulates the signal using part-of-speech (POS) n-gram-modeled linguistic indeterminacy, weakening it in grammatically constrained contexts to preserve quality and strengthening it in contexts with greater linguistic flexibility to enhance detectability. Our detector operates without access to any model logits, thus facilitating publicly verifiable detection. Through extensive experiments on typologically diverse languages-analytic English, isolating Chinese, and agglutinative Korean-we show that STELA surpasses prior methods in detection robustness. Our code is available at https://github.com/Shinwoo-Park/stela_watermark.