  In recent years, large language models (LLMs) have achieved remarkable
performances in various NLP tasks. They can generate texts that are
indistinguishable from those written by humans. Such remarkable performance of
LLMs increases their risk of being used for malicious purposes, such as
generating fake news articles. Therefore, it is necessary to develop methods
for distinguishing texts written by LLMs from those written by humans.
Watermarking is one of the most powerful methods for achieving this. Although
existing watermarking methods have successfully detected texts generated by
LLMs, they significantly degrade the quality of the generated texts. In this
study, we propose the Necessary and Sufficient Watermark (NS-Watermark) for
inserting watermarks into generated texts without degrading the text quality.
More specifically, we derive minimum constraints required to be imposed on the
generated texts to distinguish whether LLMs or humans write the texts. Then, we
formulate the NS-Watermark as a constrained optimization problem and propose an
efficient algorithm to solve it. Through the experiments, we demonstrate that
the NS-Watermark can generate more natural texts than existing watermarking
methods and distinguish more accurately between texts written by LLMs and those
written by humans. Especially in machine translation tasks, the NS-Watermark
can outperform the existing watermarking method by up to 30 BLEU scores.
