Retrieval

The previous chapter ended with a better-specified request ready for retrieval: “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.” Retrieval begins with that gap between the remembered plot and the language stored in the corpus.

The visualization above shows the evidence available to cross it. An embedding model converted each film summary into a vector with 384 coordinates, far more axes than a screen can display. Rotate the 3D view, then switch to the cluster map to inspect the same films flattened into a plane. 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. These views are projections made for inspection; retrieval still uses the original 384-dimensional vectors.

The question is whether that representation can recover Interstellar without losing the exact names and phrases that identify other films. Lexical retrieval searches the terms stored in an index. Dense retrieval compares the learned representations of complete texts. Their different matching rules create different failures, and those failures determine which films survive for ranking.

Lexical retrieval scores exact term matches

The most direct way to search for the space-dad request is to compare its terms 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.

For the opening request, each query term opens one posting list. An AND query intersects the lists and keeps only films containing every term, while a broader query takes their union and keeps any film containing at least one. Either operation produces candidates. Deciding which candidate best matches the request requires a score.

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. Diamond-marked titles appear in every posting list, while the broader BM25 ranking scores any film matching at least one term and 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. The score changes because k1 and b change how the same indexed evidence is valued, which makes BM25 an explicit judgment rather than a fact stored with the document. The next question is whether the evidence it can value includes the connection between the request and Interstellar.

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]

Exact terms leave Interstellar behind

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. As long as each query term can contribute only through its own posting list, BM25 has no direct evidence connecting “ages slowly” with time dilation and children growing old.

Dense retrieval changes the matching problem

That exact-term condition comes from how lexical retrieval represents 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.

SPLADE is a learned sparse retriever that can add terms inferred from context before scoring them in this traceable term space. That expansion can bridge some vocabulary gaps while preserving term-level matches, but its quality depends on how well the model’s training transfers to the current corpus. It extends the lexical representation rather than removing the need for another way to compare complete meanings.

Dense retrieval supplies that comparison by changing the representation. The embedding model maps each text to learned coordinates whose individual dimensions do not carry labels such as “space” or “horror.” Together, those coordinates form a latent space, with evidence distributed across the complete vector. A query and a summary can therefore occupy nearby regions even when they share no exact terms.

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 vectors into two dimensions so their neighborhoods can be inspected. Drag the ringed query probe and watch which films enter its neighborhood. You can also place two anchors to inspect the region between their meanings. The projection preserves some local structure but distorts distances, so it illustrates the geometry rather than reproducing the cosine ranking. 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

Recovering Interstellar by comparing the query with every document vector 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 shortened search reduces latency by accepting a new risk: it may miss a relevant neighbor. Retrieval recall measures how much of the relevant candidate set the search successfully recovers.

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 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. Watch how the upper layers cross the graph before the lower layer searches the local neighborhood.

The short route shows the intuition behind approximate nearest-neighbor search: reach a useful neighborhood without scoring every film as a candidate. The hop count is not a complete latency measurement because each hop still compares connected nodes, and the route is illustrative rather than an exact implementation of production HNSW.

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. The size of the candidate set kept during search, called efSearch in HNSW implementations, widens or narrows each descent. The number of links per node, M, fixes the graph’s density at build time. Both parameters 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

The two retrievers preserve different evidence

Dense retrieval recovered the space-dad paraphrase, but that success does not make the exact path disposable. 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 two running requests now occupy opposite cells. Dense retrieval preserves the semantic connection needed to recover Interstellar, while BM25 preserves the rare token that identifies “M3GAN.” The same division appears with product codes, error messages, names, and quoted phrases: a paraphrase favors distributed meaning, while an identifier favors exact characters. Each weakness follows from the evidence the method preserves.

These reversed outcomes also limit what public embedding benchmarks can tell a team. Benchmarks can narrow the model choices, but their rankings come from other corpora and queries. A leaderboard winner can still trail BM25 when the current traffic depends heavily on exact identifiers. The useful comparison is recall measured with representative queries and relevance judgments from the system’s 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 discarding score magnitude and using each document’s position in a ranked list instead:

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.

Discarding magnitude makes RRF robust to incompatible scales, but it also throws away information about the distance between adjacent results. Weighted fusion keeps more of that 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. Start with the two running cases. For the space-dad paraphrase, only dense retrieval reaches Interstellar. For “M3GAN,” both paths rank the film first, though they arrive there from different evidence. Select a candidate to see how its BM25 and vector positions contribute to the fused score.

Then switch between “RRF” and “Weighted” to inspect what changes when score magnitude is allowed to matter. In Weighted mode, one balance control keeps the lexical and vector 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). The 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)

The useful evidence changes columns across the two requests, but the fused ranking can retain it. Interstellar survives through dense retrieval without sacrificing the exact-token path that protects “M3GAN.” Hybrid retrieval therefore gives ranking candidates recovered through both representations instead of allowing either retriever’s blind spot to define the pool.

A stronger candidate set still has a cost

The fused candidate set preserves more evidence, but production scale determines how broadly either path can search. 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.

The candidate set also inherits the granularity of the stored representation. 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.

Finally, the candidates from one path can change the next retrieval request. 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. In this cross-space form of pseudo-relevance feedback, sometimes called a wormhole vector, evidence recovered by one retriever becomes the query for another.

Cost determines how broadly retrieval can search, granularity determines which match evidence survives, and the route through the indexes determines whether one pass can inform another. None changes 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.