# LSHBloom: Memory-efficient, Extreme-scale Document Deduplication

arXiv: https://arxiv.org/abs/2411.04257 · HTML: https://mlsanity.com/paper/2411.04257/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 85 references that are in the map.
- First posted on arXiv 6 Nov 2024.

## Builds on (most cited first, 29 of 29)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Scaling Language Models: Methods, Analysis & Insights from Training Gopher](https://mlsanity.com/paper/2112.11446/) (2021)
- [Gemma: Open Models Based on Gemini Research and Technology](https://mlsanity.com/paper/2403.08295/) (2024)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [StarCoder: may the source be with you!](https://mlsanity.com/paper/2305.06161/) (2023)
- [Deduplicating Training Data Makes Language Models Better](https://mlsanity.com/paper/2107.06499/) (2021)
- [CCNet: Extracting High Quality Monolingual Datasets from Web Crawl Data](https://mlsanity.com/paper/1911.00359/) (2019)
- [StarCoder 2 and The Stack v2: The Next Generation](https://mlsanity.com/paper/2402.19173/) (2024)
- [Dolma: an Open Corpus of Three Trillion Tokens for Language Model Pretraining Research](https://mlsanity.com/paper/2402.00159/) (2024)
- [DataComp-LM: In search of the next generation of training sets for language models](https://mlsanity.com/paper/2406.11794/) (2024)
- [SemDeDup: Data-efficient learning at web-scale through semantic deduplication](https://mlsanity.com/paper/2303.09540/) (2023)
- [Nougat: Neural Optical Understanding for Academic Documents](https://mlsanity.com/paper/2308.13418/) (2023)
- [A Comprehensive Survey of Scientific Large Language Models and Their Applications in Scientific Discovery](https://mlsanity.com/paper/2406.10833/) (2024)
- [Reuse, Don't Retrain: A Recipe for Continued Pretraining of Language Models](https://mlsanity.com/paper/2407.07263/) (2024)
- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [UniSeg: A Prompt-driven Universal Segmentation Model as well as A Strong Representation Learner](https://mlsanity.com/paper/2304.03493/) (2023)
- [Parsl: Pervasive Parallel Programming in Python](https://mlsanity.com/paper/1905.02158/) (2019)
- [Smaller Language Models are Better Black-box Machine-Generated Text Detectors](https://mlsanity.com/paper/2305.09859/) (2023)
- [Evading Data Contamination Detection for Language Models is (too) Easy](https://mlsanity.com/paper/2402.02823/) (2024)
- [LSH Ensemble: Internet-Scale Domain Search](https://mlsanity.com/paper/1603.07410/) (2016)
- [TRUCE: Private Benchmarking to Prevent Contamination and Improve Comparative Evaluation of LLMs](https://mlsanity.com/paper/2403.00393/) (2024)
- [1.5-Pints Technical Report: Pretraining in Days, Not Months -- Your Language Model Thrives on Quality Data](https://mlsanity.com/paper/2408.03506/) (2024)
- [On the Optimal Time/Space Tradeoff for Hash Tables](https://mlsanity.com/paper/2111.00602/) (2021)

## Built on by (most cited first, 5 of 5)

- [A Survey of LLM × DATA](https://mlsanity.com/paper/2505.18458/) (2025)
- [Byte-Exact Deduplication in Retrieval-Augmented Generation: A Three-Regime Empirical Analysis Across Public Benchmarks](https://mlsanity.com/paper/2605.09611/) (2026)
- [Merlin: Deterministic Byte-Exact Deduplication for Lossless Context Optimization in Large Language Model Inference](https://mlsanity.com/paper/2605.09990/) (2026)
- [LP Data Pipeline: Lightweight, Purpose-driven Data Pipeline for Large Language Models](https://mlsanity.com/paper/2411.11289/) (2024)
- [PUFFER: Incremental Fuzzy Deduplication for Continuously Evolving Corpora](https://mlsanity.com/paper/2608.28622/) (2026)

## Abstract (arXiv)

Contemporary large language model (LLM) training pipelines require the assembly of internet-scale databases full of text data from a variety of sources (e.g., web, academic, and publishers). Preprocessing these datasets via deduplication -- detecting and eliminating additional instances of the same content -- is a major focus for assembling and curating training datasets for LLMs. Unrestrained, duplicates in the training dataset increase training costs and lead to undesirable properties such as memorization in trained models or cheating on evaluation. Unfortunately, contemporary approaches to document-level deduplication are either unreliable at accurately identifying duplicate documents or extremely expensive in terms of both runtime and memory. We propose LSHBloom, an extension to MinhashLSH, which replaces the expensive LSHIndex with lightweight Bloom filters. LSHBloom demonstrates the same state-of-the-art deduplication performance as MinhashLSH, with only a marginal increase in false positives (near zero in our experiments), while boasting competitive runtime (12× faster than MinhashLSH on peS2o) and, crucially, using 18× less disk space than MinhashLSH (as measured on peS2o). Based on extrapolation, we show that this advantage in space and runtime remains even at the extreme scale of several billion documents. LSHBloom allows practitioners to access the deduplication quality of MinHashLSH at scales that are normally only tractable for less sophisticated, heuristic solutions. As a result, LSHBloom promises to enable scaling high-quality document deduplication to internet-scale text datasets.