Research map / Large language models / Language, safety and interpretability

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

NeurIPS 2026 · Large language models › Language, safety and interpretability · approach: Text watermarking · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes ArcMark, a distortion-free multi-byte LLM watermark that combines random linear channel coding with circular optimal transport (Sinkhorn), and derives a capacity expression for distortion-free multi-bit watermarking.

Problem

Multi-bit LLM watermarks typically embed only a few bits over hundreds of tokens and encode one bit per token; it is unclear how many bits can be reliably embedded without distorting the next-token distribution.

Approach

Treat distortion-free watermarking as channel coding with side information: a random linear code maps the message to codeword symbols on a circle, and an optimal-transport (Sinkhorn) step selects tokens close to the target angle while preserving the LLM distribution; minimum-distance decoding recovers the whole message jointly over tokens.

Key results

• On Qwen3-8B, ArcMark's perplexity at 300 tokens (3.821 for 3-byte) is closer to the unwatermarked baseline (3.941) than BiMark (4.116), and the gap widens with payload size.
• Under French back-translation at ratio 0.3 on a 3-byte payload, ArcMark still outperforms unattacked BiMark on all three models.
• The derived distortion-free capacity for uniform two-token distributions approaches about 0.2787 bits/token as N grows to infinity.

Surprising findings

• Under the paper's binary-token-distribution model, the distortion-free capacity is only about 0.2787 bits/token in the large-vocabulary limit, far below what practical schemes embed in bytes.

Limitations

• Capacity result is proven only for a specific class of two-token uniform distributions and under i.i.d. assumption on next-token distributions.
• Optimality of ArcMark is shown only under simplifying assumptions; practical random linear code is not generally capacity-achieving.
• Several distortion-free baselines lack public implementations, so comparison is limited to BiMark (and MPAC as non-distortion-free reference).

Experimental setup

Datasets: C4-RealNewslike SQuAD v2 LCC HumanEval

Benchmarks: C4-RealNewslike SQuAD v2 LCC HumanEval

Metrics: message accuracy perplexity true positive rate at 1% FPR downstream task accuracy

Baselines: BiMark MPAC

Builds on: BiMark SynthID-style OT watermarking (HeavyWater/SimplexWater) Red-Green watermark

Closest papers by meaning

• BiMark: Unbiased Multilayer Watermarking for Large Language Models (ICML 2025 · similarity 0.91)
• MC$^2$Mark: Distortion-Free Multi-Bit Watermarking for Long Messages (NeurIPS 2026 · similarity 0.91)
• PRO: Enabling Precise and Robust Text Watermark for Open-Source LLMs (NeurIPS 2026 · similarity 0.91)
• Every Bit, Everywhere, All At Once: A Binomial Multibit LLM Watermark (NeurIPS 2026 · similarity 0.91)
• Robust Multi-bit Text Watermark with LLM-based Paraphrasers (ICML 2025 · similarity 0.91)
• Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach (NeurIPS 2025 · similarity 0.90)