arXiv：cs.LG· Anders Wikum, Nina Mishra, Amin Saberi, Tal Wagner·· 3 小时前AI 评分41
研究：向量检索几何上可行时，学习查询编码器仍可能很难
Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy
AI 导读
研究提出"冻结文档索引下最大召回率"这一几何容量概念，发现在多个真实检索基准上，单向量查询编码器的检索质量远低于文档索引所能支撑的上限。作者进一步构造了一个检索任务：存在由小型单隐层 ReLU 网络表示的完美召回查询编码器，但任何统计查询学习器要取得优于随机基线 k/n 的非平凡召回优势，都需要指数级数量的统计查询。
正文
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.
| Subjects: | Information Retrieval (cs.IR); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.02749 [cs.IR] |
| (or arXiv:2610.02749v1 [cs.IR] for this version) | |
| https://doi.org/10.48550/arXiv.2610.02749 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Anders Wikum [view email]
[v1]
Fri, 2 Oct 2026 03:22:56 UTC (95 KB)
来源：arXiv：cs.LG · arxiv.org