Core Retrieval Algorithms

Ask How do I rotate an API key? and search might return the quota dashboard instead of the rotation steps. The model then writes a confident answer about daily rate limits. The prose is fluent. The evidence for rotation never reached the prompt.

In Clustering and PCA, we examined geometry in vector spaces and compared cosine similarity with dot products. The EM clustering walkthrough grouped unlabeled observations into latent Gaussian mixtures. Retrieval tackles an operational challenge: given millions of documentation chunks, which specific passages contain the factual evidence to answer an arbitrary developer query?

Four passages are small enough to check every ranking by hand. The quota page shares the words API key. The paraphrase that actually describes rotation does not. Before a score can prefer one of them, search has to decide which words count as a match.

One question, four possible sources

Here's the developer question:

How do I rotate an API key?

Start with this invented four-passage corpus. The relevance labels below are our teaching judgments, not annotations from a real user study. The snippets describe a generic rotation story; an actual assistant would need the provider's current procedure, credential type, and access rules.

The gap between d2 and d4 highlights the central challenge of search. Passage d4 shares literal vocabulary (API key), yet it's completely unhelpful for rotation. Meanwhile, d2 directly answers how to rotate credentials without using the exact phrase API key.

Relevance judgments must address the question. In real documentation, also check whether the passage applies to the user's product version and permissions. Broad topical similarity doesn't establish that.

View larger

Sparse retrieval starts with an inverted index

Classical lexical search represents documents by terms. An inverted index maps each indexed term to a posting list of document identifiers containing it. Lists are commonly ordered by document ID and may also store frequencies and positions.^{[1]Reference 1Introduction to Information Retrieval.https://nlp.stanford.edu/IR-book/}

Compression can store gaps between consecutive IDs, then encode those integers with a method such as variable-byte coding. Gap formation and integer encoding are separate steps.

A straightforward OR query visits the query terms' posting lists rather than reading every passage. Its posting traversal work is $O(\sum_{t \in Q} |\text{postings}(t)|)$, excluding analysis, decoding, and top-$K$ selection. Common terms can still touch most documents; optimized query execution may skip postings or blocks.

For technical search, inspect what the analyzer does to identifiers. Our regex turns AUTH_401 into auth and splits rotate_api_key() into three words. That loses the distinction between error codes sharing a prefix. A production schema might preserve the full identifier in a keyword field and index its parts in a text field. Test both exact-symbol queries and ordinary wording.

For this walkthrough, tokenization lowercases text, extracts alphabetic runs, and removes a small stopword list. It has no stemming or synonym expansion.

Our test query filters down to three terms: rotate, api, and key. The script below builds the inverted index and prints each term's posting list. Notice: rotate matches nothing because our passage used rotation, while api and key point only to d1 and d4.

Before running it, predict what happens if the query becomes AUTH_401 and a passage contains only AUTH_403. Both collapse to auth with this regex. A lexical match can be exact relative to analyzed tokens while losing the original identifier's meaning.

import re
from collections import defaultdict

docs = {
    "d1": "API key rotation guide. Create a replacement key, deploy it, then revoke the old key.",
    "d2": "Generate a new credential before disabling the previous credential.",
    "d3": "Change a project display name in workspace settings.",
    "d4": "API key quota dashboard. Usage limits reset daily.",
}
query = "How do I rotate an API key?"
stopwords = {"a", "an", "and", "do", "for", "how", "i", "in", "it", "the", "then", "to", "your"}

def tokenize(text: str) -> list[str]:
    return [word for word in re.findall(r"[a-z]+", text.lower()) if word not in stopwords]

postings = defaultdict(list)
for doc_id, passage in docs.items():
    for term in sorted(set(tokenize(passage))):
        postings[term].append(doc_id)

query_terms = tokenize(query)
print("query terms:", query_terms)
for term in query_terms:
    print(f"{term:6} -> {postings[term]}")
assert query_terms == ["rotate", "api", "key"]
assert postings["rotate"] == []
assert postings["api"] == ["d1", "d4"]
assert "d2" not in postings["key"]

query terms: ['rotate', 'api', 'key']
rotate -> []
api    -> ['d1', 'd4']
key    -> ['d1', 'd4']

Passage d2 is relevant under our labels but absent from all three posting lists. This is a vocabulary mismatch in this analyzer. Lexical systems can use stemming and explicit synonym/query expansion; BM25's scoring formula doesn't supply those transformations itself.^{[1]Reference 1Introduction to Information Retrieval.https://nlp.stanford.edu/IR-book/}

BM25 scores lexical evidence

Once candidate documents are identified from posting lists, how should we score them?

In d1, api appears once and key three times. Using raw frequency in $TF \times IDF$ would triple that term's weight when its count triples, with IDF fixed. That's a scoring rule, not three times the relevance. TF-IDF has other variants, including logarithmic frequency and document normalization, so linear frequency isn't a defining property of every TF-IDF ranker.^{[1]Reference 1Introduction to Information Retrieval.https://nlp.stanford.edu/IR-book/}

Okapi BM25 combines term-frequency saturation with document-length normalization.^{[2]Reference 2Okapi at TREC-3.https://trec.nist.gov/pubs/trec3/t3_proceedings.html[3]Reference 3The Probabilistic Relevance Framework: BM25 and Beyond.https://doi.org/10.1561/1500000019} We'll use this common textbook form for the contribution of query term $t$ in document $d$:

Here, $f(t, d)$ is the count of term $t$ in document $d$, $|d|$ is the token length of document $d$, and $\mathrm{avgdl}$ is the average document length across the corpus. The formula relies on two parameters:

1. Term-frequency saturation ($k_1 \ge 0$): With the length factor held fixed and positive, the fractional term tends to $k_1+1$ as frequency grows. Lower $k_1$ reduces the benefit of repetition. At $k_1=0$, a present term has weight 1; $k_1=0.5$ still rewards repetitions. Absent terms contribute zero.
2. Length normalization ($0 \le b \le 1$): With frequency fixed, $b=0$ ignores length and $b=1$ uses $|d|/\mathrm{avgdl}$ as the length factor. This adjusts term frequency relative to document length; it doesn't judge comprehensiveness.

Lucene 10.5.1 defaults to $k_1=1.2$ and $b=0.75$, checked September 21, 2026.^{[4]Reference 4BM25Similarity: Apache Lucene 10.5.1https://lucene.apache.org/core/10_5_1/core/org/apache/lucene/search/similarities/BM25Similarity.html} Our scores aren't exact Lucene outputs: that implementation omits the numerator's $k_1+1$ factor and encodes length norms. Omitting the factor alone preserves rankings when $k_1$ is shared, but changes raw scores by a factor of 2.2 here.^{[5]Reference 5BM25Similarity implementation, Lucene 10.5.1https://github.com/apache/lucene/blob/releases/lucene/10.5.1/lucene/core/src/java/org/apache/lucene/search/similarities/BM25Similarity.java}

An IDF form associated with Robertson-Spärck Jones weighting, without known relevance-feedback counts, is $\log((N-\mathrm{df}+0.5)/(\mathrm{df}+0.5))$. It becomes negative when a term appears in more than half the documents. Lucene uses a positive variant:

$N$ is the total document count and $\mathrm{df}(t)$ counts documents containing term $t$.

Computing BM25 scores illustrates the length factor in practice. After stopword removal, d1 has 11 tokens, and the four passages average 8 tokens ($\mathrm{avgdl} = 8$). For api in d1, $\mathrm{df} = 2$ and $f = 1$. With $N = 4$:

The length normalization factor is $1 - 0.75 + 0.75 \cdot (11 / 8) = 1.28125$. Plugging these into the formula yields $0.601$. Repeating this for key ($f = 3$) gives $1.008$. The total BM25 score for d1 is $0.601 + 1.008 = 1.609$.

The three occurrences of key contribute $1.008$ compared to api's $0.601$. Tripling the word count didn't triple the score.

The script below scores all passages and sorts the candidate list.

import math
import re
from collections import Counter

docs = {
    "d1": "API key rotation guide. Create a replacement key, deploy it, then revoke the old key.",
    "d2": "Generate a new credential before disabling the previous credential.",
    "d3": "Change a project display name in workspace settings.",
    "d4": "API key quota dashboard. Usage limits reset daily.",
}
query = "How do I rotate an API key?"
stopwords = {"a", "an", "and", "do", "for", "how", "i", "in", "it", "the", "then", "to", "your"}

def tokenize(text: str) -> list[str]:
    return [word for word in re.findall(r"[a-z]+", text.lower()) if word not in stopwords]

tokens = {doc_id: tokenize(text) for doc_id, text in docs.items()}
query_terms = tokenize(query)
average_length = sum(len(row) for row in tokens.values()) / len(tokens)
document_frequency = Counter(term for row in tokens.values() for term in set(row))

def bm25(doc_id: str, k1: float = 1.2, b: float = 0.75) -> float:
    score = 0.0
    counts = Counter(tokens[doc_id])
    for term in query_terms:
        frequency = counts[term]
        if frequency == 0:
            continue
        df = document_frequency[term]
        idf = math.log(1 + (len(docs) - df + 0.5) / (df + 0.5))
        denominator = frequency + k1 * (1 - b + b * len(tokens[doc_id]) / average_length)
        score += idf * frequency * (k1 + 1) / denominator
    return score

ranking = sorted(((doc_id, bm25(doc_id)) for doc_id in docs), key=lambda item: (-item[1], item[0]))
assert ranking[0][0] == "d1"
assert ranking[1][0] == "d4"
assert ranking[2][1] == 0.0
for rank, (doc_id, score) in enumerate(ranking, start=1):
    print(f"#{rank} {doc_id}: {score:.3f}")
sparse_candidates = [doc_id for doc_id, score in ranking if score > 0]
assert sparse_candidates == ["d1", "d4"]
print("matching candidates:", sparse_candidates)

#1 d1: 1.609
#2 d4: 1.386
#3 d2: 0.000
#4 d3: 0.000
matching candidates: ['d1', 'd4']

BM25 ranks d1 first ($1.609$) and d4 second ($1.386$). Documents d2 and d3 score zero because they contain no query terms.

BM25 puts the quota dashboard above the credential guide because only the former matches our query tokens. You could investigate analyzer expansion or introduce a dense lane. We'll try the latter; neither change should be accepted without relevance evaluation.

Repetition saturates instead of winning automatically

Isolating the saturation factor clarifies how $k_1$ behaves. Holding document length and IDF constant ($|d| = \mathrm{avgdl}$), the term weight simplifies to:

For $k_1 = 1.2$, the upper bound as frequency climbs is $k_1 + 1 = 2.2$. The next lab traces how the curve flattens as word frequency increases from 1 to 20:

def term_weight(frequency: int, k1: float = 1.2) -> float:
    return frequency * (k1 + 1) / (frequency + k1)

limit = 1.2 + 1
for frequency in (1, 2, 4, 20):
    weight = term_weight(frequency)
    remaining = limit - weight
    print(f"api count={frequency:2}: tf weight={weight:.3f} gap to limit={remaining:.3f}")

api count= 1: tf weight=1.000 gap to limit=1.200
api count= 2: tf weight=1.375 gap to limit=0.825
api count= 4: tf weight=1.692 gap to limit=0.508
api count=20: tf weight=2.075 gap to limit=0.125

The first occurrence has weight $1.000$; the twentieth reaches $2.075$, still below $2.200$. This isolates saturation by fixing the length factor. Repeating words in an actual document also changes its length and potentially corpus statistics. BM25 limits the benefit of repetition. An irrelevant page can still outrank a useful one, and a relevant paraphrase can score zero.

Dense retrieval recovers paraphrases

d2 never entered the posting lists, because the paraphrase shares no analyzed query term. A second representation can still place that passage near the question when their vectors point the same way.

Dense retrieval represents queries and passages as continuous vectors in $\mathbb{R}^D$ using neural bi-encoders.^{[6]Reference 6Dense Passage Retrieval for Open-Domain Question Answering.https://arxiv.org/abs/2004.04906}

A bi-encoder computes a query representation $E_Q(q)$ and a passage representation $E_D(d)$ independently. The two encoders may share weights or use different ones; DPR uses two independent BERT encoders. Passage vectors can be precomputed because they don't depend on the incoming query. At runtime, encode the query and search the index using the model's scoring contract.

Here are hand-chosen 3D vectors. Their coordinates deliberately place the query near the credential guide. These coordinates demonstrate ranking geometry; evaluate a model's ability to understand passages with judged queries:

Cosine similarity measures the angle between vectors, normalizing out differences in vector length:

For d2, the dot product is $1.0(0.9)+0.8(0.9)=1.62$. Dividing by $\sqrt{1.64}\sqrt{1.62}\approx1.6300$ gives approximately $0.994$. The vector directions are nearly aligned. Whether a trained encoder maps an unseen paraphrase this well is a separate empirical question.

import math

vectors = {
    "query": [1.0, 0.8, 0.0],
    "d1": [1.0, 0.4, 0.0],
    "d2": [0.9, 0.9, 0.0],
    "d3": [0.0, 0.2, 1.0],
    "d4": [0.4, 0.0, 0.3],
}

def dot(left: list[float], right: list[float]) -> float:
    if len(left) != len(right):
        raise ValueError("vector dimensions must match")
    return sum(a * b for a, b in zip(left, right))

def l2(vector: list[float]) -> float:
    return math.sqrt(dot(vector, vector))

def cosine(left: list[float], right: list[float]) -> float:
    numerator = dot(left, right)
    denominator = l2(left) * l2(right)
    if denominator == 0:
        raise ValueError("cosine is undefined for a zero vector")
    return numerator / denominator

ranking = sorted(
    ((doc_id, cosine(vectors["query"], vector)) for doc_id, vector in vectors.items() if doc_id != "query"),
    key=lambda item: (-item[1], item[0]),
)
assert ranking[0][0] == "d2"
assert abs(ranking[0][1] - 0.994) < 0.001
for rank, (doc_id, score) in enumerate(ranking, start=1):
    print(f"#{rank} {doc_id}: {score:.3f}")

#1 d2: 0.994
#2 d1: 0.957
#3 d4: 0.625
#4 d3: 0.123

In this chosen geometry, d2 ranks first ($0.994$), d1 second ($0.957$), and d4 third ($0.625$). Unlike the token matcher, this vector comparison includes d2. A real encoder's ranking still needs measurement.

Similarity must match the embedding contract

If vectors are unit-normalized ($\lVert v \rVert_2 = 1$), dot product and cosine similarity produce the exact same rank order because the denominator is always $1.0$.

Without normalization, dot product multiplies angular alignment by the vector norms. For positive alignment, a larger document norm can raise the score and overturn cosine's ordering. Assume our desired contract is directional similarity and compare:

import math

query = [1.0, 0.8, 0.0]
candidates = {
    "aligned_paraphrase": [1.0, 0.8, 0.0],
    "large_partial_match": [6.0, 0.0, 0.0],
}

def dot(left: list[float], right: list[float]) -> float:
    return sum(a * b for a, b in zip(left, right))

def l2(vector: list[float]) -> float:
    return math.sqrt(dot(vector, vector))

dot_ranking = sorted(candidates, key=lambda name: -dot(query, candidates[name]))
cosine_ranking = sorted(
    candidates,
    key=lambda name: -dot(query, candidates[name]) / (l2(query) * l2(candidates[name])),
)

assert dot_ranking[0] == "large_partial_match"
assert cosine_ranking[0] == "aligned_paraphrase"
print("dot-product winner:", dot_ranking[0])
print("cosine winner:     ", cosine_ranking[0])

dot-product winner: large_partial_match
cosine winner:      aligned_paraphrase

The dot product with large_partial_match is $6.0$, exceeding aligned_paraphrase's $1.64$. Cosine removes vector magnitude and picks the aligned vector. That's appropriate for our stipulated directional contract; it doesn't make cosine universally better.

Check the embedding model's intended score. Cosine requires nonzero vectors; zero vectors need an explicit policy. With documents normalized to a common positive norm, inner product and cosine give the same ordering for a fixed nonzero query. With varying document norms, they may disagree. Models trained for inner product, including DPR, can intentionally retain magnitude.^{[6]Reference 6Dense Passage Retrieval for Open-Domain Question Answering.https://arxiv.org/abs/2004.04906}

Fuse independent retrieval lanes

The hybrid hope only works if the two lists can be combined without one score scale drowning the other:

• Lexical BM25: Often useful for selective terms and identifiers when analysis preserves them. Unexpanded wording can miss paraphrases.
• Dense bi-encoders: Can retrieve lexical variations and related meaning. Exact identifiers and qualifiers need evaluation too; their treatment depends on the model and training data.

Hybrid pipelines combine these signals. In our fixture, take the positive-score sparse results and the first three dense results:

How should we combine these results?

Cosine lies in $[-1,1]$. BM25 has no universal scale shared across queries, corpora, boosts, and settings. It isn't unbounded for a fixed finite query and corpus: with our positive IDF and valid positive length factors, each contribution is at most $\mathrm{IDF}(t)(k_1+1)$. The issue is comparability, not whether addition is mathematically possible. A raw sum is a possible baseline, but its relative weights need validation.

Two useful baselines are:

1. Normalized score blending: Min-max scaling uses $s_{\text{norm}}=(s-s_{\min})/(s_{\max}-s_{\min})$, followed by a weighted sum $\alpha S_{\text{sparse}}+(1-\alpha)S_{\text{dense}}$. Define a convention when all scores are equal, a policy for candidates absent from a lane, and which returned set supplies the extrema. Outliers and shortlist changes affect normalization; tune weights on held-out queries. Scaling to $[0,1]$ doesn't calibrate relevance probabilities.
2. Reciprocal Rank Fusion (RRF): Discards magnitudes and combines positions in returned rankings.^{[7]Reference 7Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods.https://dl.acm.org/doi/10.1145/1571941.1572114} It needs no training labels to compute the score, but relevance and cutoff choices still need evaluation. Learned fusion and calibrated score combinations are other options.

The RRF formula for document $d$ over ranked lists $L$ is:

Here, $r_\ell(d)$ is the 1-indexed rank of document $d$ in list $\ell$. If list $\ell$ didn't return document $d$, that lane contributes zero.

We'll use $k=60$, the constant in the original RRF experiments and Elasticsearch's current rank_constant default.^{[7]Reference 7Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods.https://dl.acm.org/doi/10.1145/1571941.1572114[8]Reference 8Reciprocal rank fusion: rank constant and result windowshttps://www.elastic.co/docs/reference/elasticsearch/rest-apis/reciprocal-rank-fusion} Rank 1 contributes $1/61\approx0.01639$; rank 2 contributes $1/62\approx0.01613$. The small gap favors consensus over a single lane's first place. This $k$ isn't the number of neighbors or the shortlist size. Our later $k=0$ calculation is a mathematical comparison; Elasticsearch requires rank_constant of at least 1.

View larger

The following function computes RRF rankings for both $k = 60$ and $k = 0$:

from collections import defaultdict

bm25 = ["d1", "d4"]  # zero-score documents aren't candidates
dense = ["d2", "d1", "d4"]  # top three of the cosine ranking

def rrf(rankings, k=60):
    if k < 0:
        raise ValueError("k must be nonnegative")
    scores = defaultdict(float)
    for ranking in rankings:
        if len(set(ranking)) != len(ranking):
            raise ValueError("each lane must return unique document IDs")
        for rank, document in enumerate(ranking, start=1):
            scores[document] += 1 / (k + rank)
    return scores

for k in (60, 0):
    scores = rrf([bm25, dense], k=k)
    fused = sorted(scores, key=lambda document: (-scores[document], document))
    expected = ["d1", "d4", "d2"] if k == 60 else ["d1", "d2", "d4"]
    assert fused == expected
    print(f"k={k}")
    for rank, document in enumerate(fused, start=1):
        print(f"  #{rank} {document}: {scores[document]:.6f}")

k=60
  #1 d1: 0.032522
  #2 d4: 0.032002
  #3 d2: 0.016393
k=0
  #1 d1: 1.500000
  #2 d2: 1.000000
  #3 d4: 0.833333

At $k = 60$, document d1 wins ($0.032522$) because it ranked high in both lanes. But notice document d4: because it received votes from both lanes (#2 in BM25, #3 in dense), its fused score ($0.032002$) beats d2 ($0.016393$), which received votes only from the dense lane.

At $k=0$, d2 moves above d4 because its first-place vote counts more strongly. Which result is better under our labels? The smaller constant improves this particular top-two shortlist, but one question can't select a production constant.

A top-two fused shortlist contains d1 and d4, dropping d2. A top-three shortlist retains it. Fusion itself didn't improve the dense lane's ordering here. On a real corpus, vary each lane's result window and the fused cutoff, then measure candidate recall, latency, and reranking cost. Fifty or a hundred candidates are possible starting budgets. Tune them to the corpus and serving constraints.

Reranking spends compute on the shortlist

Fusion can drop the paraphrase before any later model sees it. A heavier scorer helps only the passages that survived, and only if you can afford to run it. Why not score every passage with that joint model?

A bi-encoder separates queries and documents into distinct vector computations:

In this single-vector architecture, query and document tokens don't interact inside the encoder. Each passage has one query-independent representation. Multi-vector late-interaction retrieval is another design, so this isn't a limitation of every dense retriever.^{[9]Reference 9BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models.https://arxiv.org/abs/2104.08663}

A cross-encoder reranker can examine a query and candidate together rather than comparing two precomputed vectors. For the BERT-based reranker in Nogueira and Cho's paper, the input has this form:^{[10]Reference 10Passage Re-ranking with BERT.https://arxiv.org/abs/1901.04085}

BERT's bidirectional attention lets query and document tokens interact. Dense attention has $O((L_Q+L_D)^2)$ token-pair interactions per candidate; that's the sequence-length term for attention, not the full transformer's compute formula. Model width, layers, feed-forward work, batching, and attention implementation also matter.

A classification head scores the [CLS] representation. A score or sigmoid output isn't automatically a calibrated probability: a value of 0.96 doesn't establish 96% relevance on your queries. Calibration needs separate evaluation.^{[11]Reference 11On Calibration of Modern Neural Networkshttps://arxiv.org/abs/1706.04599} Joint encoding also remains limited by truncation and model capacity. Other rerankers can use different input formats and architectures.

Scoring a million query-passage pairs is usually far more costly than scoring a shortlist, even when pairs are batched. Whether exhaustive reranking meets a latency budget depends on sequence lengths, model, hardware, and workload.

Trace one query through its ranking lanes, cutoff, and reranker:

View larger

The reranker values are invented for the membership example. Compare candidate recall and final ordering on held-out judged queries, then evaluate calibration separately before interpreting scores as probabilities.

The limit is membership. A reranker only orders the candidates it receives. The following hypothetical score table prefers d2. It isn't output from a trained reranker, a probability estimate, or evidence that d2 is better than d1:

reranker_score = {"d1": 0.55, "d2": 0.96, "d4": 0.12}
# Invented ranking scores to demonstrate shortlist membership only.

def rerank(candidates):
    return sorted(candidates, key=lambda doc: -reranker_score[doc])

for name, candidates in [
    ("sparse-only top2", ["d1", "d4"]),
    ("hybrid top3", ["d1", "d4", "d2"]),
]:
    ordered = rerank(candidates)
    d2_first = ordered[0] == "d2"
    print(f"{name:16}: top={ordered[0]} d2_first={d2_first}")

sparse-only top2: top=d1 d2_first=False
hybrid top3     : top=d2 d2_first=True

With ["d1","d4"], the table can only put d1 first. With d2 added, it puts d2 first. Both are labeled relevant. The fixture verifies that retrieval made both candidates available. Measure precision over labeled queries to assess a real gain.

Candidate recall is useful for diagnosing missing evidence; MRR or nDCG can assess its placement after reranking. Those aren't exclusive stage requirements. Use metrics that match the task: finding one answer, covering several required sources, and avoiding irrelevant context are different objectives.

Measure ranking before evaluating answers

Before asking whether the LLM used its evidence faithfully, check whether retrieval found the passages that matter for each judged query:

• Hit Rate @ K: The fraction of queries where at least one relevant passage appears in the top $K$ results.
• Relevance Recall @ K: The fraction of all judged relevant passages for a query that appear in the top $K$ results, averaged across the query set.
• Mean Reciprocal Rank (MRR @ K): The average of $1/r$ for the first relevant result at rank $r\le K$, or 0 if none appears by $K$. It ignores additional relevant passages after the first.
• nDCG @ K: Discounted gains from relevance grades, normalized by the ideal ranking's gain. One common convention uses gain $2^{g_r}-1$ and discount $1/\log_2(r+1)$. Declare the grading, gain, and zero-ideal-gain conventions.^{[1]Reference 1Introduction to Information Retrieval.https://nlp.stanford.edu/IR-book/}

These metrics use available judgments. Unjudged passages aren't necessarily irrelevant, and incomplete labels can bias comparisons.^{[9]Reference 9BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models.https://arxiv.org/abs/2104.08663} Specify how queries with no judged relevant source enter evaluation; separately test unanswerable questions and abstention.

The next example has nonempty relevant sets and two invented runs over three questions. It computes macro averages: each question gets equal weight. The example demonstrates metric arithmetic. A retrieval benchmark needs realistic queries, corpora, judgments, and runs.

gold = {
    "q1 api key rotation": {"d1", "d2"},
    "q2 replace credential": {"d2"},
    "q3 quota dashboard": {"d4"},
}
run_a = {
    "q1 api key rotation": ["d1", "d4", "d2"],
    "q2 replace credential": ["d3", "d4", "d2"],
    "q3 quota dashboard": ["d4", "d1", "d2"],
}
run_b = {
    "q1 api key rotation": ["d1", "d2", "d4"],
    "q2 replace credential": ["d2", "d1", "d4"],
    "q3 quota dashboard": ["d4", "d1", "d2"],
}

def evaluate(run, retrieval_k=2, mrr_k=3):
    if retrieval_k <= 0 or mrr_k <= 0:
        raise ValueError("cutoffs must be positive")
    hits = []
    reciprocals = []
    recalls = []
    for question, relevant in gold.items():
        ranking = run.get(question, [])
        if len(set(ranking)) != len(ranking):
            raise ValueError("rankings must contain unique document IDs")
        hits.append(any(doc in relevant for doc in ranking[:retrieval_k]))
        recalls.append(len(set(ranking[:retrieval_k]) & relevant) / len(relevant))
        first_rank = next((rank for rank, doc in enumerate(ranking[:mrr_k], start=1) if doc in relevant), None)
        reciprocals.append(0.0 if first_rank is None else 1 / first_rank)
    return sum(hits) / len(gold), sum(recalls) / len(gold), sum(reciprocals) / len(gold)

for name, run in [("run A", run_a), ("run B", run_b)]:
    hit_rate, recall, mrr = evaluate(run)
    print(f"{name}: hit@2={hit_rate:.3f} recall@2={recall:.3f} mrr@3={mrr:.3f}")

hit_a, recall_a, mrr_a = evaluate(run_a)
assert abs(hit_a - 2 / 3) < 1e-9
assert abs(recall_a - 0.5) < 1e-9
assert abs(mrr_a - (1 + 1 / 3 + 1) / 3) < 1e-9
assert evaluate(run_b) == (1.0, 1.0, 1.0)
assert evaluate({}) == (0.0, 0.0, 0.0)
assert evaluate(run_a, mrr_k=2)[2] == 2 / 3

run A: hit@2=0.667 recall@2=0.500 mrr@3=0.778
run B: hit@2=1.000 recall@2=1.000 mrr@3=1.000

Notice how these metrics capture different behaviors: on query q1, run A achieves a Hit Rate of $1.0$ at $K = 2$ (because d1 was returned), but its Recall@2 is only $0.5$ because d2 was pushed to rank 3. On query q2, run A gets a Hit Rate of $0$ and Recall of $0$ at $K = 2$, but still gets a non-zero reciprocal rank contribution of $1/3$ in MRR@3 because d2 appeared at rank 3.

If answering requires both sources in q1, its perfect reciprocal rank doesn't certify a complete context. Choose the metric by the evidence requirement before choosing the winning run.

Those metrics score the list you hand them. An approximate index can return a different neighbor before any of them is computed.

Approximate search is a recall decision

Flat exact search scores every eligible vector. It computes $N$ distances or similarities, each using $O(D)$ coordinate work, plus top-$K$ selection.

For a straightforward inner-product scan with $N=10^6$ and $D=1536$, there are $1.536\times10^9$ coordinate multiplications plus roughly as many additions per query. The float32 vector payload is $4ND=6.144$ GB. At 200 queries per second, scanning it separately for each query implies about 1.23 TB/s of vector reads, before other work. These estimates size the workload; measure throughput on the target system, where batching can reuse data.

ANN can reduce search work by skipping candidates or approximating scores, at the risk of different neighbors. There is no universal corpus-size cutoff or 1–5% recall cost. Exact GPU and batched search can be viable at scale; compare them with approximate choices under your workload.^{[12]Reference 12Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734}

Three mechanisms you'll encounter are:

PQ is compression, so these aren't mutually exclusive families: IVF-PQ and HNSW-PQ combine mechanisms. For $D=1536$, $M=96$, and eight-bit indices, a PQ vector code occupies 96 bytes versus 6144 bytes for float32 coordinates, a 98.44% payload reduction. IDs, codebooks, graph links, and any retained original vectors still consume memory. Standard equal-size PQ requires $M$ to divide $D$.^{[15]Reference 15Faiss indexeshttps://github.com/facebookresearch/faiss/wiki/Faiss-indexes[16]Reference 16Faiss ProductQuantizer: dimensions, code size, and codebookshttps://github.com/facebookresearch/faiss/blob/main/faiss/impl/ProductQuantizer.cpp}

IVF's nprobe=1 searches the nearest coarse list. Raising it selects more lists, not a uniform metric radius. More lists can recover missed neighbors but also require routing and scanning work. With IVFFlat, probing every list restores exhaustive scoring if no additional limits apply; with IVF-PQ, compression error can remain.

HNSW's query search budget is often called efSearch; hnswlib exposes it through set_ef and calls the construction parameter ef_construction. Larger budgets often improve recall at more cost, but don't certify exact results. hnswlib requires query ef to be at least the requested neighbor count. $M$ controls connectivity, not an identical degree for every node.^{[17]Reference 17HNSW algorithm parametershttps://github.com/nmslib/hnswlib/blob/master/ALGO_PARAMS.md}

View larger

Watch an IVF probe miss the nearest passage

A one-dimensional coordinate fixture demonstrates how boundary misses occur in code.

Use two preselected coarse centers, $0.0$ and $10.0$. They aren't the result of fitting k-means to these three documents. The boundary is $5.0$; the code's insertion-order tie rule assigns an exactly equidistant point to list 0.

Our target document key_rotation sits at $5.1$ (inside list 1). A developer query arrives at $4.9$. The distance to centroid 0 is $|4.9 - 0.0| = 4.9$, while the distance to centroid 1 is $|4.9 - 10.0| = 5.1$.

Because centroid 0 is slightly closer, single-probe search (nprobe = 1) routes the query exclusively into list 0. It never opens list 1, missing key_rotation even though it's only $0.2$ units away:

documents = {
    "generic_api": 0.0,
    "key_rotation": 5.1,
    "quota_page": 9.0,
}
centroids = {0: 0.0, 1: 10.0}
lists = {0: [], 1: []}
for doc, value in documents.items():
    bucket = min(centroids, key=lambda i: abs(centroids[i] - value))
    lists[bucket].append(doc)
query = 4.9

def nearest(candidates: list[str]) -> str:
    return min(candidates, key=lambda doc: abs(documents[doc] - query))

exact = nearest(list(documents))
ordered_lists = sorted(centroids, key=lambda bucket: abs(centroids[bucket] - query))
one_probe = nearest(lists[ordered_lists[0]])
two_probe = nearest(lists[ordered_lists[0]] + lists[ordered_lists[1]])

assert exact == "key_rotation"
assert one_probe == "generic_api"
assert two_probe == "key_rotation"
print("exact nearest:  ", exact)
print("nprobe=1 result:", one_probe)
print("nprobe=2 result:", two_probe)

exact nearest:   key_rotation
nprobe=1 result: generic_api
nprobe=2 result: key_rotation

Exact search finds the nearest hand-placed point; single-probe search misses it. We didn't test semantic embedding quality. Even this toy's compute savings need care: one probe compares two centers plus one document, matching flat search's three distance calculations. Two probes compare two centers plus three documents, exceeding flat search's three. Index overhead can outweigh pruning on a tiny corpus.

For a real audit, hold vectors, metric, eligible documents, filters, and tie handling fixed. If exact search finds evidence that ANN misses under that same contract, investigate the approximation before changing embeddings.

A version filter changes the search problem

Suppose the user needs version 2 instructions. Taking the unfiltered top two and then discarding version 1 passages doesn't necessarily return the top two eligible passages. This separate fixture uses invented ranking scores, not model measurements:

passages = [
    ("v1_rotation", 1, 0.99),
    ("v1_credentials", 1, 0.98),
    ("v2_rotation", 2, 0.97),
    ("v2_credentials", 2, 0.96),
]

def top_two(rows):
    return sorted(rows, key=lambda row: (-row[2], row[0]))[:2]

post_filtered = [row[0] for row in top_two(passages) if row[1] == 2]
eligible_top_two = [row[0] for row in top_two([row for row in passages if row[1] == 2])]
print("filter after unfiltered top 2:", post_filtered)
print("exact top 2 among version 2:", eligible_top_two)
assert post_filtered == []
assert eligible_top_two == ["v2_rotation", "v2_credentials"]

filter after unfiltered top 2: []
exact top 2 among version 2: ['v2_rotation', 'v2_credentials']

The empty result came from the cutoff's placement, even with exact scores. Define eligibility before the reference top-$K$ calculation. A serving engine can enforce a filter during search or fetch more candidates and continue until it has enough eligible results. A fixed overfetch count can still leave fewer than $K$ eligible results. Filter-aware ANN search also has its own accuracy and cost trade-offs.^{[18]Reference 18Indexing: Vector Indexhttps://qdrant.tech/documentation/manage-data/indexing/#vector-index} Compare its results with an exact scan of the eligible corpus, and include selective filters in the evaluation set. Comparing against an unfiltered exact list measures a different search problem.

Put an exact-search gate around ANN settings

Before deploying an ANN index configuration, measure ANN Recall@K against an exact brute-force scan across a representative evaluation query set:

Compute this per query, then average over the evaluation set, assuming at least $K$ eligible vectors. It measures how often two searches return the same neighbor IDs. Relevance requires judgments; duplicate or equal-distance vectors can have different IDs without worse distance, so document tie handling and inspect score differences too.

The following separately invented, query-aligned result lists illustrate Recall@1 arithmetic. They don't build an index or measure latency:

exact_top1 = ["key_rotation", "quota_page", "display_name", "duplicate_secret"]
ann_fast = ["generic_api", "quota_page", "display_name", "generic_api"]
ann_tuned = ["key_rotation", "quota_page", "display_name", "duplicate_secret"]

def recall_at_one(approximate, exact):
    if not exact or len(approximate) != len(exact):
        raise ValueError("provide nonempty, equally sized query-aligned result lists")
    matches = sum(found == expected for found, expected in zip(approximate, exact))
    return matches / len(exact)

print(f"fast setting recall@1:  {recall_at_one(ann_fast, exact_top1):.2f}")
print(f"tuned setting recall@1: {recall_at_one(ann_tuned, exact_top1):.2f}")
print("launch only after checking latency alongside recall")
assert abs(recall_at_one(ann_fast, exact_top1) - 0.5) < 1e-9
assert recall_at_one(ann_tuned, exact_top1) == 1.0

fast setting recall@1:  0.50
tuned setting recall@1: 1.00
launch only after checking latency alongside recall

The first imagined list agrees with exact top 1 on two of four queries; the second agrees on all four. The variable names ann_fast and ann_tuned are scenario labels. Nothing in this code establishes speed or which search mechanism produced either list.

Measure recall and latency across actual configurations and representative filtered queries. Include tail latency, throughput, memory, build/update cost, and judged evidence quality. Choose a target from the application's tolerance for missed evidence; no universal 95–98% threshold establishes readiness. Use held-out queries to check the chosen setting.

A retrieval review checklist

A missing passage can start in different parts of the pipeline. Use these examples to narrow down where to look:

• Vocabulary mismatch: Inspect analysis and query expansion; test whether another retrieval lane supplies missing evidence.
• Repetition bias: Saturation limits repeated terms' score gains; still inspect irrelevant high scorers.
• Score-scale mismatch: Compare rank fusion with validated score blending.
• Shortlist loss: Measure what each lane and the fused cutoff omit before reranking.
• Approximation loss: Compare ANN with exact scoring under the same retrieval contract.

Before blaming an LLM for hallucinating, audit the retrieval stages systematically:

This separation helps locate the failure. Retrieved evidence can still be stale, inapplicable, misread, or ignored by the generator. Evaluate answer support and abstention after evaluating retrieval. Good neighbor agreement alone doesn't validate a RAG answer.

A miss can come from the analyzer, the score, the fusion cutoff, or the approximate index. Keep that miss separate from a generator that ignored a passage it was given.

Practice tasks

Using the four-document fixture, alter one mechanism at a time and observe how the metrics respond:

1. In bm25-from-scratch.py, add a fifth document d5: "Rotate an API key safely." and five distractor documents mentioning only API key quota limits. Recalculate document frequencies and IDFs. How do $\mathrm{df}(\text{rotate})$ and $\mathrm{df}(\text{api})$ change, and which term gains higher IDF weight?
2. In reciprocal-rank-fusion.py, introduce a dense-only candidate d5 at dense rank 4. How does d5 score under RRF with $k = 60$? If downstream reranking takes only the top 3 candidates, does d5 survive?
3. Add a fourth question to gold and run_b, with one relevant passage appearing at rank 3. Recalculate Hit Rate@2, Relevance Recall@2, and MRR@3.
4. Shift the IVF query vector from $4.9$ to $5.2$. Which centroid is probed first under nprobe = 1, and does single-probe search recover key_rotation?

Practice guidance

1. With 10 total documents, rotate appears once ($\mathrm{df} = 1$), while api appears in 8 documents ($\mathrm{df} = 8$). The positive IDF for rotate is $\ln(1 + (10 - 1 + 0.5) / (1 + 0.5)) \approx 1.992$, while api drops to $\ln(1 + (10 - 8 + 0.5) / (8 + 0.5)) \approx 0.258$. Rarity amplifies the discriminative power of rotate.
2. Document d5 receives $1 / (60 + 4) = 1/64 \approx 0.015625$ from dense retrieval and $0$ from BM25. It ranks behind d1, d4, and d2. With a top-3 cutoff, d5 is dropped before reranking.
3. With four queries and the fourth query's first relevant passage at rank 3, Hit Rate@2 and Recall@2 drop to $3/4 = 0.750$. MRR@3 becomes $(1.0 + 1.0 + 1.0 + 1/3) / 4 \approx 0.833$.
4. At $5.2$, centroid 10 ($|5.2 - 10.0| = 4.8$) is closer than centroid 0 ($|5.2 - 0.0| = 5.2$). List 1 is selected first, immediately finding key_rotation ($|5.2 - 5.1| = 0.1$) even with nprobe = 1.