SemaSync: Robust Semantic-State Watermarking for Structured LLM Generation

Large language models (LLMs) increasingly generate structured outputs such as mathematical solutions and software code, creating a growing need for reliable provenance verification. Watermarking these outputs faces two challenges: rewriting can disrupt token-dependent watermark states and weaken detection, while indiscriminate sampling biases can compromise correctness. We introduce SemaSync, a watermarking framework that uses semantic and structural anchors to support synchronization after rewriting. Multi-anchor voting provides redundancy when individual anchors change, while distribution-aware selective embedding balances watermark detectability with output quality. We establish a margin-based partition stability guarantee and use ablations to clarify the roles of state construction, selective embedding, and multi-anchor voting. Across GSM8K and MBPP with Qwen3.5-9B and Llama-3.1-8B-Instruct, SemaSync achieves higher AUROC on unmodified outputs than all evaluated baselines in all settings. On Qwen GSM8K, SemaSync improves TPR at 1% FPR by 20.1% on unmodified outputs and 44.2% after Mistral rewriting relative to the strongest baseline in each condition with moderate accuracy loss.