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.
Figures & tables
Figure 1: Measured gap between geometric capacity of the document index and the expected recall of single-vector query encoders.
Figure 2: Expected recall@ k for k∈{10,20,50,100} averaged over the datasets in each benchmark. On LIMIT, lexical and fine-tuned ColBERT-style multi-vector retrieval are near-saturated at every cutoff while the single-vector encoders remain far below even at k=100 .
Figure 3: Expected recall on training vs. held-out queries for each fine-tuned retrieval model. Points in the lower right reflect near-perfect recall on training data but limited generalization.
Figure 4: A simple intent. Each document code bit is the parity of a fixed pair of keywords. The two queries share waterproof and only differ in a single term, yet the resulting retrieval codes are dramatically different.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
DistilBERT
Qwen3-Embedding-4B
GTE-ModernColBERT
Checkpoint
sentence-transformers/
Qwen/
lightonai/
msmarco-distilbert-
Qwen3-Embedding-4B
GTE-ModernColBERT-
base-v3
v1
Representation
single-vector
single-vector
multi-vector (MaxSim)
Pooling
mean
last token
none (per token)
Truncation
350 tok.
512 tok.
300 tok. (queries 32)
Appendix
Table 1: Encoder configurations. The default Qwen3 query prompt is "Instruct: Given a search query, retrieve relevant passages that answer the query\nQuery: " .
DistilBERT
Qwen3-Embedding-4B
Category
train
eval
train
eval
LIMIT
limit
1.000
1.000
1.000
1.000
BRIGHT
biology
0.979
0.962
0.980
0.954
earth science
0.980
0.997
0.985
0.999
economics
0.983
1.000
0.984
0.999
psychology
0.999
0.996
0.995
0.990
Appendix
Table 2: Geometric capacity by category, as measured by the ranking SVM.
Category
BM25
DistilBERT
Qwen3-Embedding-4B
GTE-ModernColBERT
LIMIT
limit
0.917
0.002
0.015
0.525
BRIGHT
biology
0.156
0.016
0.073
0.078
earth science
0.201
0.078
0.233
0.168
economics
0.186
0.074
0.179
0.143
psychology
0.087
0.073
0.210
0.102
robotics
0.046
0.045
0.038
0.104
Appendix
Table 3: Expected recall@ ∣G(q)∣ of pre-trained models, without fine-tuning.
DistilBERT
Qwen3-Embedding-4B
GTE-ModernColBERT
Category
train
eval
train
eval
train
eval
LIMIT
limit
0.439
0.045
1.000
0.068
1.000
0.998
BRIGHT
biology
0.972
0.105
0.972
0.189
0.975
0.240
earth science
0.973
0.178
0.982
0.274
0.910
0.243
economics
0.984
0.103
0.995
0.276
0.971
0.197
psychology
0.992
0.021
0.996
0.151
0.970
0.119
Appendix
Table 4: Expected recall@ ∣G(q)∣ after query-side fine-tuning.
Recent works have highlighted the expressive limitations of embedding based retrieval models through both theoretical analyses and challenging benchmarks such as LIMIT. While multi-vector embeddings consistently outperform single-vector embeddings, the precise representational gap between them remains poorly understood. In this work, following Jayaram's work, we provide the first explicit family of query and document sets, together with their relevance matrices, for which single-vector embeddings that rank all relevant documents above irrelevant ones require exponential size, whereas polynomial-size multi-vector embeddings suffice. Our result establishes an exponential separation between the expressive power of single-vector and multi-vector embeddings for the task of ranking of documents as opposed to approximating numerical scores as in the work of Jayaram. Motivated by our theoretical construction, we introduce ANDOR, a new retrieval benchmark that naturally instantiates these hard examples. We show that state-of-the-art single-vector embedding models perform poorly on ANDOR in the zero-shot setting and exhibit only marginal improvements after fine-tuning, highlighting the inherent difficulty of the benchmark compared to prior work. In contrast, multi-vector models consistently outperform their single-vector counterparts and improve substantially with fine-tuning, closely aligning with our theoretical predictions.
We propose Latent Terms, a method revealing that models trained for dense retrieval, whether single- or multi-vector, learn representations that can trivially be decomposed into retrieval-ready sparse features. When trained on frozen retrievers, Sparse Autoencoders without any retrieval-specific adjustments extract a latent vocabulary with approximately Zipfian collection statistics, directly suitable for classical sparse retrieval scoring via BM25. This approach enables sparse retrieval while requiring no learned expansion objective or sparse retrieval supervision whatsoever, and can be readily applied to any dense retriever. Latent Terms is able to match or outperform single-vector scoring methods from its own base model as well as comparable SPLADE variants. In addition, it substantially outperforms its base model on LIMIT, a task specifically designed to highlight the failures of single-vector retrieval. Overall, our results highlight that neural retrievers contain more expressive and indexable structure than their default scoring functions expose, but that other methods can nonetheless be leveraged.
Benjamin Clavié, Sean Lee, Aamir Shakir +1
Mixedbread AI · National Institute of Informatics (NII) · University of Tsukuba
Dense embedding retrieval compresses all relevance information into a single inner product, imposing a fundamental geometric limit -- the Voronoi Bottleneck -- on the number of query-document relevance patterns expressible at fixed embedding dimension (d). We make three contributions. (1) Unified capacity theory. We prove that Voronoi complexity and sign-rank are equivalent for top-1 retrieval, yielding tight dimension bounds and a computable diagnostic, the Capacity Utilization Score (CUS), that predicts per-query retrieval failure with AUC (> 0.8) without relevance labels. (2) Diagnosis. CUS identifies two capacity regimes -- moderate ((δ\gtrsim 1)), where density-aware training yields measurable gains, and vacuous ((δ\ll 1)), where it does not -- giving practitioners an a priori check before investing in retraining. (3) DART training. We introduce AT-DW-InfoNCE, an Adaptive-Temperature Density-Weighted contrastive objective with formally derived optimal weighting (α^* = 2.0). On a 100K-query synthetic product-search corpus with controlled relevance structure, DART improves +1.9 Recall@100 over a same-data InfoNCE baseline ((84.9 \pm 0.0) vs. (83.0 \pm 0.3); 8 seeds, (p < 0.001)), outperforming focal loss and temperature-schedule alternatives. DART requires zero inference-time overhead -- it is a drop-in training objective that improves any dual-encoder system.
Charith Chandra Sai Balne, Rithwik Maramraju, Siddharth Pratap Singh +4
Walmart Global Tech USA · Walmart Global Tech2026 USA