System Design Cases
Vector Similarity & ANN
Vector similarity & ANN concept page. Distance metrics (cosine/dot/euclidean), brute-force kNN O(n) baseline, then ANN families (HNSW/IVF/PQ/LSH/ScaNN/DiskANN/Annoy). 4 scenarios: brute-force slow, HNSW logarithmic descent, IVF-PQ billion-scale, filtering pre/post/filterable HNSW. ADR on HNSW vs IVF-PQ vs DiskANN selection.
Vector search: exact ground truth and measured ANN trade-offs
Approximate nearest-neighbor indexes trade some retrieval fidelity for resource and latency benefits. The curve depends on data, hardware, filters, metric, implementation, build settings, and workload.
Mental model
- HNSW is an approximate graph-search method whose accuracy and efficiency depend on construction and search parameters. Teach a tunable empirical trade-off, not O(log N) or fixed recall as a production guarantee.
- FAISS implements and evaluates exact and approximate similarity-search methods, including compression. Keep exact baselines and distinguish compressed candidate scoring from exact reranking.
- ScaNN reports workload-specific trade-offs from learned quantization and search. Attribute performance to the paper's evaluated setup, never universal hardware claims.
- ANN benchmarks compare recall and query performance across implementations and datasets. Require local representative benchmarks because library rankings can change by workload.
Guarantees and boundaries
- Exact kNN over the eligible corpus defines top-K for the chosen metric and tie policy.
- ANN does not guarantee that the exact nearest neighbors are returned.
- Authorization cannot be traded away for recall or latency.
Diagram scenarios
Exact search establishes ground truth. Linear comparison is expensive at scale but defines the reference set used to measure approximation.
Graph search is tuned empirically. Graph parameters change recall, memory, build cost, and latency; no setting is universal.
Compression with exact reranking. Quantized codes reduce storage but change distance estimates; reranking uses original representations.
Filtering and distribution drift. Post-filtering can yield too few authorized results, while changed data can move the recall curve.
Architecture decision
Maintain an exact-search sample as ground truth. Tune ANN and compression using recall at the requested K together with latency, throughput, memory, build time, and filter slices. Fail closed on tenant filtering and keep raw vectors or another exact representation for reranking when needed.
Failure modes
- Metric or normalization mismatch silently changes rankings.
- Sparse filters can starve a post-filtered candidate set.
- Data drift, deletes, graph maintenance, and shard merge policy can change recall.
Operational checklist
- Benchmark exact and ANN results at the same corpus version and K.
- Measure percentiles under concurrent load, not isolated averages.
- Slice by filter selectivity, tenant size, language, and tail queries.
- Version index build parameters, quantizer, metric, and embedding schema.