mlsanityData to 7 Oct 2026

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

arXiv 2602.10908 ↗First posted 11 Feb 2026cs.CL cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 38 of its 88 references that are in the map. First posted on arXiv 11 Feb 2026.

Builds on

38 of 88 references.

References · 38

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  4. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  5. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  6. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  7. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,049
  8. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  9. 2020Measuring Massive Multitask Language Understandingcited by 7,768
  10. 2020Scaling Laws for Neural Language Modelscited by 6,411
  11. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  12. 2018Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challengecited by 4,710
26 more
  1. 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,346
  2. 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,779
  3. 2014Sequence to Sequence Learning with Neural Networkscited by 2,974
  4. 2023GPQA: A Graduate-Level Google-Proof Q&A Benchmarkcited by 2,748
  5. 2021SimCSE: Simple Contrastive Learning of Sentence Embeddingscited by 2,168
  6. 2024MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmarkcited by 1,758
  7. 2024The FineWeb Datasets: Decanting the Web for the Finest Text Data at Scalecited by 1,104
  8. 2025OpenAI GPT-5 System Cardcited by 910
  9. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  10. 2020Fact or Fiction: Verifying Scientific Claimscited by 546
  11. 2021Documenting Large Webtext Corpora: A Case Study on the Colossal Clean Crawled Corpuscited by 481
  12. 2024Dolma: an Open Corpus of Three Trillion Tokens for Language Model Pretraining Researchcited by 475
  13. 2021A Survey on Automated Fact-Checkingcited by 376
  14. 2024The Faiss librarycited by 370
  15. 2018Learning Word Vectors for 157 Languagescited by 279
  16. 2024Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokenscited by 148
  17. 2024Benchmarking Benchmark Leakage in Large Language Modelscited by 102
  18. 2022Preventing Verbatim Memorization in Language Models Gives a False Sense of Privacycited by 97
  19. 2020ORCAS: 18 Million Clicked Query-Document Pairs for Analyzing Searchcited by 34
  20. 2022Norm of Word Embedding Encodes Information Gaincited by 21
  21. 2021Searching for Scientific Evidence in a Pandemic: An Overview of TREC-COVIDcited by 19
  22. 2025Why and How LLMs Hallucinate: Connecting the Dots with Subsequence Associationscited by 14
  23. 2025Infini-gram mini: Exact n-gram Search at the Internet Scale with FM-Indexcited by 13
  24. 2020RRF102: Meeting the TREC-COVID Challenge with a 100+ Runs Ensemblecited by 6
  25. 2024Zipfian Whiteningcited by 3
  26. 2025SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searchescited by 3

Built on by

Not cited yet.