4 ms·

The focus on the top 10 in vector search is a product of wanting to prove value over keyword search. Keyword search is going to miss some conceptual matches. Yo

The focus on the top 10 in vector search is a product of wanting to prove value over keyword search. Keyword search is going to miss some conceptual matches. You can try to work around that with tokenization and complex queries with all variations but it's not easy. Vector search isn't all that new a concept. For example, the annoy library (https://github.com/spotify/annoy https://github.com/spotify/annoy) has been around since 2014. It was one of the first open source approximate nearest neighbor libraries. Recommendations have always been a good use case for vector similarity. Recommendations are a natural extension of search and transformers models made building the vectors for natural language possible. To prove the worth of vector search over keyword search, the focus was always on showing how the top N matches include results not possible with keyword search. In 2023, there has been a shift towards acknowledging keyword search also has value and that a combination of vector + keyword search (aka hybrid search) operates in the sweet spot. Once again this is validated through the same benchmarks which focus on the top 10. On top of all this, there is also the reality that the vector database space is very crowded and some want to use their performance benchmarks for marketing. Disclaimer: I am the author of txtai (https://github.com/neuml/txtai https://github.com/neuml/txtai), an open source embeddings database

marginalia_nu 3y ago
Amusingly, vector search is conceptually nearly as old as keyword search. Most older IR textbooks promote the idea of viewing keyword search as a maximization problem of the weighted bit vector product between the query and the document, where the weight matrix is something like BM-25.
- PaulHoule 3y ago
  I was interested in dense vector search in 2004 and a bit depressed at how the indexing algorithms weren’t that good, Around 2013 I was involved with an actual product which was a search engine for patents. The thing about vector search today is that it is an absolute gold rush, Pinecone had the right idea but the wrong product (sorry SAAS is toxic), many of the latecomers are… late, and will find the whole startup and VC process will cost precious months when customers want to build products right now. Note for that patent search engine we had a quite a different idea than is fashionable today, that is, like very old TREC we care about the quality of results you got 1000 or 2000 results in in the assumption that a patent researcher wanted to be comprehensive. When I was first into IR it was in the context of “how is Google so much better than other search engines?” and one part of it was that based on the way search engines were being evaluated at TREC, Google was not a better search engine* because it was so focused on the first page. It has come full circle now, I have talked to people recently who complain that current TREC evaluations are too focused on the first few results.
  - thfuran 3y ago
    I assume we're not talking about the Texas Real Estate Commission?
    - marginalia_nu 3y ago
      https://trec.nist.gov/ https://trec.nist.gov/
snowstormsun 3y ago
Isn't one big problem of vector search that it is bounded by the complexity of the knn problem in multiple dimensions, whereas keyword search like bm25 is very fast and scalable because of inverted indices? Annoy and others need to sacrifice accuracy for speed I believe. Hybrid search can be used to first filter a smaller number of candidates and then rerank them using vector search. Performance wise, it is naturally pretty slow and hard to scale compared to keyword search.
- etiennedi 3y ago
  We (at Weaviate) support separate BM25, vector, and combined hybrid search, so I can talk about the performance aspect of all of these a lot. The tl;dr is: It's complicated. What you say, may be true in some cases, but not in others. One does not always scale better than the other. For example, ANN indexing with an index like HNSW scales pretty much logarithmically. A bit oversimplified, but roughly we see search times double with every 10x of the search space. In addition, calculations like euclidean distance and dot product (and therefore cosine sim) can be parallelized very well at a hardware level, e.g. AVX2/AVX512/neon and similar SIMD techniques. With BM25, this isn't quite as simple. We have algorithms such as WAND and Block-Max-WAND, which help eliminate _scoring_ elements that cannot reach a top-k spot. However, the distribution of terms plays a big role here. As a rule of thumb, the rarer a word is the fewer documents require scoring. Let's say you have 1B documents, and a 2-term query, but each term matches only 100k documents. If you AND-combine those queries, you will have at most 100k matches, if you OR-combine them, you will have at most 200k. The fact that there were 1B documents indexed played no role. But now think of two terms that each match 500M objects. Even with the aforementioned algorithms – which rely on the relative impact of each term – there is a risk we would now have to score every single document in the database. This is, again, over-simplified, but my point is the following: ANN latency is fairly predictable. BM25 latency depends a lot on the input query. Our monitoring shows that in production cases, when running a hybrid search, sometimes the vector query is the bottleneck, sometimes the BM25 query is. > Hybrid search can be used to first filter a smaller number of candidates and then rerank them using vector search My post is already getting quite long, but want to quickly comment on this two-step approach. For Weaviate, that's not the case. BM25 and vector searches happen independently, then the scores are aggregated to combine a single result set. Yes, you could also use BM25 as a filter set first, then re-rank the results with embeddings, however you wouold lose the BM25 scores. If you want to use keywords just as filters, you can do that much, much cheaper than through BM25 scoring. In Weaviate matching keywords to create a filter set, would only require AND-ing or OR-ing a few roaring bitmaps which is orders of magnitides more efficient than BM25 scoring. Disclaimer: associated with Weaviate.
rafaelero 3y ago
> In 2023, there has been a shift towards acknowledging keyword search also has value and that a combination of vector + keyword search (aka hybrid search) operates in the sweet spot. Do you have evidence that this hybrid approach is better than a vector search? That would be surprising.
- dmezzetti 3y ago
  In relation to txtai: https://neuml.hashnode.dev/benefits-of-hybrid-search https://neuml.hashnode.dev/benefits-of-hybrid-search If you run a web search for "vector hybrid search" you'll come across plenty of articles for a number of vector databases discussing the topic.
- softwaredoug 3y ago
  I'd actually want evidence for the opposite. Why vector retrieval for search? What's the evidence for that? BM25 is often a baseline for improving upon. But I see improvements using lots of techniques, not just vector retrieval.
  - dmezzetti 3y ago
    It would be good to have a BM25 baseline entry on this leaderboard: https://huggingface.co/spaces/mteb/leaderboard https://huggingface.co/spaces/mteb/leaderboard And I'm sure you're aware of the BEIR paper: https://arxiv.org/abs/2306.07471 https://arxiv.org/abs/2306.07471. Elastic references that in this blogpost: https://www.elastic.co/blog/improving-information-retrieval-elastic-stack-hybrid https://www.elastic.co/blog/improving-information-retrieval-... I agree that BM25 retrieval + vector re-ranking can work. But vector search does bring results to the table that vanilla BM25 can't, even with a large retrieval window. So I do think there is a place for both with the usual "it depends on your data/requirements" caveat.
    - softwaredoug 3y ago
      The opposite is also true. BM25 prefers lexical matches and brings these candidates back that vector search often doesn’t. I am not disagreeing vectors are useful, but I think benchmark based evidence is not the same as deploying a solution that must scale, be constantly updated, serve many use cases like filtering, search syntax, etc customers want. And plus I think there’s a real danger Of herding to vector retrieval (even then one view of it) which cuts off exploration of diverse solutions.
ofermend 3y ago
I agree. my experience is that hybrid search does provide better results in many cases, and is honestly not as easy to implement as may seem at first. In general, getting search right can be complicated today and the common thinking of "hey I'm going to put up a vector DB and use that" is simplistic. Disclaimer: I'm with Vectara (https://vectara.com https://vectara.com), we provide an end-to-end platform for building GenAI products.
IKantRead 3y ago
> The focus on the top 10 in vector search is a product of wanting to prove value over keyword search I'm surprised to see less mention of the use of vector search in RAG. The reason top 10 (or less) is so important in RAG is that you only have so much context to work with (and even in large context models, you still would prefer to minimize the total amount of context you're sending the model). Everyone I know working seriously on vector search is using it to plug into a prompt for an LLM. For this use case top 10 is a fairly important metric.

marginalia_nu 3y ago

Amusingly, vector search is conceptually nearly as old as keyword search. Most older IR textbooks promote the idea of viewing keyword search as a maximization problem of the weighted bit vector product between the query and the document, where the weight matrix is something like BM-25.

PaulHoule 3y ago
I was interested in dense vector search in 2004 and a bit depressed at how the indexing algorithms weren’t that good, Around 2013 I was involved with an actual product which was a search engine for patents. The thing about vector search today is that it is an absolute gold rush, Pinecone had the right idea but the wrong product (sorry SAAS is toxic), many of the latecomers are… late, and will find the whole startup and VC process will cost precious months when customers want to build products right now. Note for that patent search engine we had a quite a different idea than is fashionable today, that is, like very old TREC we care about the quality of results you got 1000 or 2000 results in in the assumption that a patent researcher wanted to be comprehensive. When I was first into IR it was in the context of “how is Google so much better than other search engines?” and one part of it was that based on the way search engines were being evaluated at TREC, Google was not a better search engine* because it was so focused on the first page. It has come full circle now, I have talked to people recently who complain that current TREC evaluations are too focused on the first few results.
- thfuran 3y ago
  I assume we're not talking about the Texas Real Estate Commission?
  - marginalia_nu 3y ago
    https://trec.nist.gov/ https://trec.nist.gov/

snowstormsun 3y ago

Isn't one big problem of vector search that it is bounded by the complexity of the knn problem in multiple dimensions, whereas keyword search like bm25 is very fast and scalable because of inverted indices? Annoy and others need to sacrifice accuracy for speed I believe. Hybrid search can be used to first filter a smaller number of candidates and then rerank them using vector search. Performance wise, it is naturally pretty slow and hard to scale compared to keyword search.

etiennedi 3y ago
We (at Weaviate) support separate BM25, vector, and combined hybrid search, so I can talk about the performance aspect of all of these a lot. The tl;dr is: It's complicated. What you say, may be true in some cases, but not in others. One does not always scale better than the other. For example, ANN indexing with an index like HNSW scales pretty much logarithmically. A bit oversimplified, but roughly we see search times double with every 10x of the search space. In addition, calculations like euclidean distance and dot product (and therefore cosine sim) can be parallelized very well at a hardware level, e.g. AVX2/AVX512/neon and similar SIMD techniques. With BM25, this isn't quite as simple. We have algorithms such as WAND and Block-Max-WAND, which help eliminate _scoring_ elements that cannot reach a top-k spot. However, the distribution of terms plays a big role here. As a rule of thumb, the rarer a word is the fewer documents require scoring. Let's say you have 1B documents, and a 2-term query, but each term matches only 100k documents. If you AND-combine those queries, you will have at most 100k matches, if you OR-combine them, you will have at most 200k. The fact that there were 1B documents indexed played no role. But now think of two terms that each match 500M objects. Even with the aforementioned algorithms – which rely on the relative impact of each term – there is a risk we would now have to score every single document in the database. This is, again, over-simplified, but my point is the following: ANN latency is fairly predictable. BM25 latency depends a lot on the input query. Our monitoring shows that in production cases, when running a hybrid search, sometimes the vector query is the bottleneck, sometimes the BM25 query is. > Hybrid search can be used to first filter a smaller number of candidates and then rerank them using vector search My post is already getting quite long, but want to quickly comment on this two-step approach. For Weaviate, that's not the case. BM25 and vector searches happen independently, then the scores are aggregated to combine a single result set. Yes, you could also use BM25 as a filter set first, then re-rank the results with embeddings, however you wouold lose the BM25 scores. If you want to use keywords just as filters, you can do that much, much cheaper than through BM25 scoring. In Weaviate matching keywords to create a filter set, would only require AND-ing or OR-ing a few roaring bitmaps which is orders of magnitides more efficient than BM25 scoring. Disclaimer: associated with Weaviate.

rafaelero 3y ago

> In 2023, there has been a shift towards acknowledging keyword search also has value and that a combination of vector + keyword search (aka hybrid search) operates in the sweet spot. Do you have evidence that this hybrid approach is better than a vector search? That would be surprising.

dmezzetti 3y ago
In relation to txtai: https://neuml.hashnode.dev/benefits-of-hybrid-search https://neuml.hashnode.dev/benefits-of-hybrid-search If you run a web search for "vector hybrid search" you'll come across plenty of articles for a number of vector databases discussing the topic.
softwaredoug 3y ago
I'd actually want evidence for the opposite. Why vector retrieval for search? What's the evidence for that? BM25 is often a baseline for improving upon. But I see improvements using lots of techniques, not just vector retrieval.
- dmezzetti 3y ago
  It would be good to have a BM25 baseline entry on this leaderboard: https://huggingface.co/spaces/mteb/leaderboard https://huggingface.co/spaces/mteb/leaderboard And I'm sure you're aware of the BEIR paper: https://arxiv.org/abs/2306.07471 https://arxiv.org/abs/2306.07471. Elastic references that in this blogpost: https://www.elastic.co/blog/improving-information-retrieval-elastic-stack-hybrid https://www.elastic.co/blog/improving-information-retrieval-... I agree that BM25 retrieval + vector re-ranking can work. But vector search does bring results to the table that vanilla BM25 can't, even with a large retrieval window. So I do think there is a place for both with the usual "it depends on your data/requirements" caveat.
  - softwaredoug 3y ago
    The opposite is also true. BM25 prefers lexical matches and brings these candidates back that vector search often doesn’t. I am not disagreeing vectors are useful, but I think benchmark based evidence is not the same as deploying a solution that must scale, be constantly updated, serve many use cases like filtering, search syntax, etc customers want. And plus I think there’s a real danger Of herding to vector retrieval (even then one view of it) which cuts off exploration of diverse solutions.

ofermend 3y ago

I agree. my experience is that hybrid search does provide better results in many cases, and is honestly not as easy to implement as may seem at first. In general, getting search right can be complicated today and the common thinking of "hey I'm going to put up a vector DB and use that" is simplistic. Disclaimer: I'm with Vectara (https://vectara.com https://vectara.com), we provide an end-to-end platform for building GenAI products.

IKantRead 3y ago

> The focus on the top 10 in vector search is a product of wanting to prove value over keyword search I'm surprised to see less mention of the use of vector search in RAG. The reason top 10 (or less) is so important in RAG is that you only have so much context to work with (and even in large context models, you still would prefer to minimize the total amount of context you're sending the model). Everyone I know working seriously on vector search is using it to plug into a prompt for an LLM. For this use case top 10 is a fairly important metric.