Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy
Anders Wikum, Nina Mishra, Amin Saberi, Tal Wagner
cs.IR, cs.LG
2026-10-02
A ranking-SVM probe shows document indexes support 95%+ recall on most of 20 benchmarks, yet fine-tuned query encoders often stay below 25%; learning them is also proven SQ-hard, requiring 2^Ω(P) queries.
Production vector retrieval runs on the bi-encoder architecture: documents are embedded offline into a frozen, reusable index, and at query time an encoder maps the query into the same space so the system can return the top-k by inner product. Two things decide whether this works: the document geometry has to admit query vectors that put the right documents on top, and the query encoder has to be learnable at all. A year of theory attacked the first half, proving dimension lower bounds for realizing every top-k subset, and the LIMIT dataset was built to expose exactly that limit. Follow-up measurements kept finding the bounds don't bite on real data. This paper inverts the question: given a frozen index, what is the best recall it could support, and how close do learned query encoders actually get?
Half empirical, half theory.
The empirical half needs a way to measure geometric capacity. For each query, directly optimize a query vector in the embedding space that ranks every gold document above every non-gold one. That is precisely the convex feasibility problem behind ranking SVM: find a hyperplane separating all gold-minus-non-gold difference vectors. Solving it with Joachims' cutting-plane method avoids materializing the quadratic number of pairwise constraints, and corpora up to about 500k documents finish in 2-4 hours. The resulting recall is a lower bound on capacity, and a zero-slack solution certifies the gold set is perfectly retrievable.
The theory half constructs a retrieval task where queries are P-bit keyword indicators, the corpus is n = 2^d documents (d = Θ(log P)) embedded as hypercube vertices, and a hidden intent matrix A sends each query to a gold set: the Hamming ball of radius ρ around the code Aq. Each bit of Aq is a parity of query keywords, so two queries differing in a single term can have disjoint gold sets.
Twenty datasets: 12 BRIGHT categories, 7 BEIR categories, and LIMIT, with single-vector encoders DistilBERT (768-dim) and Qwen3-Embedding-4B (2560-dim), plus BM25 and multi-vector GTE-ModernColBERT as reference points. Fine-tuning used LoRA (rank 16) with an InfoNCE contrastive loss for 3,000 steps.
| Setting | Metric | Result |
| All datasets except trec-covid | ranking-SVM capacity lower bound | 95%+ expected recall |
| BRIGHT, fine-tuned DistilBERT | train / held-out recall | 0.957 / 0.148 |
| BRIGHT, fine-tuned Qwen3-4B | train / held-out recall | 0.982 / 0.245 |
| LIMIT, fine-tuned Qwen3-4B | train / held-out recall | 1.0 / 0.068 |
| LIMIT, fine-tuned GTE-ModernColBERT | train / held-out recall | 1.000 / 0.998 |
Geometric capacity is rarely the limit. Outside BEIR's trec-covid (an outlier with median gold sets of 529), the ranking-SVM probe supports 95%+ expected recall on nearly every task, even over DistilBERT embeddings. Learned query encoders, pre-trained or fine-tuned, rarely exceed 50% average recall and often land under 25% on held-out queries. Retrieving k=100 documents still leaves the single-vector models below the ceiling, while BM25 and the ColBERT-style model are near-saturated on LIMIT at every cutoff.
The failure mode is generalization, not fitting. LIMIT isolates the architecture's role: all 1,000 queries draw gold sets from a shared pool of 46 documents, so every gold document appears in training, yet fine-tuned Qwen3-Embedding-4B reaches only 0.068 held-out recall while GTE-ModernColBERT scores 0.998.
On the theory side, a perfect-recall encoder exists for every intent and fits in a one-hidden-layer ReLU network, yet any SQ learner needs 2^Ω(P) statistical queries to beat the random baseline k/n by an inverse-polynomial margin. The intent family has size 2^Ω(P), and any two intents map a random query to the same center at exactly chance rate, so aggregate statistics cannot separate them.
For RAG and retrieval engineers, this reorders the blame. The index side already sits near its ceiling on these benchmarks, so upgrading document encoders or shaving quantization error may buy little; the bottleneck is on the query side. The 0.068 versus 0.998 gap on LIMIT is the sharpest evidence that late interaction's term-level matching dodges the difficulty of compressing a query into a single vector.
The theory offers a candidate explanation for stubborn fine-tuning: tasks exist where the perfect encoder is small and representable, but gradient-style learning cannot find it statistically. It is a worst-case existence result, not a claim about real benchmarks, and it establishes query-encoder learnability as a research object on par with geometric capacity.
The authors park their own limitations discussion in an appendix not included in this extraction. Checkable boundaries from the main text: capacity comes from per-query optimization that consumes gold labels, an oracle-style bound with no claim that a single shared encoder attains it; the fine-tuning protocol is fixed (LoRA rank 16, 3,000 steps, final checkpoint taken for lack of validation data), leaving stronger regimes untested; BEIR coverage is 7 categories for compute and licensing reasons. The hardness construction is worst-case parity, proving that hard tasks exist without showing that BRIGHT or BEIR gaps come from this mechanism. And since BRIGHT relevance judgments deliberately avoid keyword overlap, annotation noise may contribute to the low held-out recall, which the paper does not decompose.