Source-linked AI summary
Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search
Leonid Boytsov, David Novak, Yury Malkov, Eric Nyberg
TL;DR
Term-based candidate retrieval can miss relevant documents because query and document terms may differ despite denoting the same concepts. The paper replaces term-based retrieval with generic k-NN using BM25 and IBM Model 1 scores; approximate search is nearly two orders of magnitude faster than exact search and can sometimes be faster and more accurate than Lucene.
Problem
Term-based candidate retrieval may be incomplete because query and relevant-document terms can mismatch despite denoting the same concepts.
Source: §1 · p. 1Method
The paper replaces term-based retrieval with approximate generic k-NN using a weighted combination of BM25 and IBM Model 1 scores.
Source: §5 · p. 9Results
Approximate k-NN is nearly two orders of magnitude faster than exact brute-force search and can sometimes be both faster and more accurate than term-based Lucene.
Source: §5 · pp. 9–10Takeaways & Limitations
The work demonstrates generic k-NN retrieval with a challenging non-metric, non-symmetric BM25 and IBM Model 1 similarity.
Source: §5 · p. 10Whether sentence- or document-level embeddings can improve on the tested embedding retrieval results remains to be verified.
Source: §3 · p. 6
Abstract
from arXiv · showhide
Retrieval pipelines commonly rely on a term-based search to obtain candidate records, which are subsequently re-ranked. Some candidates are missed by this approach, e.g., due to a vocabulary mismatch. We address this issue by replacing the term-based search with a generic k-NN retrieval algorithm, where a similarity function can take into account subtle term associations. While an exact brute-force k-NN search using this similarity function is slow, we demonstrate that an approximate algorithm can be nearly two orders of magnitude faster at the expense of only a small loss in accuracy. A retrieval pipeline using an approximate k-NN search can be more effective and efficient than the term-based pipeline. This opens up new possibilities for designing effective retrieval pipelines. Our software (including data-generating code) and derivative data based on the Stack Overflow collection is available online.
1. INTRODUCTION
Term-based retrieval can miss relevant documents when query and document terms differ despite denoting the same concepts. The paper explores generic k-NN retrieval with BM25+Model 1 similarity as an alternative, reporting faster approximate search and potential gains over Lucene.
1. INTRODUCTION
- A vocabulary gap—query and document terms denoting the same concepts differently—can make term-based candidate retrieval incomplete.The filter-and-refine pipeline assumes that term-based search produces a reasonably complete candidate list.Source: §1 · p. 1
- Query expansion adds related terms or phrases, but hundreds or thousands of expansions seem infeasible with an inverted index, motivating unlimited aliases through k-NN.The paper contrasts this with traditional expansion techniques, which are limited to dozens of terms for efficiency.Source: §1 · p. 1
- Generic k-NN offers a conceptually simple optimization approach, but the curse of dimensionality makes exact, efficient search challenging for textual data.The paper notes that textual data seems intrinsically high-dimensional and describes approximate search as a way to partially address the problem.Source: §1 · pp. 1–2
- Approximate k-NN with BM25+Model 1 is nearly two orders of magnitude faster than exact brute-force search and can be 1.5× faster than Lucene while more effective.The paper attributes the effectiveness advantage to bridging the vocabulary gap.Source: §1 · p. 2
2. APPROACH
The paper tests approximate k-NN retrieval on community question-answer collections, using similarity functions intended to capture term associations beyond BM25. Its BM25+Model 1 model surpasses prior art on Manner, while the approach compares multiple similarity models and k-NN search methods.
2. APPROACH
- Community QA serves as a testbed for approximate k-NN retrieval, with each question's summary and description used to retrieve its single best answer.The similarity function must outperform BM25 enough that search inaccuracy does not erase the benefit.Source: §2 · p. 2
2.1.1 Cosine TF×IDF and BM25
- Cosine TF×IDF compares lemmatized query and answer vectors, while BM25 sums normalized term-frequency contributions only for terms they share.The BM25 score is normalized by the sum of query-term IDFs.Source: §2.1.1 · p. 3
2.1.2 IBM Model 1
- IBM Model 1 represents query-answer term associations as translation probabilities; pruning probabilities below 2.5 · 10−3 improves efficiency and effectiveness while reducing memory.The authors motivate pruning as a way to discard small probabilities likely caused by overfitting.Source: §2.1.2 · pp. 3–4
2.1.3 BM25+Model 1
- BM25+Model 1 surpasses prior art on Manner by 14–26% in P@1 and 10–11% in MRR.The comparison follows Surdeanu et al.'s methodology across result-set sizes N.Source: Table 2 · p. 4, §2.1.3 · p. 4
- BM25+Model 1 is trained as a linear two-feature ranker using BM25 and IBM Model 1 scores, with P@1 as its optimization target.Training uses BM25-retrieved candidates and labels the true answer relevant when it is retrieved.Source: §2.1.3 · p. 4
2.1.4 Cosine Embed
- Cosine Embed uses IDF-weighted averaged word embeddings, with non-lemmatized terms and retrofitting through the Model 1 translation table as a relational lexicon.The authors evaluate pretrained embedding sets and select the most effective ones.Source: §2.1.4 · p. 4
2.2 Methods of k-NN Search
- Approximate k-NN methods use black-box similarities, including non-metric BM25+Model 1; NAPP suits sparse TF×IDF data, while SW-graph is faster for dense embeddings.For dense vector data, SW-graph outstrips NAPP by an order of magnitude; NAPP substantially outperforms SW-graph for sparse BM25 and BM25+Model 1 data.Source: §2.2 · pp. 4–5
3. MAIN EXPERIMENTS
Across Stack Overflow and Comprehensive, approximate k-NN results show speed–effectiveness trade-offs that depend on the retrieval model and collection. The experiments also find that pivot filtering depends on the distance function used to compare points.
3. MAIN EXPERIMENTS
- Brute-force Cosine TF×IDF without reranking has less than half BF BM25’s recall, while averaged word-embedding cosine remains worse than BM25 despite reranking.The authors leave open whether sentence or document embeddings could improve results.Source: §3 · p. 6
- BM25+Model 1 recall is 16% higher on Comprehensive and 26% higher on Stack Overflow than BM25; matching it with Lucene on Stack Overflow requires N > 20 rather than N = 10.Source: §3 · p. 6
- 340 ms lets SW-graph answer Stack Overflow queries while losing only 1.3% of answers compared with brute-force search.The paper describes approximate search as nearly as accurate as exact search.Source: §3 · pp. 6–7
- 230 ms lets NAPP BM25 answer Stack Overflow queries nearly 2.7× faster than Lucene and 15× faster than brute force, with 2.1% lower P@1 and 4.7% lower answer recall.Source: §3 · p. 7
- 400 ms gives NAPP BM25+Model 1 P@1 0.074 and answer recall 0.252 on Stack Overflow, improving over brute-force BM25 by 19.3% and 5.4%, respectively.Its second-slowest run was nearly as efficient as Lucene and beat BM25 by 27.4% in P@1 and 18.4% in recall.Source: §3 · p. 7
- On Comprehensive, NAPP BM25+Model 1 can be faster and more accurate than NAPP BM25 because pivot-posting-list merging can dominate time once distance computation is reduced.Source: §3 · p. 7
- At approximately equal R@1, BM25+Model 1 needs 2–3× fewer distance computations than BM25 on Comprehensive, while BM25 needs significantly fewer on Stack Overflow.BM25’s reduction on Stack Overflow can be two orders of magnitude higher than on Comprehensive; the authors relate the difference to query length and term overlap.Source: §3 · p. 7, Table 4 · p. 7
- Proxy pivot distances weaken filtering: BM25 instead of BM25+Model 1 requires more candidates at equal recall, especially on Comprehensive, and Cosine TF×IDF instead of BM25 causes greater deterioration.The figure compares original and proxy distances by the reduction in distance computations; larger reductions indicate better filtering.Source: §3 · pp. 7–8, Figure 3 · p. 8
4. DISCUSSION AND RELATED WORK
The discussion contrasts term-based retrieval and cosine-oriented k-NN with approaches for handling vocabulary mismatch. It also highlights the large association counts required for gains and limits in the evaluated methods.
4. DISCUSSION AND RELATED WORK
- Term-based indexing can miss documents under vocabulary mismatch, while prior k-NN retrieval work largely focuses on cosine similarity and LSH.Related work also describes term-index and LSH approaches, including a hybrid for streaming First Story Detection.Source: §4 · pp. 8–9
- For any rank N, TF×IDF cosine finds 2× fewer answers than BM25; increasing N can reduce approximate search accuracy or efficiency.The paper notes that an accurate 1-NN search is easier than an accurate 500-NN search.Source: §4 · p. 9
- The authors hypothesize that DBH performance, like NAPP performance, depends on pivot choice; randomly selected terms produced substantially better NAPP pivots than random pivots.They leave a detailed comparison of pivoting approaches to DBH outside the paper’s scope.Source: §4 · p. 9
- The SW-graph works well for dense vector spaces but is less useful for BM25 and BM25+Model 1, and the authors do not know why.Source: §4 · p. 9
- More than 10K associations per query term are needed to outperform BM25 by about 20%, while retaining only entries with probabilities ≥0.1 yields a 2.6% improvement.Frequent terms are associated with many less frequent terms, producing many non-zero translation probabilities; Table 5 reports association counts at performance levels on dev2.Source: §4 · p. 9, Table 5 · p. 9
- The experiments use quite long queries, leaving the applicability of k-NN to shorter ad hoc Web queries unclear.Source: §4 · p. 9
5. CONCLUSION
The paper applies approximate generic k-NN retrieval with a BM25 and IBM Model 1 similarity function. It reports near two-orders-of-magnitude speedup over exact brute force and says the pipeline can sometimes be faster and more accurate than Lucene.
5. CONCLUSION
- The method combines BM25 scores and IBM Model 1 log-scores in a linguistically motivated, non-metric and non-symmetric similarity function.Source: §5 · p. 9
- Approximate k-NN is nearly two orders of magnitude faster than exact brute force with only a small accuracy loss, and can sometimes be faster and more accurate than Lucene.The Lucene comparison is reported in Table 3.Source: §5 · pp. 9–10
- The paper presents this as the first successful generic k-NN search for a similarity function combining BM25 and IBM Model 1.Source: §5 · p. 10
- The techniques target vocabulary gaps but are described as generic for modeling semantic and syntactic mismatch; the software and derivative Stack Overflow data are available online.Source: §5 · p. 10