Advanced Retrieval: Hybrid Search, Reranking and Query Rewriting

A basic RAG pipeline embeds the question, takes the top five chunks, and hopes. Production systems do much better by combining several retrievers, re-scoring candidates with stronger models, rewriting questions before searching, and measuring all of it with proper ranking metrics. These techniques are the difference between a demo and a system people trust, and they are standard in search engineering, long predating LLMs.

The picture: a funnel with specialists

Think of hiring. A recruiter skims thousands of CVs with keyword filters (fast, literal), a second recruiter skims them for overall fit (fast, fuzzy), their shortlists are merged, and then an expert interviewer spends real time on the top 50 (slow, accurate). Advanced retrieval is the same funnel: cheap, high-recall first-stage retrievers (sparse and dense) produce candidates, fusion merges their lists, and an expensive, high-precision reranker orders the final few. Query rewriting is the step before the funnel: making sure the job description itself is well written.

Sparse retrieval and BM25

Sparse retrieval represents texts as vectors over the vocabulary, where almost all entries are zero, and stores them in an inverted index: for each term, the list of documents containing it. It matches exact tokens, which makes it strong on names, codes, numbers and rare jargon, and needs no training.

BM25 (Robertson and colleagues, from the probabilistic relevance framework developed through the 1970s to 1990s) is the standard scoring function. For a query $Q$ with terms $q_1,\dots,q_n$ and a document $D$:

where $f(q_i,D)$ is the number of times $q_i$ occurs in $D$, $|D|$ is the document length in tokens, $\text{avgdl}$ is the average document length in the collection, $k_1$ (typically 1.2 to 2.0) controls term-frequency saturation, and $b$ (typically 0.75) controls length normalization. A common IDF (used by Lucene) is

with $N$ the number of documents and $n(q)$ the number containing $q$. Intuition: rare terms are worth more (IDF); the tenth occurrence of a word adds much less than the first (saturation through $k_1$); and a match in a short document counts more than in a long one (normalization through $b$).

Worked example. Four documents, query "cheap paris", $k_1 = 1.2$, $b = 0.75$:

• D1 "cheap flights to paris" (4 tokens)
• D2 "paris hotel deals and cheap paris tours" (7 tokens)
• D3 "flights and hotels in paris" (5 tokens)
• D4 "weather in london" (3 tokens)

$\text{avgdl} = (4+7+5+3)/4 = 4.75$. "cheap" is in 2 documents: $\text{IDF} = \ln(2.5/2.5 + 1) = \ln 2 = 0.693$. "paris" is in 3: $\text{IDF} = \ln(1.5/3.5 + 1) = \ln 1.4286 = 0.357$.

Let $K_D = k_1(1 - b + b|D|/\text{avgdl})$. For D1: $K = 1.2(0.25 + 0.75 \times 4/4.75) = 1.058$. Each term occurs once, so cheap contributes $0.693 \times 2.2 / 2.058 = 0.741$ and paris $0.357 \times 2.2/2.058 = 0.381$; total 1.122.

For D2: $K = 1.2(0.25 + 0.75 \times 7/4.75) = 1.626$. Cheap: $0.693 \times 2.2/2.626 = 0.581$. Paris occurs twice: $0.357 \times 2 \times 2.2 / 3.626 = 0.433$. Total 1.013.

For D3: $K = 1.247$; only paris: $0.357 \times 2.2/2.247 =$ 0.349. D4 scores 0.

D2 mentions paris twice yet ranks below D1: saturation limits the reward for repetition and D2 is longer than average. Here is the same computation in code:

import math
from collections import Counter

def bm25_scores(query, docs, k1=1.2, b=0.75):
    toks = [d.lower().split() for d in docs]
    N = len(toks)
    avgdl = sum(len(t) for t in toks) / N
    df = Counter(term for t in toks for term in set(t))   # document frequency
    scores = []
    for t in toks:
        tf, s = Counter(t), 0.0
        for q in query.lower().split():
            if q not in tf:
                continue
            idf = math.log((N - df[q] + 0.5) / (df[q] + 0.5) + 1)
            norm = k1 * (1 - b + b * len(t) / avgdl)         # length normalization
            s += idf * tf[q] * (k1 + 1) / (tf[q] + norm)
        scores.append(s)
    return scores

docs = ["cheap flights to paris", "paris hotel deals and cheap paris tours",
        "flights and hotels in paris", "weather in london"]
print([round(s, 3) for s in bm25_scores("cheap paris", docs)])
# [1.122, 1.013, 0.349, 0.0]

Real systems add tokenization, stemming, stop words and an inverted index so that only documents containing a query term are scored. Learned sparse models (for example SPLADE) use a transformer to assign weights to vocabulary terms, including expansion terms not literally present, keeping the inverted-index efficiency while adding some semantic matching.

Dense retrieval

Dense retrieval uses a bi-encoder: one transformer encodes the query, one (often the same) encodes each passage, independently, into vectors compared by dot product or cosine (Karpukhin et al.'s Dense Passage Retrieval, 2020, is the classic reference). Because passages are encoded independently of the query, their vectors are computed once and indexed with ANN. Dense retrieval handles paraphrase and synonyms ("car" matches "automobile") but can miss exact identifiers and degrade on domains far from its training data.

Hybrid search and reciprocal rank fusion

Sparse and dense retrievers make different mistakes, so combining them generally improves recall. The difficulty is that their scores live on incomparable scales (BM25 is unbounded; cosine is in $[-1, 1]$). Two families of fusion:

• Score fusion: normalize each retriever's scores (for example min-max within the result list) and take a weighted sum $\alpha s_\text{dense} + (1-\alpha) s_\text{sparse}$. Flexible, but sensitive to the normalization and needs $\alpha$ tuned.
• Rank fusion: ignore scores, use only ranks. Reciprocal rank fusion (RRF; Cormack, Clarke and Büttcher, SIGIR 2009) scores each document $d$ as

where $R$ is the set of ranked lists, $\text{rank}_r(d)$ is $d$'s 1-based position in list $r$ (a document missing from a list contributes nothing for it), and $k$ is a smoothing constant, $60$ in the original paper. A large $k$ flattens the difference between rank 1 and rank 5, so consistent presence across lists beats a single top placement.

Worked example. BM25 returns $[A, B, C, D]$; dense returns $[C, A, E, B]$. With $k = 60$:

Fused order: A, C, B, E, D. A wins by being near the top of both lists; E and D, each found by one retriever only, fall to the bottom.

from collections import Counter

def rrf(rankings, k=60):
    fused = Counter()
    for ranking in rankings:                     # each: doc ids, best first
        for rank, doc in enumerate(ranking, start=1):
            fused[doc] += 1.0 / (k + rank)
    return fused.most_common()

print(rrf([["A", "B", "C", "D"], ["C", "A", "E", "B"]]))
# [('A', 0.0325...), ('C', 0.0322...), ('B', 0.0317...), ('E', 0.0158...), ('D', 0.0156...)]

RRF needs no training and no score calibration, which is why it is the default fusion in many search engines and vector databases.

Cross-encoder reranking

A cross-encoder feeds the query and one passage together into a transformer, so every query token can attend to every passage token, and outputs a single relevance score (Nogueira and Cho's 2019 BERT passage re-ranker established the approach). This joint reading is far more accurate than comparing two independently computed vectors, but it cannot be precomputed: scoring $N$ passages costs $N$ full forward passes. Hence the funnel: retrieve 50 to 200 candidates cheaply, rerank them with the cross-encoder, keep the top 5 to 10.

from sentence_transformers import CrossEncoder

reranker = CrossEncoder("cross-encoder/ms-marco-MiniLM-L-6-v2")
query = "How long is parental leave?"
candidates = ["Employees receive 16 weeks of paid parental leave.",
              "Sick leave is ten days per year.",
              "Leave requests go through the HR portal."]
scores = reranker.predict([(query, c) for c in candidates])
for score, text in sorted(zip(scores, candidates), reverse=True):
    print(f"{score:7.2f}  {text}")

Rerankers are also available as hosted APIs and as LLM-based rerankers (prompting an LLM to score or order passages), which are more expensive but can follow instructions such as "prefer the most recent policy". Measure the latency: reranking 100 passages adds a noticeable delay, so tune the candidate count.

Query rewriting and expansion

User questions are often short, ambiguous, conversational ("what about for contractors?") or phrased differently from the documents. Rewriting happens before retrieval:

• Conversational rewriting: an LLM turns the latest turn plus chat history into a standalone query ("What is the parental leave policy for contractors?"). Essential for chat interfaces.
• Expansion: add synonyms, acronyms expanded, related terms; classic in BM25 systems (pseudo-relevance feedback adds terms from the top initial results).
• HyDE (Hypothetical Document Embeddings): Gao, Ma, Lin and Callan (2022) proposed asking an instruction-following LLM to write a hypothetical document that answers the query, then embedding that document and using its vector for retrieval. The fake answer may contain wrong facts, but it is shaped like a real answer, so it lands near real answers in embedding space; the encoder's bottleneck filters out much of the hallucinated detail. Their experiments used it for zero-shot retrieval with an unsupervised dense encoder (Contriever) and no relevance labels. Costs: an LLM call before every search, and possible drift when the LLM knows little about your private domain.
• Step-back and decomposition: ask the LLM for a more general question ("what are the leave policies?") or split a compound question into sub-questions retrieved separately.

Multi-query retrieval

Generate several paraphrases of the question (say 3 to 5), retrieve for each, and fuse the lists with RRF. This raises recall because different phrasings hit different relevant chunks, at the cost of several retrievals and one LLM call. Combining multi-query with RRF is sometimes called RAG-Fusion.

ColBERT and late interaction

Between bi-encoders (fast, coarse) and cross-encoders (slow, precise) sits late interaction. ColBERT (Khattab and Zaharia, 2020) encodes query and passage independently, like a bi-encoder, but keeps one vector per token instead of pooling to a single vector. Relevance is the MaxSim sum: for each query token, find its best-matching passage token, and add up those maxima:

where $\mathbf{e}_{q_i}$ and $\mathbf{e}_{p_j}$ are the normalized token embeddings.

Worked example. Query token embeddings $\mathbf{e}_{q_1} = (1, 0)$, $\mathbf{e}_{q_2} = (0.6, 0.8)$; passage tokens $(0.8, 0.6)$, $(0, 1)$, $(1, 0)$. For $q_1$ the dot products are $0.8, 0, 1$, maximum$1$. For$q_2$ they are $0.96, 0.8, 0.6$, maximum$0.96$. Score$= 1.96$.

Because passage token vectors are precomputed, late interaction scales to large collections while keeping fine-grained term matching. The price is storage: one vector per token rather than per passage, which ColBERTv2 (Santhanam et al., 2021) reduced with residual compression. Late-interaction models are used both as first-stage retrievers and as rerankers.

Filtering

Apply hard constraints (permissions, tenant, date, document type) inside every retriever, before fusion and reranking, so that disallowed content never becomes a candidate. Filters also improve quality: restricting to "current policies" removes superseded versions that would otherwise compete. An LLM can extract filters from the question ("contracts signed in 2025" becomes a date filter plus a query), a pattern often called self-querying; validate the extracted filters against a schema.

Retrieval metrics

Evaluate retrieval separately from generation. You need a set of queries with relevance judgments (human labels, or carefully reviewed LLM labels). Let $\text{rel}_i$ be the relevance of the result at rank $i$.

• Recall@k: fraction of all relevant documents for the query that appear in the top $k$. Most important for RAG, because the generator cannot use what was not retrieved.
• Precision@k: fraction of the top $k$ that are relevant.
• MRR (mean reciprocal rank): for each query, $1/\text{rank}$ of the first relevant result (0 if none), averaged over queries. Good when one right answer suffices.
• nDCG@k (normalized discounted cumulative gain): handles graded relevance and rewards putting the best results first.

where IDCG is the DCG of the ideal ordering of the relevant documents. (A common variant uses gain $2^{\text{rel}_i} - 1$ to emphasize highly relevant results; state which you use.)

Worked example. For one query, the collection has four relevant documents with grades 3, 2, 2, 1. The system returns five results with grades $[2, 0, 3, 0, 1]$.

• Recall@5: three of four relevant documents retrieved, $3/4 = 0.75$. Precision@5 $= 3/5 = 0.6$.
• Reciprocal rank: first relevant at rank 1, so $1.0$. If two other queries had their first relevant hit at rank 3 and nowhere, MRR $= (1 + 1/3 + 0)/3 = 0.444$.
• DCG@5 $= 2/1 + 0 + 3/\log_2 4 + 0 + 1/\log_2 6 = 2 + 1.5 + 0.387 = 3.887$.
• Ideal order $[3, 2, 2, 1, 0]$: IDCG@5 $= 3/1 + 2/1.585 + 2/2 + 1/2.322 = 3 + 1.262 + 1 + 0.431 = 5.693$.
• nDCG@5 $= 3.887 / 5.693 = 0.683$.

The best document (grade 3) at rank 3 instead of rank 1, and one relevant document missing, cost about a third of the ideal score.

Common pitfalls

• Skipping BM25. Dense-only systems fail on product codes, names and error strings that users type verbatim.
• Fusing raw scores from different retrievers without normalization.
• Reranking too few candidates (the reranker cannot rescue what was not retrieved) or too many (latency explodes).
• Evaluating only end-to-end answers, so you cannot tell whether a failure came from retrieval or generation.
• Tiny or synthetic-only test sets. Fifty real, labelled queries beat a thousand generated ones you never inspected.
• Over-rewriting: an LLM rewrite that changes the meaning of the question, or HyDE on a private domain the LLM knows nothing about.
• Applying filters after reranking, wasting reranker budget and risking leaks.

In practice

• A strong default pipeline: conversational rewrite, then BM25 and dense retrieval (about 50 candidates each) with permission filters, RRF fusion, cross-encoder reranking of the top 50 to 100, and the top 5 to 10 passed to the generator.
• Add multi-query, HyDE or late interaction only when evaluation shows a recall gap they close.
• Track recall@k for the first stage and nDCG@10 after reranking on a fixed, versioned query set; rerun it on every change to chunking, models or parameters.
• Budget latency explicitly: rewriting (one LLM call), retrieval (tens of milliseconds), reranking (tens to hundreds of milliseconds), generation (seconds).