Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
The paper introduces QuantileMark, a novel multi-bit watermarking scheme for LLMs designed to ensure message symmetry, meaning the embedded message doesn't systematically impact text quality or verification. QuantileMark achieves this by partitioning the cumulative probability interval into equal-mass bins and sampling from the bin corresponding to the target symbol, guaranteeing a fixed probability budget. Experiments on C4 continuation and LFQA demonstrate that QuantileMark improves multi-bit recovery and detection robustness compared to baselines, while maintaining generation quality.
LLM watermarks don't have to sacrifice text quality or verification accuracy for certain messages: QuantileMark proves it with a message-symmetric design that ensures uniform probability budgets.
As large language models become standard backends for content generation, practical provenance increasingly requires multi-bit watermarking. In provider-internal deployments, a key requirement is message symmetry: the message itself should not systematically affect either text quality or verification outcomes. Vocabulary-partition watermarks can break message symmetry in low-entropy decoding: some messages are assigned most of the probability mass, while others are forced to use tail tokens. This makes embedding quality and message decoding accuracy message-dependent. We propose QuantileMark, a white-box multi-bit watermark that embeds messages within the continuous cumulative probability interval $[0, 1)$. At each step, QuantileMark partitions this interval into $M$ equal-mass bins and samples strictly from the bin assigned to the target symbol, ensuring a fixed $1/M$ probability budget regardless of context entropy. For detection, the verifier reconstructs the same partition under teacher forcing, computes posteriors over latent bins, and aggregates evidence for verification. We prove message-unbiasedness, a property ensuring that the base distribution is recovered when averaging over messages. This provides a theoretical foundation for generation-side symmetry, while the equal-mass design additionally promotes uniform evidence strength across messages on the detection side. Empirical results on C4 continuation and LFQA show improved multi-bit recovery and detection robustness over strong baselines, with negligible impact on generation quality. Our code is available at GitHub (https://github.com/zzzjunlin/QuantileMark).