  Large Language Models (LLMs) have been widely deployed for their remarkable
capability to generate texts resembling human language. However, they could be
misused by criminals to create deceptive content, such as fake news and
phishing emails, which raises ethical concerns. Watermarking is a key technique
to mitigate the misuse of LLMs, which embeds a watermark (e.g., a bit string)
into a text generated by a LLM. Consequently, this enables the detection of
texts generated by a LLM as well as the tracing of generated texts to a
specific user. The major limitation of existing watermark techniques is that
they cannot accurately or efficiently extract the watermark from a text,
especially when the watermark is a long bit string. This key limitation impedes
their deployment for real-world applications, e.g., tracing generated texts to
a specific user.
  This work introduces a novel watermarking method for LLM-generated text
grounded in \textbf{error-correction codes} to address this challenge. We
provide strong theoretical analysis, demonstrating that under bounded
adversarial word/token edits (insertion, deletion, and substitution), our
method can correctly extract watermarks, offering a provable robustness
guarantee. This breakthrough is also evidenced by our extensive experimental
results. The experiments show that our method substantially outperforms
existing baselines in both accuracy and robustness on benchmark datasets. For
instance, when embedding a bit string of length 12 into a 200-token generated
text, our approach attains an impressive match rate of $98.4\%$, surpassing the
performance of Yoo et al. (state-of-the-art baseline) at $85.6\%$. When
subjected to a copy-paste attack involving the injection of 50 tokens to
generated texts with 200 words, our method maintains a substantial match rate
of $90.8\%$, while the match rate of Yoo et al. diminishes to below $65\%$.
