MuxMark: Multi-Channel Bit Multiplexing for LLM Watermarking

Multi-bit LLM watermarking embeds recoverable messages for text provenance. With a fixed token budget and per-token bit load, larger payloads reduce coverage per message bit. Increasing this load improves coverage, but joint encoding based on disjoint vocabulary partitions concentrates the bias on exponentially smaller target regions, potentially weakening recovery signals at a fixed bias strength. We propose MuxMark, a multi-channel bit multiplexing framework that assigns selected message positions to separately keyed binary channels. During generation, channel contributions are summed to form a token-level logit bias that increases with the number of matched target bits. During decoding, the channels are reconstructed from the secret key and observed prefix, and weighted token votes are aggregated to recover the message bit by bit. Experiments across payloads, generation lengths, model families, and text perturbations demonstrate improved message recovery over existing multi-bit watermarking methods while maintaining comparable text quality, with particularly strong gains when recovering long messages from short texts.