Core Retrieval Algorithms

Ask How do I rotate an API key? and your search engine might hand back a beautifully formatted quota dashboard instead of key rotation steps. The LLM then generates an eloquent, authoritative answer about daily rate limits. It sounds convincing, but it didn't receive the evidence required to solve the developer's problem.

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?

Using one question and four representative passages, this analysis works through the full evidence-selection stack: sparse lexical matching with BM25, dense bi-encoder embeddings, candidate fusion with RRF, and cross-encoder reranking. We can then audit Approximate Nearest Neighbor (ANN) indices to isolate approximate search boundary misses from representation errors.

One question, four possible sources

Here's the developer question:

How do I rotate an API key?

The documentation assistant retrieves four candidate passages:

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.

Retrieval evaluation demands relevance judgments tied strictly to specific questions, not broad topical categories.

Sparse retrieval starts with an inverted index

Classical lexical search represents documents by their individual terms. Instead of linearly reading through all $N$ passages at query time, an inverted index maps each unique vocabulary token to a sorted posting list of document identifiers containing that token.^{[1]Reference 1Introduction to Information Retrieval.https://nlp.stanford.edu/IR-book/}

At scale, posting lists are compressed using delta-encoding (such as Frame of Reference or variable-byte encodings) so that lookups only touch documents that contain at least one query term. The query execution time drops from $O(N)$ passage evaluations to $O(\sum_{t \in Q} |\text{postings}(t)|)$.

Production tokenization requires careful engineering: stripping punctuation carelessly can ruin technical searches. An error code like AUTH_401 or an API symbol like rotate_api_key() must stay intact. For this minimal walkthrough, tokenization lowercases text, removes punctuation, and filters out common stopwords.

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.

Passage d2 is judged relevant by human reviewers, but it doesn't appear in any posting list for our query terms. This is the classic vocabulary mismatch problem. Lexical indices can't see through synonyms or paraphrased syntax on their own.

BM25 scores lexical evidence

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

In passage d1, the term api appears once, while key appears three times. Early TF-IDF implementations assumed linear term frequency: repeating a word ten times made the passage ten times as relevant ($TF \times IDF$). In technical documentation, that behavior rewards keyword stuffing: a verbose release note mentioning API key twelve times easily beats a concise, direct troubleshooting snippet.

The Okapi BM25 algorithm solves this by applying an asymptotic saturation curve to term frequency, combined 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} The contribution of query term $t$ in document $d$ is:

$$\mathrm{Score}(t, d) = \mathrm{IDF}(t) \cdot \frac{f(t,d) \cdot (k_1 + 1)}{f(t,d) + k_1 \cdot \left(1 - b + b \cdot \frac{|d|}{\mathrm{avgdl}}\right)}$$

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$): Controls how quickly term frequency gains level off. As $f(t, d) \to \infty$, the fractional term approaches $k_1 + 1$. Standard engines like Lucene set $k_1 = 1.2$. A lower setting (such as 0.5) saturates almost immediately, acting like a binary presence check. A higher setting (such as 2.0) gives more weight to repeated terms.
2. Document length normalization ($b$): Governs how severely long documents are penalized. If $b = 1.0$, full length normalization applies, scaling the penalty directly with document length. If $b = 0.0$, document length is completely ignored. Lucene defaults to $b = 0.75$, penalizing verbose documents while acknowledging that comprehensive guides naturally contain more words.^{[4]Reference 4BM25Similarity: Apache Lucene 10.3.1https://lucene.apache.org/core/10_3_1/core/org/apache/lucene/search/similarities/BM25Similarity.html}

For Inverse Document Frequency (IDF), Robertson-Spärck Jones weighting uses $\log((N - \mathrm{df} + 0.5) / (\mathrm{df} + 0.5))$. When a term appears in more than half the documents, that formula turns negative. Lucene uses a positive variant:

$$\mathrm{IDF}(t) = \ln\left(1 + \frac{N - \mathrm{df}(t) + 0.5}{\mathrm{df}(t) + 0.5}\right)$$

$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$:

$$\mathrm{IDF}(\text{api}) = \ln\left(1 + \frac{4 - 2 + 0.5}{2 + 0.5}\right) = \ln(2) \approx 0.693$$

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.

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

Notice what happened: BM25 ranks d4 (the quota dashboard) above d2 (the credential guide) simply because d4 contains the exact tokens api and key. Lexical search alone can't bridge semantic intent. That's why we need a dense retrieval lane.

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:

$$\text{TF weight} = \frac{f \cdot (k_1 + 1)}{f + k_1}$$

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:

The first occurrence contributes $1.000$. By the twentieth occurrence, the weight has reached $2.075$, closing within $0.125$ of the theoretical $2.200$ ceiling. BM25 prevents keyword stuffing from overwhelming the search results.

Dense retrieval recovers paraphrases

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

A bi-encoder architecture uses two separate encoder towers: a query encoder $E_Q(q)$ and a passage encoder $E_D(d)$. Because the passage representations don't depend on the incoming query, we can precompute and index every document vector offline. When a developer submits a query at runtime, the system runs a single forward pass $E_Q(q)$ and computes vector similarity against the indexed document vectors.

To see how directional similarity works in practice, consider a 3D coordinate fixture. These synthetic vectors place the query close to the paraphrased credential guide:

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

$$\cos(q, d) = \frac{q \cdot d}{\lVert q \rVert_2 \lVert d \rVert_2}$$

For passage d2, the dot product is $1.0(0.9) + 0.8(0.9) + 0.0(0.0) = 1.62$. Dividing by the norms ($\sqrt{1.64} \cdot \sqrt{1.62} \approx 1.2806 \cdot 1.2728 \approx 1.6300$) gives approximately $0.994$. Even though d2 says credential instead of API key, its direction aligns almost perfectly with the query's intent.

Dense retrieval recovers d2 ($0.994$) as its top candidate, solving the vocabulary mismatch that caused BM25 to drop it. It also ranks d1 high ($0.957$) while pushing the quota distractor d4 down to $0.625$.

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$.

If vectors aren't normalized, vector magnitude can overturn angular alignment. An unnormalized dot product rewards longer vectors, which can lead to misleading search results:

The dot product with large_partial_match is $6.0 \cdot 1.0 = 6.0$, overpowering aligned_paraphrase ($1.64$) simply because of its length. Cosine normalizes out length, correctly picking the aligned paraphrase.

Always verify the distance contract your embedding model was trained for. If a model was trained on cosine distance, storing unnormalized embeddings in an inner-product index changes the ranking semantics.

A query contains an exact error code plus a paraphrase of the surrounding symptom. Why can a hybrid retriever outperform either BM25 or dense retrieval alone?

Answer

BM25 preserves exact lexical evidence such as the error code, while dense retrieval can recover semantically similar wording. Fusion lets both signals contribute without pretending their raw scores share one scale.

Fuse independent retrieval lanes

Neither retrieval strategy is flawless on its own:

• Sparse BM25: Excellent for exact identifiers, error codes, UUIDs, and rare function names. It fails on paraphrases and conceptual synonyms.
• Dense bi-encoders: Excellent for semantic intent, broad themes, and natural language paraphrases. They struggle with rare alphanumeric tokens, version tags, and exact keyword matches.

Because their strengths are complementary, production search pipelines run both in parallel:

How should we combine these results?

BM25 produces unbounded scores (from 0 to 20+), while cosine similarity is bounded between -1 and 1. We can't simply add them together without distorting the results.

Engineers typically use one of two fusion methods:

1. Normalized score blending: Rescale BM25 and cosine scores to $[0, 1]$ via min-max scaling ($s_{\text{norm}} = (s - s_{\min}) / (s_{\max} - s_{\min})$) and compute a weighted sum $S = \alpha \cdot S_{\text{bm25}} + (1 - \alpha) \cdot S_{\text{dense}}$. While this retains relative score margins, it's sensitive to distribution shifts and outlier scores on individual queries.
2. Reciprocal Rank Fusion (RRF): Ignores score magnitudes entirely and evaluates relevance purely by rank position across result lists.^{[6]Reference 6Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods.https://dl.acm.org/doi/10.1145/1571941.1572114}

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

$$\mathrm{RRF}(d) = \sum_{\ell \in L} \frac{1}{k + r_\ell(d)}$$

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.

The constant $k$ (defaulting to 60 in Lucene, Elasticsearch, and Azure AI Search) acts as a smoothing parameter. For $k = 60$, rank 1 contributes $1 / (60 + 1) \approx 0.01639$, while rank 2 contributes $1 / (60 + 2) \approx 0.01613$. The gap between adjacent ranks is small ($0.00026$). This dampens the impact of extreme outliers and rewards candidates that earn consensus across multiple lanes.

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

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.

This outcome carries an important operational lesson: if you pass only the top two fused candidates to the downstream stage, you'll forward d1 and d4, dropping the paraphrase d2 completely. Candidate retrieval needs a wide enough shortlist (such as top 50 to 100) so that high-quality single-lane discoveries survive.

Why does RRF use ranks instead of averaging the BM25 and cosine scores?

Answer

BM25 and cosine have different score scales. RRF combines rank positions instead. It discards score magnitudes, which also means it discards any useful information in their margins.

Reranking spends compute on the shortlist

Why don't we use a bi-encoder for everything?

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

$$\text{score}_{\text{bi-encoder}} = E_Q(q) \cdot E_D(d)$$

The query never directly interacts with document tokens inside the transformer layers. The embedding vector must compress all subtle technical semantics into a single fixed-length vector.

A cross-encoder reranker eliminates this compression bottleneck.^{[7]Reference 7Passage Re-ranking with BERT.https://arxiv.org/abs/1901.04085} It concatenates the query and document into a single token sequence:

$$[\text{CLS}] \circ \text{Query} \circ [\text{SEP}] \circ \text{Document}$$

The concatenated sequence passes through all transformer layers together. Every query token can attend directly to every document token via full bidirectional self-attention ($O((L_Q + L_D)^2)$ compute cost per candidate). The model outputs a calibrated relevance score from the [CLS] representation.

Evaluating a million passages with a cross-encoder would require a million full transformer forward passes, which is computationally impossible for real-time applications.

Production architectures organize retrieval into a multi-stage cascade:

First-stage hybrid retrieval acts as a wide, computationally light net that filters millions of documents down to 50 or 100 candidates. The cross-encoder then focuses its heavy attention computation only on that shortlist.

The critical constraint is that a reranker can only reorder candidates it receives. If the candidate retrieval stage fails to include a relevant passage, no reranker can salvage it:

When the candidate pool is restricted to ["d1", "d4"], the reranker picks d1. It never sees d2. When the hybrid pool expands to ["d1", "d4", "d2"], the reranker evaluates d2 and correctly promotes it to rank 1.

The two stages require distinct evaluation metrics: candidate generation must be measured by Recall@K, while reranking is measured by MRR@K or nDCG@K.

Measure ranking before evaluating answers

Before evaluating LLM generation faithfulness, measure the accuracy of the retrieved evidence against judged evaluation queries:

• 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$, where $r$ is the position of the first relevant passage retrieved. If no relevant passage appears in the top $K$, the reciprocal rank for that query is 0.^{[8]Reference 8BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models.https://arxiv.org/abs/2104.08663}

The script below evaluates two candidate runs on three judged test queries:

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.

Approximate search is a recall decision

Flat exact search computes distances against every single vector in the database. For $N$ documents in $D$ dimensions, exhaustive scanning requires $O(N \cdot D)$ distance operations per query.

For $N = 10^6$ passages and $D = 1536$ dimensions, an exact scan performs $1.5 \times 10^9$ floating-point multiplications per query. At 200 concurrent queries per second, exact search exhausts CPU and GPU compute budgets.

To scale beyond hundreds of thousands of vectors, systems rely on Approximate Nearest Neighbor (ANN) search algorithms. ANN trades a tiny fraction of recall (typically 1% to 5%) in exchange for substantial latency reductions and higher throughput.^{[9]Reference 9Billion-scale similarity search with GPUs.https://arxiv.org/abs/1702.08734}

Three indexing families power modern vector databases:

In an IVF index, the search budget is governed by nprobe: setting nprobe = 1 searches only the single closest Voronoi centroid, which is fast but risky. Increasing nprobe widens the search radius across neighboring cells, recovering recall at the cost of checking more vectors.

In HNSW graphs, the runtime knob is efSearch: increasing the priority queue size expands graph exploration, approaching exact search recall while increasing latency.

Watch an IVF probe miss the nearest passage

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

Consider a 1D space with two centroids: centroid 0 at $0.0$, and centroid 1 at $10.0$. The Voronoi boundary between them falls at $5.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:

The miss has nothing to do with embedding quality: the vector representations were accurate. It's an indexing artifact. When an approximate retriever drops relevant results, benchmark exact search on the same vectors first. If exact search finds the answer and ANN misses it, adjust nprobe or efSearch before retraining embeddings.

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:

$$\text{ANN Recall@K} = \frac{|\text{Top-}K_{\text{approx}} \cap \text{Top-}K_{\text{exact}}|}{K}$$

This measures index fidelity, distinct from relevance evaluation. It checks whether the approximate index returns the same mathematical neighbors as brute-force search:

The ann_fast setting cuts latency by skipping neighboring clusters, but drops ANN Recall@1 to $0.50$. The ann_tuned setting inspects adjacent cells, restoring recall to $1.00$.

When tuning production vector databases, plot the full Pareto frontier of ANN Recall versus p99 query latency across varying efSearch or nprobe values. Choose the most aggressive setting that keeps ANN recall above your target threshold (typically 95% to 98%).

An approximate index lowers latency but drops candidate recall@20 from 0.94 to 0.81. Can a stronger reranker recover the missing relevant documents?

Answer

No. A reranker can reorder only candidates it receives. Tune the approximate-search knob against candidate recall and latency before spending more compute downstream.

A retrieval review checklist

Our worked examples isolated distinct failure modes across the retrieval pipeline:

• Lexical vocabulary misses: Handled by adding a dense bi-encoder lane.
• Keyword stuffing: Handled by BM25 term frequency saturation ($k_1$).
• Score scale distortion: Handled by Reciprocal Rank Fusion ($k=60$).
• Shortlist truncation losses: Handled by tuning the first-stage candidate cutoff $K$.
• ANN partition boundary misses: Handled by tuning index knobs (nprobe, efSearch) against exact brute-force search.

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

This disciplined separation prevents premature model retraining. When retrieval delivers verified evidence, the downstream LLM generation becomes significantly more reliable.

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 judged query with a single relevant passage appearing at rank 3 in run_b. 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.