Why HNSW is not the answer and disk-based alternatives might be more practical

SIMD-accelerated search over binary vectors is very fast and you can fit a lot in memory. Then rerank over f32 from disk.<p>I tried a few alternatives and found that SQLite + usearch extension wins for my use cases (&lt; 1 million records), as measured by latency and simplicity. I believe this approach can scale up to hundreds of millions of records.

IVF, unfortunately, is barely compatible with filtered search. It have to rely on post-filtering and retrieve more and more candidates if the result set is not big enough. If the query is in some form correlated with the filter, this approach quickly degrades to brute-force.<p>Surprised that the article doesn&#x27;t mention filtering use-case at all.

&gt; For example, the typical distance computation complexity between two D-dimensional vectors is O(D^2), but compressing floats into bits reduces this by a factor of 1024 (32x32).<p>This isn&#x27;t right, cosine distance between two vectors is definitely O(D)…<p>Of course replacing float multiplications with xor+popcount is a nice speedup in computation, but assuming you&#x27;re memory bandwidth limited, speedup should be linear.

Quantization can be applied exactly in the same way in HNSW. I&#x27;m using quantization in the implementation of Redis vector sets and it works very well. I have very big issues with the other points as well, but I prefer to reply to these concerns with the implementation I hope to have into Redis in a short time (early 2025).<p>About insertion &#x2F; deletion cost. Sure, they are costly, but if instead of grabbing one of the available implementations you start from scratch, extend the paper in sensible ways, and experiment with it, I think it is possible to do much better than one could initially believe.

I&#x27;ve been doing vector search since 2002 or so and it&#x27;s amazing how far you can get keeping vectors in RAM and using primitive search algorithms, enough that I&#x27;m afraid the market for vector databases is 1% of what VC&#x27;s think it is. (e.g. full scan was good enough for a search engine of international patents and non-patent literature)

The problem with IVF is that you need to find the right centroids. And that doesn&#x27;t work well if your data grow and mutate over time.<p>Splitting a centroid is a pretty complex issue.<p>As are clustering in an area. For example, let&#x27;s assume that you hold StackOverflow questions &amp; answers. Now you have a massive amount of additional data (&gt; 25% of the existing dataset) that talks about Rust.<p>You either need to re-calculate the centroids globally, or find a good way to split.<p>The posting list are easy to use, but if you are unbalanced, it gets really bad.

Nit: the drawback of “not working well in disk based systems” isn’t a drawback unless you’re already using disk based systems.<p>The difference in recall is also significant — what you really get with HNSW is a system made to give good cost:approximation quality. These IVFPQ based systems are ones I’ve seen people rip and replace if the use case is high value.<p>I really don’t understand the push to make pg do everything. It wasn’t designed for search, and trying to shove these features into the platform feels like some misguided cost optimization that puts all of your data infrastructure on the same critical path.

HNSW became the defacto default specifically because you don’t need to precalculate the index and it updates as writes come in.<p>This is a great article, and all the points are there, but the truth is that most teams running million scale vectors don’t want the operational complexity of quantizing offline in some frequency. They’ll gladly outsource the costs to paying for RAM instead of some IVFPQ calculation.<p>However if there were a solution that “just worked” to handle PQ for shards in near real time for updates that also had sane filtering, that would be really nice.

Highly recommend to prompt the following in LLM if you are trying to grasp Hybrid(Keyword, Filter + Vector) search or HNSW vs IVF flavour topics<p>Graph-Based (HNSW) vs Cluster-Based (IVF)<p>Memory Usage: Higher for HNSW due to graph storage requirements vs Lowerfor IVF; stores cluster centroids and subsets of vectors<p>Accuracy: High recall and precision, close to exact search vs Recall depends on the number of clusters and visited partitions<p>Build Time: Slower for HNSW, Faster for IVF<p>Best for: Real-time, high-accuracy tasks requiring dynamic updates vs Large, static datasets with strict memory constraints<p>Notable Graph-Based (HNSW) Variants - Faiss HNSW or PANNG (Proximity and Navigable Neighbor Graph)<p>Cluster-Based (IVF) Variants - IVF-PQ for memory-constrained environments, Multi-Index IVF partitions, IVF-GPU

HNSW can be used for large indexes when combined with an effective caching strategy. Aerospike uses a distributed cache with query steering approach which allows you to have many indexes, including large ones and load them into memory as your application needs them.

&quot;Its reliance on frequent random access patterns makes it incompatible with the sequential access nature of disk storage.&quot;<p>Is this true for SSD storage, or does it only apply to spinning metal platters?

What about DiskANN? <a href="https:&#x2F;&#x2F;milvus.io&#x2F;docs&#x2F;disk_index.md" rel="nofollow">https:&#x2F;&#x2F;milvus.io&#x2F;docs&#x2F;disk_index.md</a>

Yep, I believe it<p>HNSW has been great for relatively small datasets (a website with 30K pages), but it’s a dangerous stretch for anything bigger

&gt; Its reliance on frequent random access patterns makes it incompatible with the sequential access nature of disk storage.<p>So use SSD? Are people seriously still trying to use spinning disk for database workloads in 2024?