# ℝ2k is Theoretically Large Enough for Embedding-based Top-k Retrieval

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 18 references that are in the map.
- First posted on arXiv 28 Jan 2026.

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

- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [Unsupervised Dense Information Retrieval with Contrastive Learning](https://mlsanity.com/paper/2112.09118/) (2021)
- [Latent Retrieval for Weakly Supervised Open Domain Question Answering](https://mlsanity.com/paper/1906.00300/) (2019)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizes](https://mlsanity.com/paper/2012.14210/) (2020)
- [On the Dimensionality of Word Embedding](https://mlsanity.com/paper/1812.04224/) (2018)
- [mFollowIR: a Multilingual Benchmark for Instruction Following in Retrieval](https://mlsanity.com/paper/2501.19264/) (2025)
- [Hierarchical Retrieval: The Geometry and a Pretrain-Finetune Recipe](https://mlsanity.com/paper/2509.16411/) (2025)
- [Information-Theoretic Bounds for Adaptive Sparse Recovery](https://mlsanity.com/paper/1402.5731/) (2014)

## Abstract (arXiv)

This paper studies the Minimal Embeddable Dimension (MED): the least dimension in which there exists a configuration of m object vectors so that every subset of size at most k is exactly retrieved by score comparison. Our result shows MED is Theta(k), independent of m, for inner product, Euclidean distance, and cosine similarity. We then consider Robust MED (RMED), where all vectors are unit normed and an ε gap of scores is required. We derive the m-dependent feasibility ceiling ε_star(m,k)=m/√k(m-1)(m-k), which approaches 1/√k when mgg k, and a Gaussian centroid construction gives a robust witness upper bound in the feasible margin regime. Numerical simulation on synthetic top-2 retrieval with cyclic polytope and centroid query optimization confirmed our theoretical claims. Experiments on LIMIT and LIMIT-small datasets also show that simple embedding-based retrieval baselines can overfit and outperform the reported single-vector LLM embedding baseline. Both theoretical and empirical findings rule out the lack of exact geometric capacity as the obstruction.