Toward Stronger Code Watermarking: A Grammar-Driven Approach to Optimizing the Trade-off Between Quality and Detectability

TLDR

• What: Grammar-Driven Watermarking (GDW) preserves syntactic correctness in LLM-generated code using context-free grammars (CFGs) and adjusts watermark strength based on the structural roles of tokens (syntax-critical vs. content-bearing).
• Who's at risk: Enterprise code-generation pipelines, AI coding assistants (e.g., Copilot, Cursor, Claude Code), and open-source compliance frameworks trying to track intellectual property or detect machine-generated code without breaking compilability.
• Key number: GDW achieves an Area Under the Trade-off Curve (AUTC) of up to 0.951 (Qwen2.5-Coder-3B on HumanEvalPack-Go), outperforming standard KGW by up to 0.116 points on low-entropy code generation benchmarks.

In recent years, large language models (LLMs) have become indispensable tools for code generation, powering popular coding assistants like GitHub Copilot, Cursor, and Claude Code. However, as AI-generated code increasingly integrates into open-source projects and proprietary codebases, concerns over licensing, copyright infringement, and provenance have surged.

Traditional text watermarking methods, which subtly bias token selection to leave statistical footprints, struggle when applied to code. Because programming languages are inherently low-entropy (governed by rigid syntax and predictable structures), naively modifying output logits often breaks compilability, degrades code quality, or fails to embed a detectable signature. GDW attempts to solve this by making the watermarking process explicitly aware of code grammar and token functionality.

Threat Model

Background & Problem Setup

The primary challenge in code watermarking is the low-entropy nature of programming languages. As shown in Figure 2 of the paper, syntax-critical tokens (like keywords and operators) consistently exhibit significantly lower mean token entropy (e.g., 0.419 on MBPP+ with Qwen2.5-Coder-3B) compared to content-bearing tokens (like variable identifiers, which average 0.649 on the same dataset).

When standard logits-based watermarks apply uniform biases across all tokens, they risk corrupting these highly deterministic, syntax-critical positions, causing syntax errors. Conversely, entropy-based baselines that simply skip low-entropy tokens lose valuable opportunities to embed watermark signals, degrading detectability.

The following table compares the GDW approach with existing methods cited in the paper:

Methodology

GDW mitigates the trade-off between code quality and watermark strength through a three-step generation framework and an aligned, weighted detection mechanism.

                  +--------------------------+
                  |    Input Prefix Code     |
                  +-------------+------------+
                                |
                                v
               +----------------+---------------+
               |    Incremental CFG Parsing     |
               +----------------+---------------+
                                |
                                v
         +----------------------+----------------------+
         |                                             |
         v                                             v
+--------+--------+                           +--------+--------+
| Syntax Validity |                           | Greenlist Split |
| Mask (Msyn)     |                           | Mask (Mwm)      |
+--------+--------+                           +--------+--------+
         |                                             |
         +----------------------+----------------------+
                                |
                                v
                  +-------------+------------+
                  |  Eligibility Mask (Melig)|
                  +-------------+------------+
                                |
                                v
             +------------------+------------------+
             | Structural Role Modulation (Mrole)  |
             | - Weak bias (\delta) for Syntax     |
             | - Strong bias (\lambda*\delta)      |
             |   for Content Tokens                |
             +------------------+------------------+
                                |
                                v
                  +-------------+------------+
                  |    Watermarked Logits     |
                  +--------------------------+

Step 1: Three-Level Masking Mechanism

At each decoding step $t$, GDW constructs three binary masks over the vocabulary $V$ to determine where a watermark can be safely applied:

1. Watermark Greenlist Mask ($M_{wm,t} \in \{0, 1\}^{|V|}$): Partitions the vocabulary based on a hash of the preceding token $x_{t-1}$ (following standard KGW).

2. Syntactic Validity Mask ($M_{syn,t} \in \{0, 1\}^{|V|}$): An incremental parser evaluates the current prefix against Context-Free Grammar (CFG) rules in EBNF format, identifying the set of syntactically admissible next tokens $A_t$.

3. Eligibility Mask ($M_{elig,t}$): Merges both constraints via element-wise multiplication:

   $$$$

Melig,t = Mwm,t \odot Msyn,t

r(v) = \begin{cases} 1, & \text{if } v \in V_{syntax} \ \lambda, & \text{if } v \in V_{content} \end{cases}

l'_t = l_t + Melig,t \odot (Mrole + \lambda \cdot (1 - Mrole)) \cdot \delta

z = \frac{\sum_{t=2}^T w_t I_t - \gamma \sum_{t=2}^T w_t}{\sqrt{\gamma(1 - \gamma) \sum_{t=2}^T w_t^2}}