Sparse retrieval & hybrid fusion

BM25 scores documents by how well their terms match the query terms, weighted by how rare those terms are across the corpus. It is a bag-of-words model — it ignores word order, synonyms, and meaning. It cares only whether the exact tokens appear, and how distinctive those tokens are.

The scoring formula for a single query term t in document d:

score(t, d) = IDF(t) * (tf(t, d) * (k1 + 1)) / (tf(t, d) + k1 * (1 - b + b * |d| / avgdl))

where tf(t, d) is the term frequency in d, |d| is the document length, avgdl is the average document length across the corpus, k1 controls term frequency saturation (typically 1.2–2.0), and b controls length normalization (typically 0.75). IDF(t) — inverse document frequency — gives rare terms more weight than common ones. Robertson and Zaragoza formalized this in the Okapi BM25 family; it remains the strongest unsupervised lexical baseline after three decades.

Where lexical beats dense

Dense retrieval excels at paraphrase matching and semantic similarity. Sparse retrieval excels at precision on exact tokens. The failure modes from L8 — identifiers, rare terms, negation — are exactly where BM25 succeeds:

Exact identifiers. "error code E-4012" matches documents containing the literal string "E-4012." BM25 treats it as a rare term (high IDF), so documents containing it rank high.
Rare proper nouns. "Kagra interferometer" — BM25 finds every document mentioning "Kagra" regardless of whether the embedding model has ever seen the word.
Acronyms and codes. "HNSW", "pgvector", "AX-7890-B" — any token that appears in few documents gets a high IDF weight and matches precisely.

BM25 also has failure modes that dense retrieval handles: it misses synonyms ("car" vs. "automobile"), cannot match paraphrases ("how to fix" vs. "troubleshooting steps"), and is blind to meaning beyond surface tokens.

Neither retrieval method dominates. They fail on complementary query types. This is why hybrid search works.

BM25 retrieval in Python

from rank_bm25 import BM25Okapi

corpus = [
    "error code E-4012 indicates a connection timeout on the gateway",
    "error code E-5033 means the API key has expired or is invalid",
    "HNSW builds a multi-layer navigable small world graph for ANN search",
    "troubleshooting connection timeouts in distributed systems",
    "the Kagra interferometer detects gravitational waves in Kamioka, Japan",
]

tokenized_corpus = [doc.lower().split() for doc in corpus]
bm25 = BM25Okapi(tokenized_corpus)

query = "error code E-4012"
tokenized_query = query.lower().split()
scores = bm25.get_scores(tokenized_query)

ranked = sorted(enumerate(scores), key=lambda x: x[1], reverse=True)
for idx, score in ranked[:3]:
    print(f"[{score:.2f}] {corpus[idx][:80]}")

BM25 ranks the E-4012 document first with a high score. The E-5033 document scores lower — it shares "error" and "code" but not the specific identifier. Dense retrieval, as shown in L8, would score these two documents nearly identically.

Hybrid search: combining dense and sparse

Hybrid search runs both a dense retriever and a sparse retriever, then merges their ranked results. The simplest merge strategy is Reciprocal Rank Fusion (RRF), introduced by Cormack, Clarke, and Buettcher.

RRF assigns each document a score based on its rank position in each result list, not its raw score. This avoids the calibration problem — dense cosine similarities and BM25 scores are on incompatible scales, so averaging them directly is meaningless.

The RRF formula:

RRF(d) = sum(1 / (k + rank_i(d))) for each ranking i that contains document d

where k is a constant (typically 60) that dampens the influence of high ranks. A document ranked 1st in one list and 5th in another gets 1/(60+1) + 1/(60+5) = 0.01639 + 0.01538 = 0.03177. A document ranked 1st in both gets 1/61 + 1/61 = 0.03279. The gap is small — RRF rewards documents that appear in multiple lists more than documents that rank extremely high in just one.

Full hybrid retrieval implementation

from rank_bm25 import BM25Okapi
from openai import OpenAI
import numpy as np
import psycopg2

client = OpenAI()

def dense_search(query: str, conn, k: int = 20) -> list[dict]:
    vec = client.embeddings.create(
        input=[query], model="text-embedding-3-small"
    ).data[0].embedding

    with conn.cursor() as cur:
        cur.execute("""
            SELECT id, content, 1 - (embedding <=> %s::vector) AS score
            FROM chunks
            ORDER BY embedding <=> %s::vector
            LIMIT %s
        """, [vec, vec, k])
        return [{"id": r[0], "content": r[1], "score": r[2]} for r in cur.fetchall()]

def sparse_search(
    query: str, corpus_texts: list[str], corpus_ids: list[int], k: int = 20,
) -> list[dict]:
    tokenized = [doc.lower().split() for doc in corpus_texts]
    bm25 = BM25Okapi(tokenized)
    scores = bm25.get_scores(query.lower().split())
    top_k = np.argsort(scores)[-k:][::-1]
    return [
        {"id": corpus_ids[i], "content": corpus_texts[i], "score": float(scores[i])}
        for i in top_k if scores[i] > 0
    ]

def reciprocal_rank_fusion(
    *ranked_lists: list[dict],
    k: int = 60,
) -> list[dict]:
    rrf_scores: dict[int, float] = {}
    doc_content: dict[int, str] = {}

    for ranked_list in ranked_lists:
        for rank, doc in enumerate(ranked_list, start=1):
            doc_id = doc["id"]
            rrf_scores[doc_id] = rrf_scores.get(doc_id, 0.0) + 1.0 / (k + rank)
            doc_content[doc_id] = doc["content"]

    fused = sorted(rrf_scores.items(), key=lambda x: x[1], reverse=True)
    return [
        {"id": doc_id, "content": doc_content[doc_id], "rrf_score": score}
        for doc_id, score in fused
    ]

def hybrid_retrieve(query: str, conn, corpus_texts, corpus_ids, k: int = 5):
    dense_results = dense_search(query, conn, k=20)
    sparse_results = sparse_search(query, corpus_texts, corpus_ids, k=20)
    fused = reciprocal_rank_fusion(dense_results, sparse_results)
    return fused[:k]

Note that the BM25 index is rebuilt per query in this example for clarity. In production, build it once at startup and reuse it, or use a database with built-in BM25 support (Elasticsearch, pgvector with pg_trgm, or a dedicated store like Weaviate with hybrid mode).

The query that proves the point

Consider a corpus of technical documentation and three retrieval approaches on the same query:

query = "error code E-4012 connection timeout"

dense_only = dense_search(query, conn, k=5)
sparse_only = sparse_search(query, corpus_texts, corpus_ids, k=5)
hybrid = hybrid_retrieve(query, conn, corpus_texts, corpus_ids, k=5)

Dense retrieval returns chunks about connection timeouts in general — semantically relevant, but misses the specific error code document because "E-4012" and "E-5033" embed to nearly identical vectors.

BM25 returns the exact E-4012 document at rank 1 (high IDF on "E-4012"), plus generic chunks that mention "error" and "connection" without addressing timeouts in the relevant context.

Hybrid fusion promotes the E-4012 document (ranked high by BM25) and the best timeout-explanation chunks (ranked high by dense), giving the generator both the specific error reference and the conceptual explanation.

Anthropic's benchmarks on hybrid retrieval

Anthropic's Contextual Retrieval benchmarks (Anthropic 2024) quantified this effect across multiple knowledge bases:

Embeddings alone — baseline retrieval failure rate (percentage of queries where the relevant chunk was not in the top 20)
Embeddings + BM25 (hybrid) — 49% reduction in retrieval failure rate vs. embeddings alone
Embeddings + BM25 + reranking — 67% reduction in retrieval failure rate vs. embeddings alone

The gains come precisely from the complementary failure modes: BM25 catches the exact-match queries that dense misses, and dense catches the paraphrase queries that BM25 misses. Adding a reranker on top (covered in L11) further improves precision by rescoring the merged set with a cross-encoder.

Tuning hybrid search

The main knobs:

RRF `k` constant. Higher values (e.g., 100) flatten the rank differences, giving more weight to documents that appear in both lists. Lower values (e.g., 20) amplify rank differences, favoring whichever list ranked a document highest. The standard value of 60 is a reasonable default; tune on labeled data if you have it.
Per-retriever `k`. Retrieve more candidates from each method (e.g., top-20 from each) before fusion, then return top-5 after RRF. This gives the fusion more signal to work with.
Weighted RRF. Multiply each retriever's contribution by a weight: w_dense / (k + rank_dense) + w_sparse / (k + rank_sparse). If your queries are mostly paraphrase-style, increase w_dense. If they frequently contain identifiers or codes, increase w_sparse. Start at equal weights and adjust based on retrieval evaluation.

Key takeaways

BM25 scores documents by exact term overlap weighted by term rarity (IDF). It excels on identifiers, rare terms, and exact matches — precisely where dense retrieval fails.
Neither dense nor sparse retrieval dominates. They fail on complementary query types, making hybrid search strictly better than either alone for general-purpose RAG.
Reciprocal Rank Fusion merges ranked lists by position, not raw score, sidestepping the score-calibration problem. RRF(d) = sum(1 / (k + rank_i(d))) with k=60 is the standard default.
Anthropic's benchmarks show hybrid retrieval (embeddings + BM25) reduces top-20 retrieval failure by 49% vs. embeddings alone. Adding a reranker brings that to 67%.
Build BM25 once at startup, not per query. In production, use a store with built-in hybrid support or maintain a parallel BM25 index alongside your vector index.

← Previous