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

AI summary

Overview

Research area: Natural language processing — large-scale corpus search, full-text pattern matching, and information retrieval for language model training data.

Technical level: Advanced. The paper assumes familiarity with suffix arrays, word embeddings, Zipfian/Heaps' law statistics, and index engineering for disk-based systems.

One-sentence scope: The paper presents SoftMatcha 2, a suffix-array-based search algorithm that supports semantic variation (substitution, insertion, deletion) while searching trillion-token corpora in under 0.3 seconds, and evaluates it against infini-gram, infini-gram mini, and SoftMatcha.

What This Paper Is About

Language model pretraining corpora have grown to trillions of tokens (the paper contrasts the 1M-token Brown Corpus, the 4B-token Gigaword, and the 1.4T-token FineWeb-Edu), and modern corpus search must simultaneously scale to that size, tolerate paraphrase and orthographic variation, and preserve word order — since queries are natural language and order carries meaning. The authors argue no existing tool satisfies all three requirements, and they build a soft (lexical-semantic) string matcher that does, by combining word vectors with suffix arrays rather than the inverted indexes used by the prior soft-search tool SoftMatcha.

Key Contributions

1. A soft full-text search algorithm for trillion-token corpora that handles semantic similarity and token-count differences between queries and results, built from two ideas: dynamic corpus-aware pruning to control the combinatorial blowup of candidate patterns, and disk-aware, staged suffix arrays.

2. A theoretical analysis showing that the expected number of exact lookups performed by the algorithm is sublinear in corpus size — approximately O(|C|^(1/δ)) under Zipf's law with exponent δ > 1 (the paper notes δ is typically about 1.5 for many languages) — and a more detailed upper bound of Aa(1−r^m)/(1−r) when r ≠ 1.

3. An empirical evaluation showing substantially lower latency than existing methods: 95th-percentile latencies of 278.17 ms for soft search and 0.34 ms for exact search on FineWeb-Edu (1.4T tokens), with soft-search p95 under 400 ms for Chinese (38.3B tokens) and Japanese (169B tokens) corpora.

4. Three practical applications — information retrieval, paraphrase detection, and detection of benchmark contamination in training corpora — plus a released online demo running on a 100B-token-scale English corpus that searches corpora in seven languages.

Main Findings

• Soft search latency on English: On FineWeb-Edu (1.4T tokens), the median soft-search latency was 89.59 ms and the p95 latency was 278.17 ms. On the real-world ORCAS queries, the p95 latency was 433.50 ms.

• Exact-search speedup: The p95 latency for exact lookup on FineWeb-Edu (1.4T tokens) was 0.34 ms, versus 11.05 ms for infini-gram — a 33x speedup. It also speeds up the underlying exact-match primitive by roughly 33x relative to infini-gram per the algorithm section.

• Comparison with infini-gram mini: Full-corpus (1.4T token) comparison was not possible because infini-gram mini's index construction timed out. At 273B tokens, the paper's method was 475 times faster (0.32 ms vs. 151.84 ms). At 273B tokens, infini-gram mini's index construction took 22.2 hours.

• Comparison with SoftMatcha: Latency was nearly the same up to 500M tokens, but beyond 1B tokens SoftMatcha's latency increased almost linearly, and SoftMatcha was unable to handle corpora exceeding 50B tokens due to memory limits and timeouts.

• Cross-lingual results: p95 soft-search latencies were under 400 ms for Japanese (C4, 169B tokens) and Chinese (C4, 38.3B tokens). The paper reports the seven experimental corpora — English (FineWeb-Edu, 1,375,278,465,557 tokens, Moses tokenizer, GloVe embeddings), Japanese (C4, 168,756,125,544 tokens, MeCab tokenizer, fastText), Chinese (C4, 38,313,934,910 tokens, ICU tokenizer, fastText), German (C4, 1,099,885,019), Italian (C4, 1,070,947,829), French (C4, 978,329,060), and Russian (C4, 1,006,500,018); German, Italian, and French used subsampled datasets.

• Index size and construction cost: For FineWeb-Edu (1.4T tokens, 6.7TB of raw text), the SoftMatcha 2 index is 21.6TB including raw text — 2.2 times greater than infini-gram's index size (9.9TB, excluding raw text). Run-length compression reduced the index from 56.0TB to 21.6TB. Index construction took 53.8 hours, compared with 61.2 hours for infini-gram, and timeouts for infini-gram mini and SoftMatcha.

• Quality of soft matches: In a qualitative example, searching for "olympics gold medalist" returned results such as "olympics silver medalist" and "olympic gold medallist," while "importance of the machine learning" returned token-count-varying matches such as "importance of machine learning." Under LLM-as-a-judge, the method outperformed SoftMatcha in 61.3% of cases.

• Pruning effectiveness (ablation): Across three pruning techniques (iterative pruning, k-gram pruning, last-bits pruning), the geometric mean number of exact string-matching lookups grew 2.30 times per token with all three enabled, versus 5.17 times with none.

• Contamination detection: Across 7 benchmarks and 2,564 samples, exact matching flagged 338 samples (13.2%) as dirty; soft search found an additional 36 samples (1.4%). Manual inspection of those 36 gave an 81% precision rate (29/36): 18 were classified as semantic contamination and 11 as template leakage. Examples include a MMLU question where "in" was deleted, and a MATH question where a number was substituted ("The sum of two numbers is 25 and their difference is 11" matching a corpus text reading "The sum of two numbers is 139 …"). The paper notes infini-gram mini previously identified contaminations in 24 popular benchmarks.

• Experimental setup: All experiments ran on an AWS i4i.32xlarge instance (128 vCPU, 1024GB RAM, 30TB NVMe SSD). Queries were 400 English and 100 per-other-language queries of token length 10 or less, generated semi-automatically with Gemini 3.0 Pro, plus real-world queries from ORCAS. The top K = 20 patterns were retrieved, with a similarity floor of 0.45; 38 of the 400 English queries (≈10%) returned fewer than K results. β was set to 10⁴ and γ to mγ′ with γ′ ≈ 21.70 for FineWeb-Edu. Last-bits pruning is applied when a pattern has 50 or fewer occurrences.

Methodology in Plain English

The system works in two stages: an offline index built once from the corpus, and a runtime search that uses that index.

For scaling, the authors use a suffix array — a data structure that allows an exact lookup of a short string in time logarithmic in corpus size, which is why they can handle a trillion tokens while an inverted index (used by SoftMatcha) scales only linearly.

For semantic flexibility, query words and candidate words are compared as word vectors. Cosine similarity between vectors lets the system match words that are close in meaning, not just identical.

The central difficulty is combinatorial: if a query has many semantically similar words per position, the number of candidate patterns grows exponentially with query length, and suffix arrays can only look up one pattern at a time. The authors attack this in three ways:

• Iterative pruning. Instead of enumerating all possible similar patterns up front, the algorithm processes the query token by token. At each step it extends the previous step's surviving patterns and then keeps only those that actually occur in the corpus (checked by the fast suffix-array lookup). Because n-gram frequencies follow a power-law distribution, most candidate extensions die out immediately.

• k-gram pruning. For 2-grams and 3-grams made only of high-frequency words, occurrence information is precomputed and kept in RAM, avoiding disk accesses at runtime.

• Last-bits pruning. When a surviving pattern has only a few occurrences in the corpus, the algorithm enumerates those occurrences directly rather than extending the pattern further.

For speed, they design a disk-aware, staged suffix array. A trillion-token index exceeds 5TB and cannot fit in RAM, and disk latency is roughly 10³ times RAM latency. Their two-stage scheme builds a sorted array of all contiguous L-token sequences (where L is the maximum query length), keeps a sparse sample of it in RAM, uses the sample to narrow down the approximate region, and then touches disk once to find the exact position. This yields one disk access per exact-match query, versus O(log |C|) for a standard suffix array.

For search quality, they define a new similarity measure: a smooth minimum of per-position cosine similarities (parameterized by β), which, unlike SoftMatcha's plain minimum, does not ignore all words except the worst-matching one. Insertions and deletions are handled by scaling similarity down using the norm of the inserted or deleted word's vector after Zipfian whitening, so that low-information words like "the" and "of" incur small penalties. They also add adaptive similarity thresholding: the system relaxes the threshold α until at least K matches are found or the threshold becomes too low.

Why This Matters

Corpus search is the diagnostic tool researchers use to trace unintended model behavior and to check whether benchmark questions have leaked into pretraining data. If search is slow, limited to exact matches, or unable to scale to the full corpus, those audits return incomplete answers.

Real-world applications:

• Benchmark contamination auditing: The paper shows that soft search finds 36 additional dirty samples (1.4% of 2,564) that exact matching misses, with 81% manually verified precision — including semantic contamination and numeric template leakage.
• Information retrieval: The method is demonstrated as a practical retrieval use case, with reported p95 latency of 433.50 ms on real-world ORCAS queries.
• Paraphrase detection: Because the similarity function handles substitution, insertion, and deletion, the system surfaces paraphrases and orthographic variants of a query.
• Corpus linguistics and model-behavior investigation: Searching trillion-token corpora quickly supports the investigation of why a model behaves in a particular way.

Industry relevance: Pretraining pipelines operate at trillion-token scale, and the paper's index (21.6TB for 1.4T tokens) and construction time (53.8 hours, versus 61.2 hours for infini-gram and timeouts for infini-gram mini and SoftMatcha) are concrete operational numbers. The reported 33x speedup for exact lookup suggests the disk-aware suffix array is valuable on its own, independent of the soft-search component.

Future Directions

• Index size and construction cost. The index is 21.6TB including raw text, and index construction takes 53.8 hours with infini-gram mini and SoftMatcha unable to complete; whether these costs can be reduced while preserving one-disk-access lookups is an open engineering question.

• Extending beyond the seven tested languages. The multilingual evidence covers English, Japanese, Chinese, German, Italian, French, and Russian, with German, Italian, and French on subsampled data; behavior on low-resource or morphologically different languages is not reported.

• Tightening the theory's gap with practice. The authors note that as i grows, the actual size of R_i becomes much larger than the uniform-sampling estimate, which they attribute to linguistic constraints such as grammar and collocations being stronger for corpus n-grams than for the similar-pattern set — a discrepancy worth modeling.

• Broadening contamination detection. The study analyzes 7 benchmarks and 2,564 samples with a manual audit of 36 soft-only hits; scaling this audit methodology to more benchmarks and to other leakage forms remains future work.

Target Audience

This paper is most useful to researchers and engineers building or auditing large-scale language model training data: NLP researchers working on corpus search, contamination detection, and information retrieval; systems researchers interested in disk-resident suffix arrays and index compression; and industrial practitioners who need to search trillion-token corpora quickly. Readers without a background in string data structures or embedding-based similarity will need to consult the appendices and cited prior work, since the main text assumes that background.

Authors’ abstract

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.