cs.IRJun 9, 2026

The Voronoi Bottleneck: Capacity-Aware Dense Retrieval for Product Search

Authors: Charith Chandra Sai Balne, Rithwik Maramraju, Siddharth Pratap Singh, Rohit Upadhyay, Aditya Singh, Chittaranjan Tripathy, Yogananda Domlur Seetharama

Organizations: Walmart Global Tech USA · Walmart Global Tech2026 USA

Abstract

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.

Explore similar work

CardsList
May 31, 2026cs.IR

Test-Time Training for Zero-Resource Dense Retrieval Reranking

Dense retrievers excel at first-stage candidate generation but lack effective reranking in zero-resource settings. Existing approaches face a fundamental dilemma: cross-encoders deliver strong reranking quality but require costly supervised training and incur high latency, while unsupervised BM25 reranking consistently degrades dense retrieval performance on most of BEIR benchmarks. We propose DART (Dense Adaptive Reranking at Test-time), which resolves this dilemma by adapting the scoring function at inference time. For each query, the top-ranked documents serve as pseudo-positive examples and the bottom-ranked as pseudo-negative examples, providing noisy but readily available supervision to adapt a bilinear scoring matrix WW via a small number of gradient updates. We further introduce a confidence-weighted margin loss and a cross-query momentum buffer that warm-starts adaptation across queries. On six BEIR benchmarks, DART achieves a mean per-dataset relative NDCG@10 gain of +2.1% over the dense retrieval baseline with under 10ms additional latency per query, demonstrating a powerful capability for zero-shot performance enhancement and cross-domain generalization.
Shiyan Liu, Yichen Li
Generative Reasoning Re-RankersRetrieval LayerRerankingCross-EncoderZero-Shot BenchmarkTest-Time Adaptation
AskPDF
May 28, 2026cs.IR

Latent Terms: Dense Retrievers Contain Trivially Extractable BM25-ready Zipfian Vocabularies

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
Retrieval LayerMulti-Hop RetrievalSparse Supervision
AskPDF
Jun 10, 2026cs.IR

What Limits Does Quantization Place on Dense Top-k Retrieval? A Theoretical Study

We establish conditions for embedding a corpus of NN documents as dd-dimensional vectors such that every kk-subset S⊆[N]S \subseteq [N] is realizable as a result of top-kk retrieval by some query vector. Recent work shows that d=O(k)d = O(k) suffices for such embeddings to exist in Rd\mathbb{R}^d, independently of NN. We theoretically prove that this corpus-independent bound is specific to infinite precision. With BB bits per coordinate, perfect top-kk retrieval requires Bd=Ω(kln⁡N)Bd = Ω(k \ln N); thus, at any fixed precision, the dimension must grow at least logarithmically with NN. Specializing to a ℓ2\ell_2-normalized BB-bit uniform scalar quantization model, we also identify a threshold on the precision B∗=O(ln⁡ln⁡N)B^{*} = O(\ln \ln N) below which no dimension suffices, together with two further regimes that bound the feasible (B,d)(B, d) pairs. Our result implies that in practical vector databases and dense retrieval systems where quantization is standard, the embedding dimension and possibly the precision must grow with the corpus size.
Koki Okajima, Tsukasa Yoshida
Vector DatabaseTop-KCalibration-Free Low-Bit Vector QuantizationIntrinsic DimensionalityQuantizationCorpus
AskPDF