Dense, Sparse, and Hybrid Retrieval

The last post searched vectors efficiently. But the nearest vector is only as useful as the encoder’s ranking. A lexical index supplies a different signal: which analyzed terms actually occur in a document.

We will compute BM25, compare it with a dense ranking, and fuse two candidate lists with reciprocal rank fusion. Hybrid retrieval can help when the lists contain complementary relevant documents; it can also promote noise.

The problem

For each query, return a ranked list of documents likely to answer it. Binary or graded relevance labels let us check whether useful documents reach the positions the reader or generator will see.

The query error code XRN-9042 calls for an exact identifier match. A query about hair loss after pregnancy may need passages describing “postpartum shedding.” These queries stress different matching signals; evaluate both before choosing a retriever.

BM25: still the baseline

BM25 (Best Matching 25) is a term-weighting function from the mid-1990s, descended from Robertson and Spärck Jones's probabilistic retrieval framework. It scores each (query, document) pair as a sum over the query terms, with weights for document frequency, term frequency, and document length.

Inverse document frequency gives rarer terms more weight. Under the positive-IDF formula below, even a term appearing in every document has a small positive weight.

The second idea is term frequency saturation. If a document mentions "quantum" once, great. If it mentions "quantum" ten times, that's more signal but not ten times more. BM25 takes term frequency and bends it through a saturating curve so the first occurrence matters most and the tenth barely moves the score.

The third idea is length normalization. A short document where the query term appears once is a stronger match than a long one where it appears once, because the short document is more about that term. BM25 downweights long-document matches and boosts short-document ones, with a tunable knob b controlling how aggressive that is.

Put them together and you get the BM25 score for a term t in a document d:

This example uses $k_1=1.5$ and $b=0.75$. Implementations use different defaults, and these parameters can be tuned. Sum the term contributions to score a document.

BM25 does not require a trained neural encoder. An inverted index finds the postings for each analyzed query term; the ranker combines their contributions. Query latency depends on posting-list sizes, index layout, filters and hardware.

Try “the” and then “chess.” Document frequency changes IDF, while length normalization and term frequency change the contribution within a matching document.

BM25 matches analyzed terms, so tokenization, stemming and synonym expansion affect what counts as overlap. A plain whitespace tokenizer has no built-in understanding of paraphrases.

Dense retrieval: cosine similarity in a trained space

A dense retriever can learn a match between “hair loss after pregnancy” and “postpartum shedding” from its training pairs, without requiring those strings to share terms. Whether it ranks that match correctly is a question for evaluation.

DPR uses a bi-encoder: query and passage are encoded separately and ranked by an unnormalized dot product. Other retrieval models normalize their outputs and use cosine. Those choices are part of the model’s training contract.

Dense retrievers can use the contrastive setup from the embeddings post: increase a positive passage’s score relative to negative candidates. In-batch negatives and mined hard negatives are common choices; the exact training recipe varies by model.

At inference, the document side is precomputed and stored in a vector index (the ANN structures from the last post); the query side is encoded once, then a k-nearest-neighbor lookup gives the top candidates.

The core capability dense retrieval adds is that the query and the document don't have to share any tokens: search for "cheap place to sleep in tokyo" and get back a document titled "budget hostels in shinjuku", because the embedding model has learned those two strings are geometrically nearby. Plain term matching cannot bridge that vocabulary gap by itself. Synonym expansion or other query analysis can add matching terms, and learned sparse retrieval can learn expansions.

The failure modes, side by side

A query can need both kinds of evidence: an exact product code and a paraphrased explanation of its fault. That is a useful test case for hybrid retrieval.

Learned sparse: SPLADE

Learned sparse retrieval keeps the inverted-index machinery of BM25 but learns the term weights from data, and can add terms to a document that aren't literally in its text.

SPLADE learns these sparse vocabulary weights. Expansion can bridge some vocabulary gaps. The number of nonzero terms and their distribution affect index size and query cost; BM25-like storage does not guarantee BM25-like speed.

ColBERT, from Khattab and Zaharia, keeps a vector per token instead of compressing each passage to one, so scoring becomes a sum of maxes over per-token similarities, more expressive than a single-vector biencoder and more expensive to index. We examine it in rerankers and two-stage pipelines.

Hybrid: reciprocal rank fusion

Reciprocal rank fusion, or RRF, combines ranked lists without requiring their raw score scales to agree.

Each retriever produces a ranked list. A document's RRF score is the sum, across lists, of one over its rank plus a constant k (usually 60). Higher score wins.

With $k=60$, rank 1 contributes $1/61$, rank 2 contributes $1/62$, and rank 50 contributes $1/110$. The large constant makes adjacent top ranks relatively similar. A document absent from a returned list contributes zero from that list.

The rank constant and list depths affect the fused ranking. Vary them on held-out queries when choosing a configuration.

A weighted score combination is another option. It needs a normalization or calibration strategy and validation data. Compare it with RRF using the same candidate budget.

The worked example

Our corpus is ten short "documents":

1. the king of england visited france
2. queen elizabeth ruled england for decades
3. the royal leader addressed the nation
4. a chess king can move one square
5. monarchs of europe met in paris
6. france and england share a border
7. pawns protect the king in chess
8. the president of france spoke today
9. elizabeth crowned king edward the second
10. royal family visits the paris monument

These are artificial lexical examples, not historical or geographic claims. Total tokens: 61. Average document length: 6.1. We'll run the query king of england through both BM25 and a pretend dense encoder, then fuse.

For BM25 we need three idf values. With $N=10$ and Lucene-style idf $\ln(1 + (N - n + 0.5) / (n + 0.5))$:

• "king" appears in 4 docs. $\text{idf} = \ln(1 + 6.5/4.5) = 0.89$
• "of" appears in 3 docs. $\text{idf} = \ln(1 + 7.5/3.5) = 1.15$
• "england" appears in 3 docs. $\text{idf} = \ln(1 + 7.5/3.5) = 1.15$

For document 1, "the king of england visited france", all three query terms match with $\text{tf} = 1$. The length normalization term is $1 - 0.75 + 0.75 \cdot (6/6.1) = 0.988$, so the saturation factor is $2.5 / (1 + 1.5 \cdot 0.988) \approx 1.007$. The three contributions are $0.89 \cdot 1.007 \approx 0.90$, $1.15 \cdot 1.007 \approx 1.16$, and $1.16$ again. Sum: about $3.22$.

Document 9, "elizabeth crowned king edward the second", only has "king". Its score is about $0.90$. Documents 2, 5, 6, 8 each have exactly one of the query terms and end up at about $1.16$. Document 3, "the royal leader addressed the nation", contains zero query terms. Its score is zero.

With ties broken by document ID, BM25 ranks d1, d2, d5, d6, d8, d7, d9, d4, d3, d10. Its top five are [d1, d2, d5, d6, d8].

Now pretend we have a trained biencoder that loves d1 (exact semantic match), d9 (crowning a king of england), d3 ("royal leader" ≈ "king of england"), d2 (queen of england), and d5 (monarchs of europe), but not d6 (a border) or d8 (the french president). Dense top 5: [d1, d9, d3, d2, d5].

Fuse only the returned top-five lists, matching the visuals. A document missing from one list gets zero from that retriever:

• d1: $1/61+1/61=0.03279$
• d2: $1/62+1/64=0.03175$
• d5: $1/63+1/65=0.03126$
• d9: $0+1/62=0.01613$
• d3: $0+1/63=0.01587$

Fused top 5: [d1, d2, d5, d9, d3].

What to evaluate

Measure recall at the candidate stage and ranking quality at the depth users or the generator actually see. Include exact identifiers, paraphrases and mixed queries. Keep a query set that was not used to choose the fusion settings.

The implementation sketch

This Python example combines BM25, a toy dense retriever, and RRF fusion, on the same corpus we worked through above. The BM25 numbers match what we computed by hand.

import math
from collections import Counter
 
corpus = [
    "the king of england visited france",
    "queen elizabeth ruled england for decades",
    "the royal leader addressed the nation",
    "a chess king can move one square",
    "monarchs of europe met in paris",
    "france and england share a border",
    "pawns protect the king in chess",
    "the president of france spoke today",
    "elizabeth crowned king edward the second",
    "royal family visits the paris monument",
]
docs = [d.lower().split() for d in corpus]
N = len(docs)
avgdl = sum(len(d) for d in docs) / N
 
def bm25(query, docs, k1=1.5, b=0.75):
    N = len(docs)
    if not N:
        return []
    avgdl = sum(map(len, docs)) / N or 1.0
    # Document frequency for each query term
    df = {t: sum(1 for d in docs if t in d) for t in query}
    scores = []
    for d in docs:
        tf = Counter(d)
        dl = len(d)
        s = 0.0
        for t in query:
            if tf[t] == 0 or df[t] == 0:
                continue
            idf = math.log(1 + (N - df[t] + 0.5) / (df[t] + 0.5))
            sat = (tf[t] * (k1 + 1)) / (tf[t] + k1 * (1 - b + b * dl / avgdl))
            s += idf * sat
        scores.append(s)
    return scores
 
bm25_scores = bm25(["king", "of", "england"], docs)
bm25_rank = sorted(range(N), key=lambda i: -bm25_scores[i])
print("BM25 top 5:", [i + 1 for i in bm25_rank[:5]])
# [1, 2, 5, 6, 8]

# --- Toy "dense" retriever ---
# In real life this would be cosine sim between trained embeddings.
dense_scores = [0.92, 0.78, 0.81, 0.55, 0.74, 0.48, 0.52, 0.46, 0.86, 0.61]
dense_rank = sorted(range(N), key=lambda i: -dense_scores[i])
print("Dense top 5:", [i + 1 for i in dense_rank[:5]])
# [1, 9, 3, 2, 5]
 
# --- Reciprocal rank fusion ---
def rrf(rankings, k=60):
    scores = [0.0] * N
    for r in rankings:
        for pos, doc_id in enumerate(r):
            scores[doc_id] += 1.0 / (k + pos + 1)
    return scores
 
fused = rrf([bm25_rank[:5], dense_rank[:5]])
fused_rank = sorted(range(N), key=lambda i: -fused[i])
print("Fused top 5:", [i + 1 for i in fused_rank[:5]])
# [1, 2, 5, 9, 3]

Misconceptions

"Dense retrieval obsoleted BM25." Lexical ranking remains a useful baseline and can supply relevant candidates a particular dense model misses.

"Hybrid retrieval needs a trained fusion model." RRF works without training a fusion model. You still choose its constant, list depths and underlying retrievers, then validate the result.

"Embeddings replace inverted indexes." They supply different representations and rankings. A system can use either or both according to its measured needs.

"Bigger embeddings always beat BM25." More dimensions do not guarantee exact-identifier recall or domain coverage. Evaluate the model and indexing pipeline together.

What's next

The next question is what counts as a retrievable document: a page, paragraph, sentence or overlapping window.

Next, chunking strategies determine which units can enter those lists and how much supporting context each unit preserves.

Additional reading (and watching)

• Robertson, S. & Zaragoza, H. (2009). The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval. The canonical reference for BM25's derivation and parameter choices.

• Karpukhin, V., et al. (2020). Dense Passage Retrieval for Open-Domain Question Answering. EMNLP 2020. The biencoder-plus-contrastive recipe that made dense retrieval practical at scale.

• Formal, T., et al. (2021). SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking. SIGIR 2021. Learned sparse retrieval that keeps inverted-index machinery while adding expansion terms.

• Thakur, N., et al. (2021). BEIR: A Heterogeneous Benchmark for Zero-Shot Evaluation of Information Retrieval Models. NeurIPS 2021. The benchmark that made clear BM25 isn't obsolete: dense retrievers lose to it on many out-of-distribution tasks.

• Khattab, O. & Zaharia, M. (2020). ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT. SIGIR 2020. The late-interaction architecture we'll revisit in the rerankers post.

• Cormack, G., Clarke, C., & Büttcher, S. (2009). Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods. SIGIR 2009. The original RRF formulation and its evaluation on several ranked-list fusion tasks.

• Lin, J., Nogueira, R., & Yates, A. (2021). Pretrained Transformers for Text Ranking: BERT and Beyond. Synthesis Lectures on Human Language Technologies. Book-length survey of the neural IR landscape, mapping where BM25, DPR, SPLADE, and ColBERT sit relative to each other.

• Supabase. (2024). Hybrid search with Postgres, pgvector, and tsvector. The small-scale Postgres version of the same pattern, retrieval inside the application database.