Source-linked AI summary
Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy
Anders Wikum, Nina Mishra, Amin Saberi, Tal Wagner
TL;DR
Vector retrieval requires both document geometry that supports the desired results and a learned query encoder that can reach them, but the attainable recall of an index and encoders’ ability to approach it remain key questions. The paper measures that gap on retrieval benchmarks and constructs an SQ-hard task; it finds that geometry is rarely the limit in tested settings, while learning a strong query encoder can be computationally hard.
Problem
How much recall can a frozen document index support, and can learned query encoders reach that ceiling?
Source: §1 · pp. 1–2Method
The paper estimates geometric capacity with a ranking-SVM approach and constructs a retrieval task with a perfect-recall ReLU encoder but SQ-hard learning.
Source: §1 · p. 2, §3.1 · p. 4Results
20 datasets: geometric capacity is rarely limiting, while tested query encoders mostly fail to exceed 50% or even 25% held-out recall.
Source: §1 · p. 2Takeaways & Limitations
The findings identify query-encoder learnability as a potential barrier even when the geometry of the document index is not restrictive.
Source: §5 · p. 11The empirical gap may partly reflect the specific fine-tuning setup, and the ranking-SVM capacity bounds do not immediately extend to multi-vector retrieval.
Source: A Limitations · p. 14
Abstract
from arXiv · showhide
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.
1 Introduction
Vector retrieval depends both on document geometry that supports the desired results and on learning query encoders that can reach them. The paper studies this gap empirically and theoretically, alongside prior work on geometric limits and statistical-query learning.
1 Introduction
- The paper asks how much recall a frozen document index can support and how much of that ceiling a learned query encoder can achieve.Retrieval requires both geometry that supports the intended top-k documents and a computationally feasible way to learn suitable query embeddings.Source: §1 · pp. 1–2
- Across 20 datasets, geometric capacity is rarely limiting, while tested query encoders mostly fail to exceed 50% or even 25% recall on held-out queries.The study finds near-perfect retrieval is geometrically possible on most datasets, even with a lightweight document encoder.Source: §1 · p. 2
- A constructed task has a small ReLU query encoder with perfect recall, yet any statistical-query learner needs exponentially many queries for better-than-random recall.The statistical-query model limits learners to accessing training data through aggregate statistics.Source: §1 · p. 2
1.1 Related work
- Geometric-limit research studies the minimum dimension needed to realize all top-k subsets; empirical work reports geometry is not the primary difficulty on LIMIT (Weller et al., 2026; S et al., 2026; Wang et al., 2026).Other cited work extends bounds beyond inner-product scoring, studies max-margin separation, and examines quantization (Bangachev et al., 2026; Okajima and Yoshida, 2026).Source: §1.1 · p. 2
- Prior statistical-query research includes lower bounds for learning shallow neural networks and other problems, while this work applies such techniques to single-vector retrieval (Kearns, 1993; Song et al., 2017; Goel et al., 2020; Chen et al., 2022).The SQ model restricts access to aggregate statistics, and can capture gradient-based learning under suitable precision and batch-size conditions (Abbe et al., 2021).Source: §1.1 · pp. 2–3
2 Preliminaries
The preliminaries define retrieval around query-specific target documents and expected recall. They then describe single-vector retrieval with a frozen document index and introduce statistical-query access to training data.
2 Preliminaries
- A retrieval task pairs a corpus and query distribution with query-specific gold documents, and seeks a retrieval rule with high expected recall.A retrieval rule maps each query to a returned document set.Source: §2 · p. 3
- In single-vector retrieval, documents are embedded offline in a frozen index, while a query encoder maps each query to a vector and ranks documents by inner product.The retriever returns the k documents with the largest scores.Source: §2 · p. 3
- The statistical-query model gives learners aggregate-statistic access to training examples; its oracle returns an estimate of a queried expectation within tolerance.The oracle may answer adversarially within that tolerance, and lower bounds cover several algorithmic approaches under stated conditions.Source: §2 · p. 3
3 Beyond Geometric Limitations
The section reframes geometric capacity as the best recall achievable by a single-vector query encoder on a frozen index, then estimates this capacity and compares it with learned encoders on retrieval benchmarks. Across most tasks, the index can support high recall, but learned encoders often fall short, with training-to-test gaps also evident.
3 Beyond Geometric Limitations
- The section’s capacity measure asks how much recall a single-vector query encoder can achieve for a query distribution on a frozen document index.This contrasts with prior work focused on the minimum dimension needed to realize every document subset of size k.Source: §3 · p. 4
3.1 Capacity lower bounds via ranking SVM
- Per-query ranking SVM finds query vectors that rank gold documents above non-gold documents; their achieved recall gives a lower bound on the index’s best possible recall.The method solves the ranking SVM for each query and averages the recall of the highest-scoring |G(q)| documents.Source: §3.1 · p. 4
3.2 Experiments
- The evaluation covers LIMIT, reasoning-intensive BRIGHT, and seven BEIR categories, comparing DistilBERT and Qwen3-Embedding-4B with BM25 and GTE-ModernColBERT.The geometric-capacity ceiling applies to single-vector retrievers.Source: §3.2 · p. 5
3.2.1 Results
- Outside BEIR trec-covid, both document embedding models support 95%+ expected recall on nearly all tasks, while learned single-vector encoders rarely exceed 50% average recall and often fall below 25% on evaluation queries.The comparison is between the geometric-capacity lower bound and pre-trained or fine-tuned single-vector encoders.Source: §3.2.1 · p. 5, Figure 1 · p. 6
- On BRIGHT, fine-tuned DistilBERT and Qwen3-Embedding-4B average 0.957 and 0.982 train recall, versus 0.148 and 0.245 on held-out queries.Increasing the returned set to k = 100 still leaves single-vector recall below the geometric-capacity lower bound.Source: Figure 2 · p. 6, Figure 3 · p. 7, §3.2.1 · p. 7
- On LIMIT, Qwen3-Embedding-4B reaches only 0.068 held-out recall despite perfect training fit, while fine-tuned GTE-ModernColBERT reaches 1.000/0.998 train/test recall.The LIMIT queries draw gold sets from a shared pool of 46 documents, so every gold document appears during training.Source: §3.2.1 · p. 7
4 Computational Barriers in the SQ Model
The section constructs a retrieval task with perfect geometric realizability but computationally hard query-encoder learning in the statistical-query model. Its main lower bound requires exponentially many statistical queries to achieve recall above the random baseline.
4.1 Retrieval construction
- Queries are uniform binary strings, and intent A maps each query q to center Aq, whose bits are parities of selected query keywords.The gold set contains documents whose codes are within Hamming radius ρ of that center.Source: §4.1 · p. 8
- Training examples provide queries paired with their full gold document sets, a strong-supervision setting that the paper notes is harder than partial feedback such as clicks.Source: §4.1 · p. 9
4.2 Perfect geometric realizability
- Every intent admits perfect top-k recall through a polynomial-size, one-hidden-layer ReLU query encoder.The resulting top-k set consists of the k documents closest to Aq in Hamming distance.Source: §4.2 · p. 9
4.3 SQ-hardness
- For inverse-polynomial tolerance and target advantage, every SQ learner needs 2^Ω(P) queries to achieve recall at least k/n + ε for every intent with constant success probability.The lower bound applies to the constructed family of intents.Source: §4.3 · pp. 9–10
- A probabilistic construction yields an exponentially large family of intents whose pairwise matrix differences have full rank with probability at least 1/2.The family is built from independently sampled binary matrices.Source: §4.3 · pp. 9–10
- The construction makes beating k/n recall require narrowing the hidden intent to a small candidate set, while statistical queries reveal information about only a limited number of intents.The proof counts how many intents each query can rule out.Source: §4.3 · pp. 9–10
5 Conclusion
The paper concludes that learned query encoders may fail to exploit a frozen index’s geometric capacity, supported by empirical benchmark evidence and a theoretical hardness result.
5 Conclusion
- The study finds that high-quality query-encoder learning can be a substantial barrier even when the frozen document index’s geometry is not restrictive.The authors support this conclusion with real-world encoder and benchmark experiments using ranking-SVM to gauge geometric capacity, and a computationally hard-to-learn task in the statistical query model.Source: §5 · p. 11
AI use statement
- The authors used Anthropic’s Opus 5 and OpenAI’s GPT 5.6 Sol for coding, literature search, proof work, and writing, while retaining responsibility for the manuscript, proofs, and code.Source: AI use statement · p. 12
A Limitations
The empirical gap may partly reflect the fine-tuning setup and does not rule out better encoders that were not tested or discovered. The theoretical hardness result is limited to statistical-query learners and a contrived task that may not resemble real applications.
Empirical results
- The observed empirical gap is partly an artifact of the fine-tuning setup and does not preclude better encoders that remain untested or undiscovered.The authors also note that their geometric-capacity bounds do not immediately extend to multi-vector retrieval, which they leave for future work.Source: A Limitations · p. 14
- The ranking SVM bounds on geometric capacity do not immediately extend to multi-vector models, and directly optimizing multi-vector embeddings remains future work.Source: A Limitations · p. 14
Theoretical results
- The hardness result applies to statistical-query learning, and its proof task may not resemble retrieval tasks in real applications.Source: A Limitations · p. 14
B Omitted Proofs
The omitted proof represents the query-to-embedding model with a one-hidden-layer ReLU network by using a spline that realizes parity. The spline alternates between 1 and -1 at consecutive integers, allowing each binary-cube embedding coordinate to encode a keyword parity.
B.1 Perfect realizability
- The embedding model q 7→Aq is represented by a simple ReLU network with one hidden layer.Source: §B.1 · p. 14
- At integer inputs, the ReLU spline pP alternates between 1 and -1, realizing parity as (−1)^t.Source: §B.1 · p. 14
- Between consecutive integers, the spline is linear with alternating slopes of 2 and −2.Source: §B.1 · p. 14
- For the binary-cube index, each coordinate of h(Aq) is a keyword parity, so the construction gives width dP directly.Source: §B.1 · p. 14
B.2 Recovery from individual samples
Individual training samples suffice to recover the hidden intent matrix in polynomial time. Because the gold set identifies its center, recovering that matrix yields an encoder with recall one.
B.2 Recovery from individual samples
- The gold set uniquely identifies its center Aq, reducing recovery to reconstructing A from matrix-vector samples (q, Aq).Source: §B.2 · p. 15
- The sample equations determine each row of A once the query vectors span F_2^P.Source: §B.2 · p. 15
- With T = 2P samples, Gaussian elimination recovers all d rows of A in O(P^3) time with probability at least 1 − 2^-P.Source: §B.2 · p. 15
- Recovering A yields an encoder with recall one, so the computational barrier is specific to statistical access rather than individual samples.Source: §B.2 · p. 15
B.3 SQ Hardness
The proof compares learning under intent-specific distributions with a null distribution, using statistical queries and bounds on how many intents a query can distinguish. It also establishes that the random-retrieval baseline is k/n under the null distribution.
B.3 SQ Hardness
- With probability at least 1/2, every pairwise difference between intent matrices has full rank.Source: §B.3 · p. 15
- The lower bound is proved even with the stronger observation (q, y) where y = Aq, so it also holds for gold-set supervision.A statistical query on (q, G) can be simulated using (q, y) with the same expectation and tolerance.Source: §B.3 · p. 15
- Bessel's inequality bounds the number of intents on which a fixed query can have advantage greater than τ.Source: §B.3 · p. 16
- Under N0, each document returned by a fixed rule lies in the gold set with probability k/n, the random-retrieval baseline.Source: §B.3 · p. 16
C Additional Experimental Details
The appendix specifies benchmark splits, encoder configurations and fine-tuning settings, and the compute environment.
C.1 Setup
- Table 1 lists encoder configurations and gives the default Qwen3 query prompt as an instruction followed by “Query:”.Source: Table 1 · p. 17
- Benchmark reporting includes category, document totals, train/evaluation counts, and mean |G(q)|; all datasets except fiqa, nfcorpus, and scifact use a 70/30 query split.Source: §C.1 · pp. 16–17
BRIGHT
- BRIGHT fine-tuning uses LoRA with r = 16, α = 32, dropout 0.05, AdamW, a cosine schedule, 100 warmup steps, weight decay 0.01, learning rate 10^-4, and 3000 steps.The training loss is multi-positive InfoNCE with temperature 0.05; BM25 uses Okapi parameters k1 = 0.9 and b = 0.4.Source: BRIGHT · p. 17
- BRIGHT experiments ran on an NVIDIA HGX H200 node with 8 GPUs, 2 Intel Xeon Platinum 8470 CPUs, and 1T of RAM.Source: BRIGHT · p. 18
C.2 Full results
The full-results tables cover ranking-SVM geometric-capacity lower bounds, pretrained recall, and fine-tuned recall on training and evaluation queries.
C.2 Full results
- Table 2 reports ranking-SVM geometric-capacity lower bounds by category for indexes embedded with DistilBERT and Qwen3-Embedding-4B.Source: Table 2 · p. 18, §C.2 · p. 18
- Table 3 reports expected recall@|G(q)| for pretrained models without fine-tuning, covering the four out-of-the-box retrieval methods.Source: §C.2 · p. 18, Table 3 · p. 19
- Table 4 reports expected recall@|G(q)| after query-side fine-tuning for single- and multi-vector models on training and evaluation queries.Source: §C.2 · p. 18, Table 4 · p. 19