Vector Search Infrastructure

Index types and what each trades, the recall/latency dial, filtering, freshness and sharding.

AI EngineeringAdvanced⏱ 1 hour4 min readvector databaseHNSWIVFrecallfiltering

AssumesData Pipelines and Lineage · Vector Search — Exact and Approximate Nearest Neighbours

DefinitionWhat each index type costs

	Build	Memory	Query	Recall	Updates
Flat (exhaustive)	none	vectors only	$O(N)$	1.0 exactly	trivial
IVF (inverted file)	$k$ -means, minutes	vectors + centroids	$O(N/k \cdot n_{\text{probe}})$	tunable via `nprobe`	cheap inserts, drifts from centroids
HNSW (graph)	slow, $O(N \log N)$	vectors + graph, ~1.5×	$O(\log N)$	tunable via `ef_search`	inserts fine, deletes are tombstones

Flat is correct and is the right answer far more often than people expect: at a hundred thousand vectors of 768 dimensions, exhaustive search is a few hundred megabytes and single-digit milliseconds. Do not deploy an approximate index until exhaustive search is genuinely too slow, because the approximate one costs you a recall number you now have to monitor.

PropositionRetrieval recall caps end-to-end quality

Let $R$ be the probability that the document needed to answer is in the retrieved set, and let $A$ be the probability the model answers correctly given it is present. Assuming the model cannot answer correctly without it, end-to-end accuracy is

\Pr[\text{correct}] \;=\; R \cdot A \;\le\; R .

Key idea

Recall is a ceiling, and it multiplies with every other stage exactly as Caching — Hit Rates, Zipf and the Working Set and the pipeline-recall argument describe. Tuning ef_search from 40 to 200 to move recall from 0.92 to 0.98 raises the ceiling by six points — frequently more than a prompt change achieves, and far more measurable.

DefinitionThree ways to combine filters with vector search

Almost every real query is "nearest neighbours where tenant = X and date > Y".

Strategy	How	Fails when
post-filter	retrieve top- $k$ , then drop non-matching	the filter is selective — you asked for 10 and got 2
pre-filter	restrict the candidate set, then search	the set is large; you have lost the index
filtered traversal	apply the predicate during graph/list traversal	needs index support, but is the correct answer

Post-filtering is the default in naive implementations and is the source of the "why did I only get three results?" bug. With a filter matching 1% of the corpus, a top-100 retrieval yields about one result.

HeuristicTwo-tier indexing for freshness

Heuristic — a reasoning shortcut that predicts the right answer in the regimes discussed here. It is not a proof and can fail outside them.

Graph indexes are much cheaper to build in bulk than to update one vector at a time, and deletes leave tombstones that degrade the graph. The standard resolution:

query ──┬──► hot index   (flat, last few hours, rebuilt every few minutes)
        └──► cold index  (HNSW, everything, rebuilt nightly)
              └── results merged and re-ranked by true distance

New documents are searchable within minutes at flat-search cost, because the hot index is small. The cold index is rebuilt offline, which also removes accumulated tombstones and re-centres IVF centroids that have drifted.

What this does not say

Dense retrieval alone under-performs on exact identifiers — part numbers, error codes, names — where lexical matching is strictly better. Production retrieval is usually hybrid, combining BM25 and dense scores, and the combination weight is another dial that needs the same recall measurement as ef_search.

References

PaperY. A. Malkov, D. A. Yashunin (2020). Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World GraphsThe HNSW index whose parameters are discussed below.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

DefinitionWhat each index type costsFlat, IVF and HNSW trade build time, memory and query latency against recall in different proportions.
PropositionRetrieval recall caps end-to-end qualityproof includedAn answer that requires a document the retriever did not return cannot be produced, so index recall multiplies into every downstream metric.
DefinitionThree ways to combine filters with vector searchPre-filtering, post-filtering and filtered traversal differ in whether they can silently return too few results.
HeuristicTwo-tier indexing for freshnessA small frequently-rebuilt hot index beside a large periodically-rebuilt cold one gives low write latency without paying incremental-update costs on the whole corpus.