#大模型预训练数据准备中的去重算法：从 ExactSubstr 到 MinHash LSH 与语义去重

#一句话核心结论

今天大模型预训练数据去重的事实标准，仍然是“精确去重 + MinHash LSH 近重复去重”的组合；如果追求更强的数据效率，可以再叠加句子级/子串级去重和 embedding-based 语义去重，但后两者更依赖阈值、算力和质量评估，通常作为增强模块，而不是完全替代 MinHash。

如果只记一个实践建议：

先做 URL/文档级 exact dedup，再做 normalized-text 的 MinHash LSH near-dedup；对于高价值语料或图文/多模态语料，再考虑 SemDeDup 式语义去重；对训练/评测污染敏感的场景，单独做 benchmark contamination filtering。

#1. 为什么预训练数据去重如此重要？

Web-scale 语料天然存在大量重复：镜像站、转载、模板页、导航栏、版权声明、论坛引用、爬虫重复抓取、Common Crawl 多 snapshot 重叠、同一文章不同 URL、轻微改写的 SEO 页面等。重复数据会带来四类问题：

1. 训练效率浪费：模型反复看同一段内容，token budget 被低信息量样本占用。
2. 记忆与泄漏：重复出现的长字符串更容易被模型 verbatim memorization，增加隐私、版权和 benchmark contamination 风险。
3. 分布扭曲：被转载/模板化的内容权重被不成比例放大，影响模型学到的知识分布。
4. 评估虚高：如果训练集中存在测试集或其近似副本，模型能力会被高估。

Lee et al. 的经典工作 Deduplicating Training Data Makes Language Models Better 发现，已有语言模型数据集中存在大量 near-duplicate examples 和 long repetitive substrings；去重后模型生成中逐字复制训练数据的比例显著降低，训练也更高效。这篇工作基本奠定了 LLM 数据准备中“去重不是清洗小步骤，而是训练质量核心组件”的共识。

#2. 发展脉络：去重算法从“完全一样”走向“语义相似”

#阶段 A：精确去重——把完全相同的文档/行/句子删掉

之前的问题：早期网页语料中最显眼的是完全重复文档，比如同一 URL 被多次抓取、多个 dump 重复、同一文件重复入库。

解决方法：对 normalized text 做哈希，例如 MD5、SHA1、xxHash，按 hash 分组，只保留一个副本。粒度可以是文档、段落、句子或行。

优点：极快、可解释、误删风险低、工程成本最低。

新问题：Web 重复往往不是完全一样，而是“主体一样但模板、广告、时间戳、空格、标点、少量段落不同”。精确哈希无法识别这类近重复。

实践地位：必须做，但只够当第一层过滤。

#阶段 B：长公共子串/后缀数组——解决“局部大段复制”

之前的问题：两个文档可能不是整体重复，但包含大段相同文本，比如新闻转载、论坛引用、书籍片段、代码片段、模板 boilerplate。文档级哈希无法发现。

解决方法：使用后缀数组、ExactSubstr 等方法发现跨文档长重复子串，并移除或标记重复片段。Google Research 的 deduplicate-text-datasets 开源了 ExactSubstr 实现。

代表工作：Lee et al. 2021 讨论了 ExactSubstr 和 NearDup 两类工具。ExactSubstr 偏向找到长的逐字重复 substring；NearDup 偏向文档级近重复聚类。

新问题：子串级算法对超大规模数据工程要求高；如果阈值不当，可能破坏文档结构；对“语义相近但表面不同”的重复仍然无能为力。

实践地位：非常适合减少 memorization 和长片段污染，但在通用 web-scale pipeline 中通常作为增强，而不是唯一主干。

#阶段 C：MinHash + LSH——当前最主流的近重复去重事实标准

之前的问题：需要一种能在万亿 token / 数十亿文档规模上找到“主体内容高度重叠但不完全相同”的算法，同时不能做全量两两比较。

解决方法：

1. 将文档切成 shingles，常见是 word n-grams 或 token n-grams。
2. 每个文档被表示为 shingle 集合。
3. 用 MinHash 估计两个集合的 Jaccard 相似度。
4. 用 LSH（Locality-Sensitive Hashing） 把相似文档分到同一 bucket，避免 O(N²) 比较。
5. 对候选重复组做 connected components / clustering，只保留每组中质量最高或最早的文档。

为什么它成为主流？

• 效果足够好：对网页近重复、转载、模板化文本非常有效。
• 规模友好：不需要计算所有 pairwise similarity。
• 模型无关：不依赖 embedding 模型，跨语言/跨领域更稳健。
• 工程成熟：DataTrove、NeMo Curator、datasketch、Spark/Ray/Slurm 管线都有相关实现。
• 可控性强：阈值、shingle 大小、hash 数量、banding 参数都能显式调节。

新问题：

• 主要捕捉 lexical overlap，而不是真正语义重复。
• 对短文本不稳定；短文档 shingle 太少，Jaccard 估计噪声大。
• 阈值选择会影响多样性：过低会误删同主题不同观点，过高会漏掉轻微改写。
• 多语言和代码数据需要不同 normalization 与 tokenization。

实践地位：这是当前“最好、最新、最有效且使用人数最多”的核心答案。更准确地说，MinHash LSH 不是最新的理论算法，但它是当前最成熟、最广泛采用、性价比最高的 web-scale LLM 预训练去重算法。

#阶段 D：语义去重 SemDeDup / embedding dedup——从表面重复走向语义冗余

之前的问题：MinHash 只能看字面重叠。如果两段文本表达同一事实但措辞不同，或者图文数据中图片/标题语义相似，MinHash 很难发现。

解决方法：用预训练模型生成 embedding，在向量空间中搜索高相似样本；再按相似度阈值、聚类或 kNN 图删除语义重复。SemDeDup 提出用 embedding 去识别 semantic duplicates，并显示在 LAION 等 web-scale 数据上去掉语义重复可以保持性能并节省训练。

优势：

• 能识别 paraphrase、同义改写、图文语义近似。
• 对多模态数据尤其有价值，例如 CLIP embedding 用于图文数据去重。
• 可以作为“数据效率”工具，减少同质化样本。

风险：

• embedding 模型本身有偏差，可能把“相似但互补”的样本误删。
• 阈值非常敏感；不同领域、语言、长度需要不同策略。
• 成本高，需要向量索引、GPU/ANN 检索和额外评估。
• 对基础模型预训练来说，语义多样性本身可能是能力来源，不能盲目删。

实践地位：很有前景，尤其适合高冗余语料、多模态语料和数据效率研究；但在通用 LLM 文本预训练中，通常建议作为 MinHash 之后的可选增强。

#3. 当前推荐的主流 pipeline

一个比较稳健的大模型预训练去重流程通常是：

我的建议排序：

1. 必做：文档级 exact dedup。
2. 强烈建议做：MinHash LSH 文档级 near-dedup。
3. 看数据特征做：句子/段落级 exact dedup，用于模板很多的网页语料。
4. 高价值场景做：ExactSubstr 或长 n-gram contamination filtering。
5. 研究/高算力/多模态场景做：SemDeDup / embedding semantic dedup。

#4. MinHash LSH 细节：为什么它是今天最值得掌握的算法？

#4.1 核心直觉

如果两个文档共享很多 shingles，那么它们的 Jaccard 相似度高：

但直接算所有文档 pair 的 Jaccard 不现实。MinHash 的关键性质是：

两个集合在随机哈希下最小 hash 值相同的概率，等于它们的 Jaccard 相似度。

所以可以用多个 hash 函数得到一个签名向量，近似估计 Jaccard。LSH 再把签名分 band；只要某个 band 完全相同，就认为两篇文档是候选近重复。

#4.2 常用参数

• shingle size：常见 5-gram、7-gram、13-gram。越小越敏感，越大越保守。
• num permutations / num hashes：常见 64、128、256。越大估计越准，成本越高。
• Jaccard threshold：常见 0.7–0.9。网页去重常在 0.8 附近调参；保守场景用更高阈值。
• normalization：lowercase、unicode normalization、空白归一、去 HTML、去 boilerplate、标点处理。这个步骤往往比算法本身更影响结果。
• 保留策略：重复簇中保留质量分最高、长度合适、来源可信、语言识别置信度高的文档。

#4.3 它解决了什么，没解决什么？

解决：转载、镜像、轻微编辑、模板重复、同一网页多次抓取。

没解决：语义复述、主题过度集中、低质量但不重复内容、事实错误、benchmark 语义污染。

因此，去重不应被理解为“数据质量”的全部，而是数据过滤、质量打分、来源混合、毒性/PII 过滤、语言识别、benchmark contamination filtering 中的一环。

#5. 代表工具与推荐网站

#5.1 Hugging Face DataTrove

• 网站/GitHub：https://github.com/huggingface/datatrove
• 适合：开源 LLM 数据处理、Common Crawl/FineWeb 风格 pipeline、Slurm/Ray/本地执行。
• 亮点：DataTrove 是 Hugging Face 用于大规模文本处理、过滤和去重的库，FineWeb 相关数据处理也高度依赖这类模块化 pipeline。它包含 MinHash dedup、sentence dedup 等示例。
• 推荐理由：如果你要真正复现或搭建开源 LLM 预训练数据管线，这是目前最值得看的工程入口之一。

#5.2 NVIDIA NeMo Curator

• 文档：https://docs.nvidia.com/nemo/curator/latest/curate-text/process-data/deduplication/index.html
• GitHub：https://github.com/NVIDIA/NeMo-Curator
• 适合：GPU 加速数据清洗、企业级/大规模数据处理、多模态数据清洗。
• 亮点：官方文档明确提供三类去重：exact matching、fuzzy matching（MinHash + LSH）、semantic matching（embeddings），并强调 GPU 加速和数据处理 pipeline 集成。
• 推荐理由：如果你关注“最快、工程最强、可扩展”，NeMo Curator 是当前非常重要的工具链。

#5.3 Google Research deduplicate-text-datasets

• GitHub：https://github.com/google-research/deduplicate-text-datasets
• 论文：https://arxiv.org/abs/2107.06499
• 适合：理解 ExactSubstr、NearDup、memorization 与去重关系。
• 亮点：来自经典论文《Deduplicating Training Data Makes Language Models Better》的实现，包含 ExactSubstr Rust 实现和 NearDup 结果。
• 推荐理由：这是理解“为什么去重会让 LM 更好”的必读入口。

#5.4 SemDeDup

• 论文：https://arxiv.org/abs/2303.09540
• 适合：语义去重、数据效率、多模态/web-scale 数据冗余研究。
• 亮点：使用预训练模型 embedding 找 semantic duplicates，目标是删除“语义上重复但表面不完全重复”的样本。
• 推荐理由：如果你想研究“数据分布如何塑造模型能力”，SemDeDup 比传统 MinHash 更接近机制性问题。

#5.5 FineWeb / FineWeb-Edu

• FineWeb blog：https://huggingface.co/spaces/HuggingFaceFW/blogpost-fineweb-v1
• 论文：https://arxiv.org/abs/2406.17557
• 适合：学习现代开源 web pretraining dataset 的整体构建方法。
• 亮点：FineWeb 是 15T token 级别开放数据集，围绕 Common Crawl 清洗、过滤、去重和 ablation 展开。
• 推荐理由：不要只看算法，要看整个 pipeline 如何影响下游模型表现；FineWeb 是非常好的现代案例。

#5.6 datasketch / Spark MinHashLSH / FAISS

• datasketch：https://ekzhu.com/datasketch/lsh.html
• Spark MinHashLSH：https://spark.apache.org/docs/latest/ml-features.html#minhash-for-jaccard-distance
• FAISS：https://github.com/facebookresearch/faiss
• 适合：自己搭建原型或理解底层近邻搜索。
• 推荐理由：datasketch 适合快速实验 MinHash LSH；Spark 适合传统大数据平台；FAISS 适合 embedding-based semantic dedup。

#6. “最好、最新、最有效、使用人数最多”的判断

如果按不同维度排序：

所以，综合推荐是：

生产级 LLM 文本预训练：DataTrove 或 NeMo Curator 中的 exact dedup + MinHash LSH 是首选；研究级数据效率/语义冗余：在其后加入 SemDeDup；隐私、版权、评测污染敏感：再加入 ExactSubstr/长 n-gram 过滤。

#7. 和基础模型训练机制相关的几个开放问题

#7.1 去重到底是在提升质量，还是在改变训练分布？

重复样本相当于隐式 reweighting。删除重复不只是“清理垃圾”，而是在重新定义训练分布。某些高频重复内容可能代表真实世界重要知识，也可能只是 SEO 噪声。关键问题是：什么重复应该保留为“重要性权重”，什么重复应该删除为“爬虫偏差”？

#7.2 语义去重会不会误删能力形成所需的多样化 paraphrase？

对 LLM 来说，同一个概念的多种表达可能正是泛化能力来源。语义去重如果过强，可能让模型见不到足够的语言变体。未来更好的方向可能不是简单删除，而是做 redundancy-aware reweighting：降低冗余样本权重，而不是完全移除。

#7.3 去重应该发生在 token 级、文档级，还是训练动态中？

传统 pipeline 在训练前静态去重。但从机制上看，模型训练过程中对样本的 marginal utility 会变化：早期重复样本可能帮助稳定学习，后期则造成浪费。未来可能出现 training-dynamics-aware dedup 或 curriculum dedup。

#7.4 Agent 数据和代码数据是否需要新的去重定义？

代码和 agent 轨迹中，重复不一定是坏事。相似任务的不同解法、不同错误恢复路径，可能蕴含过程能力。简单 MinHash 可能删除“表面相似但策略不同”的轨迹。对 agent pretraining 来说，更合理的去重对象可能不是文本，而是 state-action-outcome 结构。

#8. 最后建议

如果你现在要做一个 LLM 预训练数据准备系统，我会这样落地：

1. 先用 DataTrove 快速搭一版 pipeline：解析 Common Crawl / JSONL，做语言识别、质量过滤、exact dedup、MinHash LSH。
2. 用 NeMo Curator 对 GPU 加速版本做对照：特别是数据规模很大、需要多机 GPU 或语义去重时。
3. 单独复现 Google ExactSubstr 思路：用于分析 memorization、benchmark contamination、长片段复制。
4. 把 SemDeDup 当作研究模块：研究不同 embedding、阈值、聚类策略对下游能力和数据效率的影响。
5. 不要只比较去重率：最终要看 validation loss、下游任务、memorization、contamination、diversity、domain coverage 的综合变化。

去重的本质不是“删掉重复文本”这么简单，而是一个关于 训练分布、样本权重、数据效率和模型记忆机制 的问题。MinHash LSH 是当前最可靠的工程主干，而语义去重和动态数据重加权，可能是下一阶段更值得研究的方向。