Retrieval

The previous chapter ended with a better-specified request ready for retrieval. The visualization above shows the evidence it must search: all 250 films in the shared corpus, represented by their plot summaries. An embedding model converted each summary into a vector with 384 coordinates, far more axes than a screen can display. The 3D field and 2D cluster map are projections made for inspection; retrieval still uses the original 384-dimensional vectors. Rotate the 3D view, then switch to the cluster map to see the same films flattened into a plane. Hover across either view and the structure becomes apparent. Space films gather in one region, heist films in another, and Alien sits between science fiction and horror because its summary carries evidence of both.

Now consider a request that names none of those categories: “a space movie where the dad ages slowly”. A person who has seen Interstellar may recognize it immediately, but the system receives only those words and must recover the film from 250 summaries. The relevant summary describes relativity, time dilation, and a daughter growing older than her father without using the phrase “ages slowly.” The request and the document express the same idea in different language.

Retrieval must find plausible candidates despite that gap, quickly enough to leave time for the stages that follow. Lexical retrieval searches the words the index stores, while dense retrieval searches the geometry created by an embedding model. Each preserves evidence the other can lose, and each introduces its own failure modes. This chapter develops both approaches, examines how approximate search changes recall and latency, then combines their candidate sets so ranking receives a stronger pool to judge.

Lexical retrieval scores exact term matches

The most direct way to search the corpus is to compare the query with all 250 summaries. That scan is harmless at this scale, but its cost grows with every document added. An online system avoids repeating that work by organizing the corpus before any query arrives.

Chapter 2 introduced the resulting structure: an inverted index. Instead of storing only the terms found in each film, it maps every term to the films that contain it. The list attached to one term is its posting list. When a query arrives, the engine reads those short lists rather than every summary in the corpus.

How the lists are combined depends on the request. An AND query intersects them and keeps documents containing every term. A broader query can take their union and keep any document containing at least one term. Either operation produces candidates, but those candidates still need to be ordered.

BM25 provides that order by adding a contribution from each matching query term. Its formula encodes three useful assumptions:

1. Rare words tell you more. Matching “wormhole” narrows the corpus far more than matching “the”. This is inverse document frequency.
2. Repetition helps, less each time. A summary that mentions “shark” three times is more about sharks than one that mentions it once, but the tenth mention adds almost nothing. The parameter k1 controls how quickly repetition saturates.
3. Long documents get no credit for being long. A 400-word summary matches more words by accident than a 40-word one, so length is penalized, and the parameter b controls how hard.

Here, q is the query, d is the document being scored, and t is one term in the query. N is the number of documents, n_t is the number containing t, and f_{t,d} is its frequency in d. The ratio between |d| and avgdl compares the document’s length with the corpus average.

The instrument below applies BM25 scoring to ten films and exposes each term’s contribution. Each query term opens a posting list, and gold titles mark films present in every list. The BM25 ranking is broader: it scores any film matching at least one term, then adds the contribution from each match.

Lower k1, and repeated terms lose some of their advantage. Raise b, and document length has more influence. The documents and posting lists remain fixed while the ranking moves, making the underlying point visible: a relevance score expresses assumptions about the available evidence rather than a fact stored in the index.

def search(query: str, k: int = 10) -> list[SearchResult]:
    if k < 1:
        return []

    scores = BM25.get_scores(tokenize(query))
    matching = np.flatnonzero(scores > 0)
    order = matching[np.argsort(scores[matching], descending=True, stable=True)[:k]]
    return [{**DOCS[index], "bm25_score": float(scores[index])} for index in order]

Dense retrieval changes the matching problem

The BM25 formula makes one condition unavoidable: a query term contributes only when the same term appears in a document. That condition comes from how lexical retrieval represents the text.

Imagine one coordinate for every term in the corpus vocabulary. A film has a nonzero value only at coordinates for terms it contains, so most of its vector is empty. The query can be represented in the same term space, and BM25 uses term frequency, document frequency, and document length to weight the coordinates they share. These are sparse vectors, and their named dimensions make every match traceable to an indexed term.

Dense retrieval changes the representation rather than the need to compare a query with documents. The embedding model used for the field above maps each text to 384 learned coordinates, with meaning distributed across the full vector rather than assigned to individual words. A query and a summary can therefore lie close together even when they share no exact terms. That creates a path around vocabulary mismatch, while compressing away some of the exact distinctions the sparse representation preserved.

Lexical retrieval cannot cross vocabulary gaps

Return to the request from the introduction: “space movie where the dad ages slowly”. BM25 ranks Scream, Toy Story, and Lost in Translation first. Interstellar appears much farther down the list.

The ranking follows the evidence BM25 can use. Terms such as “movie,” “dad,” and “space” occur in several summaries, so documents matching or repeating them collect points. The Interstellar summary instead describes an hour costing seven years at home and Cooper watching his children grow old. Those details express the remembered plot, but they share almost none of its useful terms.

This failure is vocabulary mismatch: the request and a relevant document describe the same subject with different words. Query understanding can add known aliases or domain terms, but it cannot anticipate every paraphrase. A posting list still requires exact indexed terms before BM25 can assign them weight. Dense retrieval addresses that limit by comparing learned representations of the complete texts, allowing evidence expressed in different language to contribute to a match.

Dense retrieval searches by proximity

The embedding model’s coordinates, 384 for the model used here and hundreds or thousands for others, together form a latent space, a learned coordinate system whose individual dimensions do not carry labels such as “space” or “horror.” The evidence is distributed across the complete vector.

Geometrically, a vector has both direction and magnitude. When drawn from the origin, its endpoint identifies one position in the latent space. Training encourages related texts to occupy nearby regions, which is why recognizable neighborhoods can emerge without supplying the model with the genre labels used in the display.

Dense retrieval embeds the query with the same model and compares it with every document vector. This implementation normalizes each vector to a magnitude of one, then uses cosine similarity to compare their directions. Normalization means the original magnitude does not affect the score. A larger cosine similarity indicates a closer match, which places Interstellar first for the remembered description even though the query and summary share almost none of their useful words.

The instrument below projects the 384-dimensional vectors into two dimensions so their neighborhoods can be inspected. That projection preserves some local structure but distorts distances, so it illustrates the geometry rather than reproducing the cosine ranking. Drag the gold probe to see how nearby films change across the map, or place two anchors and inspect the midpoint between them. The code example below performs the actual comparison in the full embedding space.

def vector_search(query: str, k: int = 10) -> list[dict]:
    if k < 1:
        return []
    if not query.strip():
        raise ValueError("Query must contain non-whitespace text")
    query_vector = embed_query(query)
    if query_vector.shape[1] != VECTORS.shape[1]:
        raise ValueError("Query and document embedding dimensions do not match")
    if not np.allclose(np.linalg.norm(query_vector, axis=1), 1.0, atol=1e-4):
        raise ValueError("The query embedder produced a non-unit vector")
    scores, indices = INDEX.search(query_vector, k)
    return [
        {**DOCS[index], "vector_score": float(score)}
        for score, index in zip(scores[0], indices[0])
        if index >= 0
    ]

def compare(query: str, k: int = 5) -> None:
    print(f"\nQuery: {query!r}")
    print("BM25")
    for result in bm25_search(query, k):
        print(f"{result['bm25_score']:5.2f}  {result['title']}")
    print("\nVector")
    for result in vector_search(query, k):
        print(f"{result['vector_score']:.3f}  {result['title']}")

Approximate search trades recall for speed

Exact dense retrieval compares the query with every document vector. That is manageable for 250 films, but the work grows with both the number of documents and the size of each vector. A vector index spends additional memory and offline construction time so the online search can avoid most of those comparisons. The reduction in latency introduces a new risk: the shortened search may miss a relevant neighbor.

Hierarchical Navigable Small World (HNSW) is a widely used graph index for making that trade. It stores a sparse upper layer for long-range movement and progressively denser layers for local search. A query begins from an entry point, explores connected vectors that appear closer, then descends into finer neighborhoods. Production implementations maintain a set of candidates at each layer, allowing the search to explore more than one route before choosing its nearest results.

The instrument below simplifies that process into one greedy route over 60 films in a two-dimensional projection. Choose a film whose plot summary will act as the query, then use Play or Step to follow the walk through all three layers. Hover any node to identify it. The hop count shows the intuition behind the index: a short route can reach a useful neighborhood without scoring every film as a candidate. Each hop still compares connected nodes, so the count is not a complete latency measurement. The route is illustrative rather than an exact implementation of production HNSW.

This is approximate nearest-neighbor search. Visiting more candidates improves the chance of recovering the true nearest results but increases latency, while a narrower search is faster and may reduce recall. Index parameters determine where the system sits on that curve: the size of the candidate set kept during search (efSearch in HNSW implementations) widens or narrows each descent, and the number of links per node (M) fixes the graph’s density at build time. Both must be evaluated with representative queries rather than chosen from speed alone.

Filtering adds another recall risk. In the instrument, the graph finds five nearby candidates before applying the selected genre as a post-filter, a constraint checked only after the search completes. The route does not change when the post-filter changes, but the candidate list does. If none passes, the result is empty even when qualifying films exist elsewhere. Systems can respond by exploring more candidates, applying filters during traversal when the index supports it, or falling back to another retrieval path.

def greedy_walk(graph: dict[int, list[int]], dist, entry: int, query) -> int:
    """One layer of an HNSW search: hop to whichever neighbor is closest
    to the query, stop when no neighbor improves. The graph is built so
    this converges instead of wandering."""
    node = entry
    while True:
        best = min(graph[node], key=lambda n: dist(n, query), default=node)
        if dist(best, query) >= dist(node, query):
            return node
        node = best

Lexical and vector retrieval fail differently

Embeddings can make an inverted index look obsolete, but the corpus shows why production systems keep both. For the query “M3GAN”, BM25 treats the title as a rare exact token and gives the matching film a decisive score. Dense retrieval also finds the film, but places it among Ex Machina, Moon, and other stories about artificial intelligence. The embedding preserves the broader meaning while softening the exact characters that identify the title. The comparison instrument in the next section lets you inspect both rankings.

The space-dad request reverses that advantage. BM25 depends on shared words and retrieves Scream, while dense retrieval connects the paraphrase to Interstellar through the meaning encoded in their vectors. Lexical retrieval therefore struggles when the same idea is expressed in different language. Dense retrieval can struggle when a rare string carries the meaning, as it does for titles, product codes, error messages, names, and quoted phrases. Each weakness follows from the evidence the method preserves.

This tradeoff also limits what public embedding benchmarks can tell a team. They narrow the model choices, but their rankings come from benchmark corpora and queries. A leaderboard winner can still trail BM25 on the requests your users make against your documents. The useful comparison is recall measured with representative queries and relevance judgments from your own domain. Chapter 7 develops that evaluation process; here, the complementary failures motivate combining the candidate sets.

Combine candidate sets

Because lexical and dense retrieval preserve different evidence, running both gives the system two opportunities to recover a relevant document. Their candidate sets can be combined into a union, but the scores that produced them cannot be added directly. A BM25 score has no fixed upper bound and changes with the query and corpus statistics. Cosine similarity follows a different scale determined by the embedding model. Adding the raw values would let those incompatible scales decide which retriever dominates.

Reciprocal Rank Fusion (RRF) avoids that comparison by using each document’s position in a ranked list rather than its retrieval score:

Here, d is one document, r is one input ranking, and rank_r(d) is the document’s one-based position in that ranking. A document near the top of either list makes a larger contribution, while one ranked low in both contributes little. The constant k reduces the difference between adjacent positions, preventing the first result in one list from overwhelming the evidence supplied by the other. RRF still requires choices such as k and the number of candidates to retrieve, but it does not require the underlying scores to be calibrated against each other.

Weighted fusion keeps more of the score information. It first normalizes the BM25 and cosine scores within the candidate set, then multiplies them by separate lexical and vector weights. Those weights must be fitted with relevance judgments and checked on held-out queries so the system does not merely memorize the examples used to choose them.

The instrument below compares both approaches over six labeled queries from the film corpus. Select the two running cases to watch fusion combine what each retriever recovered: the space-dad paraphrase, where only dense retrieval reaches Interstellar, and “M3GAN,” where both rank the film first but for different reasons. Each fused candidate shows the contribution from its BM25 position and vector position; select a film to read the calculation. Switch between “RRF” and “Weighted” to inspect how the order changes. In Weighted mode, one balance control keeps the two weights summing to one because scaling both by the same amount cannot change the ranking. “Fit on 6 examples” tests that balance and reports the setting with the highest mean reciprocal rank (MRR). That small search demonstrates the fitting process, but six queries are not enough to establish that the balance will generalize.

def rrf(
    rankings: dict[str, list[dict]],
    rank_constant: int = 60,
) -> list[Result]:
    if rank_constant < 1:
        raise ValueError("rank_constant must be positive")

    candidates = _collect(rankings)
    for candidate in candidates.values():
        candidate["rrf_score"] = sum(
            1.0 / (rank_constant + int(candidate[f"{source}_rank"]))
            for source in rankings
            if f"{source}_rank" in candidate
        )

    return sorted(
        candidates.values(),
        key=lambda candidate: (
            -float(candidate["rrf_score"]),
            min(
                int(candidate[f"{source}_rank"])
                for source in rankings
                if f"{source}_rank" in candidate
            ),
            str(candidate["doc_id"]),
        ),
    )

def weighted_fusion(bm25: dict[str, float], cosine: dict[str, float],
                    lexical_weight: float) -> list[str]:
    """Weighted-additive fusion over normalized scores; BM25 is unbounded,
    cosine lives in [-1, 1]. One free weight: vector gets the remainder."""
    def normalize(scores: dict[str, float]) -> dict[str, float]:
        lo, hi = min(scores.values()), max(scores.values())
        if hi == lo:
            return {d: 0.5 for d in scores}
        return {d: (s - lo) / (hi - lo) for d, s in scores.items()}

    b, c = normalize(bm25), normalize(cosine)
    fused = {
        d: lexical_weight * b.get(d, 0.0) + (1.0 - lexical_weight) * c.get(d, 0.0)
        for d in b.keys() | c.keys()
    }
    return sorted(fused, key=fused.__getitem__, reverse=True)

Across the two queries, the useful evidence changes columns, but the fused ranking can retain it. Hybrid retrieval does not require the system to predict whether the next request will depend on a paraphrase or an exact token before searching. It gives ranking candidates recovered through both representations instead of allowing either retriever’s blind spot to define the pool.

Production scale presses on the baseline

Hybrid retrieval completes the baseline developed in this chapter, but production scale introduces pressures that the baseline does not resolve. The first is cost. Chapter 2 introduced vector quantization as an indexing decision; at millions of full-precision vectors it becomes unavoidable. Compression makes the first search cheaper but can change the nearest-neighbor order, so the recovery pattern retrieves more candidates from the compressed index and rescores that shortlist with the full-precision vectors. This progression from a cheap, wide pass to a more faithful, narrow pass becomes the organizing idea of Chapter 5.

A second constraint is what each stored representation preserves. Representing an entire document with one vector is efficient, but that single vector can blur which passage or term supplied the match. Late-interaction models such as ColBERT retain a separate vector for each token and compare query tokens with document tokens at search time. The finer representation can preserve local evidence while still supporting semantic matching, at the cost of a larger index and more query-time computation. Retrieval quality therefore depends not only on choosing lexical or dense search, but also on deciding how much evidence each stored representation should preserve.

Retrieval can also move beyond a single comparison between one query and one index. Chapter 3 showed how a term-to-document-to-term traversal can learn domain language from the inverted and forward indexes. A related technique searches one representation, collects the leading documents, combines their representations in another space, and searches again. This cross-space form of pseudo-relevance feedback is sometimes called a wormhole vector. Evidence recovered by one retriever becomes the query for another.

These extensions change the cost, representation granularity, or route through the indexes, but they do not change retrieval’s responsibility. For the opening request, retrieval succeeds when Interstellar survives candidate generation alongside plausible alternatives. It has not yet decided that Interstellar belongs first. That decision requires additional signals, more expensive comparisons, and explicit control over where that cost is spent. That is the work of Chapter 5.