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

Masaaki Yoneda, Yusuke Matsushita, Go Kamoda, Kohei Suenaga, Takuya Akiba, Masaki Waga, Sho Yokoi

Abstract

We present an ultra-fast and flexible search algorithm that enables search over trillion-scale natural language corpora in under 0.3 seconds while handling semantic variations (substitution, insertion, and deletion). Our approach employs string matching based on suffix arrays that scales well with corpus size. To mitigate the combinatorial explosion induced by the semantic relaxation of queries, our method is built on two key algorithmic ideas: fast exact lookup enabled by a disk-aware design, and dynamic corpus-aware pruning. We theoretically show that the proposed method suppresses exponential growth in the search space with respect to query length by leveraging statistical properties of natural language. In experiments on FineWeb-Edu (1.4T tokens), we show that our method achieves significantly 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, we demonstrate that our method identifies benchmark contamination in training corpora, unidentified by existing approaches.

Introduction

As Large Language Models (LLMs) scale, their training datasets often reach trillions of tokens. Researchers require efficient tools to search these massive corpora to investigate model behavior, identify biases, or detect benchmark contamination—where test data inadvertently leaks into training sets.

Existing search tools face a significant trade-off. Exact matchers, such as infini-gram, are highly efficient but brittle; they fail to find semantically similar phrases with minor variations (e.g., "Alice has 8 pens" vs. "Alice has 5 pens"). Conversely, soft matchers that allow for synonyms or insertions typically suffer from "combinatorial explosion." SoftMatcha 2 addresses this by enabling sub-second soft search at the trillion-token scale.

Algorithmic Innovations

The efficiency of SoftMatcha 2 stems from two primary innovations:

1. Fast Disk-Aware Suffix Array

Standard suffix arrays often require numerous random disk accesses, leading to high latency. SoftMatcha 2 implements a two-staged indexing scheme. A sparse "summary" index is maintained in RAM to identify the relevant neighborhood on the disk. This design reduces the search to a single random disk access per exact lookup, making exact search up to 33x faster than previous state-of-the-art methods.

2. Dynamic Corpus-Aware Pruning

To handle soft matching without exponential slowdown, the algorithm employs iterative pruning. Instead of generating all possible query variations upfront, it validates prefixes against the corpus at each step. If a specific word combination does not exist in the dataset, the algorithm immediately prunes that branch of the search tree.

Iterative pruning process: the algorithm checks the existence of patterns in the corpus at each step to avoid searching non-existent variations.

This approach leverages the inherent sparsity of natural language. Because most word combinations are never used in real-world text, the search space remains manageable even with high similarity thresholds.

Performance and Scalability

Evaluations on the 1.4 trillion-token FineWeb-Edu dataset demonstrate that SoftMatcha 2 achieves a 95th-percentile latency of approximately 278 ms for soft searches.

Search time vs. corpus size for soft search across English (EN), Japanese (JA), and Chinese (ZH) datasets, comparing SoftMatcha 2 (Ours) against baselines.

The system scales efficiently across different languages and corpus sizes. Notably, the index size for the full FineWeb-Edu dataset is 21.6 TB, which is only 2.2x larger than an index supporting only exact matches.

Practical Application: Benchmark Contamination

SoftMatcha 2's ability to find "near-miss" matches makes it uniquely suited for auditing training data. In practical tests, it identified an additional 1.4% of "dirty" samples in training corpora that were missed by exact matchers. These cases often involved minor numerical substitutions or semantic variations that still constitute data leakage.

Conclusion and Future Work

SoftMatcha 2 provides a scalable solution for auditing the massive datasets powering modern AI. While currently limited to word-level variations, future work aims to incorporate compositional representations to handle multi-word semantic shifts and expand support for general wildcard queries. The system requires high-speed NVMe storage and significant RAM, but its performance gains offer a new standard for large-scale corpus analysis.

Summary updated

Abstract

We present an ultra-fast and flexible search algorithm that enables search over trillion-scale natural language corpora in under 0.3 seconds while handling semantic variations (substitution, insertion, and deletion). Our approach employs string matching based on suffix arrays that scales well with corpus size. To mitigate the combinatorial explosion induced by the semantic relaxation of queries, our method is built on two key algorithmic ideas: fast exact lookup enabled by a disk-aware design, and dynamic corpus-aware pruning. We theoretically show that the proposed method suppresses exponential growth in the search space with respect to query length by leveraging statistical properties of natural language. In experiments on FineWeb-Edu (Lozhkov et al., 2024) (1.4T tokens), we show that our method achieves significantly 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, we demonstrate that our method identifies benchmark contamination in training corpora, unidentified by existing approaches. We also provide an online demo of fast, soft search across corpora in seven languages.
BibTeX
@inproceedings{yoneda2026softmatcha,
  author = {Masaaki Yoneda and Yusuke Matsushita and Go Kamoda and Kohei Suenaga and Takuya Akiba and Masaki Waga and Sho Yokoi},
  title = {{SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=y1czGbUum5},
}
Figure