acceptodds
Under review as a conference paper at ICLR 2027

Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy

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- answer sets of 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 . 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.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
retrieval, encoder, statistic query, SQ model, vector search, nearest neighbor search

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_dbi6OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proves that, given a frozen set of document embeddings, learning the query encoder for a bi-encoder retrieval setup can be computationally hard under the Statistical Query (SQ) model. A few recent works showed that some cases are geometrically impossible, but this work discusses a setting where it is geometrically possible, meaning good embeddings exist (a perfect query encoder exists by construction in the paper's setting), but you simply can't learn them. The SQ model closely approximates mini-batch SGD (Abbe et al., 2021). The paper also includes some experiments to demonstrate the motivation for this problem, showing that we actually do observe cases where query encoders are difficult to train.

Critical strengths

This paper explores a question I've thought about myself, and I was surprised to see they present it in a very clear way. In bi-encoder retrieval, encoding documents is relatively easy to understand; it is essentially a form of information compression. But we actually know very little about how to encode queries. In practice, all we can do is learn from massive retrieval sample data, seeing which queries correspond to which documents, and learn patterns from all those statistics. Therefore, the setting they study is very natural, and they prove that learning query encoders can actually be hard. Furthermore, the setting closely mirror real-world training practices like mini-batch SGD. To a large extent, this work deepens my understanding of how we train embedding models.

Critical weaknesses

None. I don't see any weaknesses here that would make me lean toward rejection. The authors acknowledge some limitations of this work in Appendix A.

Questions for authors

These are just out of curiosity, and overall they won't change my (positive) assessment.

  1. My understanding is that SGD ≈ SQ relies on the batch gradient being an average of the per-sample gradients over i.i.d. samples. In practice, however, in-batch negatives are often used, so the samples are not i.i.d. (i) Could the authors clarify whether Section 3 uses in-batch negatives? (ii) Do you expect the SQ lower bound to extend to contrastive objectives with in-batch negatives?
  2. I'm curious how a negative result can inform practice (in a way that is more understandable to practitioners). Are there any practical tools to diagnose whether we are in the hard regime?
  3. Section 3.2 says all datasets were trained for a fixed 3,000 steps, but they vary in size, e.g., BRIGHT biology only has 72 queries, fiqa has 5,500. So the number of effective epochs is very different? If you have the compute to train them properly, that would be great...
2 comments

We're glad you found the paper interesting, thanks for the thoughtful feedback (and for your patience)! To answer each of your questions:

In-batch negatives and the SQ model. Our experiments in Section 3 use a contrastive loss with full negatives where feasible (up to 200k total documents) and randomly sample 100k documents otherwise. One of the main reasons in-batch negatives are used is to avoid re-embedding many documents in each training iteration when training query and document embedding models simultaneously; training only a query encoder on a frozen document index avoids this efficiency problem.

That being said, our SQ lower-bound argument does extend to contrastive losses with in-batch negatives (for a fixed batch size BB) with minor modifications. At a high level, we instead allow the SQ oracle to return the expectation of any [-1,1]-valued function of BB iid (query, gold-center) samples within tolerance τ\tau. The intent and null distributions over samples become DA⊗BD_A^{\otimes B} and N0⊗B\mathcal{N}_0^{\otimes B}, respectively, and the same orthogonality argument gives a batch version of Lemma 4.5 with nB−1n^B-1 replacing n−1n-1. The downstream effect is that our statistical query lower bound in Lemma 4.4 will have a denominator of nB−1n^B-1. This is polynomial in PP for a fixed batch size, so the number of required statistical queries remains exponential in PP.

Useful diagnostics in practice. As we do in the paper, a useful first step is determining the geometric capacity of the frozen index to diagnose whether poor retrieval performance is a consequence of document geometry or a learning failure on a particular task. Though we have no formal diagnostic for learning failures, one interpretation of our negative result is that it represents a worst-case setting in which semantic similarity between a query and document gives essentially no useful information about relevance to an SQ learner. This may suggest that hard settings are ones where semantic similarity is a poor proxy for query/document relevance, but this is not well understood and stands as an open direction for future work.

Epoch standardization. Thanks for catching this! We initially set a fixed number of steps because some datasets are too data-limited to do proper model selection. We will scale up the number of effective epochs for the larger categories to check whether they benefit from additional training. We don’t expect substantial changes to our overall results, as test recall peaked before the end of the original horizons on all but one category.

Thanks! I'll keep my positive score. Good luck!

Reviewer_cS7yOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates why dense retrieval models underperform relative to the theoretical geometric capacity of their document indices. Using a ranking SVM approach to measure geometric capacity across multiple benchmarks, the authors demonstrate a striking gap: even when document indices support near-perfect retrieval (95%+ geometric capacity), fine-tuned single-vector query encoders frequently plateau below 50% recall and generalize poorly on held-out test data. To explain this, the paper provides a theoretical proof in the Statistical Query (SQ) model showing that learning a query encoder can be computationally hard even when a small, perfect-recall document index exists. However, the audience may expect a more practical analysis of the synergy between semantic geometry and query encoder learning, as well as a more thorough discussion of model scaling impact.

Critical strengths

The paper shifts attention away from geometric constraints (the primary focus of recent literature) toward query-side learnability as a critical bottleneck in dense retrieval. The construction of a hard retrieval task in the SQ model offers formal mathematical insight into why gradient-based or statistical learning can struggle with query encoder learning.

Critical weaknesses
  1. While the paper's SQ-hardness proof establishes a worst-case theoretical barrier, the chosen construction relies on an idealized, discrete hypercube geometry that largely decouples document representation from query learning. In practice, query encoding and document embedding are deeply coupled. If a document embedding space possesses rich, well-structured semantic geometry, it should theoretically provide a continuous "semantic runway" that makes query encoder learning substantially easier. The paper would be strengthened by discussing how the quality and continuity of real-world document embeddings mediate or alleviate this computational hardness in practice.

  2. The empirical evaluation is restricted to relatively modest or mid-sized models: DistilBERT and Qwen3-Embedding-4B. While Qwen3-4B consistently outperforms DistilBERT, the evaluation leaves open a crucial question regarding model scale. Given the rapid evolution of foundation models, the authors should address whether scaling model capacity (e.g., to 7B, 30B, or larger models) can further bridge the train-test generalization gap, or if the limitation is fundamentally structural.

Questions for authors

Does scaling help bypass the single-vector compression trap, or does the single-vector bottleneck persist regardless of parameter count?

1 comment

Thanks for your feedback and suggestions! We agree that including a discussion about how the quality of semantic geometry can affect learning will strengthen the paper and help to contextualize our worst-case construction (it will be integrated into the introduction and start of Section 4 in the camera-ready version). To answer both points:

The motivation for this paper—and the broader line of research on limits of vector search—is to study the performance of vector search on the types of complex retrieval problems it is increasingly being applied to in practice. The fundamental difference between a simple application like semantic search (where vector search excels) and more complex retrieval tasks is that query/document relevance need not be a smooth function of semantic similarity in general (for example, retrieving the documents that answer a question may require reasoning like in BRIGHT). This makes for a more challenging learning landscape. We see our theoretical construction as representing a worst-case setting in which semantic similarity gives essentially no useful relevance information to an SQ-learner, though reality often sits somewhere between and is dependent on the retrieval task and inductive bias of the embedding model. Understanding the characteristics underlying this interaction is an under-explored area that we hope to steer future research toward.

Regarding model size, it’s uncommon to see large 10B+ parameter embedding models used in production vector search systems due to latency constraints on inference (often milliseconds). There is some evidence in the literature that scaling models can lead to performance improvements at a fixed dimension (see, e.g. “Large Dual Encoders Are Generalizable Retrievers" by Ni et al. ‘22). The fact that DistilBERT embeddings already support near-perfect retrieval in our experiments suggests that this parameter scaling may produce semantic embeddings that are more amenable to learning generalizable retrieval rules, though this is not well understood and stands as an interesting topic for future research.

Reviewer_m9Q9OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper shows that document embeddings often support much better retrieval. It measures this gap and gives a theoretical example where even a small, accurate query encoder can be hard to learn.

Critical strengths

The experiments expose substantial unused retrieval capacity, making a strong case for focusing on query encoders. The SQ lower bound adds theoretical weight by showing that even a small, perfect encoder can be hard to learn.

Critical weaknesses

Many experiments use small training sets and a fixed LoRA method. Stronger training controls are needed to separate learning difficulty from limited data or training choices.

Questions for authors

Can the results separate query-encoding difficulty from limited data and LoRA?

1 comment

Thanks for the support and for bringing attention to training controls. To better isolate learning difficulty, we have run ablations to test both the influence of small training sets (common in QA benchmarks since eliciting human-labeled question/answer pairs is expensive) and the LoRA pipeline. We will add both ablations to the appendix with a brief description and reference after the main experimental results in Section 3.2.1.

Sensitivity to training set size. For the first, we fine-tune DistilBERT using our LoRA pipeline on 5 random subsets of 25%, 50%, and 75% of the original training set (evaluation set fixed) and measure evaluation recall across each of the 15 resulting models. We find that in data-limited categories with at most 1000 total samples, training recall is often saturated by each model while evaluation recall is low-variance and doesn’t show a sizable upward trend as the size of the training set increases. Extrapolating this behavior to larger training sets is purely speculative, but it seems to suggest that the learning difficulty we observe is not only a relic of data limitations. The following table gives evaluation recall (mean + std) at each training set size across the 5 random training subsets for each benchmark, with NN denoting the number of queries in the full (100%) training set:

BenchmarkNGeometric capacity25%50%75%100%
Touché-20203486.09.3 ± 1.512.2 ± 0.613.0 ± 1.013.4
TREC-COVID3549.314.4 ± 2.418.8 ± 1.321.2 ± 1.123.1
TheoremQA theorems53100.08.3 ± 5.516.2 ± 2.217.1 ± 2.915.9
Psychology7099.64.7 ± 2.55.5 ± 3.62.8 ± 1.72.3
Robotics7096.84.2 ± 2.14.7 ± 1.94.8 ± 1.03.9
Biology7296.28.0 ± 3.29.2 ± 3.010.4 ± 2.79.4
Economics72100.09.9 ± 0.312.8 ± 2.411.0 ± 2.69.6
Sustainable living7595.75.3 ± 1.76.5 ± 1.78.7 ± 2.76.4
AoPS77100.010.1 ± 1.212.2 ± 3.412.4 ± 1.813.7
Pony78100.073.9 ± 0.973.0 ± 1.372.2 ± 0.973.1
Earth science8199.717.1 ± 3.119.0 ± 3.018.2 ± 3.916.1
Stack Overflow8183.31.6 ± 1.42.3 ± 1.82.3 ± 1.33.7
LeetCode99100.05.0 ± 1.74.5 ± 2.63.9 ± 1.15.5
TheoremQA questions13599.67.0 ± 2.17.4 ± 2.210.9 ± 1.710.7

LoRA vs full fine-tuning. Second, we fully fine-tuned DistilBERT on each of the QA categories to see if our recall gaps could be explained by limitations of LoRA. Previous work has shown that LoRA and full fine-tuning of Qwen3-Embedding-4B for query encoding yield similar downstream retrieval quality (Jain et al. ‘26), and our findings are similar. Full DistilBERT fine-tuning yields a 0.5% mean and 1% median improvement for held-out recall over LoRA fine-tuning, which is only a small fraction of the observed gap between geometric capacity and achieved recall on our benchmarks. The following table gives evaluation recall (mean + std across two training runs) for LoRA and full fine-tuned DistilBERT query encoders under the same step size:

BenchmarkGeometric capacityLoRA recallFull FT recall
ArguAna96.45.7 ± 0.34.3 ± 0.3
FiQA99.618.1 ± 0.014.1 ± 0.2
NFCorpus97.515.6 ± 0.219.2 ± 0.1
Quora98.975.4 ± 0.174.3 ± 0.2
SCIDOCS98.08.4 ± 0.69.0 ± 0.4
SciFact100.066.3 ± 0.369.4 ± 0.2
TREC-COVID49.323.1 ± 0.014.7 ± 0.1
Touché-202086.013.6 ± 0.97.6 ± 0.1
AoPS100.014.7 ± 0.117.6 ± 0.0
Biology96.210.1 ± 0.612.0 ± 0.2
Earth science99.716.1 ± 2.315.2 ± 1.0
Economics100.010.4 ± 0.111.2 ± 0.2
LeetCode100.06.4 ± 0.87.4 ± 0.5
Pony100.073.9 ± 0.276.4 ± 0.1
Psychology99.62.3 ± 0.46.7 ± 2.4
Robotics96.82.9 ± 1.11.1 ± 0.0
Stack Overflow83.33.1 ± 0.03.1 ± 0.0
Sustainable living95.75.3 ± 2.38.9 ± 0.2
TheoremQA questions99.610.6 ± 0.818.1 ± 0.0
TheoremQA theorems100.015.4 ± 0.817.0 ± 0.0
LIMIT100.04.1 ± 0.65.3 ± 0.0
  • Prateek Jain, Shabari S Nair, Ritesh Goru, Prakhar Agarwal, Ajay Yadav, Yoga Sri Varshan Varadharajan, & Constantine Caramanis. (2026). Succeeding at Scale: Enterprise Retrieval Benchmark Construction and Index-Preserving Query Adaptation for Multi-Tenant Search.
Reviewer_hVeGOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the gap between the retrieval potential of document embeddings and a query encoder’s ability to exploit that potential. Through experiments on real-world data and theoretical constructions under the SQ model, the authors show that even when document embeddings support high-recall retrieval, training an effective query encoder can remain challenging.

Critical strengths
  1. The authors use Ranking SVM’s recall as a benchmark for comparison with other models, providing a reference point for evaluating their performance.

  2. The authors find that document embeddings may inherently support high-recall retrieval, while training a query encoder that fully exploits this potential remains challenging. They support this finding with experiments on real-world data and theoretical constructions under the SQ model.

Critical weaknesses
  1. The authors use a 70/30 train–test split, but model performance also depends on the size and composition of the training set. Poor test performance may stem from insufficient training data or characteristics of the training data. The current experiments do not clearly distinguish among these possible explanations.

  2. The experiments show that the tested models fail to reach Ranking SVM’s reference recall on the selected datasets and under the specified training settings. However, this result does not establish that other models or training methods would also fail to achieve effective retrieval. The authors should limit their empirical conclusions to the models and settings evaluated, or include experiments with additional models and training methods to strengthen the generalizability of their findings.

  3. In Figure 2, the same multi-vector model performs noticeably differently across LIMIT, BRIGHT, and BEIR, indicating that retrieval performance depends substantially on the task and dataset. The current experiments demonstrate substantial gaps for the tested single-vector models on several tasks, but are insufficient to establish that models generally struggle to learn effective retrieval strategies. The authors should further clarify the scope of their conclusions.

Questions for authors

Please refer to the points raised in the Weaknesses section. My main concerns are the three points raised in the Weaknesses section. If these concerns are satisfactorily addressed, I would be willing to reconsider my final score.

2 comments

Thank you for your thoughtful feedback! Addressing each of the three concerns you raised:

Effects of training set composition. Realistic QA benchmarks like the ones we consider tend to be small because obtaining labeled training examples requires significant human effort. To isolate the effects of the particular scale and composition of our training sets, we ran an ablation in which we fine-tune DistilBERT on 5 subsets of 25%, 50%, and 75% of the original training set (fixed evaluation set) and measure evaluation recall across each of the 15 resulting models. We find that on our datasets with fewer than 1000 total samples, training recall is often saturated by each model while evaluation recall is low-variance and has only a small upward trend. This suggests that the poor evaluation recall we observe empirically is not primarily a relic of our training sets. See the table below for evaluation recall (mean + std) for each training set size across benchmarks, where NN is the full number of training queries (100%). We will add this ablation to the appendix with a brief description and reference after the main experimental results in Section 3.2.1.

BenchmarkNGeometric capacity25%50%75%100%
Touché-20203486.09.3 ± 1.512.2 ± 0.613.0 ± 1.013.4
TREC-COVID3549.314.4 ± 2.418.8 ± 1.321.2 ± 1.123.1
TheoremQA theorems53100.08.3 ± 5.516.2 ± 2.217.1 ± 2.915.9
Psychology7099.64.7 ± 2.55.5 ± 3.62.8 ± 1.72.3
Robotics7096.84.2 ± 2.14.7 ± 1.94.8 ± 1.03.9
Biology7296.28.0 ± 3.29.2 ± 3.010.4 ± 2.79.4
Economics72100.09.9 ± 0.312.8 ± 2.411.0 ± 2.69.6
Sustainable living7595.75.3 ± 1.76.5 ± 1.78.7 ± 2.76.4
AoPS77100.010.1 ± 1.212.2 ± 3.412.4 ± 1.813.7
Pony78100.073.9 ± 0.973.0 ± 1.372.2 ± 0.973.1
Earth science8199.717.1 ± 3.119.0 ± 3.018.2 ± 3.916.1
Stack Overflow8183.31.6 ± 1.42.3 ± 1.82.3 ± 1.33.7
LeetCode99100.05.0 ± 1.74.5 ± 2.63.9 ± 1.15.5
TheoremQA questions13599.67.0 ± 2.17.4 ± 2.210.9 ± 1.710.7

Scope. We agree! Our results cover a number of benchmarks and training methods used in practice, but we can make no overarching claim about all datasets or query-encoder training methods. We call attention to this in lines 55-57 of our summary of contributions (“the tested query encoders… mostly fail”) and as an explicit statement in lines 589-593 of our Limitations section: “The empirical gap we demonstrate on real-world encoders and benchmarks is, in some part, an artifact of our specific fine-tuning setup; it does not preclude the existence of better query encoders which might have not been tested or not yet discovered.” We’re happy to add additional qualifiers if there is any ambiguity (e.g., “retrieval quality of single-vector query encoders” -> “retrieval quality of our single-vector query encoders” in the abstract). For context, we chose this particular LoRA fine-tuning pipeline because is an increasingly popular way to adapt pre-trained semantic embedding models to particular retrieval tasks in practice (e.g., Jain et al. '26), and LoRA-based contrastive training has been used to build state-of-the-art embedding models such as NV-Embed-v2 (Lee et al. ’24).

Task/model alignment. It is true that retrieval performance varies greatly based on the retrieval task and inductive bias of the retrieval model considered. As we note in lines 295-301, the LIMIT benchmark is constructed in such a way that keyword lookup achieves perfect recall with proper tokenization. This is a challenging setting empirically for single-vector retrievers (see the original LIMIT paper for more detailed experiments), but multi-vector models perform well because their MaxSim scoring function effectively “matches” each query token with the most relevant token in each document. Relevance in BEIR or BRIGHT, in contrast, does not share an obvious structural alignment with MaxSim scoring. This question of model/task alignment has been studied in some settings (see, e.g. Xu et al. ICLR ‘20), and we will add a note that further exploring this question in the context of retrieval is an interesting direction for future research.

  • Jain, P., Nair, S. S., Goru, R., Agarwal, P., Yadav, A., Varadharajan, Y. S. V., & Caramanis, C. (2026). Succeeding at Scale: Enterprise Retrieval Benchmark Construction and Index-Preserving Query Adaptation for Multi-Tenant Search. arXiv preprint.
  • Lee, C., Roy, R., Xu, M., Raiman, J., Shoeybi, M., Catanzaro, B., & Ping, W. (2025). NV-Embed: Improved Techniques for Training LLMs as Generalist Embedding Models. ICLR.
  • Xu, K., Li, J., Zhang, M., Du, S. S., Kawarabayashi, K., & Jegelka, S. (2020). What Can Neural Networks Reason About? ICLR..

Thank you for your response. My questions have been addressed thoroughly, and I will submit my final score to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.