# On the Theoretical Limitations of Embedding-Based Retrieval

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

## Key facts

- Cited by 104 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 77 references that are in the map.
- First posted on arXiv 28 Aug 2025.

## Builds on (most cited first, 30 of 52)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilities](https://mlsanity.com/paper/2507.06261/) (2025)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models](https://mlsanity.com/paper/2506.05176/) (2025)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023)
- [Unsupervised Dense Information Retrieval with Contrastive Learning](https://mlsanity.com/paper/2112.09118/) (2021)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Chameleon: Mixed-Modal Early-Fusion Foundation Models](https://mlsanity.com/paper/2405.09818/) (2024)
- [Latent Retrieval for Weakly Supervised Open Domain Question Answering](https://mlsanity.com/paper/1906.00300/) (2019)
- [BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agents](https://mlsanity.com/paper/2504.12516/) (2025)
- [MTEB: Massive Text Embedding Benchmark](https://mlsanity.com/paper/2210.07316/) (2022)
- [Fact or Fiction: Verifying Scientific Claims](https://mlsanity.com/paper/2004.14974/) (2020)
- [Smarter, Better, Faster, Longer: A Modern Bidirectional Encoder for Fast, Memory Efficient, and Long Context Finetuning and Inference](https://mlsanity.com/paper/2412.13663/) (2024)
- [LLM2Vec: Large Language Models Are Secretly Powerful Text Encoders](https://mlsanity.com/paper/2404.05961/) (2024)
- [One Embedder, Any Task: Instruction-Finetuned Text Embeddings](https://mlsanity.com/paper/2212.09741/) (2022)
- [Improving Text Embeddings with Large Language Models](https://mlsanity.com/paper/2401.00368/) (2023)
- [Overview of the TREC 2019 deep learning track](https://mlsanity.com/paper/2003.07820/) (2020)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [Multimodal Foundation Models: From Specialists to General-Purpose Assistants](https://mlsanity.com/paper/2309.10020/) (2023)
- [Generative Representational Instruction Tuning](https://mlsanity.com/paper/2402.09906/) (2024)
- [ColPali: Efficient Document Retrieval with Vision Language Models](https://mlsanity.com/paper/2407.01449/) (2024)
- [BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrieval](https://mlsanity.com/paper/2407.12883/) (2024)
- [MMTEB: Massive Multilingual Text Embedding Benchmark](https://mlsanity.com/paper/2502.13595/) (2025)
- [Unifying Multimodal Retrieval via Document Screenshot Embedding](https://mlsanity.com/paper/2406.11251/) (2024)
- [Gemini Embedding: Generalizable Embeddings from Gemini](https://mlsanity.com/paper/2503.07891/) (2025)

## Built on by (most cited first, 30 of 104)

- [MetaEmbed: Scaling Multimodal Retrieval at Test-Time with Flexible Late Interaction](https://mlsanity.com/paper/2509.18095/) (2025)
- [PLUM: Adapting Pre-trained Language Models for Industrial-scale Generative Recommendations](https://mlsanity.com/paper/2510.07784/) (2025)
- [The Geometry of Reasoning: Flowing Logics in Representation Space](https://mlsanity.com/paper/2510.09782/) (2025)
- [StructMem: Structured Memory for Long-Horizon Behavior in LLMs](https://mlsanity.com/paper/2604.21748/) (2026)
- [Understanding LoRA as Knowledge Memory: An Empirical Analysis](https://mlsanity.com/paper/2603.01097/) (2026)
- [Milco: Learned Sparse Retrieval Across Languages via a Multilingual Connector](https://mlsanity.com/paper/2510.00671/) (2025)
- [PRISM: Agentic Retrieval with LLMs for Multi-Hop Question Answering](https://mlsanity.com/paper/2510.14278/) (2025)
- [AutoSurvey2: Empowering Researchers with Next Level Automated Literature Surveys](https://mlsanity.com/paper/2510.26012/) (2025)
- [Dynamic Long Context Reasoning over Compressed Memory via End-to-End Reinforcement Learning](https://mlsanity.com/paper/2602.08382/) (2026)
- [Revisiting Text Ranking in Deep Research](https://mlsanity.com/paper/2602.21456/) (2026)
- [Understanding Generative Recommendation with Semantic IDs from a Model-scaling View](https://mlsanity.com/paper/2509.25522/) (2025)
- [Beyond the Failures: Rethinking Foundation Models in Pathology](https://mlsanity.com/paper/2510.23807/) (2025)
- [Query-focused and Memory-aware Reranker for Long Context Processing](https://mlsanity.com/paper/2602.12192/) (2026)
- [Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Accelerators](https://mlsanity.com/paper/2602.22647/) (2026)
- [Global Minimizers of Sigmoid Contrastive Loss](https://mlsanity.com/paper/2509.18552/) (2025)
- [Beyond the limitation of a single query: Train your LLM for query expansion with Reinforcement Learning](https://mlsanity.com/paper/2510.10009/) (2025)
- [Beyond Single Embeddings: Capturing Diverse Targets with Multi-Query Retrieval](https://mlsanity.com/paper/2511.02770/) (2025)
- [From Topology to Retrieval: Decoding Embedding Spaces with Unified Signatures](https://mlsanity.com/paper/2511.22150/) (2025)
- [Long-Tail Knowledge in Large Language Models: Taxonomy, Mechanisms, Interventions and Implications](https://mlsanity.com/paper/2602.16201/) (2026)
- [ParamMem: Augmenting Language Agents with Parametric Reflective Memory](https://mlsanity.com/paper/2602.23320/) (2026)
- [LLM-guided Hierarchical Search for End-to-end Reasoning Intensive Retrieval](https://mlsanity.com/paper/2510.13217/) (2025)
- [Taxonomy of the Retrieval System Framework: Pitfalls and Paradigms](https://mlsanity.com/paper/2601.20131/) (2026)
- [What Limits Does Quantization Place on Dense Top-k Retrieval? A Theoretical Study](https://mlsanity.com/paper/2606.11780/) (2026)
- [A Systematic Approach to Multi-Agent AI from Advanced Regulatory Control Theory: Safe and Auditable LLM Operator Agents for Process Control](https://mlsanity.com/paper/2606.30877/) (2026)
- [Structured RAG for Answering Aggregative Questions](https://mlsanity.com/paper/2511.08505/) (2025)
- [Beyond Single-Shot: Multi-step Tool Retrieval via Query Planning](https://mlsanity.com/paper/2601.07782/) (2026)
- [Efficient and High-Fidelity Omni Modality Retrieval](https://mlsanity.com/paper/2603.02098/) (2026)
- [Is Dimensionality a Barrier for Retrieval Models?](https://mlsanity.com/paper/2605.23556/) (2026)
- [Why Solve It Twice? Hierarchical Accumulation of Skills for Transfer-Efficient ML Engineering](https://mlsanity.com/paper/2606.30911/) (2026)
- [Retrieval Needs Multivectors: An Exponential Separation](https://mlsanity.com/paper/2608.21494/) (2026)

## Abstract (arXiv)

Vector embeddings have been tasked with an ever-increasing set of retrieval tasks over the years, with a nascent rise in using them for reasoning, instruction-following, coding, and more. These new benchmarks push embeddings to work for any query and any notion of relevance that could be given. While prior works have pointed out theoretical limitations of vector embeddings, there is a common assumption that these difficulties are exclusively due to unrealistic queries, and those that are not can be overcome with better training data and larger models. In this work, we demonstrate that we may encounter these theoretical limitations in realistic settings with extremely simple queries. We connect known results in learning theory, showing that the number of top-k subsets of documents capable of being returned as the result of some query is limited by the dimension of the embedding. We empirically show that this holds true even if we directly optimize on the test set with free parameterized embeddings. Using free embeddings, we then demonstrate that returning all pairs of documents requires a relatively high dimension. We then create a realistic dataset called LIMIT that stress tests embedding models based on these theoretical results, and observe that even state-of-the-art models fail on this dataset despite the simple nature of the task. Our work shows the limits of embedding models under the existing single vector paradigm and calls for future research to develop new techniques that can resolve this fundamental limitation.