💬 NLP

SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora

SoftMatcha 2 是一种超快速、灵活的搜索算法，它通过利用后缀数组、基于向量的词表示以及动态语料库感知剪枝来缓解组合爆炸，从而实现对万亿级规模语料库的亚 0.3 秒语义模式匹配。

原作者： Masataka Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi

发布于 2026-06-11

📖 1 分钟阅读☕ 轻松阅读

原作者： Masataka Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你拥有一座包含一万亿本书的图书馆。这不仅仅是很多书，这是一个规模宏大的图书馆，如果你试图读完每一个字，将需要数百万年。现在，想象你想在那个图书馆中寻找一个特定的句子，但你不记得确切的词汇了。也许你记得那个“想法”，或者你知道那个句子略有不同（例如，你记得是“机器的重要性”，但书里写的其实是“机器的意义”）。

这就是 SoftMatcha 2 所解决的问题。它是一个超快速的搜索引擎，旨在即使在你的查询与精确匹配不符的情况下，也能在不到 0.3 秒的时间内，在万亿级规模的图书馆中找到文本。

以下是它的工作原理，通过简单的类比进行拆解：

1. 问题所在：“组合爆炸”

如果要求计算机寻找与你的查询“相似”的文本，它会面临一个噩梦般的场景。

类比： 想象你正在食谱书中寻找一种特定的食谱。如果你说，“帮我找类似‘巧克力蛋糕’的东西”，计算机必须检查所有可能的变体：“巧克力玛芬”、“黑巧克力蛋糕”、“巧克力派”、“带坚果的巧克力蛋糕”、“去掉坚果的巧克力蛋糕”等等。
问题： 随着你的查询变长，可能出现的变体数量会呈指数级爆炸。这就像是在草堆里找一根针，但每当你寻找时，草堆就会变成一座大山。之前的工具要么会被困在这座大山中，要么只能寻找那根“精确”的针，从而错过了那些相似的针。

2. 解决方案：两个神奇的技巧

SoftMatcha 2 使用两个聪明的技巧来驯服这座可能性之山：

技巧 A：“智能过滤器”（动态语料库感知剪枝）

系统不是检查你的搜索中所有可能的变体，而是先检查图书馆中实际存在的内容。

类比： 想象你在一个巨大的停车场里寻找一种特定类型的汽车。与其检查所有可能存在的车型（比如“飞行汽车”或“水下汽车”），不如先观察停车场并说：“好吧，我看到这里有红色轿车和蓝色卡车，但没有飞行汽车。”
工作原理： 系统会构建一个相似词汇的列表（如同义词），但会立即丢弃任何实际上并未出现在万亿级语料库中的组合。它利用语言的统计“形状”（例如某些词非常常见而另一些词很罕见）在开始搜索之前就剔除掉不可能的选项。这阻止了搜索空间的爆炸。

技巧 B：“磁盘感知地图”（快速精确查找）

图书馆太大，无法装入计算机的主内存（RAM），因此它存储在硬盘（磁盘）上。从磁盘读取通常很慢，就像去仓库取书一样。

类比： 在一个标准的图书馆里，你必须走到书架前，找到书，走回来，然后重复这个过程数百次。SoftMatcha 2 构建了一张特殊的“地图”（后缀数组），能准确告诉管理员该去哪里。
创新点： 大多数搜索工具需要管理员多次往返仓库寻找书籍。SoftMatcha 2 的新地图设计使得管理员只需要前往仓库一次，就能找到精确的位置。这使得寻找精确文本变得极其迅速，即使图书馆存储在缓慢的磁盘上。

3. 它能做什么（“软”的部分）

因为它将这些速度技巧与对词义的理解（使用词向量）相结合，所以它可以处理“软”搜索：

替换： 你搜索“金牌”，它能找到“银牌”（因为它们相关）。
插入/删除： 你搜索“机器的重要性”，它能找到“机器的重要性”（增加了一个词）或“机器学习的重要性”（增加了词组）。
顺序很重要： 与其他仅关注“词袋”模型的工具不同，SoftMatcha 2 尊重顺序。它知道“狗咬人”与“人咬狗”是不同的。

4. 现实世界的结果

研究人员在包含 1.4 万亿个单词 的 FineWeb-Edu 数据集上测试了该系统。

速度： 它在 0.3 秒 内找到了结果。
对比： 它比之前的最佳精确搜索工具（infini-gram）快了 33 倍，并且明显快于之前的“软”搜索工具（SoftMatcha），后者根本无法处理如此大规模的库。
发现： 由于它在寻找“近似匹配”方面表现出色，研究人员利用它发现了训练数据中的**污染（Contamination）**问题。他们发现，一些用于 AI 基准测试的测试题以略微不同的形式出现在了训练数据中（例如，数字改变了或单词被替换了），而之前的精确匹配工具错过了这些情况。这就像是发现了一个通过稍微修改数字就抄袭了答案集的学生。

总结

SoftMatcha 2 是世界最大图书馆里的超级快速图书管理员。它不仅能寻找与你请求完全一致的副本；它还能理解含义并找到相似的句子，即使你漏掉了一个词或用一个同义词替换了某个词。它通过聪明地忽略不可能的选项，并使用高效的地图来导航庞大的数据存储，从而在眨眼之间完成任务。

技术摘要：SoftMatcha 2

问题陈述

大语言模型（LLM）的快速规模化使得训练语料库必须达到万亿级 Token（例如包含 1.4T Token 的 FineWeb-Edu）。现有的语料库搜索工具在处理这些数据时面临三个独特的挑战，而当前的方法无法同时解决这些问题：

可扩展性： 搜索方法必须能够扩展到万亿级 Token 的数据集，且不会产生过高的延迟或内存成本。
语义灵活性： 自然语言查询需要检索语义相似的文本，能够容忍替换、插入和删除，而非仅仅依赖精确的字符串匹配。
顺序敏感性： 与词袋模型（如 TF-IDF、BM25）或稠密向量搜索（通常会丢失词序）不同，查询中单词的具体序列承载着意义，在检索过程中必须予以保留。

以往的方法，如 infini-gram（仅限精确匹配）和 SoftMatcha（具备语义能力但受限于倒排索引的可扩展性），无法同时满足这三个要求。具体而言，SoftMatcha 对倒排索引的依赖使其无法扩展到万亿级规模的语料库，而精确匹配工具则会遗漏关键的语义变化，如模板泄露或轻微的改写。

方法论

SoftMatcha 2 引入了一种超快速、灵活的搜索算法，它结合了后缀数组与词向量，以实现大规模的软模式匹配（soft pattern matching）。该方法通过两项主要的算法创新来缓解语义松弛带来的组合爆炸问题：

1. 动态语料库感知剪枝（Dynamic Corpus-Aware Pruning）

为了解决允许替换、插入和删除时候选模式呈指数级增长的问题，该算法采用了迭代剪枝策略（算法 1）：

迭代剪枝： 该算法并非在全球范围内枚举所有可能的相似模式，而是逐个 Token 构建候选模式。在每一步 $i$ ，它生成与查询前缀 $q_1 \dots q_i$ 相似的候选者，然后立即通过精确查找将其与语料库进行比对。这利用了自然语言中 n-gram 的幂律分布特性，通过尽早丢弃语料库中不存在的候选者，极大地缩小了搜索空间。
k-gram 剪枝： 高频的 2-gram 和 3-gram 会被预先检查并缓存在 RAM 中，以避免为常见的组合进行磁盘访问。
末位比特剪枝（Last-bits Pruning）： 对于出现次数极少（≤50）的模式，算法直接枚举其在语料库中的出现位置，而不是追加后缀，从而绕过了进一步的后缀数组查找。

2. 磁盘感知型分阶段后缀数组（Disk-Aware, Staged Suffix Arrays）

为了处理万亿级 Token 语料库所需的庞大索引规模（>5 TB，无法全部装入 RAM），作者设计了一种全新的磁盘感知后缀数组：

两阶段索引： 受 BigTable 启发，该索引由一个存储在磁盘上的所有连续 $L$ -token 的排序数组 $X$ ，以及一个存储在 RAM 中的稀疏数组 $Y$ （包含 $X$ 中每隔 $B$ 个元素的元素）组成。
效率： 为了定位查询，算法首先使用 $Y$ 来确定 $X$ 中的近似范围（仅需一次 RAM 访问），然后在磁盘上的该特定范围内执行单次二分查找。这使得每次精确匹配查找的随机磁盘访问次数从标准后缀数组的 $O(\log|C|)$ 降低到了一次随机磁盘访问。
压缩： 索引应用了游程编码（Run-length compression），将 FineWeb-Edu 索引的理论磁盘占用从 56 TB 降至 21.6 TB。

3. 软相似度度量（Soft Similarity Measure）

系统定义了一种新型相似度函数 $sim(\bar{q}, \bar{p})$ ，它集成了：

平滑最小值（Smooth Minimum）： 词向量余弦相似度的参数化平滑最小值，避免了普通最小值（忽略非最小得分）和简单求和（过度惩罚多个不匹配）的缺陷。
基于范数的惩罚： 插入和删除的惩罚基于插入/删除 Token 向量的范数（经过齐普夫白化处理后），确保低信息量词汇（如“the”）产生的惩罚比高信息量词汇更小。
自适应阈值： 系统动态调整相似度阈值 $\alpha$ 以确保返回目标数量的结果（ $K$ ），防止在面对困难查询时出现空结果集。

核心贡献

算法提案： SoftMatcha 2 是首个在万亿级语料库上实现具备词序保持能力的软（词汇-语义）搜索的方法，它结合了动态剪枝与磁盘感知后缀数组。
理论分析： 论文提供了一个理论证明，即在齐普夫定律（Zipf's law）下，预期精确查找次数相对于语料库规模是亚线性的（ $O(|C|^{1/\delta})$ ），证明了剪枝策略有效地缓解了指数级的搜索空间增长。
实证性能：
- 延迟： 在 FineWeb-Edu（1.4T Token）上，SoftMatcha 2 实现软搜索的第 95 百分位延迟为 278.17 ms，精确搜索延迟为 0.34 ms。
- 对比： 其精确搜索速度比 infini-gram 快 33 倍，并且显著优于 SoftMatcha（后者在处理大型语料库时会超时或触及内存限制）。
- 多语言： 该方法能有效扩展至中文（38.3B Token）和日语（169B Token），延迟均低于 400 ms。
实际应用： 作者展示了该工具在以下方面的用途：
- 污染检测： 识别训练语料库中精确匹配工具无法发现的“语义污染”和“模板泄露”（例如数学题中的数值替换）。
- 信息检索与改写检测： 在检索和改写检测任务中表现优于 BM25、infini-gram 和 SoftMatcha 等基准模型。

重要性与主张

作者将 SoftMatcha 2 定位为 LLM 研究社区的关键基础设施工具。其核心意义在于实现了对训练数据的详尽、语义感知式检查，而这在以前的规模下是无法实现的。通过揭示精确匹配工具所忽略的微妙形式的基准测试污染（语义相似性和模板泄露），该方法为评估数据卫生和模型行为提供了更严谨的方式。

论文也客观地指出了局限性：该方法在词级别运行，若要捕捉多词语义变化（例如“U.S.”与“United States”），会导致替换候选者过多，从而损害延迟。此外，系统所需的磁盘和内存资源与语料库规模成正比。然而，作者认为，能够在不到 0.3 秒内对万亿级数据集进行软搜索，代表了语料库分析、信息检索以及 AI 训练流水线中数据泄露检测领域的重大飞跃。