# PUFFER: Incremental Fuzzy Deduplication for Continuously Evolving Corpora

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 29 Jul 2026.

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [Deduplicating Training Data Makes Language Models Better](https://mlsanity.com/paper/2107.06499/) (2021)
- [Dolma: an Open Corpus of Three Trillion Tokens for Language Model Pretraining Research](https://mlsanity.com/paper/2402.00159/) (2024)
- [Deduplicating Training Data Mitigates Privacy Risks in Language Models](https://mlsanity.com/paper/2202.06539/) (2022)
- [SemDeDup: Data-efficient learning at web-scale through semantic deduplication](https://mlsanity.com/paper/2303.09540/) (2023)
- [D4: Improving LLM Pretraining via Document De-Duplication and Diversification](https://mlsanity.com/paper/2308.12284/) (2023)
- [FineWeb2: One Pipeline to Scale Them All -- Adapting Pre-Training Data Processing to Every Language](https://mlsanity.com/paper/2506.20920/) (2025)
- [LSHBloom: Memory-efficient, Extreme-scale Document Deduplication](https://mlsanity.com/paper/2411.04257/) (2024)
- [LSM-based Storage Techniques: A Survey](https://mlsanity.com/paper/1812.07527/) (2018)
- [FOLD: Fuzzy Online Deduplication for Very Large Evolving Datasets via Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2606.03001/) (2026)

## Abstract (arXiv)

Large language model training corpora grow through successive, often redundant releases, so each release must be deduplicated against both itself and the accumulated history. At trillion-token scale, this requires incremental ingestion, bounded resident memory, deterministic retry, and dataset-scoped lifecycle control without repeated corpus-wide rebuilding. We introduce PUFFER (Provenance-aware Updatable Fuzzy Filtering for Evolving Repositories), a MinHash-LSH fuzzy-deduplication pipeline built around two design choices. First, PUFFER stores each LSH band as immutable, dataset-tagged, memory-mapped sorted segments, enabling exact historical band-key membership checks without RAM proportional to corpus size. Second, T-fanout tiered compaction periodically merges segments to control screening fanout, trading lower query cost against additional index-maintenance writes while preserving membership decisions. Across N ingested keys and K equal-sized releases, PUFFER's cumulative maintenance cost is O(N log N log_T K), compared with Theta(KN) for repeated snapshot rebuilding. Dataset-tagged segments also support dataset-scoped withdrawal: removal is constant-time for uncompacted or protected datasets, while post-compaction withdrawal reconstructs only the affected merged segment, even if the original dataset is unavailable. In our implementation, PUFFER completed cumulative index-stage ingestion for one billion documents in about 1.75 hours in a single process, using 128 bytes per document for a 16-band index. A classical resident MinHash-LSH table required about 6.5 KB per document and exceeded a 900 GiB RAM cap. In a ten-hour comparison capped at one billion documents, PUFFER was 11x faster than LSHBloom and 35x faster than Milvus-LSH. PUFFER is deployed on more than 30 billion documents, and we release it as open-source software at https://github.com/Zyphra/puffer.