Large-scale Near-deduplication Behind BigCode

Hugging Face has implemented a large-scale near-deduplication pipeline using MinHash and Locality Sensitive Hashing (LSH) to improve the quality of training data for the BigCode project. This process reduces benchmark contamination, mitigates privacy risks, and increases training efficiency by allowing models to achieve similar or better performance with smaller datasets.

The Importance of Deduplication in LLM Training

Data duplication in Large Language Model (LLM) training leads to several critical issues, including the tendency for models to output training data verbatim and increased vulnerability to privacy attacks. Effective deduplication provides three primary advantages:

  • Training Efficiency: Models can achieve equivalent or superior performance with fewer training steps.
  • Evaluation Integrity: Removing duplicates prevents data leakage and benchmark contamination, ensuring that performance improvements are genuine and not the result of the model having seen the test data during training.
  • Accessibility: Reducing the physical size of datasets makes them easier to store, transfer, and collaborate upon.

Technical Implementation: MinHash and LSH

BigCode utilizes a three-step workflow to identify and remove near-duplicate documents at scale.

1. Shingling and Fingerprinting

The process begins with tokenization into n-grams (shingles). For example, word-level tri-grams are used to represent documents. Each shingle is then hashed and permuted multiple times. By taking the minimum hash value for each permutation across all shingles in a document, a "MinHash" fingerprint is created. This operation has a time complexity of $\mathcal{O}(NM)$ (where $N$ is the number of documents and $M$ is the document length), making it linearly scalable through parallelization.

2. Locality Sensitive Hashing (LSH)

To avoid the computationally prohibitive task of comparing every document pair, LSH divides the MinHash fingerprint array into bands. Documents that share the same hash values within a specific band are grouped into the same bucket and flagged as candidate pairs for deduplication.

3. Duplicate Removal and Clustering

Once candidate pairs are identified, BigCode employs a graph-based approach to cluster duplicates into connected components. While initial versions of the pipeline double-checked Jaccard similarities to filter false positives, experiments on "The Stack" dataset revealed that treating all LSH candidates as true positives often yielded the best downstream model performance.

Scaling the Pipeline with Spark

To handle terabyte-scale data, Hugging Face transitioned from local Python frameworks to Apache Spark. This allowed for distributed groupBy operations and the implementation of connected component detection algorithms. Using GCP DataProc, the team successfully deduplicated 1.4 TB of data in under four hours at a cost of approximately $15 per hour.

Impact on Model Performance

Near-deduplication significantly impacts the quality of code models. Key findings include:

  • Dataset Size vs. Performance: Near-deduplication allows a model to perform better with a smaller dataset (e.g., 3 TB vs. 6 TB).
  • Aggressive Deduplication: Further performance gains can be achieved by lowering the similarity threshold and increasing shingle size (e.g., moving from unigrams to 5-grams), which reduces the rate of false positives.
  • Recall: Lowering the similarity threshold increases the recall of high-similarity pairs, removing more redundant data.

Limitations and Future Directions

Near-deduplication is a foundational step but does not replace the need for data quality filtering regarding toxicity, bias, or PII. Furthermore, the team noted that benchmark contamination remains a challenge; for instance, the MBPP benchmark shares significant similarity with Leetcode problems commonly found on GitHub.

Future research directions include exploring substring deduplication for code, detecting repeated paragraphs within single documents, and investigating semantic deduplication using model embeddings to balance diversity and redundancy.

Sources