SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches
Authors: Hiroyuki Deguchi
Go Kamoda
Yusuke Matsushita
Chihiro Taguchi
Kohei Suenaga
Masaki Waga
Sho Yokoi
Venue: ICLR 2025 Poster (2025)
Keywords: natural language processing
full-text search
word embeddings
inverted index
pattern match
Primary area: applications to computer vision, audio, language, and other modalities
TL;DR: Achieving soft yet efficient full-text search, we introduce a novel method that extends inverted indexes with word embeddings to enable sub-second searches of billion-scale corpora without GPUs.

Abstract: 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.

Published as a conference paper at ICLR 2025
SOFTMATCHA: A SOFT AND FAST PATTERN MATCHER FOR BILLION-SCALE CORPUS SEARCHES
Hiroyuki Deguchi'; Go Go Kamoda', Yusuke Matsushita', Chihiro Taguchi'
Kohei Suenaga', Masaki Waga', Sho Yokoi
NAIST, Tohoku University, *Kyoto University, *University of Notre Dame,
NINIAL,, 'RIKEN
deguchi Segguci..hrryuuke wwwroykki.i..... wbb.yikii.00ii.. db00is maittiiiiiiiii.................. jp. go, Bamoda@de.totokku.cc
ymat&fos craatfoo.kkis.keer www..k..o.ooo..ece...... jp, ctaguchi eeraguchi@nd... @nd. edu
sikenaraakkiss.yyorooo.coo ip, www.wwaaaaaaa......mm...mmm fos kuis kyoto-u. ac.
yokoi@ninjal.ac..
ABSTRACT
Researchers and practitioners in natural language processing and computational linguistics frequently observe and analyze the real language usage large-scale corpora. For that purpose, they often employ off-the-shelf pattern-matching tools, such as grep, and seyword-in-conter concordancers, which is widely used corpus linguistics for gathering examples. Nonetheless, these existing techniques rely on surface-level string matching, and thus they suffer from the major limita- tion of not being able to handle orthographic variations and paraphrasing and common phenomena in any natural language. In addition, existing continu- ous approaches such dense vector search tend be overly coarse, often re- trieving texts that are unrelated but share similar topics. Given these challenges, we propose a novel algorithm that achieves saft (or semantic) yet efficient pat- tern matching by relaxing 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 surface-level string matching and dense vector search; (ii) extract harmful instances that semantically match queries from large of English and Japanese Wikipedia articles; and (ii)) can be effectively applied to corpus-linguistic analyses of Latin, language with highly diverse inflections.
e -notable
INTRODUCTION
Recent advances in natural language processing (NLP) and corpus linguistics are largely driven by the availability of massive text corpora (Gao et al., 2020: Biderman et al.] 2023b Raffel et al.) 2019 Van Der Zwaan et al., 2017 Mcgillivray et al., 2020). The field of NLP, driven by the grand goal of building intelligent chatbots and machine translation systems, has achieved remark- able breakthroughs over the past decade, largely thanks to self-supervised representation learning from vast corpora (Mikolov et al. 2013 Pennington et al. 2014 Devlin et al. 2019a Radford al. Notable causal language models (LMs), capable of passing high-stakes exams (Katz et al,
2019).
2024
OpenAl 2024 Jung et al. 2023), serving as general purppoe problem solvers (Brown al.
2020
and engaging in realistic conversations with beloved characters (De Freitas [2023 Chen et al.,
2024
owe their foundational abilities to next-token prediction learned from large-scale data (Brown
et al.
2020; Dubey et al., 2024] Riviere et al., (024). In corpus linguistics (McEnery & Hardie
2011
computational linguistics Jurafsky Martin (2024). and digital humanities (Jensen) 20014)
disciplines aiming to uncover the scientific and computational principles of human language- such vast linguistic resources, consisting of the language use itself, have become more indispensable than ever in this era of large-scale corpora (Van Der Zwaan et al. 2017 Mcgillivray et al.) 2020).
"Currently affiliated with NTT. E-mail: hi royuki .eelichheeehhhhhco @ntt..com

---

Published as a conference paper at ICLR 2025
Table 1: Hard pattern matching (c.g., grep) and soft pattern matching (our method). Hard matching is based on surface-level comparison and does not match if, e.g., synonym is used: Soft matching based on semantic comparison and robust to such variations thanks to word embeddings.
Pattern
Theorem 1
John was born in
Hard matching
thanks to Theorem 1
John was born in 1345 ...
(e.g., grep)
Soft matching
thanks to Theorem 1
John was born in 1345 ...
(ours)
Theorem holds because
Edward had died in May 1910
By Lemma we may assume
Robert was born in England ...
Equation 1 describes
the Emperor Henry, died in 1125
Given this context, the demand for efficient pattern matchers that enable rapid searches across mas- sive corpora is higher than ever (Liu et al.] 2024]] [Smadja 1993). For example, when harmful information, misinformation,
memorized privacy information is generated by large L.,, it is
necessary to identify the corresponding training instances where this information originated (Guo al. 2022 Wang al. 2024c; [ppolito et al., 2023 Biderman et al. 2023a). Another example is when researchers wish to determine which of two linguistic phenomena of interest is more frequent; conducting exhaustive searches across the largest available corpora is essential (Biber) 2015) for this purpose. Notably, many linguistic phenomena- word frequency as a simple example- a power-law distribution (Zipf] 1951 Heap 1980, Kobayashi & Tanaka- Ishii 2018). Consequently, only with vast corpora can we observe and analyze the various rare events residing in the long tail, which constitute the majority of linguistic phenomena.
One of the challenges when working with large corpora is that manternn-ttciinng tools based on string matching (Hakak et al. 2019), such as grep (Bambenek & Klus 2009) and zipgrep (Gallant 2024). or linguist-oriented tools often referred to as KWIC (Anthony 2013 Culy & Lyding 2010 Schweinberger 2024). primarily rely on surface-level exact matching as their core strategy. Because natural languages are characterized by their flexibility and richness in how humans can express similar concepts in different ways (McKeown) 1979) Witteveen & Andrews] 2019) Ganitkevitch ct al. 2013), strictly exact string matching may not meet users' demands. For example, on top of the query word in standard spelling, it is often desirable to catch non-standard spellings as well, such as how r instead of how are you, which are widespread particularly on the web and in texting (Schulz) 2018). Additionally, it is also desirable to catch different inflected word forms such as sing, sang, sung. sings, and singing. which differ only in their morphological features and share the same lemma (base form) (Don) 2014 Embick 2015). Rule-based exact matching is particularly hard when the target language is morphologically complex and exhibits irregular inflectional patterns.
To resolve the mismatch between the symbolic nature of existing pattern matchers and the diverse orthographic and morphological variations inherent in natural language, we have developed a soft (or semantic) yet efficient pattern matcher (Section 3). The core strategy is based on the simple idea of softening the matching process from binary {0. 1} values to continuous values, using word embeddings. By adopting inverted indexes and several other techniques, our tool can enumerate all softly matching instances in billion-scale corpora in less than a second. (Tall I shows specific examples of its operation. Our proposed method is capable not only of enumerating exact matches but also of flexibly listing semantically similar instances, even when their surface forms differ. For example, given the query "Theorem I", the method can retrieve instances such as "Lemma 5", This characteristic substantially enhances key tasks in both NLP and corpus linguistics. For instance, it improves the filtering of harmful texts, and facilitates more efficient example retrieval, particularly for languages with complex morphological features (Section 4).
The contributions of our study are summarized as follows.
We developed a soft (or semantic) pattern-matching algorithm- relaxation of the exact string matching-usine word embeddings (Section 3). By leveraging inverted indexing, we achieved high scalability (Sections 2.1 2.3 andd
GitHub: http://giihh..oookooommaaaaatttt
2

---

Published as a conference paper at ICLR 2025
We developed an easy-to-use web demo to facilitate interaction with the soft matching algo- rithm H This demo is particularly beneficial for NLP researchers and developers who want to analyze LMs in data-driven manner, well as for language learners and humanities researchers who are conducting language analysis on large corpora from the perspectives of corpus linguistics and digital humanities (Section 4.1)
For quantitative evaluation, we verified that our method achieves complete enumeration in less than a second on billion-scale corpora, which are commonly used in training large LMs (Section 4.2). For instance, the running time for searching over an English corpus with 3.4B words was less than 0.1 seconds without GPUs. This performance is comparable in speed to dense vector search; moreover, method enables the retrieval of examples closely aligned with specific queries, rather than just broad topical similarities.
We conducted qualitative evaluations in specific scenarios to verify the usefulness of the proposed method in both the fields of NLP and corpus linguistics. In experiments assuming the training of LMs on large-scale corpora, we provided search examples for identifying and removing harmful instances contained within the corpus (Section 4.2). In experiments assuming the analysis of classical Western languages by linguists, we chose Latin a lan- guage with highly complex inflections-al as example. We demonstrated that a corpus search with our tool can flexibly extract morphologically and semantically similar usage examples from the corpus (Section 4.3).
RELATED WORK
The procedures for finding sentences (or lines, documents) that match given pattern (query) prevalent across nearly all areas of computer science and data science, making it difficult to enu- merate all related research. In this section, we review particularly relevant work in NLP and com- putational linguistics, which are the primary focus of this study, as well as in the closely related areas of string matching. Beyond the fields discussed here, we believe many other domains, such as information retrieval, time series analysis, and semantic web, also have connections to this research.
2.1 NATURAL LANGUAGE PROCESSING AND CORPUS SEARCH
The significant progress in NLP over the past decade is largely attributed to deep-leaming-based self-supervised representation learning (Mikolov et al. 2013 Pennington et al., 2014 Bojanowski jct al.] Devlin et al.) 2019a Radford et al.) [019] Brown et al. 2020 Dubey et al. 2024). The vast corpora without label annotations serve as the source of such models' capabilities GGao jet al. 2020]] Biderman et al., 2023b) Raffel et al. 2019), and, therefore, these corpora are continu- ally referenced and analyzed for model improvement and evaluation (Biderman et al. 2023b). For instance, as LMs can memorize and elicit facts written in training corpora, they are reported to gen- erate text containing privacy-related information (Huang et al., 2022; Li et al., 2023 Lukas al.
2023
or content that could be used for terrorism or violence (Gehman et al., 2020 Schick et al., 2021 Kumar et al. (023). In this context, [ppolito et al.] (2023) work on filtering out verbatim memorization, requiring searches accross large-scale training corpora F N-gram substring pattern matchers, as representative tools for corpus search in NL.P, have been particularly well-developed
even before the advent of deep learning (Sekine, 2008 Sekine & Dalwani 2010). In terms of data
structures, inverted indexes (Sekine & Dalwani 2010
Rogozinski & Kuc 2016). and suffix arrays
including their variants (Sekine & Dalwani (0100) Yamamoto & Church 2001 Liu et al. 2024
Burrows et al. 1994, Ferragina & Manzini 2005] Langmead et al.) 2009) are typically employed.
Our algorithm based on inverted indexes due to its algorithmic requirements, which we discuss in /ection 3] Here, regardless of which data structure is used, it is important to note that existing n-gram matching techniques assume exact surface-level matching, making it extremely challenging to search and enumerate all relevant sentences while handling the complex characteristics of natural language, such as paraphrasing, orthographic variation, and inflection. Dense vector search (Khat-)
tab & Zaharia 2020, Karpukhin et al. 2020 Izacard et al. 2022] Wang et al. 2024a) has recently gained widespread popularity as the foundational technology for retrieval-aus -wggeall--ugmeteede generation
Demo: https:/softmatcca gith The screenshot of the demo is presented in Appendix C
3 Measuring influence of training corpus is also an important theme (Koh & Liang] 2017 Pruthi et al. 2020
Chen al. 2021 Isonuma & Titov 2024), but their application corpora remains highly challenging.
3

---

Published as a conference paper at ICLR 2025
(RAG) (Lewis et al. 2020; Khandelwal et al. 2020 Guu et al., 2020 Izacard et al. 2024). Dense vector search is highly compatible with approximate nearest neighbor search (Malkov Yashunin 2020 Jégou al. 20IT), and it offers significant advantage in reducing the issue of hallucina- tion (Ayala & Bechard 2024 Gao et al. 2023) in scenarios requiring factual knowledge. However, dense vector search is a relatively "coarse" method, primarily used to retrieve documents that are lopically similar, making it less suitable for the cases that require more specific n n--ram level queries.
2.2 CORPUS LINGUISTICS AND CORPUS SEARCH
Corpus linguistics is a subfield of linguistics that utilizes corpora to study language based on ex- amples of 'real-life' language use (McEnery & Wilson| 2001). Digital humanities, a closely related field, is an interdisciplinary domain that aims to advance humanities through the application of data and information science. In digital humanities as well, quantitative analysis of texts using corpora is also actively pursued (Jensen, 2014). Corpora consist of collections of texts or spoken language data (Van Der Zwaan et al.) 2017] Megillivray et al.) 2020), offering real-world examples of how language is used in various contexts. In most settings, an ideal corpus is large in size to ensure the statistical reliability of certain linguistic phenomena and to cover broader range of language use, including rare occurrences such as low-frequency words (Ha et al., 2009 Coole et al. 2020). Search tools (Hockey & Martin 1987; TEI Consortium 2023) are an indispensable element of corpus linguisties because they enable the identification of linguistic patterns, such as word frequen- cies, collocations, and syntactic structures. Traditional search methods commonly used in corpus linguisties include exact matching and its extension with regular expressions (Jurafsky & Martin 2024). However, given the nature of natural languages-witl their morphological complexity and unlimited paraphrases and synonyms with varying surface extreme difficulties in exhaustively enumerating instances that closely match a given query.
search methods face
2.3 STRING MATCHING
From an algorithmic point of view, our method is closely related to string matching algo- rithms (Hakak et al.] 2019). In what follows, we briefly give an algorithmic comparison with some of them and elucidate their relationship to ours. Offline string matching algorithms pro- cess the corpus text to build an index that accelerates future searches, a technique widely applied in search engines and information retrieval systems such as Elasticsearch (Rogozinski & Kuc, 2016) and Apache Lucene (Grand et al.) 2020). Inverted indexing is a well-known approach in this do- main (Zobel& & Moffat, 2006), and our method serves soft generalization of string matching algorithm based on inverted indexing. Online string matching algorithms do not rely on prepro- cessing and handle the corpus text the fly. Efficient algorithms include the Karp-Rabin, and Boyer-Moor algorithms (Knuth et al. 1977, Karp & Rabin 1987 Booerr & Moore, 1977]. While widely used in tools such as grep, online string matching is also basis of runtime verification (Bartocci et al. 2018), where system's 's execution data is monitored. Although it is pos- sible to relax these algorithms with word embeddings, the number of soft word comparisons in such a relaxation would be linear in the size of the corpus. In contrast, our algorithm requires only constant soft word comparisons, thanks indexing. See [Section 3.3 for the complexity analysis. Approximate string matching allows flexible matching, typically using edit distance to accommo- date noisy or incomplete data (Navarro 200T). Tools like agrep (Wu & Manber 1992b a) perform online matching that tolerates mismatches. Indexing- based algorithms are also proposed for approx- imate string matching (Boytsov) 201I). As a relaxation of exact string matching, approximate string matching is orthogonal to ours: approximate string matching focuses on relaxing surface-level com- parison, while our approach focuses on semantic-level similarity based on word embeddings. For example, morphologically irregular forms such as "person" and "people", only differing in plurality, will likely be missed in approximate string matching, while our methods are able to catch them.
Pratt,
3 OUR ALGORITHM FOR SOFT PATTERN MATCHING
3.1 OVERVIEW
Key aspect of design: Hard vs. Soft. One key aspect we considered in designing the algorithm for soft pattern matching is hard computation vs. soft computation. Hard (or exact) pattern matching
4

---

Published as a conference paper at ICLR 2025
Corpus text
When
jazz pianist plays funk with
blues singer
La
Inverted index
T juzz
Ttuess
(a) Preprocessing: Build the inverted index the corpus text.
Pattern
P
the
jazz
musician
where blues when jazz with funk
singer
Word
the this
plays play
musician
embeddings
pianist
Soft pattern
S
(th this, ... (jazz, blues, funk, ...
{musician, singer, pianist, ...
Matching Step Soften the pattern into the soft pattern.
Hit!
Hit!
jazz.
Ljuze
The
blues,
Inlues
I Ijazz
funk.
funk
mussician
Soft matches
M
Sjuce
Jjzz
a jazz pianist blues singer
(c) Matching Step 2-1: Get the soft inverted index.
(d) Matching Step 2-2: Find the soft matches.
Figure 1: Illustration of our algorithm for soft pattern matching.
(such grep) can process large texts blazingly fast. This is because hard matching requires only "hard computation", e.g., bitwise comparison, which highly efficient. Soft pattern matching, on the other hand, involves "soft computation". e.g., cosine similarity of two vectors. Since such soft computation involves many floating-point arithmetic operations over high-dimensional vectors, is typically much slower than hard computation. For instance, just taking the cosine similarity of pair of word embeddings can be as expensive as thousands of simple bitwise operations.
Overview of our algorithm. With this in mind, we designed the algorithm for soft pattern match- ing, which is precise and efficient. Our algorithm is illustrated in Figurre I| Our key idea is to run soft computation only over the vocabulary, not over the whole text as naive algorithm would do. More specifically, our algorithm works in the following two steps: For each query, (Step 1) it first per- forms soft computation over the vocabulary, softening the pattern into the soft pattern S,S2 ... S, (Fg.. Ib); (Step 2) then it performs hard computation that finds the exact positions in the corpus text that match the soft pattern Figs. Ic and [dp. Here, the soft pattern S1S² S,, is the key data in play. It consists of the set of vocabulary words that softly match each word of the pattern in terms of word embeddings. The amount of soft computation (Step is small, given that the vocabulary size typically much smaller than the size of the corpus text. The amount of hard computation (Step 2) also quite small, because it only handles filtered positions, not the whole corpus text.
3.2 DETAILS
Problem formulation. First, we formulate the soft pattern-matching problem by simply relaxing the classical hard (or exact) matternmmaching problem (Hakak et al. 2019) as follows:
5

---

Published as a conference paper at ICLR 2025
Algorithm 1:
Our soft pattern-matchinn algorithm.
Given
The corpus text f .... fN and its inverted index S [1, (I...., N) over each vocabulary word a such E I and only if = 4.
Input :
The phrase pattern p = P1 -- Pn, and the threshold a E (0, 1]. Output The set of soft match positions M (1,...,N) N) such that i M holds if and only if Pa Ra f+48-1 holds over any k I,...?..
// Step 1: Soften the pattern pipa into the soft pattern S1 ...
for k + 1...n do
Sk
for u V do
if a Pk then Se + Se U (n)
// Step 2-1: Get the soft inverted index hn by relaxing I with S.
for 1...n
L 1 Ø
for E Sk do it + I U
1/ Step 2-2: Get the cemplete matching M by aggregating h . I
for 2. 2...n do M M Mn
10 return M
The soft pattern-matching problem.
INPUT: The corpus text 41 ... IN V the pattern p P1 ... Pn V*, and the threshold a E (0,1]
OUTPUT: The set of soft match positions M with respect the soft equivalence Ra. i.e. Ph Ra li+k-1
the set M = (1...,,,
We define here the soft equivalence v Ra v' between words as v Ra v' A cos(F(()) F(t')) > o, to capture the similarity in terms of word embeddings E. Here, we let = (11, ..,..., UL be the vocabulary and write E(v) E iRD for the word embedding of word E V. Also, write cos(e, e') for the cosine similarity cos(e, e')
e.e' of word embeddings e, e' E R.D. Tell [e']
Preprocessing. Before processing queries, our algorithm preprocesses the whole corpus to compute the inverted index 1 (Fig. Iab, following a standard technique in search engine index- ing (Zobel & Moffat 2006). The inverted index I maps each vocabulary word V to the set of positions I fl...., N that represents the occurences of the word e in the corpus text t, that is, the set I = (1, v=
Our algorithm.
Algorithm and Figures to ld outline our algorithm for soft pattern matching. Our algorithm works in the following two steps:
1. For each query, it performs soft computation over the vocabulary, softening the pattern P1P2 ... PP, into the soft pattern S₁ S2 ... Sn (lines T in i 1] Figure 1b). Here, Sa is the set of vocabulary words that softly matches each word pk of the pattern in terms of the soft equivalence Na, i.c. Sg
E V V Za Pk
2. Then, it performs hard computation that computes the exact set of positions M in the corpus text that matches the soft pattern SyS² S, by the following two sub-steps:
2-1. Compute the soft inverted index ī, which maps each pattern word py the union i ULes, I, of the exact inverted index I over S₃ glines 5 to Fig. lch. The
set ja agrees with the set of positions that softly match the pattern word Pk. i.e.,
1 = {ie (1....,N) 44 Ra Pk
2-2. Output the set of soft matches M by computing the shifting intersection M n (k 1) E ix over the soft inverted index ī dlines 8 to

---

Published as a conference paper at ICLR 2025
Fig. Idh. The resulting set precisely agrees with the expected set, ie., M [L,..., N Vk nI....,nI.. Pk Ra }.
{i
We perform soft pattern matching using the index 1. First, for each word pk in p. we construct the set I indicating the positions of the words in t matching Ps (lines 1 to 4 we compare each word
V in the vocabulary with pk: <line 4) we add I, to JA if we have Ra Pk (line 7). Then, we construct the result M by aggregating each I considering the position & of Pæ: in
Inverted index vs. Suffix array. Our algorithm uses an inverted index rather than a suffix ar- ray (Yamamoto & Church 200T), which is crucial. A suffix army manages exact sequences of char- acters (or tokens) in the corpus text, for which softening patterns cannot be performed efficiently. In contrast, entries of an inverted index I, just have the occurrences of each word type and can be relaxed for soft matching simply by merging the sets, as illustrated in Fig. Ic
3.3 FORMAL ANALYSIS
How efficient is our algorithm? To answer this with theoretical guarantees, we analyze the time and space complexity of the algorithm. Overall, the high-level observation is that the corpus text size N affects the time and space required for preprocessing and soft matching only linearly.
The time complexity for constructing the inverted index is OI.x N), consisting of T. x exact word comparisons, since each vocabulary word u E V compared with each word in the corpus text t. Notably, the constant factor here typically very low, as only bitwise comparison is required. The total space required to store the inverted index / is only O(N + L), by simply storing the list of positions (of space O(II,)) for each vocabulary word v E V. This is because each position i E (1.2..... .N in the text t occurs exactly once in I and hence N = Evev [/]. The space complexity is also O(N + L), since no extra space required.
Preprocessing.
Soft matching. Step 1 for softening the pattern takes O(n x L) in time, where the dominant part is x L soft word comparisons (laking the cosine similarity of word embeddings) between each pattern word P3 and each vocabulary word v E (line 4). The space complexity is O k= S. Notably, the time and the space for Step are independent of the corpus text size N. Step 2 for finding the set of soft matches takes O(K) in time and space, where K the total size the soft inverted index & Remarkably, this is only linear to the corpus text size N.
" S
[Tel (or roughly the total number of 'candidate' positions for matches).
EMPIRICAL EVALUATION
We address the following research questions in the experiments:
RQI:
Does SoftMatcha scale to a billion-scale corpus, which is the typical size of training corpus for large causal LMs? (Section 4.2)
RQ2: Does SoftMat perform as expected in typical scenarios in NLP and corpus linguis- tics? (Sections 4.2 and
4.1 IMPLEMENTATION
We implemented the algorithm in Section as tool named SoftMat cha Our implementation adopts the following designs for efficiency. Firstly, design inverted index using sparse matrix in a compressed sparse row (CSR) format to reduce memory consumption and enable efficient access to the index for each word, i.e., T The index 7 represented by one-dimensional array, with the positions of each word contiguously allocated in memory. Secondly, we compile some time-consuming operations to native code using NUMBA (Lam et al. 2015). Specifically, line 4 in Algorithm I calculates word embedding similarities over x L times, i.c., the time complexity is
The word Matcha means powdered green tea in Japanese and is here pun for 'matcher'. Matcha softo in Japanese means soft-serve ice of green flavor.

---

Published as a conference paper at ICLR 2025
On L x D). where D is the dimension of each word embedding. To speed up this calculation, we leverage the vectorized instruction set (SIMD) for parallel processing. In addition, finding the intersection of two large sets in |lie 9 in Algorithm I is computationally expensive. We employ just-in-time (JIT) compilation and parallei loops for efficient comparisons of elements. To ensure reproducibility, we release our source code on GitHub (Footnote 1) and the package on Pypp
We provide a demo environment (Footnote 2) for users to explore the capabiliiies of our method and experience how diverse and linguistically natural the search results are and how quickly results can be obtained. The corpora used in experiments in Sections 4.2 and 4.3 are available. To prevent excessive output. for English and Japanese, only subsets of the corpora have been incorporated. Furthermore, search results are presented in smaller batches- to improve usability- with additional results available upon request, rather than all at once.
4.2 CASE STUDY IN NATURAL LANGUAGE PROCESSING - BILLION-SCALE CORPUS SEARCH
In this section, we simulate scenarios where NLP researchers use SoftMatcha on sillion-scale English and Japanese corpora. We focus on two types of evaluations: (i) quantitative evaluation we assess the running time using large data comparable in size to those used for training standard large LMs; and (ii) qualitative evaluation instances within large LM training corpora.
examine the tool's effectiveness in detecting toxic
Why English and Japanese? English is the dominant language in modern NLP and accounts for the largest portion of training data for large LMs (Brown et al. 2020; Chowdhery et al.) 2002 Tou- vron al. 2023). In contrast, Japanese presents a typologically distinct language, with orthographic and structural features that differ significantly from English, such as: (i) character types (alphabetic vs. hiragana, katakana, and kanji); (ii) syntax (SVO vs. SOV, head-initial vs. head-final); and (iii)
word segmentation (space-separated vs. word separation) (Haspelmath et al.) 2005). Further- more, the substantial size of Japanese corpora (Wikipedia 2024) makes it suitable for testing the scalability of our approach.
Setup. Corpora: we utilized the LLM-jp corpus v2.0 (LLM-jp et al., 2024). which con-
tains organized collections of Wikipedia articles both English (3.4B words) and Japanese (1.1B words). Word embeddings: we used GloVe
Sove-wiki-gigawwo 300 (Penning- ton et al. 2014) with a threshold a = 0.55 for the English word embeddings, and fastText facebook wwsttext-ttt-e.eee -ateettaa-eeeooos (Grave et al. 2018) with a threshold
0.50 for the Japanese word embeddings. Baseline methods: we compared the search results of So SoftMatcht with those of exact matching, i.e., pattern matching with a standard inverted index, and dense vector search using int intfloar float petat/mull /mmltiiiiiim/ i iinuuall 1-e1--e-elll large model (Wang et al. 2024b). In dense vec- tor search, we encoded each training instance in the corpus and built the graph-based index using hierarchical navigable small worlds (HNSW) (Malkov & Yashumin 2020) with the FAISS imple- mentation (Douze al. (2024) for the approximate nearest neighbor search. In HNSW, the number of edges was 32, the efConstruction was set to 40, and efSearch was configured as 16 (Malkov & Yashunin p020 We prepended the prefix "passage: " to each instance and "query: " to each query, following Wang et al. (2024b), and truncated any instances that exceeded 512 tokens. The text embeddings were calculated by averaging the contextualized token embeddings. Computational environment: we measured the running time on 152 core CPUs (Intel Xeon Platinum 8368 CPU @ 2.40GHz) and a 226 GiB main memory for the exact matching and softMatcha. and on NVIDIA A100 GPUs for the dense vector search.
Running time. We measured the indexing time and search time in both the English and Japanese Wikipedia articles. Table 2 demonstrates that SoftMat is faster than dense vector search in both indexing and search time and takes the same indexing time exact matching. Next, we investigated the relationship between the search speed and the corpus size. We constructed subsets of the English Wikipedia, whose sizes are {10 3 10-2 10 '} times that of the original corpus of 3.4B tokens, by randomly sampling from the original corpus, and measured the search time with each subset. Figure 2 shows the results. We observed that the search time increased only sublinearly,
5 PyPl: httpps:/ppppiirrrgptte//r https///pppp.or///mmmc///stttttt
AA training instance of I.M is chunk of texts, which may consist of multiple sentences.
8

---

Published as a conference paper at ICLR 2025
10"
Table 2: Running time (sec) of indexing and search in the English and Japanese Wikipedia articles.
0.55
---
1.0
time (seo)
En (3.4B words)
Ja (1.1B words)
10
Indexing
Search
Indexing
Search
Exact matching
685.8
0,005
242.5 0.022
So SoftMat cha
685.8
0.098
242.5
0.055
10
10"
10
Dense vector search
1036.5
0,389
320.4 0.283
size ratio
Figure 2: Running time on subsampled English Wikipedia corpora.
Table 3: Results of billion-scale corpus search in the English and Japanese Wikipedia articles.
Exact matching
SoftMatcha
Dense vector search
Query: "homemade bombs" (2 tokens) in English Wikipedia (3.4B words)
# Hits
107
1,473
n/a (depends on the top-k)
Match examples
homemade bombs
homemade bombs
Article: Survival Under Atomic Attack
home-made grenades
Article: Mark 24 nuclear bomb
homemade missiles
Article: List of common misconceptions
Query: Ka
(homemade bombs)" (2 tokens) Japanese Wikipedia (L.IB words)
Hits
27
42
n/a (depends on the top-k)
Match examples
I Te MA
Article: HE.k (freworks)
(homemadee bombb)
Chomenade hombs)
Article: 3 5 t6: (consumer fireworks)
home--ade grenades)
not linearly, with respect to the increase in corpus size. We thus confirmed that our algorithm works effectively for billion-scall corpus searches.
Search results. Table 3) shows the results of the billion-scale corpus search. We queried "home- made bombs" in the English Wikipedia corpus and "M (homemade bombs)" in the Japanese Wikipedia corpus. In the dense vector search, we selected some retrieved examples from the top- 10 search results. The table demonstrates that SoftMatche extends the exact matching. Note that the results of exact matching are a subset of the results of SoftMatch cha. In Japanese, the dense vector search retrieved an article of ""ES"" (fireworks), which does not contain the contents related to the query. In contrast, SoftMat cha lists all contents that have the query pattern or its similar pattern. In addition, while dense vector search allows semantic similarity search, it cannot identify where the query pattern is located in text. To summarize, text that exactly contains the query pattern is not always retrieved in dense vector search, i.e., the recall not always 100%, while exact matching and MaftMatct cha can return all texts that contain the query pattern, and SoftMatcha also enables matching of semantically similar patterns.
4.3 CASE STUDY IN CORPUS LINGUISTICS - RETRIEVING LATIN EXAMPLES
Why Latin? Latin is morphologically complex fusional language where lemma (dictionary form) may exhibit numerous different word forms depending on the morphological features (e.g., voice, mood, tense, aspect, person, and number for verbals; gender, number, and case for nominals) that the word bears. For example, a transitive verb may conjugate to more than 100 different finite verb forms. This morphological complexity makes it harder to search through corpus by exact matching. Furthermore, due to Latin's 's philological significance and the vast body of accumulated literature, there has been persistent demand for advanced search tools facilitate corpus analysis (Bamman & Smith 2012). For these reasons, Latin is suitable touchstone to test the utility of our proposed soft pattern matcher, particularly for humanities researchers and language learners.

---

Published as a conference paper at ICLR 2025
Table 4: Latin match examples by SoftMat cha with queries factus est 'he/it was done/fnisheddmmae and equas est 'it is a horse'. The top row of interlinear gloss represents words (and the cosine similarity between the matched word and its corresponding query word), the middle row their morphological analysis, and the bottom row the free translation. Morphological matches are highlighted in pink, semantics matches blue, and exact matches green.
Query
Query
factus
est
equus
est De.IND.PRS.35
do. PTW.PPPPPPP...M...O
DEC.IN..RR..3
horse. M.NOM.GG 'i is horse'
heeh is dlon/finishedmmade
Matches
Matches
0.56
0.56
0.48 bos
1.00
facta
sunt
est
N...PAS.FF.PTP.NN. N......
Pe..ND.PRS.3PL
COW.E.NOM.SG 'it is cow:"
PRS.NGG
"hey are done' 'they are facts'
0.53
0.58
0.44
0.63
mortuus
essef
fuil
D.C.CC..P..TCC-M..O...
CE.SUB.IMPP.356
ChariotM.NOM.SC
be.IND.PF.3GG
hheit was dead'
' was a chariot"
0.65
0.65
0.49
0.58
creatus
erul
Minotaurus
essef
create, PASS.PP. PWW.PTCPMMNNO....
bc.IND. 3MG
Minotaur.M. M.NOM.SG I.SUU..MPP.33.. 't would be the Minotaur"
'hefit was created"
Setup. Corpora: we used two corpora: one from the Perseus Project (Crane) 2023 (5M tokens) and the Augustinian Sermon Parallelism (ASP) Dataset (Bothwell et al. 2023) (0.IM tokens). Word embeddings: we used the pre-trained fastText embeddings (Grave et al. 2018).
Search results. Table shows the returned matches with the queries factus est ('it/he done' or 'it/he is made') and equus est ('it is a horse'). It is evident that SoftMatche effectively links the queries to semantically similar words, as seen in mortuus 'dead' and creatus 'created' matched with the query factus 'done, finished, made", and bos 'cow", currus 'chariot', and Minotaurus 'Minotaur' with equus 'horse'. Interestingly, the tool is also able to catch different word forms with different morphological features while sharing the same lemma, which are highlighted in pink. For example, although the Latin copula verb the query est 'is' exhibits highly irregular conjugation patterns, the matches successfully include their inflected forms such sunt, esset, erat, and fuit. Furthermore, the matches mortuus and creatus are not only semantically similar to the query word factus but also have morphological features in common (perfect, participle, masculine, nominative, and singular).
5 CONCLUSION
In this paper, we propose new mattern-matching algorithm that can flexibly handle the orthographic diversity of natural languages while also performing efficiently on large-scale corpora. Our algo- rithm, combining word embeddings and inverted indexing, achieves inference speed independent of corpus size. We have also developed and released simple-to-use web demo for researchers and practitioners. For quantitative evaluation, we confirm that the developed tool can enumerate all search results within one second on billion-scale corpora, typical scenario in training large LMs. For qualitative evaluation, we assess the tool in typical scenarios in NLP (detecting harmful examples from large-sec scale Japanese and English Wikipedia corpora) and computational linguistics (example retrieval from Latin, a language with highly diverse inflections), observing that our method retrieve semantically similar examples that hard pattern matchers would miss.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We conducted experiments using the language and computational resources of LLM-ip (ttpps: 7/1lm- jp. nii ac. ip). This research was supported in part by JSPS KAKENHI JP24KI0133, ISPS KAKENHI J223K24910, JST ACT-X JPMJAX200S, JST ACT-X JPMIAX200U, JST FOR- EST JPMJFR2331, JST PREST JPMJPR22CA, and JST CREST JPMJCR2012.
ETHICS STATEMENT
The corpora used for training large LMs, composed of web corpora. including Common Crawl (Common Crawl 2024) and digitized book data such as (Zhu 2013), can be said encompass substantial portion of humanity's s linguistic knowledge. Inevitably, these corpora include signifi- cant amount ethically problematic content. This includes personal information (Subramani al.) 2023), as well as information that could be "beneficial" for violence and terrorism (or in ventional terms, harmful information) (Albalak et al. (024). Moreover, as these corpora continue to grow exponentially and our languages possess numerous paraphrases, comprehensively identifying such harmful learning resources is far from a simple task. Our research aims to substantially simplify this crucial activity for human ethics: identifying harmful learning instances within vast linguistic resources Section 4.2] We hope that, by leveraging our tool, NLP researchers and developers will contribute providing LLMs as safe and reliable social infrastructure.
REPRODUCIBILITY STATEMENT
Our source code is available on GitHub (ooonnoe 1t, and released installable package PyPI (Footnote 5). all experiments, we used open datasets. Further details on the embeddings, corpora, computational environment, and protocols used in experiments explained in |Section 4
REFERENCES
Alon Albalak, Yanai Elazar, Sang Michael Xie, Shayne Longpre, Nathan Lambert, Xinyi Wang, Niklas Muennighoff, Bairu Hou, Liangming Pan, Haewon Jeong, Colin Raffel, Shiyu Chang, Tatsunori Hashimoto, and William Yang Wang. A Survey on Data Selection for Language Models. arXiv (LJ. 26 February 2024. URL /ttp/v/xvvv//.////////e/////.al. wwwpwiiv.org/aaaaeeoe absgg//bb//2a 2ttp//242........ abtpg///bb//222266633
Laurence Anthony. A critical look at software tools in corpus linguistics. Linguistic Research, 30 (2):141-161, 2013.
Orlando Ayala and Patrice Bechard. Reducing hallucination in structured outputs via retrieval- augmented generation. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies (Volume 6: Indus- try Track), pp. 228-238, Stroudsburg, PA, USA, 2024. Association for Computational Linguistics. URL https: https///aaaaaatttaa /ttp://aaaaaaaooooooooo//////
nww.l wiw.aaaclliiiuuur....u 19 ppdf
John Bambenek and Agnieszka Klus. Grep Pocket Reference: A Quick Pocket Reference for Utility Every UNIX User Needs. O" O'Reilly Media, 2009.
David Bamman and David Smith. Extracting two thousand years of latin from million book library. Comput. Cult. Herit,, 5(1), April 2012. ISSN 155564673. doi: 10.11445/260116221160066 URI.
httpps:/ddo org.orgggl/o
Ezio Bartocci, Yliès Falcone, Adrian Francalanza, and Giles Reger. Introduction runtime verifi- cation. Lectures on Runtime Verification, volume 10457 Lecture Notes in Computer Science, pp. 1-33. Springer, 2018
Michael Bendersky, Honglei Zhuang, Ji Ma, Shuguang Han, Keith Hall, and Ryan McDonald. Rrf102: Meeting the trec-covid challenge with a 100+ runs ensemble, 2020. URL https:
//arxiv. wwtp://worr//b////..cooo 00200
11

---

Published as a conference paper at ICLR 2025
Douglas Biber. Corpus-Bass Based and Corpus-Drives Analyses of Language Variation and Use. In The Oxford Handbook of Linguistic Analysis. Oxford Academic, 2nd edition, 2015. doi: 10.1093/
Stella Biderman, USVSN Sai Prashanth, Lintang Sutawika, Hailey Schoelkopf, Quentin Anthony, Shivanshu Purohit, and Edward Raff. Emergent and Predictable Memorization in Large Language Models, 2023a. URL
http://aaxiiviogggr/////////0// 11158
Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O'Brien, Eric Hal- lahan, Mohammad Aflah Khan, Shivanshu Purohit, Usvsn Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal. Pythia: A suite for analyzing large language models across training and scaling. arXiv [es. (CS. April 2023b. URL http:
wawxii.crgg/o........o... /ab////////// 2204. 01373
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. Enriching word vectors with subword information. Trans. Assoc. Comput. Linguist,, 5:135-146, December 2017. URL
https://ack antho wochoooooy..... logy. 0rgy.org//77-10100 pdf
Stephen Bothwell, Justin DeBenedetto, Theresa Crnkovich, Hildegund Müller, and David Chiang- Introducing Rhetorical Parallelism Detection: A New Task with Datasets, Metrics, and Base- lines. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings the 2023 Conference Empirical Methods in Natural Language Processing, pp. 5007-5039, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 18158/6//111 wwtp://......m.mmiinnn.mmm https://aclantholoogg ott.aaaaaaattooooooooooo0//2222 emnlp ma 305
the
URL
Robert Boyer and Strother Moore. A Fast String Searching Algorithm. Commun. ACM, 20
(10):762-772, 1977. doi: 10.11145/599442.55989,, URL
359842.358859
Leonid Boytsov. Indexing methods for approximate dictionary searching: Comparative analysis. ACM J. Exp. Algorithmics, 16(1), 2011.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam Mc- Candlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language Models are Few-Shot Learners Advances in Neural Information Processing Systems, 33:1877-1901, 2020. URL pttps::/pproeeddngs www.eeediiinnnnnnnnneeee www.nnnuri.... wwtpsss.ccpppppppppepeeepe files/paper/2020 fi e/
.pdf
Michael Burrows, D J Wheeler D I G 1 T A L, Robert W. Taylor, David J. Wheeler, and David Wheeler. A block-sorting lossless data compression algorithm. 1994. URL /htpss//appi
wewanticscholeeeeeo org/ Corpus ID: 0222217455 67441
Julius Caesar. Commentarii de bello gallico. With explanatory notes, lexicon, maps, indexes, etc. Eldredge & Brother, Philadelphia, 1882.
Yi-Pei Chen, Noriki Nishida, Hideki Nakayama, and Yuji Matsumoto. Recent Trends in Person- alized Dialogue Generation: A Review of Datasets, Methodologies, and Evaluations. In Pro- ceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (IREC-COLMN) 2024), pp. 13650-13665, 2024. URI. hntpp:
//aclanthology o 20244 -rec-mainnee n. 11 pd
Yuanyuan Chen, Boyang Li, Han Yu, Pengcheng Wu, and Chunyan Miao. HyDRA: Hypergra- dient Data Relevance Analysis for Interpreting Deep Neural Networks. Proc. Conf. AAAI Ar- tif. Intell., 7001)))08177899 18 May 2021. URL BRLhttps:/ /dd aaai otgp//////1/111111111 16871-13-20663 1-22-2222221111 pdf..
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh,
12

---

Published as a conference paper at ICLR 2025
Kensen Shi, Sasha Tsyyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard. Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov. Katherine Lee, Zongwei Zhou, Xuezhi Wang, Bren- nan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy
Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. PaLM: Scaling language modeling with Pathways. arXiv [cs.CL]. CLJ, 5 April 2022. URL http: /ttt://rxiiii .ogg abs////b///// /204. 02311
Common Crawl. Common Crawl Open Repository of Web Crawl Data, 2024. URL https:
//commoncrawl. org/
Matthew Coole, Paul Rayson, and John Mariani. LexiDB: Patterns & Methods for Corpus Linguis- tic Database Management. In Proceedings of the Twelfth Language Resources and Evaluation Conference, pp. 3128-3135, 2020. URL battps://aclaatioloogy wrg.loyy.org//2000 1rec- 383. pdf
Gregory Crane. The Perseus Digital Library and the future of libraries. International Journal on Digital Libraries, 2023. doi: 10.10077600799-022-00033
Chris Culy and Verena Lyding. Double Tree: An Advanced KWIC Visualization for Expert Users. In 2010 14th International Conference Information Visualisation, pp. 98- 18-103, 2010. doi: 10. 1109//
Daniel De Freitas Announcing our Series A and our new Al model, C1.2. https://blog 23 March 2023. Accessed: 2024-10-1.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference the North American Chapter of the Association for Computational Linguistics, pp. 4171-41888 Stroudsburg, PA, USA, 2019a. Association for Computational Linguistics. URL https:// aclanthology www.oogggg...........ooo.o...... 10119-122..0 pdf
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume 1 (Long and Short Papers), pp. 4171 1171-4186, Minneapolis, Minnesota, June 2019b. Association for Com- putational Linguisties. doi: 10. 10.1853//1/N19-111
URL
N19-14233
Jan Don. Morphological theory and the morphology of English. Edinburgh University Press, 2014. doi: 10.155579780748645145.
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The Faiss library, 2024.
URL https:ts:: / http::::///xxxvvr/o///oo abs/ /2011 08281
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, Anirudh Goyal, Anthony Hartshorn, Aobo Yang, Archi Mitra, Archie Sravankumar, Artem Korenev, Arthur Hinsvark, Arun Rao, Aston Zhang, Aurelien Rodriguez, Austen Gregerson, Ava Spataru, Baptiste Roziere, Bethany Biron, Binh Tang, Bobbie Chern, Charlotte Caucheteux, Chaya Nayak, Chloe Bi, Chris Marra, Chris McConnell, Christian Keller, Christophe Touret, Chunyang Wu, Corinne Wong, Cristian Canton Ferrer, Cyrus Nikolaidis, Damien Allonsius, Daniel Song. Danielle Pintz, Danny Livshits, David Esiobu, Dhruv Choudhary, Dhruv Mahajan, Diego Garcia-Olano, Diego Perino, Dieuwke Hupkes, Egor Lakomkin, Ehab AlBadawy, Elina Lobanova, Emily Dinan, Eric Michael Smith, Filip Radenovic, Frank Zhang, Gabriel Synnaeve, Gabrielle Lee, Georgia Lewis Ander- son, Graeme Nail, Gregoire Mialon, Guan Pang. Guillem Cucurell, Hailey Nguyen, Hannah
13

---

Published as a conference paper at ICLR 2025
Korevaar, Hu Xu, Hugo Touvron, Ilyann Zarov, Imanol Arrieta Ibarra, Isabel Kloumann, Ishan Misra, Ivan Evtimov, Jade Copet, Jaewon Lee, Jan Geffert, Jana Vranes, Jason Park, Jay Ma- hadcokar, Jeet Shah, Jelmer van der Linde, Jennifer Billock, Jenny Hong, Jenya Lee, Jeremy Fu, Jianfeng Chi, Jianyu Huang, Jiawen Liu, Jie Wang, Jiecao Yu, Joanna Bitton, Joe Spisak, Jongsoo Park, Joseph Rocca, Joshua Johnstun, Joshua Saxe, Junteng Jia, Kalyan Vasuden Al- wala, Kartikeya Upasani, Kate Plawiak, Ke Li, Kenneth Heafield, Kevin Stone, Khalid El-Arini, Krithika Iyer, Kshitiz Malik, Kuenley Chiu, Kunal Bhalla, Lauren Rantala- Yeary, Laurens van der Maaten, Lawrence Chen, Liang Tan, Liz Jenkins, Louis Martin, Lovish Madaan, Lubo Malo, Lukas Blecher, Lukas Landzaat, Luke de Oliveira, Madeline Muzzi, Mahesh Pasupuleti, Man- nat Singh, Manohar Paluri, Marcin Kardas, Mathew Oldham, Mathieu Rita, Maya Pavlova, Melanie Kambadur, Mike Lewis, Min Si, Mitesh Kumar Singh, Mona Hassan, Naman Goyal, Narjes Torabi, Nikolay Bashlykov, Nikolay Bogoychev, Niladri Chatterji, Olivier Duchenne, Onur Çelebi, Patrick Alrassy, Pengchuan Zhang, Pengwei Li, Petar Vasic, Peter Weng, Prajjwal Bhar- gava, Pratik Dubal, Praveen Krishnan, Punit Singh Koura, Puxin Xu, Qing He, Qingxiao Dong, Ragavan Srinivasan, Raj Ganapathy, Ramon Calderer, Ricardo Silveira Cabral, Robert Stojnic, Roberta Raileanu, Rohit Girdhar, Rohit Patel, Romain Sauvestre, Ronnie Polidoro, Roshan Sum- baly. Ross Taylor, Ruan Silva, Rui Hou, Rui Wang, Saghar Hosseini, Sahana Chennabasappa. Sanjay Singh, Sean Bell, Seohyun Sonia Kim, Sergey Edunov, Shaoliang Nie, Sharan Narang. Sharath Raparthy, Sheng Shen, Shengye Wan, Shruti Bhosale, Shun Zhang, Simon Vandenhende, Soumya Batra, Spencer Whitman, Sten Sootla, Stephane Collot, Suchin Gururangan, Sydney Borodinsky, Tamar Herman, Tara Fowler, Tarek Sheasha, Thomas Georgiou, Thomas Scialom, Tobias Speckbacher, Todor Mihaylov, Tong Xiao. Ujjwal Karn, Vedanuj Goswami, Vibhor Gupta, Vignesh Ramanathan, Viktor Kerkez, Vincent Gonguet, Virginie Do, Vish Vogeti, Vladan Petro- vic, Weiwei Chu, Wenhan Xiong, Wenyin Fu, Whitney Meers, Xavier Martinet, Xiaodong Wang, Xiaoqing Ellen Tan, Xinfeng Xie, Xuchao Jia, Xuewei Wang, Yaelle Goldschlag, Yashesh Gaur, Yasmine Babaei, Yi Wen, Yiwen Song, Yuchen Zhang, Yue Li, Yuning Mao, Zacharie Delpierre Coudert, Zheng Yan, Zhengxing Chen, Zoe Papakipos, Aaditya Singh, Aaron Grattafiori, Abha Jain, Adam Kelsey, Adam Shajnfeld, Adithya Gangidi, Adolfo Victoria, Ahuva Goldstand, Ajay Menon, Ajay Sharma, Alex Boesenberg, Alex Vaughan, Alexei Baevski, Allie Feinstein, Amanda Kallet, Amit Sangani, Anam Yunus, Andrei Lupu, Andres Alvarado, Andrew Caples, Andrew Gu, Andrew Ho. Andrew Poulton, Andrew Ryan, Ankit Ramchandani, Annie Franco, Aparajita Saraf, Arkabandhu Chowdhury, Ashley Gabriel, Ashwin Bharambe, Assaf Eisenman, Azadeh Yazdan, Beau James, Ben Maurer, Benjamin Leonhardi, Bernie Huang, Beth Loyd, Beto De Paola, Bhargavi Paranjape, Bing Liu, Bo Wu, Boyu Ni, Braden Hancock, Bram Wasti, Bran- don Spence, Brani Stojkovic, Brian Gamido, Britt Montalvo, Carl Parker, Carly Burton, Catalina Mejia, Changhan Wang, Changkyu Kim, Chao Zhou, Chester Hu, Ching-Hsiang Chu, Chris Cai, Chris Tindal, Christoph Feichtenhofer, Damon Civin, Dana Beaty, Daniel Kreymer, Daniel Li, Danny Wyatt, David Adkins, David Xu, Davide Testuggine, Delia David, Devi Parikh, Diana Liskovich, Didem Foss, Dingkang Wang, Duc Lc, Dustin Holland, Edward Dowling, Eissa Jamil, Elaine Montgomery, Eleonora Presani, Emily Hahn, Emily Wood, Erik Brinkman, Esteban Ar- caute, Evan Dunbar, Evan Smothers, Fei Sun, Felix Kreuk, Feng Tian, Firat Ozgenel, Francesco Caggioni, Francisco Guzmán, Frank Kanayet, Frank Seide, Gabriela Medina Florez, Gabriella Schwarz, Gada Badeer, Georgia Swee, Gil Halpern, Govind Thattai, Grant Herman, Grigory Sizov, Guangyi, Zhang, Guna Lakshminarayanan. Hamid Shojanazeri, Han Zou, Hannah Wang, Hanwen Zha, Haroun Habeeb, Harrison Rudolph, Helen Suk, Henry Aspegren, Hunter Gold- man, Ibrahim Damlaj, Igor Molybog, Igor Tufanov. Irina-Elens Veliche, Itai Gat, Jake Weissman, James Geboski, James Kohli, Japhet Asher, Jean-Baptiste Gaya, Jeff Marcus, Jeff Tang, Jennifer Chan, Jenny Zhen, Jeremy Reizenstein, Jeremy Teboul, Jessica Zhong, Jian Jin, Jingyi Yang. Joe Cummings, Jon Carvill, Jon Shepard, Jonathan McPhie, Jonathan Torres, Josh Ginsburg, Junjie Wang, Kai Wu, Kam Hou U, Karan Saxena, Karthik Prasad, Kartikay Khandelwal, Katayoun Zand, Kathy Matosich, Kaushik Veeraraghavan, Kelly Michelena, Keqian Li, Kun Huang, Kunal Chawla, Kushal Lakhotia, Kyle Huang, Lailin Chen, Lakshya Garg, Lavender A, Leandro Silva, Lee Bell, Lei Zhang, Liangpeng Guo, Licheng Yu, Liron Moshkovich, Luca Wehrstedt, Madian Khabsa, Manav Avalani, Manish Bhatt, Maria Tsimpoukelli, Martynas Mankus, Matan Hasson, Matthew Lennie, Matthias Reso, Maxim Groshev, Maxim Naumov, Maya Lathi, Meghan Ke- neally, Michael L Seltzer, Michal Valko, Michelle Restrepo, Mihir Patel, Mik Vyatskov, Mikayel Samvelyan, Mike Clark, Mike Macey, Mike Wang, Miquel Jubert Hermoso, Mo Metanat, Mo- hammad Rastegari, Munish Bansal, Nandhini Santhanam, Natascha Parks, Natasha White, Navy- ata Bawa, Nayan Singhal, Nick Egebo, Nicolas Usunier, Nikolay Pavlovich Laptev, Ning Dong,
14

---

Published as a conference paper at ICLR 2025
Ning Zhang, Norman Cheng, Oleg Chemoguz, Olivia Hart, Omkar Salpekar, Ozlem Kalinli, Parkin Kent, Parth Parekh, Paul Saab, Pavan Balaji, Pedro Rittnrr, Philip Bontrager, Pierre Roux, Piotr Dollar, Polina Zvyagina, Prashant Ratanchandani, Pritish Yuvraj, Qian Liang, Rachad Alao, Rachel Rodriguez, Rafi Ayub, Raghotham Murthy, Raghu Nayani, Rahul Mitra, Raymond Li, Rebekkah Hogan, Robin Battey, Rocky Wang, Rohan Maheswari, Russ Howes, Ruty Rinott, Sai Jayesh Bondu, Samyak Datta, Sara Chugh, Sara Hunt, Sargun Dhillon, Sasha Sidorov, Sa- tadru Pan. Saurabh Verma, Seiji Yamamoto. Sharadh Ramaswamy, Shaun Lindsay, Shaun Lind- say, Sheng Feng, Shenghao Lin, Shengxin Cindy Zha, Shiva Shankar, Shugiang Zhang, Shuqiang Zhang, Sinong Wang, Sneha Agarwal, Soji Sajuyigbe, Soumith Chintala, Stephanie Max. Stephen Chen, Steve Kehoe, Steve Satterfield, Sudarshan Govindaprasad, Sumit Gupta, Sungmin Cho, Sunny Virk, Suraj Subramanian, Sy Choudhury, Sydney Goldman, Tal Remez, Tamar Glaser, Tamara Best, Thilo Kohler, Thomas Robinson, Tianhe Li, Tianjun Zhang, Tim Matthews, Tim- othy Chou, Tzook Shaked, Varun Vontimitta, Victoria Ajayi, Victoria Montanez, Vijai Mohan, Vinay Satish Kumar, Vishal Mangla, Vitor Albiero. Vlad Ionescu, Vlad Poenaru, Vlad Tiberiu Mihailescu, Vladimir Ivanov, Wei Li, Wenchen Wang. Wenwen Jiang, Wes Bouaziz, Will Con- stable, Xiaocheng Tang, Xiaofang Wang, Xiaojian Wu, Xiaolan Wang, Xide Xia, Xilun Wu, Xinbo Gao, Yanjun Chen, Ye Hu, Ye Jia, Ye Qi, Yenda Li, Yilin Zhang, Ying Zhang, Yossi Adi, Youngjin Nam, Yu, Wang, Yuchen Hao, Yundi Qian, Yuzi He, Zach Rait, Zachary DeVito, Zef Rosnbrick, Zhaoduo Wen, Zhenyu Yang, and Zhiwei Zhao. The Llama 3 herd of models. arXiv [cs.Al], 31 July 2024. URL http::tt://aatt
org/ abs
David Embick. The morpheme: A theoretical introduction. De Gruyter Mouton, Berlin, München, Boston, 2015. doi: (0.1515/9781501102555
Paolo Ferragina and Giovanni Manzini. Indexing compressed text. J. ACM, 52(4)5552-581, July 2005. ISSN 0004-5411. doi: 10.1145/183233611822009 URL httpps://oi..zg//11 1145/108200 1082039
Andrew Gallant. ripgrep: ripgrep recursively searches directories for a regex pattern while respect- ing your gitignore, 2024. URL
Juri Ganitkevitch, Benjamin Van Durme, and Chris Callison- PPDB: The Paraphrase Database. In Proceedings of the 2013 Conference of the North American Chapter of the As- sociation for Computational Linguistics: Human Language Technologies, pp. 758-764, 2013. URL htttts::s//ccattatt/t ogy.ogy..oo.o...............oo 20gyyoorg/111110000 1092 pdf
Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang. Horace He, Anish Thite, Noa Nabeshima, Shawn Presser, and Connor Leahy. The pile: An 800GB dataset of diverse text for language modeling. arXiv [cs.CL], 31 December 2020.
WtRLihtt:///axtttt org abs. 00027
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Meng Wang, and Haofen Wang. Retrieval-angmenttd generation for large language models: A survey. arXiv (CJ, 18 December 2023. URL /taxxiv//axxi..../ org/ abs 2aabs/2312 2212. 10997
Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A Smith. Real- ToxicityPrompts: Evaluating neural toxic degeneration in language models. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 3356-3369, Stroudsburg, PA, USA, November 2020. Association for Computational Linguistics. URL https:// aclanthology oro//////////// 2020. wwndinnnnnnnnnnnnn emprspeemmnpp..... 301. pdf
Adrien Grand, Robert Muir, Jim Ferenczi, and Jimmy Lin. From MAXSCORE to Block-Max Wand: The Story of How Lucene Significantly Improved Query Evaluation Performance. In ECIR (2), volume 12036 of Lecture Notes in Computer Science, pp. 20-27. Springer, 2020.
Edouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomas Mikolov. Learning Word Vectors for 157 Languages, 2018.
Zhijiang Guo, Michael Schlichtkrull, and Andreas Vlachos. A Survey Automated Fhec-Ch. Transactions of the Association for Computational Linguisticss 10: 206, 2022. doi: 16.1 tacl 00454. URL
15

---

Published as a conference paper at ICLR 2025
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wo Wei Chang. REALM: Retrieval- Augmented Language Model Pre- Training. In Proceedings of the 37th International Conference Machine Learning, ICML'20. JMLR.org, 2020.
Le Quan Ha, Philip Hanna, Ji Ming, and F. J. Smith. Extending Zipf's law to n-grams for large corpora. Artificial Intelligence Review, 2009. doi: 10. 000000//114020009-919919
Saqib Hakak, Amirrudin Kamsin, Palaiahnakote Shivakumara, Gulshan Amin Gilkar, Wazir Zada Khan, and Muhammad Imran. Exact String Matching Algorithms: Survey, Issues, and Future Research Directions. IEEE Access, 7:69614-69637 2019, doi: 10. 10.100//ACCESSS221992299 URL https: / / 00ci.oo00 /0. 110.0/119991000
/ttp///..///...1//////////////// www.:///////...... 2019. 2914071
Martin Haspelmath, Martin S Dryer, David Gil, and Bernard Comrie. The World Atlas of Language Structures. Oxford University Press, London, England, 21 July 2005.
H. Heap. Information retrieval: Computational and thcoretical aspects. Libr. Q. 50(1):153-154, January 1980. URL http: //wp:///xxxoooooo/ org/ 11.1111111181 100.1086666887
Susan Hockey and Jeremy Martin. The Oxford Concordance Program version 2. Literary and Linguistic Computing, 2(2):125-131) January 1987. doi: 10.10993/lc2..2.125..
Jie Huang, Hanyin Shao, and Kevin Chen-Chuan Chang. Are Large Pre- Pre-Trained Language Models Leaking Your Personal Information? In Findings of the Association for Computational Linguis- fies: EMNLP 2022, pp. 2038-2047, December 2022. URL https:::::: /aaclaanttttt aclantho ogy. org/
2022. wwndingsnnniiie....ee..n emnlp 148. pdf
Daphne Ippolito, Florian Tramer, Milad Nasr, Chiyuan Zhang, Matthew Jagielski, Katherine Lee, Christopher Choquette Choo, and Nicholas Carlini. Preventing generation of verbatim memoriza- tion in language models gives a false sense of privacy. In C. Maria Keet, Hung-Y Yi Lee, and Sina Zarrieß (eds.), Proceedings of the 16th International Natural Language Generation Conference, pp. 28-53, Prague, Czechia, September 2023, Association for Computational Linguistics. doi: 10. URL http::ts:://ctl http:///aaaanntooo..o.o.o org. 1.2..inggge. inig-
18653/v h/tp::/.nnn22.mmmiiii...
Masaru Isonuma and Ivan Titov. Unlearning Traces the Influential Training Data of Language Mod- cls. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 6312-6325, Stroudsburg, PA, USA, 2024. Association for Compu- tational Linguistics. URL httppss:/aaaaanhlll....oo wwg.://looooooooooooooooooooee 220//22244222 ac1- 343. pdd
Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave, Unsupervised Dense Information Retrieval with Contrastive Learn- ing, 2022. /tRpsss::///xxix
abs//11111 09118
Gautier Izacard, Patrick Lewis, Maria Lomeli, Lucas Hosseini, Fabio Petroni, Timo Schick, Jane Dwivedi- Yu, Armand Joulin, Sebastian Riedel, and Edouard Grave. Atlas: Few-shot Learning with Retrieval Augmented Language Models. J. Mach. Learn. Res., 24(1), March 2024. ISSN 1532-4435.
Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1):177-28,, 2011.
Kim Ebensgaard Jensen. Linguistics in digital humanities: (computational) corpus linguistics. MedieKultur: Journal of Media and Communication Research, 30(57), 2014. doi: 10.7146/ mediekkultur.y30557..5555
Leonard B Jung, Jonas A Gudera, Tim L T Wiegand, Simeon Allmendinger, Konstantinos Dimi- triadis, and Inga K Koerte. ChatGPT Passes German State Examination in Medicine With Pic- ture Questions Omitted. Dtsch. Arztel.. Int., 1 120(21):373331) 374,, 30 May 2023. URL http:
dibx.doi..rg. 10. 3238/ 1338/arztebl. www.tteell..02...mmmmmm C113
Daniel Jurafsky and James H. Martin. Speech and Language Processing: An Introduction to Natural Language Processing. Computational Linguistics. and Speech Recognition with Language Mod- els. 3rd edition, 2024. ht //web. st staford. edu/ htt.a//uuddduuuaaf33/////s// Online
manuscript released August 20, 2024.
16

---

Published as a conference paper at ICLR 2025
Richard M. Karp and Michael O. Rabin. Efficient Randomized Pattern-Matchin Algorithms. IBM
J. Res. Dev. (1(2):249-2666 1987.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense Passage Retrieval for Open-Domain Question Answering. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), P). pp. 6769-6781, Online, November 2020. Association for Computational Linguistics. doi: 10. 00.18633/v1/2000 100000001-1122000.00mmmmmm 2020 emn 1--malppmmmiii 550
URL https: hatt:::/www..cccvee.oo/////aaa wwtp:::wwwwwww............. wwtp://wwwww.../////.ooo.ooo/.o.
Daniel Martin Katz, Michael James Bommarito, Shang Gao, and Pablo Arredondo. GPT-4 Passes the Bar Exam. Philos. Trans. A Math. Phys. Eng. Sci., 382(2270):20232254, 15 April 2024. URL
0254
Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. General- ization through Memorization: Nearest Neighbor Language Models. In International Confer- Learning Representations, 2020. URL httLhhtt///// /ttpp:/v///peeevveew net httt/formm?iee
HklBiccs [BjEKH
Omar Khattab and Matei Zaharia. ColBERT: Efficient and Effective Passage Search via Contextu- alized Late Interaction over BERT. In Proceedings of the 43rd International ACM SIGIR Confer- ence on Research and Development in Information Retrieval, New York. NY, USA, 25 July 2020.
ACM. URL https: / dl. acm. org/ 0100//.0.115/3397220 3401075
Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6(2):323-350 1977.
Tatsuru Kobayashi and Kumiko Tanaka-Ishii. Taylor's law for Human Linguistic Sequences. In Proceedings ofth the 56th Annual Meeting the Association for Computational Linguistics (Volume 1: Long Papers), pp. 11 1138-1148, Stroudsburg. PA, USA, 2018. Association for Computational Linguistics. URL https: beattps://aclantho..oggo/ wtg.://oo.oo....ooo.
pdf
Pang Wei Koh and Percy Liang. Understanding Black-box Predictions via Influence Functions. arXiv [stat.MLJ. 14 March 2017. URLL/Ettpe//aaxii.co//aaa//////
04730
Sachin Kumar, Vidhisha Balachandran, Lucille Njoo, Antonios Anastasopoulos, and Yulia Tsvetkov. Language Generation Models Can Cause Harm: So What Can We Do About It? An Actionable Survey. In Proceedings of the 17th Conference of the European Chapter of the Association for Computational Linguistics, pp. 3299 3321, Stroudsburg, PA, USA, 2023. Association for Com- putational Linguistics. URL
http:://ww..aattooooooooo/////// eacl main... 2411.
idff
Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: LLVM-based Python JIT compiler. In Proceedings the Second Workshop on the LLVM Compiler Infrastructure in HPC, LLVM 15, New York, NY, USA. 2015. Association for Computing Machinery. ISBN 9781450340052. doi:
10.1145/2833157 2833116..
URL WtRLhttps://dda org/10...1oo0 1 /111/1133111111 2833163
B Langmead, C Trappell, M Pop, and Salzberg. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol, 10:R25, 2009. doi: 10.1186/ 10-2009-10-3--25.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin. Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-Tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. SetrieallAuugmented Generation for Knowledge Intensive NLP Tasks. arXiv [cs.CL), 22 May 2020.
11401
Haoran Li, Dadi Guo, Wei Fan, Mingshi Xu, Jie Huang. Fanpu Meng, and Yangqiu Song. Multi- step Jailbreaking Privacy Attacks on ChatGPT. In Findings of the Association for Compu- tational Linguistics: EMNLP 2023, pp. 4138 4153, Stroudsburg, PA,, USA, December 2023. Association for Computational Linguistics. URL htttps://aeLantiooooyyyoooo org.2202...../22......
findi ngs-emmn 1.222.
17

---

Published as a conference paper at ICLR 2025
Jiacheng Liu, Sewon Min, Luke Zettlemoyer, Yejin Choi, and Hannanch Hajishirzi. Infini-grami Scaling Unbounded n-gram Language Models to a Trillion Tokens. arXiv [cs.CL], 30 January 2024. [RL::ttp://arxt
org/ als 2401.11377
LLM-jp. :, Akiko Aizawa, Eiji Aramaki, Bowen Chen, Fei Cheng, Hiroyuki Deguchi, Rintaro Enomoto, Kazuki Fujii, Kensuke Fukumoto, Takuya Fukushima, Namgi Han, Yuto Harada, Chikara Hashimoto, Tatsuya Hiraoka, Shohei Hisada, Sosuke Hosokawa, Lu Jie, Keisuke Ka- mata, Teruhito Kanazawa, Hiroki Kanezashi, Hiroshi Kataoka, Satoru Katsumata, Daisuke Kawa- hara, Seiya Kawano, Atsushi Keyaki, Keisuke Kiryu, Hirokazu Kiyomaru, Takashi Kodama, Takahiro Kubo, Yohei Kuga, Ryoma Kumon, Shuhei Kurita, Sadao Kurohashi, Conglong Li, Taiki Maekawa, Hiroshi Matsuda, Yusuke Miyao, Kentaro Mizuki, Sakae Mizuki, Yugo Murawaki, Ryo Nakamura, Taishi Nakamura, Kouta Nakayama. Tomoka Nakazato, Takuro Niitsuma, Jiro Nishitoba, Yusuke Oda, Hayato Ogawa, Takumi Okamoto, Naoaki Okazaki, Yohei Oseki, Shin- taro Ozaki, Koki Ryu, Rafal Rzepka, Keisuke Sakaguchi, Shota Sasaki, Satoshi Sekine, Kohei Suda, Saku Sugawara, Issa Sugiura, Hiroaki Sugiyama, Hisami Suzuki, Jun Suzuki, Toyotaro Suzumura, Kensuke Tachibana, Yu Takagi, Kyosuke Takami, Koichi Takeda, Masashi Takeshita, Masahiro Tanaka, Kenjiro Taura, Arseny Tolmachev, Nobuhiro Ueda, Zhen Wan, Shuntaro Yada, Sakiko Yahata, Yuya Yamamoto, Yusuke Yamauchi, Hitomi Yanaka, Rio Yokota, and Koichiro Yoshino. LLM-jp: A Cross-organizational Project for the Research and Development of Fully Open Japanese LLMs, 2024. URL (tLLhttps:/// /tt.iii.://aai..oo.o org/ abs 2407 03963
Nils Lukas, Ahmed Salem, Robert Sim, Shruti Tople, Lukas Wutschitz, and Santiago Zanella- Béguelin. Analyzing Leakage of Personally Identifiable Information in Language Models. In 2023 IEEE Symposium on Security and Privacy (SP). IEEE, May 2023. URL http://dx.
doi www.orrg/1.0. 110..1119//9900 wttp:////...111999921155522.2000 2023..2.22..20 2023.101733000
Yu Malkov and A. Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trwns. Puttern Anal. Mach. Intell., 42 (4):824-836, April 2020. ISSN 0162-8828. doi: 10.1109/TPAMI.001 28899777 URL https:
//doi. 10. 1109/ TTAMIMI 2018 2889473
Tony McEnery and Andrew Hardic. Corpus Linguistics: Method, Theory and Practice. Cambridge University Press, 2011.
Tony McEnery and Andrew Wilson. Corpus Linguistics. Edinburgh University Press, Edinburgh, 2001. doi: 1774778744447755..
Barbara Mcgillivray, Thierry Poibeau, and Pablo Ruiz. Digital Humanities and Natural Language Processing: "Je t'aime... Moi non plus". Digital Humanities Quarterly, 14(2), 2020. doi: 10.
17863/CAM.55816.
Kathleen R McKeown. Paraphrasing Using Given and New Information in Question-Answer System. In Proceedings of the 17th annual meeting on Association for Computational Linguistics pp. 67-72, Morristown, NJ, USA, 1979. Association for Computational Linguisties. URL http::///eelannttoooooooorr/////
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient Estimation of Word Rep-
resentations in Vector Space. arXiv (Cs, 16 January 2013. URL http://arxiv.
abs/1301.3781
D. Lee Miller. Wordllama: Recycled token embeddings from large language models, 2024. URL https::/githhb.cco
www./leerrrerr weaer//orrlll. aama
Niklas Muennighoff, Nouamane Tazi, Loic Magne, and Nils Reimers. MTEB: Massive text em- bedding benchmark. Andreas Vlachos and Isabelle Augenstein (eds.), Proceedings of the 17th
Conference of the European Chapter of the Association for Computational Linguistics, pp. 2014- 2037, Dubrovnik, Croatia, May 2023. Association for Computational Linguistics. doi: 10. 18653/ v1/2023.eacl-main
/ org 2023. w.w....clmm..
148/
Gonzalo Navarro. A Guided Tour to Approximate String Matching, ACM Comput. Sure, 33(1):
31-88, 2001.
18

---

Published as a conference paper at ICLR 2025
OpenAL.
Introducing OpenAl ol. https://openas www.coo///////o indd//
int
12 September 2024. Accessed: 2024-10-1.
Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Alessandro Moschitti, Bo Pang, and Walter Daelemans (eds.), Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 1532-1543, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10. 3115/v1/D14-1162.
Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating Training Data Influence by Tracing Gradient Descent. Advances in Neural Information Processing Systems, 33:19920 19930, 2020. URL
www.renrrr.... cw/paper.pppp...ccee files/ [0apr//000/111113333333355555222
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language Models are Unsupervised Multitask Learners. 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the Limits of Transfer Learning with a Unified Text-to- Text Transformer. arXiv [cs. 23 October 2019. URL http:/t::/ //tp:v//aavvvvv http://rrii..orr/////199/
10683
Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, Johan Ferret, Peter Liu, Pouya Tafti, Abe Friesen, Michelle Casbon, Sahela Ramos, Ravin Kumar, Charline Le Lan, Sammy Jerome, Anton Tsitsulin, Nino Vieillard, Piotr Stanczyk, Sertan Girgin, Nikola Momchev, Matt Hoffmann Shantanu Thakoor, Jean-Bastien Grill, Behnam Neyshabur, Olivier Bachem, Alanna Walton, Aliaksei Severyn, Alicia Parrish, Aliya Ahmad, Allen Hutchison, Alvin Abdagic, Amanda Carl, Amy Shen, Andy Brock, Andy Coenen, Anthony Laforge, Antonia Paterson, Ben Bastian, Bilal Piot, Bo Wu, Brandon Royal, Charlie Chen, Chintu Kumar, Chris Perry, Chris Welty, Christopher A Choquette- Choo, Danila Sinopalnikov, David Weinberger, Dimple Vijayku- mar, Dominika Rogozińska, Dustin Herbison, Elisa Bandy, Emma Wang, Eric Noland, Brica Moreira, Evan Senter, Evgenii Eltyshev, Francesco Visin, Gabriel Rasskin, Gary Wei, Glenn Cameron, Gus Martins, Hadi Hashemi, Hanna Klimczak-Pluciisee Ivan Nardini, Jacinda Mein, Jack Zhou, James Svensson, Jeff Stanway, Jetha Chan, Jin Peng Zhou, Joana Carrasqueira, Joana Iljazi, Jocelyn Becker, Joe Fernandez, Joost van Amersfoort, Josh Gordon, Josh Lipschultz, Josh Newlan, Yeong Ji, Kareem Mohamed, Kartikeya Badola, Kat Black, Katie Millican, Keelin McDonell, Kelvin Nguyen. Kiranbir Sodhia, Kish Greene, Lars Lowe Sjoesund, Lauren Usui, Laurent Sifre, Lena Heuermann, Leticia Lago, Lilly Mc- Nealus, Livio Baldini Soares, Logan Kilpatrick, Lucas Dixon, Luciano Martins, Machel Reid, Manvinder Singh, Mark Iverson, Martin Görner, Mat Velloso, Mateo Wirth, Matt Davidow, Matt Miller, Matthew Rahtz, Matthew Watson, Meg Risdal, Mehran Kazemi, Michael Moyni- han, Ming Zhang, Minsuk Kahng, Minwoo Park, Mofi Rahman, Mohit Khatwani, Natalie Dao, Nenshad Bardoliwalla, Nesh Devanathan, Neta Dumai, Nilay Chauhan, Oscar Wahltinez, Pankil Botarda, Parker Barnes, Paul Barham, Paul Michel, Pengchong Jin, Petko Georgiev, Phil Culli- ton, Pradeep Kuppala, Ramona Comaneseu, Ramona Merhej, Reena Jana, Reza Ardeshir Rokni, Rishabh Agarwal, Ryan Mullins, Samaneh Saadat, Sara Mc Carthy, Sarah Perrin, Sébastien M R Arnold, Sebastian Krause, Shengyang Dai, Shruti Garg, Shruti Sheth, Sue Ronstrom, Susan Chan, Timothy Jordan, Ting Yu, Tom Eceles, Tom Hennigan, Tomas Kocisky, Tulsee Doshi, Vihan Jain, Vikas Yadav, Vilobh Meshram, Vishal Dharmadhikari, Warren Barkley, Wei Wei, Wenming Ye, Woohyun Han, Woosuk Kwon, Xiang Xu, Zhe Shen, Zhitao Gong, Zichuan Wei, Victor Cotruta, Phoebe Kirk, Anand Rao, Minh Giang, Ludovic Peran, Tris Warkentin, Eli Collins, Joelle Barral, Zoubin Ghahramani, Raia Hadsell, D Sculley, Jeanine Banks, Anca Dragan, Slav Petrov, Oriol Vinyals, Jeff Dean, Demis Hassabis, Koray Kavukcuoglu, Clement Farabet, Elena Buchatskaya, Sebastian Borgeaud, Noah Fiedel, Armand Joulin, Kathleen Kenealy, Robert Dadashi, and Alek Andreev. Gemma 2: Improving Open Language Models at Practical Size. arXiv Mcs.CLJ,33 31 July 2024. URL htLLttp://// http:://aaxvvvvii.
Harlcen Batra, Harsh Dhand,
Kirk Roberts, Tasmeer Alam, Steven Bedrick. Dina Demner-Fushmand Kyle Lo, Ian Soboroff, Ellen Voorhees, Lucy Lu Wang, and William R. Hersh. Searching for scientific evidence in pandemic:
19

---

Published as a conference paper at ICLR 2025
An overview of trec-covid, J. of Biomedical Informatics, 121(C), September 2021. ISSN 1532- 0464. doi: 10.10161,,b22201110366.. Cttphttps:/ htttpps//ddi..oxg100.00000 jai. 2021. 103865
Stephen Robertson and Hugo Zaragoza. The probabilistic relevance framework: Bm25 and beyond. Found. Trends Inf. Retr. 3(4):333-389, April 2009. ISSN 1554-0669, doi: 10.150//1500000011
URL https: doi org/ 11t.11..11111100001111
Marek Rogozinski and Rafal Kuc. Elasticsearch Server, 3rd edition. Packt Publishing, 2016.
Timo Schick, Sahana Udupa, and Hinrich Schütze. Self-Diagnosis and Self- Self-Debiasing: A Proposal for Reducing Corpus-Based Bias in NLP. Trans. Assoc. Comput. Linguist., 9:1408-1424, 17 De- cember 2021. URL https:: http:////caaatthoooooooooooo wwtpooooooooooogoo.ooo//// tacl 1..4..88.....
Sarah Schulz. The Taming of the Shrew: Non-Standard Text Processing in the Digital Humanities. PhD thesis, University of Stuttgart, 2018.
Martin Schweinberger. Concordancing with R. https://ladal.edu. www.wii....u.ccc........aaaaa .html 2024.
Satoshi Sekine. Linguistic Knowledge Discovery Tool: Very Large Ngram Database Search with
Arbitrary Wildcards. In Coling 2008: Companion volume: Demonstrations, pp. 181-184, 2008.
URL
www.lllggyroggoooeee org/c08-3010. pdf
Satoshi Sekine and Kapil Dalwani. Ngram Search Engine with Patterns Combining Token, POS, Chunk and NE Information. In Proceedings of the Seventh International Conference on Lan-
guage Resources and Evaluation (LREC' 2010. URL http: / /ww. 1rec conf.org
pxcceeiings//ree20100/ httpapaaaisaappppppPPeee
Frank Smadja. Retrieving Collocations from Text: Xtract, 1993.
URL https://
aclanthology. wwtp/o/-////.......
Nishant Subramani, Sasha Luccioni, Jesse Dodge, and Margaret Mitchell. Detecting Personal In- formation in Training Corpora: an Analysis. In Proceedings of the 3rd Workshop Trustwor- thy Natural Language Processing (TrustNLP 2023), pp. 208 220, Stroudsburg, PA, USA, 2023. Association for Computational Linguistics. URL https: httts::/ http://///aaaaathloasaes wwgp://oooorr//222.....
trustnl p- 1. 18.1884 1d. pdf.
TEI Consortium. TEI P5: Guidelines for electronic text encoding and interchange, 2023. URL https:// /www. tei- wtt..ee.o..ooooieeeeeiieeeeeeeee
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Maric-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang. Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open Foundation and Fine- Tuned Chat Models. arXiv /cs. CLJ, 18 July 2023. URL BRRLttp::// httt:://aaxii.. wttpiviivvv..////////..///a..ava org/ abs/ /20/s/230..2m2 09288
Janneke Van Der Zwaan, Wouter Smink, Anneke Sools, Gerben Westerhof, Bernard Veldkamp. and Sytske Wiegersma. Flexible NLP Pipelines for Digital Humanities Research. In 4th Digital Humanities Benelux Conference, Utrecht, Netherlands, 2017.
Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Ma- Contrastive Pre-training, 2024a.
jumder, and Furu Wei. Text Embeddings by URL htllhttts::/ / www./rgg///aa.... ablla/ss/222222 03533
20

---

Published as a conference paper at ICLR 2025
Liang Wang, Nan Yang, Xiaolong Huang, Linjun Yang. Rangan Majumder, and Furu Wei. Mul- tilingual e5 text embeddings: A technical report, 2024b. URL https:// org/ abs/ 2202.05672
Yuxia Wang, Revanth Gangi Reddy, Zain Muhammad Mujahid, Arnav Arora, Aleksandr Ruba- shevskii, Jiahui Geng, Osama Mohammed Afzal, Liangming Pan, Nadav Borenstein, Aditya Pil- lai, Isabelle Augenstein, Iryna Gurevych, and Preslav Nakov. Factcheck-bench: Fine- grained evaluation benchmark for automatic fact-checkers, 2024c. URL
/bs/
231 09000
Wikipedia. Wikipedia statistics, 2024. URL https://en..kkieeiiaaa
w wiki /Wik witiikkieddaaaai. htt./ollliiiinuuaalaaaoa
Sam Witteveen and Martin Andrews. Paraphrasing with Large Language Models. In Pro-
ceedings of the 3rd Workshop on Neural Generation and Translation, pp. 215-220, Strouds-
burg. PA. USA. November 2019. Association for Computational Linguistics. URL hetps:
//aclanthole o
pdd
Sun Wu and Udi Manber. Fast Text Searching Allowing Errors, Commun. ACM, 35(10):83- 91, 1992a. doi: 10.1 10.1449433529.1132444 URL ottptt/s//....../111...11. 111g//00.145/13539. 135244
Sun Wu and Udi Manber. Agrep Fast Approximate Pattern-Matching Tool. In 1992 Winter USENIX Conference, 1992b.
Mikio Yamamoto and Kenneth W Church. Using Suffix Arrays to Compute Term Frequency and Document Frequency for All Substrings in Corpus. Comput. Linguist, Assoc. Comput. Linguist., 27(1):1-30, March 2001.
org/
Yukun Zhu, Ryan Kiros, Richard Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Tor- ralba, and Sanja Fidler. Aligning Books and Movies: Towards Story-like Visual Explana- tions by Watching Movies and Reading Books. arXiv [cs.CV], 22 June 2015. URL http:
//axxiv..rrgbbb//5556..
George Kingsley Zipf. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Am. J. Psychol., 64(1):149, Januuryy 1951. URL http::/dx....../// doi. orw.orgg///..
1418618
Justin Zobel and Alistair Moffat. Inverted Files for Text Search Engines, ACM Comput. Surv. 38(2): 6, 2006, doi: 00.1145/1132956 112959. URL
1132959
A OTHER EXAMPLES OF SOFT MATCHES IN LATIN
Table 5 shows several additional examples of Latin soft matches SoftMatcha.
B LIST OF GLOSSING ABBREVIATIONS
Table lists the glossing abbreviations used in this paper.
C WEB INTERFACE
Figures shows screenshots of our demo tool.
21

---

Published as a conference paper at ICLR 2025
Table 5: Additional examples of soft matches Latin and their scores returned by SoftMat cha. The top row of an interlinear gloss represents words (and the cosine similarity between the word and its corresponding query word), the middle row their morphological analysis, and the bottom row the free translation. Morphological matches are highlighted in pink, semantic matches in blue, and exact matches green.
Query
Query
non
potest
bellum
gallicum
war.N-NOM.S
gallic-N.NOM.SC
Che/shefit cannot'
'the Gallic war'
Matches
Matches
1.00
0,59
1.00
0.44
non
possit
bellum
etruscum
Can.SUB.PRS.B35
war N-OO..G
Etruscan-N.NOM.C
hheshe/it cannot'
'the Eiruscan war"
0.49
0.45
nec
posse
contra
Caesarem
nor
Can.INE.PRS
against
Caesar.M-ACC.SC
not to be able'
"against Caesar'
Query
Query
homo
sapiens
quo where 'where do you go
vadis
Muuman.M.NOM.S..
Wisc.M.NOM.SG
go.ID..PSS
a wise human"
Matches
Matches
0.39
0.42
1.00
homo
honestus
ihi
vadis
hurann NOM.SG
noble-M.NOM.S.
go.IND.PRS.250
an honorable human"
you go there'
0.47
0.40
0.48
vir
sincerus
autem but
vocaris
man.M. NOM.SG
pure-M.NOM.SG
summon-
a pure man"
'btt you summoned"
Query
Query
10
post
meridiem
quod which erat
demonstrandum
after
DOOn.M.ACC.SG
IND.IMPP.33C BHOW.GER-N.NONE
after noon'
'which was be shown'
Matches
Matches
0.68
1.00
ante
meridiem
haee erat
forma
before
ACC..S
This.F.NOM.SC. Dc.JIN.IMPP..3. Form.F.NOM.SE
"before noon'
'this was the form'
0.51
0.52
1.00
0.54
0.47
contra
septentrionem Ursa.Major.F.oo A.C..S. "against Ursa Major', i.e., facing north'
quod which 'which we shall accept later'
postea
accipiamus
against
afterwards
acCepLACT.SSUE IPL
22

---

Published as a conference paper at ICLR 2025
Table List of the gloss abbreviations used in this paper.
Gloss
Meaning
2,
1st, 2nd, 3rd person, respectively accusative
ACC
ACT
active voice
F
feminine (gender)
FUT
future
GER
gerundive
IMPF
imperfective
IND
indicative mood
M
masculinie (gender)
neuter (gender)
NOM
nominative case
passive voice
PF
perfective
PL
plural
PRS
present tense
PTCP
participle
SG
singular
SUB
subjunctive mood
March 1, 2016
Search
SoftMatcha
arkhott00 wawwewwk--ggwood---0
Thresnokd, 0.5
Examples
theorem
2215
Jonn
facttur
eiquude
bellurr
Results
Time:
2016 Fey produced television Unbreskabie bok Kimmy Schmiet fellow 20Roct-alumra Robert abon etore Fae wiformer covetar June krwezwek) aewell Thus Burgese who had previcurcy y appeared in 30 upliodees land care Kans. Alhoough it nas raily protuced reSc, vas avertually munuually sold to hutfili and immeed staly show pewnlired March 2015 critccl aczivin.
On Juy 18 2015, the series sone nom nominnted for seven Piimeime Emmmy Acands incluting Dutebending Cormedy See wes. tersel nemiattd sotn the creatar suecutive producer the and Outstandinn Guest actross
2016, was amooreee Foy would ramator the Disney Neture fllmt Morkey fingdom, which woor ollasod cherecters, and recelwed pou
cerrolee Fay stamed beograshical comeedy-
Fovtrot st, based on the memok The Talbonn Shuffle Strongs Doys Aighanistann and Pakistan, to pook nov leww.
comp letedion November
bonus disc was momade
lehovar
materta from the main aloum os as songs from Choel the unndeasee compl atton leftower tracks Shoet
Origin in 2012 Toamsend stated that the thbaattmn attwan will he the sieth the and whum in tewin Towneerd Project serves uttimatall coniimmed trat Can.atiee Gool of
Towraend started croseti inding
PedgeMusic wewe put directly Trwensedd upooming projects. Conuaitee
funding quilkyy reeerred on May
goal, addiionaaall funds
The alturn
Figure 3: The screenshot of demo. Given the query "March 1, 2016", returns lines including softly-matched matched patterns such as "July 16, 2015."
D EFFECTS OF VARYING THRESHOLDS ON SEARCH TIME AND RESULTS
We inspected the relationship between the value of search time, and the number of matched entries for the query "homemade bomb". We varied the threshold parameter, i.c., from
"p.m.
book Caesar 1882
"Bible, John 13:36
O.F.D.
23

---

Published as a conference paper at ICLR 2025
SoftMatcha
wikksst00 (C:18) glove wik pigaword 800
Thres 0.5
Examples
bollm Oalliuu
Results
Hits
Search Time:: 0.182
stright penal BC, than rectangle BCLK tw the area triangle AB2 decause they share paee 01 andhave the came aituu DC. Le, the normal to ther commen tavss connecting the paral tree ID and Al. <
Surface diftus in kinetic can be thought ner ms of adatomsres ding adsorptionn en lattie,, moving between nocrest neighbor
characterieed athemmsynamic fetter okeates probsiility itterpe resuttigg successt tume. otternet frequency ia top cally lavan simply vibrational freeuancy the adatom, with thammdynamic fuctor as Bottoman factor dop ondont on temparature and Editf, the potential energe banfer diftusion. Equation desel bas the relodonsnip:
lumping
frequency
Where and Edif are as descr bed above, the jump of hopping rite. Tis tempentture, and -B the Boitamann constait. Edift must onglter tran the energy of sesorption for dittution to soour, otherwise desorption processes wourd dom mate valios
equatiion te's
The
diffusion takks
place is dependent thermoddmamt factor spproaches un Edit cennesto to mwsninghu baader to duudoonn This case. enown mobile dirtusion is relutiely uncommon and has only boon abserved a fow systems. Forthe phenomena described throug hout this ankile T.S. assumeed that Edit KST therffoee Txx ev, the casa Fickan dffisiinn kis possibble to extract both from Artherkus ot logarthin difludan coeffiiient. below 1, may the dffiee processes would change with temperature
rolatonshio between
given themoodeamii: factor; Editf
T. where than
Figure 4: The screenshot of our demo Given the query "Theorem 1", it returns lines including softly- matthed patterns such "lemma 2."
John was born
Search
SoftMatcha
wkkeett03 (.1BII give-------ggreooodooo
Thresnoks: 0.51
Examples
thoorem
march 2016
Jo wos borninn
2:800 shatrt
foctus est
equus
bell.m Gatliium
Results
Search Time: sec
John
Brfenne, and Montiuucon.
axceoding old
10-year-eld
Alcopalllss
correct
inweeer no other 12th-oentury authore deser bed John as an man hetter reterred John brothers
1177 and mentimee the tuter ol Jahn is brogher Welttr 1150 thacee sageets that Jonn brothers zeee bom John
1160e, Modern Notor
after probably during the 1170s.
1957 Goffmen marred Chaste iin 1953, their snn Thomes sest boin Angelics suffered from mental Insenand commiteddi..ee 1986. Outee woxteeiic Goffrren attrographic
for tie rnter and re
gambiing
Vegas casino..
signol Edward righro for aecond cousins the trouug great-granetaate hhery prectically cowvall salward pom 13321, to assuma that strong sarce of camara durie existed betwoan them Another factor thutinght rightt have uenced the king docision was the foot that Honry hadi no male heir. so the grant was mode for the Earl is Inttin only. and not intended to be hereeharr..
he would such arld eggs on
1883, Leno met Sarsh Lydla Reynolds I 1866 - 19421 i young dancer and comedy sngger from Bim righomn white both were soocaring atring Oftyy 's Circus of Harketes, Rochddale e. The daughter of stage corpenter Lydia, she known arofesstarally
piahipiihiddd that she" played very young artitte
performanc Birbod Sallor knhwn thestre whthiroper traiiing
Figure 5: The screenshot of our demo. Given the query "John was born in," returns lines including softly- matched patterns such as "Edward was born in."
(0.1,0.2. ... 1.0). in the English Wikipedia search. The search time and the number of matched entries for each a are shown in Table 7 As you can see, both the search time and the number of matched entries vary significantly depending on the threshold. The results of a < 0.2 are note- worthy. From the result, we can observe that the search time of the tool is too long to be used for real-time use if the alpha is set below 0.2. However, we remark that the threshold as low 0.2 is not
24

---

Published as a conference paper at ICLR 2025
Table 7: The search time (seconds) and the number of matched entries for each a.
seconds
# of hits
0.1
1213.503
504,955,515
0.2
55.854
19,899, 1,99,652
0.3
1.105
183,202
0.4
0,258
34,766
0.5
0.079
1,839
0.6
0,025
381
0.7
0.028
259
0.8
0.027
259
0.9
0.028
107
1.0
0.005
107
chosen in practice since the search result includes too many nonsensical phrases. For example, the results for a 0.2 included "mixing test" and "authentic scale", which are not related the query.
E
ADDITIONAL DISCUSSIONS
E.1 OUT-OF-VOCABULARY PROBLEM
Our current implementation does not handle out-of-vocabulary (OOV) words; it ignores unknown words. Handling OOV words appropriately is deferred to future work. We plan to (1) use fasttext to fallback unknown words character embeddings and (2) extend our algorithm handle subword units to deal with the OOV problem.
E.2 STATIC EMBEDDINGS VS. DYNAMIC EMBEDDINGS
used static embeddings for all experiments, but dynamic embeddings could also used.
The simple one is to use the embedding layer of contextualized models such as BERT (Devlin et al., 2019b), taking an approach like WordLlama (Miller (024).. We conducted a follow-up experiment using the embedding layer of "ERT" for the search in the English Wikipedia with threshold with the embedding layer of BERT newly
of a = 0.6. From the experiment, our SoftMatch retrieved "makeshift bomb" and "improvised bomb" etc. with query of "homemade bombs". It took less than one second, just as fast as when using the GloVe embedding. These new matches may seem bit counterintuitive, but they suggest that we can possibly obtain deep semantic matches using more dynamic embeddings.
The other more radical one is actually contextualized token embeddings instead of mere words for the search keys. Although the contextualized embeddings can be arbitrary real vectors and are not suitable for indexing as is, can approximate them finite number of embeddings by vector quantization or other methods to apply our algorithm. The context information of the query can be strengthened by adding some extra phrases before and after the query.
E.3 OMISSION, INSERTION, AND SWAPPING
The current SoftMatcha does treat word omission and insertion, e.g., "the jazz musician" does not match "a fantastic jazz musician". That said, omission and insertion could be handled by modifying Step 2-2 (technically, how to take intersections in line 9 Algorithm T} using wildcards. Wildcards can skip matching at any position, and is easy to implement by just adjusting the shift width of Step 2-2 in Algorithh IJ This extension allows us represent various similar patterns with single simple query.
In addition, it possible to extend the algorithm allow the flexible order of words in the query by considering every permutation of the query pattern. This can be quite efficient, because only Step
googl e-bert/bert. http///eettbseecccaaae base-uncased
25

---

Published as a conference paper at ICLR 2025
Table 8: The results of the information retrieval task on the TREC-COVID dataset.
Method
P@20 20
R 1000
NDCG@20
BM25
22.2 41.5
39.5
34.6
Soft-BM25 (a: = 0.55)
23.5
36.3
2-2 (Find the soft matches) needs to be repeated and typically the pattern length not too large (technically, dynamic programming be used here to achieve even better performance).
F EFFECTIVENESS OF SOF IMATCHA IN THE INFORMATION TASK
We conducted experiments to apply method to information retrieval.
Soft-BM25
The well-known and strong baseline, BM25 (Robertson Zaragozal 2009). calculates relevance scores between query and document using term frequency (TF) and inverse document frequency (IDF), which involve counting occurrences words or n-grams.
We implemented soft version of BM25 (soft-BM25). For calculating the soft term frequency in a document, we compute the pattern-level score by multiplying the matching scores of each word in query pattern, and then sum up for each pattern occurrence. Similarly, soft inverse document frequency is calculated by counting documents that softly contain the given query patterns. Then, we calculated the soft-BM25 score based on the most standard Lucene implementation.
To examine the effectiveness of soft matching on the information retrieval task, we compared the threshold parameter a between 1.0 and 0.55. a 1.0 means "not performing any semantic relax- ation",, making it equivalent to standard BM25. In contrast, a = 0.55 allows for semantic relaxation of query pattern counting using our method, serving as a means to verify the effectiveness of the proposed method in information retrieval.
Benchmark dataset We used TREC-COVID dataset (Roberts et al. 2021). which part of Massive Text Embedding Benchmark (MTEB) (Muennighoff et al. (023). This dataset consists of 171k documents and 50 queries (= instances). Notably, the original dataset comprised only queries formatted natural language questions that are not suitable for queries of BM25 and soft-BM25; thus, we prepared the pattern queries for this experiment. Specifically, we manually transformed the natural language question, e.g., "how does the coronavirus respond to changes in the weather" the queries for BM25 and soft-BM25, c.g., ["coronavirus", 'response to weather", "weather change", "coronavirus response to weather changes"].
Evaluation metries We evaluated the retrieval performance on the precision @ 20 (P@20) call@ 1000 (R 1000), NDCG@20 following the previous work (Bendersky et al. 2020).
Results The experimental results are demonstrated in Table 8 The table shows that soft matching achieved better performance compared with exact matching in the information retrieval task.
To summarize this experiment, confirmed that our So faa cha is effective not only in full-text search but also in the information retrieval task, which ranks relevant texts.
26


Reviews:
[{"review_id": "bsAJrQF7ed", "reviewer": "Reviewer_9DuR", "summary": "Paper addresses the problem of soft (or semantic) pattern matching over a billion-scale text corpora. Exact matching is often too stringent; on the other hand, naive semantic matching based on computing similarities between word embeddings is much slower, since it requires a lot of floating point operations with high-dimensional vectors instead of fast bitwise comparisons. \n\nAuthors leverage inverted indexes data structure to reduce the amount of required soft matches, and propose an algorithm which requires only a constant amount of soft matches with respect to corpura size. They also conduct two case studies: testing the speed of the proposed implementation on a billion-scale search, and retrieving patterns from a morphologically complex language (Latin). Finally, they provide a demo to interact with the proposed algorithm.", "questions": "Major:\n- There are some questions in Weaknesses section.\n- How the sample search results were selected for Table 3?\n\nMinor:\n- How to choose alpha?\n- How much more search results does SoftMatcha retrieve depending on alpha?\n    - How many of additional entries are irrelevant?\n    - How to rank additional entries found by Softmatcha?\n- For potential future work: is it possible to modify the algorithm to allow flexible order of words in the query, or matching with some words omitted / inserted (e.g. finding “a fantastic jazz musician” by a query “the jazz musician”)? Fixed word order is still quite restrictive, especially for queries containing many words.\n\nSuggestions:\n\n- In footnote 5, page 8 information about Japanese as fifth language in Wikipedia by total amount of articles is outdated — Japanese is now 17th, while Chinese is 10th with almost twice as many total articles. Source: https://wikistats.wmcloud.org/display.php?t=wp. I propose to update the footnote.\n- Lines 099-100: “0.1 seconds … without GPU” — I’d propose to add hardware specifications used for speed evaluations (156 cores and 226 Gib of main memory), to make the claim more concrete.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "- Paper is very clearly written and easy to follow.\n\n- Main algorithm is simple and straightforward Notably, it requires a constant amount of costly soft word comparisons (which can be ~1000 longer compared to hard comparisons) with respect to corpus size Meanwhile, it still allows for much more flexible matching.\n\n- Provided demo works.", "weaknesses": "1. Description of dense vector search lacks details.\n- e.g. in Line 415, what is a “training instance” — a sentence? A paragraph?\n- How the training instances and queries were formatted for the model? Does it follow the description at https://huggingface.co/intfloat/multilingual-e5-large?\n- What was the maximal length of training instances encoded by the model?\nIf maximal length of a training instance is too long for the model, was it truncated or split into chunks?\n- How token embeddings were pooled in a single chunks-level score?\n- What were the HNSW hyperparameters?\n\n2. Table 2 lacks details.\n- How many search queries were done (e.g. 1, 100, 1000)?\n- How long the queries were (e.g. <20 words)?\n- What are the variation in search time (standard deviation of search time over multiple queries, maximal / minimal search time for a single query)?\n\n3. Approximate string matching baselines were not included (e.g. agrep (Wu & Manber, 1992b;a) or TRE (https://en.wikipedia.org/wiki/TRE_(computing))). While unlike SoftMatcha they can not e.g. find synonyms, they are still useful for finding matches with typos / inflected word forms (which e.g. was part of the goal in “Section 4.3 Case study in computational linguistics — retrieving Latin examples), and it is interesting to compare search speed.\n- In Section 2.3 String Matching, lines 200-202 you state that approximate string matching is orthogonal to your work as it focuses on surface-level comparison, while you target semantic-level similarity.\nHowever, in Introduction, lines 076-080 you mention that “...it is often desirable to catch non-standard spellings as well, such as how r u instead of how are you … Additionally, it is desirable to catch different inflected word forms such as sing, sang, sung, signs and singing, which differ only in their morphological features and share the same lemma (base form).”\n\nOne big difficulty with assigning an overall score is the fact, that there are basically no metrics in the paper, except for running time. \nFor approximate/fuzzy pattern matching algorithms it is interesting to estimate how relevant are the search results, using ranking metrics like mean average precision, or NDCG. However, these require a labeled dataset, which is hard to obtain.\n\nOn a qualitative level, this algorithm looks like a noticeable improvement over exact matching, and it might have some benefits compared to dense vector search (e.g. 100% recall in cases where the query exactly matches the pattern, higher speed, simpler implementation). Nonetheless, with more search results there arises a need to rank them. Considering Figure 3: while in some cases the ability to match “July 16, 2015” by the query “March 1, 2016” is useful, in others this might be a completely irrelevant search result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3kEU5UNDJh", "reviewer": "Reviewer_Y3Li", "summary": "This paper presents an efficient method for pattern matching over billion-token corpus by combining soft matching via word embeddings and inverted indexes. The method is compared to exact matching and dense vector search as baselines over wikipedia corpora in English and Japanese. They show that the running time of the proposed algorithm is on par with the exact matching but much faster than dense vector search. Through qualitative case analysis, they also show that the algorithm returns relevant results and can be more robust than the other baselines.", "questions": "n/a", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithm proposed is straightforward and effective, and it can be quite helpful for quickly locating relevant texts in massive pretraining data. The paper is also well-written and structured clearly, especially the demo interface.", "weaknesses": "The empirical evaluation can be further strengthened. It would be helpful to include analysis that shows 1) how the threshold influences speed and the relevance of the retrieved results. 2) a tradeoff analysis between the efficiency and the qualitative analysis. Table 3 seems to show that SoftMatcha retrieve relevant and robust texts fast. However I wonder if the observed relevancy can be quantified with a information retrieval corpora so that we can understand its relevant performance compared to the baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rhmsNr2Kq7", "reviewer": "Reviewer_4JZq", "summary": "This paper introduces a pattern-matching algorithm designed to efficiently handle semantic matching across vast text corpora, addressing the limitations of existing methods that struggle with language variations like orthographic diversity and paraphrasing. Unlike conventional string-based approaches, which lack flexibility, the proposed algorithm leverages word embeddings and inverted indexing to perform \"soft\" matching, enabling it to find meaningfully related phrases without relying on exact string matches. The algorithm operates at a speed comparable to traditional methods, achieving search times of under a second on billion-word corpora. It proves effective in practical applications: identifying harmful content in large English and Japanese datasets, and retrieving linguistically relevant examples in Latin, where morphological variations are common. SoftMatcha, the resulting tool, is accessible via a web interface, making it practical for users in NLP and digital humanities.", "questions": "Since the algorithm operates solely on the vocabulary present in the corpus, there is limited discussion on its approach to out-of-vocabulary (OOV) items. This omission raises questions about how the system performs when faced with rare or unseen words and could impact its scalability across languages and domains with rich vocabularies or evolving terminologies.\n\nSo my question is: how the matching algorithm deals with OOV words? For instance, if \"John\" is not in the vocabulary, does it means I can't search for phrases containing \"John\"?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The algorithm is optimized for billion-scale corpora, achieving search speeds that are comparable to traditional tools but with a much richer, semantic matching capability. This scalability and speed are significant achievements, especially for applications involving extensive datasets like web-scale corpora.\n\nThe paper is well explained and the demo is functional and can be accessed easily. The examples in different languages give a good overview of the applicability potential of the algorithm.", "weaknesses": "An important limitation is the reliance on static embeddings, such as GloVe, which have largely been superseded by contextual embeddings in modern NLP applications. The continued use of GloVe and similar embeddings raises questions about the model's ability to capture context-dependent semantics, which are crucial in diverse language patterns and semantic matching tasks. The paper's illustrative example, where semantically \"opposite\" concepts (e.g., \"lived\" vs. \"died\") are matched, does not illustrate, in my opinion, the advantage of using this soft matching but instead it highlights a potential issue, which derives from the use of \"classic\" embeddings. \"live\" and \"die\" are used in similar contexts, which yields a high similarity according to the embedding spaces of word2vec or GloVe, but they are opposite semantically.\n\nI also think that while the paper contains notable technical contributions, the primary focus on linguistic applications, corpus search, and retrieval, with an emphasis on efficiency, suggests that it may align more closely with the interests of venues like ACL rather than ICLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)