aiqbench analysis
This research identifies a fundamental computational barrier in embedding-based retrieval, demonstrating that even when document indices possess sufficient geometric capacity, learning effective query encoders can be provably hard for statistical learners. The authors provide theoretical evidence that achieving optimal recall may require exponentially many queries, suggesting significant unrealized potential in current benchmarks where single-vector encoders underperform relative to the index's theoretical limits.
Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy
arXiv:2610.02749v1 Announce Type: cross Abstract: Efficient vector retrieval requires both a corpus geometry that supports retrieving the right documents through vector similarity, and a query encoder that can embed queries near their desired documents in the embedding space. Recent work has studied geometric capacity through the lens of the minimum embedding dimension needed to realize all top-$k$ answer sets of $n$ documents. We study a different notion of geometric capacity--the maximum recall achievable for a frozen document index--and explore whether learned query encoders can reach this ceiling. On several real-world retrieval benchmarks, we show that retrieval quality of single-vector query encoders often lies far below what the document indices can support. Motivated by this observation, we give theoretical evidence that learning query encoders can be computationally hard. In particular, we construct a retrieval task that (1) admits a query encoder with perfect recall which is representable by a small one-hidden-layer ReLU network, but (2) any statistical-query learner (a class capturing learners that access training data through aggregate statistics) provably requires exponentially many statistical queries to achieve non-trivial recall advantage over the random baseline $k/n$. Taken together, our results suggest substantial unrealized geometric capacity in retrieval benchmarks and establish query encoder learnability as a possible barrier in embedding-based retrieval.
Abstract:Efficient vector retrieval requires both a corpus geometry that supports retrieving the right documents through vector similarity, and a query encoder that can embed queries near their desired documents in the embedding space. Recent work has studied geometric capacity through the lens of the minimum embedding dimension needed to realize all top-$k$ answer sets of $n$ documents. We study a different notion of geometric capacity--the maximum recall achievable for a frozen document index--and explore whether learned query encoders can reach this ceiling. On several real-world retrieval benchmarks, we show that retrieval quality of single-vector query encoders often lies far below what the document indices can support. Motivated by this observation, we give theoretical evidence that learning query encoders can be computationally hard. In particular, we construct a retrieval task that (1) admits a query encoder with perfect recall which is representable by a small one-hidden-layer ReLU network, but (2) any statistical-query learner (a class capturing learners that access training data through aggregate statistics) provably requires exponentially many statistical queries to achieve non-trivial recall advantage over the random baseline $k/n$. Taken together, our results suggest substantial unrealized geometric capacity in retrieval benchmarks and establish query encoder learnability as a possible barrier in embedding-based retrieval.
Information Retrieval (cs.IR); Machine Learning (cs.LG)
arXiv:2610.02749 [cs.IR]
(or arXiv:2610.02749v1 [cs.IR] for this version)
https://doi.org/10.48550/arXiv.2610.02749 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 300 words
Related coverage
Training and Finetuning Multi-Vector Embedding Models with Sentence Transformers
Hugging Face · Aug 26, 2026
Introducing the Ettin Reranker Family
Hugging Face · May 19, 2026
Presentation: From Models to Agents: Building Context-Aware Consumer AI at Scale at DoorDash
InfoQ · Aug 15, 2026
What's Continual Learning, and Why Might We Expect To See It In Advanced LLM Agents?
LessWrong · Jun 12, 2026