Limitations of graph-based indexes
Graph-based approximate nearest neighbor indexes such as HNSW excel at low-latency, high-recall search in many workloads, but they have clear limitations that can make other index types (e.g. IVF, tree-based) or hybrid approaches more suitable in some cases.
Summary
- Memory: Graph + vectors usually in RAM; scale limits → disk-backed or quantized variants. Updates/deletes: Deletes create orphans; often soft deletes or rebuilds. High dimensions: tuning and resources grow.
- Less predictable recall–latency; pre-filtering during traversal is hard; build cost unless parallelized.
- Disk-oriented alternatives exist (e.g. Disk-ANN, Vamana) for scale beyond RAM; metadata filtering often done via post-filtering.
- Pipeline: graph indexes are optimized for “find nearest by vector”; adding metadata filters or deletes complicates the pipeline and can force trade-offs.
- Trade-off: choose graph indexes for best recall–latency when RAM and update pattern allow; choose IVF or hybrid for very large scale, heavy updates, or simpler filter semantics.
Memory, updates, and dimensionality
Memory: The graph structure and full-precision (or high-precision) vectors are usually kept in RAM for fast traversal. That limits scale on memory-constrained machines and pushes designs toward disk-backed or quantized variants. Updates and deletes: Adding nodes is supported but can degrade graph quality over time; deleting nodes creates “orphans” (dangling links) and often requires soft deletes or periodic rebuilds. High dimensionality: In very high dimensions, distance concentration and the curse of dimensionality can reduce the advantage of graph shortcuts; tuning M and efSearch becomes more critical and resource-heavy.
Pre-filtering and predictability
Pre-filtering by metadata during graph traversal is hard: you must filter neighbors while walking the graph, which can prune branches that would have led to valid results and hurt recall or force over-fetching. Many systems do post-filtering (search without filter, then filter results) or use hybrid approaches (e.g. IVF for filter + HNSW within cells). Recall–latency behavior can also be less predictable than cluster-based methods because graph traversal depends on the local structure; worst-case queries may take more hops or need higher efSearch.
Build cost and disk-oriented alternatives
Build-time cost can be high for very large datasets unless parallelized; each insert does multiple internal searches. For scale beyond RAM, disk-oriented designs (e.g. Disk-ANN, Vamana) layout the graph and vectors for bounded disk reads per query, trading some latency for capacity. So the limitations of “classic” in-memory graph indexes motivate disk-backed variants, IVF, or hybrid systems when scale or cost constraints bite.
Pipeline implications
Graph indexes are optimized for “find nearest by vector.” Adding metadata filters, deletes, or updates complicates the pipeline: deletes need orphan handling or soft-delete flags; filters need in-bitmap checks or post-filtering; updates may require delete + re-insert or special handling. Understanding these implications helps when choosing and tuning a vector index.
Trade-offs and practical tips
Trade-off: graph indexes (HNSW) are a strong default for in-memory, moderate scale, and when deletes/updates are manageable. For billions of vectors, heavy update load, or when pre-filtering is critical, consider IVF, disk-backed graph indexes, or hybrid designs. Practical tip: profile your workload (scale, update rate, filter usage, latency SLA); if any of these push against graph limitations, evaluate IVF or Disk-ANN/Vamana and measure recall and latency on your data.
Frequently Asked Questions
When should I choose IVF over HNSW?
When you need lower memory, very large scale with quantization, or simpler delete/update semantics. IVF can also be easier to combine with pre-filtering.
Can graph indexes support metadata filters?
Yes, but pre-filtering during graph traversal is hard (you must filter neighbors while walking). Many systems do post-filtering or use hybrid approaches.
Do graph indexes work on disk?
With care: layout and access patterns matter. See Disk-ANN and Vamana for disk-oriented designs.
Is HNSW still a good default?
For in-memory, moderate scale, and when deletes/updates are manageable, yes. For billions of vectors or heavy updates, consider IVF or hybrid.