Constructing Budgeted KGW Evasion through Token-Event Evidence Replacement

Hongliang LiuarXiv 2026 · arXiv

This paper explores the limits of LLM watermarking by demonstrating how a "blind" editor—one who doesn't have the secret key or access to a detector—can systematically evade detection while staying within a strict token-edit budget. By treating evasion as a structural optimization problem, the author shows that nearly half of watermarked passages can be successfully disguised using ordinary phrase rewrites without sacrificing text quality.

TL;DR

The researchers developed a method to evade KGW watermarks by strategically replacing "watermark-enriched" token sequences with ordinary phrase rewrites. By maximizing the removal of original token pairs within a 20% edit budget, they achieved a ~48% success rate in evading detection while maintaining high prose quality.

What Problem Does This Paper Address?

Large Language Model (LLM) watermarking, such as the widely studied KGW (Kirchenbauer et al.) scheme, works by slightly biasing the model's token selection toward a "green" vocabulary determined by a secret key and the preceding token context. Detectors can then identify AI-generated text by looking for a statistically significant excess of these "green" tokens.

While previous work has shown that heavy paraphrasing can break these watermarks, this paper asks a more precise question: Can we evade detection using only localized, ordinary edits while staying under a strict "token-edit budget"? This is a difficult constrained optimization problem because tokenization boundaries often don't align with word boundaries, and changing one token can alter the context (and thus the "color") of subsequent tokens.

Methods

The author proposes a construction called Budgeted Token-Event Evidence Replacement. The process works as follows:

  1. Proposal Generation: An independent LLM (GPT-5.6 Luna) is given the watermarked source text and asked to provide two localized rewrites for several spans (e.g., changing "exposed grave misconduct" to "revealed serious misconduct").
  2. Mechanical Filtering: The system checks these proposals for basic quality: they must round-trip through the tokenizer correctly, stay within length limits, and preserve key lexical anchors (like numbers or names).
  3. Joint Selection (The Core Algorithm): The system uses a dynamic programming approach to find the combination of these local rewrites that removes the maximum number of original token pairs (the "events" the detector scores) for a given global edit distance budget (e.g., 5%, 10%, 15%, or 20% of the total tokens).
  4. Blind Operation: Crucially, the editor performs this selection without the secret key, without detector feedback, and without access to the original model's probabilities. It relies purely on the structural goal of removing original token pairs.
This schematic illustrates how a simple phrase replacement changes the underlying token events, potentially replacing "green" (G) tokens with "red" (R) ones.

Datasets

  • Prompts: Derived from the C4 (Colossal Clean Crawled Corpus).
  • Source Generation: Qwen2.5-1.5B-Instruct was used to generate 128 watermarked passages (continuations of the C4 prompts).
  • Rewrite Provider: GPT-5.6 Luna (at low reasoning effort) proposed the alternatives.
  • Quality Review: GPT-6.1 Sol acted as a blinded reviewer to ensure the rewrites preserved the original meaning and fluency.

Key Insights and Ideas

  • Removal is the Driver: The paper finds that successful evasion is driven primarily by removing the original "green-enriched" source events rather than the accidental introduction of "red" tokens in the new text.
  • The Theoretical Floor: The author derives a necessary token budget for evasion: to escape a watermark with an initial margin $M_0$, you generally need an edit budget $q \ge \lfloor M_0/2 \rfloor + 1$.
  • Trace-Based Estimation: Even without the key, the initial strength of a watermark ($Z_0$) can be estimated from generation traces (logits) with a high correlation (0.793). However, the study found that this aggregate information didn't necessarily help in allocating edits more efficiently than simple structural removal.
  • Localized Impact: Evasion doesn't require rewriting the whole text. As shown in Figure 1, a few strategic changes can drop the cumulative detector score below the threshold.
Figure 1 shows how three localized phrase changes (b) successfully drop the cumulative KGW score (a) from 6.290 to 3.973, crossing the detection threshold of 4.

Key Results

  • Escape Rate: At a 20% edit allowance, the method achieved 39/82 (47.6%) relative-quality-qualified escapes.
  • Efficiency: The mean actual cost for these successful escapes was 15.96% edits.
  • Quality Preservation: Of the 40 raw escapes at the 20% budget, 39 passed the relative quality review, and 34 passed a stricter "polished" review.
  • Budget Sensitivity: Most successful escapes were found by the 15% budget mark; increasing the budget to 20% only yielded a few additional successes.

Limitations and Future Work

  • Setting Specificity: The study focused on the original "one-token-context" KGW configuration. The effectiveness of this attack on more modern watermarks with larger context windows or different seeding rules remains to be seen.
  • The Stopping Problem: While the "largest-dose" rule (using the full budget) works, a blind editor still struggles to identify the minimum necessary edit to escape. Many passages could have escaped with much smaller edits (median ~5.7%) if the editor had detector access.
  • Model-Based Review: Quality was assessed by an LLM (GPT-6.1 Sol). While rigorous, this does not perfectly substitute for human judgment of nuance and factual grounding.
  • Short Passages: The evaluation was conducted on relatively short passages (median length of 85 tokens). The dynamics of budgeted evasion on much longer documents may differ.

Summary updated

Abstract

KGW watermarks bias sampling to accumulate keyed detection evidence. We construct budgeted evasion through token-event evidence replacement using ordinary phrase rewrites. Our construction jointly selects compositions of LLM-proposed alternatives from an independent model and measures global token-edit distance on complete outputs. At the largest attainable cost within the budget, exact coverage search maximizes removal of original scored token pairs. It uses a known tokenizer without the key, detector feedback or queries to the watermarked model. Exact accounting separates source evidence removed, evidence created and length effects, with initial strength setting the required reduction. Separate signed-event analysis found that mean suppression arose mainly from removing watermark-enriched source events. In controlled, occurrence-counted, one-token-context KGW tests on short passages, 39 of 82 qualified, initially detected sources yielded rewrites with terminal detector score Z < 4 that passed blinded source-relative model review, at a mean actual token-edit cost of 16.0% under a 20% allowance. To examine whether this initial requirement can be inferred, a separate historical 95-passage study estimated initial detector score Z0 from generation traces with correlation 0.793 and an in-sample association beyond length. This aggregate information did not establish improved allocation, and the separate no-trace stopping test did not reliably exploit cheaper reviewed crossings in the candidate bank. Comparisons did not establish an advantage over simpler selection and ordinary constrained rewriting. The construction makes budgeted evidence replacement executable while exposing limits in signed reduction and recognition of sufficient editing.
BibTeX
@misc{liu2026constructing,
  author = {Hongliang Liu},
  title = {{Constructing Budgeted KGW Evasion through Token-Event Evidence Replacement}},
  year = {2026},
  eprint = {2611.00726},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.00726},
}
Figure