The Voronoi Bottleneck: Capacity-Aware Dense Retrieval for Product Search
For practitioners building dense retrieval systems for product search, this work provides a theoretical framework and a practical training objective to improve retrieval quality without inference overhead.
The paper identifies a fundamental capacity limit (Voronoi Bottleneck) in dense retrieval and introduces a diagnostic (CUS) that predicts retrieval failures with AUC > 0.8. It also proposes DART training (AT-DW-InfoNCE) that improves Recall@100 by +1.9 over InfoNCE on a synthetic product-search corpus.
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.