Recent studies show that large language models (LLM) unintendedly memorize part of the training data, which brings serious privacy risks. For example, it has been shown that over 1% of tokens generated unprompted by an LLM are part of sequences in the training data. However, current studies mainly focus on the exact memorization behaviors. In this paper, we propose to evaluate how many generated texts have near-duplicates (e.g., only differ by a couple of tokens out of 100) in the training corpus. A major challenge of conducting this evaluation is the huge computation cost incurred by near-duplicate sequence searches. This is because modern LLMs are trained on larger and larger corpora with up to 1 trillion tokens. What's worse is that the number of sequences in a text is quadratic to the text length. To address this issue, we develop an efficient and scalable near-duplicate sequence search algorithm in this paper. It can find (almost) all the near-duplicate sequences of the query sequence in a large corpus with guarantees. Specifically, the algorithm generates and groups the min-hash values of all the sequences with at least t tokens (as very short near-duplicates are often irrelevant noise) in the corpus in linear time to the corpus size. We formally prove that only 2 n+1/t+1 -1 min-hash values are generated for a text with n tokens in expectation. Thus the index time and size are reasonable. When a query arrives, we find all the sequences sharing enough min-hash values with the query using inverted indexes and prefix filtering. Extensive experiments on a few large real-world LLM training corpora show that our near-duplicate sequence search algorithm is efficient and scalable.

In this paper, we study the near-duplicate text alignment search problem, which, given a collection of source (data) documents and a suspicious (query) document, finds all the near-duplicate passage pairs between the suspicious document and every source document. It finds applications in plagiarism detection. Specifically, the first two steps in plagiarism detection are source retrieval and text alignment. Source retrieval finds candidate source documents in a corpus that share content with the suspicious document while text alignment finds all the similar passage pairs between the suspicious document and every candidate source document. This problem is computation-intensive, especially for long documents. This is because there are O(n2m2) passage pairs between a single source document with n words and a suspicious document with m words, not to mention the large number of source documents in a corpus. Due to the high computation cost, existing solutions primarily rely on heuristic rules, such as the "seeding-extension-filtering" pipeline, and involve many hard-to-tune hyper-parameters. To address these issues, a recent work ALLIGN leverages the min-wise hash sketch for the text alignment problem. However, ALLIGN only works for two documents and leaves the source retrieval problem unattended. In this paper, we propose to leverage the bottom-k sketch (a.k.a. conditional random sampling) to estimate the similarity of two passages. We observe that many nearby passages in a document would share the same bottom-k sketch. Thus we propose to group all the passages in a document by their sketches. We prove that all the O(n2) passages can be partitioned into O(nk) groups in a document with n words and develop an algorithm to generate these groups in O(nlogn+nk) time. Then, to address the source retrieval problem, we only need to find groups of passages with "similar" bottom-k sketches. Every passage pair in two groups with "similar" sketches are near-duplicates. Experimental results on real-world datasets show that our techniques are highly efficient.