7 ms·
Why HNSW is not the answer and disk-based alternatives might be more practical
- rekoros 2y agoYep, I believe it HNSW has been great for relatively small datasets (a website with 30K pages), but it’s a dangerous stretch for anything bigger
- aabhay 2y agoWhat systems would you recommend for larger deployments?
- rekoros 2y agoI ended up breaking up/sharding HNSW across multiple tables, but I'm dealing with many distinct datasets, each one just small enough to make HNSW effective in terms of index build/rebuild performance. The article suggests IVF for larger datasets - this is the direction I'd certainly explore, but I've not personally had to deal with it. HNSW sharding/partitioning might actually work even for a very large - sharded/partitioned - dataset, where each query is a parallelized map/reduce operation.
- nostrebored 2y agoWhat are you using for HNSW? Is the implementation handwritten? I’ve seen people using it well over XXm at full precision vectors with real time updates
- rekoros 2y agopgvector - I wasn't able to get HNSW to build/rebuild quickly [enough] with a few million vectors. Very possibly I was doing something wrong, but fun research time ran out and I needed to get back to building features.
- VoVAllen 2y agoHi, I'm the author of the article. Please check out our vector search extension in postgres, VectorChord [1]. It's based on RabitQ (a new quantization method) + IVF. It achieves 10ms-level latency for top-10 searches on a 100M dataset and 100ms-level latency when using SSD with limited memory. [1] https://blog.pgvecto.rs/vectorchord-store-400k-vectors-for-1-in-postgresql https://blog.pgvecto.rs/vectorchord-store-400k-vectors-for-1...
- redskyluan 2y agowhy not try milvus? you get multiple index types, SIMD based brute force search, IVF, HNSW and DiskANN and you never bother to scale
- bluecoconut 2y agoI don’t quite understand this - by 30k pages, is this the number of entries in your index? Did you mean 30M? At the <100k scale I just full compute / inner product directly, and I don’t mess with vector stores or added complexity. No ANN algo needed — they’ll all be slower than actual exact kNN re ranking. (10k7684 =30MB, a scan over it and a sort is on the ~100us or faster). frankly, I’ve even sent at the 5k scale to client and done that client side in JS. Often, I find i use an ANN algo / index to get me my nearest 10k then I do final re ranking with more expensive algorithms/compute in that reduced space. The original HNSW paper was testing/benchmarking at the 5M-15M scales. That’s where it shines compared to alternatives. When pushing to the 1B scale (I have an instance at 200M) the memory consumption does become a frustration (100GB of ram usage). Needing to vertically scale nodes that use the index. But it’s still very fast and good. I wouldn’t call it “dangerous” just “expensive”. Interestingly though, I found that usearch package worked great and let me split and offload indexes into separate files on disk, greatly lowered ram usage and latency is still quite good on average, but has some spikes (eg. sometimes when doing nearest 10k though can be ~1-3 seconds on the 200M dataset)
- VoVAllen 2y agoHi, I'm the author of the article. Please check out our vector search extension in postgres, VectorChord [1]. It's based on RabitQ (a new quantization method) + IVF. It achieves 10ms-level latency for top-10 searches on a 100M dataset and 100ms-level latency when using SSD with limited memory. [1] https://blog.pgvecto.rs/vectorchord-store-400k-vectors-for-1-in-postgresql https://blog.pgvecto.rs/vectorchord-store-400k-vectors-for-1...
- rekoros 2y agoYou're dealing with much larger datasets than I have, so far - mine is only a few million vectors. I have a hard constraint on resources, so had to get things working quickly in a relatively gutless environment.
- PaulHoule 2y agoI've been doing vector search since 2002 or so and it's amazing how far you can get keeping vectors in RAM and using primitive search algorithms, enough that I'm afraid the market for vector databases is 1% of what VC's think it is. (e.g. full scan was good enough for a search engine of international patents and non-patent literature)
- zackangelo 2y agoThis is so true. A plain old exhaustive SIMD-optimized similarity search will do just fine in many cases and not have any of the approximation tradeoffs of HNSW.
- PhilippGille 2y agoIn chromem-go [1] I'm searching through 100,000 vectors in 40ms on a mid-range laptop CPU, even without SIMD. It's quick enough for many use cases. [1] https://github.com/philippgille/chromem-go https://github.com/philippgille/chromem-go
- PaulHoule 2y agoIt would be very hard to find a problem that has better mechanical sympathy than full-scan similarity search. Even if the operation count of some other algorithm was 1/10 on paper it might not be faster if the prefetcher and branch predictor aren't running at their best. People who want to start with RAG should not start with a vector search engine but instead download https://sbert.net/ https://sbert.net/ and start messing around w/ Jupyter notebooks and maybe FAISS. People who think I'm going to upload vectors to an expensive cloud service over a slow ADSL connection are delusional.
- rockwotj 2y agoSwap out FAISS with usearch, you get all the awesome SIMD acceleration (via dynamic dispatch), optional compression. Not affiliated but really cool tech. https://github.com/unum-cloud/usearch https://github.com/unum-cloud/usearch
- binarymax 2y agoHNSW became the defacto default specifically because you don’t need to precalculate the index and it updates as writes come in. 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. 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.
- nostrebored 2y agoYes, real time updates, filtering, and multi vector support make most of these on device, in memory approaches untenable. If you really are just doing a similarity search against a fixed set of things, often you know the queries ahead of time and can just make a lookup table.
- bddicken 2y agoAt PlanetScale, we have a really nice solution for this in MySQL using SPANN + SPFresh. The way we've implemented it allows for pre and post filtering, full compatibility with where clause filtering, and has the same kind of acid compliance you'd expect from a relational database. You can read about it here: https://planetscale.com/blog/announcing-planetscale-vectors-public-beta https://planetscale.com/blog/announcing-planetscale-vectors-...
- VoVAllen 2y agoHi, I'm the author of the article. In our product, VectorChord, we use a quantization algorithm called RaBitQ, which doesn’t require a separate codebook. Unlike IVFPQ, it avoids the need to maintain and update the corresponding codebook, so the update issue you mentioned is not a problem. Regarding filtering, I’m not sure which specific scenario you’re referring to, but we currently support iterative post-filtering and are technically capable of perfectly supporting pre-filtering as well.
- binarymax 2y agoPre and post filtering are both not great. Some HNSW implementations in products like Vespa and Qdrant have filter-during-search. This remains an unsolved problem in cluster-based indices.
- generall 2y agoIVF, 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. Surprised that the article doesn't mention filtering use-case at all.
- VoVAllen 2y agoHi, I'm the author of the article. I actually think the opposite of what you mentioned. IVF is more suitable for prefiltering compared to HNSW. For prefiltering in HNSW, there is a certain requirement for the filtering rate—it can't be too low, or the entire graph may become disconnected. For instance, with the commonly used parameter m=16, each node can have at most 16 neighbors. If the filtering rate is below 5%, it can directly result in no neighbors meeting the condition, causing the algorithm to fail entirely. This is why the academic community has proposed alternatives like ACRON[1]. On the other hand, IVF doesn't have this problem at all—you can check whether a candidate meets the condition before calculating distances. [1] https://arxiv.org/abs/2403.04871 https://arxiv.org/abs/2403.04871
- generall 2y agoIn IVF you can start checking conditions only in the final bucket. There are no guarantees if the bucket has any acceptable value, and there are no procedures to find the bucket which has acceptable values before scanning it.
- VoVAllen 2y agoI'm not sure I fully understand your point. This can be implemented quite easily by organizing each posting list with specific attributes to locate the values efficiently. For example, you could build each posting list into a B-tree, or similar to a column-oriented format that stores attribute statistics to enable skip scanning. Could you elaborate more?
- 2y ago
- intalentive 2y agoSIMD-accelerated search over binary vectors is very fast and you can fit a lot in memory. Then rerank over f32 from disk. I tried a few alternatives and found that SQLite + usearch extension wins for my use cases (< 1 million records), as measured by latency and simplicity. I believe this approach can scale up to hundreds of millions of records.
- wild_egg 2y agoI've been using DuckDB similarly and loving the simplicity. What sort of latency are you seeing with your setup? I'm hitting 300ms to query against 10M vectors and could see that becoming a bottleneck if going into the hundreds of millions.
- VoVAllen 2y agoHi, I'm the author of the article. Please check out our vector search extension in postgres, VectorChord [1]. It achieves 10ms-level latency for top-10 searches on a 100M dataset and 60ms-level latency when using SSD with limited memory. [1] https://blog.pgvecto.rs/vectorchord-store-400k-vectors-for-1-in-postgresql https://blog.pgvecto.rs/vectorchord-store-400k-vectors-for-1...
- wild_egg 2y agoLook like very nice tech but unfortunately the operational overhead of postgres is too high for my use case. Will keep it in mind for future postgres-backed projects though
- ashvardanian 2y agoDuckDB also uses USearch and the underlying SimSIMD library for kernels, but both were originally designed for a Billion+ scale. Depending on how the wrapper is implemented you can get different numbers. With the raw libraries, on larger machines, I'd expect 200'000 requests per second for 1 Billion entries.
- tveita 2y ago> 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). This isn't right, cosine distance between two vectors is definitely O(D)… Of course replacing float multiplications with xor+popcount is a nice speedup in computation, but assuming you're memory bandwidth limited, speedup should be linear.
- DoctorOetker 2y agoSome snippets: > Leverages concentration of measure phenomena > Uses anisotropic vector quantization to optimize inner product accuracy by penalizing errors in directions that impact high inner products, achieving superior recall and speed. I only skimmed the article, but the 2 words I emphasized seems to imply they apply a quadratic metric for distance, i.e. they assume the data coordinates are with respect to non-orthogonal basis vectors, resulting in off-diagonal distance metric terms.
- VoVAllen 2y agoHi, I'm the author of the article. We actually rely on a new quantization method called RaBitQ instead of ScaNN. You can read more about it at https://dev.to/gaoj0017/quantization-in-the-counterintuitive-high-dimensional-space-4feg https://dev.to/gaoj0017/quantization-in-the-counterintuitive....
- VoVAllen 2y agoHi, I'm the author of the article. I think you're right, and we’ll update the description in the blog. Since binary operations are simpler than floating-point operations, the speedup could indeed be greater than 32x.
- ayende 2y agoThe problem with IVF is that you need to find the right centroids. And that doesn't work well if your data grow and mutate over time. Splitting a centroid is a pretty complex issue. As are clustering in an area. For example, let's assume that you hold StackOverflow questions & answers. Now you have a massive amount of additional data (> 25% of the existing dataset) that talks about Rust. You either need to re-calculate the centroids globally, or find a good way to split. The posting list are easy to use, but if you are unbalanced, it gets really bad.
- VoVAllen 2y agoHi, I'm the author of the article. Meta have conducted some experiments on dynamic IVF with datasets of several hundred million records. The conclusion was that recall can be maintained through simple repartitioning and rebalancing strategies. You can find more details here: DEDRIFT: Robust Similarity Search under Content Drift https://arxiv.org/pdf/2308.02752 https://arxiv.org/pdf/2308.02752. Additionally, with the help of GPUs, KMeans can be computed quickly, making the cost of rebuilding the entire index acceptable in many cases.
- nostrebored 2y agoNit: the drawback of “not working well in disk based systems” isn’t a drawback unless you’re already using disk based systems. 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. 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.
- VoVAllen 2y agoHi, I'm the author of the article. In our actual product, VectorChord, we adopted a new quantization algorithm called RaBitQ. The accuracy has not been compromised by the quantization process. We’ve provided recall-QPS comparison curves against HNSW, which you can find in our blog: https://blog.pgvecto.rs/vectorchord-store-400k-vectors-for-1-in-postgresql https://blog.pgvecto.rs/vectorchord-store-400k-vectors-for-1.... Many users choose PostgreSQL because they want to query their data across multiple dimensions, including leveraging time indexes, inverted indexes, geographic indexes, and more, while also being able to reuse their existing operational experiences. From my perspective, vector search in PostgreSQL does not have any disadvantages compared to specialized vector databases so fat.
- nostrebored 2y agoBut why are you benchmarking against pgvector HNSW, which is known to struggle with recall and performance at large numbers of vectors? Why is the graph measuring precision and not recall? The feature dump is entirely a subset of Vespa features. This is just an odd benchmark. I can tell you in the wild, for revenue attached use cases, I saw _zero_ companies choose pg for embedding retrieval.
- tw04 2y ago> Its reliance on frequent random access patterns makes it incompatible with the sequential access nature of disk storage. So use SSD? Are people seriously still trying to use spinning disk for database workloads in 2024?
- JoeAltmaier 2y agoData farms are all about cost per GB. Spinning media is a fraction of the cost per.
- jandrewrogers 2y agoAn SSD does not solve the problem of page fault chasing, it just makes it slightly less bad. This is fundamentally a software architecture problem. This is solved with latency-hiding I/O schedulers, which don’t rely on cache locality for throughput.
- redskyluan 2y agoEven SSD won't be fast enough for most indexes due to the random access nature. I've seen more than 1M iops on a huge nvme disk when use DiskANN index
- VoVAllen 2y agoHi, I'm the author of the article. The sequential access pattern of IVF makes prefetching and large block sequential reads much easier, whereas it's almost impossible for HNSW to achieve efficient prefetching.
- 634636346 2y ago[dead]
- srajabi 2y agoWhat about DiskANN? https://milvus.io/docs/disk_index.md https://milvus.io/docs/disk_index.md
- antirez 2y agoQuantization can be applied exactly in the same way in HNSW. I'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). About insertion / 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.
- cratermoon 2y ago"Its reliance on frequent random access patterns makes it incompatible with the sequential access nature of disk storage." Is this true for SSD storage, or does it only apply to spinning metal platters?
- VoVAllen 2y agoHi, I'm the author of the article. The sequential access pattern of IVF makes prefetching and large block sequential reads much easier, whereas it's almost impossible for HNSW to achieve efficient prefetching.
- cratermoon 2y agoYes, I get that, but does the large block sequential read pattern matter with SSDs, or do the benefits only accrue with spinning disk drives?
- weiichongy24 2y ago[dead]
- ahevenor 2y agoHNSW 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.
- ahevenor 2y agohttps://aerospike.com/docs/vector/learn/caching https://aerospike.com/docs/vector/learn/caching
- Jackosas 2y ago[dead]
- adeptima 2y agoHighly recommend to prompt the following in LLM if you are trying to grasp Hybrid(Keyword, Filter + Vector) search or HNSW vs IVF flavour topics Graph-Based (HNSW) vs Cluster-Based (IVF) Memory Usage: Higher for HNSW due to graph storage requirements vs Lowerfor IVF; stores cluster centroids and subsets of vectors Accuracy: High recall and precision, close to exact search vs Recall depends on the number of clusters and visited partitions Build Time: Slower for HNSW, Faster for IVF Best for: Real-time, high-accuracy tasks requiring dynamic updates vs Large, static datasets with strict memory constraints Notable Graph-Based (HNSW) Variants - Faiss HNSW or PANNG (Proximity and Navigable Neighbor Graph) Cluster-Based (IVF) Variants - IVF-PQ for memory-constrained environments, Multi-Index IVF partitions, IVF-GPU
- Peterthomos 2y ago[dead]