From Similarity to Search

Part III — Retrieval Is an Experiment

Retrieval in four lines

# assume embed() returns L2-normalized vectors, so dot product == cosine (Chapter 4)
query_vec = embed(query)                    # one unit vector
scores    = corpus_vecs @ query_vec         # a cosine score for every document
order     = np.argsort(-scores)             # rank all n documents, best first
results   = [corpus[i] for i in order[:k]]  # keep the top k

That is the whole primitive for the simple policy shown here. A vector database may add several different kinds of machinery around it: an ANN index or quantization may approximate the same ranking more cheaply; sharding may distribute the computation; filtering may change the eligible candidate set; persistence and replication may make the system operable. Do not collapse all of those into “faster search” — some preserve the target policy, some approximate it, and some redefine it.

A note on the second and third lines. corpus_vecs @ query_vec is a dot product; it equals cosine only because we assumed unit vectors (Chapter 4). This brute-force implementation spends about O(n d) arithmetic to score all n documents. That is the cost of exhaustive scoring, not a theorem that every exact nearest-neighbor method must inspect every vector: exact indexes can sometimes prune candidates while preserving the answer, depending on the metric, dimensionality, and data geometry. The full sort on the third line is O(n log n), but returning only the exact top k does not require it — argpartition, a bounded heap, or another exact selection method can recover the top set more cheaply. Treat these four lines as the transparent reference implementation, not as the only exact algorithm or the fastest one.

The reason to start here is attribution. Once an index, a threshold, a query rewrite, a permission filter, and a de-duplication step are all active, a quality change could have come from any of them. The primitive fixes a reference for a simple policy: given a query representation, an eligible candidate set, a score function, k, any threshold, and a deterministic tie rule, the ranked selection is defined. If de-duplication or diversity is part of the intended output, that rule belongs in the reference policy too. Everything else is either a deliberate change to that target or an alternative way of computing it.

What exactly is a retrieval system deciding, and which of its parameters change that decision rather than just how fast it is computed?

Similarity is a score; retrieval is a procedure

A similarity is one number about two texts. Retrieval is a decision procedure built around many such numbers. Written out, it has these stages:

1. Query representation. Construct one or more retrieval vectors and an aggregation rule for combining their results.
2. Candidate eligibility. Decide which documents are even allowed to be returned — permission filters, date and source filters, corpus version.
3. Scoring. Apply the score function to each eligible candidate.
4. Ranking. Order the candidates by score, with a defined tie-break.
5. Selection. Apply k and any threshold.
6. Set shaping (optional). De-duplicate or diversify.
7. Return.

Call stages 1–6 the retrieval policy: the set that should be returned if every computation were exact. A concrete policy reads like “the ten highest-cosine documents the user is authorized to see, with cosine ≥ 0.42, collapsed so no two share a source.” The four-line primitive is one exact implementation of a simple policy (no filter, no threshold, no de-duplication).

Two layers: policy and execution

Separate from the policy is the execution strategy — how the answer is actually computed:

• exhaustive scoring (the primitive);
• HNSW, IVF, or another approximate-nearest-neighbor (ANN) index;
• product quantization or another compressed representation for approximate distances;
• distributed shards.

An ANN index is designed to compute the same policy answer, faster. But designed-to-preserve is not guaranteed-to-preserve: its parameters can change the set it returns. That gives the chapter’s governing rule:

Exact search tells you what your retrieval policy asked for. An ANN index tells you how closely your implementation reproduced it.

Two failure surfaces, stacked:

query
  │
  ▼
representation
  │
  ▼
exact vector ranking      ← semantic retrieval quality can fail here (Chapter 10)
  │
  ▼
ANN implementation        ← computational fidelity can fail here (this chapter)
  │
  ▼
returned candidates

And one more thing the primitive is not: it is not semantic truth. The exact top k is the reference output of the specified vector retrieval policy — the documents the geometry ranks highest under your metric. Whether those documents are the right answer is a separate question, and the next chapter is about the cases where the exact top result is fluent, on-topic, geometrically closest, and wrong. An ANN index that reproduces a bad exact ranking perfectly has done its job; the index is blameless and the answer is still wrong.

    flowchart TD
    Q[query] --> QT["query construction — one or more retrieval representations + an aggregation rule"]
    QT --> E["embed — model + normalization (determines the score geometry below)"]
    E --> CE["candidate eligibility — permissions, filters, corpus version"]

    CE --> EX["exact execution — score eligible candidates with dot / cosine / L2"]
    EX --> SR["rank; apply k and threshold"]

    CE --> ANN["approximate execution — HNSW / IVF / PQ candidate search"]
    ANN --> ASR["approximate ranking / top-k under the same target policy"]

    SR --> PP["optional policy step: source-aware duplicate collapse or diversity reranking"]
    ASR --> PP
    PP --> R[results]
  

The parameters that change the target answer

Change any of these and the policy is different — a perfect exact search now returns a different set.

• The representation. Which model, which normalization (Parts I–II). It determines the score geometry every comparison runs in.
• The metric. Dot vs. cosine vs. L2 (Chapter 4). Same vectors, different order when norms vary.
• The candidate universe. Permission filters, date/source/category filters, corpus version. Permission filtering is a correctness and security concern, not a ranking preference: if permissions are part of the contract, the exact reference must already exclude unauthorized items. Non-permission filters are a product decision about what “eligible” means.
• k. The size of the returned set. It moves the operating point of downstream recall, precision, context cost, and latency. Whether raising k raises recall and lowers precision is an empirical fact about your workload, not a mathematical law — measure it.
• The threshold. A score-admission rule separate from k: for a similarity score it may be a minimum; for a distance it may be a maximum. Without an admission rule, top-k returns k items whenever at least k candidates are eligible, even when the application should have said “no sufficiently supported match” (Chapters 10 and 14). A raw threshold is meaningful only with its space, metric, normalization, and calibration; it does not automatically transfer across model or space versions.
• Query construction. Raw query, expanded query, a HyDE-style embedded hypothetical answer, or multi-query — which produces several representations and combines their rankings or candidate sets. This changes every score downstream, which is why it belongs in the retrieval spec rather than in prompt folklore.
• De-duplication / diversity. Discussed below; it changes which set comes back.

Filtering: semantics, then execution

It is often said that pre-filtering and post-filtering “give different results.” That is not inherently true, and the distinction that matters is between the filter’s semantics and where it is executed.

If the policy is “the top k among allowed documents,” then these two exact procedures return the same set:

1. Remove disallowed documents, then rank the rest and take the top k.
2. Score everything, remove disallowed documents, then take the top k of what remains.

The difference appears when “post-filter” actually means: retrieve the unfiltered top k (or top N), discard the disallowed ones, and stop. That truncated procedure can under-fill the result, or miss an allowed document that would have ranked highly within the permitted subset. With an ANN index the stakes rise: pre-filtering can change graph traversal or candidate generation, and post-filtering usually requires over-fetching to avoid under-filling. Decide the semantics first — “top k among allowed” — then choose an execution that actually delivers it.

De-duplication, provenance, and diversity are three operations

Real corpora contain repeated text, and naive top-k fills with it. But “these five passages are similar” supports several different conclusions, and the right response depends on which one holds:

• Exact duplicate chunks — byte- or content-identical material may be accidental repeated ingestion, intentional replication, or the same passage attached to different provenance. Detect the duplication first; collapse it only according to the application’s source/provenance policy.
• Near-duplicate text — could be syndication, a shared quotation, templated boilerplate, or genuinely independent sources making the same point. Semantic similarity alone does not establish copying or dependence; provenance metadata is needed.
• Diversity reranking (MMR and similar) — deliberately changes the ranking objective, trading the base relevance score against novelty or coverage. It may suppress semantically redundant results, but that is not the same operation as proving two records are duplicates.

The evidence-integrity point runs through the whole book: a retrieval system should not collapse genuinely independent corroboration just because the texts look alike, and it should not feed a downstream model five copies of one source that then reads them as five agreeing sources. A de-duplication policy ideally consults source and provenance metadata alongside similarity.

Predict, then measure: HNSW vs. exact on RELATE

An ANN graph traversal explores a subset of the corpus. So a reasonable prediction: it will sometimes return a different top k than exact search — most likely dropping a true neighbor when the margin to the runner-up is small and a slightly longer search would have found it.

MEASURED on RELATE v0.1, Wave 1 row 1.6 — artifact experiments/embeddings-from-first-principles/wave1/artifacts/ann-vs-exact.json. Model all-mpnet-base-v2; hnswlib, cosine space, M = 16, ef_construction = 200. 1,173 items, 269 queries. A fresh index is built for each ef_search value.

Two things are measured per query, and they answer different questions:

• Exact-top-10 overlap — |ANN_top10 ∩ exact_top10| / 10, averaged over the 269 queries. This is a set overlap: it says nothing about ordering, so returning the same ten documents in reverse order still scores 1.0.
• Preservation of already-found relevant items — for each query, take the grade-≥2 items that exact retrieval placed in its top 10 and measure the fraction of those also present in ANN top 10. The implementation averages this fraction only over queries for which exact_top10 contains at least one grade-≥2 item; queries with no such exact-top-10 relevant item contribute no value to this statistic. It is therefore a conditional preservation metric, not end-to-end Recall@10 over the full relevant set. It asks one narrow attribution question: when exact search had already surfaced a relevant item, did the approximation keep it?

ef_search   exact-top-10 overlap   relevant items from exact top-10, preserved
10                0.9937                        1.0000
20                1.0000                        1.0000
40                0.9993                        1.0000
80                1.0000                        1.0000
160               0.9996                        1.0000

The prediction barely landed. The lowest exact-top-10 overlap is 0.9937, at ef_search = 10; every setting is at or above that, and several are effectively perfect at this precision. The curve is not monotonic (0.9937 → 1.0000 → 0.9993 → 1.0000 → 0.9996). Those reversals are tiny, and because the implementation builds a fresh HNSW index inside each ef_search iteration, do not read them as a clean query-effort response curve from one fixed graph. The safe statement is that every tested configuration achieved at least 0.9937 mean exact-top-10 set overlap. The conditional relevant-preservation statistic is 1.0 throughout: among queries whose exact top 10 contained at least one grade-≥2 item, ANN preserved all such exact-top-10 relevant items in this run.

MEASURED: on RELATE v0.1 (1,173 items, 269 queries) with HNSW (M = 16, ef_construction = 200), every tested configuration from ef_search = 10 to 160 reproduced at least 99.37% of the exact top-10 set on average. The conditional relevant-preservation metric was 1.0000 at every setting. Under this workload and implementation, the measured approximation debt was very small.

What this establishes. We built the instrument that would expose ANN fidelity debt — set overlap against exact, plus preservation of already-found relevant items — and under this workload it found almost none.

What it does not establish.

• What kind of neighbors an index misses when debt is real. The artifact records overlap and relevant-preservation only. It contains no exact-score margins, no near-tie flags, no easy-versus-hard error breakdown, no assessment of what the misses were worth. The idea that ANN error concentrates on the hardest, closest-margin neighbors is not measured here; treat it as an open question for a larger experiment.
• That corpus size is why the result is near-perfect. ANN fidelity depends on corpus size, dimensionality, M, ef_construction, ef_search, insertion order and seed, data distribution, density, duplicates, query distribution, metric, and library. This run held all of those fixed. Isolating any one requires a sweep.
• Any latency claim. The artifact has no timing. At 1,173 vectors exhaustive scoring is computationally modest in principle, but “how modest,” and how it compares to the index, was not measured here.

Fidelity and utility are different questions

When an approximate result differs from exact, there are two separate comparisons:

• Fidelity — did the implementation reproduce the exact vector-retrieval reference? Compare ANN output to exact output.
• Utility delta — did using ANN make the task metric better, worse, or unchanged relative to the exact reference? Score both systems on the same task evaluation and compare them.

                           ANN task metric ≈ exact     ANN task metric worse than exact
ANN ≈ exact                 implementation faithful;  any poor absolute task score is not
                            little ANN-induced change  explained by approximation fidelity

ANN differs from exact      approximation debt exists approximation debt is accompanied by
                            but this metric is stable  measured task harm under this evaluation

The absolute quality of exact retrieval is a third fact. Exact and ANN can both score badly because the representation or retrieval policy is bad; ANN can also differ substantially while leaving the chosen task metric unchanged. Therefore ANN ≠ exact plus “task metric bad” is not enough to blame approximation. Attribution requires the task delta relative to exact, not merely the ANN system’s absolute score.

What this chapter establishes and what it does not

Establishes: retrieval is a policy (query representation, candidate eligibility, scoring, ranking, selection, optional set shaping) with a separate execution strategy; the exact primitive is a reference implementation of the policy but not semantic truth; ANN attempts to compute the same policy answer approximately; fidelity (vs. exact) and utility (vs. labels) are distinct measurements; and on RELATE v0.1, HNSW reproduced the exact top 10 to within ≥99.4% overlap at every tested ef_search, preserving every already-found relevant item.

Does not establish: which index to use (workload-dependent); that approximate search is unsafe at scale (this run cannot speak to scale); what neighbors an index misses when debt is substantial; that corpus size caused the near-perfect result; or any latency ordering — the artifact has no timing.

Lab 9: define exact retrieval, then approximate it

MEASURED — artifact experiments/embeddings-from-first-principles/wave1/artifacts/ann-vs-exact.json (mpnet-base, HNSW, M = 16, ef_construction = 200). REPRODUCIBLE — run_wave1.py 1.6.

Question. What does an index cost against the exact reference — and would you notice under this workload?

Step 1 — define exact retrieval. Freeze the corpus, the query set, the embedding space, the query and document embedding roles, the normalization, the score function, the candidate filters, k, the threshold, and the tie-break rule. Compute the exact top-k for every query.

Step 2 — build HNSW. Record M = 16, ef_construction = 200, cosine space, the library and version, and a corpus hash / index id.

Step 3 — sweep ef_search ∈ {10, 20, 40, 80, 160}. Measure exact-top-10 overlap for each.

Step 4 — measure relevant-result preservation, defined precisely: the fraction of grade-≥2 items that exact retrieval placed in its top 10 which also appear in the ANN top 10. This is conditional on the exact top 10 — do not call it total graded Recall@10.

Step 5 — read the negative result.

Minimum exact-top-10 overlap is 0.9937; the conditional preservation statistic is 1.0 at every setting. Under this workload and implementation, there was almost no fidelity debt to find. If you looked only at that conditional grade-based column, every configuration would appear identical at 1.0 and the small divergence from exact at ef_search = 10 would disappear. The against-exact column is what exposes approximation debt independently of whether the lost exact results happened to carry grade≥2 labels.

Step 6 — design the experiment that could reveal debt (PROPOSED — no artifact backs these).

scale:            1k → 10k → 100k → 1M vectors
distractors:      add controlled near-neighbor distractors around exact-policy top-k candidates
fixed-index ef:   build one graph, then sweep ef_search on that fixed graph where the library permits
build variance:   vary M / ef_construction and repeat independent builds or seeds; report spread
timing:           exact latency, HNSW latency, build time, memory, throughput
miss analysis:    for each exact result the index drops, log exact rank, exact score,
                  adjacent score margins, graded relevance, and query/relation slice;
                  then test rather than assume whether misses concentrate near small margins
k:                repeat at k ∈ {1, 5, 10, 50}
filters:          add an authorization filter and test whether each execution strategy
                  still implements "top-k among authorized candidates"

Try it yourself

On your own corpus, run Steps 1–5, then the PROPOSED miss analysis. When the index does drop an exact result, do not assume a small score gap means the swap was harmless. A small gap tells you the geometry viewed the two candidates as similar — not that they are interchangeable. Two candidates with nearly identical cosine can differ in correctness, permission, temporal validity, provenance, negation, or which entity did what. Use the labels and the task metric to judge whether a substitution mattered; the score gap alone cannot.

Companion component: the retrieval spec

The spec records the target policy, the execution strategy, and the measured fidelity separately, so that when an output changes you can ask which layer moved.

retrieval_spec:
  space_record:            <from Chapter 1>
  query_embedding_role:
  document_embedding_role:
  similarity_spec:         <from Chapter 4>

  candidate_policy:
    corpus_version:
    filters:               <date | source | category | ...>
    permissions:           <the authorization rule; unauthorized items are never eligible>

  ranking_policy:
    k:
    threshold:             float | none        # how it is set: Chapter 14
    tie_break:             <deterministic secondary key>
    query_transform:       <raw | expand | hyde | multi(+aggregation rule)>
    dedup_or_diversity:    <none | collapse_by_source | mmr(lambda) | cluster>

  execution:
    method:                <exact | hnsw | ivf | +pq | ...>
    index_id:              <build identity / hash>
    build_params:          <metric, M, ef_construction, nlist, seed, library@version>
    search_params:         <ef_search, nprobe, ...>
    quantization:          <none | pq(m) | ...>

    fidelity:                # bound to a workload, not a permanent property of the index
    exact_reference_id:
    measured_on:           <query set, k, corpus version, filters>
    topk_set_overlap:
    top1_agreement:
    rank_fidelity:         <optional rank-sensitive comparison>
    exact_topk_relevant_preservation:
                          <conditional metric; define denominator explicitly>
    task_metric_exact:
    task_metric_approx:
    task_delta:

Two details earn their place. First, tie_break: if several documents have equal scores around position k, two correct implementations of the numerical scoring rule can still return different sets — a deterministic secondary key removes that ambiguity. Second, fidelity.measured_on: a fidelity result measured on RELATE cannot simply be carried to production traffic, because it depends on the query set, k, index build, search parameters, filters, and data distribution. The current Wave 1 artifact directly supplies only the exact-top-10 set-overlap metric and the conditional relevant-preservation metric; fields such as top-1 agreement, rank-sensitive fidelity, latency, and task delta are recommended extensions until separately measured. The spec’s real job is to be an attribution boundary — when output changes, it tells you whether the policy, the space, candidate eligibility, execution, or measured fidelity is what moved.

Failure modes

• Adding an index before defining the exact reference. Tempting because the index is the interesting engineering. Check: you cannot measure approximation debt without a reference to measure against — build the exact top-k first.
• Evaluating the index against labels only. Tempting because the task metric is what you ultimately care about. Check: a task score can stay flat while the ANN result drifts from exact; measure overlap against the exact primitive too.
• Evaluating against exact only. Tempting because perfect fidelity feels like success. Check: reproducing a semantically wrong exact ranking is faithful computation, not a good answer — Chapter 10.
• Confusing filter execution with filter semantics. Tempting because “filter then search” and “search then filter” sound equivalent. Check: a retrieve-top-k-then-discard implementation can under-fill a policy that meant “top k among allowed.”
• De-duplicating without provenance. Tempting because similar text looks redundant. Check: semantic similarity can collapse genuinely independent corroboration; use source metadata, not cosine alone.
• Leaving the index configuration unversioned. Tempting because the defaults “just work.” Check: record the build/search parameters and implementation identity needed to recreate the index — for HNSW, at least the metric, M, ef_construction, ef_search, corpus/index version, and library version, plus construction seed or build identity where the implementation exposes them. The current artifact records some but not all of that provenance, which is exactly why the retrieval spec should.
• Setting a threshold without calibration. Tempting because one number in a config is easy. Check: a raw score threshold does not transfer across spaces or model versions (Chapter 14).

What this chapter established

• Retrieval policy (what answer is requested) and execution strategy (how that answer is computed) are separate layers. The four-line primitive is a transparent exact reference for a specified policy — not the only exact algorithm, and not semantic truth.
• Fidelity to exact and task utility answer different questions. Attributing harm to approximation requires comparing the approximate task metric against the exact-reference task metric, not against absolute quality.
• On RELATE, every tested HNSW configuration reproduced at least 99.4% of the exact top-10 set. We built the instrument that would have exposed approximation debt and found almost none — which removes exactly one suspect, and no more.
• Filter semantics, filter execution, source-aware duplicate handling, and diversity reranking are distinct operations with different correctness consequences. The retrieval spec keeps policy, execution, and workload-bound fidelity separate so that a later failure can be attributed to one of them.

Next

Perfect index fidelity removes exactly one suspect. This chapter asked whether the search implementation returned the neighbors the vector geometry requested; the RELATE experiment says, here, it did. The next chapter asks the question underneath: were those neighbors actually right? It builds the cases where the nearest neighbor is fluent, on-topic, geometrically closest — and wrong.