SoftMatcha: A Soft and Fast Pattern Matcher for Billion-Scale Corpus Searches

We appreciate your detailed comments and suggestions. We will consider them carefully and update our revised version of the paper. Let us address your concerns in the following.

---

Static embeddings vs. Dynamic embeddings

We appreciate your valuable comments. Inspired by your comment, we discovered that we can also apply our algorithm to contextualized embeddings with a slight modification described as follows, reported with our preliminary experimental results. The detailed and thorough experimental results will be included in the revised version.

The simple one is to use the embedding layer of contextualized models such as BERT, taking an approach like WordLlama ( https://github.com/dleemiller/WordLlama ). We conducted a follow-up experiment using the embedding layer of BERT (bert-base-uncased) for the search in the English Wikipedia (threshold = 0.6). From the experiment, our SoftMatcha with the embedding layer of BERT newly retrieved “makeshift bomb” and “improvised bomb” etc. with a query of “homemade bombs” (taking less than one second, just as fast as when using the GloVe embedding). These new matches may seem a bit counterintuitive, but they suggest that we can possibly obtain deep semantic matches using more dynamic embeddings.

The other more radical one is to actually use 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, we can approximate them to a 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.

We would like to emphasize that our proposed algorithm is designed to work with any preferred embeddings, whether static or dynamic.

---

“opposite” concepts

As you note, whether to include antonyms in the search result depends on the use case. Here, we argue that including them is indeed important due to two reasons: (1) For corpus linguistics and digital humanities (Bothwell et al. 2023), which is one of the main use cases of SoftMatcha, it is useful to capture such opposite concepts in their search in use cases like parallelism detection; and (2) antonyms are indeed semantically similar to the query word in the sense that they differ in only one semantic feature: polarity. As an example of (1), an excerpt from Martin Luther King Jr.’s speech “I have a dream that one day every valley shall be exalted, every hill and mountain shall be made low…” contains a rhetoric parallelism with phrases of opposite semantics. The present feature of capturing phrases of opposite concepts is useful in detecting such parallelism.

---

Regarding the venue

Thank you for your suggestion. Although our submission is related to NLP, we believe that it aligns well with the topic “representation learning for computer vision, audio, language, and other modalities” exemplified in the CfP of ICLR 2025 (https://iclr.cc/Conferences/2025/CallForPapers).

---

Out-of-vocabulary problem

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"?

Yes, our current implementation cannot handle 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 to character embeddings and (2) extend our algorithm to handle subword units to deal with the OOV problem. We expect that these extensions are smooth since our algorithm does not assume any particular tokenizer or embedding.

We appreciate your taking the time to review this paper. We will answer your questions and comments, and also update our revised manuscript. Let us address your concerns in the following.

---

Additional empirical evaluation

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.

Thank you for your question. This question is very important since its answer directly affects the user experience of the tool. To answer your question, we quickly examined the relationship between the value of $\alpha$, search time, and the number of matched entries for the query “homemade bomb”, as shown in Table 3. We varied the threshold parameter, i.e., $\alpha$ from $\lbrace 0.1, 0.2, …, 1.0 \rbrace$, in the English Wikipedia search. The search time and the number of matched entries for each alpha were as follows:

As you can see, both the search time and the number of matched entries vary significantly depending on the threshold $\alpha$. This comparison which you suggested certainly seems valuable. We would like to include the results of these experiments in our revised manuscript.

The results of $\alpha \leq 0.2$ are noteworthy. From the result, we can observe that the search time of the tool is too long to be used for real-time use if alpha is set below 0.2. However, we remark that the threshold as low as 0.2 is not chosen in practice since the search result includes too many nonsensical phrases. For example, the results for $\alpha=0.2$ included “mixing test” and “authentic scale”, which are not related to the query. We may need to inspect the relationship between alpha and relevance of the search results and change the web interface so that one can choose alpha only from the range that produces the relevant results. We will include these discussions in the updated version.

---

Regarding information retrieval and ranking the search results

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.

Thank you for the valuable comment. It is indeed natural to recall ranking problems such as information retrieval from our setting of matching documents from a query. Other reviewers also asked about an evaluation of the information retrieval task and I understand that this is an important point to improve the clarity of our manuscript. Let us address your concern below, which will be incorporated in the revised version.

We first would like to remark that our method is intended for enumerating all matched spans, like grep in CLI environment and concordancers in corpus linguistics. However, the information retrieval tools such as Elasticsearch are intended to be used for ranking. Due to this difference, the format of the output of these two is different from each other.

That said, an extension of our method for ranking is an attractive direction. We have the following ideas for this extension. One idea is to rank entries by the match score itself, which uses the pooled match score over the pattern. A possible problem with this is that many matches can have the same rank if the same set of words appears at many positions in the text. Another idea is to rerank by other rank-based retrievers, such as BM25 or dense vector search, combiging several search methods depending on the purpose.

Experiments of the information retrieval task

Thank you for your insightful comments. From your comments “IR methods could capture relevance signals from n-gram matching or word frequencies”, we noticed that we could calculate the soft term frequency and soft inversed document frequency by softly counting the frequencies of query patterns with our method, and thus could realize the soft version of BM25 (soft-BM25).

We promptly conducted experiments to apply our method to information retrieval. Encouragingly, the experimental results demonstrate that, by relaxing this discrete counting of words or word-level n-grams with our SoftMatcha, the search accuracy of BM25 has been improved. Specifically, both recall and precision were enhanced through this approach.

We will include these experimental results in the revised manuscript.

Soft-BM25

We implemented a 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 a 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 $\alpha$ between $1.0$ and $0.55$. $\alpha=1.0$ means “not performing any semantic relaxation”, making it equivalent to standard BM25. In contrast, $\alpha=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. For this experiment, we did not tune the $\alpha$ and set it to the same value as that employed in the current manuscript.

Benchmark dataset

We used trec-covid dataset for the experiment, which is included in MTEB: Massive Text Embedding Benchmark. This dataset consists of 171k documents and 50 queries (= instances). Notably, the original dataset comprised only queries formatted as natural language questions that are not suitable for queries of BM25 and soft-BM25. Thus, we prepared the pattern queries for this experiment. For example: - Natural language question: "how does the coronavirus respond to changes in the weather" - Queries for BM25 and soft-BM25: ["coronavirus", "response to weather", “weather change”, “coronavirus response to weather changes”]

Evaluation metrics

The retrieval accuracy is evaluated on the precision@20 (P@20), recall@1000, NDCG@20 following the previous work.

Results

The table shows that soft matching achieved better performance compared with exact matching in the information retrieval task.

To summarize this experiment, we confirmed that our SoftMatcha is effective not only in full-text search but also in the information retrieval task, which ranks relevant texts.

We appreciate your detailed comments and suggestions. We will consider them carefully and reflect them in our revised version. The following is the answer to your comments.

---

Detailed descriptions of dense vector search

e.g. in Line 415, what is a “training instance” — a sentence? A paragraph?

“Training instance” there refers to a chunk of text, which could be a single sentence or multiple sentences. It means the mini-batches that were actually used in the LLM training, the chunks to be searched in our experiments.

How the training instances and queries were formatted for the model? Does it follow the description at https://huggingface.co/intfloat/multilingual-e5-large?

Yes, we followed the description of https://huggingface.co/intfloat/multilingual-e5-large; we pretended the prefix “passage: ” to each chunk of text and “query: ” to each query.

What was the maximal length of training instances encoded by the model? If maximal length of a training instance is too long for the model, was it truncated or split into chunks?

The maximal length was set to 512 tokens, which corresponds to the maximum length supported by the multilingual-e5-large tokenizer and its positional embeddings. We truncated tokens that exceed 512.

How token embeddings were pooled in a single chunks-level score?

We averaged the contextualized token embeddings following the description of https://huggingface.co/intfloat/multilingual-e5-large.

What were the HNSW hyperparameters?

We used the faiss implementation for HNSW with the number of edges set to 32. The efConstruction parameter was set to 40, while efSearch was configured as 16, which are the default parameters in the faiss implementation.

We will describe these details of settings in the revised manuscript.

---

Details of Table 2

Thank you for pointing it out. We will include the following explanation in the revised version, which will improve the reproducibility of our experiments.

How many search queries were done (e.g. 1, 100, 1000)? How long the queries were (e.g. <20 words)?

Table 3 shows the running time of a single query “homemade bomb”, consisting of two tokens.

What are the variation in search time (standard deviation of search time over multiple queries, maximal / minimal search time for a single query)?

We additionally conducted the same search ten times. For exact match search, the average search time was 0.009 seconds with a standard deviation of 0.009 seconds. Meanwhile, in our soft match search (with α = 0.55), the average search time was 0.114 seconds with a standard deviation of 0.021 seconds. Dense vector search took an average time of 0.431 seconds with a standard deviation of 0.053 seconds.

We will add these descriptions to the section of experiments.

---

Approximate string match

This is indeed an important point. Let us elaborate on the relationship between approximate string matching and our method below.

Surface-level similarity between two words (defined, for example, based on their edit distance) often works very differently from their semantic similarity; in this sense, we argue that these two similarity notions are orthogonal. For example, strings like “desert” and “dessert” (Levenshtein distance of 1) may match in approximate string matching, while our method likely ignores them given their semantic irrelevance. On the other hand, morphologically irregular forms such as “person” and “people” (Levenshtein distance of 4), only differing in plurality, will likely be missed in approximate string matching, while our methods are able to catch them. Since approximate string matching is conditioned by strings and ours by token embeddings, we can enhance our method via integration with approximate string matching. For example, our present method cannot handle the cases in which adjectives, adverbs, and prepositional phrases are inserted in the middle of a phrase, e.g., “He is actually kind” and “Tom is kind”, which edit-distance-based similarity can handle better. This observation can lead to a promising future direction of integrating our method and word-level Levenshtein distance. Thank you very much for your inspiring comment. We will add this discussion in the revised version in detail.

Regarding your suggestions

Thank you for your detailed comments to help improve our paper. We will reflect your suggestions in the revised manuscript.

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.

We appreciate your valuable information. Upon verifying the source, the source and confirmed that Japanese is now 17th, while Chinese is 10th with almost twice as many total articles. We will update our description with the latest statistics.

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.

This is also as you pointed out. We will also add the hardware specs to the introduction to clarify our claim.

Questions that you pointed out

How the sample search results were selected for Table 3?

We picked up several toxic queries that are frequently used to filter corpus for AI safety aiming at deterring terrorism. The search results in Table 3 are randomly sampled from the entire results due to page limitations. We recognize the importance of presenting diverse examples to demonstrate the importance of our tool. In the revised version, we will incorporate more examples in the appendix that are as exhaustive as we can. For example, we will include an example in which “illicit drug selling” hits for the query “illegal drug sales” in the English Wikipedia search.

How to choose alpha?

We decided on the threshold alpha subjectively after trying several values and observing the results. We plan to study the automated selection of alpha in future work.

How much more search results does SoftMatcha retrieve depending on alpha? How many of additional entries are irrelevant?

Thank you for your question. This question is very important since its answer directly affects the user experience of the tool. To answer your question, we inspected the relationship between the value of $\alpha$, search time, and the number of matched entries for the query “homemade bomb”. We varied the threshold parameter, i.e., $\alpha$ from $\lbrace 0.1, 0.2, …, 1.0 \rbrace$, in the English Wikipedia search. The search time and the number of matched entries for each $\alpha$ were as follows:

As you can see, both the search time and the number of matched entries vary significantly depending on the threshold $\alpha$. This comparison which you suggested certainly seems valuable. We would like to include the results of these experiments in our revised manuscript.

The results of $\alpha \leq 0.2$ are noteworthy. From the result, we can observe that the search time of the tool is too long to be used for real-time use if alpha is set below 0.2. However, we remark that the threshold as low as 0.2 is not chosen in practice since the search result includes too many nonsensical phrases. For example, the results for $\alpha=0.2$ included “mixing test” and “authentic scale”, which are not related to the query. We may need to inspect the relationship between alpha and relevance of the search results and change the web interface so that one can choose alpha only from the range that produces the relevant results. We will include these discussions in the updated version.

How to rank additional entries found by Softmatcha?

Our SoftMatcha is a kind of full-text search algorithm, so currently it just enumerates all the matches in order without ranking. Still, as future topics, we can consider ranking methods, such as ranking by the match score itself or by cascaded BM25 reranker.

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.

Thank you for suggesting an interesting extension. Omission and insertion can be handled by modifying Step 2-2 (technically, how to take intersections in Line 9, Algorithm 1). In particular, we plan to discuss and implement the wildcard pattern in future work or the final submission. Wildcard can skip matching at any position, and is easy to implement by just adjusting the shift width of Step 2-2 in Algorithm 1. This extension allows us to represent various similar patterns with a single simple query. Thank you for your attractive suggestion.

Flexible order can also be handled by considering every permutation of the query pattern. This can be quite efficient, because only Step 2-2 (Find the soft matches) needs to be repeated and typically the pattern length is not too large (technically, dynamic programming can be used here to achieve even better performance). We plan to discuss and implement this in future work or the final submission.

Rank of the search results

One big difficulty with assigning an overall score is the fact, that there are basically no metrics in the paper, except for running time. For 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.

Thank you for the valuable comment. It is indeed natural to recall ranking problems such as information retrieval from our setting of matching documents from a query. Let us address your concern below, which will be incorporated in the camera-ready version.

We first would like to remark that our method is intended for enumerating all matched spans, like grep in CLI environment and concordancers in corpus linguistics. However, the information retrieval tools such as Elasticsearch are intended to be used for ranking. Due to this difference, the format of the output of these two is different from each other.

That said, an extension of our method for ranking is an attractive direction. We have the following ideas for this extension. One idea is to rank entries by the match score itself, which uses the pooled match score over the pattern. A possible problem with this is that many matches can have the same rank if the same set of words appears at many positions in the text. Another idea is to rerank by other rank-based retrievers, such as BM25 or dense vector search, combiging several search methods depending on the purpose.

Experiments of the information retrieval task

Thank you for your additional explanations! We have finally understood the importance of evaluating our proposed method in the context of information retrieval task as well.

We promptly conducted experiments to apply our method to information retrieval. The well-known and strong baseline, BM25, calculates relevance scores between a query and a document using term frequency (TF) and inverse document frequency (IDF), which involve counting occurrences of words or n-grams. Encouragingly, the experimental results demonstrate that, by relaxing this discrete word or n-gram counts with our SoftMatcha, the search accuracy of BM25 has been improved. Specifically, both recall and precision were enhanced through this approach.

Again, we appreciate your valuable suggestion. We will include more comprehensive experimental results in the revised manuscript.

Soft-BM25

We implemented a 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 a 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 $\alpha$ between $1.0$ and $0.55$. $\alpha=1.0$ means “not performing any semantic relaxation”, making it equivalent to standard BM25. In contrast, $\alpha=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. For this experiment, we did not tune the $\alpha$ and set it to the same value as that employed in the current manuscript.

Benchmark dataset

We used trec-covid dataset for the experiment, which is included in MTEB: Massive Text Embedding Benchmark. This dataset consists of 171k documents and 50 queries (= instances). Notably, the original dataset comprised only queries formatted as natural language questions that are not suitable for queries of BM25 and soft-BM25. Thus, we prepared the pattern queries for this experiment. For example: - Natural language question: "how does the coronavirus respond to changes in the weather" - Queries for BM25 and soft-BM25: ["coronavirus", "response to weather", “weather change”, “coronavirus response to weather changes”]

Evaluation metrics

The retrieval accuracy is evaluated on the precision@20 (P@20), recall@1000, NDCG@20 following the previous work.

Results

The table shows that soft matching achieved better performance compared with exact matching in the information retrieval task.

To summarize this experiment, we confirmed that our SoftMatcha is effective not only in full-text search but also in the information retrieval task, which ranks relevant texts.

---

Factors that affect search speed

Thank you for your valuable feedback on the performance of our algorithm for various patterns. We would like to clarify that the time complexity of soft matching is, at most, linear in the pattern length. This implies that the execution time is unproblematic in practice since the pattern length is typically at most ~20 words. More precisely, as we explain below, the computational cost of our algorithm also depends on the number of occurrences of the words that softly match the pattern words. In our final version, we will add this theoretical complexity analysis and more extensive experiments with diverse queries to clarify this aspect. Below is a sketch of the complexity analysis. As explained in Section 3.3, the number of soft membership evaluations (i.e., line 4 of Algorithm 1) is exactly $n \times L$, where $n$ is the pattern length and $L$ is the vocabulary size. Therefore, it is linear in the pattern length. The number of the union operations (i.e., line 7 of Algorithm 1) is $\sum_{k \in \{1,\dots,n\}} |S_k|$, where $S_k$ is the set of words that softly match the $k$-th word in the pattern. Therefore, it is also linear in the pattern length. More precisely, the computational cost also depends on how many times the words in $S_k$ occur in the corpus. The number of intersection operations (i.e., line 9 of Algorithm 1) is also linear in the pattern length. Again, more precisely, the computational cost also depends on the number of the current match candidates $|M|$ and how many times the words in $S_k$ occur in the corpus.

Thank you for your reminder to encourage discussion. We have submitted author responses to each reviewer.

We are pleased to have received many constructive comments and hope to continue these fruitful discussions.