FRESH

Hacker News

Home

Scaling HNSWs

220 points by cyndunlop

by stevage

3 subcomments

From Wikipedia:
> The Hierarchical navigable small world (HNSW) algorithm is a graph-based approximate nearest neighbor search technique used in many vector databases.[1] Nearest neighbor search without an index involves computing the distance from the query to each point in the database, which for large datasets is computationally prohibitive. For high-dimensional data, tree-based exact vector search techniques such as the k-d tree and R-tree do not perform well enough because of the curse of dimensionality.

by softwaredoug

5 subcomments

At very high scale, there's less usage of graphs. Or there's a set of clustering on top of graphs.
Graphs can be complex to build and rebalance. Graph-like data structures with a thing, then a pointer out to another thing, aren't that cache friendly.
Add to that, people almost always want to *filter* vector search results. And this is a huge blindspot for consumers and providers. It's where the ugly performance surprises come from. Filtered HNSW isn't straightforward, and requires you to just keep traversing the graph looking for results that satisfy your filter.
HNSW came out of a benchmark regime where we just indexed some vectors and tried to only maximize recall for query latency. It doesn't take into account the filtering / indexing almost everyone wants.
Turbopuffer, for example, doesn't use graphs at all, it uses SPFresh. And they recently got 200ms latency on 100B vectors.
https://turbopuffer.com/docs/vector

by simonw

1 subcomments

This is well worth reading in full. The section about threading is particularly interesting: most of Redis is single-threaded, but antirez decided to use threads for the HNSW implementation and explains why.

by jbellis

1 subcomments

two great points here: (1) quantization is how you speed up vector indexes, and (2) how your build your graph matters much much less*
These are the insights behind DiskANN, which has replaced HNSW in most production systems.
past that, well, you should really go read the DiskANN paper instead of this article, product quantization is way way way way way more effective than simple int8 or binary quant.
here's my writeup from a year and a half ago: https://dev.to/datastax/why-vector-compression-matters-64l
and if you want to skip forward several years to the cutting edge, check out https://arxiv.org/abs/2509.18471 and the references list for further reading
* but it still matters more than a lot of people thought circa 2020

by patcon

1 subcomments

> Similarly, there are, right now, efforts in order to really check if the “H” in the HNSWs is really needed, and if instead a flat data structure with just one layer would perform more or less the same (I hope I’ll cover more about this in the future: my feeling is that the truth is in the middle, and that it makes sense to modify the level selection function to just have levels greater than a given threshold).
Small world networks have been my obsession for almost a decade, from a biological and sociological evolution angle. Love this stuff.
This is the paper he's referring to, which I was just reading again yesterday :)
Down with the Hierarchy: The 'H' in HNSW Stands for "Hubs" (2025) https://arxiv.org/abs/2412.01940
Also:
Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data (2010) https://www.jmlr.org/papers/v11/radovanovic10a.html
As someone also interested in not just repair of the social fabric, but the evolution of gendered social dynamics in social species (biologically and culturally), it's interesting to me that there might be some property of networks that:
1. Makes any random point as close as possible to any other random point (all solutions are equally likely to be close to the unknown solution somewhere in the network)
2. Minimally edges must be maintained (valuable in social networks, where edges are relationships that have maintenance cost)
3. Involves some negotiation between hierarchy (aka entrepreneurial networks, with opportunity for value extraction thru rent-seeking traffic) and hubness (which dissolve capture points in networks via "weaving" them out of existence). All the short paths in a small-world pass through hubs, which necessarily maintain many more weaker connections in a much more "gossip" comms protocols
Am working on this stuff related to collective intelligence and democracy work, if anyone wants to be in touch https://linkedin.com/in/patcon-

by dizzant

1 subcomments

> many programmers are smart, and if instead of creating a magic system they have no access to, you show them the data structure, the tradeoffs, they can build more things, and model their use cases in specific ways. And your system will be simpler, too.
Basically my entire full-time job is spent prosecuting this argument. It is indeed true that many programmers are smart, but it is equally true that many programmers _are not_ smart, and those programmers have to contribute too. More hands is usually better than simpler systems for reasons that have nothing to do with technical proficiency.

by natenethercott

1 subcomments

> Actually, you can implement HNSWs on disk, even if there are better data structures from the point of view of disk access latencies
I built a KV-backed HNSW in Rust using LMDB to address this exact usecase (https://github.com/nnethercott/hannoy). The trickiest part for sure is being clever with your IO ops since HNSW search requires tons of random reads to find the nearest neighbours. Especially if you're not on NVMe's (think EBS-based HNSW) you really start to feel the cost of those reads, even with all the fancy SIMD.

by jacobgorm

0 subcomment

What the blog post calls Vector Quantization is just numeric vector component quantization. Vector quantization typically uses K-means to quantize the entire vector, or parts of the vector in product quantization, into K-means indices.
https://en.wikipedia.org/wiki/Vector_quantization

by udkl

0 subcomment

Two resources that helped me understand HNSWs: https://blog.wilsonl.in/graph-vector-search/ https://github.com/brtholomy/hnsw

by danielfalbo

1 subcomments

> long, sad story about MacOS and bad habits – I hadn’t lost something like that since the 90s, during blackouts
would love to hear this story as well now!

by rishabhaiover

1 subcomments

How does redis deal with the case of an in-memory HNSW growing faster than it can comfortably flush pages to disk?

by unit149

0 subcomment

[dead]

by cluckindan

1 subcomments

I may not remember this correctly, but normalizing to -127..127 may be counterproductive. When normalized to -1..1, all of Euclidian, dot product and cosine similarities produce the same ranking, allowing you to calculate similarity without having to calculate cosines.