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

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

As Large Language Models (LLMs) scale, their training datasets routinely exceed trillions of tokens. Auditing these massive "haystacks" is critical for investigating model hallucinations, performing information retrieval, and detecting benchmark contamination (where test questions inadvertently leak into training data).

However, researchers searching these corpora have traditionally been forced to compromise. Exact match tools, like infini-gram, are blazing fast but brittle—they will miss "gold medallist" if queried for "gold medalist." Conversely, vector search (Approximate Nearest Neighbors) captures semantics but often ignores word order and specific lexical structures, making it poor for finding precise phrasing variations.

SoftMatcha 2 bridges this gap. It is an ultra-fast search engine designed to query trillion-scale text corpora in under 0.3 seconds, offering the semantic flexibility of vector search with the speed and order-preservation of exact string matching.

The Challenge of Semantic Relaxation

The primary hurdle in "soft" matching—finding semantically similar phrases with substitutions, insertions, or deletions—is the combinatorial explosion. If you allow synonyms for every word in a 10-word query, the number of possible combinations grows exponentially. SoftMatcha 2 mitigates this through a combination of classic data structures and modern embeddings.

Key Algorithmic Innovations

To achieve sub-second latency on trillion-token datasets, SoftMatcha 2 relies on several core innovations:

  • Dynamic Corpus-Aware Pruning: The algorithm's most crucial insight is that the corpus itself is the best pruner. By verifying candidate phrases against the corpus during the iterative expansion of the query, the system avoids exploring millions of semantic variations that simply do not exist in natural language.
  • Disk-Aware Staged Suffix Array: Standard suffix arrays require $O(\log |Corpus|)$ random disk accesses, which bottlenecks multi-terabyte indices. SoftMatcha 2 uses a two-stage design: a sparse index kept in RAM identifies a narrow disk range, reducing the search to a single random disk access per exact lookup.
  • Smooth Minimum Similarity: Instead of a "hard" minimum score dictated by the worst-matching word, the system uses a $\beta$-parameterized "softmin" function to evaluate overall match quality, preventing a single outlier word from tanking a valid match.
  • Norm-Based Penalties: Using "Zipfian whitening," the algorithm penalizes the alteration (insertion or deletion) of high-information words more heavily than common stop words like "the" or "of."

Empirical Results & Contamination Detection

The researchers evaluated SoftMatcha 2 across seven languages using massive datasets, including FineWeb-Edu (1.4 trillion English tokens) and various C4 subsets. The results demonstrate remarkable performance:

  • Ultra-Low Latency: On the 1.4T token FineWeb-Edu corpus, SoftMatcha 2 achieved a 95th-percentile latency of just 278.17 ms for soft search and 0.34 ms for exact search.
  • Massive Speedups: It operates roughly 33x faster than infini-gram for exact lookups and hundreds of times faster than its predecessor, SoftMatcha v1, at large scales.
  • Uncovering "Template Leakage": Exact matching misses substantial data leakage. SoftMatcha 2 successfully identifies "template leakage"—such as math problems identical to training samples except for the specific numbers used (e.g., "Alice has 5 apples" vs. "Alice has 8 apples"). In a study of popular benchmarks (MMLU, GSM8K, MATH, etc.), it found 36 additional contaminated samples missed by exact-match tools, with an 81% manual verification precision.
  • Sublinear Scaling: Theoretical proofs show search time scales sublinearly ($O(|C|^{1/\delta})$) relative to corpus size, ensuring the tool remains viable as datasets approach quadrillions of tokens.

Limitations and Future Directions

Despite its speed and efficiency (the 21.6 TB index for 1.4T tokens is only about 2.2x larger than an exact-match-only index), SoftMatcha 2 is resource-intensive. It requires significant disk space and substantial RAM for the sparse index, which may limit its deployment to well-resourced research environments.

Furthermore, the system currently operates on a strict word-by-word basis, meaning it struggles with multi-word semantic variations (e.g., matching "U.S." to "United States"). Future iterations aim to incorporate compositional representations—such as sums of word vectors—to handle multi-word variations and to support more complex queries, including wildcards.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yoneda2026softmatcha,
  author = {Masataka 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