Skip to main content
Back to timeline
arXivSource publication:

Hybrid retrieval stops rebuilding per query weight: UniGraph merges neighborhoods from several weights into one graph and lifts QPS 27.6%–52.3% over the fastest baseline under mixed weights

Synopsis

Dense vectors capture semantics and sparse vectors keep lexical terms, and hybrid retrieval ranks items by a query-dependent weighted sum of the two distances; existing systems either search separate dense and sparse indexes and rerank the union, or build one graph at a fixed weight whose neighborhoods shift when the weight changes. UniGraph samples neighbors at multiple weights, merges them by selection frequency into one bounded-degree graph, routes each query to a sparse- or dense-guided entry point, and uses dense-first distance pruning to skip some exact sparse computations. On five BEIR datasets under mixed weights, it delivers 27.6%–52.3% higher QPS than the fastest baseline at Recall@100 without index reconstruction.

Source-provided article image: UniGraph: A Unified Graph-based Index for Dynamic Hybrid Dense-Sparse Vector Retrieval
arXiv

Interpretation

Hybrid dense-sparse retrieval can now serve different query weights from one prebuilt graph instead of rebuilding an index for each weight. The two-route approach searches a dense index and a sparse index separately and reranks the union under the query weight; a fixed-weight hybrid graph holds only at its construction weight, so search must explore more vertices when the query weight differs. On five BEIR datasets, NQ, HotpotQA, MS MARCO, FEVER and DBpedia-Entity, with query weights varying from query to query, UniGraph delivers 27.6%–52.3% higher QPS than the fastest baseline at Recall@100.

Graph construction merges neighbor relations from several weights, keeping edges that are repeatedly selected across dense-sparse trade-offs. A single-weight graph records nearest neighbors at one weight only, and those connections may no longer be nearest neighbors when the weight changes. Construction samples the weight range at a fixed step, takes the top-k hybrid neighbors of each center at every sampled weight, and keeps up to a capped out-degree by selection frequency; the sampling step used was found sufficient to capture neighborhood changes, with smaller steps yielding little additional improvement.

At query time the search picks entry points by weight and computes the dense component first, using vector norms to estimate the hybrid distance and skip some exact sparse distance evaluations. Every visited candidate may otherwise require both dense and sparse distances, and the sparse inner product is costly because it matches irregularly stored nonzero entries. Under mixed weights, enabling this pruning improves QPS by an average of 10.3% across datasets, with a maximum Recall@100 decrease of only 0.055 percentage points.

Perspective

The demonstrated scope is five public BEIR retrieval datasets, with documents and queries encoded by BGE-M3 into 1024-dimensional dense vectors and weighted sparse vectors, HNSW and SINDI as the dense and sparse underlying indexes, and search experiments run single-threaded with all data in memory. It suits readers interested in vector-index structures and hybrid retrieval systems.

Discrete sampling works to the extent that hybrid neighborhoods change with the weight; the authors explain this by the hybrid distance varying linearly with the weight and candidate order changing only at crossings of distance functions, and report that the sampling step used suffices with smaller steps giving little gain. With a pruning scale above 1 the estimate is no longer guaranteed to lower-bound the hybrid distance, which may change the search path and affect recall.