Research map / Large language models / Language, safety and interpretability
SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SoftMatcha, a soft pattern matcher that relaxes exact n-gram matching with word-embedding similarity and uses inverted indexes to search billion-word corpora in under a second.
Problem
Corpus search tools such as grep and KWIC rely on exact surface-level matching and miss orthographic and morphological variation and paraphrase, while dense vector search is too coarse for n-gram-level queries.
Approach
Softens each pattern word into the set of vocabulary words whose embeddings have cosine similarity above a threshold (computed only over the vocabulary), then uses an inverted index union and a shifting intersection to find exact corpus positions matching the soft pattern.
Key results
- On English Wikipedia (3.4B words) SoftMatcha returns 1,473 hits for 'homemade bombs' versus 107 for exact matching, with search completing in under 0.1 s without GPUs.
- Soft-BM25 with alpha=0.55 improves TREC-COVID P@20 from 39.5 (BM25) to 41.5 and NDCG@20 from 34.6 to 36.3.
- Search time grows sublinearly with corpus size on subsampled English Wikipedia, and lower thresholds (alpha<=0.2) become too slow for real-time use (1213 s at alpha=0.1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use semantic relaxation in Soft-BM25 (α=0.55) instead of exact BM25 matching | BM25 on TREC-COVID · TREC-COVID | P@20: 39.5 -> 41.5 | Helped |
| Use semantic relaxation in Soft-BM25 (α=0.55) instead of exact BM25 matching | BM25 on TREC-COVID · TREC-COVID | R@1000: 22.2 -> 23.5 | Helped |
| Use semantic relaxation in Soft-BM25 (α=0.55) instead of exact BM25 matching | BM25 on TREC-COVID · TREC-COVID | NDCG@20: 34.6 -> 36.3 | Helped |
| Use soft semantic pattern matching rather than exact matching | SoftMatcha search on English Wikipedia · English Wikipedia (3.4B words), “homemade bombs” query | # hits: 107 -> 1,473 | Helped |
| Use soft semantic pattern matching rather than exact matching | SoftMatcha search on Japanese Wikipedia · Japanese Wikipedia (1.1B words), “手製爆弾” query | # hits: 27 -> 42 | Helped |
| Lower the cosine-similarity threshold α (ablation) | SoftMatcha search on English Wikipedia · English Wikipedia, “homemade bomb” query | search time (seconds): 0.005 at α=1.0; 1213.503 at α=0.1 | Mixed |
| Lower the cosine-similarity threshold α (ablation) | SoftMatcha search on English Wikipedia · English Wikipedia, “homemade bomb” query | # hits: 107 at α=1.0; 504,955,515 at α=0.1 | Helped |
| Use α below 0.2 (ablation) | SoftMatcha real-time search · English Wikipedia, “homemade bomb” query | search time (seconds): 55.854 at α=0.2; 1213.503 at α=0.1 | Hurt |
Surprising findings
- Lowering the similarity threshold to 0.2 or below makes search impractically slow (over 55 s at 0.2 and 1213 s at 0.1) and returns many nonsensical matches.
- Dense vector search does not always retrieve texts containing the exact query pattern, so its recall on exact matches is below 100%.
Limitations
- Does not handle out-of-vocabulary words, which are ignored.
- Does not handle word omission, insertion, or reordering in the current version.
- Low thresholds produce slow searches and many nonsensical matches.
Experimental setup
Datasets: LLM-jp corpus v2.0 (English and Japanese Wikipedia) Perseus Project Latin corpus Augustinian Sermon Parallelism (ASP) Dataset TREC-COVID
Benchmarks: TREC-COVID
Metrics: running time (seconds) number of hits P@20 R@1000 NDCG@20
Baselines: exact matching dense vector search with multilingual-e5-large BM25
Builds on: inverted index faiss HNSW BM25
Closest papers by meaning
- Can Language Models Actually Retrieve In-Context? Drowning in Documents at Million Token Scale (NeurIPS 2026 · similarity 0.86)
- What's In My Big Data? (ICLR 2024 · similarity 0.85)
- MMTEB: Massive Multilingual Text Embedding Benchmark (ICLR 2025 · similarity 0.85)
- GlotCC: An Open Broad-Coverage CommonCrawl Corpus and Pipeline for Minority Languages (NeurIPS 2024 · similarity 0.85)
- Contextual Tokenization for Graph Inverted Indices (NeurIPS 2025 · similarity 0.84)
- SWEb: A Large Web Dataset for the Scandinavian Languages (ICLR 2025 · similarity 0.84)
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.