Searching by meaning: vector databases and retrieval · 07 / 08

The lexical side: BM25 and hybrid search

Semantic search, brilliant on paraphrases, misses an exact invoice number. How do you marry vectors to the world of exact words, without one score scale crushing the other?

In the previous chapter, we made the index durable and verified it: it survives restarts, and a round-trip oracle proves we read it back faithfully. All the search we have built since the beginning of this course rests on a solid foundation. But it also rests on one thing alone: meaning, captured by vectors. And there are queries where meaning, precisely, is not enough.

Imagine your personal document base, and this query: “invoice 8831”. You are not looking for a document that vaguely talks about billing. You are looking for invoice number 8831 - that exact one. Yet to a semantic engine, “8831” is just another point in space, a neighbor of “8830” and “2207”. It will hand you a pile of very similar invoices, unable to tell the right one apart. Semantic search just ran into what it cannot see: the letter.

The reflex would be to say: “let’s go back to good old keyword search - it finds the exact number.” True, but we would fall back into the trap that opened this course. Keyword search is blind to meaning: ask it “cancel a settlement,” it will never find a document titled “procedure for refunding an order,” because not a single word is shared. That is the vocabulary mismatch : two texts can be about the same thing using entirely different words.

So we have two blind spots, symmetrical and complementary:

Semantic search excels at paraphrases and synonyms, but floats on exact identifiers, rare proper nouns, literal references. It sees meaning, not letters.
Lexical search (by words) pins the exact token every time, but is deaf to synonyms. It sees letters, not meaning.

The idea of this chapter is to refuse the choice. Rather than pitting the two worlds against each other, we will make them collaborate: that is hybrid search . But before marrying two scores, we first need to know how to build a good one on the lexical side. That is the role of BM25.

BM25, the score of the letter

How do you rate how well a document “fits” a keyword query? The basic intuition: the more a query word appears in the document, the more relevant that document is. This counting is called term frequency . But this raw intuition leads to three pitfalls, and BM25 (for “Best Matching 25”) is precisely the formula that corrects all three. Let us walk through them one by one.

First pitfall: not all words are equal. If your query is “the consulting contract,” the word “the” appears in almost every document: it discriminates nothing. The word “consulting,” on the other hand, is rare and therefore very informative. BM25 weights each term by its rarity through the inverse document frequency , or IDF:

\text{IDF}(t) = \ln\!\left(1 + \frac{N - n(t) + 0.5}{n(t) + 0.5}\right)

This equation reads: the weight of term $t$ is the logarithm of a quantity that grows when $n(t)$ , the number of documents containing $t$ , is small. In other words, a term present in few documents (like “8831”) receives a large weight; a term present everywhere receives a tiny one. The rare speaks loudly, the commonplace goes quiet.

Second pitfall: the tenth occurrence is not worth the first. A document containing “consulting” five times is more relevant than one containing it only once. But is it five times more relevant? No. The gain must taper off: going from one to two occurrences counts a lot, going from nine to ten counts almost nothing. BM25 makes term frequency saturate via a parameter $k_1$ , which controls the speed at which this ceiling is reached.

Third pitfall: long documents cheat. A very long document mechanically has more chances of containing any given word, without being any more relevant. BM25 corrects this bias with length normalization , dosed by a parameter $b$ : at equal frequency, a document longer than average is penalized. Everything comes together in a single formula:

\text{BM25}(q, d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{f(t,d)\,(k_1 + 1)}{f(t,d) + k_1\left(1 - b + b\,\dfrac{|d|}{\text{avgdl}}\right)}

Read it as follows: the score of document $d$ for query $q$ is the sum, over each term $t$ in the query, of its rarity weight $\text{IDF}(t)$ multiplied by a saturated frequency. In the numerator, $f(t,d)$ is the number of times $t$ appears in $d$ . In the denominator, the term $|d|/\text{avgdl}$ compares the document length to the average corpus length: that is what penalizes long documents. Typical values are $k_1 = 1.5$ and $b = 0.75$ .

The fusion trap

We now know how to produce two scores for the same document: a lexical BM25 score, and a semantic score via cosine similarity (the one from chapter 1). The temptation is immediate: add them up, and the best of both worlds will emerge.

That is a trap, and a subtle one. The two scores do not live on the same scale. Cosine similarity is bounded in $[0, 1]$ . BM25 is not bounded: it grows with term rarity and count, and commonly reaches values of 2, 10, 15. Adding $0.9$ (an excellent cosine) to $14$ (a strong BM25) gives $14.9$ : the cosine is drowned, it no longer matters. The naive sum does not merge two signals - it lets the noisiest one crush the other. In practice, it behaves almost like a purely lexical search in disguise.

Fusion by rank: RRF

The remedy is almost insolently elegant: if the problem comes from score scales, then let us stop using scores altogether. Let us use only ranks. Whether you are first with a cosine of $0.99$ or first with a BM25 of $14$ , you are first, full stop. That is the idea behind Reciprocal Rank Fusion (RRF).

\text{RRF}(d) = \sum_{i} \frac{1}{k + r_i(d)}

This equation reads: the fused score of document $d$ is the sum, over each ranking $i$ (here the lexical and the semantic), of the inverse of $k + r_i(d)$ , where $r_i(d)$ is the rank of $d$ in ranking $i$ . Being ranked high (small rank) gives a large contribution; being ranked low gives a small one. The constant $k$ , classically set to $60$ , dampens the gap between the very top positions so that a single ranking cannot decide everything on its own.

The beauty of this formula is that it never reads a raw score. Multiply all BM25 values by a thousand: the ranks do not move, so the fused result does not move. RRF is scale-invariant by construction. A document that gets rewarded must be well ranked in both worlds at once; that is exactly what we expect from a good fusion.

Your turn to fuse

The component below puts the three rankings side by side on a small document corpus: the lexical ranking (BM25), the semantic ranking (cosine), and the hybrid ranking. Switch between the two queries, and especially switch the fusion method between RRF and naive sum to see BM25’s scale take over.

Query

lexical tokensinvoice8831

Fusion method

Lexical (BM25)

#1top
2.234
Invoice FR-2024-8831, consulting services
#2
0.693
Invoice FR-2024-2207, annual hosting
#3
0.693
Invoice FR-2023-1180, software license
#4
0.000
Cancel or get a refund for an order
#5
0.000
Settlement of internal staff rules
#6
0.000
Expense report, trip to Lyon
zero score: no shared token

Semantic (cosine)

#1top
1.000
Invoice FR-2024-8831, consulting services
#2
0.998
Invoice FR-2024-2207, annual hosting
#3
0.990
Invoice FR-2023-1180, software license
#4
0.788
Settlement of internal staff rules
#5
0.643
Expense report, trip to Lyon
#6
0.407
Cancel or get a refund for an order

Hybrid

#1top
0.033
Invoice FR-2024-8831, consulting services
#2
0.032
Invoice FR-2024-2207, annual hosting
#3
0.032
Invoice FR-2023-1180, software license
#4
0.031
Settlement of internal staff rules
#5
0.031
Cancel or get a refund for an order
#6
0.031
Expense report, trip to Lyon

What you observe

Identifier query: BM25 isolates d1 decisively, while cosine makes d1, d2 and d3 nearly indistinguishable. Meaning cannot tell three almost identical invoices apart; the rare token 8831 can.

Three questions to ask yourself while playing:

On the “invoice 8831” query, compare the lexical column and the semantic column. Which one places the right document far ahead? Which one hesitates between three invoices nearly tied? Why?
Switch to “cancel the settlement”. Which document does the lexical column put at the top, and is it the right one? What does the semantic column do?
Still on the paraphrase, switch fusion from RRF to naive sum. Does the document at the top of the hybrid column change? Which of the two fusion modes keeps the right document, and why does the other get it wrong?

Exercises

Solution to exercise 1: computing an IDF and understanding rarity

A corpus contains $N = 100$ documents. The term “invoice” appears in $60$ of them, the term “8831” in just one. We compute the IDF weight of each to understand which one discriminates.

Step 1. The frequent term “invoice”. We have $n(t) = 60$ . We apply the formula.

\text{IDF}(\text{invoice}) = \ln\!\left(1 + \frac{100 - 60 + 0.5}{60 + 0.5}\right)

Step 2. We simplify the fraction.

\frac{40.5}{60.5} \approx 0.669

Step 3. We take the logarithm.

\text{IDF}(\text{invoice}) = \ln(1.669) \approx 0.512

Step 4. The rare term “8831”. We have $n(t) = 1$ .

\text{IDF}(\text{8831}) = \ln\!\left(1 + \frac{100 - 1 + 0.5}{1 + 0.5}\right) = \ln(1 + 66.33\ldots) \approx \ln(67.3) \approx 4.21

Result. The rare term weighs approximately $4.21$ against $0.51$ for the frequent one, more than eight times as much. That is why, in the component, the document carrying “8831” stands out so clearly from the other invoices: all its weight comes from a single token, but a rare one.

Solution to exercise 2: why naive sum betrays on the paraphrase

On the “cancel the settlement” query, two documents compete: d4, the right one (“Cancel or get a refund for an order”), and d5, an intruder (“Settlement of internal staff rules”). We have the rounded scores from the component.

Step 1. The raw scores. On the cosine side, d4 scores $1.00$ and d5 scores $0.89$ . On the BM25 side, it is the opposite: d5 scores $1.67$ and d4 scores $1.34$ .

Step 2. The naive sum. We add the two scores for each document.

\text{naive}(d4) = 1.00 + 1.34 = 2.34

\text{naive}(d5) = 0.89 + 1.67 = 2.56

Partial result. The naive sum places d5 ( $2.56$ ) ahead of d4 ( $2.34$ ): it gets it wrong, because the magnitude of BM25 outweighed the precision of cosine.

Step 3. RRF. We no longer look at scores, only ranks. d4 is rank 1 in semantic and rank 2 in lexical; d5 is rank 1 in lexical but much further down in semantic. With $k = 60$ :

\text{RRF}(d4) = \frac{1}{60 + 1} + \frac{1}{60 + 2} \approx 0.0325

Result. RRF puts d4 back at the top: being first in meaning AND second in letters beats being first in letters but distanced in meaning. Rank fusion did what naive sum could not, without ever comparing two incomparable scales.

In one sentence

Semantic search and lexical search have symmetrical blind spots (one misses exact identifiers, the other misses synonyms); they are reconciled through hybrid search, on the condition of fusing not the raw scores (whose incompatible scales let BM25 crush the cosine) but the ranks, via reciprocal rank fusion, scale-invariant by construction.

Quiz

1. Why can a purely semantic search miss the query 'invoice 8831'?
2. What is the IDF factor in BM25 for?
3. Why fuse with RRF rather than by summing scores?

Toward chapter 8

We now know how to retrieve the right documents: by meaning, by letters, and by their robust fusion. But retrieving is not answering. If you ask your document base a real question, you do not want a list of documents to read yourself - you want a written answer, grounded in those documents. That is the whole challenge of the final chapter: connecting our search engine to a language model. We will give it, in context, the best passages surfaced by hybrid search, and it will compose the answer by drawing on them. That is the architecture known as retrieval-augmented generation, RAG, where everything we have built finally converges.

Sources

Robertson, S. & Zaragoza, H. (2009). “The Probabilistic Relevance Framework: BM25 and Beyond.” Foundations and Trends in Information Retrieval 3(4), 333-389. DOI 10.1561/1500000019
Spärck Jones, K. (1972). “A Statistical Interpretation of Term Specificity and its Application in Retrieval.” Journal of Documentation 28(1), 11-21. DOI 10.1108/eb026526
Cormack, G. V., Clarke, C. L. A. & Büttcher, S. (2009). “Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods.” SIGIR ‘09, 758-759. DOI 10.1145/1571941.1572114