betaFeedback

WorksComputer Science

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

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.

Introduction

The growing volume of unstructured data and the increasing use of retrieval-driven AI applications have established vector search as a fundamental component of modern information systems. Retrieval-augmented generation (RAG), for example, relies on vector search to retrieve relevant information from external document collections and utilizes the retrieved information to provide large language models with additional context [1, 2]. In vector search, data objects and queries are encoded as high-dimensional vectors, and the objects are ranked according to their distances or similarities to the query.

Vector search commonly uses either dense or sparse representations. Dense vectors effectively capture semantic similarity but may not preserve exact lexical information such as rare terms or identifiers [3]. Sparse vectors retain term-level information and are therefore well suited to exact lexical matching [4, 5]. By combining the complementary semantic and lexical signals from dense and sparse representations, hybrid retrieval can achieve higher retrieval effectiveness than dense-only or sparse-only retrieval [6]. Hybrid dense-sparse vector retrieval has also seen growing adoption in practical information retrieval systems [7].

In hybrid dense-sparse vector retrieval, each item xx in the base dataset is represented by a dense vector xdx^{d} and a sparse vector xsx^{s}. Given a query qq with its dense representation qdq^{d} and sparse representation qsq^{s}, the hybrid distance Dh(q,x;α)D_{h}(q,x;\alpha) is defined as a weighted sum of the dense distance Dd(qd,xd)D_{d}(q^{d},x^{d}) and the sparse distance Ds(qs,xs)D_{s}(q^{s},x^{s}):

Dh(q,x;α)=α⋅Dd(qd,xd)+(1−α)⋅Ds(qs,xs),(1)D_{h}(q,x;\alpha)=\alpha\cdot D_{d}(q^{d},x^{d})+(1-\alpha)\cdot D_{s}(q^{s},x^{s}), \tag*{(1)}

where α∈[0,1]\alpha\in[0,1] controls the trade-off between semantic and lexical matching. This weight is naturally query-dependent. A conceptual question may rely more on dense similarity, while a query containing rare terms or identifiers may require stronger sparse matching. In this work, we consider the setting where α\alpha is specified at query time, focusing on efficiently supporting retrieval under the resulting query-specific hybrid distance.

A common existing approach to hybrid retrieval is a two-route pipeline that searches dense and sparse indexes independently, merges their candidate sets, and reranks them under the query-specific hybrid distance [8, 9, 10, 11]. This design entails an effectiveness–efficiency trade-off: for a requested result size kk, retrieving fewer candidates from each index risks missing some of the final hybrid top-kk results, whereas retrieving more candidates increases the costs of both searches and reranking. Alternatively, a graph constructed directly under a certain DhD_{h} is tailored to the hybrid query weight used during construction and cannot maintain stable retrieval performance under dynamically varying query weights [12].

Our key observation is that dense and sparse vectors are complementary representations of the same underlying objects. Although they emphasize different aspects of relevance, both are derived from the same content and therefore induce correlated similarity structures: objects with high dense similarity also tend to have high sparse similarity. Figure 1 illustrates this observation. A more direct and efficient design is to use a unified index in which dense and sparse signals are combined during graph construction and traversal.

With this observation, we propose the Unified Hybrid Graph (UniGraph), a graph-based index for dense-sparse hybrid retrieval with dynamic query-specific weights. UniGraph constructs a single bounded-degree graph by merging neighborhoods sampled at multiple α\alpha values for various dense-sparse trade-offs. The resulting graph retains edges useful across different dense-sparse trade-offs, allowing the same graph to support different query weights without reconstruction. At query time, our search algorithm first obtains a set of entry points according to the query-specific α\alpha, aligning graph initialization with the query’s dense-sparse preference. It then traverses the unified graph and ranks results using the query-specific hybrid distance. To further improve search efficiency, we develop a dense-first hybrid distance pruning strategy during traversal, which computes the dense component first and utilizes sparse vector norms to determine whether exact sparse distance evaluation can be skipped.

Figure 1. Motivating example for unified dense-sparse hybrid retrieval. The left panel shows that dense, sparse, and hybrid retrieval can produce different top-ranked results for the same query. In this example, doc1 is not ranked first by either dense or sparse retrieval, but becomes the top result under hybrid ranking. The right panel shows three graph neighborhoods built from dense, sparse, and hybrid similarities. Although the three neighborhoods have different highest-ranked nodes, their top-neighbor sets still overlap substantially.

In summary, this paper makes the following contributions:

  • We propose UniGraph, a unified graph index for dense-sparse hybrid retrieval with dynamic query-specific weights. Its α\alpha-cover construction merges neighborhoods sampled at multiple dense-sparse trade-off weights into a bounded-degree graph, allowing a single hybrid graph to support different query-specific weights without reconstruction.

  • We develop an α\alpha-adaptive search strategy in UniGraph. It routes each query through a sparse-guided or dense-guided execution path according to trade-off value α\alpha and applies dense-first hybrid distance pruning to avoid unnecessary exact sparse distance computations.

  • We conduct extensive experiments on five real-world datasets. At Recall@100 ≥0.95\ge0.95, UniGraph delivers 27.6%∼52.3% higher QPS than the fastest baseline on each dataset under mixed weights, and 1.18×∼2.85× QPS of the fastest baseline across the fixed weights.

The remainder of this paper is organized as follows: §II defines the hybrid retrieval problem and discusses existing two-route and graph-based solutions. §III presents the construction and search procedure of UniGraph, including hybrid distance pruning. §IV presents guided entry-point search in UniGraph and α\alpha-adaptive execution through sparse-guided and dense-guided paths. §V reports the experimental setup and results on five datasets. §VI reviews related work.

Preliminaries

Problem Definition

Definition 1 (kk-Nearest Neighbor Search (kk-NNS)). Let X={xi}i=1N\mathcal{X} = \{x_i\}_{i=1}^{N} be a finite vector dataset with ∣X∣=N|\mathcal{X}| = N. Given a query vector qq, a distance function D(q,xi)D(q,x_i), and a result size kk, the objective of kk-nearest neighbor search (kk-NNS) is to retrieve a size-kk subset of X\mathcal{X} whose vectors have the smallest distances to qq. The exact result is defined as

RD(q,X,k)=arg⁡min⁡S⊆X∣S∣=k ∑xi∈SD(q,xi).(2)R_D(q,\mathcal{X},k) = \underset{\substack{S\subseteq\mathcal{X}\\|S|=k}}{\arg\min}\ \sum_{x_i\in S} D(q,x_i). \tag*{(2)}

Definition 2 (kk-Approximate Nearest Neighbor Search (kk-ANNS)). Given a finite vector dataset X={xi}i=1N\mathcal{X} = \{x_i\}_{i=1}^{N}, a query vector qq, a distance function D(q,xi)D(q,x_i), and a result size kk, the objective of kk-approximate nearest neighbor search (kk-ANNS) is to efficiently retrieve a size-kk approximate result set R^D(q,X,k)\hat{R}_D(q,\mathcal{X},k) that closely matches the exact kk-NNS result RD(q,X,k)R_D(q,\mathcal{X},k) without exhaustively evaluating D(q,xi)D(q,x_i) over all xi∈Xx_i\in\mathcal{X}. The retrieval quality of R^D(q,X,k)\hat{R}_D(q,\mathcal{X},k) is measured by its recall against the exact result:

Recall⁡@k(q;D)=∣R^D(q,X,k)∩RD(q,X,k)∣k.(3)\operatorname{Recall}@k(q;D)=\frac{\left|\hat{R}_D(q,\mathcal{X},k)\cap R_D(q,\mathcal{X},k)\right|}{k}. \tag*{(3)}

Dense and Sparse Retrieval

In the dense-sparse retrieval setting, each base item xi∈Xx_i\in\mathcal{X} is represented as a dense-sparse vector pair xi=(xid,xis)x_i=(x_i^d,x_i^s). A query is written as q=(qd,qs)q=(q^d,q^s), where qdq^d and qsq^s represent the dense and sparse vectors of query qq, respectively.

A dense base vector xidx_i^d is obtained by encoding an item in the base dataset using a dense encoding model, such as DPR [13], Sentence-BERT [14], or BGE-M3 [15]. Dense retrieval ranks dense base vectors using distance measures such as inner-product distance, cosine distance, or Euclidean distance. Let Dd(qd,xid)D_d(q^d, x_i^d) denote the dense distance between query vector qdq^d and base vector xidx_i^d. The exact dense top-kk result Rd(q,X,k)R_d(q, \mathcal{X}, k) is the size-kk subset S⊆XS \subseteq\mathcal{X} that minimizes the total dense distance:

Rd(q,X,k)=arg⁡min⁡S⊆X∣S∣=k∑xi∈SDd(qd,xid).(4)R_d(q, \mathcal{X}, k) = \underset{\substack{S \subseteq\mathcal{X}\\ |S|=k}}{\arg\min} \sum_{x_i \in S} D_d(q^d, x_i^d). \tag*{(4)}

A sparse base vector xsx^s has high dimensionality, with most dimensions equal to zero. Nonzero entries correspond to vocabulary terms and preserve lexical information. Sparse base vectors can be produced by term-weighting models such as BM25 [4] or learned sparse encoders such as SPLADE [5], [16, 17, 18]. Let T(qs)T(q^s) and T(xis)T(x_i^s) denote the sets of nonzero terms in the sparse query and base vector, respectively, and let qtsq_t^s and xi,tsx_{i,t}^s be their weights for term tt. The sparse inner-product score ss(qs,xis)s_s(q^s, x_i^s) between query vector qsq^s and base vector xisx_i^s is defined as

ss(qs,xis)=∑t∈T(qs)∩T(xis)qtsxi,ts.(5)s_s(q^s, x_i^s) = \sum_{t \in T(q^s) \cap T(x_i^s)} q_t^s x_{i,t}^s. \tag*{(5)}

The exact sparse top-kk result Rs(q,X,k)R_s(q, \mathcal{X}, k) is the size-kk subset S⊆XS \subseteq\mathcal{X} that maximizes the total sparse score:

Rs(q,X,k)=arg⁡max⁡S⊆X∣S∣=k∑xi∈Sss(qs,xis).(6)R_s(q, \mathcal{X}, k) = \underset{\substack{S \subseteq\mathcal{X}\\ |S|=k}}{\arg\max} \sum_{x_i \in S} s_s(q^s, x_i^s). \tag*{(6)}

Hybrid Dense-Sparse Retrieval

3) Hybrid Dense-Sparse Retrieval: We use the hybrid distance defined in Eq. (1), with the query-level weight α∈[0,1]\alpha\in[0, 1] controlling the dense-sparse trade-off. Sparse retrieval uses inner-product scores, which we convert to distances as Ds(qs,xis)=1−ss(qs,xis)=1−⟨qs,xis⟩D_s(q^s, x_i^s) = 1 - s_s(q^s, x_i^s) = 1 - \langle q^s, x_i^s \rangle. To use a consistent distance formulation for the dense and sparse components, we also adopt inner-product distance for dense retrieval, i.e., Dd(qd,xid)=1−⟨qd,xid⟩D_d(q^d, x_i^d) = 1 - \langle q^d, x_i^d \rangle. In this definition, a smaller α\alpha value places greater weight on the sparse distance, whereas a larger α\alpha value places greater weight on the dense distance.

Definition 3 (Hybrid Dense-Sparse Retrieval). Given a dataset X\mathcal{X} of base vector pairs, a query vector pair qq, a trade-off weight α\alpha, and a result size kk, the hybrid dense-sparse retrieval problem is to find the top-kk base vector pairs in X\mathcal{X} with the smallest hybrid distances:

Rh(q,X,k;α)=arg⁡min⁡S⊆X∣S∣=k∑xi∈SDh(q,xi;α).(7)R_h(q, \mathcal{X}, k; \alpha) = \underset{\substack{S \subseteq\mathcal{X}\\ |S|=k}}{\arg\min} \sum_{x_i \in S} D_h(q, x_i; \alpha). \tag*{(7)}

At scale, we address this objective as a kk-ANNS problem under DhD_h. Let R^h(q,X,k;α)\widehat{R}_h(q, \mathcal{X}, k; \alpha) denote the returned top-kk result set; its recall is computed using Eq. (3) against the exact result Rh(q,X,k;α)R_h(q, \mathcal{X}, k; \alpha). The challenge studied in this paper is to compute high-recall approximations R^h(q,X,k;α)\widehat{R}_h(q, \mathcal{X}, k; \alpha) efficiently for query-level α\alpha values without rebuilding the index for each query. Table I summarizes the main symbols used in the paper.

SymbolDescription
X,N\mathcal{X}, NBase dataset and its size
xi=(xid,xis)x_i = (x_i^d, x_i^s)Dense-sparse base vector pair
q=(qd,qs)q = (q^d, q^s)Dense-sparse query vector pair
Dd,Ds,DhD_d, D_s, D_hDense, sparse, and hybrid distances
α\alphaHybrid weight
Rd,Rs,RhR_d, R_s, R_hDense, sparse, and hybrid top-kk results
A\mathcal{A}Hybrid weights sampled for graph construction
δ\deltaSampling step for hybrid weights
kgk_gNumber of neighbors retained per sampled weight
Niα\mathcal{N}_i^\alphaTop-kgk_g neighbors of xix_i under weight α\alpha
Ui\mathcal{U}_iUnion of neighbor sets of xix_i over sampled weights
fi(xj)f_i(x_j)Selection frequency of xjx_j as a neighbor of xix_i
MMMaximum graph out-degree
NG(x)N_G(x)Outgoing neighbor set of xx in UniGraph
C,RC, \mathcal{R}Candidate and result sets in graph search
k,Rkk, R_kNumber of returned results and final top-kk result set
Vseen\mathcal{V}_{\mathrm{seen}}Vertices seen during graph search
ef,ese_f, e_sConstruction and search beam sizes
γ\gammaHybrid-distance pruning scale

Table I. Summary of notation.

Existing Solutions

Two-route retrieval. A common way to support hybrid retrieval is to run dense and sparse retrieval as two independent routes [8, 9, 10, 11]. For a query qq, a dense vector index retrieves top candidates ranked by the dense distance DdD_d, while a sparse vector index retrieves top candidates ranked by the sparse distance DsD_s. The union is then reranked by computing Dh(q,x;α)D_h(q, x; \alpha) for each candidate xx to produce the final top-kk [9], [10]. The two-route design imposes no restrictions on the choice of dense or sparse indexes. The number of candidates retrieved from each index can be adjusted to balance recall and retrieval efficiency. Retrieving more candidates can improve recall but increases search and reranking costs, whereas retrieving fewer candidates reduces these costs but risks missing hybrid top-kk results [11].

Fixed-weight hybrid graph. Another approach is to construct a proximity graph using the hybrid distance with a fixed weight α\alpha, such as α=0.5\alpha= 0.5 [12]. Because nearest-neighbor relationships can change with the hybrid weight, a graph constructed at a fixed α\alpha may lack connections between items that are close under other query weights. When the query weight differs from the weight used for graph construction, the search may need to explore more vertices to reach the nearest neighbors. This can increase query cost or reduce recall for a fixed search budget. Although this approach can be improved by first performing coarse retrieval with a dense or sparse index and then conducting fine-grained search on the hybrid graph [12], it still fundamentally relies on a graph constructed with a fixed hybrid weight and therefore cannot adapt to query-dependent hybrid weights.

Unified Hybrid Graph

Motivation

Dense and sparse vectors are paired representations of the same items in the base dataset. They are partially correlated: not identical, but not independent. This partial correlation creates both the problem and the opportunity. The problem is that two-route retrieval may miss hybrid top-kk results when an item does not rank highly in either vector modality. The opportunity is that neighborhoods under nearby α\alpha values overlap, allowing a unified graph to reuse edges across multiple hybrid weights.

Figure 2 analyzes the source composition of the exact hybrid top-kk result sets across five real-world datasets. For k=100k = 100, we classify each item in the exact hybrid result set according to whether it also appears in the exact dense and sparse result sets. At intermediate weights, both dense-only and sparse-only results account for substantial portions of the hybrid top-100, indicating that neither component overwhelmingly dominates the hybrid ranking. This suggests that, for the datasets shown, the dense and sparse distance scales are sufficiently compatible. The Neither portion shows that some hybrid top-kk results are absent from both single-modality result sets. On dataset NQ at α=0.3\alpha= 0.3 and 0.5, this portion reaches 24%. These omissions limit the recall of two-route retrieval.

Figure 2. Source composition of the exact hybrid result set RhR_h for k=100k = 100. Each bar partitions the items in RhR_h according to their membership in RsR_s and RdR_d: only in RsR_s, only in RdR_d, in both sets, or in neither set. The Both segment remains relatively stable across α\alpha values because the items it contains rank highly in both dense and sparse retrieval and therefore also tend to rank highly under the hybrid distance.

Figure 2 also suggests why a unified graph is feasible. As α\alpha increases from 0 to 1, the contribution of the two modalities changes accordingly, while the portion shared by both rankings remains stable. In other words, hybrid neighborhoods are weight-dependent but still related: different weights favor different neighbors, yet part of the neighborhood structure can be reused. A graph constructed at a fixed α\alpha value captures only the neighbor relations under that weight. This motivates the α\alpha-cover construction of UniGraph, which combines neighbor relations from multiple α\alpha values, retaining weight-specific connections while sharing their common structure in a single graph.

Why Is Discrete α\alpha Sampling Effective? The effectiveness of discrete sampling depends on how the hybrid neighborhood changes with α\alpha. For a fixed center base vector pair xix_i and a candidate neighbor xjx_j, the hybrid distance can be rewritten as

Dh(xi,xj;α)=Ds(xis,xjs)+α(Dd(xid,xjd)−Ds(xis,xjs)).(8)D_h(x_i,x_j;\alpha) = D_s(x_i^s,x_j^s) + \alpha\left(D_d(x_i^d,x_j^d) - D_s(x_i^s,x_j^s)\right). \tag*{(8)}

This equation shows that the hybrid distance between two base vector pairs changes linearly with α\alpha. For a fixed center base vector pair xix_i, each of the remaining N−1N - 1 base vector pairs defines a linear hybrid distance function of α\alpha. When two candidates are compared, their relative order can change only at a crossing of their distance functions. Only crossings within α∈[0,1]\alpha\in[0,1] can affect the candidate ranking, and the partial correlation between dense and sparse distances further limits the number of such crossings. Many candidate pairs have the same relative order under both the dense and sparse distances. For such pairs, this order is preserved under any convex combination of the two distances. Even among the remaining crossings, those with the selected neighbors or within the unselected candidates change only their internal order. For a per-weight neighbor-set size (kgk_g), the neighbor set changes only when a candidate crosses the top-kgk_g boundary. Only a relatively small number of pairwise crossings can change the top-kgk_g neighbor set. Between consecutive change points, the neighbor set remains unchanged. Therefore, discrete α\alpha sampling can effectively capture neighborhood structures across the continuous weight range. Accordingly, to construct UniGraph, we use a fixed sampling step δ\delta to select a finite set of α\alpha values instead of finding all change points explicitly.

UniGraph Construction

Given a sampling step δ\delta, we discretize [0,1][0,1] into A={0,δ,2δ,…,1}\mathcal{A} = \{0,\delta,2\delta,\ldots,1\} and compute the top-kgk_g hybrid neighbors of xix_i for each α∈A\alpha\in\mathcal{A}. We denote this per-α\alpha neighbor set by

Niα=arg min⁡S⊆X∖{xi}∑xj∈SDh(xi,xj;α),∣S∣=kg(9)\mathcal{N}_i^\alpha= \underset{S \subseteq\mathcal{X}\setminus\{x_i\}}{\operatorname{arg\,min}} \sum_{x_j\in S} D_h(x_i,x_j;\alpha), \quad|S|=k_g \tag*{(9)}

The α\alpha-cover neighbor set is

Ui=⋃α∈ANiα.(10)\mathcal{U}_i = \bigcup_{\alpha\in\mathcal{A}} \mathcal{N}_i^\alpha. \tag*{(10)}

This set approximates the union of the top-kgk_g neighbor sets induced by all hybrid weights α∈[0,1]\alpha\in[0,1]. In our experiments, we find that a sampling step of δ=0.1\delta= 0.1 is sufficient to capture neighborhood changes, and using a smaller step yields little additional improvement.

After collecting the per-α\alpha top-kgk_g sets, we perform an α\alpha-frequency merge. For each candidate xjx_j, let

fi(xj)=∑α∈A1[xj∈Niα],(11)f_i(x_j) = \sum_{\alpha\in\mathcal{A}} \mathbf{1}[x_j \in\mathcal{N}_i^\alpha], \tag*{(11)}

where 1[⋅]\mathbf{1}[\cdot] is the indicator function, equal to 1 when its condition holds and 0 otherwise. We represent UniGraph as a directed graph G=(V,E)G=(V,E), where V=XV=\mathcal{X} is the vertex set and EE is the edge set. The final outgoing neighbor set of xix_i in GG retains the candidates with the highest frequencies:

NG(xi)=arg⁡max⁡S⊆Ui∣S∣=min⁡{M,∣Ui∣} ∑xj∈Sfi(xj).(12)N_G(x_i)=\underset{\substack{S\subseteq U_i\\ |S|=\min\{M,|U_i|\}}}{\arg\max}\ \sum_{x_j\in S}f_i(x_j). \tag*{(12)}

This caps the outgoing degree at MM by favoring neighbors that are repeatedly selected across sampled hybrid weights rather than discarding candidates at random. A higher occurrence frequency indicates that the neighbor remains important under more dense-sparse trade-offs. Figure 3 illustrates the α\alpha-cover construction workflow. Overall, the construction samples multiple hybrid weights, computes the top-kgk_g neighbors at each weight, merges the resulting neighbor sets, and ranks the candidates by occurrence frequency to obtain the final neighbor list used by UniGraph.

Figure 3. Overview of UniGraph construction for one center base vector pair xx. Across sampled α\alpha values ranging from the sparse (lexical) endpoint to the dense (semantic) endpoint, the construction retains the top-kgk_g hybrid neighbors of xx at each weight; the illustration uses kg=3k_g=3. The per-α\alpha lists are merged and deduplicated, and the number in parentheses indicates each candidate’s occurrence frequency. Ranking the candidates by this frequency produces a single UniGraph neighborhood that favors neighbors selected across multiple dense-sparse trade-offs.

Algorithm 1 formalizes the complete α\alpha-cover construction of UniGraph. It first initializes the vertex and edge sets (Line 1). For each center xix_i and each sampled α\alpha, the algorithm selects the kgk_g other base vector pairs with the smallest hybrid distances to xix_i, inserts them into UiU_i, and increments fi(xj)f_i(x_j) once for every selected xjx_j (Lines 2–8). Consequently, after all sampled weights have been processed, UiU_i and fif_i are exactly the union and occurrence counts in Eqs. (10) and (11). The algorithm then keeps the min⁡{M,∣Ui∣}\min\{M,|U_i|\} candidates with the largest frequencies as NG(xi)N_G(x_i) and adds a directed edge (xi,xj)(x_i,x_j) for each retained neighbor (Lines 9–10). Repeating

Image not extracted

Figure 1.

these operations for every xix_i completes EE, after which the algorithm returns G=(V,E)G=(V,E) (Lines 11–12).

In practice, we use dense and sparse indexes as offline candidate generators during UniGraph construction to avoid all-pairs distance computations. For each base vector pair, we independently retrieve candidate neighbors from the dense and Algorithm 2: UniGraph Search

Input: qq, G=(V,E)G=(V,E), entry-point set EqE_q, top-kk, efsef_s, hybrid weight α\alpha, pruning scale γ∈[0,1]\gamma\in[0,1].

Output: RkR_k.

  1. C←R←{(e,Dh(q,e;α))∣e∈Eq}C \leftarrow R \leftarrow\{(e,D_h(q,e;\alpha)) \mid e \in E_q\}; Vseen←Eq\mathcal{V}_{\mathrm{seen}} \leftarrow E_q

  2. nq←∥qs∥2n_q \leftarrow\lVert q^s\rVert_2

  3. τ←max⁡(v,Dv)∈RDv\tau\leftarrow\max_{(v,D_v)\in R} D_v

  4. while C≠∅C \ne\varnothing do

  5. (x,Dx)←arg⁡min⁡(v,Dv)∈CDv(x,D_x) \leftarrow\arg\min_{(v,D_v)\in C} D_v; C←C∖{(x,Dx)}C \leftarrow C \setminus\{(x,D_x)\}

  6. if ∣R∣=efs\lvert R\rvert= ef_s and Dx>τD_x > \tau then

  7. break

  8. foreach y∈NG(x)y \in N_G(x) do

  9. if y∈Vseeny \in\mathcal{V}_{\mathrm{seen}} then

  10. continue

  11. Vseen←Vseen∪{y}\mathcal{V}_{\mathrm{seen}} \leftarrow\mathcal{V}_{\mathrm{seen}} \cup\{y\}

  12. Dd,y←Dd(qd,yd)D_{d,y} \leftarrow D_d(q^d,y^d)

  13. if ∣R∣=efs\lvert R\rvert= ef_s then

  14. D^y←αDd,y+(1−α)(1−γnq∥ys∥2)\widehat{D}_y \leftarrow\alpha D_{d,y}+(1-\alpha)(1-\gamma n_q\lVert y^s\rVert_2)

  15. if D^y≥τ\widehat{D}_y \ge\tau then

  16. continue

  17. Ds,y←Ds(qs,ys)D_{s,y} \leftarrow D_s(q^s,y^s)

  18. Dy←αDd,y+(1−α)Ds,yD_y \leftarrow\alpha D_{d,y}+(1-\alpha)D_{s,y}

  19. if ∣R∣<efs\lvert R\rvert< ef_s or Dy<τD_y < \tau then

  20. C←C∪{(y,Dy)}C \leftarrow C \cup\{(y,D_y)\}; R←R∪{(y,Dy)}R \leftarrow R \cup\{(y,D_y)\}

  21. if ∣R∣>efs\lvert R\rvert> ef_s then

  22. (z,Dz)←arg⁡max⁡(v,Dv)∈RDv(z,D_z) \leftarrow\arg\max_{(v,D_v)\in R}D_v; R←R∖{(z,Dz)}R \leftarrow R \setminus\{(z,D_z)\}

  23. τ←max⁡(v,Dv)∈RDv\tau\leftarrow\max_{(v,D_v)\in R}D_v

  24. Rk←arg⁡min⁡S⊆R∣S∣=k∑(v,Dv)∈SDvR_k \leftarrow\arg\min_{\substack{S\subseteq R\\\lvert S\rvert=k}}\sum_{(v,D_v)\in S}D_v

  25. return RkR_k

sparse indexes, merge their results into a compact candidate pool, and compute the exact dense and sparse distances only for these candidates. The subsequent construction procedure does not depend on the specific dense and sparse indexes used for candidate generation. The dense and sparse indexes are used only to accelerate UniGraph construction. The per-α\alpha neighbor selection and frequency merge in Algorithm 1 are then performed over this pool rather than the full dataset; the remaining construction procedure is unchanged.

Given a query qq, a hybrid weight α\alpha, and an entry-point set EqE_q, we perform greedy beam search over UniGraph. Let efsef_s denote the search beam size. Unguided UniGraph search starts from a single randomly selected entry point (Eq={e0}E_q=\{e_0\}), whereas guided UniGraph search uses multiple query-dependent entry points retrieved from a guide index, as detailed in §IV-A. The traversal maintains a candidate set CC ordered by the query-specific hybrid distance and an efsef_s-sized result set RR containing the best vertices found so far. At each step, the search selects the closest unexpanded vertex from CC, visits its graph neighbors, evaluates promising unseen vertices, and updates CC and RR. Once ∣R∣=efs\lvert R\rvert=ef_s, it uses the standard beam-search termination condition: traversal stops when the closest remaining candidate is farther than the worst vertex in RR. During traversal, UniGraph directly uses the query-specific hybrid distance to order candidates, while supporting any query-level hybrid weight α∈[0,1]\alpha\in[0,1] without requiring graph reconstruction.

Hybrid distance evaluation can dominate traversal cost because every visited candidate may require computing both dense and sparse distances. Computing the sparse inner-product distance is especially costly because it requires matching query terms with irregularly stored nonzero entries. UniGraph search therefore evaluates the dense component first and combines it with sparse vector norms to obtain an estimated hybrid distance. Based on this estimate, it determines whether exact sparse distance computation is necessary. Base vector norms are query-independent and can be precomputed during index construction and stored with the index; the sparse query norm is computed once and reused for all candidates during the query. Once the dense distance is available, computing the pruning estimate requires only a few scalar operations and no sparse vector matching. We next derive a norm-based lower bound, use it to construct a tunable hybrid-distance estimate, and characterize the resulting pruning guarantee and efficiency–recall tradeoff.

Norm-Based Lower Bound Let ∥⋅∥2\lVert\cdot\rVert_2 denote the Euclidean norm. Applying the Cauchy–Schwarz inequality to the sparse inner-product distance defined in § II, and noting that 1−α≥01-\alpha\ge0, the norm-based sparse estimate and its induced hybrid estimate satisfy

Ls(qs,xs)=1−∥qs∥2∥xs∥2≤1−⟨qs,xs⟩=Ds(qs,xs),L_s(q^s,x^s)=1-\lVert q^s\rVert_2\lVert x^s\rVert_2 \le1-\langle q^s,x^s\rangle=D_s(q^s,x^s),
Lh(q,x;α)=αDd(qd,xd)+(1−α)Ls(qs,xs)≤Dh(q,x;α).(13)L_h(q,x;\alpha)=\alpha D_d(q^d,x^d)+(1-\alpha)L_s(q^s,x^s) \le D_h(q,x;\alpha). \tag*{(13)}

Thus, after computing the dense distance, UniGraph obtains a valid hybrid-distance lower bound using only the vector norms, without matching the nonzero entries of qsq^s and xsx^s.

Scaled Estimate and Pruning Rule The lower bound in (13) is safe but can be loose. To control pruning strength, we introduce a pruning scale γ∈[0,1]\gamma\in[0,1] and define the scaled hybrid distance estimate D^h\widehat{D}_h as

D^h(q,x;α,γ)=αDd(qd,xd)+(1−α)(1−γ∥qs∥2∥xs∥2).(14)\widehat{D}_h(q,x;\alpha,\gamma)=\alpha D_d(q^d,x^d)+(1-\alpha)(1-\gamma\lVert q^s\rVert_2\lVert x^s\rVert_2). \tag*{(14)}

Equivalently, D^h=Lh+(1−α)(1−γ)∥qs∥2∥xs∥2\widehat{D}_h=L_h+(1-\alpha)(1-\gamma)\lVert q^s\rVert_2\lVert x^s\rVert_2, so γ\gamma controls a nonnegative margin above the Cauchy–Schwarz lower bound.

Once ∣R∣=efs\lvert R\rvert=ef_s, let τ\tau be the current worst hybrid distance in RR. UniGraph compares D^h\widehat{D}_h with τ\tau. If D^h≥τ\widehat{D}_h\ge\tau, it skips the exact sparse distance for xx; otherwise, it computes Ds(qs,xs)D_s(q^s,x^s) and forms the exact hybrid distance.

Pruning Guarantee and Tradeoff

Lemma III.1 (Safe Dense-First Pruning). Suppose ∣R∣=efs\lvert R\rvert=ef_s and γ=1\gamma=1. If D^h(q,x;α,1)≥τ\widehat{D}_h(q,x;\alpha,1)\ge\tau, then Dh(q,x;α)≥τD_h(q,x;\alpha)\ge\tau. Hence, the exact-distance beam-search insertion rule would reject xx, and its exact sparse distance need not be evaluated. Proof. When γ=1\gamma= 1, Eq. (14) gives D^h=Lh\widehat{D}_h = L_h. By Eq. (13), Lh≤DhL_h \le D_h. Hence, D^h≥τ\widehat{D}_h \ge\tau implies Dh≥τD_h \ge\tau.

For γ<1\gamma< 1, the nonnegative margin makes D^h\widehat{D}_h larger and may prune more candidates, but the estimate is no longer guaranteed to lower-bound DhD_h. Smaller γ\gamma values therefore reduce exact sparse distance evaluations at the risk of changing the search path and affecting recall, whereas larger values are more conservative. We use γ=0.3\gamma= 0.3 in the main experiments and isolate its throughput effect in the pruning ablation. Figure 4 illustrates how D^h\widehat{D}_h is compared with the current result-set threshold τ\tau.

Figure 4. A concrete example of UniGraph search for a query with α=0.4\alpha= 0.4. Because α≤0.5\alpha\le0.5, the α\alpha-adaptive policy selects the sparse guide index, which returns e1e_1, e2e_2, and e3e_3 as entry points. During UniGraph traversal, expanding e1e_1 discovers ww and uu and updates the result set, whose current worst distance is τ=0.4\tau= 0.4. For brevity, we omit the fixed query and parameter arguments from the distance notation in this example. For candidate zz, dense-first pruning uses Dd(z)=0.3D_d(z) = 0.3 to obtain D^h(z)=0.5\widehat{D}_h(z) = 0.5. Since D^h(z)≥τ\widehat{D}_h(z) \ge\tau, zz is pruned without exact sparse distance evaluation. Blue values in parentheses denote exact hybrid distances.

Algorithm 2 formalizes the complete UniGraph search procedure. It first computes the exact hybrid distance Dh(q,e;α)D_h(q,e;\alpha) for each entry e∈Eqe \in E_q, inserts the resulting pairs into both C\mathcal{C} and R\mathcal{R}, and marks all entries as seen (Line 1). It computes the query sparse norm nq=∥qs∥2n_q = \lVert q^s \rVert_2 once and initializes τ\tau to the largest entry distance in R\mathcal{R} (Lines 2–3). At each iteration, the algorithm removes from C\mathcal{C} the unexpanded pair (x,Dx)(x,D_x) with the smallest distance (Lines 4–5); if R\mathcal{R} is full and Dx>τD_x > \tau, traversal terminates because no remaining candidate can improve the current result set (Lines 6–7). Otherwise, it scans every outgoing neighbor y∈NG(x)y \in N_G(x), skips previously seen neighbors, and marks each unseen neighbor immediately so that it is evaluated at most once (Lines 8–11). It first computes the dense component Dd,yD_{d,y} (Line 12) and, when R\mathcal{R} is full, uses Dd,yD_{d,y}, nqn_q, and the stored norm ∥ys∥2\lVert y^s \rVert_2 to obtain D^y\widehat{D}_y

from Eq. (14); if D^y≥τ\widehat{D}_y \ge\tau, it skips yy without computing the exact sparse component (Lines 13–16). If R\mathcal{R} is not yet full or D^y<τ\widehat{D}_y < \tau, the algorithm computes Ds,yD_{s,y} and the exact hybrid distance Dy=αDd,y+(1−α)Ds,yD_y = \alpha D_{d,y} + (1-\alpha)D_{s,y} (Lines 17–18). The result set R\mathcal{R} retains at most efe_f closest vertices found so far, and τ\tau is the distance of its farthest member (Lines 19–23). If R\mathcal{R} is not full, (y,Dy)(y,D_y) is pushed directly into both C\mathcal{C} and R\mathcal{R}; once R\mathcal{R} is full, the pair is pushed only when Dy<τD_y < \tau, meaning that yy is closer than the current farthest member (Lines 19–20). If this insertion makes ∣R∣>ef|\mathcal{R}| > e_f, the algorithm removes the farthest pair and updates τ\tau to the largest remaining distance (Lines 21–23). When traversal terminates or C\mathcal{C} becomes empty, the algorithm selects the kk pairs with the smallest distances in R\mathcal{R} and returns their vertices as Rk\mathcal{R}_k (Lines 24–25).

Guided Search in UniGraph

The guided search framework in UniGraph uses query-dependent entry points to initialize traversal of the unified graph. It selects between sparse-guided and dense-guided paths according to the query weight α\alpha. We first describe how the two paths obtain their entry points, and then present the α\alpha-adaptive routing policy and analyze the benefits of guided initialization.

Guided Entry-Point Search

Guided UniGraph search uses a guide index to obtain query-dependent entry points, as illustrated in Figure 4. We use either a sparse index or a dense index as the guide index. The sparse- and dense-guided paths retrieve results under DsD_s and DdD_d, respectively. The retrieved results serve as the entry-point set EqE_q for initializing the traversal in Algorithm 2; thereafter, UniGraph ranks and explores vertices using the query-specific hybrid distance DhD_h. The framework is independent of the specific guide index implementation. Any dense or sparse index that returns results ranked by the corresponding component distance can serve as the guide index.

α\alpha-Adaptive Execution

The guided search framework selects an execution path according to the query-level hybrid weight α\alpha: sparse- and dense-dominant queries are routed to the sparse- and dense-guided paths, respectively. After routing, the corresponding sparse or dense guide index is queried, and its results form the entry-point set EqE_q for UniGraph traversal. The two paths use the same UniGraph search procedure, differing only in the selected guide index and the resulting entry points.

We express this query-time selection as

Path⁡(q,α)={sparse-guided path,α≤αt,dense-guided path,α>αt,\operatorname{Path}(q,\alpha) = \begin{cases} \text{sparse-guided path}, & \alpha\le\alpha_t, \\ \text{dense-guided path}, & \alpha> \alpha_t, \end{cases}

where αt\alpha_t is the routing threshold between sparse-guided and dense-guided execution.

In our experiments, the dense and sparse distances have comparable scales. We therefore set αt=0.5\alpha_t = 0.5, the balance point at which the two distances receive equal weights in Eq. (1).

Analysis

Guided entry points improve search by reducing the number of hybrid graph traversal steps needed to reach the result region. During UniGraph traversal, visiting a candidate may require evaluating the hybrid distance, which combines both dense and sparse distances. In contrast, the sparse and dense guide indexes perform single-route coarse search using only one component distance. Since dense and sparse vectors are correlated, the top-kk results under either component distance are often close in UniGraph to highly ranked hybrid results. Guided UniGraph search can therefore be viewed as a coarse-to-fine process: it first uses DsD_s or DdD_d to approach the result region and then uses the query-specific hybrid distance DhD_h to refine the search over UniGraph, reducing hybrid distance evaluations and improving search efficiency compared with unguided UniGraph traversal initialized from a random graph entry point.

The α\alpha-adaptive policy further matches the entry-point strategy to the query’s dense-sparse weighting. For smaller α\alpha values, results returned by the sparse guide index are more likely to include or lie near highly ranked hybrid results. For larger α\alpha values, results returned by the dense guide index provide analogous guidance for dense-dominant queries. Taken together, guided initialization and α\alpha-adaptive routing provide two benefits: they reduce the hybrid distance evaluations needed to reach the result region and improve recall by selecting entry points that match the dense-sparse preference specified by the query.

Experiments

Experimental Setup

We evaluate UniGraph in terms of retrieval effectiveness and efficiency under mixed and fixed query weights, as well as index construction time and storage cost. We further conduct ablation studies on guided entry points, hybrid distance pruning, and multi-weight graph construction.

Datasets, query weight settings, and metrics. We use five public retrieval datasets from the BEIR benchmark [19]: NQ [20], HotpotQA [21], MS MARCO [22], FEVER [23], and DBpedia-Entity [24]. NQ covers open-domain question answering, HotpotQA focuses on multi-hop question answering, MS MARCO evaluates web passage retrieval, FEVER evaluates evidence retrieval for fact verification, and DBpedia-Entity evaluates entity retrieval over DBpedia articles. Each document and query is encoded by BGE-M3 [15] into a 1024-dimensional dense vector and a weighted sparse vector. The dense embeddings produced by BGE-M3 are ℓ2\ell_2-normalized. Table II summarizes basic statistics for the encoded datasets. For NQ, HotpotQA, MS MARCO, and FEVER, each query set contains 1,000 queries; for DBpedia-Entity, it contains all 467 available queries. We evaluate both mixed-α\alpha and fixed-α\alpha query weight settings. For each evaluated query–weight combination, we compute the exact hybrid top-kk result under Eq. (1) as ground truth.

DatasetBaseQueriesDense Dim.Avg. NNZ
NQ2.68M1,000102466.0/10.7
HotpotQA5.23M1,000102444.2/17.5
MS MARCO8.84M1,000102447.7/7.2
FEVER5.42M1,000102466.2/11.5
DBpedia-Entity4.64M467102447.8/7.3

Table II. DATASET STATISTICS. AVG. NNZ REPORTS, IN BASE/QUERY ORDER, THE AVERAGE NUMBER OF NONZERO ENTRIES PER SPARSE VECTOR.

We report Recall@50, Recall@100, and Recall@200 in the mixed-α\alpha setting, and Recall@100 in the fixed-α\alpha setting. We measure end-to-end query throughput over the complete query set and report it in queries per second (QPS).

Baselines. We compare UniGraph with six baselines. Across all evaluated methods, we use HNSW [25] and SINDI [26] as the dense and sparse indexes, respectively. HNSW is a widely used graph-based ANNS index that organizes dense vectors in a hierarchical proximity graph, while SINDI is an efficient inverted-index-based sparse retrieval method without redundant computation. Below, we describe each baseline. We reimplement the Naive Hybrid and Opt Hybrid variants introduced in [12]. These two baselines represent fixed-weight hybrid graph approaches, whereas HNSW+SINDI represents the two-route retrieval approach.

  • LADR: LADR [27] uses sparse retrieval results as entry points and, with an adaptive expansion width (cc), repeat-

edly expands the neighbors of the current top-cc candidates ranked by their dense scores until convergence. We rerank all candidates using the query-specific hybrid distance.

  • HNSW (dense-only) and SINDI (sparse-only): HNSW and SINDI retrieve candidates according to the dense and sparse distances, respectively. Each baseline then computes the missing distance component for its retrieved candidates and reranks them using the query-specific hybrid distance.

  • HNSW+SINDI (two-route): This baseline represents the two-route retrieval approach. It independently retrieves candidate sets from HNSW and SINDI for dense and sparse vectors respectively, and reranks the resulting candidates using the query-specific hybrid distance.

  • Naive Hybrid [12]: The Naive Hybrid variant constructs and searches an HNSW index directly using the hybrid distance with a fixed weight of α=0.5\alpha= 0.5.

  • Opt Hybrid [12]: The Opt Hybrid variant starts from a dense HNSW graph, augments it with neighbors selected by the fixed-weight hybrid distance, and performs dense traversal followed by hybrid traversal. Although the original method includes sparse vector pruning, we disable this optimization because our preliminary experiments found that it yielded only marginal end-to-end throughput improvements under the evaluated workloads and did not materially change the Recall-QPS trade-off.

UniGraph selects SINDI or HNSW according to the query weight to obtain entry points, then traverses the unified graph and ranks candidates using the query-specific hybrid distance. UniGraph is compatible with other dense and sparse indexes.

Parameter settings. UniGraph uses HNSW and SINDI as dense and sparse candidate generators, respectively, during graph construction. The Naive Hybrid and Opt Hybrid baselines are constructed at the fixed weight α=0.5\alpha= 0.5, while LADR uses a proximity graph extracted from the dense HNSW index and obtains its lexical seeds from SINDI.

For the Recall-QPS curves, the graph search width ranges approximately from kk to 10k10k for HNSW, the two fixed-weight hybrid baselines, and UniGraph. The SINDI candidate count ranges from 10k10k to 100k100k. For the two-route baseline, the dense and sparse candidate counts are set equal, as determined by grid search, and the count for each route ranges from kk to 5k5k. For LADR, the adaptive expansion width ranges from 1 to 200. Table III summarizes the settings.

MethodParameter Settings
HNSWConstruction: M=64M = 64; construction beam size efc=200ef_c = 200<br>Search: Candidate count =efs= ef_s
SINDIConstruction: Document pruning ratio =0= 0<br>Search: Query pruning ratio =0.5= 0.5
HNSW+SINDIConstruction: HNSW and SINDI settings as specified above<br>Search: Dense candidate count == sparse candidate count; SINDI query pruning ratio =0.5= 0.5
Naive HybridConstruction: α=0.5\alpha= 0.5; M=64M = 64; efc=200ef_c = 200
Opt HybridConstruction: α=0.5\alpha= 0.5; M=64M = 64; efc=200ef_c = 200; hybrid neighbor expansion width =200= 200<br>Search: dense-stage stopping threshold τd=0.8\tau_d = 0.8; hybrid-stage stopping threshold τh=1.0\tau_h = 1.0; no sparse vector pruning
LADRConstruction: HNSW and SINDI settings as specified above<br>Search: Lexical seed count =200= 200; SINDI query pruning ratio =0.5= 0.5
UniGraphConstruction: A={0.0,0.1,…,1.0}\mathcal{A} = \{0.0, 0.1, \ldots, 1.0\}; dense/sparse candidate counts =100/100= 100/100; HNSW efs=200ef_s = 200; SINDI query pruning ratio =0.9= 0.9; kg=32k_g = 32; M=64M = 64<br>Search: γ=0.3\gamma= 0.3; guided-entry count == guide-HNSW efs=ef_s = UniGraph efsef_s; SINDI query pruning ratio =0.5= 0.5

Table III. FIXED PARAMETER SETTINGS FOR INDEX CONSTRUCTION AND SEARCH.

Experimental environment. All methods are implemented in C++17 and compiled with GCC/G++ 15.2.0 using CMake 4.2.3. All experiments are conducted on a server running Linux 5.10.134 and equipped with one AMD EPYC 9T24 processor with 96 physical cores and 1.1 TiB of memory. Index construction uses up to 32 physical cores. At search time, all indexes and vector data reside entirely in memory, and all search experiments use a single thread.

Overall Performance

1) Mixed-α\alpha Setting. The mixed-α\alpha setting tests whether an index remains effective when the relative weighting of dense and sparse signals varies from query to query. For each dataset, the query weights are uniformly distributed over [0.3,0.7][0.3, 0.7]. We select this interval, because at more extreme weights such as α=0.1\alpha= 0.1 or 0.90.9, the hybrid distance is determined primarily by only one modality.

Figure 5 compares the Recall-QPS trade-offs of all methods when α\alpha varies across queries. At Recall@100 ≥0.95\ge0.95, UniGraph achieves 27.6%∼\sim52.3% higher QPS than the fastest baseline across the five datasets. On NQ, UniGraph sustains about 1.7×\times the QPS of two-route at Recall@100 ≈0.88\approx0.88. A more pronounced advantage appears on FEVER, where UniGraph delivers about 3.0×\times the QPS of Naive Hybrid at Recall@100 ≈0.94\approx0.94. UniGraph also retains a clear advantage over LADR on DBpedia-Entity, providing an approximately 2.3×\times QPS speedup at Recall@100 ≈0.95\approx0.95.

Figure 5. Recall@50-QPS (top), Recall@100-QPS (middle), and Recall@200-QPS (bottom) trade-offs in the mixed-α\alpha setting. The query weights are uniformly distributed over [0.3,0.7][0.3, 0.7]. Curves closer to the upper-right corner indicate better performance.

2) Fixed-α\alpha Setting. The fixed-α\alpha setting evaluates performance when all queries share the same weight. We consider five fixed weights: α∈{0.3,0.4,0.5,0.6,0.7}\alpha\in\{0.3, 0.4, 0.5, 0.6, 0.7\}.

Figure 6 reports the Recall@100-QPS trade-offs at each fixed α\alpha value. Among the two single-modality baselines, the sparse-only baseline achieves higher QPS at matched recall for smaller α\alpha, whereas the dense-only baseline achieves higher QPS for larger α\alpha. At Recall@100 ≥0.95\ge0.95, UniGraph achieves 1.18×∼\times\sim2.85×\times the QPS of the fastest baseline, with a

Figure 6. Fixed-α\alpha Recall@100-QPS trade-offs on NQ, MS MARCO, and DBpedia-Entity. The upper-right region is better.

geometric-mean speedup of 1.66×\times over all three datasets and five query weights. On NQ with α=0.3\alpha= 0.3, UniGraph delivers about 2.5×\times the QPS of the sparse-only baseline at Recall@100 ≈0.95\approx0.95. Compared with the fixed-weight hybrid graph baselines, UniGraph achieves 1.44×∼\times\sim3.34×\times the QPS of Naive Hybrid and 1.40×∼\times\sim2.26×\times that of Opt Hybrid in their comparable configurations. The advantage persists at α=0.5\alpha= 0.5, even though this query weight matches the construction weight of both Hybrid indexes. On MS MARCO with α=0.6\alpha= 0.6, UniGraph also provides about 2.1×\times the QPS of LADR at Recall@100 ≈0.95\approx0.95, consistent with the benefit of traversing the graph under the query-specific hybrid distance rather than dense scores alone. At α=0.5\alpha= 0.5 on DBpedia-Entity, UniGraph maintains about 1.6×\times the QPS of two-route at comparable recall.

3) Index Construction and Storage. Table IV compares the construction times of two-route, UniGraph, Naive Hybrid, Opt Hybrid, and LADR, while Figure 7 compares their index sizes across all five datasets. Building the unified graph introduces additional offline construction cost relative to two-route. Nevertheless, UniGraph requires 6.6%∼21.9% less construction time than Opt Hybrid and incurs only 4.5%∼5.3% additional storage over two-route.

Figure 7. Index size of HNSW+SINDI, UniGraph, Naive Hybrid, Opt Hybrid, and LADR on all five datasets; lower is better.

DatasetHNSW+ SINDIUniGraphNaive HybridOpt HybridLADR
NQ4389189101,175442
HotpotQA1,1812,4971,5923,0691,190
MS MARCO1,4182,9462,2653,1551,428
FEVER1,3002,8442,0603,6091,309
DBpedia-Entity1,0522,2151,4502,7521,060

Table IV. Index construction time in seconds; lower is better.

The reported construction time includes all index components required by each method. For UniGraph, it includes constructing HNSW, SINDI, and the unified graph.

The construction cost of HNSW+SINDI is dominated by its HNSW component. In our measurements, SINDI takes only tens of seconds to build, so the construction time of HNSW+SINDI remains close to that of HNSW alone. Naive Hybrid incurs additional cost by evaluating the hybrid distance directly during graph construction. Opt Hybrid further augments a dense HNSW graph with neighbors selected by the hybrid distance, while UniGraph constructs neighborhoods at multiple weights and merges them into a unified graph. These additional hybrid distance evaluations and graph processing steps account for the higher construction costs of the graph-based hybrid methods.

Compared with Naive Hybrid, Opt Hybrid, and LADR, UniGraph uses 14.7%∼18.7%, 16.3%∼20.2%, and 4.5%∼5.5% more index space, respectively. The additional space is the cost of maintaining both the multi-weight unified graph and the two guide structures. By sharing the underlying vectors and labels among these structures, UniGraph limits its storage overhead relative to the two-route baseline to about 5% while supporting efficient retrieval under query-dependent hybrid weights without graph reconstruction.

Ablation Study

We evaluate how guided entry points affect retrieval effectiveness, how hybrid distance pruning affects search efficiency, and whether multi-weight graph construction improves the graph-only Recall-QPS trade-off.

1) Entry-Point Strategy. We compare unguided UniGraph search initialized from a random graph entry point with sparse-guided UniGraph search at α=0.3\alpha=0.3 and dense-guided UniGraph search at α=0.7\alpha=0.7. All variants use the same hybrid graph, pruning scale γ=0.3\gamma=0.3, and search beam size efs=300e_{fs}=300.

Figure 8 shows that guided entry points substantially improve recall in all comparisons. Unguided UniGraph search obtains 83.6%∼92.6% Recall@100, whereas the sparse- and dense-guided configurations reach 94.7%∼98.1%. At α=0.3\alpha=0.3, sparse-guided UniGraph search improves recall by 7.4∼12.0 percentage points, averaging 9.7 points across the datasets. At α=0.7\alpha=0.7, dense-guided UniGraph search improves recall by 5.5∼9.7 percentage points, averaging 7.1 points. At both tested weights, using the corresponding sparse or dense guide index to select entry points substantially improves recall over random initialization.

Figure 8. Recall@100 of unguided and guided UniGraph search at efs=300e_{fs}=300. Panel (a) compares unguided and sparse-guided UniGraph search at α=0.3\alpha=0.3, while panel (b) compares unguided and dense-guided UniGraph search at α=0.7\alpha=0.7.

2) Hybrid Distance Pruning. For the hybrid distance pruning ablation, we use the mixed-α\alpha setting to compare UniGraph search with dense-first hybrid distance pruning (γ=0.3\gamma= 0.3) and UniGraph search without pruning. To isolate the effect of pruning, both configurations use the same prebuilt UniGraph and select between sparse-guided and dense-guided search using the same α\alpha-adaptive routing policy. We set efs=300ef_s = 300. The configuration without pruning disables only the pruning test in Eq. (14); candidate insertion and traversal termination still use the current result set threshold τ\tau, as in standard beam search.

As Figure 9 shows, hybrid distance pruning improves QPS on all datasets, with an average improvement of 10.3%. This throughput improvement incurs negligible recall loss: the maximum decrease in Recall@100 is only 0.055 percentage points. These results demonstrate that hybrid distance pruning effectively accelerates UniGraph search with almost no impact on result quality.

Figure 9. QPS with and without dense-first hybrid distance pruning under the mixed-α\alpha setting at efs=300e_{fs}=300.

3) Multi-Weight Graph Construction. To examine the effect of multi-weight graph construction, we compare UniGraph with a fixed-weight graph, which selects nearest neighbors only at α=0.5\alpha= 0.5 for graph construction with M=64M = 64. Query weights are uniformly distributed over [0,1][0, 1]. To exclude the effects of the query-time optimizations studied above, both methods use graph-only search initialized from the same randomly selected entry point for each query, with dense/sparse-guided entry points and hybrid distance pruning disabled.

As shown in Table V, UniGraph achieves higher QPS than the fixed-weight graph on all three datasets at both target recall levels. At Recall@100 = 0.90, its QPS improvements range from 7.95% to 25.46%, with a mean improvement of 15.49%. At Recall@100 = 0.95, the improvements range from 4.48% to 26.71%, averaging 15.77%. These results show that, under the graph-only setting, constructing one graph from neighborhoods sampled at multiple weights provides a better high-recall throughput trade-off than constructing the graph at a single fixed weight.

DatasetRecall@100Fixed-weight graphUniGraphGain
MS MARCO0.90150.96189.39+25.46%
MS MARCO0.9553.8868.28+26.71%
FEVER0.9092.73104.85+13.07%
FEVER0.9535.9741.77+16.13%
DBpedia-Entity0.90129.57139.87+7.95%
DBpedia-Entity0.9548.3950.55+4.48%

Table V. Graph-only QPS of the fixed-weight graph and UniGraph at matched Recall@100; higher is better.

Fusion-based dense-sparse retrieval. Fusion-based systems typically retrieve dense and sparse candidates separately and then combine their truncated result lists. Weighted score fusion [10] preserves score magnitudes but requires calibration, whereas reciprocal rank fusion (RRF) [10, 28] avoids calibration but discards score magnitudes and is sensitive to its rank constant. They both can lose candidates before fusion.

Dense and sparse retrieval. Dense vector ANNS methods include locality-sensitive hashing [29, 30], quantization and inverted file methods (e.g., product quantization [31] and IVF-PQ [32]), and graph-based indexes (e.g., HNSW [25], NSG [33], and DiskANN [34]). Empirical evaluations show that graph-based methods offer competitive recall-efficiency trade-offs and often perform particularly well in high-recall regimes [35, 36].

Efficient sparse retrieval is commonly implemented with inverted indexes. Representative approaches accelerate retrieval through pruning or compact index structures. Classical block-max pruning and BMP skip low-potential document blocks [37, 38]; Seismic groups inverted lists into geometrically cohesive blocks [39]; SInnamon uses compact sketches [40]; and SINDI uses optimized inverted lists for approximate sparse maximum inner-product search [26].

Unified dense-sparse indexing and dynamic-weight hybrid search. A graph-based ANNS method for dense-sparse hybrid vectors [12] aligns the dense and sparse distance distributions and refines an HNSW-style topology under a predetermined hybrid weight. Its fixed-weight topology may not match queries with different weights.

Existing query-dependent hybrid methods face limitations in dense-sparse retrieval. IVF-MIPS [41] reuses IVF partitions for query-side reweighting, but lacks cross-weight neighborhood optimization. LADR [27] seeds dense graph exploration with lexical results, but is tailored for dense retrieval. While GPU-based Allan-Poe [42] supports dynamic multi-path weighting without index reconstruction, UniGraph builds a CPU-based bounded-degree graph by merging multi-weight sampled neighborhoods.

Other multi-metric approaches and DEG [43] support query-specific weights via Pareto frontier neighborhoods or multi-graph traversals [44, 45, 46, 47, 48]. However, DEG is restricted to fixed-length Euclidean embeddings; its formulation and analysis do not cover high-dimensional inner-product sparse vectors, making it inapplicable to our dense-sparse hybrid setting without fundamental redesign.

Conclusion

This paper studies efficient dense-sparse hybrid retrieval with query-specific hybrid weights. We investigate UniGraph, a unified hybrid graph that supports different query weights without index reconstruction. UniGraph uses an α\alpha-cover construction to merge neighborhoods sampled at multiple weights. We further study α\alpha-adaptive graph search with sparse-guided and dense-guided execution paths. We also study dense-first hybrid distance pruning for reducing exact sparse distance computations. Experiments show that, at Recall@100 ≥0.95\ge0.95, UniGraph achieves 27.6%∼\sim52.3% higher QPS than the fastest baseline on each dataset under mixed weights and 1.18×\times2.85×\times QPS of the fastest baseline across the fixed-weight settings.

Acknowledgment

The authors disclose the use of OpenAI’s ChatGPT to assist with drafting the experimental code. The experimental design, testing, and correctness validation of all results were performed by the authors. ChatGPT was additionally used for editing and grammar polishing of parts of the manuscript. All AI-assisted content was reviewed and verified by the authors, who take full responsibility for the correctness and originality of this paper.

References

References

  1. [1]P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W.-t. Yih, T. Rocktäschel, S. Riedel, and D. Kiela, “Retrieval-augmented generation for knowledge-intensive nlp tasks,” in Advances in Neural Information Processing Systems, vol. 33, 2020, pp. 9459–9474.arxiv.org/abs/2005.11401
  2. [2]Y. Gao, Y. Xiong, X. Gao, K. Jia, J. Pan, Y. Bi, Y. Dai, J. Sun, M. Wang, and H. Wang, “Retrieval-augmented generation for large language models: A survey,” arXiv preprint arXiv:2312.10997, 2024.
  3. [3]C. Scialom, Z. Zhong, J. Lee, and D. Chen, “Simple entity-centric questions challenge dense retrievers,” in Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, 2021, pp. 6138–6148.
  4. [4]S. Robertson and H. Zaragoza, “The probabilistic relevance framework: BM25 and beyond,” Foundations and Trends in Information Retrieval, vol. 3, no. 4, pp. 333–389, 2009.
  5. [5]T. Formal, B. Piwowarski, and S. Clinchant, “SPLADE: Sparse lexical and expansion model for first stage ranking,” in Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2021, pp. 2288–2292.arxiv.org/abs/2107.05720
  6. [6]Y. Luan, J. Eisenstein, K. Toutanova, and M. Collins, “Sparse, dense, and attentional representations for text retrieval,” Transactions of the Association for Computational Linguistics, vol. 9, pp. 329–345, 2021.
  7. [7]K. Sawarkar, A. Mangal, and S. R. Solanki, “Blended RAG: Improving RAG (retriever-augmented generation) accuracy with semantic search and hybrid query-based retrievers,” in Proceedings of the 2024 IEEE 7th International Conference on Multimedia Information Processing and Retrieval, 2024, pp. 155–161.DOI
  8. [8]S. Kuzi, M. Zhang, C. Li, M. Bendersky, and M. Najork, “Leveraging semantic and lexical matching to improve the recall of document retrieval systems: A hybrid approach,” arXiv preprint arXiv:2010.01195, 2020.arxiv.org/abs/2010.01195
  9. [9]S. Wang, S. Zhuang, and G. Zuccon, “BERT-based dense retrievers require interpolation with BM25 for effective passage retrieval,” in Proceedings of the 2021 ACM SIGIR International Conference on Theory of Information Retrieval, 2021, pp. 317–324.DOI
  10. [10]S. Bruch, S. Gai, and A. Ingber, “An analysis of fusion functions for hybrid retrieval,” ACM Transactions on Information Systems, vol. 42, no. 1, pp. 20:1–20:35, 2024.DOI
  11. [11]Y. Chen, R. Zheng, Q. Chen, S. Xu, Q. Zhang, X. Wu, W. Han, H. Yuan, M. Li, Y. Wang, J. Li, F. Yang, H. Sun, W. Deng, F. Sun, Q. Zhang, and M. Yang, “OneSparse: A unified system for multi-index vector search,” in Companion Proceedings of the ACM Web Conference 2024, 2024, pp. 393–402.DOI
  12. [12]H. Zhang, J. Liu, Z. Zhu, S. Zeng, M. Sheng, T. Yang, G. Dai, and Y. Wang, “Efficient and effective retrieval of dense-sparse hybrid vectors using graph-based approximate nearest neighbor search,” arXiv preprint arXiv:2410.20381, 2024.arxiv.org/abs/2410.20381
  13. [13]V. Karpukhin, B. Oguz, S. Min, P. Lewis, L. Wu, S. Edunov, D. Chen, and W.-t. Yih, “Dense passage retrieval for open-domain question answering,” in Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020, pp. 6769–6781.arxiv.org/abs/2004.04906
  14. [14]N. Reimers and I. Gurevych, “Sentence-BERT: Sentence embeddings using siamese BERT-networks,” in Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, 2019, pp. 3982–3992.arxiv.org/abs/1908.10084
  15. [15]J. Chen, S. Xiao, P. Zhang, K. Luo, D. Lian, and Z. Liu, “M3-embedding: Multi-linguality, multi-functionality, multi-granularity text embeddings through self-knowledge distillation,” in Findings of the Association for Computational Linguistics: ACL 2024, 2024, pp. 2318–2335.arxiv.org/abs/2402.03216
  16. [16]T. Formal, C. Lassance, B. Piwowarski, and S. Clinchant, “From distillation to hard negative sampling: Making sparse neural IR models more effective,” in Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2022, pp. 2353–2359.
  17. [17]C. Lassance and S. Clinchant, “An efficiency study for SPLADE models,” in Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2022, pp. 2220–2226.DOI
  18. [18]T. Formal, C. Lassance, B. Piwowarski, and S. Clinchant, “Towards effective and efficient sparse neural information retrieval,” ACM Transactions on Information Systems, vol. 42, no. 5, pp. 1–46, 2024.DOI
  19. [19]N. Thakur, N. Reimers, J. Rücklé, A. Srivastava, and I. Gurevych, “BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models,” in Thirty-Fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
  20. [20]T. Kwiatkowski, J. Palomaki, O. Redfield, M. Collins, A. Parikh, C. Alberti, D. Epstein, I. Polosukhin, J. Devlin, K. Lee, K. Toutanova, L. Jones, M. Kelcey, M.-W. Chang, A. M. Dai, J. Uszkoreit, Q. Le, and S. Petrov, “Natural questions: A benchmark for question answering research,” Transactions of the Association for Computational Linguistics, vol. 7, pp. 452–466, 2019.DOI
  21. [21]Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. W. Cohen, R. Salakhutdinov, and C. D. Manning, “HotpotQA: A dataset for diverse, explainable multi-hop question answering,” in Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 2018, pp. 2369–2380.arxiv.org/abs/1809.09600
  22. [22]P. Bajaj, D. Campos, N. Craswell, L. Deng, J. Gao, X. Liu, R. Majumder, A. McNamara, B. Mitra, T. Nguyen, M. Rosenberg, X. Song, A. Stoica, S. Tiwary, and T. Wang, “MS MARCO: A human generated machine reading comprehension dataset,” arXiv preprint arXiv:1611.09268, 2016.arxiv.org/abs/1611.09268
  23. [23]J. Thorne, A. Vlachos, C. Christodoulopoulos, and A. Mittal, “FEVER: A large-scale dataset for fact extraction and verification,” in Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2018, pp. 809–819.arxiv.org/abs/1803.05355
  24. [24]F. Hasibi, F. Nikolaev, C. Xiong, K. Balog, S. E. Bratsberg, A. Kotov, and J. Callan, “DBpedia-Entity v2: A test collection for entity search,” in Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2017, pp. 1265–1268.DOI
  25. [25]Y. A. Malkov and D. A. Yashunin, “Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 42, no. 4, pp. 824–836, 2020.
  26. [26]R. Li, X. Zhong, J. Jin, P. Cheng, W. Ni, Z. Shen, W. Jia, X. Wang, H. T. Shen, and J. Song, “SINDI: An efficient index for sparse vector approximate maximum inner product search,” in Proceedings of the 2026 IEEE 42nd International Conference on Data Engineering, 2026.arxiv.org/abs/2509.08395
  27. [27]H. Kulkarni, S. MacAvaney, N. Goharian, and O. Frieder, “Lexically-accelerated dense retrieval,” in Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2023, pp. 152–162.DOI
  28. [28]G. V. Cormack, C. L. A. Clarke, and S. Büttcher, “Reciprocal rank fusion outperforms condorcet and individual rank learning methods,” in Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval, 2009, pp. 758–759.DOI
  29. [29]P. Indyk and R. Motwani, “Approximate nearest neighbors: Towards removing the curse of dimensionality,” in Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, 1998, pp. 604–613.
  30. [30]A. Gionis, P. Indyk, and R. Motwani, “Similarity search in high dimensions via hashing,” in Proceedings of the 25th International Conference on Very Large Data Bases, 1999, pp. 518–529.
  31. [31]H. Jégou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 1, pp. 117–128, 2011.DOI
  32. [32]J. Johnson, M. Douze, and H. Jégou, “Billion-scale similarity search with GPUs,” IEEE Transactions on Big Data, vol. 7, no. 3, pp. 535–547, 2019.arxiv.org/abs/1702.08734
  33. [33]C. Fu, C. Xiang, C. Wang, and D. Cai, “Fast approximate nearest neighbor search with the navigating spreading-out graph,” Proceedings of the VLDB Endowment, vol. 12, no. 5, pp. 461–474, 2019.arxiv.org/abs/1707.00143
  34. [34]S. J. Subramanya, F. Devvrit, H. V. Simhadri, R. Krishnawamy, and R. Kade-kodi, “DiskANN: Fast accurate billion-point nearest neighbor search on a single node,” in Advances in Neural Information Processing Systems, vol. 32, 2019.
  35. [35]M. Aumüller, E. Bernhardsson, and A. Faithfull, “ANN-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms,” Information Systems, vol. 87, p. 101374, 2020.
  36. [36]M. Wang, X. Xu, Q. Yue, and Y. Wang, “A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search,” Proceedings of the VLDB Endowment, vol. 14, no. 11, pp. 1964–1978, 2021.arxiv.org/abs/2101.12631
  37. [37]S. Ding and T. Suel, “Faster top-k document retrieval using block-max indexes,” in Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2011, pp. 993–1002.DOI
  38. [38]M. Mallia, T. Suel, and N. Tonellotto, “Faster learned sparse retrieval with block-max pruning,” in Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2024, pp. 2411–2415.arxiv.org/abs/2405.01117
  39. [39]S. Bruch, F. M. Nardini, C. Rulli, and R. Venturini, “Efficient inverted indexes for approximate retrieval over learned sparse representations,” in Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2024, pp. 152–162.DOI
  40. [40]S. Bruch, F. M. Nardini, A. Ingber, and E. Liberty, “An approximate algorithm for maximum inner product search over streaming sparse vectors,” ACM Transactions on Information Systems, vol. 42, no. 2, pp. 1–43, 2023.DOI
  41. [41]——, “Bridging dense and sparse maximum inner product search,” ACM Transactions on Information Systems, vol. 42, no. 6, pp. 151:1–151:38, 2024.DOI
  42. [42]Z. Li, Y. Li, Y. Zhu, C. Ge, Z. Chen, and Y. Gao, “All-in-one graph-based indexing for hybrid search on GPUs,” arXiv preprint arXiv:2511.00855, 2025.arxiv.org/abs/2511.00855
  43. [43]Z. Yin, J. Gao, P. Balsebre, G. Cong, and C. Long, “DEG: Efficient hybrid vector search using the dynamic edge navigation graph,” Proceedings of the ACM on Management of Data, vol. 3, no. 1, pp. 29:1–29:34, 2025.arxiv.org/abs/2502.07343
  44. [44]M. Franzke, T. Emrich, A. Züfle, and M. Renz, “Indexing multi-metric data,” in Proceedings of the 32nd IEEE International Conference on Data Engineering, 2016, pp. 1122–1133.
  45. [45]Y. Zhu, L. Chen, Y. Gao, B. Zheng, and P. Wang, “DESIRE: An efficient dynamic cluster-based forest indexing for similarity search in multi-metric spaces,” Proceedings of the VLDB Endowment, vol. 15, no. 10, pp. 2121–2133, 2022.
  46. [46]H. Hu and J. Li, “Efficient approximate nearest neighbor search for multiple weighted l_p≤2 distance functions,” arXiv preprint arXiv:2011.11907, 2020.arxiv.org/abs/2011.11907
  47. [47]Y. Zhu, L. Chen, Y. Gao, R. Ma, B. Zheng, and J. Zhao, “HIG: An effective hierarchical joint graph for ANNS in multi-metric spaces,” in Proceedings of the 40th IEEE International Conference on Data Engineering, 2024, pp. 4275–4287.DOI
  48. [48]R. Uemura, D. Amagata, and T. Hara, “An efficient framework for approximate nearest neighbor search on high-dimensional multi-metric data,” in Similarity Search and Applications, ser. Lecture Notes in Computer Science, vol. 15268, 2024, pp. 3–17.

Paper details

vlnc:W_2cznbm87
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI’s ChatGPT, ChatGPT

View statement
Looking for related papers…
Contents