Deduplication: removing near-identical documents before training

The problem, from first principles

Real training corpora, scraped from the web or assembled from many sources, contain a LOT of near-duplicate content: the same article mirrored on several sites, boilerplate legal text repeated across thousands of documents, near-identical product descriptions. Training on heavily duplicated data wastes compute (the model sees essentially the same information many times over, without learning anything new from the repetition) and, more seriously, can cause the model to MEMORIZE that duplicated content disproportionately (Lee et al. 2021 showed measurably higher memorization and verbatim regurgitation of content that appears many times in training data), a real quality and privacy concern for production LLMs. Deduplication removes documents that are EXACT or NEAR duplicates of something already kept, before training ever sees them.

From theory to code

Implement jaccard_similarity(tokens_a, tokens_b), a standard set-overlap similarity measure, and deduplicate_documents(documents, threshold), greedily keeping a document only if it isn't a near-duplicate (similarity >= threshold) of anything ALREADY kept.

Constraints

• Jaccard similarity operates on token SETS, not lists: |intersection| / |union|, so repeated tokens within one document don't inflate similarity.
• deduplicate_documents processes documents IN ORDER, comparing each one against EVERY already-kept document (not just the immediately preceding one), keeping it only if it fails to match (at or above threshold) all of them.
• Returns the INDICES of kept documents (into the original list), preserving their original relative order.

Hints

set_a, set_b = set(tokens_a), set(tokens_b)
return len(set_a & set_b) / len(set_a | set_b)

kept_indices = []
for i, doc in enumerate(documents):
    if not any(jaccard_similarity(doc, documents[j]) >= threshold for j in kept_indices):
        kept_indices.append(i)
return kept_indices