UNICOMARK: UNBIASED AND ROBUST MULTI-BIT LLM WATERMARKING VIA CO-DESIGN OF ERROR- RESILIENT RECOVERY AND SAMPLING

Multi-bit watermarking for large language models (LLMs) aims to embed decodable source identifiers into generated text, but exact and robust recovery remains difficult while preserving text quality in normal and adversarial settings. We propose UniCoMark, which co-designs two tightly coupled components: an embedding–extraction process for reliable watermark message recovery and a matched sampling process for text generation. UniCoMark combines a fixed-length linear code with soft-information decoding and a sampling rule tailored to the recovery objective. To ensure high text quality, we introduce an unbiasedness constraint into the sampling design, enabling the sampling process to be formulated as an optimal transport problem. We further establish a recovery theorem for UniCoMark, giving a message-accuracy bound that characterizes robustness under textual attacks. Extensive experiments validate the effectiveness of UniCoMark. In the normal setting, with 256 tokens generated by base LLMs and a 32-bit payload, UniCoMark achieves 94.9% message accuracy, significantly outperforming the strongest baseline at 60.2%, while also attaining lower perplexity (10.10 vs. 11.22). Under adversarial conditions, UniCoMark remains highly robust: for a 512-token sequence and a 32-bit payload, it achieves 88.0% message accuracy under 15% token-level mixed edits and 87.7% under 30% sentence-level mixed edits, exceeding the best baseline by 64.3 and 52.1 percentage points, respectively.