Wiki
Core12 min read

Vector databases and approximate search

Embeddings are only useful if you can find the nearest ones. Exact search is O(N·d); approximate indexes trade a little recall for orders of magnitude fewer comparisons.

Once a corpus is embedded, the operations you want are neighbour queries: "find the ten chunks most similar to this one" for retrieval-augmented generation, "find near-duplicates" for deduplication, "find visually similar items" for a recommender. Each is a k-nearest-neighbour search in a space of hundreds or thousands of dimensions, over a corpus that may run to billions of vectors. Doing it exactly is easy to write and impossible to scale.

That gap — easy in principle, infeasible at size — is the entire reason vector databases exist. They are not databases of embeddings so much as indexes for approximate nearest-neighbour (ANN) search, plus the ordinary database concerns (durability, filtering, updates) bolted around them. The engineering is one long negotiation with the recall/latency/memory triangle.

Find the right answer by not looking everywhere

Exact search compares against every vector. An ANN index instead builds a structure — a graph, a set of clusters, a compressed code — that lets a query walk toward its neighbours and stop early. You give up the guarantee of finding the true nearest, and in exchange you do a tiny fraction of the comparisons. The whole design question is how much recall to trade for how much speed and memory.

Move the query and tune the beam below. The solid dots are the index's answer; the rings are the true nearest neighbours.

Click to move the query — exact search versus a bounded graph walk

recall

100%

comparisons

31 / 40

distance calcs saved

1.3× fewer

Solid dots are the index's answer; outlined dots are the true top-4. Recall is the overlap. Brute force would visit all 40 points.

The tension is the whole point of a vector database: raising ef (or the graph degree M) lifts recall toward 100% but costs comparisons and memory, and lowering it is faster but can miss a true neighbour. HNSW layers such navigable graphs into a hierarchy so a walk starts coarse and zooms in; IVF and product quantisation make different trades. The graph here is a single flat layer at 2-D — illustrative, not HNSW.

Exact search is O(N·d)

Given NN vectors of dimension dd, brute-force search computes NN distances, each costing O(d)O(d) — so O(Nd)O(Nd) per query. At N=109N = 10^9 and d=768d = 768, that is 7.7×10117.7 \times 10^{11} multiply-adds per query, before counting memory traffic: you must stream the entire index from memory every time. No amount of batching rescues a query that must touch a terabyte of vectors. Exact search is a fine baseline and a fine correctness oracle; it is not a serving strategy.

Recall, latency, memory

ANN indexes are judged by four numbers, and you can only optimise three at a time:

  • Recall@k — the fraction of true top-kk neighbours actually returned.
  • Latency — often reported as queries per second.
  • Memory — the index must fit in RAM, or be sharded, or be quantised.
  • Build/update time — how long it takes to index and keep current.

You raise recall at the cost of latency or memory by widening the search. The graph below makes the trade concrete: move the beam ef up and watch recall climb and comparisons rise. This is the dial every ANN system exposes, under different names (ef_search, nprobe, reorder).

HNSW: navigable small worlds

Hierarchical Navigable Small World graphs are the default in most vector databases. Each vector is a node connected to its MM nearest neighbours, forming a navigable graph; layers are stacked with exponentially fewer nodes in the upper layers, so search starts coarse and descends. A query enters at the top, greedily hops toward closer nodes, then drops a layer and refines.

Two parameters dominate: the graph degree MM (memory and recall) and the search beam ef (latency and recall). HNSW gives excellent recall and fast queries, supports incremental insertion, and is the usual first choice — at the cost of significant memory (the graph edges are stored alongside the vectors) and slower builds.

IVF and quantisation

The other family attacks the memory wall directly.

  • IVF (inverted file) clusters vectors with k-means and searches only the nprobe nearest clusters. This cuts comparisons, not memory.
  • Product quantisation (PQ) compresses each vector into a short code — replacing, say, 768 floats with 96 bytes — at the cost of approximate distances. The FAISS family combines IVF with PQ, and variants like ScaNN reorder candidates to recover recall.

The pattern in practice is a two-stage search: a cheap, compressed or coarse index retrieves a candidate set, then exact distances re-rank the small shortlist. You get most of the accuracy of exact search for a fraction of the cost, which is why every serious system ships a re-ranking stage.

Filtering, freshness, and the database part

Embeddings rarely stand alone. Real queries carry metadata filters ("only documents from this tenant", "only products in stock"), and combining a vector index with an attribute filter is genuinely hard: post-filtering can return too few results, pre-filtering can destroy the graph structure the index relies on. Engines differ (pgvector, for instance, offers HNSW and IVFFlat, with different trade-offs for filtered queries), and it is worth testing on your own filter selectivity rather than trusting a benchmark.

Likewise, embeddings go stale. When the source document changes you must re-embed and re-index just that item; delete-and-renumber is a trap because neighbour lists and ids shift. Treat the index as a derived, rebuildable artifact with a pipeline behind it, not as a system of record.

Careful

Recall is measured against the exact answer, and the exact answer changes if you change the distance metric (cosine versus Euclidean versus dot product) or the normalisation of your vectors. A recall number means nothing unless the metric, the dataset, and the ground truth are pinned. Also: adding a metadata filter after the vector search silently lowers recall, because the index optimised for a different objective than the one your application needs.

Illustrative vs real

The demo runs 40 points in two dimensions with a single-layer navigable graph, so the walk is legible and the distances exact. HNSW is hierarchical, operates in hundreds of dimensions where distances concentrate and intuition breaks, and adds quantisation and filtering. The shape of the recall/cost trade is faithful; the specific numbers are not transferable to any real corpus.

Check yourself

Eduspheria wiki · Systems for AI, Serving at scale

0 / 5 answered

  1. 1An exact search over N = 1,000,000 vectors of dimension d = 512 computes how many scalar multiply-adds per query (in millions)?
    million
    Numeric answer
  2. 2What does raising the HNSW search beam ef do?
    Multiple choice
  3. 3Which method compresses vectors into short codes to cut the memory footprint of an index?
    Short answer
  4. 4Approximate nearest-neighbour search guarantees finding the true nearest neighbour.
    True / false
  5. 5Why is combining a metadata filter with vector search hard?
    Multiple choice

From the exam paper

Modeled on NITJ AI-619, End-Sem June 2025

0 / 5 answered

  1. 1An exact search over N = 4,000,000 vectors of dimension d = 256 computes how many scalar multiply-adds per query, in millions?
    million
    Numeric answer
  2. 2Which on-chip GPU memory acts as a fast scratchpad shared by all threads in a block?
    Multiple choice
  3. 3Which index clusters vectors with k-means and searches only the nprobe nearest clusters?
    Short answer
  4. 4An approximate index returns 90 of the true top-100 neighbours. What is recall@100, in percent?
    %
    Numeric answer
  5. 5Cosine similarity between two vectors changes if you scale one of them by a positive constant.
    True / false

Where next: the last mile — batching, latency and throughput at the serving boundary.