Research map / Learning theory and algorithms / Combinatorial and search optimization
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
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use disk-aware staged suffix array instead of standard suffix array (infini-gram) | exact lookup · FineWeb-Edu 1.4T | p95 latency (ms): 11.05 -> 0.34 | Improved |
| use disk-aware staged suffix array instead of FM-index (infini-gram mini) | exact lookup · FineWeb-Edu 273B | p95 latency (ms): 151.84 -> 0.32 | Improved |
| add all three pruning techniques (iterative, k-gram, last-bits) (ablation) | SoftMatcha 2 soft search · FineWeb-Edu | geometric mean lookup growth per token: 5.17 -> 2.30 | Improved |
| add run-length compression to the index (ablation) | SoftMatcha 2 index · FineWeb-Edu 1.4T | index size (TB): 56.0 -> 21.6 | Improved |
| replace inverted index with suffix array and pruning | SoftMatcha · Soft search latency vs corpus size | latency: SoftMatcha latency increases almost linearly beyond 1B tokens; ours shows almost no increase | Improved |
| use SoftMatcha 2 instead of SoftMatcha | soft search · LLM-as-a-judge quality | win rate (%): 61.3 | Improved |
| use soft search in addition to exact match | contamination detection · 7 benchmarks | samples flagged dirty: 338 of 2,564 (13.2%) -> additional 36 (1.4%), 29/36 true (81%) | Improved |
| use SoftMatcha 2 instead of SoftMatcha | information retrieval · TREC-COVID | P@20: 35.4 -> 36.0 | Improved |
| use SoftMatcha 2 instead of BM25 | information retrieval · SciFact | P@1: 42.7 -> 42.7 | No clear effect |
| use SoftMatcha 2 instead of BM25 | paraphrase detection · Paraphrase detection | score: 82.8 -> 84.3 | Improved |
| use SoftMatcha 2 instead of infini-gram exact match | paraphrase detection · Paraphrase detection | score: 65.5 -> 84.3 | Improved |
Closest papers by meaning
- SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches (ICLR 2025 · similarity 0.95)
- Can Language Models Actually Retrieve In-Context? Drowning in Documents at Million Token Scale (NeurIPS 2026 · similarity 0.84)
- OBLIQ-Bench: Exposing Overlooked Bottlenecks in Modern Retrievers with Latent and Implicit Queries (NeurIPS 2026 · similarity 0.84)
- Weak-to-Strong Search: Align Large Language Models via Searching over Small Language Models (NeurIPS 2024 · similarity 0.83)
- Beyond Semantic Similarity: Rethinking Retrieval for Agentic Search via Direct Corpus Interaction (NeurIPS 2026 · similarity 0.83)
- Earley-Driven Dynamic Pruning for Efficient Structured Decoding (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
