UniGraph: A Unified Graph-based Index for Dynamic Hybrid Dense-Sparse Vector Retrieval

Keyu Chen, Xiaoyao Zhong, Jiabao Jin, Peng Cheng, Wangze Ni, Jingkuan Song, Heng Tao ShenarXiv 2026 · arXiv

TL;DR

UniGraph is a unified graph-based index designed for hybrid (dense-sparse) vector retrieval that supports dynamic, query-specific weights without needing to rebuild the index. By merging neighborhoods from multiple weight configurations and employing an adaptive search strategy, it achieves up to 52% higher throughput (QPS) than state-of-the-art baselines at high recall levels.

What Problem Does This Paper Address?

Modern information retrieval, especially in Retrieval-Augmented Generation (RAG) systems, relies on two types of vector representations: dense vectors (which capture semantic meaning) and sparse vectors (which capture exact lexical matches like rare terms or IDs).

To get the best of both worlds, systems use "hybrid retrieval," ranking items by a weighted distance:
$D_h = \alpha \cdot D_{dense} + (1-\alpha) \cdot D_{sparse}$

The challenge is that the "perfect" balance ($\alpha$) often changes depending on the query. A conceptual question might need more dense weight, while a query for a specific part number needs more sparse weight. Existing solutions struggle with this:

  1. Two-route pipelines search dense and sparse indexes separately and then merge results. This is computationally expensive and can miss items that only rank highly when both signals are combined.
  2. Fixed-weight graphs are built for a specific $\alpha$. If a query uses a different weight, the graph's neighborhood structure becomes inefficient, leading to a sharp drop in speed or accuracy.

Methods

The authors introduce UniGraph, which treats dense and sparse signals as complementary parts of a single unified index. Its architecture rests on three pillars:

  • $\alpha$-cover Construction: Instead of building a graph for one weight, UniGraph samples multiple $\alpha$ values (e.g., from 0.0 to 1.0). It computes the top neighbors for each weight and merges them into a single bounded-degree graph. It uses an "occurrence frequency" merge, prioritizing neighbors that appear across multiple weights to ensure the graph remains robust for any $\alpha$ chosen at query time.
  • $\alpha$-adaptive Search: The search doesn't start from a random point. If a query is sparse-dominant ($\alpha \le 0.5$), it uses a sparse index to find entry points; if dense-dominant, it uses a dense index. This "guided" initialization places the search agent much closer to the target neighborhood.
  • Dense-First Pruning: Calculating sparse distances is expensive because it involves matching irregular non-zero entries. UniGraph calculates the dense distance first, then uses vector norms and the Cauchy-Schwarz inequality to estimate a lower bound for the hybrid distance. If this estimate is already worse than the current top results, it skips the expensive sparse calculation entirely.

Datasets

The researchers evaluated UniGraph using five diverse datasets from the BEIR benchmark, representing different retrieval tasks:

  • NQ (Natural Questions)
  • HotpotQA (Multi-hop question answering)
  • MS MARCO (Web passage retrieval)
  • FEVER (Fact verification)
  • DBpedia-Entity (Entity retrieval)

All documents and queries were encoded using the BGE-M3 model to produce both 1024-dimensional dense vectors and weighted sparse vectors.

Key Insights and Ideas

  • Neighborhood Correlation: A key "aha" moment is the observation that dense and sparse similarities are highly correlated. Objects that are semantically similar often share lexical overlap. This allows a single graph to effectively navigate both spaces.
  • The Power of Frequency: By keeping edges that appear frequently across different $\alpha$ samples, UniGraph naturally preserves the "backbone" of the data's similarity structure while still allowing for weight-specific "shortcuts."
  • Coarse-to-Fine Traversal: The guided entry-point strategy essentially turns graph search into a coarse-to-fine process—using a single modality to get to the right "neighborhood" and then using the hybrid distance to find the exact top-k.

Key Results

  • Superior Efficiency: In mixed-weight settings, UniGraph delivered 27.6% to 52.3% higher QPS (Queries Per Second) than the fastest baselines while maintaining a Recall@100 $\ge$ 0.95.
  • Robustness: Unlike fixed-weight graphs that degrade when the query weight shifts, UniGraph maintained stable, high performance across the entire spectrum of $\alpha$ values.
  • Low Overhead: Despite maintaining a more complex neighborhood structure, UniGraph only incurs about 5% additional storage overhead compared to standard two-route systems.
  • Production Ready: The system has already been deployed at scale within Ant Group’s production environment, proving its viability for real-world, high-demand applications.

Limitations and Future Work

  • Construction Time: Building the $\alpha$-cover graph is more time-consuming than building a standard HNSW graph because it requires multiple neighbor-search passes during the indexing phase.
  • Memory Requirements: To perform the dense-first pruning and hybrid ranking during traversal, the system must keep both dense and sparse representations (or at least their norms) readily accessible in memory.
  • Future Directions: The authors suggest exploring more sophisticated sampling for $\alpha$ or extending the unified graph approach to handle more than two modalities (e.g., adding image or audio vectors into the hybrid mix).

Summary updated

Abstract

Hybrid dense-sparse vector retrieval combines semantic signals from dense representations with lexical signals from sparse representations, typically ranking items by a query-dependent weighted sum of dense and sparse vector distances. Existing systems commonly search separate dense and sparse vector indexes and rerank the union of their candidates, incurring two retrieval passes and potentially discarding items that rank highly only after the semantic and lexical signals are combined. Constructing a graph-based index directly under a hybrid distance can mitigate this premature candidate loss. However, because varying the hybrid weight alters the underlying neighborhood relationships, a single static graph built at a fixed weight cannot accommodate dynamic query-specific weights. Therefore, we propose a Unified Hybrid Graph (UniGraph), which merges neighbor sets computed at multiple hybrid weights into a single bounded-degree graph index, enabling hybrid vector retrieval with different query-specific weights without index reconstruction. We further develop an adaptive weight-guided search framework that chooses between sparse- and dense-guided entry points according to the query weight, together with a dense-first hybrid distance pruning strategy that avoids unnecessary exact sparse distance computations. Extensive experiments show that UniGraph provides a favorable Recall-QPS trade-off across different query weights. In the mixed-weight setting, UniGraph delivers 27.6%~52.3% higher QPS than the fastest baseline on each dataset at Recall@100 greater than or equal to 0.95. UniGraph has been deployed at scale in Ant Group's production environment, where hybrid retrieval with query-dependent weights is in strong demand.
BibTeX
@misc{chen2026unigraph,
  author = {Keyu Chen and Xiaoyao Zhong and Jiabao Jin and Peng Cheng and Wangze Ni and Jingkuan Song and Heng Tao Shen},
  title = {{UniGraph: A Unified Graph-based Index for Dynamic Hybrid Dense-Sparse Vector Retrieval}},
  year = {2026},
  eprint = {2611.20758},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.20758},
}
Figure