InterviewsVector
Arc 7
Build labAdvanced115 min estimateOriginal publication

Approximate Nearest Neighbors Under a Latency Budget

An ANN index is an explicit exchange of exact search work for a workload-specific error and operations envelope.

Authorship
InterviewsVector
Published / updated
2026-09-20 / 2026-09-20
Review status
Artifact tests passing · primary sources recorded

Original InterviewsVector teaching. Executable illustrative contracts are covered by focused tests and primary sources are recorded. No named human review, benchmark result, or production certification is claimed.

The decision in one pass

Choose an approximate-nearest-neighbor index only from evidence measured against exact top-k neighbors on the real embedding contract and workload. HNSW uses a navigable graph and typically trades graph memory and construction/update behavior for strong search at tuned exploration. IVF partitions vectors into coarse lists and searches a selected number of lists, making training quality and probe count central. Compression can reduce memory while introducing another approximation. Compare recall@k by meaningful slices, p95 and tail latency under concurrency, memory, build time, filtering, update visibility, deletion, and recovery. Tune search parameters on held-out queries; do not treat a library default or a single average QPS number as an architecture decision.

Why this matters

ANN errors are upstream omissions: a reranker or generator cannot recover a document that candidate generation never returned. Yet demanding exact search at every scale can violate latency and cost bounds. The engineering problem is to spend a declared error budget without hiding filter, freshness, deletion, or tail-latency failures.

You will be able to

  • Define exact top-k evidence and compute recall@k rather than trusting self-reported ANN scores.
  • Explain the core search controls and operational tradeoffs of HNSW and IVF families.
  • Evaluate filtering, updates, deletion, build, memory, and latency alongside unfiltered recall.
  • Build an immutable candidate decision record tied to corpus, embedding, parameters, and query set.
  • Stage index rollout and rollback without mixing representations or losing source obligations.

Your Vector Loop for this lab

  1. 01

    Model

    Bind corpus, embedding contract, exact baseline, query set, filters, concurrency, and service objectives.

  2. 02

    Derive

    Derive recall@k and tail-latency measurements, then map HNSW exploration and IVF probing to work performed.

  3. 03

    Build

    Evaluate candidate indexes with immutable builds, exact parameter digests, and slice-preserving evidence.

  4. 04

    Stress

    Attack rare filters, clustered data, cold caches, updates, deletions, restarts, memory pressure, and constructor bypasses.

  5. 05

    Operate

    Shadow, canary, observe candidate misses and freshness, and retain an exact or prior-index rollback route.

  6. 06

    Defend

    Defend a candidate from bound evidence while refusing to generalize synthetic or single-machine measurements.

Approximation needs an exact reference

For each held-out query, compute exact neighbors under the same vector revision, metric, filter predicate, and tie policy. The approximate result is evaluated against that set. Keep query identities and exact neighbor identities in the evidence so a candidate cannot be compared against a different corpus snapshot or easier query cohort.

Recall@k(q) = |ANNₖ(q) ∩ Exactₖ(q)| / k; macro recall = (1/|Q|) Σq Recall@k(q)

Macro averaging gives each query equal weight. Report slice distributions and confidence as well; the illustrative artifact uses a tiny deterministic fixture and makes no statistical claim.

Graph exploration and partition probing spend work differently

ConcernHNSW-style graphIVF-style partition
searchnavigate layered proximity links and expand a candidate frontierassign query to coarse centroids and scan selected inverted lists
quality controlincrease search exploration such as efSearchincrease lists probed such as nprobe; optionally refine compressed results
memoryvectors plus graph links and allocator overheadcentroids, list IDs, vectors or compressed codes, and optional refine storage
buildincremental graph construction depends on insertion and construction settingscoarse quantizer requires representative training before population
filter/update riskpost-filtering can exhaust viable neighbors; mutation and deletion semantics are implementation-specificfilters can leave probed lists sparse; retraining and list imbalance affect maintenance

The families are not single points. Storage format, quantization, graph degree, construction effort, probes, refinement, and hardware change the frontier. Record the complete parameter set and binary/index revision, not only the family label. A paper result explains a method on its datasets and machines; it is not your capacity plan.

Latency is only one binding budget

Measure p50, p95, and p99 latency at representative batch size and concurrency, including filter evaluation and vector fetches. Account for resident memory, transient build memory, replicas, snapshots, and recovery. Track build duration and update visibility because an index that answers quickly but remains stale is not meeting a freshness objective. Exercise deletion and authorization after index mutation, restart, and restore.

  • Stratify exact recall by tenant, language, filter selectivity, query difficulty, source type, and newly added content.
  • Warm and cold cache states separately; make compaction, snapshot, and background-build interference visible.
  • Measure the same metric and k used by the serving system, including deterministic tie policy.
  • Record failure behavior: timeouts, partial results, empty filtered sets, unavailable shards, and stale replicas.

Choose from the whole evidence envelope

A low-memory candidate can still fail filtered recall or update visibility, and a high-recall graph can still exceed a replica budget. This bounded lab isolates recall@10, p95 latency, and additional index memory: set all three inclusive bounds, reject any row outside them, then choose the lowest-latency survivor. The executable decision record below extends the same qualification discipline to filtered recall, build, update, and deletion evidence.

Spend the search budget deliberately

Set recall@10, p95 latency, and additional-index-memory bounds, then predict the lowest-latency measured candidate that satisfies all three. The values are illustrative evidence, not vendor or hardware benchmarks.

Choose an ANN configuration from measured bounds

Set an acceptance envelope, then choose the lowest-latency measured candidate that satisfies every bound. This original synthetic benchmark is an arithmetic teaching fixture, not a production performance claim.

Whole number 90–100. Clear to replace; blur or Escape restores the last valid value.

Whole number 4–50. Clear to replace; blur or Escape restores the last valid value.

Whole number 0–256. Clear to replace; blur or Escape restores the last valid value.

Selection rule: first reject any row outside a bound; among the remaining rows, choose the lowest measured p95 latency. Equality satisfies a bound.

Frozen benchmark observations

One synthetic 100,000-vector corpus, one fixed query set, and one declared hardware profile. Every row uses the same vectors and similarity policy.

Synthetic observations for exact, graph, and partitioned retrieval candidates
CandidateRecall@10p95Extra memory
Exact scanFlat scan over every stored vector.100%42 ms0 MiB
Graph indexFixed HNSW build and search settings.97%8 ms180 MiB
Partitioned indexFixed IVF training and probe settings.93%5 ms44 MiB

“Extra memory” means index overhead beyond the shared stored-vector bytes. These observations do not transfer to another corpus, filter workload, update rate, implementation, or machine.

Which measured candidate should this rule select?

Select a prediction, then check it against the recorded evidence.

Audit candidate evidence instead of marketing labels

The artifact binds corpus, embedding contract, query set, exact baseline, index and parameter digests. It recomputes unfiltered and filtered recall from identities, calculates p95 latency, and gates memory, build, update, and deletion evidence. The declared selection rule chooses the least-memory qualified fixture candidate, then latency, but that rule is an explicit teaching policy rather than a universal objective.

ann_index_audit.py
1def main():
2    result = audit(example_contract())
3    selected = next(report for report in result.reports if report.candidate_id == result.selected)
4    print("example=illustrative_only")
5    print("selected=" + result.selected)
6    print(f"qualified={sum(report.qualified for report in result.reports)}/{len(result.reports)}")
7    print(f"selected_recall={selected.recall:.3f}")
8    print(f"selected_p95_latency_ms={selected.p95_latency_ms:.3f}")
9    print("claim=" + result.claim)

Expected output

example=illustrative_only
selected=hnsw-m16
qualified=1/2
selected_recall=1.000
selected_p95_latency_ms=5.000
claim=FIXTURE_DECISION_NOT_A_BENCHMARK

Verify: python3 -m unittest discover courses/ai-engineering/reference-impl/ann_index

Index releases are recoverable system changes

  1. 01Build immutablyCreate the candidate from one corpus and embedding snapshot; record parameters, binary, hardware, and checksums.
  2. 02Prove offlineCompare with exact search on frozen held-out queries, filters, recent writes, deletions, and tail slices.
  3. 03Shadow onlineReplay production-shaped queries without changing responses; compare misses, latency, load, and freshness.
  4. 04Canary and cut overRoute a bounded cohort through an explicit read alias while preserving the prior index and rollback trigger.
  5. 05Reconcile obligationsVerify every write, update, ACL change, and deletion across both indexes before contraction.

Operate at three altitudes

Production lens

  • — Track exact-sampled recall, filtered recall, tail latency, memory, build/recovery time, update lag, and deletion completion by index revision.
  • — Keep corpus, embedding, parameter, binary, and query-set identities on every benchmark and release decision.
  • — Rehearse shard loss, cold restart, snapshot restore, and dual-index reconciliation before making a candidate the default.

Staff lens

  • — Define which quality, latency, memory, freshness, and compliance constraints are gates and which objective ranks candidates after qualification.
  • — Fund exact-reference sampling and representative filtered cohorts as permanent infrastructure, not one-time launch analysis.
  • — Reject cross-team index comparisons that do not share corpus, embeddings, metric, hardware, concurrency, and workload evidence.

Interview defense

How would you choose between HNSW and IVF for a filtered retrieval service with frequent updates?

I bind the same corpus snapshot, embedding contract, metric, k, filter semantics, and exact baseline, then evaluate parameterized candidates rather than family names. I recompute recall@k overall and by filter selectivity, measure tail latency under production concurrency, and account for memory, build/recovery, update visibility, deletion, and imbalance. HNSW spends memory and graph exploration; IVF spends coarse training and list probes, with optional compression. I shadow and canary an immutable index revision, dual-write and reconcile changes, and preserve the prior index for rollback. The decision is workload evidence, not a generic winner.

Expect the interviewer to press on

  • — Why measure filtered recall separately?
  • — What does increasing nprobe change?
  • — How do you roll back without resurrecting deleted data?

Misconceptions to remove

“ANN recall is the same as answer accuracy.”

ANN recall measures overlap with exact neighbors. Reranking, context assembly, and generation have separate outcomes.

“HNSW is always faster and IVF is always smaller.”

Parameters, storage, compression, data geometry, filters, hardware, and workload determine the measured frontier.

“A one-machine benchmark chooses the production index.”

Production evidence must include concurrency, replicas, cache state, filters, updates, failures, recovery, and representative slices.

Check your model

1. Why bind exact neighbor IDs instead of accepting a recall field?

The audit can recompute recall and verify that every candidate used the same exact baseline and query cohort.

2. What can make filtered ANN recall worse than unfiltered recall?

Post-filtering may remove explored candidates, while pre-filtering can make the searchable subgraph or probed lists sparse; the effect depends on implementation and selectivity.

3. When should a smaller-memory candidate still be rejected?

Whenever it fails a declared quality, latency, build, update, deletion, recovery, or compliance gate.

Prove the mechanism

Construct exact top-10 evidence for 100 queries across two filter-selectivity slices. Compare two parameterized ANN candidates and write the first blocking gate for each without using downstream answer quality as a substitute.

Add a production constraint

Design a zero-downtime index migration with frequent writes and hard deletions. Specify dual-write ordering, reconciliation, shadow reads, canary criteria, rollback state, and the later old-index destruction authorization.

Artifact: ANN index decision record

courses/ai-engineering/reference-impl/ann_index/ann_index_audit.py

Download reference implementation

Primary references and next links

References

  1. 1. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs

    Malkov and Yashunin. Primary HNSW method and experimental study.

  2. 2. Billion-scale similarity search with GPUs

    Johnson, Douze, and Jégou. Primary Faiss systems work on exact, approximate, and compressed similarity search.

  3. 3. Faiss IndexIVF documentation

    Faiss. Official documentation for inverted-list search and multi-probe behavior.

  4. 4. Faiss IndexHNSW documentation

    Faiss. Official documentation for the HNSW graph structure exposed by Faiss.

Continue through the graph

Glossary: approximate nearest neighbor · recall@k · HNSW · inverted file index · nprobe · quantization · tail latency · exact baseline