[jhj]

Speaking as an author of one of the primary libraries for doing this stuff (faiss), it is not because it is still an open ended research problem on how approximate high-dimensional dense or sparse nearest neighbor should work, let alone maximum inner product search where the research story is even worse, or other non-metric space similarity measures. All of the current techniques still have quite unacceptable tradeoffs involved.

While traditional database indexing is also still an open-ended research problem (e.g., read amplification/write amplification tradeoffs and the like), it produces exact solutions. That isn't the case at all for vector indexing beyond brute-force search, or exact indexing like k-D/BSP trees which don't work well in high dimensions due to the curse of dimensionality.

[jbellis]

Why is the research story for MIPS even worse than for ANN?

[jhj]

There is no good geometry to be exploited, and the query vectors might be (and are usually) distributed quite differently than the indexed vectors.

For Euclidean (L2) distance indexes where the vectors are partitioned based on geometry (e.g., pretty much every indexing type, including cell-probe like IVF, most forms of LSH, or graph based indices), query vectors can be naturally associated geometrically with candidate nearest neighbor vectors, so the distribution of queries doesn't matter as much.

For inner product, it's hard to do much better than spherical clustering (what one would usually do for cosine similarity, which is to project all vectors to the surface of a unit hypersphere, and searching for nearest neighbors via cosine similarity is exactly equivalent to L2 search). But, in general the maximum inner product in the indexed set may lie nowhere near to the projection of the query vector onto the surface of the hypersphere.

The maximum inner product for a query vector might be almost nearly perpendicular to the query vector (e.g., a very, very far out and almost perpendicular) versus a vector that is parallel to the query vector but with tiny norm. In two dimensions, an example could be (1, 0) as a query vector, but (1, 10^6) as a database vector (or vice versa). The inner product is 1 but the two vectors are very far apart in Euclidean distance. If you project the vectors to the unit 1-sphere, the query vector is still (1, 0) but the database vector now becomes (1 / sqrt(10^12 + 1), 10^6 / sqrt(10^12 + 1)) ~= (0.000000999..., 0.99999...) (apologies if there's an error here) which would also be in a very different cell if one were using a graph-based or IVF partitioning.

Neural search techniques do show some promise here though (say, using a neural net to predict which vector buckets to look at).

[sjkoelle]

How much of this is due to DNNs (e.g. VAEs but also others) forcing embeddings to distribute in a Gaussianish manner? Is the data intrinsically missing geometry or could a more subtle learning algorithm give a cleaner manifold and therefore more efficiently indexable structure?

[jbellis]

Thanks!

What kinds of use cases cause this kind of situation, where the query and indexed vectors are from different distributions?