Breaking The Curse Of Dimensionality: On The Stability Of Modern Vector Retrieval

Abstract

Modern vector databases enable efficient retrieval over high-dimensional neural embeddings, powering applications from web search to retrieval-augmented generation. However, classical theory predicts such tasks should suffer from the curse of dimensionality, where distances between points become nearly indistinguishable, thereby crippling efficient nearest-neighbor search. We revisit this paradox through the lens of stability, the property that small perturbations to a query do not radically alter its nearest neighbors. Building on foundational results, we extend stability theory to three key retrieval settings widely used in practice: (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 induce stability even when the underlying search is unstable; and (iii) sparse vector

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keylakshman2025breaking

Related papers

• Gleanvec: Accelerating Vector Search With Minimalist Nonlinear Dimensionality Reduction (2024)0.00
• On Strengths And Limitations Of Single-vector Embeddings (2026)0.00
• Scaling Laws For Embedding Dimension In Information Retrieval (2026)0.00
• Semantic Certainty Assessment In Vector Retrieval Systems: A Novel Framework For Embedding Quality Evaluation (2025)0.00
• On The Theoretical Limitations Of Embedding-based Retrieval (2025)0.00
• Leanvec: Searching Vectors Faster By Making Them Fit (2023)0.00
• Can You Trust The Vectors In Your Vector Database? Black-hole Attack From Embedding Space Defects (2026)0.00
• Reveal Hidden Pitfalls And Navigate Next Generation Of Vector Similarity Search From Task-centric Views (2025)0.00