Large-Scale Text Deduplication for LLMs

Two approaches: MinHashLSH for coarse filtering and embeddings for fine-grained deduplication.

The MinHashLSH Approach

Basic Idea

1. Extract n-grams from each document, treating the document as a set of n-grams.
2. Define K hash functions and hash each n-gram to obtain hash sets for each document.
3. For each hash function, take the minimum hash across all n-grams, producing a MinHash signature of length k.
4. Use LSH buckets: split the k dimensions into b bands and hash each whole band to obtain a band_hash.
5. Group by band_idx and band_hash. A matching band_hash means two documents are similar in at least one band, making them comparison candidates. Documents with no matching band_hash need no further processing.
6. Build connected components for documents sharing a band_hash. For an edge (u,v), run multiple rounds of connectivity processing. Assign each processing node a set of doc_ids. In every round:
   1. Send edge (u,v) to the nodes responsible for u and v.
   2. Each node discovers new connections, producing new (u,v) edges. Data accumulates, and the cluster (set of doc_ids) associated with each doc_id grows.
7. After multiple rounds, generally two or three, decide which doc_ids to retain.
8. Scan the original data and retain the nonduplicate doc_ids.

I made a flowchart with Codex:

One detail matters: each doc_id ultimately corresponds to a set of band_hash values, so duplicate detection uses Jaccard similarity. For performance, implementations do not always connect every component for a doc_id and compute the full Jaccard score. For example, BigCode (https://huggingface.co/blog/zh/dedup) treats documents as duplicates if even one band_hash matches. This introduces a probabilistic relationship:

Spark

Spark is the most straightforward approach and was widely used early on. Group by (band_idx, band_hash) and compare matching values. See Alibaba Cloud’s Serverless Spark implementation at https://help.aliyun.com/zh/emr/emr-serverless-spark/use-cases/minhash-lsh-based-large-scale-text-duplication-scheme. However, the connected-component processing involves shuffles, so I do not recommend it.

NeMo Curator (Open Source from NVIDIA, Based on Ray)

ref: https://docs.nvidia.com/nemo/curator/curate-text/process-data/deduplication/fuzzy

• It follows the same basic idea but uses GPU libraries. LSH processes only five bands at a time, persisting intermediate results as Parquet.
• MinHash uses cuDF, while connected components use cuGraph’s multi-GPU weakly connected components algorithm. Duplicate verification is also less strict.

Data-Juicer (The Basic Approach on Ray, with Hotspot Optimizations)

ref: https://github.com/datajuicer/data-juicer/blob/main/data_juicer/ops/deduplicator/ray_bts_minhash_deduplicator.py#L689

1. Scan the data and calculate band hashes. First merge locally within each actor into a two-level connected graph, pointing all doc_ids to the smallest doc_id.
2. Reshuffle by doc_id. Each actor owns a subset of doc_ids, and each edge is sent to two actors.
3. After multiple reshuffle rounds, each actor has a doc_id-to-cluster mapping and decides which values are duplicates.

What if a cluster is too large, as with license text? A proxy-based rebalancing approach avoids placing the entire cluster on one node. Each node holds its own smaller cluster, whose root acts as a proxy connected to the actual root. Changes to the actual root may require communication between actors.

SimHash

For text:

1. Tokenize the text or extract features.
2. Compute a standard hash for each feature.
3. Weight features using term frequency, TF-IDF, or similar measures.
4. Perform a weighted vote for each bit across feature hashes.
5. Set each bit to 1 if its total is positive, otherwise 0, producing a fixed-length SimHash.

SimHash has a drawback: with relatively few bits, individual keywords, such as Python or README in code, can have too much influence. MinHashLSH is therefore more common for LLM text today.

The Embedding Approach

Kmeans

A straightforward option is to reuse Faiss, which also supports GPUs. Its k-means approach works as follows:

1. Sample the data and train k-means to obtain k cluster centroids.
2. Scan the existing data, assign and distribute it to clusters, then deduplicate embeddings within each centroid’s cluster, essentially using matrix multiplication.
3. If the k clusters are still too large, cluster again into k groups. Two rounds should be sufficient.

Embedding Similarity

Another option is a distributed embedding service with indexes. Two common index types are:

1. HNSW: Similar to a Skip List

• Idea: Dynamically build a graph as embeddings are inserted. As their number grows, construct multiple layers of subgraphs. A level n+1 subgraph can be viewed as connections among selected central points from the level n graph.
• Characteristics: Slow writes because of graph construction; fast queries because the skip-list-like structure quickly locates relevant regions.

2. IVF: An Inverted-Index Approach

• Idea: Sample embeddings and train k-means to obtain centroids. Each cluster contains a group of embeddings, resembling an inverted index. Queries locate the cluster and then calculate similarity within its list.
• Characteristics: Fast writes, which become append operations after k-means training; slower queries that scan inverted lists, with potential hotspots.

IVF has many variants. The common version described above is IVF-FLAT, whose query time grows linearly when a cluster contains too many items. IVF-PQ builds on IVF-FLAT: in each cluster’s inverted list, split every m-dimensional embedding into n segments, run k-means independently on each segment, and obtain a fixed-size K codebook. Each embedding can be represented through its distances to these codebooks, with length n.

• IVF-PQ = IVF-Flat + a PQ codebook in each cluster, substantially reducing similarity computation.

IVF-PQ queries are fast thanks to multiple index levels, but the original embedding values are lost. A vector_id-to-embedding mapping must therefore be maintained on disk; memmap provides fast reads.

Measurements

Today I tested a single-machine FAISS database with 14 million document embeddings of 384 dimensions:

• IVF-FLAT: About one minute to train k-means and five minutes to insert (50k/s); with nprobe=4, query p99 was 4 ms.
• HNSW: 52 minutes to insert; queries took 0.7 ms.

Use cases:

• For one-off offline deduplication, follow the IVF approach: cluster first, then compare pairs within each cluster.
• For continuously arriving data, use an embedding cluster for deduplication.

Additional Notes

datasketch

An interesting open-source project supports various deduplication methods and external embedding databases. It is suitable for experimenting on one machine and sufficient for smaller datasets.

• https://github.com/ekzhu/datasketch