高效处理持续更新的语料库去重，10亿文档仅用1.75小时完成
PUFFER: Incremental Fuzzy Deduplication for Continuously Evolving Corpora
- 用分段内存映射存储哈希带，实现无需全量加载的历史去重查询
- 通过分层合并控制查询开销，维护成本仅为传统方法的1/11
- 支持按数据集快速删除，适合超大规模语言模型训练场景
大型语言模型训练语料库随时间不断更新，每次发布都需与自身及历史数据去重。在万亿级文本规模下，需支持增量摄入、内存受限、确定性重试和数据集级生命周期管理，且避免重复全量重建。本文提出PUFFER（面向演化仓库的溯源感知可更新模糊过滤），基于最小哈希-局部敏感哈希（MinHash-LSH）构建去重流水线。核心设计包括：将每个LSH带作为不可变、带标签、内存映射的有序段存储，实现不依赖于语料规模的内存查询；采用T-扇出分层压缩机制定期合并段落，平衡查询效率与索引维护写入开销。在N个输入键、K个等大小发布中，累计维护成本为O(N log N log_T K)，远优于重复快照重建的Theta(KN)。带标签段支持数据集级撤回：未压缩或受保护的数据集删除为常数时间，压缩后仅需重构受影响段落，即使原数据不可用。实验表明，处理10亿文档仅耗时1.75小时，每文档仅需128字节（16带索引），而传统驻留表需6.5KB/文档并超900GiB内存。在10小时对比中，PUFFER比LSHBloom快11倍，比Milvus-LSH快35倍。目前已在超过300亿文档上部署，并开源至https://github.com/Zyphra/puffer。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。