Suppose you are building a search engine for a large pool of study documents. Students will send their queries to the search engine and expect a list of matching documents back, ranked by relevance to the query.
You implement keyword search with BM25 which handles queries like ‘periodic table of elements’ well because the documents you want contain exactly that phrase. You also implement vector search to handle queries like ‘how do trees use sunlight to make food’ and find documents that describe photosynthesis. BM25 would miss these documents since query terms do not appear in them. A dense embedding model understands the meaning and will place the query and the photosynthesis document close together. The opposite also happens i.e. a student searching ‘Problem set 4’ may receive problem sets 3 and 5 from vector search.
So to make your search engine return high quality results, you decide to use both BM25 (keyword) and vector search. You index every study document 2x: once in BM25 for keyword matching and once as a dense vector from an embedding model like text-embedding-ada-002 stored in a vector index like Pinecone or FAISS.
This solves one problem and creates another.
Two lists that use different scores
For every query you get 2 ranked lists back. BM25 returns documents with scores like 12.3, 8.2, 7.5. Vector search returns documents with cosine similarities like 0.89, 0.86, 0.84. You want to hand your users the best of both lists, but the two sets of numbers have no relationship to each other.
Let’s look at an example. Suppose you run this query: ‘how do trees use sunlight to make food’. The two indexes return the following results:
| Rank | BM25 (score) | Vector (cosine similarity) |
|---|---|---|
| 1 | Doc_A (12.3) | Doc_F (0.89) |
| 2 | Doc_B (8.2) | Doc_G (0.86) |
| 3 | Doc_C (7.5) | Doc_B (0.84) |
| 4 | Doc_D (5.1) | Doc_A (0.79) |
| 5 | Doc_E (4.4) | Doc_C (0.68) |
Doc_A is the top result in BM25 but 4th place in Vector. In the final result, which slot it should identify: 1, 4 or some other position? We need a way to combine the two lists to get the best of both.
Reciprocal Rank Fusion
Enter Reciprocal Rank Fusion (RRF). It’s a very simple algorithm for merging two ranked lists. It discards scores (and cosines similarities) and uses the rank (position) of documents in each list to combine them. In other words, rank #3 means the same thing for both lists. Here’s the RRF formula:
\[\mathrm{RRF}(d) = \sum_{i} \frac{1}{k + \mathrm{rank}_i(d)}\]- You can combine any number of retrievers with RRF.
- \(\mathrm{rank}_i(d)\) is position of document \(d\) in retriever \(i\)’s list (starting at 1)
- \(k\) is a constant. 60 is the default in most libraries. If you are curious where 60 comes from, its from this paper. The authors ran some experiments and decided to use 60 because it was “near-optimal” and the “choice was not critical”.
- If a document isn’t part of a retriever’s list, that retriever contributes 0.
| Docs | BM25 rank | Vector rank | RRF score |
|---|---|---|---|
| Doc_A | 1 | 4 | 1/61 + 1/64 = 0.03202 |
| Doc_B | 2 | 3 | 1/62 + 1/63 = 0.03200 |
| Doc_C | 3 | 5 | 1/63 + 1/65 = 0.03126 |
| Doc_F | – | 1 | 0 + 1/61 = 0.01639 |
| Doc_G | – | 2 | 0 + 1/62 = 0.01613 |
| Doc_D | 4 | – | 1/64 + 0 = 0.01563 |
| Doc_E | 5 | – | 1/65 + 0 = 0.01538 |
The final result after RRF combines the 2 lists: Doc_A, Doc_B, Doc_C, Doc_F, Doc_G, Doc_D, Doc_E.
Few things to remember about RRF:
- It rewards consensus. A document appearing in both lists often outperforms a document appearing only in one.
- The spread between positions doesn’t matter as much e.g. Doc_B (ranked #2 and #3) nearly outperformed Doc_A (ranked #1 and #4). This is because of \(k = 60\). Rank #1 contributes only about 1/61 (about 0.0164) and rank #5 contributes 1/65 (0.0154), ~6% difference. Without \(k\), rank #1 would contribute 1 and rank #5 will contribute 0.2. This would let a single retriever’s top result dominate everything else. A large value of
kfavors consensus. - RRF is oblivious to scores. It only sees ranks. A list where #1 scores 0.96 and #2 scores 0.31 looks identical to another where #1 scores 0.96 and #2 scores 0.95. This means it can’t tell a strong result from a junk one: if a query has only one good keyword match but you asked for the top 5, BM25 will still return 4 more junk results, and RRF will give BM25’s #2 (junk) the same weight as vector search’s #2 (possibly a great result). In practice, you’ll design your retrievers to not return junk e.g. cosine similarity below 0.6 gets dropped.
- In examples above, we gave BM25 and vector search the same weight but in practice, depending on your use case, you’d give more weight to one retriever to allow its results to have higher priority. E.g. you might go with 70% BM25 and 30% vector search. The weights are defined by you and are applied to all queries, meaning RRF cannot learn to adjust weights based on query intent. In my opinion, this is another weakness.
- You can also other other techniques like min-max, z-score normalization etc. instead of RRF. RRF’s main appeal is that it’s simple: it requires no calibration and no tuning: all it needs are scores.
If you can tolerate some addition costs and latency, a cross-encoder reranker (such as the recently launched bge-reranker) is a better option to produce the final result. A bi-encoder like text-embedding-ada-002 embeds the query and the document independently; a cross-encoder reads both of them together and outputs one score for the pair on a consistent scale. Here’s how you can use cross encoder:
- Take top 10 documents from each list
- Merge the two lists with a simple union and drop duplicates
- Call the cross-encoder score and sort the documents in the (merged) list
In our experiments, cross-encoder showed an improvement in results quality for most of the queries. The primary concern was added latency since the system is real-time. RRF is simple math operations on the CPU. With cross-encoders, we are doing a full forward pass through a transformer and it usually involves a GPU instance and network calls. While cross-encoder models are much smaller and faster than full LLMs, you are still looking at 100-300ms to score 10 or 20 results.
You can also combine both techniques. Say you have 30 eligible documents from your two retrievers, but only show 10 per page. You can use RRF to choose the top 15 or 20 and send only those to the cross-encoder. Remaining documents, you can sort with RRF since most users will not scroll past page 1. However, I must stress that choosing weights (i.e. how much importance to give to lexical vs semantic), using either or both (cross-enconder or RRF) highly depends on your goals and the type of search you are performing. For a system that’s mostly searching keywords, 90% lexical + 10% semantic with RRF may give the best results. For a different system, that’s searching municipal regulations, you may get best results with 30% lexical + 70% semantic with cross-encoder.
Another option for choosing the right set of weights at run-time is to use a small classifier model i.e. course codes, concepts, lean towards BM25 while natural-language type queries lean vector search. You can also probably fine-tune the cross-encoder.
But here’s the deeper issue: when we start getting into complexity, we’ve given up the real reason to use RRF and one of the key takeaways of this post: RRF is super simple. It doesn’t care about which retrievers you use or how many, has no parameters to tune you, you can just start using it. My suggestion is to use RRF when you are first starting out. Then as you test, you evolve to fixed weights, per-query weights or something else. If you can afford latency, a cross-encoder reranker is a good option.
Measure before you tune
This brings me the second takeaway: the right settings and tools you use all depend on the corpus and use case. It’s important that you invest time early and build a great golden dataset: real queries scrapped from logs paired with ranked list of documents that should come back. It’s not always easy to build, but without it, you are flying blind and can’t tell if a change is improving the system or making it worse.
I’ve been good teams and good engineers rush to adopt the hot new technology or the technique they read on arXiv but underinvest in golden dataset. They run a few queries, see good results and declare it’s done. Then it fails in production because no one accounted for typos that queries usually contain. Or the performance became worse for certain class to categories and the dataset didn’t account for it. Sometimes, there’s a whole dimension missing that matters more than hybrid search in your system like recency or popularity of a certain document.
Until next time.