SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917268108083200 |
|---|---|
| author | Yoneda, Masataka Matsushita, Yusuke Kamoda, Go Suenaga, Kohei Akiba, Takuya Waga, Masaki Yokoi, Sho |
| author_facet | Yoneda, Masataka Matsushita, Yusuke Kamoda, Go Suenaga, Kohei Akiba, Takuya Waga, Masaki Yokoi, Sho |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10908 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora Yoneda, Masataka Matsushita, Yusuke Kamoda, Go Suenaga, Kohei Akiba, Takuya Waga, Masaki Yokoi, Sho Computation and Language Machine Learning 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. |
| title | SoftMatcha 2: A Fast and Soft Pattern Matcher for Trillion-Scale Corpora |
| topic | Computation and Language Machine Learning |
| url | https://arxiv.org/abs/2602.10908 |