The Voronoi Bottleneck: Capacity-Aware Dense Retrieval for Product Search
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 ...
| Authors | Charith Chandra Sai Balne, Rithwik Maramraju, Siddharth Pratap Singh et al. |
|---|---|
| Primary category | cs.IR |
| Published | 9 June 2026 |
| Last updated at source | 9 June 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.