TrellisMark: Multi-Bit LLM Watermarking with Trellis Coupling and Online Strength Allocation

Multi-bit watermarking enables large language models to embed rich structured messages, such as user and model identifiers, into generated text, supporting provenance attribution and misuse tracing. Existing methods either let each token contribute evidence to only one payload position, leaving each position with limited evidence, or aggregate evidence over complete messages, making exact decoding costly as the payload grows. We introduce TrellisMark, which couples neighboring payload positions through overlapping local windows. Each token provides evidence about the symbols in one selected window, while multiple independent heads over the same window strengthen this evidence. The overlap induces a trellis over candidate payloads, enabling exact maximum-score recovery without enumerating the full message space. We further formulate watermark-strength selection as an online allocation problem driven by the current trellis recovery state. Under a cumulative KL-divergence budget, the policy assigns greater strength to steps with higher recovery value. We prove a recovery bound based on trellis-path separation and a regret bound for online allocation. Experiments show improved exact message recovery and better recovery–quality trade-offs over existing baselines.