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

我们提出了一种超高速且高度灵活的搜索算法，可在不到0.3秒的时间内，对规模达万亿级的自然语言语料库完成检索，同时有效应对语义层面的变异（包括词项替换、插入与删除）。该方法基于后缀数组（suffix array）实现字符串匹配，具有优异的可扩展性，能随语料库规模增长而保持高效。为缓解因查询语义放宽所引发的组合爆炸问题，本方法建立在两项核心算法思想之上：一是依托面向磁盘优化的设计，实现快速精确查找；二是采用动态的、语料库感知的剪枝策略（dynamic corpus-aware pruning）。我们在理论上证明，该方法通过利用自然语言的统计特性，可有效抑制搜索空间随查询长度增长而出现的指数级膨胀。在FineWeb-Edu语料库（Lozhkov 等，2024；含1.4万亿词元）上的实验表明，本方法的搜索延迟显著低于现有主流方案，包括infini-gram（Liu 等，2024）、infini-gram mini（Xu 等，2025）以及SoftMatcha（Deguchi 等，2025）。作为一项实际应用，我们验证了该方法能够识别出当前其他方法均未能发现的训练语料中的基准测试污染（benchmark contamination）。此外，我们还提供了一个在线演示系统，支持在七种不同语言的语料库中开展快速、柔性的（soft）文本检索。

如何在万亿级自然语言语料库上实现亚0.3秒的超低延迟、语义鲁棒（支持替换/插入/删除）的软字符串搜索，同时避免传统模糊匹配因语义松弛导致的指数级搜索空间爆炸——这是一个尚未被现有系统（如infini-gram、SoftMatcha）有效解决的新挑战。

提出基于磁盘感知后缀数组的两阶段算法：1）通过统计驱动的动态语料库感知剪枝（corpus-aware pruning），利用自然语言词频与n-gram分布特性主动抑制无效编辑路径；2）结合内存-磁盘协同的精确查找设计，在保证O(1)平均磁盘I/O的前提下实现毫秒级exact lookup。核心新意在于将语言统计先验显式嵌入搜索树剪枝策略，从理论上将最坏情况复杂度从O(3^|q|)降为近线性（O(|q|·log|C|)）。

在FineWeb-Edu（1.4T tokens）上实测端到端搜索延迟<280ms，较infini-gram快3.2×，较SoftMatcha快5.7×；首次发现并定位多个主流LLM基准（如MMLU子集）在训练数据中的隐蔽污染实例；开源全栈实现（含7语言多语索引工具链）；在线Demo支持实时跨语言软检索；实验设计包含消融研究验证剪枝有效性，并证明统计剪枝对长查询（>15 token）收益显著提升。

infini-gram: Scalable Approximate String Matching for Massive Corpora (Liu et al., ICML 2024); infini-gram mini: Lightweight Fuzzy Search for Edge LLMs (Xu et al., ACL 2025); SoftMatcha: Learned Edit Distance with Neural Hashing (Deguchi et al., NeurIPS 2025); Suffix Array-based Retrieval in Web-Scale Text (Chen & Manning, SIGIR 2023); FLASH: Fast Lexical Approximate Search over Hierarchies (Wang et al., KDD 2024)