On the Possibilities of AI-Generated Text Detection: A Sample Complexity Analysis

General Response We sincerely appreciate the reviewer's thoughtful feedback on our paper. We would like to acknowledge the reviewer for acknowledging the major motivation, theoretical contribution, and empirical analysis of our work, especially emphasizing that our results can motivate researchers to continue working on AI-generated text detection, despite the fear of LLMs approaching human performance --> this was our exact motivation.

Important Highlights: We want to specifically highlight the reviewer's extremely important comment "authors are under-selling themselves in the title/abstract/introduction focusing on the "number of samples" rather than "sequence length". We absolutely agree that our non-iid results are much more general and generalize to relating the sample complexity with sequence length and not just more samples (Th 1) which is practical and more general. We will be updating our draft with special emphasis on this point as we believe this contribution was missed by some of the reviewers.

Weakness

Comment: Overall, I liked the sentiment in the paper and thought the theoretical and empirical analysis was thorough. While I am leaning accept, I had some concerns about the real-world takeaways from the work, and would love to hear the author's thoughts on it (please let me know if this was mentioned somewhere in the paper or appendix and I missed it!).

Response to Comment Thanks a lot for the comment. We provide a detailed discussion below.

Weakness 1 : The theoretical analysis in the paper has a nice overall takeaway, but I am not sure how helpful the bounds are for practitioners who are developing these algorithms / trying to detect AI-generated text. We try to discuss some implications of our

Response to Weakness 1 Thanks for this comment and we agree that it is indeed very important to discuss the significance and practical implications of our result. We attempt to provide certain insights of our results in Appendix A (remarks 1, 2, 3). Here we highlight how practitioners can leverage our results in designing reliable and more robust watermarks & detectors (currently susceptible to attacks) with information gain and human-machine distribution distance, and also discuss on the task-specific detectability with our results. We give two examples for simplicity

Watermark Design: Our analysis suggests adaptive watermark designs based on Chernoff information and sample complexity, enhancing robustness against attacks—a future research avenue.

Length Constraints in Exams: Our bounds inform optimal summary lengths for easier cheating detection, leveraging the Chernoff metric.

However, we agree that a more specific and detailed discussion on the practicality will be critical and we will add the same in our updated draft.

Weakness 2: How does one go about computing the variation between machine-generated text and human-written text (TV(m,h)^n) for some SoTA LLMs like ChatGPT or GPT4, perhaps in..... corresponding upper bounds for AU-ROC for different values of the output length. I wonder if the method used in the MAUVE text evaluation paper (https://arxiv.org/abs/2102.01454) may be helpful for this calculation, who proposes a clever approximation for measuring the divergence between human/machine-written text.

Response to Weakness 2 This is a very interesting point. We agree that computing the total variation distance in exactness for a real detector for text generated from LLMs or humans is hard and hence we evaluate the performance w.r.t AUC similar to what was used in prior works on detection (Sadasivan et. al, Krishna et. al, Mitchell et al.).

However, it is important to note that we do validate the AUC upper-bound (in exactness, missing from concurrent works) for the best detector with an n-gram bag of words based on discretized feature space in Figure 2a. Since, in a finite discretized feature space, TV distance can be computed using the definition [1] and then we plot the AUC upper bounds by varying the value of n in n-grams as in Figure 2a.

On the other hand, the MAUVE metric leverages a modified KL/JS type divergence as in Equation 2 (Pillutla et al 2021), which can be an alternate measure of divergence replacing TV distance. Thanks for this very interesting suggestion and we agree that due to the piecewise constant approximation of the human (machine) distributions as done in Equation 3 (Mauve paper), we can estimate the KL divergence (or TV distance) under some approximations (depending on the clustering), and is a valid scope of future research. Additionally, one can also show theoretically by replacing TV with KL using Pinsker's inequality and obtaining the equivalent upper bound like ours in Theorem 1,2.

General Response: Thank you for your review. We appreciate your recognition of the clarity of our paper. Your insights on the significance of document length and the consideration of multiple sampled documents are valuable and will further enrich the discussion in this paper.

Weakness

Weaknesses 1: My main concern is that the results in this paper are general facts about sample complexity and not specific to the detection of AI-generated text. For example, Theorem 1 is included here: https://github.com/ccanonne/probabilitydistributiontoolbox/blob/master/testing.pdf. As this paper is outside of my area, I am less confident about the novelty of Theorem 2, but its formulation is not dependent on the domain of AI-generated text detection. It is also unclear from the paper whether the “multiple samples” required by this theorem are meant to be individual words, sentences, or documents.

Response to Weakness 1 We thank the reviewer for the reference but there seems to be a confusion regarding the novelty of our work. We note that the upper bound in the Total variation distance of the distribution (product distribution) is deep-rooted in the fundamentals of Information theory more specifically Lecam's lemma (as clearly highlighted at multiple places in our paper such as in the start of Section 3.2, before Equation (9), and Appendix B.1). We never claim the novelty regarding the same, whereas our main novelty lies in deriving a precise sample complexity bound in the context of AI-generated text detection for both iid and non-iid scenarios, which is novel.

Our Results are for AI-generated Text Detection (as acknowledged by Reviewer 6pNs): We illustrate our results precisely in the context of LLMs through several instances, provide key insights and also empirical evaluation in the text domain. For example in Section 3.4, we develop the novel connection between non-iid sample complexity and increasing sequence length in generation, illustrate the implication of $\sum_k s_k$ (Equation 16) and novel insights on dependence of topics/contexts present in the paragraph with sample complexity results and empirical evaluations with several SOTA generators and detectors. We want to highlight that our results and comparisons are inline with the recent results in the field of AI-generated text detection (Sadasivan et. al, Krishna et. al, Mitchel et al etc.)

Clarification Regarding the use of the term 'multiple samples': Our result does not depend on the specific choice of the unit (for samples) to represent i.e., it can be a bag of words, sentences, or paragraphs, but rather emphasizes on the impact of product distribution on the sample complexity. To highlight the point we empirically demonstrate with several such instances like bag of words (Figure 2), sentences (Figure 3, 4), etc.

Questions

Question 1. What is the “Percentage of Sequence used for Detection”?

Response to Question 1 We vary the sequence length from 10% to 95% as shown in Figures 3a-f, and it is evident the detection performance improves significantly.

Question 2: What does “exponentially fast” mean in the caption of Figure 1?

Response to Question 2 In Figure 1, the value of Total variation distance (best detector) increases at an exponential rate as a function of the number of samples, which is also evident from our theoretical analysis as shown in Equation 12. In equation 12, it is evident that as we increase n, TV exponentially approaches 1.

Question 3: Are there any experiment results on non-IID data?

Response to Question 3: Yes, We want to highlight that all our experimental ablations including Figures 2 (a,b) 3 (a->f) are for non-iid scenarios only, as you can see that the performance (AUC) is measured with increasing sequence length. This is exactly what we discuss in Theorem 2, when we increase the sequence length (which is equivalent to having more dependent samples) the detection performance varies, which is novel and not covered in past literature. We apologize if this point didn't come out clearly and will be updating the draft with a specific focus on this point as also highlighted by Reviewer 6pNs: "I feel like the authors are under-selling themselves in the title/abstract/introduction, by focusing on the "number of samples" rather than "sequence length"

Question 4: Maybe I missed something from the paper, but is there any sample complexity directly related to equation 15?

Response to Question 4 Equation 15 represents the sample complexity results for the iid case (Theorem 1) which states that to achieve an AUROC of $\epsilon$, we will need $O(\frac{1}{\delta^2} \log \frac{1}{1 - \epsilon})$ samples (iid case, non-iid in Theorem 2). This precisely represents the sample complexity of detection i.e how the detection performance varies (in terms of AUC) with number of samples or sequence length. Hope this clears the confusion.

General Response: We thank the reviewer for appreciating the research problem and theoretical analysis. We address the additional concerns in detail as follows.

Weaknesses:

Weakness 1: Interesting method and conclusion; however not sure how much we can connect this with MGT detection. It seems like the conclusion is generally applicable. This means the proposed method itself is not necessarily a weakness, but the disconnection is.

Response to Weakness 1 We are thankful that you find our formulation and methodology interesting.

Regarding the generality of the results, we agree that certain theoretical results for example used in Eq 6, 7, and 9 have their roots in Information theory and Large deviation theory but a precise connection to the context of AI-generated text detection was missing from literature. Specifically, our sample complexity analysis for iid samples (Theorem 1) and non-iid samples (Theorem 2) are novel and provide a first step towards showing possibility results (in a theoretically rigorous manner) of MGT detection.

We illustrate our results precisely in the context of LLMs through several instances, key insights, and empirical evaluation. For example in Section 3.4, we develop the connection between non-iid sample complexity and increasing sequence length in the generation, illustrate the implication of $\sum_k s_k$ (Equation 16), and novel insights on the dependence of topics/contexts present in the paragraph with sample complexity results and empirical evaluations with several SOTA generators and detectors.

Weakness 2: Equation 7 is not surprising. As pointed out by Sadasivan et al. (2023), it is impossible to get a reliable detector (high TPR, e.g., 90% and lower FPR, e.g., 1%), when the overlap of two distributions is relatively small.

Response to Weakness 2 We agree that Equation 7 trivially follows and it comes from an application of Lecam's Lemma from Information Theory which we have clearly cited (and not first appeared in Sadasivan et al. (2023)). But we respectfully point out that there seems to be a slight confusion here. Our point is not about Equation (7). We would like to highlight the hidden possibility part which starts around Equation (8) (which is different from Sadasivan et al. (2023)).

Our Focus: Our result in this paper focuses on Equation (9), which helps to conclude that even if the overlap of distribution in Equation (7), is small, increasing the samples/sequence length helps to increase the TPR because TV norm increases exponentially with respect to $n$ as highlighted in (12). This is rigorously connected with bounds developed in Theorem 1 (iid) and Theorem 2 (non-iid) cases.

Weakness 3: Furthermore, equation 7 does not depend on sample complexity. So, I am not sure I understand how increasing the number of examples can get around this issue pointed out by the previous comment.

Response to Weakness 3: Equation 7 is mentioned to lay the foundation of our discussion but our results follow from the expression in Equation (9) which clearly depends upon the values of $n$ (samples/sequence length). We apologize for the confusion, we will highlight this fact in the revised version of our manuscript.

Weakness 4: More generally, the real challenge of detecting MGT is the lack of information on generative models. In practice, it’s hard to predict whether a collection of texts is from the same generation model. Furthermore, a gray area of this research question: how we should treat the texts generated by machines and edited by humans.

Response to Weakness 4 This is a very interesting point. We agree that texts generated by machines and edited by humans is a very challenging setting and is very hard to detect in that case. However, our result provides a first step to rigorously show the possibility of detection where the text comes from either human/machine distribution. However, texts generated by machines and edited by humans are an extremely important and valid source of future research.

New Experimental Results (Figure 11 in Appendix E in the updated draft): We would like to provide an update that we have also validated the detection performance on Question-answering style task with OpenAI's Roberta classifier and observe that with the increase in sequence length for detection, the zero-shot detection performance of both the models improves significantly from around 55% to 98% validating our theorem for QA tasks.

Please let us know if we can address any more concerns before the rebuttal period ends. Thank you so much. We look forward to your feedback.

General Response: Thank you for your review and recognition of the importance of our work in detecting AI-generated texts. We are glad you found the paper clear and the empirical experiments supportive of our theoretical findings. Your feedback is invaluable in highlighting the strength and importance of our research.

Weakness

Weakness 1: The novelty of the finding. While the "hidden possibility" argument over the increasing sample size and increasing detectability of machine-generated texts is valid and intuitive, the novel insight in the argument is rather limited. The assumption and use of an increasing sample size/length in the machine-generated text detection problem is regular, for example, in watermarking (Kirchenbauer et al., 2023). The practical takeaway of the finding is relatively vague.

Response to Weakness 1: Thanks for appreciating our finding regarding the "hidden possibility" of AI-generated text detection. Regarding the novelty, we want to point out that our work is the first attempt to theoretically show the "hidden possibility" of AI-generated text detection and derive the precise sample complexity analysis for the detection problem. These theoretical results provide the insight that the detectability increases as the number of samples (tokens)(Theorem 1)/sequence length (Theorem 2) increases and also derive the rate of increment. The referred work by Kirchenbauer et al., 2023 is a concurrent work (can't provide more details on the timeline due to anonymity violation) and provides no theoretical analysis, rather provides empirical demonstrations that even validate our theorems for iid and non-iid cases.

The primary takeaway of our approach is to provide theoretically rigorous evidence (connecting it with the text sequence length) that the detection of AI-generated text detection is possible, which is in contrast to recently developed impossibility results in Sadasivan et. al. As highlighted by the Reviewer 6pNs: "I feel like the authors are under-selling themselves in the title/abstract/introduction, by focusing on the "number of samples" rather than "sequence length", we will specifically highlight this aspect in our revised version of our work.

Importance of Our Results. Additionally, we want to highlight that our theoretical results of characterizing the sample complexity with Chernoff information (for iid and non-iid scenarios) are critical and provide additional insights (detailed in Appendix A) for example

1. Watermark Design: Our analysis suggests adaptive watermark designs based on Chernoff information and sample complexity, enhancing robustness against attacks—a future research avenue.
2. Length Constraints in Exams: Our bounds inform optimal summary lengths for easier cheating detection, leveraging the Chernoff metric.

New Experimental Results (Figure 11 in Appendix E in the updated draft): As requested by the reviewer, we have also validated the detection performance on Question-answering style task with OpenAI's Roberta classifier and observe that with the increase in sequence length for detection, the zero-shot detection performance of both the models improves significantly from around 55% to 98% validating our theorem for QA tasks.

Please let us know if we can address any more concerns before the rebuttal period ends. Thank you so much. We look forward to your feedback.