When is Multi-Vector, Filtered, and Sparse Nearest Neighbor Meaningful? On the Stability of Modern Vector Retrieval

Modern vector databases enable efficient retrieval over high-dimensional neural embeddings, powering applications from web search to retrieval-augmented generation. However, classical theory predicts that for many high-dimensional workloads, nearest neighbor search should be inefficient as distances between points become nearly indistinguishable. Prior works have studied the notion of stability in traditional nearest-neighbor search, and identify stable workloads, which are amenable to efficient search. However, no existing research has studied stability in the context of modern formulations of similarity search that have gained traction in practice. Building on foundational results, we extend stability theory to three key retrieval settings: (i) multi-vector search, where we prove that the popular Chamfer distance metric preserves single-vector stability, while average pooling aggregation may destroy it; (ii) filtered vector search, where we show that sufficiently large penalties for mismatched filters can preserve stability; and (iii) sparse vector search, where we formalize and prove novel sufficient stability conditions via the concepts of concentration of importance and overlap of importance. Together, our results extend the classical theory of nearest neighbor meaningfulness to new retrieval settings prevalent in modern practice, offering an explanation for several of the empirically successful design choices behind state-of-the-art vector search systems.