Approximate nearest-neighbor indexes

Exact vector search computes similarity between a query and every eligible document vector. It is simple and provides a ground-truth neighbor set, but work grows with corpus size and dimension. Approximate nearest-neighbor, or ANN, indexes trade a controlled amount of neighbor recall for lower latency or memory. They do not change semantic relevance directly; they approximate the candidate set defined by the vector representation. This distinction is essential when diagnosing a miss.

Use exact search as the reference. For a sample of queries, compute the exact top k under the same vectors, metric, and filters. ANN recall at k is the fraction of those exact neighbors recovered. That is an index metric, not relevance recall: an exact nearest neighbor can still be irrelevant. Measure both ANN recall against exact search and retrieval recall against human judgments. If relevance drops after an index change while ANN recall is stable, investigate representation or ranking rather than the ANN algorithm.

HNSW constructs a multilayer proximity graph. Search enters at sparse upper layers, greedily moves toward the query, and explores more candidates in the dense bottom layer. Construction parameter M influences graph degree and memory; efConstruction affects build quality and cost; efSearch controls query-time exploration and the recall-latency trade-off. Deletions, filtered search, and incremental insertions can change graph behavior, so benchmark the intended update pattern, not only a static clean index.

Inverted-file methods cluster vectors into coarse cells. A query probes a subset of cells, reducing comparisons. Product quantization compresses vectors into codes and approximates distances using learned codebooks. Faiss documents and implements combinations such as IVF and product quantization, including GPU search. Key controls include number of clusters, probes, code size, training sample, and whether exact vectors are retained for refinement. Compression saves memory but introduces another approximation layer.

Filtering interacts with ANN. Post-filtering a global top k may return too few authorized or matching items; aggressively increasing k wastes work and may still fail for selective predicates. Pre-filtered per-tenant or per-domain indexes improve correctness at storage and management cost. Filter-aware graph traversal or segmented indexes provide other trade-offs. Always evaluate selectivity slices. Authorization must not rely on fetching unauthorized vectors and merely hiding their text; even identifiers and timing can leak.

Sharding adds distributed approximation. Routing a query to only some shards can lose neighbors. Searching all shards increases fan-out and tail latency. A coordinator must merge comparable scores from consistent vector generations and handle partial failures explicitly. Replicas improve availability but require publication discipline. Report which shards and generation answered; do not silently present partial results as a complete top k.

Capacity planning starts from vectors, index overhead, replicas, and build headroom. A million 768-dimensional float32 vectors require roughly three gigabytes before metadata and index structures. Float16, scalar quantization, or product quantization reduce space with quality trade-offs. HNSW edges can be substantial. Include tombstones, dual generations during migration, cache, and temporary build data. Measure resident memory and page faults, not only serialized index size.

Updates require policy. Frequent incremental inserts may be necessary for freshness but can reduce index balance or fragment storage. Periodic rebuilds create cleaner snapshots but add lag. A common strategy combines a small mutable recent index with a larger immutable base, searches both, then compacts. Deletion and permission revocation may require immediate masking even before physical rebuild. Every query response should identify the index generation and watermark.

Benchmark with realistic concurrency, filters, vector distributions, top k, and hardware. Record p50, p95, and p99 latency, throughput, CPU or GPU utilization, memory, ANN recall, relevance metrics, and failure rate. Warm and cold behavior differ. Run sustained loads long enough to expose memory pressure and compaction. Tune one parameter at a time against a declared service objective.

ANN is a systems optimization, not magic semantic search. Preserve a small exact-search harness for regression tests. It provides the counterfactual needed to say whether the index, embedding, or corpus caused a retrieval failure.