Vector Indexes — Semantic Search, ANN, and When Exact kNN Wins
Semantic search turns text, images, or events into vectors and answers what is closest to the query vector. Exact kNN scans every vector: perfect recall, zero build cost, trivial filters, and cost linear in N. ANN indexes give up a little recall for sub-linear queries. This hub is the decision map across HNSW, IVF, PQ, LSH, ScaNN, and DiskANN, including when brute force is the right answer.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
When would you skip an ANN index?
Answer
Small N, a filter that leaves a few thousand rows, an offline GPU batch, a correctness bar that cannot miss the true neighbor, or churn so high that index maintenance costs more than the scan.
L2
Why do kd-trees fail for 768-dimensional embeddings?
Answer
Pruning needs a region that cannot contain a closer point. In high dimensions distances concentrate, so almost every leaf is visited. Graphs and IVF use the clustered structure of real embeddings instead.
L3
What does recall at 10 equal to 0.95 mean?
Answer
On average 9.5 of the true top 10 neighbors appear in the returned 10. A re-ranker over a wider list forgives misses. A dedup check does not. Pair the mean with the share of queries under 0.8.
L4
Cosine, dot product, or L2?
Answer
Use the metric the embedding model was trained for. Normalized vectors make cosine and dot product rank the same, and L2 is monotonic with both. Unnormalized inner product is not a metric.
L5
HNSW or IVF-PQ, in one sentence each?
Answer
HNSW has the best recall-latency curve when vectors plus the graph fit in RAM and inserts are incremental. IVF-PQ wins on bytes at hundreds of millions to billions of vectors, if you re-rank with full vectors.
L6
How do you choose for 50 million vectors, 768 dimensions, 64 GB nodes?
Answer
fp32 is about 154 GB before the graph, so plain HNSW needs several nodes per replica. int8 HNSW, binary quantization with re-score, or IVF-PQ on one node are the real options. Sweep recall and p99.
L7
What is a vector index, and what is a vector database?
Answer
The index is the structure: HNSW, IVF, PQ. The database adds durability, replication, filters, updates, tenancy, and an API. Elasticsearch, OpenSearch, and Postgres with pgvector are common homes for that index.
Failure modes
HNSW larger than RAM
Page faults, a blown p99, or an OOM kill. Quantize, shard, or move to IVF-PQ or DiskANN.
IVF trained on last year's data
Lists skew, a few cells hold most vectors, and recall drops with no code change. Retrain centroids and watch list-size skew.
PQ with no re-rank
Recall sticks around 0.4 to 0.7 no matter how wide nprobe is. Re-rank the top 100 to 1000 with full vectors.
LSH on dense text embeddings
Dozens of tables, then the scan is almost brute force. Prefer a graph or IVF.
HNSW plus a very selective filter
Short result lists or a huge walk. Fall back to an exact scan under a cardinality threshold.
ANN with no recall oracle
Search got worse, and nobody can prove it. Keep exact ground truth on a frozen query set.
Misconceptions
ANN is always faster than a scan.
Under a few hundred thousand vectors, or after a selective filter, a SIMD or GPU scan is a few milliseconds and recall is 1.0.
A kd-tree is the index for embeddings.
Distances concentrate, so almost no box can be pruned. The tree becomes a slow linear scan.
Plain LSH is the default for dense text embeddings.
High recall needs many tables, and then you scan most of the corpus. Graphs and IVF fit this data better.
Interviewer traps
Rebuilding analyzers, BM25, or chunk size when the question is the index.
Name the lexical series and the embeddings page, then stay on exact versus ANN, the families, and the recall budget.
Picking HNSW because it is the popular default.
Do the bytes-per-query math first. If vectors plus the graph do not fit, quantize, shard, or switch families.
Design scenario
Same prompt for every reader.
Requirements
Interactive search, recall at 10 at least 0.95, and a plan for tenant filters. Exact search stays available as the recall oracle.
Traffic / scale
50 million vectors, dimension 768, online queries plus a steady update stream.
Latency
p99 stays inside an interactive budget after a measured sweep, not after a blog default.
Consistency
One embedding model id per index. A query from a different model is refused.
Availability
One replica holds another full copy. Losing one node does not drop the index.
Failure assumptions
- fp32 vectors plus an HNSW graph do not fit on one 64 GB node.
- A selective tenant filter can make ANN the wrong plan.
- Centroids or the graph go stale as the corpus drifts.
Constraints
- State the memory before the algorithm.
- Do not quote an efSearch default you have not measured.
Prompt
Choose an index for 50 million vectors of dimension 768 on 64 GB nodes.
API
What does the client send, and when do you refuse a query from a different model id?
Data
Where do full vectors, codes, and graph links live?
Architecture
How many nodes per replica, and which family if RAM is the constraint?
When the scan is the index
Prefer
Exact kNN while N or the filter is small
Score every surviving vector. Recall is 1.0, there is nothing to build, and any predicate is just a branch in the loop.
- Under roughly 100k to a few hundred thousand vectors, a SIMD or GPU scan is a few milliseconds.
- A tenant or ACL filter that leaves about 2,000 rows is cheaper exact than any graph walk.
- Batch jobs and the recall oracle are the same scan, often as a matrix multiply.
Alternative
ANN once the scan misses the budget
Graphs, partitions, and codes visit a candidate set. You pay build time, RAM, and a recall target.
- HNSW when full vectors plus links fit in RAM.
- IVF-PQ or ScaNN when they do not, with a full-vector re-rank.
- DiskANN-style graphs when SSD latency is acceptable and RAM is not.
From text to a top-k
Steps 1 to 3 are the embedding problem. Steps 4 to 6 are this series. Step 7 is where vectors meet lexical search and product rules.
- 1
Embed the query
Text, an image, or an event becomes a vector, often 384 to 3072 dimensions. The model and the chunking live on the embeddings lesson. - 2
Choose exact or ANN
Exact scores all N vectors. ANN visits a small candidate set. A re-rank with full vectors is optional and, for PQ, usually mandatory. - 3
Filter, fuse, and ship
Metadata predicates, a BM25 leg, and a cross-encoder sit on top. A selective filter can make the flat scan the right plan again.
Overview
Semantic search turns text, images, or events into vectors and answers which stored vectors are closest to the query. Exact kNN (a flat index) scans every vector. Approximate nearest neighbor search gives up a little recall so the query is sub-linear.
This series sits next to the lexical search cluster. It does not repeat inverted indexes or BM25 internals. Those live on Inverted Index, Analyzers, Tokenization & Mappings and Query DSL, Relevance Scoring (TF-IDF/BM25) & Filters vs Queries. It does not repeat how embeddings are trained or how you chunk. That is Embeddings & Similarity — Dense Vectors, Metrics & Chunking Basics.
The RAG series already has a one-page survey, Vector Indexes — HNSW, IVF & Product Quantization Tradeoffs. Leave that page where it is. This cluster is the deeper, interview-grade version of the same decision.
Decisions
- 1
1. Text or image
- next2. Embedding model
- 2
2. Embedding model
- next3. Query vector
- 3
3. Query vector
- next4. Index type
- ?
4. Index type
- exact5a. Scan all N vectors
- ANN5b. Small candidate set
- 5
5a. Scan all N vectors
- next6. Top-k by similarity
- 6
5b. Small candidate set
- next6b. Optional re-rank
- 7
6. Top-k by similarity
- next7. Filter, fuse, re-rank
- 8
6b. Optional re-rank
- next6. Top-k by similarity
- 9
7. Filter, fuse, re-rank
Lesson map
Vector Indexes — Semantic Search, ANN, and When Exact kNN Wins
Semantic search turns text, images, or events into vectors and answers what is closest to the query vector. Exact kNN scans every vector: perfect recall, zero build cost, trivial filters, and cost linear in N. ANN indexes give up a little recall for sub-linear queries. This hub is the decision map across HNSW, IVF, PQ, LSH, ScaNN, and DiskANN, including when brute force is the right answer.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB text["1. Text or image"] model["2. Embedding model"] qv["3. Query vector"] kind["4. Index type"] text -->|1. Text or image to 2. Embedding model| model model -->|2. Embedding model| qv qv -->|3. Query vector to 4. Index type| kind
Exact kNN versus ANN
| Property | Exact kNN (flat) | ANN index |
|---|---|---|
| Recall | 1.0 by definition | Tunable, typically 0.9 to 0.99 |
| Query cost | O(N times d) per query | Roughly O(log N) hops on graphs, or O(N times nprobe / nlist) for IVF |
| Build cost | None | Minutes to hours for a graph build or k-means |
| Extra memory | None | Graph links, centroids, codebooks |
| Filters | Scan only the matching rows | Filters fight the index structure |
| Updates and deletes | Trivial | Graph repair, tombstones, rebuilds |
| Determinism | Fully deterministic | Depends on build order and parameters |
When exact wins
- Small N. Under roughly 100k to a few hundred thousand vectors, a SIMD or GPU scan is a few milliseconds. No index, no tuning, recall 1.0.
- Highly selective filters. If a tenant or ACL filter leaves 2,000 candidates, scanning those 2,000 is cheaper and exact. Lucene, Qdrant, and others switch to exact search below a threshold.
- Ground truth. Every ANN evaluation needs exact results on a held-out query set. Flat search is the recall oracle.
- Batch and offline jobs. Dedup, clustering, and nightly recommendations can batch queries into matrix multiplies where brute force is extremely efficient.
- Strict correctness. Legal, fraud, or safety lookups where missing the nearest match is unacceptable.
When the scan gets too slow
A brute-force scan is memory-bandwidth bound. Bytes read per query equal N times d times bytes per dimension. At about 20 GB/s per socket:
| N | d | fp32 bytes | Scan time fp32 | Scan time int8 |
|---|---|---|---|---|
| 50k | 768 | 154 MB | about 8 ms | about 2 ms |
| 200k | 768 | 614 MB | about 31 ms | about 8 ms |
| 1M | 768 | 3.1 GB | about 154 ms | about 38 ms |
| 100M | 768 | 307 GB | seconds, and it does not fit in RAM | still seconds |
Why not a tree?
kd-trees, ball trees, and R-trees prune by proving that nothing in a box can be closer than what you already have. In high dimensions, distances concentrate: the farthest point is barely farther than the nearest, so almost no box can be pruned and the tree degrades into a slow linear scan. The Python sandbox prints the farthest-to-nearest ratio collapsing from about 36 times at dimension 2 to about 1.2 times at dimension 512.
Real embeddings are not uniform. They live near lower-dimensional manifolds and clusters, which is the structure graphs and IVF exploit. Low-dimensional geospatial kNN is a different lesson: R-Trees & R-star — MBRs, Bulk Load & Range/KNN Queries.
The ANN families
| Family | Core idea | Query knobs | Memory | Build | Strengths | Weak spots |
|---|---|---|---|---|---|---|
| Brute force (flat) | Score everything | none | vectors only | none | Exact, filter-friendly | O(N) per query |
| HNSW | Multi-layer proximity graph, greedy plus beam search | efSearch | vectors plus graph, about M times 2 times 4 bytes per vector at layer 0 | Slow-ish, O(N log N) | Best recall-latency curve in RAM, incremental inserts | RAM hungry, deletes and filters hurt |
| IVF-Flat | k-means cells, scan nprobe closest cells | nprobe | vectors plus centroids | k-means training | Simple, cheap build, GPU friendly | Boundary misses, needs retraining on drift |
| IVF-PQ | IVF cells plus product-quantized codes | nprobe, re-rank depth | codes, 8 to 64 bytes per vector | k-means plus PQ training | Billion-scale in RAM | Lower recall without re-rank |
| LSH | Random hash functions, collisions are candidates | tables, bits | hash tables | Fast | Theory guarantees, streaming | Needs many tables for high recall on dense embeddings |
| ScaNN | Partition plus anisotropic quantization plus exact re-score | leaves to search, re-order depth | compressed | Training | Excellent recall per CPU for inner product | Fewer integrations, tuning |
| DiskANN / Vamana | Graph on SSD, PQ in RAM | search list size | small RAM, large SSD | Heavy | Billion-scale on one box | SSD latency, complex ops |
Elasticsearch, OpenSearch, Lucene, Qdrant, Weaviate, Milvus, and pgvector all ship HNSW. Faiss ships flat, IVF, PQ, HNSW, and combinations. Milvus and pgvector also ship IVF. ScaNN powers Vertex AI Vector Search. DiskANN appears in Azure and in several vector databases. The lexical cluster owns when the product is a search engine at all: Elasticsearch & OpenSearch — Inverted Indexes, Relevance & Ops and Ecosystem — OpenSearch vs Elasticsearch vs Solr (and when not to use a search engine). Retrieval as a whole, including grounding, stays on RAG & Vector Databases — Retrieval, Embeddings & Grounding.
Choosing an index
Decisions
- 1
1. N, d, QPS, RAM, filters
- next2. N small or filter tiny?
- ?
2. N small or filter tiny?
- yesFlat exact scan
- no3. Vectors plus graph fit?
- 3
Flat exact scan
- next6. Measure recall and p99
- ?
3. Vectors plus graph fit?
- yesHNSW, tune efSearch
- no4. Fits after int8 or bits?
- 5
HNSW, tune efSearch
- next6. Measure recall and p99
- ?
4. Fits after int8 or bits?
- yesHNSW plus SQ or BQ
- no5. SSD serving ok?
- 7
HNSW plus SQ or BQ
- next6. Measure recall and p99
- ?
5. SSD serving ok?
- yesDiskANN-style graph
- noIVF-PQ or ScaNN
- 9
DiskANN-style graph
- next6. Measure recall and p99
- 10
IVF-PQ or ScaNN
- next6. Measure recall and p99
- 11
6. Measure recall and p99
Decisions
- 1
1. N, d, QPS, RAM, filters
- next2. N small or filter tiny?
- ?
2. N small or filter tiny?
- yesExact kNN
- noANN family
- 3
Exact kNN
- nextMeasure recall and p99
- 4
ANN family
- nextMeasure recall and p99
- 5
Measure recall and p99
Flow
- 1
HNSW, tune efSearch, if RAM fits
- elseQuantized HNSW if int8 or bits fit
- 2
Quantized HNSW if int8 or bits fit
- elseDiskANN-style graph if SSD is ok
- 3
DiskANN-style graph if SSD is ok
- elseIVF-PQ or ScaNN otherwise
- 4
IVF-PQ or ScaNN otherwise
Start from N, dimension, QPS, the p99 budget, the RAM budget, and how selective the filters are. If N is under about 200k, or the filtered set is tiny, stay flat. If full vectors plus the graph fit in RAM, use HNSW and tune efSearch. If they fit after int8 or binary quantization, keep HNSW and re-score. If SSD serving is acceptable, a DiskANN-style graph is the next step. Otherwise IVF-PQ or ScaNN, and re-rank the top candidates. Every branch ends at the same measurement: recall at k and p99 on real queries.
What happens if you pick the wrong index
| Wrong choice | Symptom in production | Fix |
|---|---|---|
| HNSW on a corpus that does not fit in RAM | Page faults, p99 explodes, OOM kills | Quantize, shard, or move to IVF-PQ or DiskANN |
| IVF trained on last year's data | Lists skew, a few lists hold most vectors, recall silently drops | Retrain centroids, monitor list-size skew |
| PQ with no re-rank | Recall stuck around 0.4 to 0.7 no matter how you tune nprobe | Re-rank the top 100 to 1000 with full vectors |
| LSH on dense text embeddings | Needs dozens of tables, memory and scans balloon | Use a graph or IVF |
| HNSW plus a very selective filter | Empty or short result lists, or huge latency | Pre-filter to an exact scan below a threshold, or use a filter-aware walk |
| ANN for a tiny tenant | Paying for index RAM and getting recall below 1.0 for nothing | Flat scan per tenant |
| Any ANN with no recall measurement | Search got worse, with no data | Exact ground truth on a fixed query set, alert on drift |
What this cluster covers
- HNSW — Layers, Greedy Search, M and ef — levels, greedy descent, the layer-0 beam, M, efConstruction, efSearch.
- IVF, PQ, and ScaNN — Partition, Quantize, Re-rank — nlist, nprobe, codes, ADC, and the re-rank.
- Filtered and Hybrid Search — Metadata, BM25, and Broken Recall — selectivity, and fusing BM25 without letting one score scale win.
- Recall, Latency, and Memory — Tuning and Evaluation — the harness, tail recall, and the capacity math.
- Sharding, Updates, and Stale Embeddings — Production Vector Search — fan-out, tombstones, and model upgrades.
Sandbox: exact kNN versus LSH
Exact kNN touches every vector. Random-hyperplane LSH only scores vectors that collide with the query, so recall depends on bits per table and the number of tables. The same run prints distance concentration on uniform points.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Seeded reading: one table of 12 bits scans about 0.1 percent of the corpus and recall at 10 is about 0.003. Sixteen tables of 4 bits reach about 0.93 recall and scan about 64 percent. Thirty-two tables of 4 bits reach 1.0 and scan about 85 percent. The farthest-to-nearest L2 ratio falls from about 36 at dimension 2 to about 1.16 at dimension 512. LSH can be extremely cheap and useless. Reaching high recall on dense embeddings scans most of the corpus, which is why production systems prefer graphs or IVF.
Sandbox: bounded heap and the cost model
Exact search keeps a bounded heap of the best k so each new candidate is O(log k), not a full sort. The same snippet prices a bandwidth-bound scan and shows a tenant filter that scores about 1 percent of the vectors.
Press Run. Snippets must be self-contained — no network, files, or native modules.
The cost model, which does not depend on the machine, says 50k by 768 fp32 is about 7.7 ms (exact is fine), 200k is about 30.7 ms fp32 and 7.7 ms int8 (exact only if quantized or batched), and 1 million and above needs ANN at a 20 ms budget. Wall-clock timings of the 20k by 384 scan move with the machine. The best id on this seed is the query row itself, 123, because the query is a stored vector.
Interview Q&A
When would you not use an ANN index?
Answer
Small corpora, under a few hundred thousand vectors. A filter that shrinks the candidate set to a few thousand. Offline batch jobs on a GPU. Lookups where missing the true nearest neighbor is unacceptable. Data that changes so fast that index maintenance costs more than scanning.
Why do kd-trees fail for 768-dimensional embeddings?
Answer
Pruning depends on proving a region cannot contain a closer point. In high dimensions distances concentrate, so lower bounds are rarely tight enough to prune, and the tree visits almost every leaf. Graphs and IVF exploit the clustered, low-intrinsic-dimension structure of real embeddings.
What does recall at 10 equal to 0.95 mean, and is it good?
Answer
On average 9.5 of the true top 10 neighbors appear in the returned 10. A re-ranker over the top 50 forgives misses. A dedup check does not. Always pair mean recall with tail recall, the share of queries under 0.8.
Cosine, dot product, or L2?
Answer
Use what the embedding model was trained for. If vectors are normalized, cosine and dot product rank identically and L2 is monotonic with both. Unnormalized dot product, maximum inner product search, is not a metric. That matters for some index types. ScaNN and Faiss have specific handling.
HNSW versus IVF-PQ in one sentence each?
Answer
HNSW gives the best recall-latency tradeoff when vectors plus the graph fit in RAM and you need incremental inserts. IVF-PQ gives the best recall per byte at hundreds of millions to billions of vectors, as long as you re-rank with full vectors.
How do you choose for 50 million vectors, 768 dimensions, 64 GB RAM nodes?
Answer
fp32 is about 154 GB before the graph, so plain HNSW needs about 4 to 6 nodes per replica. Options: int8 HNSW (about 38 GB of vectors plus about 7 GB of graph at M = 16, about 2 nodes), binary quantization with re-score, or IVF-PQ for a single node. Decide by the recall target and p99 after a measured sweep.
What is the difference between a vector database and a vector index?
Answer
The index is the data structure: HNSW, IVF. The database adds storage, durability, replication, metadata filtering, updates and deletes, multi-tenancy, and APIs. Many teams use Elasticsearch, OpenSearch, or Postgres with pgvector as that database.
A PM asks why semantic search misses exact product codes. What do you say?
Answer
Embeddings capture meaning, not rare exact tokens. Add lexical BM25 and fuse the lists, or route code-like queries to keyword search. That mechanics page is Filtered and Hybrid Search — Metadata, BM25, and Broken Recall.
Pitfalls
Write fp32 bytes, int8 bytes, and a rough HNSW link budget for 50 million vectors of dimension 768. Mark which option fits a 64 GB node. Then say which filter selectivity would throw the plan back to a flat scan.