Deduplication › Document-Level vs Substring Deduplication

The deduplication strategies we have discussed so far operate on whole documents. Either an entire document is too similar to another and gets discarded, or it is kept in full. But duplication does not always occur at the document level.

Consider a web-crawled corpus containing:

• News article A: a 1000-word article about climate change
• News article B: a different 1000-word article about climate change that happens to contain a 400-word quote from a famous report

Both articles are unique at the document level. Their Jaccard similarity might be 0.15, well below any reasonable deduplication threshold. Yet article B contains a 400-word passage that appears verbatim in hundreds or thousands of other documents in the corpus, because it is a widely quoted passage.

When you train a model on this data, it will see that 400-word passage disproportionately often, not because any individual document is a duplicate, but because the passage recurs across many documents. The result is the same memorization problem, just distributed differently. The model learns to associate certain prompts with that memorized passage, because regardless of what document context surrounds the passage, the passage itself is always the same. This can manifest as the model producing accurate-sounding but unhelpfully generic responses on topics where the training data was dominated by frequently quoted boilerplate.

Substring deduplication addresses this by finding and removing repeated passages within documents, even when those documents are unique at the document level.

Lee et al. (2022) introduced suffix array-based substring deduplication, which became the method used to produce the C4 and T5 training data. The algorithm works by finding all substrings of length at least $L$ (typically 50 to 100 tokens) that appear in more than one document in the corpus.

A suffix array is a data structure that allows efficient substring search across an entire corpus. If you concatenate all documents into a single string $T$ separated by a special delimiter character, the suffix array $SA$ is a permutation of $\{0, 1, \ldots, |T|-1\}$ such that the suffixes $T[SA[0]:], T[SA[1]:], \ldots, T[SA[|T|-1]:]$ are in lexicographic order.

To understand why sorting suffixes is useful, consider what happens to two identical substrings when you sort all suffixes lexicographically. Two suffixes that start with the same long substring will be placed adjacent to each other in the sorted order, because their first $L$ characters are identical and thus sort identically. A linear scan over the sorted suffixes can then identify all pairs of suffixes that share a long common prefix, which corresponds to a long repeated substring in the original corpus.

The data structure that captures this prefix information is the Longest Common Prefix (LCP) array, constructed alongside the suffix array. The LCP array stores, for each consecutive pair of sorted suffixes, the length of their common prefix. Formally, $\text{LCP}[i]$ is the length of the longest common prefix between $T[SA[i-1]:]$ and $T[SA[i]:]$. Entries where $\text{LCP}[i] \geq L$ correspond to locations where a repeated passage of length at least $L$ exists. By scanning the LCP array, you can enumerate all such passages in linear time.

The advantage of suffix arrays is that they can be built in $O(|T| \log |T|)$ time and then scanned linearly to find all shared substrings. The disadvantage is memory: the suffix array for a trillion-character corpus requires on the order of terabytes of RAM, which forces you to use distributed suffix array construction or to shard the corpus and process shards independently. The Lee et al. implementation used a multi-stage approach: they sharded the corpus, built suffix arrays for each shard, merged the results to find cross-shard duplicates, and then applied the removals in a final pass.

Let us trace through a small example to make suffix arrays concrete. Suppose your corpus (after concatenation) contains the string:

The suffix array, after sorting all suffixes lexicographically, would place the suffix starting at position 0 ("machine learning is hard. machine...") adjacent to the suffix starting at position 26 ("machine learning is hard. deep..."), because both start with "machine learning is hard." The LCP value between these two consecutive sorted suffixes would be 25 (the length of "machine learning is hard."), which exceeds any reasonable threshold $L$, which identifies this as a duplicated passage.

In practice, the corpus is tokenized before building the suffix array, so the "characters" in $T$ are tokens rather than bytes. Token-level suffix arrays have the advantage of operating on a more semantically meaningful unit than bytes, at the cost of a larger alphabet (50,000 token types rather than 256 byte values).

The choice between document-level and substring-level deduplication involves a fundamental trade-off between aggressiveness and information loss.

Document-level deduplication is conservative. It discards entire documents only when they are nearly identical to another document. This means that even a 600-word unique document containing a 400-word duplicated passage survives the dedup step. The model trains on both the unique 200 words and the repeated 400 words, but you at least do not lose the unique content.

Substring deduplication is more aggressive. It removes the repeated passage from some documents (typically keeping one copy of each repeated passage across the corpus and removing it from all other occurrences). This can leave some documents with large gaps where passages were removed, which you must either stitch together carefully or address by discarding any document that lost more than some fraction of its content. Lee et al. used a threshold of 80%: if more than 80% of a document's content was flagged as duplicated passages, the entire document was discarded rather than left as a fragment.

The decision also involves a coverage argument. When you remove a passage from a document, you are reducing the number of contexts in which that passage appears. If the passage is a legitimate scientific finding cited across many papers, removing it from all but one document means the model learns that finding from fewer contexts, potentially reducing its robustness in understanding references to that finding. If the passage is a legal disclaimer appearing identically in thousands of contracts, removing it is clearly beneficial.

In practice, most large-scale data curation pipelines apply both: document-level near-duplicate detection first to remove the most egregious copies, followed by substring deduplication to clean up repeated passages within the surviving documents.