🤖 AI

ArcMark: Distortion-Free Multi-Byte LLM Watermark via Optimal Transport

This paper introduces ArcMark, a novel distortion-free multi-byte watermarking framework for large language models that leverages optimal transport and information-theoretic channel coding principles to reliably embed substantial information into text without altering the model's output distribution or quality.

Original authors: Atefeh Gilani, Sajani Vithana, Carol Xuan Long, Oliver Kosut, Lalitha Sankar, Flavio P. Calmon

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Atefeh Gilani, Sajani Vithana, Carol Xuan Long, Oliver Kosut, Lalitha Sankar, Flavio P. Calmon

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very talented, creative writer (a Large Language Model, or LLM) who can write stories, code, or emails. You want to know if a specific piece of text was written by this AI, and if so, you want to know exactly who asked for it, which version of the AI wrote it, or even what the original prompt was.

This is where ArcMark comes in. It is a new "invisible ink" for AI text.

Here is the simple breakdown of what the paper claims, using everyday analogies:

1. The Problem: The "One-Bit" Flashlight

Previous methods of watermarking AI text were like using a flashlight that could only flash once (a "zero-bit" or "one-bit" signal).

What it did: It could tell you, "Yes, this was written by an AI" or "No, it wasn't."
The Limitation: It couldn't tell you who wrote it or what they wrote about. It was like seeing a light flash in the dark but not knowing who turned it on.
The Old Way: To send more information, old methods tried to tweak the text slightly, like changing a word here or there. This sometimes made the writing sound a bit robotic or unnatural (distortion).

2. The Solution: The "Invisible Postcard" (ArcMark)

The researchers created ArcMark, which is like an invisible postcard hidden inside the text.

The Magic: It can hide multiple bytes of information (like a whole ID number or a short message) inside just a few hundred words of text.
The "No Distortion" Promise: The most important claim is that this invisible ink does not change the quality of the writing. If you read the text, it sounds exactly as natural as if the AI had written it without any hidden message. The paper claims the text is "distortion-free," meaning the AI's natural flow isn't interrupted.

3. How It Works: The "Circle Game"

The paper uses some heavy math, but here is the simple version of their trick:

The Circle: Imagine the AI's list of possible words (its vocabulary) arranged in a giant circle.
The Target: The system picks a specific spot on that circle to represent a piece of the secret message.
The Shuffle: The AI and the decoder (the person checking for the message) share a secret "shuffle" key. This key rotates the circle so that only they know where the secret spot is.
The Selection: The AI is asked to pick a word. Instead of picking the absolute best word, it picks a word that is close to the secret spot on the circle.
- Analogy: Imagine you are playing a game where you have to pick a fruit from a basket. The rule is: "Pick a fruit that is close to the red spot on the table, but make sure the basket still looks like a normal fruit basket." The AI picks a fruit that satisfies both rules.
The Math: The paper uses a concept called "Optimal Transport" to solve this. Think of it as a super-efficient delivery driver who moves the "best" fruits to the "red spot" without making the basket look empty or messy.

4. Why It's Better: The "Team Effort" vs. "Solo Act"

Old Methods: Tried to hide one tiny bit of information in every single word. If you messed up one word, you lost that bit. It was like trying to send a message by whispering one letter at a time; if the wind blew, you lost the letter.
ArcMark: Treats the whole paragraph as a single puzzle. It uses a "linear code" (a fancy way of saying a team effort). Even if an attacker changes a few words (like paraphrasing a sentence), the decoder can still figure out the whole message because it looks at the pattern of the whole sequence, not just individual words.

5. The Results: What the Paper Found

The authors tested ArcMark on popular AI models (like Llama3, Mistral, and Qwen) and found:

Accuracy: It can successfully hide and recover 1, 2, 3, or even 4 bytes of data (which is a lot for text) with very high accuracy.
Stealth: The text sounds just as good as normal AI text. Tests measuring "perplexity" (a score for how confusing or unnatural text sounds) showed no difference between watermarked and non-watermarked text.
Robustness: Even if someone tries to "paraphrase" the text (translate it to French and back to English, or rewrite sentences), ArcMark survives much better than previous methods.
Capacity: The paper mathematically proves that ArcMark is very close to the theoretical maximum limit of how much information you can hide in AI text without ruining it.

Summary

ArcMark is a new, highly efficient way to stamp AI text with a hidden, multi-byte ID card. It does this without making the text sound weird, and it is smart enough to survive attempts to rewrite or edit the text. It turns the problem of "hiding a message in AI" from a guessing game into a precise, mathematical science.

Technical Summary: ArcMark

Problem Statement

The paper addresses the challenge of multi-bit watermarking for Large Language Models (LLMs). While existing methods can embed a single bit (zero-bit watermarking) to detect AI-generated text, or embed multiple bits by extending zero-bit principles (e.g., one bit per token), these approaches are limited in capacity. Current methods struggle to reliably embed more than a few bits into sequences of hundreds of tokens.

The authors identify a critical gap: practical applications (such as embedding user IDs, model versions, or the prompt itself) require the ability to embed multiple bytes of information. Furthermore, a "gold standard" for LLM watermarking is distortion-free embedding, where the watermarking process does not alter the LLM's average next-token predictions, thereby preserving text quality and perplexity. The paper poses two central questions:

What is the theoretical limit (capacity) of information that can be embedded into LLM output without distorting next-token predictions?
Can a practical scheme approach this limit to achieve reliable multi-byte insertion?

Methodology: ArcMark

The authors introduce ArcMark, a watermarking construction based on coding theory and optimal transport. The core insight is to reframe multi-bit watermarking not as a sequence of independent token decisions, but as a channel coding problem with side information available at both the encoder (watermarker) and decoder.

1. Information-Theoretic Formulation

The authors model the LLM as a noisy channel where the "noise" is the inherent randomness of the next-token distribution ( $Q_{X_t}$ ). They derive the Shannon capacity for distortion-free multi-bit watermarking.

Distortion-Free Constraint: The marginal distribution of the watermarked tokens must equal the original LLM distribution in expectation over the shared side information: $E_{S_t}[Q_{X_t|S_t, M=m}] = Q_{X_t}$ .
Capacity Derivation: Under the assumption that next-token distributions are independent and identically distributed (i.i.d.) random variables, the capacity is defined as the maximum mutual information $I(W; X)$ between the encoded message $W$ and the output $X$ , subject to the distortion-free constraint.
Theoretical Limit: For a specific class of binary token distributions, the capacity is derived to be approximately 0.2787 bits/token as the vocabulary size approaches infinity.

2. The ArcMark Construction

ArcMark achieves reliable embedding by mapping the problem to a geometric space and solving an optimization problem:

Geometric Representation: The token vocabulary, message codeword symbols, and shared random keys are all mapped to points on a unit circle (angles).
- Tokens are mapped to $2\pi i / N$ .
- Message symbols are mapped to $2\pi c / p$ .
- Side information (random shift) is mapped to $2\pi v / r$ .
Encoding (Linear Coding): The $k$ -bit message is mapped to a codeword symbol $C_m(t)$ using a random linear code over integers modulo $p$ . This symbol is combined with a shared random shift $V_t$ to produce a target angle $z_t$ on the circle.
Embedding (Optimal Transport): To embed the message without distorting the LLM's output distribution, the watermarker must select a token $X_t$ $X_{t}$ that is "close" to the target angle $z_t$ $z_{t}$ while satisfying the distortion-free constraint. This is formulated as an Optimal Transport (OT) problem.
- The watermarker solves for a conditional distribution $Q^*_{X_t|Z_t}$ that minimizes the expected angular distance between the selected token and the target angle, subject to the constraint that the marginal distribution matches the original LLM distribution.
- This is solved efficiently using the Sinkhorn algorithm.
Decoding: The decoder observes the token sequence and shared side information. It estimates the transmitted angles, removes the shared randomness to recover codeword symbols, and performs minimum distance decoding over all possible messages to recover the full message.

Key Contributions

ArcMark Algorithm: A new distortion-free multi-bit watermarking scheme capable of embedding multiple bytes of information into a few hundred tokens.
Capacity Characterization: A formal derivation of the Shannon capacity for distortion-free multi-bit LLM watermarking, framing the problem as channel coding with side information.
Theoretical Optimality: A proof that, under specific simplifying assumptions (binary token distributions), ArcMark achieves the derived Shannon capacity.
Empirical Validation: Comprehensive evaluation demonstrating that ArcMark outperforms existing multi-bit methods (specifically BiMark and MPAC) in message accuracy and robustness, while maintaining distortion-free properties.

Experimental Results

The authors evaluated ArcMark on three open-weight models (Llama3-8B, Mistral-7B, Qwen3-8B) using the C4-RealNewslike dataset.

Message Accuracy: ArcMark significantly outperforms BiMark in recovering the entire message (message accuracy), particularly for larger payloads (2, 3, and 4 bytes). While bit accuracy is important, the paper emphasizes message accuracy as the operational metric, noting that a single bit error renders the entire message (e.g., a user ID) incorrect.
Robustness: ArcMark demonstrates superior robustness against paraphrasing attacks (specifically French back-translation). Even at high attack ratios (30% of sentences paraphrased), ArcMark maintains higher message accuracy than unattacked BiMark.
Distortion-Free Properties:
- Perplexity: ArcMark's perplexity is nearly identical to the non-watermarked baseline and closer than BiMark, confirming the preservation of the LLM's output distribution.
- Downstream Utility: In extractive question answering (SQuAD), long-context code completion (LCC), and functional code correctness (HumanEval), ArcMark shows no meaningful degradation compared to the unwatermarked baseline.
Zero-Bit Detection: ArcMark supports zero-bit detection (determining if text is watermarked) with high accuracy, reaching near-perfect detection rates from 150 tokens onward.

Significance and Claims

The paper claims to reframe multi-bit watermarking from a heuristic problem to a channel coding problem with side information, a formulation dating back to Claude Shannon. By shifting the perspective to capacity and code design, the authors argue that information theory provides both a mathematical foundation for understanding the limits of LLM watermarks and a constructive path for designing them.

The significance of ArcMark lies in its ability to embed bytes (not just bits) of information reliably and without distorting text quality. This enables practical applications such as tracking user prompts, model versions, and specific model instances, which are crucial for accountability and regulatory compliance. The authors note that by optimizing for message-level accuracy rather than bit-level accuracy, the risk of misattribution is reduced.

The paper concludes that while their capacity analysis relies on specific distributional assumptions, the framework opens the door to broader theoretical characterizations and the design of watermarks with higher recovery rates and stronger robustness guarantees.