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 in the base dataset is represented by a dense vector and a sparse vector . Given a query with its dense representation and sparse representation , the hybrid distance is defined as a weighted sum of the dense distance and the sparse distance :
where 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 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 , retrieving fewer candidates from each index risks missing some of the final hybrid top- results, whereas retrieving more candidates increases the costs of both searches and reranking. Alternatively, a graph constructed directly under a certain 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 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 , 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 -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 -adaptive search strategy in UniGraph. It routes each query through a sparse-guided or dense-guided execution path according to trade-off value 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 , 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 -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
Nearest Neighbor Search
Definition 1 (-Nearest Neighbor Search (-NNS)). Let be a finite vector dataset with . Given a query vector , a distance function , and a result size , the objective of -nearest neighbor search (-NNS) is to retrieve a size- subset of whose vectors have the smallest distances to . The exact result is defined as
Definition 2 (-Approximate Nearest Neighbor Search (-ANNS)). Given a finite vector dataset , a query vector , a distance function , and a result size , the objective of -approximate nearest neighbor search (-ANNS) is to efficiently retrieve a size- approximate result set that closely matches the exact -NNS result without exhaustively evaluating over all . The retrieval quality of is measured by its recall against the exact result:
Dense and Sparse Retrieval
In the dense-sparse retrieval setting, each base item is represented as a dense-sparse vector pair . A query is written as , where and represent the dense and sparse vectors of query , respectively.
A dense base vector 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 denote the dense distance between query vector and base vector . The exact dense top- result is the size- subset that minimizes the total dense distance:
A sparse base vector 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 and denote the sets of nonzero terms in the sparse query and base vector, respectively, and let and be their weights for term . The sparse inner-product score between query vector and base vector is defined as
The exact sparse top- result is the size- subset that maximizes the total sparse score:
Hybrid Dense-Sparse Retrieval
3) Hybrid Dense-Sparse Retrieval: We use the hybrid distance defined in Eq. (1), with the query-level weight controlling the dense-sparse trade-off. Sparse retrieval uses inner-product scores, which we convert to distances as . To use a consistent distance formulation for the dense and sparse components, we also adopt inner-product distance for dense retrieval, i.e., . In this definition, a smaller value places greater weight on the sparse distance, whereas a larger value places greater weight on the dense distance.
Definition 3 (Hybrid Dense-Sparse Retrieval). Given a dataset of base vector pairs, a query vector pair , a trade-off weight , and a result size , the hybrid dense-sparse retrieval problem is to find the top- base vector pairs in with the smallest hybrid distances:
At scale, we address this objective as a -ANNS problem under . Let denote the returned top- result set; its recall is computed using Eq. (3) against the exact result . The challenge studied in this paper is to compute high-recall approximations efficiently for query-level values without rebuilding the index for each query. Table I summarizes the main symbols used in the paper.
| Symbol | Description |
| Base dataset and its size | |
| Dense-sparse base vector pair | |
| Dense-sparse query vector pair | |
| Dense, sparse, and hybrid distances | |
| Hybrid weight | |
| Dense, sparse, and hybrid top- results | |
| Hybrid weights sampled for graph construction | |
| Sampling step for hybrid weights | |
| Number of neighbors retained per sampled weight | |
| Top- neighbors of under weight | |
| Union of neighbor sets of over sampled weights | |
| Selection frequency of as a neighbor of | |
| Maximum graph out-degree | |
| Outgoing neighbor set of in UniGraph | |
| Candidate and result sets in graph search | |
| Number of returned results and final top- result set | |
| Vertices seen during graph search | |
| Construction and search beam sizes | |
| Hybrid-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 , a dense vector index retrieves top candidates ranked by the dense distance , while a sparse vector index retrieves top candidates ranked by the sparse distance . The union is then reranked by computing for each candidate to produce the final top- [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- results [11].
Fixed-weight hybrid graph. Another approach is to construct a proximity graph using the hybrid distance with a fixed weight , such as [12]. Because nearest-neighbor relationships can change with the hybrid weight, a graph constructed at a fixed 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- results when an item does not rank highly in either vector modality. The opportunity is that neighborhoods under nearby values overlap, allowing a unified graph to reuse edges across multiple hybrid weights.
Figure 2 analyzes the source composition of the exact hybrid top- result sets across five real-world datasets. For , 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- results are absent from both single-modality result sets. On dataset NQ at 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 for . Each bar partitions the items in according to their membership in and : only in , only in , in both sets, or in neither set. The Both segment remains relatively stable across 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 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 value captures only the neighbor relations under that weight. This motivates the -cover construction of UniGraph, which combines neighbor relations from multiple values, retaining weight-specific connections while sharing their common structure in a single graph.
Why Is Discrete Sampling Effective? The effectiveness of discrete sampling depends on how the hybrid neighborhood changes with . For a fixed center base vector pair and a candidate neighbor , the hybrid distance can be rewritten as
This equation shows that the hybrid distance between two base vector pairs changes linearly with . For a fixed center base vector pair , each of the remaining base vector pairs defines a linear hybrid distance function of . When two candidates are compared, their relative order can change only at a crossing of their distance functions. Only crossings within 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 (), the neighbor set changes only when a candidate crosses the top- boundary. Only a relatively small number of pairwise crossings can change the top- neighbor set. Between consecutive change points, the neighbor set remains unchanged. Therefore, discrete sampling can effectively capture neighborhood structures across the continuous weight range. Accordingly, to construct UniGraph, we use a fixed sampling step to select a finite set of values instead of finding all change points explicitly.
UniGraph Construction
Given a sampling step , we discretize into and compute the top- hybrid neighbors of for each . We denote this per- neighbor set by
The -cover neighbor set is
This set approximates the union of the top- neighbor sets induced by all hybrid weights . In our experiments, we find that a sampling step of is sufficient to capture neighborhood changes, and using a smaller step yields little additional improvement.
After collecting the per- top- sets, we perform an -frequency merge. For each candidate , let
where is the indicator function, equal to 1 when its condition holds and 0 otherwise. We represent UniGraph as a directed graph , where is the vertex set and is the edge set. The final outgoing neighbor set of in retains the candidates with the highest frequencies:
This caps the outgoing degree at 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 -cover construction workflow. Overall, the construction samples multiple hybrid weights, computes the top- 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 . Across sampled values ranging from the sparse (lexical) endpoint to the dense (semantic) endpoint, the construction retains the top- hybrid neighbors of at each weight; the illustration uses . The per- 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 -cover construction of UniGraph. It first initializes the vertex and edge sets (Line 1). For each center and each sampled , the algorithm selects the other base vector pairs with the smallest hybrid distances to , inserts them into , and increments once for every selected (Lines 2–8). Consequently, after all sampled weights have been processed, and are exactly the union and occurrence counts in Eqs. (10) and (11). The algorithm then keeps the candidates with the largest frequencies as and adds a directed edge for each retained neighbor (Lines 9–10). Repeating
Figure 1.
these operations for every completes , after which the algorithm returns (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: , , entry-point set , top-, , hybrid weight , pruning scale .
Output: .
;
while do
;
if and then
break
foreach do
if then
continue
if then
if then
continue
if or then
;
if then
;
return
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- 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.
UniGraph Search
Given a query , a hybrid weight , and an entry-point set , we perform greedy beam search over UniGraph. Let denote the search beam size. Unguided UniGraph search starts from a single randomly selected entry point (), 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 ordered by the query-specific hybrid distance and an -sized result set containing the best vertices found so far. At each step, the search selects the closest unexpanded vertex from , visits its graph neighbors, evaluates promising unseen vertices, and updates and . Once , it uses the standard beam-search termination condition: traversal stops when the closest remaining candidate is farther than the worst vertex in . During traversal, UniGraph directly uses the query-specific hybrid distance to order candidates, while supporting any query-level hybrid weight 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 denote the Euclidean norm. Applying the Cauchy–Schwarz inequality to the sparse inner-product distance defined in § II, and noting that , the norm-based sparse estimate and its induced hybrid estimate satisfy
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 and .
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 and define the scaled hybrid distance estimate as
Equivalently, , so controls a nonnegative margin above the Cauchy–Schwarz lower bound.
Once , let be the current worst hybrid distance in . UniGraph compares with . If , it skips the exact sparse distance for ; otherwise, it computes and forms the exact hybrid distance.
Pruning Guarantee and Tradeoff
Lemma III.1 (Safe Dense-First Pruning). Suppose and . If , then . Hence, the exact-distance beam-search insertion rule would reject , and its exact sparse distance need not be evaluated. Proof. When , Eq. (14) gives . By Eq. (13), . Hence, implies .
For , the nonnegative margin makes larger and may prune more candidates, but the estimate is no longer guaranteed to lower-bound . Smaller 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 in the main experiments and isolate its throughput effect in the pruning ablation. Figure 4 illustrates how is compared with the current result-set threshold .
Figure 4. A concrete example of UniGraph search for a query with . Because , the -adaptive policy selects the sparse guide index, which returns , , and as entry points. During UniGraph traversal, expanding discovers and and updates the result set, whose current worst distance is . For brevity, we omit the fixed query and parameter arguments from the distance notation in this example. For candidate , dense-first pruning uses to obtain . Since , 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 for each entry , inserts the resulting pairs into both and , and marks all entries as seen (Line 1). It computes the query sparse norm once and initializes to the largest entry distance in (Lines 2–3). At each iteration, the algorithm removes from the unexpanded pair with the smallest distance (Lines 4–5); if is full and , traversal terminates because no remaining candidate can improve the current result set (Lines 6–7). Otherwise, it scans every outgoing neighbor , 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 (Line 12) and, when is full, uses , , and the stored norm to obtain
from Eq. (14); if , it skips without computing the exact sparse component (Lines 13–16). If is not yet full or , the algorithm computes and the exact hybrid distance (Lines 17–18). The result set retains at most closest vertices found so far, and is the distance of its farthest member (Lines 19–23). If is not full, is pushed directly into both and ; once is full, the pair is pushed only when , meaning that is closer than the current farthest member (Lines 19–20). If this insertion makes , the algorithm removes the farthest pair and updates to the largest remaining distance (Lines 21–23). When traversal terminates or becomes empty, the algorithm selects the pairs with the smallest distances in and returns their vertices as (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 . We first describe how the two paths obtain their entry points, and then present the -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 and , respectively. The retrieved results serve as the entry-point set for initializing the traversal in Algorithm 2; thereafter, UniGraph ranks and explores vertices using the query-specific hybrid distance . 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.
-Adaptive Execution
The guided search framework selects an execution path according to the query-level hybrid weight : 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 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
where 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 , 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- 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 or to approach the result region and then uses the query-specific hybrid distance 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 -adaptive policy further matches the entry-point strategy to the query’s dense-sparse weighting. For smaller values, results returned by the sparse guide index are more likely to include or lie near highly ranked hybrid results. For larger values, results returned by the dense guide index provide analogous guidance for dense-dominant queries. Taken together, guided initialization and -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 -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- and fixed- query weight settings. For each evaluated query–weight combination, we compute the exact hybrid top- result under Eq. (1) as ground truth.
| Dataset | Base | Queries | Dense Dim. | Avg. NNZ |
| NQ | 2.68M | 1,000 | 1024 | 66.0/10.7 |
| HotpotQA | 5.23M | 1,000 | 1024 | 44.2/17.5 |
| MS MARCO | 8.84M | 1,000 | 1024 | 47.7/7.2 |
| FEVER | 5.42M | 1,000 | 1024 | 66.2/11.5 |
| DBpedia-Entity | 4.64M | 467 | 1024 | 47.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- setting, and Recall@100 in the fixed- 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 (), repeat-
edly expands the neighbors of the current top- 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 .
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 , 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 to for HNSW, the two fixed-weight hybrid baselines, and UniGraph. The SINDI candidate count ranges from to . 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 to . For LADR, the adaptive expansion width ranges from 1 to 200. Table III summarizes the settings.
| Method | Parameter Settings |
| HNSW | Construction: ; construction beam size <br>Search: Candidate count |
| SINDI | Construction: Document pruning ratio <br>Search: Query pruning ratio |
| HNSW+SINDI | Construction: HNSW and SINDI settings as specified above<br>Search: Dense candidate count sparse candidate count; SINDI query pruning ratio |
| Naive Hybrid | Construction: ; ; |
| Opt Hybrid | Construction: ; ; ; hybrid neighbor expansion width <br>Search: dense-stage stopping threshold ; hybrid-stage stopping threshold ; no sparse vector pruning |
| LADR | Construction: HNSW and SINDI settings as specified above<br>Search: Lexical seed count ; SINDI query pruning ratio |
| UniGraph | Construction: ; dense/sparse candidate counts ; HNSW ; SINDI query pruning ratio ; ; <br>Search: ; guided-entry count guide-HNSW UniGraph ; SINDI query pruning ratio |
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- Setting. The mixed- 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 . We select this interval, because at more extreme weights such as or , the hybrid distance is determined primarily by only one modality.
Figure 5 compares the Recall-QPS trade-offs of all methods when varies across queries. At Recall@100 , UniGraph achieves 27.6%52.3% higher QPS than the fastest baseline across the five datasets. On NQ, UniGraph sustains about 1.7 the QPS of two-route at Recall@100 . A more pronounced advantage appears on FEVER, where UniGraph delivers about 3.0 the QPS of Naive Hybrid at Recall@100 . UniGraph also retains a clear advantage over LADR on DBpedia-Entity, providing an approximately 2.3 QPS speedup at Recall@100 .
Figure 5. Recall@50-QPS (top), Recall@100-QPS (middle), and Recall@200-QPS (bottom) trade-offs in the mixed- setting. The query weights are uniformly distributed over . Curves closer to the upper-right corner indicate better performance.
2) Fixed- Setting. The fixed- setting evaluates performance when all queries share the same weight. We consider five fixed weights: .
Figure 6 reports the Recall@100-QPS trade-offs at each fixed value. Among the two single-modality baselines, the sparse-only baseline achieves higher QPS at matched recall for smaller , whereas the dense-only baseline achieves higher QPS for larger . At Recall@100 , UniGraph achieves 1.182.85 the QPS of the fastest baseline, with a
Figure 6. Fixed- Recall@100-QPS trade-offs on NQ, MS MARCO, and DBpedia-Entity. The upper-right region is better.
geometric-mean speedup of 1.66 over all three datasets and five query weights. On NQ with , UniGraph delivers about 2.5 the QPS of the sparse-only baseline at Recall@100 . Compared with the fixed-weight hybrid graph baselines, UniGraph achieves 1.443.34 the QPS of Naive Hybrid and 1.402.26 that of Opt Hybrid in their comparable configurations. The advantage persists at , even though this query weight matches the construction weight of both Hybrid indexes. On MS MARCO with , UniGraph also provides about 2.1 the QPS of LADR at Recall@100 , consistent with the benefit of traversing the graph under the query-specific hybrid distance rather than dense scores alone. At on DBpedia-Entity, UniGraph maintains about 1.6 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.
| Dataset | HNSW+ SINDI | UniGraph | Naive Hybrid | Opt Hybrid | LADR |
| NQ | 438 | 918 | 910 | 1,175 | 442 |
| HotpotQA | 1,181 | 2,497 | 1,592 | 3,069 | 1,190 |
| MS MARCO | 1,418 | 2,946 | 2,265 | 3,155 | 1,428 |
| FEVER | 1,300 | 2,844 | 2,060 | 3,609 | 1,309 |
| DBpedia-Entity | 1,052 | 2,215 | 1,450 | 2,752 | 1,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 and dense-guided UniGraph search at . All variants use the same hybrid graph, pruning scale , and search beam size .
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 , sparse-guided UniGraph search improves recall by 7.4∼12.0 percentage points, averaging 9.7 points across the datasets. At , 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 . Panel (a) compares unguided and sparse-guided UniGraph search at , while panel (b) compares unguided and dense-guided UniGraph search at .
2) Hybrid Distance Pruning. For the hybrid distance pruning ablation, we use the mixed- setting to compare UniGraph search with dense-first hybrid distance pruning () 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 -adaptive routing policy. We set . The configuration without pruning disables only the pruning test in Eq. (14); candidate insertion and traversal termination still use the current result set threshold , 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- setting at .
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 for graph construction with . Query weights are uniformly distributed over . 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.
| Dataset | Recall@100 | Fixed-weight graph | UniGraph | Gain |
| MS MARCO | 0.90 | 150.96 | 189.39 | +25.46% |
| MS MARCO | 0.95 | 53.88 | 68.28 | +26.71% |
| FEVER | 0.90 | 92.73 | 104.85 | +13.07% |
| FEVER | 0.95 | 35.97 | 41.77 | +16.13% |
| DBpedia-Entity | 0.90 | 129.57 | 139.87 | +7.95% |
| DBpedia-Entity | 0.95 | 48.39 | 50.55 | +4.48% |
Table V. Graph-only QPS of the fixed-weight graph and UniGraph at matched Recall@100; higher is better.
Related Work
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 -cover construction to merge neighborhoods sampled at multiple weights. We further study -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 , UniGraph achieves 27.6%52.3% higher QPS than the fastest baseline on each dataset under mixed weights and 1.182.85 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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]——, “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]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]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]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]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]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]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]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.








