Flexible retrieval with NMSLIB and F lex N eu ART (2020)

Abstract: Our objective is to introduce to the NLP community NMSLIB, describe a new retrieval toolkit FlexNeuART, as well as their integration capabilities. NMSLIB, while being one the fastest k-NN search libraries, is quite generic and supports a variety of distance/similarity functions. Because the library relies on the distance-based structure-agnostic algorithms, it can be further extended by adding new distances. FlexNeuART is a modular, extendible and flexible toolkit for candidate generation in IR and QA applications, which supports mixing of classic and neural ranking signals. FlexNeuART can efficiently retrieve mixed dense and sparse representations (with weights learned from training data), which is achieved by extending NMSLIB. In that, other retrieval systems work with purely sparse representations (e.g., Lucene), purely dense representations (e.g., FAISS and Annoy), or only perform mixing at the re-ranking stage.

## introduction although there has been substantial progress on machine reading tasks using neural models such as bert @xcite , these approaches have practical limitations for open-domain challenges, which typically require (1) a retrieval and (2) a re-scoring/re-ranking step to restrict the number of candidate documents. otherwise, the application of state-of-the-art machine reading models to large document * work done primarily while at cmu. collections would be impractical even with recent efficiency improvements @xcite . the first retrieval stage is commonly referred to as the candidate generation (i.e., we generate candidates for re-scoring). until about 2019, the candidate generation would exclusively rely on a traditional search engine such as lucene, foot_0 which indexes occurrences of individual terms, their lemmas or stems @xcite . in that, there are several recent papers where promising results were achieved by generating dense embeddings and using a k-nn search library to retrieve them @xcite @xcite . however, these studies typically have at least one of the following flaws: (1) they compare against a weak baseline such as untuned bm25 or (2) they rely on exact k-nn search, thus, totally ignoring practical efficiencyeffectiveness and scalability trade-offs related to using k-nn search, see, e.g., §3. 3 in @xcite . flexneuart implements some of the most effective non-neural ranking signals: it produced best non-neural runs in the trec 2019 deep learning challenge @xcite and would be a good tool to verify these results. furthermore, there is evidence that when dense representations perform well, even better results may be obtained by combining them with traditional sparse-vector models @xcite @xcite . it is not straightforward to incorporate these representations into existing toolkits, but flexneuart supports dense and densesparse representations out of the box with the help of nmslib @xcite ). 2 nmslib is an efficient library for k-nn search on cpu, which supports a wide range of similarity functions and data formats. nmslib is a commonly used library foot_2 , which was recently adopted by amazon. 4 because nmslib algorithms are largely distance-agnostic, it is relatively easy to extend the library by adding new distances. in what follows we describe nmslib, flexneuart, and their integration in more detail. the code is publicly available: for sufficiently small data sets and simple similarities, e.g., l 2 , the brute-force search can be a feasible solution, especially when the data set fits into a memory of an ai accelerator. in particular, the facebook library for k-nn search faiss @xcite supports the brute-force search on gpu foot_6 . however, gpu memory is quite limited compared to the main ram. for example, the latest a100 gpu has only 40 gb of memory foot_7 while some commodity servers have 1+ tb of main ram. in addition, gpus are designed primarily for dense-vector manipulations and have poor support for sparse vectors @xcite . when data is very sparse, as in the case of traditional text indices, it is possible to efficiently retrieve data using search toolkits such as lucene. yet, for less sparse sets, more complex similarities, and large dense-vector data sets we have to resort to approximate k-nn search, which does not have accuracy guarantees. one particular efficient class of k-nn search methods relies on the construction of neighborhood graphs for data set points (see a recent survey by @xcite for a thorough description). despite initial promising results were published nearly 30 years ago @xcite , this approach has only recently become popular due to good performance of nmslib and kgraph @xcite 9 . specifically, two successive ann-benchmarks challenges @xcite were won first by our efficient implementation of the navigable small world (nsw) @xcite and then by the hierarchical navigable small world (hnsw) contributed to nmslib by @xcite . hnsw performance was particularly impressive. unlike many other libraries for k-nn search, nmslib focuses on retrieval for generic similarities. the generality is achieved by relying largely on distancebased methods: nsw @xcite , hnsw @xcite , napp @xcite , and an extension of the vp-tree @xcite . distance-based methods can only use values of the mutual data point distances, but cannot exploit the structure of the data, e.g., they have no direct access to vector elements or string characters. in addition, nmslib has a simple (no compression) implementation of a traditional inverted file, which can be used to carry out an exact maximum-inner product search on sparse vectors. graph-based retrieval algorithms have been shown to work efficiently for a variety of non-metric and non-symmetric distances @xcite @xcite . this flexibility permits adding new distances/similarities with little effort (as we do not have to change the retrieval algorithms). however, this needs to be done in c++, which is one limitation. it is desirable to have an api where c++ code could call python-implemented distances. nmslib supports only in-memory indices and with a single exception all indices are static, which is another (current) limitation of the library. there is a number of data format and distances-a combination which we call a space-supported by nmslib. a detailed description can be found online 10 . most importantly, the library supports l p distances with the norm x @xmath0, the cosine similarity, and the inner product similarity. for all of these, the data can be both fixedsize "dense" and variable-size "sparse" vectors. sparse vectors can have an unlimited number of non-zero elements and their processing is less efficient compared to dense vectors. on intel cpus the processing is speed up using special simd operations. in addition, nmslib supports the jaccard similarity, the levenshtein distance (for ascii strings), and the number of (more exotic) divergences (including the kl-divergence). the library has substantial documentation and additional information can be found online 11 . ## experiments we carry out experiments with two objectives: (1) measuring effectiveness of implemented ranking models; (2) demonstrating the value of a well-tuned traditional ir system. we use two recently released ms marco collections @xcite and a community question answering (cqa) collection yahoo answers manner @xcite . collection statistics is summarized in ms marco has a document and a passage re-ranking task where all queries can be answered using a short text snippet. there are three sets of queries in each task. in addition to one large query set with sparse judgments, there are two small evaluation yahoo answers manner has a large number of paired question-answer pairs. we include it in our experiments, because model 1 was shown to be effective for cqa data in the past @xcite @xcite . it was randomly split into the training and evaluation sets. document text is processed using spacy 2.2.3 @xcite to extract tokens and lemmas. the frequently occurred tokens and lemmas are filtered out using indri's list of stopwords @xcite , which is expanded to include a few contractions such as "n't" and "'ll". lemmas are indexed using lucene 7.6. in the case of ms marco documents, entries come in the html format. we extract html body and title (and store/index them separately). in additional to traditional tokenizers, we also use the bert tokenizer from the hug-gingface transformers library @xcite . this tokenizer can split a single word into several sub-word pieces @xcite . the stopword list is not applied to bert tokens. training model 1, which is a translation model, requires a parallel corpus where queries are paired with respective relevant documents. the parallel corpus is also known as a bitext. in the case of ms marco collections documents are much longer than queries, which makes it impossible to compute translation probabilities using standard alignment tools (och and ney, 2003). 18 hence, for each pair of query q and its relevant document d, we first split d into multiple short chunks d 1 , d 2 , . . . d n . then, we replace the pair (q, d) with a set of pairs {(q, d i )}. we evaluate performance of several models and their combinations. each model name is abbreviated as x (y), where x is a type of the model (see §3.3 for details) and y is a type of the text field. specifically, we index original tokens, lemmas, as well as bert tokens extracted from the main document text. for ms marco documents, which come in html format, we also extract tokens and lemmas from the title field. first, we evaluate performance of the tuned bm25 (lemmas). second, we evaluate fusion models that combine bm25 (lemmas) with bm25, proximity, and model 1 scores (see §3.3) computed for various fields. note that our fusion models are linear. third, we evaluate collection-specific combinations of manually-selected models: except for minor changes these are the fusion models that we used in our trec 2019 and 2020 submissions. all models were trained and/or tuned using training and development sets listed in from the experiments in we further compare the accuracy of the bert-based re-ranker @xcite applied to the output of the tuned traditional ir system with the accuracy of the same bert-based re-ranker applied to the output of lucene (with a bm25 scorer). the bert scorer is used to re-rank 150 documents: further increasing the number of candidates degraded performance on the trec 2019 test set. by mistake we used the same bm25 parameters for both passages and documents. as a result, ms marco documents candidate generator was suboptimal (passage retrieval did use the properly tuned bm25 scorer). however, we refrained from correcting this error to illustrate how a good fusion model can produce a strong ranker via a combination of suboptimal weak rankers. indeed, as we can see from ## conclusion and future work we present to the nlp community an existing k-nn search library nmslib, a new retrieval toolkit flexneuart, as well as their integration capabilities, which enable efficient retrieval of sparse and sparse-dense document representations. flexneuart implements a variety of effective traditional relevance signals, which we plan to use for a fairer comparison with recent neural retrieval systems based on representing queries and documents via fixed-size dense vectors.