R7.1 · LESSON 1 OF 6

Lexical and dense search

Fuse rankings, rerank evidence and evaluate retrieval separately from grounded answer generation.

THE IDEA

Lexical and dense search

Lexical search (BM25) scores documents by the query words they contain, weighting rare words more (idf), letting repeated words help with diminishing returns (saturation) and discounting long documents (length normalisation). Dense retrieval compares embeddings and can match meaning with little word overlap. Each fails where the other works: exact identifiers favour lexical matching, paraphrases favour dense.

term frequency in the document2document length / average length1b (length normalisation)0.75k1 (saturation)1.2

term part = tf·(k1+1) / (tf + k1·(1 − b + b·dl/avgdl)) at tf = 2: 1.375 (more occurrences help less and less; a long document is penalised when b > 0)

tf	1	2	3	5	10	20
term part	1	1.375	1.571	1.774	1.964	2.075

BM25 rewards exact term evidence, weighted by how rare the term is (idf). That is why it is strong on identifiers such as ERR-1042. A synonym such as "repair" for "fix" scores zero; dense retrieval can bridge that, but neither always wins.

See saturation and length normalisation in the BM25 term part.

Predict first. Must a dense retriever always outperform keyword matching on identifiers?

Chapter context

RAG combines a retrieval step with a generator that uses retrieved evidence. Better generation cannot reliably repair missing or wrong evidence. Measure retrieval and answer quality as separate stages and connect citations to actual supporting passages.

TRY IT YOURSELF

Part 1. Do it hands-on

Evaluate BM25's term part by hand, then implement BM25 and rank documents.

term frequency in the document2document length / average length1b (length normalisation)0.75k1 (saturation)1.2

term part = tf·(k1+1) / (tf + k1·(1 − b + b·dl/avgdl)) at tf = 2: 1.375 (more occurrences help less and less; a long document is penalised when b > 0)

tf	1	2	3	5	10	20
term part	1	1.375	1.571	1.774	1.964	2.075

tf = 2, b = 0 tf = 10, b = 0 tf = 1, b = 0.75, dl/avgdl = 2 dense always beats BM25 on identifiers? (yes/no)

To do: BM25's term part is tf·(k1+1) / (tf + k1·(1 − b + b·dl/avgdl)). With k1 = 1.2, b = 0 (no length normalisation), a term occurring twice scores (3 decimals)?
To do: The same term occurring ten times (3 decimals)? Note how little it gains over twice
To do: Now b = 0.75 and the document is twice the average length (dl/avgdl = 2), term frequency 1. Term part (3 decimals)?
To do: Must a dense retriever always beat keyword matching on exact identifiers like ERR-1042? Type yes or no

Part 2. Do it in code

tf_part(tf, dl, avgdl, k1=1.2, b=0.75): tf·(k1+1) / (tf + k1·(1 − b + b·dl/avgdl)).
idf(N, n): ln(1 + (N − n + 0.5) / (n + 0.5)) for a term found in n of N documents.
bm25(query, doc, corpus, k1=1.2, b=0.75): query and doc are lists of lower-case terms, corpus a list of such docs. Sum over the distinct query terms of idf(N, n_t) · tf_part(tf_t, len(doc), avgdl).
rank_bm25(query, corpus): document indices by BM25, best first (ties: lower index).
lexical_miss(query, doc): True if the query and the document share no term (a synonym will not match).

import math

def tf_part(tf, dl, avgdl, k1=1.2, b=0.75):
    pass

def idf(N, n):
    pass

def bm25(query, doc, corpus, k1=1.2, b=0.75):
    pass

def rank_bm25(query, corpus):
    pass

def lexical_miss(query, doc):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Must a dense retriever always outperform keyword matching on identifiers?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

RRF(d)=\sum_r\frac1{k+rank_r(d)},\quad MRR=\frac1Q\sum_q\frac1{rank_q(first\ relevant)}.

An exponential-gain convention is $DCG@K=\sum_{i=1}^K(2^{rel_i}-1)/\log_2(i+1)$ and $nDCG=DCG/IDCG$ . Some tools use raw relevance gains instead: do not mix the conventions silently.

A common textbook-scaled single-term BM25 contribution is

IDF(t)\frac{tf(t,d)(k_1+1)}{tf(t,d)+k_1(1-b+b|d|/avgdl)}.

A commonly used nonnegative IDF is $\log[1+(N-df(t)+0.5)/(df(t)+0.5)]$ . Here tf is term count, df document frequency, N corpus document count and avgdl average document length. Engine-specific constant factors, field statistics and length encodings can differ, so these numbers are a teaching model rather than a promise of byte-for-byte engine scores.

Worked example

With k=60, document A has ranks 1 and 3, while B has ranks 2 and 1. A scores 1/61+1/63≈0.0322665 and B scores 1/62+1/61≈0.0325225, so B wins. For exponential gains and relevance order [1,0,2], DCG is 1+3/2=2.5, compared with ideal 3+1/log2(3).

For the stated BM25 variant, a term occurring twice in an average-length document with k1=1.2 has frequency factor 2×2.2/(2+1.2)=1.375 before multiplying by IDF. Increasing count saturates rather than increasing score linearly.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import log2,isclose
A=1/61+1/63
B=1/62+1/61
assert B > A
assert isclose(A,.032266458495966696)
assert isclose(B,.03252247488101534)
dcg=lambda labels: sum((2**rel-1)/log2(i+2) for i,rel in enumerate(labels))
assert dcg([1,0,2]) == 2.5
ndcg=dcg([1,0,2])/dcg([2,1,0])
assert 0 < ndcg < 1
tf,k1,b,length,average=2,1.2,.75,100,100
factor=tf*(k1+1)/(tf+k1*(1-b+b*length/average))
assert isclose(factor,1.375)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A retrieved answer can still hallucinate. RRF's k is a fusion constant, not the result-count k in recall@k. Evaluation must state whether relevance gains are linear or exponential.