# Breaking the Curse of Dimensionality: On the Stability of Modern Vector Retrieval

arXiv: https://arxiv.org/abs/2512.12458 · HTML: https://mlsanity.com/paper/2512.12458/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Vector search and ANN indexes, one of 15 directions in Retrieval-augmented generation.
- Builds on 25 of its 45 references that are in the map.
- First posted on arXiv 13 Dec 2025.

## Placed in

- Retrieval-augmented generation / [Vector search and ANN indexes](https://mlsanity.com/rag/vector-search-and-ann-indexes/)

## Builds on (most cited first, 25 of 25)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking](https://mlsanity.com/paper/2107.05720/) (2021)
- [Intrinsic dimension of data representations in deep neural networks](https://mlsanity.com/paper/1905.12784/) (2019)
- [Recommender Systems with Generative Retrieval](https://mlsanity.com/paper/2305.05065/) (2023)
- [ColPali: Efficient Document Retrieval with Vision Language Models](https://mlsanity.com/paper/2407.01449/) (2024)
- [Embedding-based Retrieval in Facebook Search](https://mlsanity.com/paper/2006.11632/) (2020)
- [SPLADE v2: Sparse Lexical and Expansion Model for Information Retrieval](https://mlsanity.com/paper/2109.10086/) (2021)
- [PLAID: An Efficient Engine for Late Interaction Retrieval](https://mlsanity.com/paper/2205.09707/) (2022)
- [SPLADE-v3: New baselines for SPLADE](https://mlsanity.com/paper/2403.06789/) (2024)
- [On the Intrinsic Dimensionality of Image Representations](https://mlsanity.com/paper/1803.09672/) (2018)
- [Semantic Product Search](https://mlsanity.com/paper/1907.00937/) (2019)
- [The Shape of Learning: Anisotropy and Intrinsic Dimensions in Transformer-Based Models](https://mlsanity.com/paper/2311.05928/) (2023)
- [ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data](https://mlsanity.com/paper/2403.04871/) (2024)
- [MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings](https://mlsanity.com/paper/2405.19504/) (2024)
- [Efficient Inverted Indexes for Approximate Retrieval over Learned Sparse Representations](https://mlsanity.com/paper/2404.18812/) (2024)
- [Semantic IDs for Joint Generative Search and Recommendation](https://mlsanity.com/paper/2508.10478/) (2025)
- [Approximate Nearest Neighbor Search with Window Filters](https://mlsanity.com/paper/2402.00943/) (2024)
- [DESSERT: An Efficient Algorithm for Vector Set Search with Vector Set Queries](https://mlsanity.com/paper/2210.15748/) (2022)
- [CAPS: A Practical Partition Index for Filtered Similarity Search](https://mlsanity.com/paper/2308.15014/) (2023)
- [Constrained Approximate Similarity Search on Proximity Graph](https://mlsanity.com/paper/2210.14958/) (2022)

## Abstract (arXiv)

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 search, where we formalize and prove novel sufficient stability conditions. Across synthetic and real datasets, our experimental results match our theoretical predictions, offering concrete guidance for model and system design to avoid the curse of dimensionality.