Hidden in Plain Tokens: Simply Robust, Gradient-Free Watermark for Synthetic Audio

Image generated by AI

TLDR

• What: A gradient-free, training-free audio watermarking technique that clusters neural codec vocabularies using graph community detection (Leiden algorithm) to make token-level watermarks invariant to non-idempotent retokenization errors.
• Who's at risk: Synthetic audio generation platforms, deepfake detection APIs, and provenance tracking systems deploying continuous-modality autoregressive models (e.g., Moshi, MusicGen, CosyVoice3, Spark-TTS).
• Key number: Boosts watermark detectability under identity verification by several orders of magnitude, achieving a statistical confidence score of $-\log(p) = 42.47$ on Moshi conversational audio compared to $8.51$ for the baseline KGW method, while maintaining zero gradient-training overhead.

As synthetic speech and generative music systems reach human parity, the line between authentic and AI-generated audio is almost completely gone. For security teams, red-teamers, and AI safety researchers, content provenance is now a critical battleground. While inference-time token-level watermarking—pioneered by Kirchenbauer et al. (ICML 2023) for Large Language Models—has proven highly effective for discrete text, applying it directly to continuous modalities like audio has been a massive failure.

The core issue lies in the non-idempotence of neural audio codecs (such as Mimi or EnCodec). When a watermarked audio waveform is generated, the underlying tokens are synthesized into a continuous waveform. When a validator attempts to detect the watermark, they must re-tokenize this waveform. However, because codecs prioritize perceptual reconstruction quality over exact index preservation, this re-tokenization step introduces significant index mismatches. This "retokenization noise" completely degrades the fragile watermark signal.

In a new paper presented at ICML 2026, Milis et al. (ICML 2026) introduce "Hidden in Plain Tokens," an elegant, gradient-free watermarking defense. Instead of resorting to computationally expensive neural codec fine-tuning, the authors discover that retokenization errors are highly structured and consistent. By modeling the codec vocabulary as a graph and applying community detection, they cluster frequently-confused tokens into stable "semantic communities," applying the watermark bias at the cluster level rather than the individual token level.

Threat Model

The evaluation of this watermarking scheme is framed around an attacker attempting to strip or evade synthetic audio detection while the defender attempts to retain highly reliable detection capabilities.

Background & Problem Setup

To understand why traditional token-level watermarking fails on audio, consider the standard Kirchenbauer et al. (ICML 2023) (KGW) text watermark. At each autoregressive step, a hash of the preceding $h$ tokens pseudo-randomly splits the vocabulary $V$ into a "green list" $G$ and a "red list" $R$ with a green list ratio $\gamma \in (0,1)$. The logits of the green list tokens are biased by a constant offset $\delta > 0$ to encourage their selection.

For text, the token match rate (TM) under re-tokenization is essentially $1.0$. For continuous audio codecs, however, the token match rate$r = \text{TM}(y_{1:N}, x_{1:N})$ drops significantly because codecs are lossy.

Milis et al. (ICML 2026) theoretically formalize the expected $z$-score under the alternative hypothesis $H_1$ (watermarked sequence) in the presence of retokenization corruption as:

Where:

• $N$ is the sequence length.
• $g$ is the probability of the generative model choosing a green token in the absence of corruption.
• $r$ is the token match rate (retokenization success probability).
• $h$ is the history context size used for hashing.

Because $r < 1$ in audio, the watermark signal decays exponentially as the context window $h$ increases. For $h=1$ or $h=2$, the signal vanishes almost immediately.

To solve this, prior state-of-the-art approaches like WMAR (Wu et al., 2025a) forced the codec tokenizer to become idempotent via supervised fine-tuning. However, this is computationally intensive and requires white-box access to the codec weights.

Watermarking Modality Comparison

Methodology

Instead of forcing the codec tokenizer to be idempotent, the proposed method accepts retokenization errors as a natural characteristic of continuous representation learning. The authors observe that these errors are not random noise; instead, tokens are consistently confused with their immediate semantic or acoustic neighbors in the latent space.

+------------------------+      +--------------------------+      +------------------------+
| Original Waveform (X)  | ---> |   Encoder E(X) = T1      | ---> |  Synthesized Audio     |
+------------------------+      +--------------------------+      +------------------------+
                                                                             |
+------------------------+      +--------------------------+                 v
| Retokenized Tokens T2  | <--- |  Re-encoded E(D(T1))     | <--- +------------------------+
+------------------------+      +--------------------------+      | Retokenized Waveform   |
            |                                                     +------------------------+
            v
+------------------------+
| Map to Cluster:        |
| C(T1) == C(T2) ?       | ---> Stable Cluster-level Match!
+------------------------+

Step 1: Mapping the Confusion Graph

The defender passes an unwatermarked calibration audio dataset (e.g., 2.7k sentences from the LibriSpeech development set) through the codec twice (Encode $\rightarrow$ Decode $\rightarrow$ Encode) to collect paired original and retokenized token sequences.

From these sequences, they construct a confusion matrix $M \in \mathbb{N}^{|V| \times |V|}$, where $M_{ij}$ counts how many times token $i$ was retokenized as token $j$. This matrix $M$ is interpreted as the adjacency matrix of a weighted directed graph $G = (V, M)$, where the nodes are the individual codebook vectors.

Step 2: Unsupervised Community Detection

To distill this graph into stable, robust communities, they apply the Leiden algorithm (Traag et al., 2019), which optimizes for modularity to discover tightly knit token clusters $P = \{c_1, c_2, \dots, c_K\}$. The clustering granularity is governed by a resolution parameter $\rho$:

• Small $\rho$ results in larger, highly stable clusters (higher cluster match rate $r_{cl}$).
• Large $\rho$ results in smaller, higher-resolution clusters (larger effective vocabulary size, minimizing key collisions).

The Leiden algorithm naturally isolates stable, unconfused tokens as singleton clusters.

Step 3: Cluster-Level Watermarking

At each generation step:

1. The history of the preceding $h$ tokens is converted to their corresponding cluster indices: $C(x_{i-h}), \dots, C(x_{i-1})$.
2. These cluster indices are hashed to split the cluster vocabulary (instead of the raw token vocabulary) into green and red partitions $G_i$ and $R_i$.
3. The generation model's logits are biased by adding $\delta$ to all tokens belonging to the clusters assigned to the green list $G_i$.

By making the hashing context and list assignment cluster-dependent, the expected $z$-score is modified to:

Since $r_{cl} > r$, this effectively mitigates the exponential decay of the watermark signal.

Key Results

Milis et al. (ICML 2026) evaluate their approach using two prominent setups:

• Moshi (Mimi Codec): A speech-text foundation model.
• MusicGen (EnCodec): A text-to-music generation model.

1. Watermark Detectability and Robustness (Moshi)

Table 2 from the paper shows the mean detector confidence score $-\log(p)$ and the structural loss relative to the identity baseline across various signal processing and compression attacks. Higher $-\log(p)$ indicates stronger detection confidence (the baseline $1\%$ false positive rate threshold is $-\log(p) = 2$).

As Table 2 illustrates, under standard MP3 compression, the baseline KGW watermark is severely degraded, and even the fine-tuned WMAR peaks at $15.31. The proposed method maintains an extraordinarily high confidence score of **\41.26**. Under temporal distortions (which typically ruin token alignment), the proposed method still achieves a highly detectable score of **\26.49$** under 1.1x speedup, whereas all baselines fail to meet the detection threshold.

2. Impact on Audio Quality

A common pitfall of robust watermarks is the degradation of audio quality. The authors evaluate this using Fréchet Audio Distance (FAD) (lower is better) and Mean Opinion Scores (MOS) via NISQA and DNSMOS (higher is better).

Table 1 demonstrates that clustering the vocabulary does not introduce audible distortions:

The FAD and MOS scores for the proposed method are almost identical to the unwatermarked baseline. Conversely, WMAR's codec fine-tuning degrades the FAD score to $0.407$.

Limitations & Open Questions

While this gradient-free approach is highly practical, several open challenges remain:

1. Temporal Misalignment Susceptibility: Standard token-level watermarks are fundamentally brittle to cropping or shifting because they disrupt the framing boundaries of neural audio codecs. While the proposed cluster-based method is more robust than others, extreme temporal warping still degrades the signal.
2. Key Collisions and Entropy Trade-offs: As vocabulary size shrinks from $|V|$ to $c|V|$, the likelihood of key collisions increases. This can limit the maximum length of the context window $h$ that can be safely used without introducing repetitive generation artifacts.
3. Black-box Codec Dependency: Capturing the confusion matrix requires black-box access to the target codec to collect calibration data. If the service provider updates their underlying codec, a new confusion matrix must be calculated and the community detection process re-run.

What Practitioners Should Do

If you are deploying synthetic audio generation pipelines or building deepfake detection systems, consider the following integration steps:

1. Build the Confusion Matrix Off-line

Avoid the temptation to dynamically compute retokenization errors during inference. Instead, run a calibration pass using a representative dataset (e.g., LibriSpeech for speech, MusicCaps for music) to construct a static token confusion graph:

# Conceptual pipeline to build the confusion matrix M
import numpy as np

vocab_size = 2048  # Example for Mimi codec Channel 0
M = np.zeros((vocab_size, vocab_size), dtype=np.int64)

for original_audio in calibration_loader:
    # 1. Encode original audio to tokens
    tokens_orig = codec.encode(original_audio)
    # 2. Decode back to continuous waveform
    recon_audio = codec.decode(tokens_orig)
    # 3. Re-encode to observe retokenization drift
    tokens_recon = codec.encode(recon_audio)
    
    # Update confusion counts
    for t_o, t_r in zip(tokens_orig.flatten(), tokens_recon.flatten()):
        M[t_o, t_r] += 1

2. Extract Stable Communities Using Leiden

Utilize the Leiden algorithm with a controlled resolution parameter $\rho$ (typically between $0.8 and \1.2$) to find the optimal trade-off between cluster match rate and vocabulary diversity. Section 5.4 recommends specific hyperparameter selections like$(\rho=0.8, m=1)$ for Mimi channel 0.

3. Implement Cluster-Level Red/Green Partitioning

When applying Kirchenbauer's watermarking rule, map the current generation tokens to their respective cluster IDs before executing the hash function. Ensure the logit bias $\delta$ is applied uniformly across all physical tokens belonging to the selected green-list cluster.

The Takeaway

Milis et al. (ICML 2026) demonstrate that the perceived fragility of token-level multimedia watermarking is not an inherent flaw of continuous models, but rather a solvable discretization mismatch. By replacing expensive, white-box neural network fine-tuning with simple graph community detection, they deliver a highly robust, drop-in defense. This represents a significant step forward in securing audio generative pipelines against unauthorized distribution and deepfake evasion.

Den's Take

This is an incredibly elegant solution to a massive practical headache. As someone who has spent years looking at how easily watermarks fail under basic lossy compression, I love that the authors didn't just throw more compute at the problem. By mapping codec token vulnerabilities as a graph, they solved a core structural flaw without expensive retraining. This is exactly the kind of clever, practitioner-first engineering we need.

For trust and safety teams at companies like ElevenLabs or OpenAI fighting the fallout of voice-clone scams—including high-profile incidents like the notorious $25M deepfake CFO heist in Hong Kong—this technique is a massive deal. Traditional KGW watermarks disintegrate the second audio is transcoded to MP3 or run through a basic bandpass filter, leaving platforms defenseless against adversarial stripping.

This shift to robust, structure-aware detection mirrors my findings in Prompt Injection Detection is Regime-Dependent: A Deployment-Aware Evaluation with Interpretable Structural Signals, where I demonstrated that safety defenses must be designed around the actual, messy distribution shifts of deployment-phase data rather than clean, idealized laboratory baselines. If we want generative audio provenance to be more than a compliance checkbox, we must build defenses that survive the inevitable noise of the real world.