1 Introduction↩︎

Recent advances in large language models (LLMs) enable the generation of human-like text that can convincingly mimic genuine human writing, raising significant concerns about misinformation, impersonation, and unauthorized content reuse at scale [1], [2]. To address these risks, text watermarking has emerged as a crucial technique, embedding hidden but detectable signatures into generated content, thereby enabling reliable identification of AI-generated text without compromising readability.

Various approaches have been proposed to embed statistical or encrypted patterns into generated text by selecting tokens based on specific underlying rules. However, these token-level methods [3]–[6] remain highly sensitive to paraphrasing and synonym substitutions, making the watermark easily undetectable after minor text modifications. To address these limitations, recent methods have shifted towards sentence-level watermarking, embedding signals within the semantic embedding space using techniques such as locality-sensitive hashing [7] or k-means clustering [8]. While these sentence-level approaches improve robustness—meaning the watermark remains detectable even after paraphrasing—they can still fail if paraphrasing shifts the sentence embedding.

In this paper, we introduce SWAN (Semantic Watermarking with Abstract Meaning Representation), a novel watermarking approach that embeds watermark signatures directly into the semantic structure of generated sentences. Unlike previous token-level or embedding-based approaches, SWAN leverages Abstract Meaning Representation (AMR) [9], [10], a graph-based formalism capturing core semantic relationships. By embedding watermark signals at the AMR graph level—for example, requiring a sentence to contain specific combinations of entities and relationships—SWAN ensures that any paraphrase preserving the underlying meaning will inherently retain the watermark. Anchoring the watermark to the semantic structure substantially enhances robustness to paraphrasing attacks, addressing a key limitation of prior methods while maintaining high detectability and text quality.

We validate the effectiveness and robustness of SWAN through extensive empirical evaluation on the RealNews dataset [11], a standard benchmark for sentence-level watermarking. Our experiments benchmark SWAN against state-of-the-art token-level and sentence-level watermarking baselines, assessing detectability under various paraphrase attacks. Results demonstrate that SWAN achieves detection accuracy comparable to state-of-the-art sentence-level watermarking methods and outperforms token-level watermarking techniques on unaltered text. More importantly, SWAN significantly enhances robustness under paraphrasing, consistently outperforming existing sentence-level approaches when detecting paraphrased text. Although watermarking generally introduces a trade-off in text quality, SWAN maintains text coherence, fluency, and diversity comparable to existing methods, as evaluated through a thorough LLM-based quality assessment.

To the best of our knowledge, this work represents the first exploration of Abstract Meaning Representation in the text watermarking domain, opening a new technical pathway based on symbolic semantic structures.

2 Background↩︎

2.1 Abstract Meaning Representation (AMR)↩︎

Abstract Meaning Representation is a graph-based formalism that encodes the core semantic structure of a sentence by abstracting away surface-level syntactic and lexical variations [9], [10]. Nodes in the graph represent concepts (e.g., entities, events), while edges capture semantic relations (e.g., agent, patient, location).

For instance, the sentences below, despite their surface-level differences, share the same core semantic meaning and therefore map to an identical AMR graph [12]:

• “The boy desires the girl to believe him.”

• “The boy desires to be believed by the girl.”

• “The boy has a desire to be believed by the girl.”

• “The boy’s desire is for the girl to believe him.”

These sentences correspond to the following AMR graph representation:

(w / want-01
   :ARG0 (b / boy)
   :ARG1 (b2 / believe-01
             :ARG0 (g / girl)
             :ARG1 b))

Figure 1 provides a visual depiction of this AMR structure, clearly illustrating the semantic relationships captured by the graph representation.

By representing semantic structures explicitly, AMR provides an effective means for embedding robust watermark signals that remain intact even when sentences undergo significant lexical and syntactic modifications, as long as the core meaning remains unchanged.

2.2 Text Watermarking↩︎

Text watermarking refers to techniques that embed subtle but identifiable signatures into text to allow verification of its provenance or authorship. Depending on the granularity at which the signal is embedded, watermarking methods can be broadly classified into token-level, sentence-level, and paragraph-level approaches.

2.2.0.1 Token-Level Watermarking.

Token-level schemes watermark text by subtly biasing the sampling distribution during decoding, so that the hidden statistical signature can later be detected [3]–[6], [13], [14]. A widely used design is the green-list / red-list framework of [3], which partitions the vocabulary with a secret hash and forces generation to prefer the green tokens, enabling a simple \(z\)-score detector. Subsequent variants add provable robustness guarantees [4], enforce distortion-free constraints [6], or optimize the logits with a learned key to balance invisibility and detectability, as in SynthID-Text [14]. Although straightforward, token-level methods remain fragile to paraphrasing and other surface edits, and they typically require direct access to model logits—an assumption that may not hold for proprietary LLMs.

2.2.0.2 Semantic and Sentence-Level Watermarking.

To enhance robustness against paraphrasing, recent strategies encode signals into the semantic space rather than superficial token statistics. [7] and [8] partition the embedding space using locality-sensitive hashing (LSH) or \(k\)-means to selectively sample sentences from “watermarked” regions. Similarly, [15] train a neural network to map context embeddings directly to watermark logits, while [16] discretize the continuous embedding space to robustly seed vocabulary partitioning. Although these embedding-based methods better resist small lexical changes, paraphrasing that moves the sentence embedding out of the designated region still degrades detectability.

2.2.0.3 Paragraph-Level and Post-hoc Watermarking.

Another line of research explores embedding watermark signals at the paragraph level or injecting them post-generation in a black-box manner. PostMark [17] exemplifies this by first encoding the semantic content of an entire paragraph, then selecting specific “watermark words” from a secret embedding table that an instruction-following LLM weaves into the existing text. Detection re-computes the expected word list and flags a paragraph when enough of the words (or close semantic neighbors) appear. While practical and model-agnostic, these methods introduce explicit lexical edits, making them potentially detectable or removable by sophisticated adversaries.

Our work diverges from these prior paradigms by embedding explicit watermark signatures directly into the semantic structure of sentences using Abstract Meaning Representation (AMR) graphs. This novel semantic anchoring approach provides robust detection under paraphrasing, addressing key limitations of existing token-level and embedding-based watermarking methods.

3 Overview of the Framework↩︎

SWAN embeds a sentence-level watermark by guiding each generated sentence to match a template AMR randomly drawn from a secret bank. During generation, sentences are produced conditioned on the accumulated context while adhering to the selected AMR template’s semantic structure. Detection parses candidate text back to AMRs, counts template matches, and applies a one-proportion \(z\)-test over the paragraph. Figure 2 summarizes the three components outlined below.

3.1 AMR Bank Creation↩︎

We begin by constructing a bank \(\mathcal{B}\)—a private collection of template AMR graphs that serves as the secret key for both watermark injection and detection. SWAN draws one template from this bank for each sentence to be generated.

3.1.0.1 Raw corpus.

We start from MASSIVE-AMR [10]⁵, which provides \(\sim\)​84 K AMR graphs for 1,685 information-seeking utterances.

3.1.0.2 Template AMR.

We further abstract raw AMRs into template AMRs by replacing nouns (e.g., specific named entities) with generic placeholders. This additional level of abstraction removes extraneous lexical details while retaining the underlying semantic structure. For example, a raw AMR node labeled “Alice” might become a placeholder “NE,” ensuring that the resulting template AMR focuses on conceptual and relational information rather than domain-specific references. Using these template AMRs confers two main benefits: (i) Generality: A small number of template AMRs can map to a wide variety of sentence instantiations, since names or entities can be filled in later with context-appropriate text. (ii) Robustness: By stripping away specific entity mentions, we decrease the chance that minor lexical edits (e.g., changing “Alice” to “Mary”) will disrupt the watermark’s core semantics.

3.1.0.3 Selecting AMR Patterns.

To populate the template bank, we traverse the full MASSIVE-AMR corpus and retain only those graphs that (a) occur within a specified frequency range, defined by a minimum frequency of three and a maximum frequency of twenty, effectively discarding both one-off idiosyncrasies and highly repetitive boilerplate, and (b) contain at least three concept nodes to guarantee non-trivial semantic content.

3.2 Watermark Injection↩︎

3.2.0.1 Sentence-Level Guidance.

For each sentence to be generated, we draw a template AMR \(g\) from the bank and prompt the LLM with two inputs: (1) the accumulated context from previously generated sentences for discourse coherence, and (2) the template \(g\) with instructions to generate text adhering to its semantic structure. The accumulated context carries forward the intent from the original user prompt or task specification that initiated the generation. The prompt guides the model to instantiate abstract AMR concepts (e.g., replacing “NE” placeholders with appropriate named entities) while maintaining contextual flow and alignment with the user’s original intent (full prompt in Appendix 7.1). The candidate sentence is then parsed back into an AMR \(\hat{g}\).

3.2.0.2 S2match-guided rejection.

For every candidate sentence generated, we parse its AMR \(\hat{g}\) and compute the S2match similarity to the target template \(g\)—a lightweight metric that averages node- and edge-level \(F_{1}\) scores and ranges from 0 (no overlap) to 1 (perfect match) [18]. The sentence is accepted only if \(\text{S2match}(\hat{g}, g) \ge \theta_{\text{accept}}\); otherwise we discard it and resample.

3.2.0.3 Adaptive target switching.

Because generation is conditioned on running discourse, certain templates may be semantically infeasible in a given context or for a given prompt. Rather than retrying an incompatible template indefinitely, we impose a small cap on resampling attempts; if the threshold is reached, we simply draw a new template at random from the bank and resume decoding.

3.3 Watermark Detection↩︎

Given a piece of text of unknown provenance, we determine whether it was produced by SWAN in three steps:

1. AMR Parsing: Convert each sentence into an AMR graph using an off-the-shelf AMR parser.

2. Pattern Matching: For the parsed graph \(\hat{g}\) we compute \(\max_{g \in \mathcal{B}}\text{S2match}(\hat{g}, g)\), the best similarity to any template in the bank \(\mathcal{B}\). The sentence is labelled watermarked if this score exceeds a fixed threshold \(\theta_{\text{detect}}\).

3. Paragraph test (one-proportion \(z\)-test). If \(k\) of the \(n\) sentences in a paragraph are flagged, we compute: \[z \;=\; \frac{\;k - \lambda n\;}{\sqrt{\,n\lambda(1-\lambda)\,}},\] where \(\lambda\) is the expected hit-rate under the null hypothesis:

   \(H_{0}:\)
   The text is not generated (or written) knowing the secret AMR bank.

Because paraphrasing typically preserves semantic structure, the AMRs remain consistent even when surface forms differ, ensuring that our watermark remains detectable unless meaning has been fundamentally altered.

4 Experiments↩︎

4.1 Experimental Setup↩︎

4.1.0.1 Dataset.

Following the SemStamp baseline, we evaluate on the RealNews subset of the C4 corpus [11]. RealNews consists of professionally written news articles and has become the de-facto test bed for sentence-level watermarking because its formal style reduces noise from ill-formed user content. We take the first 250 sentences of the subset as our evaluation set.

4.1.0.2 AMR-bank size.

A “bank” is the private set of template AMRs from which SWAN draws one template per sentence. Its size \(|\mathcal{B}|\) therefore controls the search space for both injection and detection. All results reported in Sec. 4 use a 50-template bank (\(|\mathcal{B}|{=}50\)); Sec. 4.3 shows that performance is stable for larger banks up to 800 templates.

4.1.0.3 Models.

We use the following models for each component in SWAN:⁶

• Watermark Generation. All watermark injection is performed with DeepSeek-R1-Distill-Qwen-14B (temperature: 0.6, top_p: 0.9).⁷ SWAN employs rejection sampling capped at 50 trials per sentence (5 attempts per AMR template across up to 10 templates), compared to SemStamp’s 100 trials per sentence.

• Watermark Detection. SWAN parses sentences with the parse_xfm_bart_large pipeline from amrlib[19], a BART-large encoder–decoder trained on AMR-3 (LDC2020T02).

• Paraphrase Generation. We create attacks with three paraphrasers—Pegasus, Parrot, and Claude 3.7 Sonnet.

• Text-Quality Evaluation. Claude 3.7 Sonnet is used, in a zero-shot setting, to rate coherence, fluency, and diversity of the generated text.

4.1.0.4 Baseline methods.

We benchmark SWAN against the strongest publicly–available watermarking approaches: (i) SynthID-Text. SynthID-Text [14] is a production-ready token-level watermark that perturbs the next-token distribution during decoding. (ii) SemStamp. SemStamp partitions the sentence-embedding space with the random-hyperplane through locality-sensitive hashing (LSH) [20] and keeps only sentences whose LSH code falls in a secret “green” bucket [7]. (iii) k-SemStamp. k-SemStamp [8] keeps the same accept/reject scheme but swaps the random-hyperplane LSH for \(k\)-means centroids learned from in-domain text, so regions follow real semantic structure which boosts paraphrase robustness.

4.1.0.5 Paraphrase attacks.

Watermark robustness is evaluated under three paraphrasers: (i) Pegasus. Pegasus [21] is a model fine-tuned for paraphrasing.⁸ (ii) Parrot. Parrot [22] is a T5-base paraphraser that seeks high lexical diversity while preserving semantics. (iii) Off-the-shelf LLM. We use Claude 3.7 in a zero-shot setting instructed to rewrite the given sentence while preserving semantic meaning.

4.1.0.6 Evaluation metrics.

We measure two orthogonal aspects: (i) watermark quality—how well the detector distinguishes watermarked text from non-watermarked text—and (ii) text quality of the watermarked output itself.

• Watermark detectability. We report three complementary metrics at the paragraph level (i.e., generate 5 new sentences given one sentence as initial context): (i) AUC, the area under the ROC curve, capturing overall separability between watermarked and non-watermarked text; (ii) TPR@1% and (iii) TPR@5%, the true positive rates at fixed false positive rates of 1% and 5%, which reflect detector performance in the low-FPR regime most relevant to deployment.

• Text quality. We use Claude 3.7 as the judge and record scores on three axes: Coherence, Fluency, and Diversity. Detailed definitions of these quality dimensions and the complete evaluation prompt are provided in Appendix 7.3.

4.2 Detection Results↩︎

4.2.0.1 Baseline performance (no paraphrase).

Table 1 reports paragraph-level AUC on the RealNews set without any rewriting. SWAN matches the sentence-level competitor and outperforms the token-level SynthID watermark, demonstrating that our semantic approach entails no loss of raw detectability.

4.2.0.2 Robustness to paraphrasing.

Table 2 shows the same evaluation after applying three paraphrasers. SynthID is omitted as SWAN outperforms it even in the non-paraphrasing scenario and its token-level cues are wiped out by even mild rewriting. Across all attacks, SWAN attains the highest AUC, confirming that anchoring the watermark in AMR graphs yields markedly stronger resilience than embedding-partition methods.

4pt

4.3 Effect of AMR-Bank Size↩︎

5pt

We further ablate the bank size, i.e., the number of AMRs in \(\mathcal{B}\). Intuitively, a larger bank provides greater semantic coverage, so the watermark can be embedded across more diverse AMR patterns. However, this also raises the possibility of false positives, since any human-written sentence that incidentally aligns with one of many templates may be flagged. Table 3 shows that while a bank of 800 AMRs yields the highest AUC (99.3%), even a much smaller bank (50 AMRs) maintains strong performance (99.1%). This indicates that SWAN is robust to different bank sizes, allowing practitioners to balance coverage and efficiency when deploying the watermark.

4.4 Text Quality Evaluation↩︎

To assess whether embedding a watermark affects generated text quality, we used a large language model (LLM) as an automated “reference-free” judge [23], rating paragraphs on a \([0,5]\) scale along three dimensions: (i) Coherence (logical organization and clarity), (ii) Fluency (grammatical correctness and readability), and (iii) Diversity (variety of vocabulary and sentence structures).

Table 4 compares text generated without watermarking (“No Watermark”) against three watermarking methods: SWAN, SemStamp, and k-SemStamp. Results indicate that while watermarking introduces a slight decrease in quality scores across all dimensions compared to the un-watermarked baseline, SWAN performs comparably to existing sentence-level watermarking methods. Thus, SWAN achieves strong paraphrase robustness (as demonstrated in §4.2) without introducing additional penalties in text coherence, fluency, or diversity relative to current state-of-the-art approaches.

4.5 Qualitative Examples↩︎

Table 5 provides illustrative examples of paragraphs generated by each watermarking method (SWAN, SemStamp, and k-SemStamp). For each method, we present one High-quality example and one Low-quality example based on the LLM-judged coherence, fluency, and diversity scores (§4.4), highlighting the typical range of output quality observed in practice.

4.6 Sampling Efficiency↩︎

Like other sentence‑level algorithms, SWAN relies on rejection sampling. Across 1,250 generated sentences (250 \(\times\) 5) we measured a mean of 17.7 trials before acceptance, versus 13.8 trials for SemStamp. Figure 5 shows the full trial distribution: 42% of sentences are accepted within 10 trials and 54% within 15, confirming that the majority of generations converge quickly. The spike at 46–50 trials corresponds to sentences that exhausted the budget, suggesting that certain AMR templates are harder to satisfy in context; future work on context-aware template selection could reduce these cases and further improve efficiency. While the overall overhead is modest, it is offset by SWAN’s significantly enhanced robustness to paraphrasing—our primary contribution—achieving up to 13.9 percentage points higher detection AUC (Table 2). SWAN remains training-free and works via pure prompting and AMR parsing.

5 Related Work↩︎

5.0.0.1 Other semantic signatures.

Early linguistic steganography embeds bits by rewiring surface structure. [24] propose two algorithms that hide information in the parse tree of selected sentences, modifying syntactic branches and then regenerating fluent text with an NLG system. More recently, [25] advance to a multi-bit framework that encodes a larger payload in invariant features—lexical or syntactic patterns shown empirically to survive minor text corruption. Complementary to these text-side schemes, [26] “plant” a watermark inside the model itself by backdooring PLM weights with rare-word or composite triggers; ownership is verified by querying the model rather than analyzing the generated text.

5.0.0.2 Authorship attribution.

Stylometric methods seek to infer the writer’s identity from persistent linguistic habits rather than from an injected signal. Classic surveys document feature-rich classifiers that use function-word counts, character \(n\)-grams, and syntactic cues [27], [28]. Neural models learn style embeddings end-to-end, from continuous character \(n\)-grams [29] to the contrastively-trained PART Transformer [30]. Because these approaches rely on labelled samples for every author and can be defeated by paraphrase or adversarial style obfuscation [31], they do not provide a verifiable yes/no provenance test.

6 Conclusion↩︎

We introduced SWAN, a novel semantic watermarking framework that embeds robust, paraphrase-resistant signals into AMR representations. By guiding generated text to align with curated AMR templates, SWAN remains detectable under paraphrasing as long as core semantic relationships are preserved. Empirically, it outperforms token-level and embedding-based watermark baselines in paraphrase robustness, while maintaining strong text fluency and naturalness.

6.0.0.1 Future Directions.

We believe this work opens new directions for semantic-level watermarking research. Improving sampling efficiency represents a key practical direction, potentially through heuristic template selection, AMR-aware language model fine-tuning, or learned template-context matching to reduce rejection sampling overhead. Beyond efficiency, promising research avenues include exploring domain-specific AMR adaptations, improving parser robustness, and strengthening detection against advanced adversarial rewrites. Additionally, investigating how watermarking methods in general—including our AMR-based approach—might impact the reasoning capabilities of LLMs across different task domains represents an important area for future exploration. While SWAN currently focuses on the sentence level, multi-sentence attacks—such as splitting or merging sentences to alter AMR structure—represent a natural next challenge that could be addressed by extending to paragraph-level or multi-sentence AMRs. Another intriguing direction lies in using AMR subgraphs as watermark signals, offering additional resilience when adversaries deliberately reorganize semantic structures.

Limitations↩︎

Our detection relies on the quality of the AMR parser, which can occasionally misparse text or introduce random variations. Such errors may reduce recall by pushing a genuine SWAN sentence below the similarity threshold, or increase false positives if they inflate similarity to a template.

We focused on English news text for evaluation, where well-trained AMR parsers and public corpora are available. In domains with highly specialized jargon or in languages with limited AMR resources, accuracy and detectability might degrade, necessitating more domain-specific or multilingual AMR tools.

In our framework, the AMR bank \(\mathcal{B}\) functions as the private key; its secrecy is required to prevent adversary detection. Future work may explore enhancing this security by integrating cryptographic protocols to manage template selection, similar to secret-key hashing in token-level schemes.

Ethical Considerations↩︎

Watermarking systems, including ours, come with both benefits and risks. On the one hand, they can help combat large-scale misinformation by allowing credible attribution of AI-generated content. On the other hand, false positives could arise if a text happens to align closely with the AMR templates by chance or if the AMR parser errs, potentially mislabeling human-authored text as AI-generated. This risk is especially salient in low-resource languages or domains where AMR parsers are less accurate, raising concerns about fairness and potential bias. Furthermore, mandated watermarking in certain contexts could impede free expression or privacy if applied too broadly. Finally, while our method robustly identifies paraphrases, adversaries may develop sophisticated rewriting strategies to remove the watermark, highlighting the possibility of an ongoing arms race. We encourage responsible use, transparency about these limitations, and continued research to refine watermarking techniques and their governance.

Acknowledgments↩︎

We thank Dipika Khullar for her contributions to the text quality evaluation experiments. We also thank Richard Zemel for valuable discussions during the course of this work.

7 Appendix↩︎

7.1 Prompt for text generation with watermark↩︎

AMR (Abstract Meaning Representation) is a graph-based representation of a sentence's meaning. Each node is a concept and edges represent semantic roles or relationships. Below are some examples of template AMRs and corresponding sentences:
{example_text}

In the provided AMR, there are placeholders:
- "NE" for named entities (e.g., "Alice", "France", "Google").
- "N" for generic nouns (e.g., "a device", "an object").
- "X" for unspecified concepts (e.g., "something", "an idea").

Instructions:
- Do not write "NE", "N", or "X" literally. Instead, replace them with appropriate English words to form a natural, meaningful sentence.
- Ensure the generated sentence aligns with both the AMR structure and the given context.
- Do not produce multiple sentences or lists.
- Produce exactly one coherent sentence.

AMR:
{chosen_template}
Context: {context}
Please output only that one sentence.

7.2 Prompt for zero-shot Claude paraphrase↩︎

Previous context: {' '.join(context)}
Current sentence to paraphrase: {sent}
Rewrite the sentence above while preserving its meaning.
Do not provide any explanation or extra commentary.
Return only the new sentence.

7.3 Prompt for LLM-as-a-Judge Text Quality Evaluation↩︎

You are an expert writing quality evaluator.

You will assess a GENERATED PARAGRAPH using the following criteria. For each, assign a score from 1 to 5 (decimals allowed), using the descriptions below.

1. **Coherence**: Measures how logically and clearly the ideas are organized and connected.
   - 1: Incoherent; sentences are unrelated or confusing.
   - 2: Poor transitions or unclear relationships between ideas.
   - 3: Basic logical flow, but some awkward connections.
   - 4: Mostly logical and clear, with minor lapses.
   - 5: Highly logical and seamless flow of ideas.

2. **Fluency**: Assesses the grammatical correctness and naturalness of the language.
   - 1: Grammatically broken or unreadable.
   - 2: Understandable but awkward or error-prone.
   - 3: Generally readable, some minor grammatical errors or odd phrasing.
   - 4: Well-written with only occasional issues.
   - 5: Grammatically correct and naturally flowing throughout.

3. **Diversity**: Use of varied vocabulary and sentence structure, avoiding repetition.
   - 1: Extremely repetitive or formulaic.
   - 2: Some repetition with occasional variation.
   - 3: Moderate variety; not monotonous.
   - 4: Good diversity in language and structure.
   - 5: Highly expressive and varied without redundancy.

**Scoring Instructions**:
- Return a score for each of the three dimensions above.
- You may use decimal values (e.g., 2.5, 4.7).

**Output Format**:
Respond with a **valid JSON object only** in this exact format:

{{
  "coherence_score":  float,
  "fluency_score":    float,
  "diversity_score":  float
}}

References↩︎