SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches
Not on the map. Why?
Abstract (arXiv)
Researchers and practitioners in natural language processing and computational linguistics frequently observe and analyze the real language usage in large-scale corpora. For that purpose, they often employ off-the-shelf pattern-matching tools, such as grep, and keyword-in-context concordancers, which is widely used in corpus linguistics for gathering examples. Nonetheless, these existing techniques rely on surface-level string matching, and thus they suffer from the major limitation of not being able to handle orthographic variations and paraphrasing -- notable and common phenomena in any natural language. In addition, existing continuous approaches such as dense vector search tend to be overly coarse, often retrieving texts that are unrelated but share similar topics. Given these challenges, we propose a novel algorithm that achieves soft (or semantic) yet efficient pattern matching by relaxing a surface-level matching with word embeddings. Our algorithm is highly scalable with respect to the size of the corpus text utilizing inverted indexes. We have prepared an efficient implementation, and we provide an accessible web tool. Our experiments demonstrate that the proposed method (i) can execute searches on billion-scale corpora in less than a second, which is comparable in speed to surface-level string matching and dense vector search; (ii) can extract harmful instances that semantically match queries from a large set of English and Japanese Wikipedia articles; and (iii) can be effectively applied to corpus-linguistic analyses of Latin, a language with highly diverse inflections.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 42 of its 103 references that are in the map. First posted on arXiv 5 Mar 2025.
Builds on
42 of 103 references.
References · 42
- 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
- 2020Language Models are Few-Shot Learnerscited by 32,419
- 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,599
- 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
- 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,297
- 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,375
- 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,824
- 2020The Pile: An 800GB Dataset of Diverse Text for Language Modelingcited by 2,411
- 2023Retrieval-Augmented Generation for Large Language Models: A Surveycited by 2,212
- 2020REALM: Retrieval-Augmented Language Model Pre-Trainingcited by 2,141
- 2023Pythia: A Suite for Analyzing Large Language Models Across Training and Scalingcited by 1,786
- 2017Understanding Black-box Predictions via Influence Functionscited by 1,741
30 more
- 2016Enriching Word Vectors with Subword Informationcited by 1,583
- 2020RealToxicityPrompts: Evaluating Neural Toxic Degeneration in Language Modelscited by 1,255
- 2022Text Embeddings by Weakly-Supervised Contrastive Pre-trainingcited by 1,253
- 2021Unsupervised Dense Information Retrieval with Contrastive Learningcited by 1,216
- 2015Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Bookscited by 1,043
- 2022Atlas: Few-shot Learning with Retrieval Augmented Language Modelscited by 952
- 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 861
- 2019Generalization through Memorization: Nearest Neighbor Language Modelscited by 800
- 2022MTEB: Massive Text Embedding Benchmarkcited by 640
- 2020Estimating Training Data Influence by Tracing Gradient Descentcited by 580
- 2021A Survey on Automated Fact-Checkingcited by 378
- 2024Multilingual E5 Text Embeddings: A Technical Reportcited by 372
- 2021Self-Diagnosis and Self-Debiasing: A Proposal for Reducing Corpus-Based Bias in NLPcited by 337
- 2023Multi-step Jailbreaking Privacy Attacks on ChatGPTcited by 333
- 2023Analyzing Leakage of Personally Identifiable Information in Language Modelscited by 285
- 2018Learning Word Vectors for 157 Languagescited by 280
- 2024A Survey on Data Selection for Language Modelscited by 236
- 2022Are Large Pre-Trained Language Models Leaking Your Personal Information?cited by 200
- 2024Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokenscited by 153
- 2023Emergent and Predictable Memorization in Large Language Modelscited by 148
- 2022Preventing Verbatim Memorization in Language Models Gives a False Sense of Privacycited by 100
- 2024Reducing hallucination in structured outputs via Retrieval-Augmented Generationcited by 93
- 2023Factcheck-Bench: Fine-Grained Evaluation Benchmark for Automatic Fact-checkerscited by 87
- 2022Language Generation Models Can Cause Harm: So What Can We Do About It? An Actionable Surveycited by 80
- 2019Paraphrasing with Large Language Modelscited by 36
- 2024Recent Trends in Personalized Dialogue Generation: A Review of Datasets, Methodologies, and Evaluationscited by 20
- 2024Unlearning Traces the Influential Training Data of Language Modelscited by 18
- 2023Introducing Rhetorical Parallelism Detection: A New Task with Datasets, Metrics, and Baselinescited by 7
- 2020RRF102: Meeting the TREC-COVID Challenge with a 100+ Runs Ensemblecited by 6
- 2018Taylor's law for Human Linguistic Sequencescited by 5
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.