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

We present SoftMatcha 2, an ultra-fast and flexible search algorithm that enables search over trillion-scale natural language corpora in under 0.3 seconds while allowing semantic variations in the form of substitution, insertion, and deletion. Our approach employs string matching based on suffix arrays that scales well with corpus size, and represents words as vectors, which underpin its semantic flexibility. To mitigate the combinatorial explosion induced by the semantic relaxation of queries, our method is built on two key algorithmic ideas: dynamic corpus-aware pruning and fast exact lookup enabled by a disk-aware design. We theoretically analyze the efficiency of the proposed method, indicating that it can mitigate exponential growth in the search space. Empirically, on FineWeb-Edu (Lozhkov et al., 2024) (1.4T tokens), it attains substantially lower search latency than existing methods: infini-gram (Liu et al., 2024), infini-gram mini (Xu et al., 2025), and SoftMatcha (Deguchi et al., 2025). As a practical application, our method uncovers benchmark contamination in training corpora that existing approaches miss, and it also benefits information retrieval and paraphrase detection. We also provide an online demo of fast, soft search across corpora in seven languages.

How can we quickly find the example sentences and hit count containing “machine learning”, from a text dataset of a trillion words? — The demand for such high-speed string searching is increasing due to the development of large language models (LLMs). In addition, since natural languages have some variations in spelling and meaning, it is also important to detect them. For example, when the search query is “olympics gold medalist”, the system should ideally detect related patterns such as “olympics silver medalist” and “olympic gold medalist”. In this paper, we developed a tool that searches for the top 20 patterns similar to the search query, within only 0.3 seconds from a dataset of 1.4 trillion tokens. In addition, to make the research more accessible, we also provide an interactive online demo capable of searching massive datasets across various languages. Moreover, our tool significantly accelerates not only text data analysis but also some important tasks in LLM development. For example, we demonstrated that our method works well to verify whether benchmark problems used for evaluating LLM performance are included in the training data.