AdaWidth is introduced, which adapts the number of evaluated dimensions to each query within a shared prefix representation, and derives a prefix sufficiency analysis showing that the required number of dimensions is set by the competing documents at the retrieval cutoff.
Abstract
High-dimensional embeddings are central to dense retrieval, but not all of these dimensions need to be evaluated at retrieval time. Existing methods reduce dimensions in two ways: truncating the same leading dimensions for every query, or masking a different subset for each query while still storing and accessing the full embedding. Yet queries within a single task differ widely in the number of dimensions they need for their rankings to stabilize. We introduce AdaWidth, which adapts the number of evaluated dimensions to each query within a shared prefix representation. An orthogonal prefix adapter applies a single learned rotation to queries and documents alike, concentrating discriminative signal in leading coordinates while leaving every full width inner product unchanged. A lightweight router then reads order statistics off the ranking a query has already produced, and evaluates more dimensions only for the queries whose top results would change. We further derive a prefix sufficiency analysis showing that the required number of dimensions is set by the competing documents at the retrieval cutoff: it grows logarithmically with corpus size, decreases logarithmically with retrieval depth, and remains heavy-tailed across queries. Across six retrieval tasks and five frozen encoders, AdaWidth matches the NDCG@10 of state-of-the-art dimensionality reduction using 55% to 84% fewer dimensions per query.
This work provides 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.
Mihir Agarwal, Viraj Agrawal, Sabyasachi Basu et al.· 2 citations
This work introduces Matryoshka Hash Representations (MHR), a two-stage procedure that separates full-width training from prefix organization and strengthens two common pipelines: shortlisting candidates for full-precision reranking, and pruning a low-storage graph index such as LEANN.
Multi-tenant dense retrieval systems increasingly employ shared compressed indexes where individual tenants adapt embeddings via fine-tuning (e.g., LoRA). While query-side projection adapters bridge the resulting embedding mismatch, a critical design choice remains for the optional reranking stage: should distances be...
Jun Woo Chung, Wei-Jie Zhao· Proceedings of the 20th ACM...· 0 citations
DiBud is presented, which takes an access budget directly as input and incrementally certifies and returns an exact prefix of the RRF ranking over the full lists, and investigates long-tailed costs for completing exact Top-20.
This work presents DESA (Dense Expansion and Sparse Anchoring), which shares generated references across channels but specializes their integration, which improves nDCG@10 and Recall@20 over the unexpanded query and reduces dense and sparse replay stopping depths.
Filtered approximate nearest neighbor search, i.e. returning the top-k vectors nearest to a query vector among those satisfying one or more attribute predicates, has become a fundamental operation in modern vector search systems. Graph-based solutions employ beam search to solve a batch of queries in parallel for high...
Farhana Akter Tumpa, Rajiv Gupta· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.