MinHash Deduplication for LLM Eval Sets

MinHash deduplication can expose near-duplicate LLM eval prompts before repeated evidence inflates a score. This guide builds a seeded, bounded pipeline that screens with MinHash and LSH, verifies with exact Jaccard similarity, and preserves every review decision.

Why MinHash deduplication protects eval confidence

MinHash deduplication is useful when an LLM evaluation set contains prompts that are not byte-identical yet ask essentially the same thing. Repeated paraphrases can make a model look consistently capable while the score is really counting one behavior several times. They also narrow confidence intervals without adding independent evidence. The goal is not to maximize deletion; it is to surface reviewable similarity groups before a score is trusted.

Treat the pipeline as screening. A near-duplicate pair does not prove that a training corpus contains a test case, and it does not prove leakage into tuning. It says two declared comparison units share enough normalized shingles to deserve exact measurement and human review. That boundary matters when communicating results to model owners.

The output should preserve every original identifier, split, label, normalization decision, similarity value, candidate reason, reviewer action, and chosen representative. Without that provenance, deduplication becomes an irreversible preprocessing trick. With it, the score can be recomputed on the full set, a reviewed unique set, or a cluster-weighted set.

This workflow complements LLM eval contamination canary tests: canaries look for suspicious exposure, while duplicate screening asks whether the evaluation itself overcounts closely related cases.

Freeze the comparison unit before hashing

A duplicate policy begins with the object being compared. For multiple-choice evaluation, that might be the stem plus options in their displayed order. For tool use, it may include the user request and tool schema but exclude an ephemeral request identifier. For a multi-turn dialogue, the unit may be the full transcript through the scored turn. Write this contract down before MinHash deduplication runs.

MinHash deduplication starts by keeping stable identifiers beside the text. Record dataset, split, task family, locale, label, and provenance. Cross-split candidates deserve special handling because a training or development example resembling a test example is operationally different from two redundant test cases. The tool should never merge across a protected boundary automatically.

Bound inputs as part of the contract. The accompanying lab accepts at most 100 fixtures and 10,000 characters per fixture. Production jobs may be larger, but the same principle applies: reject surprising size, count malformed records, and publish the skipped population. Silent truncation changes the denominator.

A measurement contract also names the decision downstream. The AI eval measurement contracts guide shows why population, scoring rule, uncertainty, and release threshold travel together. Deduplication changes the population, so its policy and receipt belong beside the score.

Normalize text without erasing meaning

Normalization should remove presentation noise without collapsing distinctions the task actually measures. Unicode normalization, consistent line endings, whitespace folding, and carefully scoped case folding are common. Stripping every digit, punctuation mark, or stop word is dangerous. “Enable logging” and “disable logging” can become deceptively similar if negation disappears; version 2 and version 3 may encode different expected behavior.

Build MinHash deduplication normalization as named, versioned steps. Store the normalized preview and a digest, not merely the final signature. Reviewers need to see why a pair collided. Domain-specific placeholders can help when they are explicit: a randomized account identifier may become a token, while an API status code should remain literal if it changes the answer.

Run adversarial fixtures before a corpus. Include negation flips, reordered choices, changed quantities, code with renamed variables, boilerplate wrappers, Unicode confusables, and translated prompts. The intended policy should catch superficial variants and preserve consequential differences.

LLM eval deduplication is especially sensitive to answer-bearing context. Never normalize labels into prompts, and never use a reference answer to decide textual similarity unless the contract explicitly compares prompt-answer pairs. A clean boundary prevents the deduper from smuggling outcome information into data selection.

Use shingles and exact Jaccard as the oracle

Convert each normalized comparison unit into overlapping token or character shingles. Token shingles preserve word structure; character shingles tolerate small spacing and punctuation changes. A five-token window is a reasonable starting point for prose prompts, but it is a policy parameter, not a universal constant. Short items need smaller windows or a separate exact path.

For shingle sets A and B, exact Jaccard similarity is the size of their intersection divided by the size of their union. Handle two empty sets explicitly and record the rule. This exact calculation is the oracle for candidate pairs because it is deterministic, interpretable, and independent of the MinHash estimate.

The near-duplicate detection study in ACL Anthology demonstrates why surface overlap can reveal important contamination patterns at language-model scale. The same technique needs tighter semantics in an evaluation pipeline: candidate generation is broad, exact verification is authoritative, and removal still requires review.

Keep threshold behavior visible. A pair at 0.79 is not categorically different from one at 0.80; it merely falls on opposite sides of an operating rule. Inspect a band around the threshold, sample rejected pairs, and report how many decisions would change under nearby settings. The oracle informs policy rather than hiding it.

Seed MinHash signatures for reproducibility

MinHash compresses a shingle set into the minimum value produced by each of several hash functions. The fraction of matching signature positions estimates Jaccard similarity. More permutations reduce estimator variance but cost memory and time. A seeded family of hash parameters makes the same input and policy produce the same signature and receipt.

Use a stable shingle encoding and an explicitly named hash construction for MinHash deduplication. Language runtime hashes are often randomized between processes, so they do not belong in a durable pipeline. Record seed, permutation count, shingle size, normalization version, and implementation version. The lab uses a small deterministic integer mixer for explanation; production systems should select a well-reviewed implementation and characterize collisions.

Broder's foundational resemblance and containment paper explains the connection between min-wise samples and set resemblance. The estimator remains an estimate. It can miss a truly similar pair or elevate a dissimilar one, particularly near the decision threshold.

That uncertainty should appear in the interface. Show estimated and exact values together for reviewed candidates. If a report exposes only a cluster label, operators cannot distinguish evidence from the screening shortcut that produced it.

Let LSH propose candidates, then verify exactly

Comparing every signature with every other signature still grows quadratically. Locality-sensitive hashing divides each signature into bands and places equal band slices into buckets. Pairs that share a bucket become candidates; pairs that never share a bucket avoid the expensive exact comparison. Band count and rows per band shape the probability curve.

Tune that curve against labeled duplicate and non-duplicate pairs from the same domain. Too many narrow bands produce a noisy candidate pool; too few wide bands miss useful pairs. Preserve candidates created by multiple bands and report bucket skew, because boilerplate can create enormous buckets that dominate runtime.

Every candidate then returns to exact Jaccard verification. Approximate similarity must never become the keep/drop verdict. The workbench makes that distinction literal: signature agreement and band collisions explain discovery, while exact overlap determines threshold eligibility.

The Hugging Face DataTrove MinHash example is a useful implementation reference for scalable document processing. An eval pipeline adds split protection, labels, review status, and score sensitivity. Those controls are not optional metadata; they are how a fast near-duplicate detector becomes a defensible evaluation operation.

Review clusters and choose representatives

MinHash deduplication pair decisions form a graph. Connected components are convenient clusters, but transitivity can be misleading: A may resemble B and B may resemble C while A does not resemble C. Display the edges and their exact similarities rather than presenting the component as uniformly interchangeable. Flag weak bridges that alone join two dense groups.

Choose representatives with a declared rule. Prefer the earliest source item, the clearest wording, the most complete metadata, or a designated canonical dataset. Do not choose the case a model answers correctly. Preserve protected splits and labels, and block an automatic decision when a component crosses either boundary.

Each reviewed item should receive one disposition: keep as representative, retain as meaningfully distinct, exclude as redundant, or escalate. Record reviewer, timestamp, policy version, reason, representative ID, and every member ID. CSV supports inspection; JSON preserves nested evidence.

This provenance also helps RAG chunking evaluation, where near-identical questions or source passages can exaggerate retrieval consistency. Similarity tooling should expose repeated evidence, not quietly manufacture a cleaner headline metric.

Validate and operate the deduplication pipeline

Validate MinHash deduplication with a labeled fixture set, an all-pairs exact oracle, and negative mutations. Measure candidate recall, candidate precision, exact-verification volume, cluster-size distribution, cross-split flags, reviewer disagreement, and score change under full, unique, and cluster-weighted views. Report all three views when a decision is sensitive to policy.

Run determinism checks across repeated processes. Reorder input records and confirm stable item signatures, pair evidence, components, and receipt hashes after canonical sorting. Change the seed and verify estimates change while exact Jaccard does not. Remove provenance fields in a mutation and require the audit to fail.

Monitor dataset evolution. A new batch may duplicate an earlier test set even when it is internally unique. Compare against a versioned reference index, retain tombstones for removed cases, and rebuild when normalization or shingling changes. Track drift with the same discipline described in embedding drift monitoring: a changed representation invalidates historical comparisons unless versions remain explicit.

The defensible outcome is not “we removed 18 percent.” It is a replayable review set showing what was compared, why each pair surfaced, which exact rule applied, and how the evaluation conclusion changes. That is original measurement evidence rather than cosmetic cleaning.

Runnable local artifact — The lab screens local text similarity; it does not prove training contamination, upload data, delete cases, or replace domain review.

Paste sanitized fixtures; inspect normalized shingles, seeded estimates, exact Jaccard values, LSH candidates, protected splits, and reviewed component receipts; export JSON or CSV.