mlsanityData to 14 Oct 2026

On the Theoretical Limitations of Embedding-Based Retrieval

arXiv 2508.21038 ↗First posted 28 Aug 2025cs.IR cs.CL cs.LGcited by 104

Not on the map. Why?

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.

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

52 of 77 references.

References · 52

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,170
  3. 2018Representation Learning with Contrastive Predictive Codingcited by 7,777
  4. 2025Gemini 2.5: Pushing the Frontier with Advanced Reasoning, Multimodality, Long Context, and Next Generation Agentic Capabilitiescited by 3,796
  5. 2018HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answeringcited by 3,754
  6. 2022Training Compute-Optimal Large Language Modelscited by 3,019
  7. 2025Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Modelscited by 1,261
  8. 2022Text Embeddings by Weakly-Supervised Contrastive Pre-trainingcited by 1,253
  9. 2021BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Modelscited by 1,252
  10. 2023Instruction-Following Evaluation for Large Language Modelscited by 1,228
  11. 2021Unsupervised Dense Information Retrieval with Contrastive Learningcited by 1,216
  12. 2020ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERTcited by 1,178
38 more
  1. 2024Chameleon: Mixed-Modal Early-Fusion Foundation Modelscited by 927
  2. 2019Latent Retrieval for Weakly Supervised Open Domain Question Answeringcited by 695
  3. 2025BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agentscited by 647
  4. 2022MTEB: Massive Text Embedding Benchmarkcited by 640
  5. 2020Fact or Fiction: Verifying Scientific Claimscited by 554
  6. 2024Smarter, Better, Faster, Longer: A Modern Bidirectional Encoder for Fast, Memory Efficient, and Long Context Finetuning and Inferencecited by 554
  7. 2024LLM2Vec: Large Language Models Are Secretly Powerful Text Encoderscited by 404
  8. 2022One Embedder, Any Task: Instruction-Finetuned Text Embeddingscited by 333
  9. 2023Improving Text Embeddings with Large Language Modelscited by 303
  10. 2020Overview of the TREC 2019 deep learning trackcited by 286
  11. 2022Matryoshka Representation Learningcited by 282
  12. 2023Multimodal Foundation Models: From Specialists to General-Purpose Assistantscited by 247
  13. 2024Generative Representational Instruction Tuningcited by 233
  14. 2024ColPali: Efficient Document Retrieval with Vision Language Modelscited by 195
  15. 2024BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrievalcited by 158
  16. 2025MMTEB: Massive Multilingual Text Embedding Benchmarkcited by 125
  17. 2024Unifying Multimodal Retrieval via Document Screenshot Embeddingcited by 110
  18. 2025Gemini Embedding: Generalizable Embeddings from Geminicited by 94
  19. 2024BM25S: Orders of magnitude faster lexical search via eager sparse scoringcited by 88
  20. 2024Gecko: Versatile Text Embeddings Distilled from Large Language Modelscited by 83
  21. 2025Rank1: Test-Time Compute for Reranking in Information Retrievalcited by 70
  22. 2024FollowIR: Evaluating and Teaching Information Retrieval Models to Follow Instructionscited by 69
  23. 2024Arctic-Embed 2.0: Multilingual Retrieval Without Compromisecited by 58
  24. 2020The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizescited by 48
  25. 2018On the Dimensionality of Word Embeddingcited by 46
  26. 2024Promptriever: Instruction-Trained Retrievers Can Be Prompted Like Language Modelscited by 40
  27. 2025Seq vs Seq: An Open Suite of Paired Encoders and Decoderscited by 38
  28. 2024RAR-b: Reasoning as Retrieval Benchmarkcited by 36
  29. 2024INSTRUCTIR: A Benchmark for Instruction Following of Information Retrieval Modelscited by 33
  30. 2023QUEST: A Retrieval Dataset of Entity-Seeking Queries with Implicit Set Operationscited by 31
  31. 2019Analyzing the Limitations of Cross-lingual Word Embedding Mappingscited by 19
  32. 2025PyLate: Flexible Training and Retrieval for Late Interaction Modelscited by 18
  33. 2025IFIR: A Comprehensive Benchmark for Evaluating Instruction-Following in Expert-Domain Information Retrievalcited by 16
  34. 2025FreshStack: Building Realistic Benchmarks for Evaluating Retrieval on Technical Documentscited by 15
  35. 2023Taming the Sigmoid Bottleneck: Provably Argmaxable Sparse Multi-Label Classificationcited by 11
  36. 2025mFollowIR: a Multilingual Benchmark for Instruction Following in Retrievalcited by 7
  37. 2025Hypencoder: Hypernetworks for Information Retrievalcited by 7
  38. 2024Beyond Content Relevance: Evaluating Instruction Following in Retrieval Modelscited by 6

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 29; 2026: 75.

104 papers.

Sort:

By area:

  1. 2025MetaEmbed: Scaling Multimodal Retrieval at Test-Time with Flexible Late Interactioncited by 39
  2. 2025PLUM: Adapting Pre-trained Language Models for Industrial-scale Generative Recommendationscited by 30
  3. 2025The Geometry of Reasoning: Flowing Logics in Representation Spacecited by 21
  4. 2026StructMem: Structured Memory for Long-Horizon Behavior in LLMscited by 18
  5. 2026Understanding LoRA as Knowledge Memory: An Empirical Analysiscited by 12
  6. 2025Milco: Learned Sparse Retrieval Across Languages via a Multilingual Connectorcited by 9
  7. 2025PRISM: Agentic Retrieval with LLMs for Multi-Hop Question Answeringcited by 8
  8. 2025AutoSurvey2: Empowering Researchers with Next Level Automated Literature Surveyscited by 8
  9. 2026Dynamic Long Context Reasoning over Compressed Memory via End-to-End Reinforcement Learningcited by 8
  10. 2026Revisiting Text Ranking in Deep Researchcited by 7
  11. 2025Understanding Generative Recommendation with Semantic IDs from a Model-scaling Viewcited by 6
  12. 2025Beyond the Failures: Rethinking Foundation Models in Pathologycited by 6
38 more
  1. 2026Query-focused and Memory-aware Reranker for Long Context Processingcited by 6
  2. 2026Vectorizing the Trie: Efficient Constrained Decoding for LLM-based Generative Retrieval on Acceleratorscited by 6
  3. 2025Global Minimizers of Sigmoid Contrastive Losscited by 5
  4. 2025Beyond the limitation of a single query: Train your LLM for query expansion with Reinforcement Learningcited by 5
  5. 2025Beyond Single Embeddings: Capturing Diverse Targets with Multi-Query Retrievalcited by 5
  6. 2025From Topology to Retrieval: Decoding Embedding Spaces with Unified Signaturescited by 5
  7. 2026Long-Tail Knowledge in Large Language Models: Taxonomy, Mechanisms, Interventions and Implicationscited by 5
  8. 2026ParamMem: Augmenting Language Agents with Parametric Reflective Memorycited by 5
  9. 2025LLM-guided Hierarchical Search for End-to-end Reasoning Intensive Retrievalcited by 4
  10. 2026Taxonomy of the Retrieval System Framework: Pitfalls and Paradigmscited by 4
  11. 2026What Limits Does Quantization Place on Dense Top-k Retrieval? A Theoretical Studycited by 4
  12. 2026A Systematic Approach to Multi-Agent AI from Advanced Regulatory Control Theory: Safe and Auditable LLM Operator Agents for Process Controlcited by 4
  13. 2025Structured RAG for Answering Aggregative Questionscited by 3
  14. 2026Beyond Single-Shot: Multi-step Tool Retrieval via Query Planningcited by 3
  15. 2026Efficient and High-Fidelity Omni Modality Retrievalcited by 3
  16. 2026Is Dimensionality a Barrier for Retrieval Models?cited by 3
  17. 2026Why Solve It Twice? Hierarchical Accumulation of Skills for Transfer-Efficient ML Engineeringcited by 3
  18. 2026Retrieval Needs Multivectors: An Exponential Separationcited by 3
  19. 2025Improving Consistency in Retrieval-Augmented Systems with Group Similarity Rewardscited by 2
  20. 2025Diffusion-Inspired Masked Fine-Tuning for Knowledge Injection in Autoregressive LLMscited by 2
  21. 2026Controlling Authority Retrieval: A Missing Retrieval Objective for Authority-Governed Knowledgecited by 2
  22. 2026Superintelligent Retrieval Agent: The Next Frontier of Agentic Retrievalcited by 2
  23. 2026MulTaBench: Benchmarking Multimodal Tabular Learning with Text and Imagecited by 2
  24. 2026EvoEmbedding: Evolvable Representations for Long-Context Retrieval and Agentic Memorycited by 2
  25. 2026Can Language Models Actually Retrieve In-Context? Drowning in Documents at Million Token Scalecited by 2
  26. 2026Semantics Delivery Network: Rethinking Web Retrieval Infrastructure for LLM Agentscited by 2
  27. 2025Automatic Music Sample Identification with Multi-Track Contrastive Learningcited by 1
  28. 2025On-device Semantic Selection Made Low Latency and Memory Efficient with Monolithic Forwardingcited by 1
  29. 2025Optimizing Retrieval for RAG via Reinforcement Learningcited by 1
  30. 2025LIR: The First Workshop on Late Interaction and Multi Vector Retrieval @ ECIR 2026cited by 1
  31. 2026Topo-RAG: Topology-aware retrieval for hybrid text-table documentscited by 1
  32. 2026The P-Completeness of Inverted Index Traversal: On the Complexity of Evaluating Boolean Query DAGscited by 1
  33. 2026LMK > CLS: Landmark Pooling for Dense Embeddingscited by 1
  34. 2026OmniReview: A Large-scale Benchmark and LLM-enhanced Framework for Realistic Reviewer Recommendationcited by 1
  35. 2026With Argus Eyes: Assessing Retrieval Gaps via Uncertainty Scoring to Detect and Remedy Retrieval Blind Spotscited by 1
  36. 2026Language Model Memory and Memory Models for Languagecited by 1
  37. 2026Revolutionizing Long-Term Memory in AI: New Horizons with High-Capacity and High-Speed Storagecited by 1
  38. 2026Fine-Grained Table Retrieval Through the Lens of Complex Queriescited by 1

50 most cited of 104 All 104 (JSON)