Finding near-duplicate documents with MinHash and LSH before you index them for RAG A developer demonstrated a MinHash and locality-sensitive hashing (LSH) pipeline for detecting near-duplicate documents before indexing them for RAG, using 5-word shingles, 128-permutation MinHash signatures built with salted blake2b hashes, and 32-band LSH bucketing to surface candidate pairs. In a four-document test, the approach flagged a re-exported refund policy as a near-copy while distinguishing a version 2 that changed 14 days to 30 and 5 business days to 7, which measured 66% similar. The developer's guidance: deduplicate copies, never deduplicate versions. Document collections are full of near-duplicates : the same policy exported twice, a page with a new footer, version 1 and version 2 of a contract. Indexed for RAG, they fill the top-k results with copies of one passage and crowd out everything else. MinHash finds them efficiently: split each document into overlapping word shingles , and compare documents by Jaccard similarity shared shingles ÷ all shingles . MinHash compresses each document into a short signature whose matching positions estimate Jaccard, and LSH banding finds candidate pairs without comparing every document to every other. One warning from my test: two versions of a policy with different numbers are 66% similar . Deduplicate copies; never deduplicate versions. A shingle is a run of k consecutive words. Two documents that share most of their 5-word runs are near-copies; a reworded document shares few. python title="minhash.py: shingles" import re def shingles text: str, k: int = 5 - set str : words = re.findall r"\w+", text.lower return {" ".join words i:i + k for i in range max 1, len words - k + 1 } def jaccard a: set, b: set - float: return len a & b / len a | b if a | b else 1.0 Exact Jaccard needs every pair of documents compared shingle by shingle: fine for a hundred documents, too slow for a million. MinHash: a signature that estimates Jaccard Hash every shingle with a seeded hash function and keep the minimum . The chance that two documents have the same minimum equals their Jaccard similarity. Repeat with 128 different seeds, and the fraction of matching positions estimates it: python title="minhash.py: signatures" import hashlib def h seed: int, s: str - int: return int.from bytes hashlib.blake2b s.encode , digest size=8, salt=seed.to bytes 8, "little" .digest , "little" def minhash sh: set str , num perm: int = 128 - list int : return min h seed, s for s in sh for seed in range num perm def estimate sig a: list int , sig b: list int - float: return sum x == y for x, y in zip sig a, sig b / len sig a blake2b with a salt gives deterministic seeded hashes from the standard library. Python's built-in hash is randomised per process, so signatures stored in one run wouldn't match the next. Split each 128-number signature into 32 bands of 4 . Two documents that are identical in any band land in the same bucket and become a candidate pair; only candidates are compared. python title="minhash.py: LSH" from collections import defaultdict def near duplicates docs: dict str, str , threshold: float = 0.8, bands: int = 32 - list tuple str, str, float : """LSH: split each signature into bands; documents sharing any identical band become candidates.""" sigs = {doc id: minhash shingles text for doc id, text in docs.items } rows = len next iter sigs.values // bands buckets = defaultdict set for doc id, sig in sigs.items : for b in range bands : buckets b, tuple sig b rows: b + 1 rows .add doc id candidates = {tuple sorted pair for ids in buckets.values for pair in pairs ids } found = a, b, estimate sigs a , sigs b for a, b in candidates return sorted f for f in found if f 2 = threshold , key=lambda f: -f 2 def pairs ids : ids = sorted ids return a, b for i, a in enumerate ids for b in ids i + 1: More bands with fewer rows catch lower similarities but produce more candidates to check. With 32 bands of 4, the chance a pair becomes a candidate is 1 - 1 - s⁴ ³² : almost certain at 0.8 similarity, about 87% at 0.5, and about 5% at 0.2. What did the test show? Four documents: a refund policy, the same policy with a "Last updated" line, a version 2 where 14 days became 30 and 5 business days became 7, and an unrelated shipping page. | Pair | Exact Jaccard | MinHash estimate | | ----------------------- | ------------- | ---------------- | | Policy vs its copy | 0.92 | 0.93 | | Policy v1 vs v2 | 0.66 | 0.62 | | Policy vs shipping page | 0.00 | 0.00 | At a 0.8 threshold, only the copy is found, which is right. At 0.5, version 1 and version 2 are flagged as duplicates . Dropping one of them by similarity alone could leave the outdated refund period in the index. That's the case to design for. How should you act on duplicates? Copies above \~0.9 : keep one, preferably the canonical URL or newest file, and record the others as aliases so citations still resolve. Versions same document, different content : don't drop either blindly. Keep the current one in the index and archive the rest, using dates or version metadata, not similarity. Boilerplate shared across many documents headers, disclaimers inflates similarity; strip it before shingling. Deduplication changes what retrieval returns, so measure before and after with the metrics in how to evaluate a RAG system https://aliahmed.si/blog/rag-retrieval-evaluation-metrics/ . How you split documents matters too; see RAG chunking strategies https://aliahmed.si/blog/rag-chunking-strategies/ . Summary Near-duplicates waste a RAG index and crowd out diverse results. Shingle documents, estimate Jaccard with MinHash , and find candidates with LSH banding . Use deterministic hashes, not Python's randomised hash . Drop copies ; resolve versions with metadata, because similar text can carry different facts. Related: hybrid search with BM25 and RRF https://aliahmed.si/blog/hybrid-search-bm25-reciprocal-rank-fusion/ and embeddings and vector search, explained https://aliahmed.si/blog/embeddings-vector-search-explained/ . --- Written by Ali Ahmed · Original article https://aliahmed.si/blog/minhash-near-duplicate-documents-rag/