acceptodds
Under review as a conference paper at ICLR 2027

A Wasserstein Barycenter Index For Efficient Rank Fusion

Abstract

Information retrieval pipelines routinely aggregate diverse base rankers, e.g., lexical, sparse, and dense, to exploit their complementary strengths. Classical fusion methods score query-document pairs pointwise and, therefore, typically ignore the relationships among retrieved documents in the embedding space. As a result, they treat near-duplicate clusters and genuinely complementary subsets alike. In this work, we recast rank fusion as a Restricted Support Wasserstein Barycenter (RSWB) problem that jointly optimizes the retrieved set and its ranking order. We then fix the support set and cast RSWB as a set-function objective. We further show that it is monotone and restricted submodular, yielding approximation guarantees for greedy maximization. However, the greedy algorithm requires an exhaustive search over the entire corpus during the marginal-gain computation step. Therefore, we approximate the marginal gain using an approximate nearest neighbor (ANN) index amenable to dot-product approximation. This reduces each greedy step to an approximate ANN search, enabling sublinear retrieval via off-the-shelf indices such as DiskANN and Faiss. Our experiments show that the proposed method achieves favorable trade-offs among ranking accuracy, corpus geometry, and query latency.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
submodular functions, Wasserstein barycenter, rank fusion, information retrieval

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Dj1FOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

WBFusion formulates rank fusion as a restricted-support Wasserstein barycenter problem, incorporating inter-document geometry into support selection and ranking. The paper establishes monotonicity and restricted weak submodularity, then learns a dot-product surrogate for ANN-assisted greedy selection, followed by supervised reranking. Experiments on five BEIR datasets report improved ranking quality, component ablations, and speedups over exact OT-based greedy selection.

Critical strengths
  1. Casting fusion as support-constrained barycenter optimization provides an explicit way to incorporate document geometry. The weak-submodularity analysis gives a meaningful foundation for greedy support selection.

  2. The method improves reported ranking performance across five datasets. Comparisons with no KL regularization and an RRF-based KL target help isolate the contribution of barycentric regularization within the same reranking architecture.

Critical weaknesses
  1. The approximation guarantee does not cover the implemented pipeline. Theorem 6 assumes uniformly accurate barycenter predictions and small cost oscillation, without establishing these conditions experimentally or bounding the required feature dimension. Theorem 7 further assumes exact maximum-inner-product retrieval and does not analyze the subsequent k′k'-to-kk filtering. Consequently, the stated end-to-end guarantee does not establish the accuracy of the practical ANN procedure
Questions for authors
  1. Which guarantee applies to Algorithm 4 with approximate ANN search and subsequent support filtering? How large are the surrogate and search errors under the experimental settings?
  2. What ranking quality and end-to-end latency does the complete ANN pipeline achieve on full corpora, including candidate generation and refinement, compared with standard fusion pipelines?
6 comments
AuthorsOpenReview ↗

Response from Authors Part 1

We thank the reviewer for their suggestions, which helped us improve our paper. We added the suggestions in the paper.

The approximation guarantee does not cover the implemented pipeline. Theorem 7 further assumes exact maximum-inner-product retrieval and does not analyze the subsequent (k')-to-(k) filtering. Consequently, the stated end-to-end guarantee does not establish the accuracy of the practical ANN procedure

We thank the reviewer for identifying the distinction between the sequence analyzed in Theorem 7 and the output after k′k'-to-kk filtering in Algorithm 4. We retain the original theorem as a guarantee for using the dot-product surrogate instead of the true marginals and add a separate result (Theorem 8 in Section 3.5 of our updated draft) that analyzes the true filtered output. We also show how the two results compose into a guarantee for the complete selection procedure.

The original theorem analyzes a singleton followed by k−1k-1 surrogate selections. The practical procedure instead constructs a larger pool Sk′S _{k'} and restarts selection within this pool. Write T1,…,TkT _1,\ldots,T _k for the supports produced during filtering.

Our new theorem for the filtered support allows the pool to be generated by arbitrary surrogate scores and approximate retrieval. For a fixed query q\boldsymbol{q}, let Fk⋆=max⁡A⊆D, ∣A∣=kF(q,A)F _k^\star=\max _{A\subseteq D,\,|A|=k}F(\boldsymbol{q},A) and γ\gamma be the weak submodularity ratio of FF. Our newly added theorem 8 says that: Fk⋆−F(q,Tk)≤E1+E2+E3,F _k^\star-F(\boldsymbol{q},T _k)\leq E _1 + E _2 + E _3, where

  • E1∝Fk⋆−F(q,T1)E _1 \propto F _k^\star-F(\boldsymbol{q},T _1)
  • E2∝Fk⋆−max⁡A⊆Sk′, ∣A∣=kF(q,A)E _2 \propto F _k^\star-\max _{A\subseteq S _{k'},\,|A|=k}F(\boldsymbol{q},A) and
  • E3∝∑t=1k−1(1−γk)k−1−t[max⁡s∈Sk′∖TtF(s∣Tt,q)−(F(q,Tt+1)−F(q,Tt))]E _3 \propto \sum _{t=1}^{k-1}\left(1-\frac{\gamma}{k}\right)^{k-1-t}\left[\max _{s\in S _{k'}\setminus T _t}F(s\mid T _t,\boldsymbol{q})-\left(F(\boldsymbol{q},T _{t+1})-F(\boldsymbol{q},T _t)\right)\right]

The three terms separate the effects of greedy selection, pool restriction, and imperfect filtering. E1E _1 is the remaining gap allowed by the greedy analysis after k−1k-1 additions from the initial singleton. E2E _2 accounts for the quality lost when the candidate pool excludes documents: it compares the best size-kk support in the original universe with the best size-kk support still available in the pool. E3E _3 is the cost of inexact selection, accumulating the shortfall between the best available marginal gain inside the pool and the gain actually selected at each filtering step. Exact greedy filtering makes E3E _3 zero, while retaining a globally optimal size-kk support makes E2E _2 zero.

This result does not require uniformly accurate barycenter predictions, small cost oscillation, or exact maximum-inner-product retrieval.

Theorems 7 and 8 can also be combined. Suppose k′≥kk'\geq k and the pool retains the surrogate's first kk distinct selections. Suppose its scores approximate the true marginal gains within O(ϵ)O(\epsilon) at all steps. If each retrieval returns an unselected item whose score is within O(η)O(\eta) of the maximum, then combining Theorems 7 and 8 gives us:

Fk⋆−max⁡A⊆Sk′, ∣A∣=kF(q,A)≤Fk⋆−F(q,Sk)≤E1+E2F _k^\star-\max _{A\subseteq S _{k'},\,|A|=k}F(\boldsymbol{q},A)\leq F _k^\star-F(\boldsymbol{q},S _k)\leq\mathcal E _1+\mathcal E _2, where E1=(1−γk)k−1[Fk⋆−F(q,S1)]\mathcal E _1=\left(1-\frac{\gamma}{k}\right)^{k-1}\left[F _k^\star-F(\boldsymbol{q},S _1)\right] and E2=O(ϵ+η)∑j=0k−2(1−γk)j\mathcal E _2=O(\epsilon + \eta)\sum _{j=0}^{k-2}\left(1-\frac{\gamma}{k}\right)^j.

For pool construction, E1\mathcal E _1 is the contribution for the surrogate's first kk selections, while E2\mathcal E _2 accumulates errors from scoring and ANN search. The factor O(ϵ+η)O(\epsilon + \eta) accounts for score-approximation and the additional retrieval error. Since the pool contains the surrogate's size-kk subset, the best size-kk subset of the pool cannot be worse than that prefix. This connects the original surrogate guarantee to the implemented filtering-based algorithm.

AuthorsOpenReview ↗

Response from Authors Part 2

Theorem 6 assumes uniformly accurate barycenter predictions and small cost oscillation, without establishing these conditions experimentally or bounding the required feature dimension.

We thank the reviewer for asking us to clarify these assumptions.

Small cost oscillation. To get an empirical estimate of cost oscillation in the data, we look at the spread of the cost matrix entries C[i,j]C[i,j] around their mean in terms of standard deviation and what percentage of the pairwise cost entries lies within a certain spread from the mean. We also report the absolute cost oscillation as min⁡/max⁡\min/\max.

Datasetstd/meanmean ±\pm 5%mean ±\pm 10%mean ±\pm 15%min⁡/max⁡\min/\max
MS-Marco0.03983.298.299.60.001
NF-Corpus0.08842.775.592.50.001
Hotpot-QA0.04874.096.399.20.001
Fever0.04873.996.299.20.001
SciFact0.07746.482.096.00.252

Since most of the cost matrix entries are concentrated around their mean in all the datasets, the assumption of small cost oscillation is empirically validated.

Barycenter-prediction accuracy. Theorem 6 assumes the Barycenter to be well approximated by a contextual softmax model having a specific parameterization. For each of the 5 datasets, we fit a contextual softmax model to the barycenter distributions. We report the per query mean KL divergence and TV distance of the true barycenter from the fitted softmax model.

MetricMS-MarcoNF-CorpusHotpot-QAFeverSciFact
KL divergence0.0700.0030.1060.0200.012
TV0.1440.0270.1680.0740.051

The goodness of fit indicates the plausibility of our softmax approximation assumption on the Barycenter.

Bounding feature dimension. The theorem actually comes up with a sufficient bound on the feature dimension through its proof. Note that we have an assumption of the barycenter being approximated by a softmax distribution, which we just empirically validated. If the feature dimension in that softmax approximator is dd, then our current proof naturally comes up with a sufficient feature dimension of O((ln⁡(1/ϵ))4d)O((\ln(1/\epsilon))^{4d}) for the dot product surrogate to achieve approximation of O(ϵ)O(\epsilon). But it should be noted that this is simply a theoretical upper bound, in practice we use neural features of dimension 128128.

Which guarantee applies to Algorithm 4 with approximate ANN search and subsequent support filtering?

In the above responses, we have discussed how the newly added theorem 8 (along with theorem 7) can give the guarantees for the filtering with surrogate, then exact greedy approach. For the ANN search, the only thing that changes is that, we retrieve the top 1 for each greedy step by probing the index (that we build using the trained surrogate) instead of exhaustive search. So if one assumes exact NN search, the guarantee applies verbatim.

AuthorsOpenReview ↗

Response from Authors Part 3

How large are the surrogate and search errors under the experimental settings?

Our final efficient search method admits two approximations: (1) Marginal gain to dot product approximation and (2) approximate nearest neighbor search from index built on the corpus vectors obtained in the dot product.

First, we isolate the effect of marginal gain to dot product approximation from ANN search, by performing exact NN search (compute exact minimum over distances) over the dot products. We obtain S^\hat{S} and compare the corresponding performance given by S∗S^{*} obtained from exact greedy. Given a metric M (M can be NDCG and MAP), we report (a) Err(M) as ∣M(S^)−M(S∗)∣/M(S∗)|M(\hat{S})-M(S^{*})|/M(S^{*}) (lower is better), (b) spearman rank correlation between M(S^)M(\hat{S}) and M(S∗)M(S^{*}) (higher is better) and Kendall Tau between M(S^)M(\hat{S}) and M(S∗)M(S^{*}) (higher is better).

MetricMS-MarcoNF-CorpusHotpot-QAFeverSciFact
NDCG@10: relative error (%)5.961.412.120.960.77
NDCG@10: Spearman rank correlation0.9760.9850.9310.9520.963
NDCG@10: Kendall Tau0.8790.9300.8980.9350.954
MAP@10: relative error (%)6.091.952.211.050.74
MAP@10: Spearman rank correlation0.9790.9770.9340.9520.963
MAP@10: Kendall Tau0.8850.9300.9040.9370.954

We observe that the relative error is very low and rank correlation metrics are very high. Therefore, items retrieved by maximizing exact marginal gains and exact NN search is close. Such high accuracy is possible because the dot product is only used to order the items. Hence, as long as the marginal gains and the dot products have similar order, our method performs well, even if dot products do not mimic the scores.

Next, we compare performance of (1) SS obtained by ANN search of the index and (2) corresponding performance given by S^\hat{S} obtained from exact NN. Following table shows the results, which show that ANN search well approximates exact NN search.

MetricMS-MarcoNF-CorpusHotpot-QAFeverSciFact
NDCG@10: relative error (%)1.283.741.693.463.06
NDCG@10: Spearman rank correlation0.9410.9470.8190.9400.958
NDCG@10: Kendall Tau0.8840.9150.8180.9350.957
MAP@10: relative error (%)4.515.581.233.302.98
MAP@10: Spearman rank correlation0.8930.9410.8190.9390.958
MAP@10: Kendall Tau0.8460.9170.8180.9350.957

What ranking quality and end-to-end latency does the complete ANN pipeline achieve on full corpora, including candidate generation and refinement, compared with standard fusion pipelines?

We report the end-to-end latency of the Fusion Baselines and compare it with WBFusion ANN pipeline. Note that search in the entire corpus is takes prohibitively large time, which is why we had first shortlisted base rankers top-100 items. Following is the time taken (in milliseconds) for retrieval averaged per-query. They show our method is fastest.

MethodMS-MarcoNF-CorpusHotpot-QAFeverSciFact
RRF63841923511748471660
CombSUM61011932508848171634
CombMNZ60261930484547071664
MoE60201940481446641697
Ensemble61671929499758061659
NeuralRRF60401956512456851631
Hybrid60891960493054951675
WBFusion ANN4888105730133128976

Suppose instead of initial shortlisting from base rankers, we use the entire corpus for retrieval. We now run WBFusion ANN on the index built on the entire corpus, which is quite fast. Then the latency (in seconds per query) numbers are given below.

MethodMS-MarcoNF-CorpusHotpot-QAFeverSciFact
RRF8736.12.74064.44386.25.1
CombSUM8631.92.54120.14315.45.4
CombMNZ8712.62.64078.64371.65.5
MoE8817.32.84166.54356.75.2
Ensemble8661.42.44115.34409.95.3
NeuralRRF8726.12.74053.34341.85.6
Hybrid8653.32.54130.74395.55.2
WBFusion ANN5.61.23.83.51.1

We observe that our method is faster than 1000x for large datasets like MS-Marco, Hotpot-QA and Fever.

We also show average ranking accuracy under the constraint that RSWB objective be within 50% of optimal (— = threshold not achieved). Following tables show the results, which show that we perform better.

NDCG@10MS-MarcoNF-CorpusHotpot-QAFeverSciFact
MoE0.5870.342—0.586—
Ensemble0.6250.290—0.8260.698
NeuralRRF0.6080.369—0.7080.684
Hybrid0.5660.333—0.5960.673
WBFusion ANN0.6740.3790.7180.8140.731
MAP@10MS-MarcoNF-CorpusHotpot-QAFeverSciFact
MoE0.1460.126—0.515—
Ensemble0.1510.104—0.7860.653
NeuralRRF0.1510.127—0.6430.635
Hybrid0.1410.116—0.5260.627
WBFusion ANN0.1630.1420.6340.7640.700
Reviewer_L9wEOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper turns each base ranker's scores into a softmax distribution over the candidate documents and defines the fused ranking as a doubly regularized entropic Wasserstein barycenter whose support is limited to kk documents (RSWB). Experiments use five BEIR datasets and six base rankers.

Critical strengths

Treating rank fusion as a set-level problem with a transport cost between documents is a reasonable idea, and I have not seen the barycenter used this way for fusion. Turning greedy marginal-gain search into repeated MIPS calls, so that the corpus side can be indexed once, is a useful trick and may apply to other set objectives. The paper also includes a fair number of ablations (reranker, KL anchor, λ\lambda and τ\tau, β\beta, z-score normalization) and a scaling study.

Critical weaknesses
  1. It is hard to tell how much of the accuracy gain comes from the barycenter. The final WBFusion score comes from a reranker built on a two-layer Transformer over query and document embeddings, the base scores, and a DeepSet summary of the support. Most trainable baselines are small MLPs or linear layers on the six scores. Table 12 shows that the same reranker with β=0\beta = 0 (no barycenter target) already reaches 0.669 NDCG on MS-Marco versus 0.673 with the barycenter, while the best baseline is 0.638. The pattern is similar on Hotpot-QA and SciFact, and on MS-Marco the barycenter even lowers MAP (Table 13). Only Fever and NF-Corpus show a clear gain from the barycenter. In addition, WBFusion (no rerank), which is the actual RSWB solution ν∗(q,S)\boldsymbol{\nu}^*(\boldsymbol{q}, S), is below MoE and Ensemble on every dataset (Table 8). A baseline that uses the same reranker architecture, trained without any fusion target, should be in Table 1.

  2. The efficiency claims are not tested at the scale the paper argues for. The "corpus" is a per-query candidate pool: the union of the base rankers' top-100 lists, or the RRF top-1000, and at most N=16,000N = 16{,}000 documents in the scaling study. So the base rankers have already done first-stage retrieval, and the ANN index is built over a small pool, not over a full corpus such as the 8.8M MS-Marco passages. The speedups are only measured against exact greedy and its lazy or stochastic variants. There is no absolute latency, and no comparison with RRF or CombSUM, which take almost no time. The offline cost of running exact greedy to build training targets is not reported either.

  3. The experimental setting is narrow. The dense rankers are MiniLM and a BERT cross-encoder. Stronger models such as SPLADE or ColBERT, cited in the introduction, are not used. Training uses at most 2,000 queries per dataset. Convex combination fusion (Bruch et al., 2023) and learned fusion methods from recent work are missing from the baselines.

Questions for authors

What are the absolute query latencies of WBFusion, exact greedy, and RRF, and what does it cost offline to build the training targets?

4 comments
AuthorsOpenReview ↗

Response from Authors Part 1

We thank the reviewer for their suggestions, which helped us improve our paper. We added the suggestions in the paper.

It is hard to tell how much of the accuracy gain comes from the barycenter... Table 12 shows that the same reranker with β=0\beta=0 (no barycenter target) already reaches 0.669 NDCG on MS-Marco versus 0.673 with the barycenter

Note that, even when we set β=0\beta=0, the subset SS is fed into the reranker as input, where SS is obtained by solving the Barycenter problem. Therefore, the signals from barycenter calculation are captured in the reranker via SS, even when β=0\beta=0. This means that the NDCG of 0.669 is obtained after incorporating the solution of Wasserstein Barycenter into the model. This signal is important since even a transformer based expressive network requires this subset as input to perform well. To illustrate this, we set β=0\beta=0 and select SS based on different methods: (1) our method, (2) top-k using RRF and (3) random selection. Then we feed SS into the reranker, along with qq and cc. Following tables shows that SS selected from Barycenter gives better result. Hence, merely a high capacity network is unable to perform well, unless we provide SS used by the Barycenter.

(NDCG@10)MS MARCONF-CorpusHotpot-QAFEVERSciFact
Random SS0.2280.1060.0500.0500.067
RRF based SS0.6240.3470.6970.8020.716
Our method0.6690.3560.7220.8110.745
(MAP@10)MS MARCONF-CorpusHotpot-QAFEVERSciFact
Random SS0.0280.0190.0400.0480.061
RRF based SS0.1540.1270.6130.7640.679
Our method0.1640.1360.6380.7670.708

A baseline that uses the same reranker architecture

We change the architectures of all baselines from MLP to transformer and compare them against our method.

(NDCG@10)MS MARCONF-CorpusHotpot-QAFEVERSciFact
Ensemble + Transformer0.5420.3390.6430.8270.713
NeuralRRF + Transformer0.5580.3530.6330.6860.672
Hybrid + Transformer0.5780.3530.5860.6070.677
WBFusion0.6730.3830.7280.8460.748
(MAP@10)MS MARCONF-CorpusHotpot-QAFEVERSciFact
Ensemble + Transformer0.1290.1240.5470.7860.673
NeuralRRF + Transformer0.1370.1280.5310.6160.625
Hybrid + Transformer0.1410.1240.4890.5380.634
WBFusion0.1630.1450.6470.8140.712

We see that WBFusion is better.

what does it cost offline to build the training targets?

The following table measures cost of generating the data to train the surrogates. We generate data by running greedy algorithm after shortlisting top-100 items from each base rankers. We observe that shortlisting allows reasonable time for data gathering.

DatasetPer-query time
MS-Marco41.8s
NF-Corpus11.5s
Hotpot-QA33.4s
Fever25.1s
SciFact19.9s
AuthorsOpenReview ↗

Response from Authors Part 2

The speedups are only measured against exact greedy and its lazy or stochastic variants. There is no absolute latency, and no comparison with RRF or CombSUM, which take almost no time + What are the absolute query latencies of WBFusion, exact greedy, and RRF?

We report the end-to-end latency of the Fusion Baselines and compare it with WBFusion ANN pipeline. Note that search in the entire corpus is takes prohibitively large time, which is why we had first shortlisted base rankers top-100 items. Following is the time taken (in milliseconds) for retrieval averaged per-query. They show our method is fastest.

MethodMS-MarcoNF-CorpusHotpot-QAFeverSciFact
RRF63841923511748471660
CombSUM61011932508848171634
CombMNZ60261930484547071664
MoE60201940481446641697
Ensemble61671929499758061659
NeuralRRF60401956512456851631
Hybrid60891960493054951675
WBFusion ANN4888105730133128976

Suppose instead of initial shortlisting from base rankers, we use the entire corpus for retrieval. We now run WBFusion ANN on the index built on the entire corpus. Then the latency (in seconds per query) numbers are given below.

MethodMS-MarcoNF-CorpusHotpot-QAFeverSciFact
RRF8736.12.74064.44386.25.1
CombSUM8631.92.54120.14315.45.4
CombMNZ8712.62.64078.64371.65.5
MoE8817.32.84166.54356.75.2
Ensemble8661.42.44115.34409.95.3
NeuralRRF8726.12.74053.34341.85.6
Hybrid8653.32.54130.74395.55.2
WBFusion ANN5.61.23.83.51.1

We observe that our method is faster by upto 1000x for large datasets like MS-Marco, Hotpot-QA and Fever.

We now show average ranking accuracy that gives RSWB objective to be within 50% of optimal (— = threshold not achieved). Following tables show the results, which show that we perform better.

NDCG@10MS-MarcoNF-CorpusHotpot-QAFeverSciFact
MoE0.5870.342—0.586—
Ensemble0.6250.290—0.8260.698
NeuralRRF0.6080.369—0.7080.684
Hybrid0.5660.333—0.5960.673
WBFusion ANN0.6740.3790.7180.8140.731
MAP@10MS-MarcoNF-CorpusHotpot-QAFeverSciFact
MoE0.1460.126—0.515—
Ensemble0.1510.104—0.7860.653
NeuralRRF0.1510.127—0.6430.635
Hybrid0.1410.116—0.5260.627
WBFusion ANN0.1630.1420.6340.7640.700

Stronger models such as SPLADE or ColBERT.

We consider four base rankers: {SPLADE, ColBERTv2, TF-IDF, Bert Cross-Encoder} and obtain results for all baselines, which show we are better.

NF-CorpusSciFactFever
MethodMAPNDCGMAPNDCGMAPNDCG
Best base ranker0.1330.3500.6590.7020.7630.807
RRF0.1230.3340.6370.6840.6280.707
CombSUM0.1320.3500.6600.7040.7270.781
CombMNZ0.1280.3450.6580.7020.7270.781
MoE0.1320.3500.6720.7120.7780.822
Ensemble0.1340.3530.6710.7110.7970.837
NeuralRRF0.1280.3460.6540.6950.7670.812
Hybrid0.1320.3480.6520.6970.7500.797
WBFusion0.1370.3590.7350.7680.8290.862

Hybrid is convex combination, which learns the weights. Also, MoE, NeuralRRF, Ensemble are all learned fusion baselines.Next, we show trade-off between ranking accuracy and the rank fusion quality in terms of optimal RSWB F(S)F(S), where the optimal barycenter weights are determined by the reranker scores.

First we show Avg. MAP and NDCG subject to the constraint that F(S)F(S) is within 30% of optimum (— means it did not reach the threshold).

MethodNF-Corpus (MAP)NF-Corpus (NDCG)Fever (MAP)Fever (NDCG)SciFact (MAP)SciFact (NDCG)
MoE0.1220.329——0.6700.709
Ensemble0.0940.268——0.6220.668
NeuralRRF0.1270.344——0.6510.693
Hybrid0.1200.318——0.6100.656
Ours0.1360.3560.8270.8600.7220.756

We constrain ranking accuracies to be within 30% of the optimal and report the maximum constrained rank fusion quality as FMAP, FNDCG.

MethodNF-Corpus (FMAP)NF-Corpus (FNDCG)Fever (FMAP)Fever (FNDCG)SciFact (FMAP)SciFact (FNDCG)
MoE2.2972.297-0.239-0.2392.2332.233
Ensemble2.2872.287-0.252-0.2522.2692.269
NeuralRRF2.2432.243-0.260-0.2602.1602.160
Hybrid2.3532.353-0.264-0.2642.3582.358
Ours2.3592.359-0.122-0.1222.3632.363

In both cases, we show that our model achieves better trade-off between rank fusion quality as measured by the RSWB objective, and downstream retrieval.

AuthorsOpenReview ↗

Additional results for rank fusion on stronger base rankers

In this response we give additional results on rank fusion using stronger base rankers: {SPLADE, ColBERTv2, TF-IDF, Bert Cross-Encoder}. Due to compute limitations, we were only able to report the results on Fever, Scifact and NF Corpus in our earlier response. However we kept the experiments running for the two larger datasets of MS-MARCO and HotpotQA. We report ranking accuracy and rank fusion quality for WBFusion and baseline rank fusion methods on these two datasets in this response.

We first report the ranking accuracy of WBFusion compared to baselines, where we see we are better.

MS-MarcoHotpot-QA
MethodMAPNDCGMAPNDCG
Best base ranker0.1670.6860.6590.745
RRF0.1680.6670.6130.707
CombSUM0.1590.6520.6380.727
CombMNZ0.1580.6510.6370.727
MoE0.1650.6720.6570.742
Ensemble0.1670.6880.6600.747
NeuralRRF0.1720.6900.6370.727
Hybrid0.1680.6910.6050.697
WBFusion0.1720.7040.6620.748

We now show trade-off between ranking accuracy and the rank fusion quality in these two datasets, like before. The ranking accuracy is measured in MAP @ 10 and NDCD @ 10 while the rank fusion quality is measured by the RSWB score F(S)=max⁡ν∈ΔS−W(ν)F(S) = \max _{\nu\in\Delta_S} -W(\nu), where the optimal barycenter weights are determined by the reranker scores.

First we show Avg. MAP and NDCG subject to the constraint that RSWB objective is within 30% of optimum (— means it did not reach the threshold).

MethodMS-Marco (MAP)MS-Marco (NDCG)Hotpot-QA (MAP)Hotpot-QA (NDCG)
MoE0.1520.625——
Ensemble0.0870.397——
NeuralRRF0.1710.688——
Hybrid0.1090.462——
WBFusion0.1710.7000.6590.744

We now constrain ranking accuracies to be within 30% of the optimal and report the maximum constrained rank fusion quality (measured by the RSWB objective) as FMAPF _{MAP}, FNDCGF _{NDCG}.

MethodMS-Marco (FMAPF _{MAP})MS-Marco (FNDCGF _{NDCG})Hotpot-QA (FMAPF _{MAP})Hotpot-QA (FNDCGF _{NDCG})
MoE8.0168.016-0.270-0.270
Ensemble8.0418.041-0.287-0.287
NeuralRRF8.0558.055-0.289-0.289
Hybrid8.0288.028-0.297-0.297
WBFusion8.0568.056-0.065-0.065

Thus, in the larger corpora of MS Marco and Hotpot QA as well, we observe that our model achieves better trade-off between rank fusion quality as measured by the RSWB objective, and downstream retrieval performance. We have included these additional numbers in Appendix G.11 of our updated draft.

We hope these set of additional results, along with our main rebuttal sufficiently address the concern of the reviewer regarding how WBFusion performs compared to state of the art rank fusion methods when stronger models such as SPLADE or ColBERT are included in the base ranker pool. We empirically show that WBFusion is better.

Hi,

Since we only have barely few hours left for the discussion period, we would request an acknowledge from the reviewer. We really hope to get responses from the reviewer.

Thanks in advance and we hope to hear from you.

Best,

Authors.

Reviewer_oSmnOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper recasts rank fusion as a Restricted Support Wasserstein Barycenter (RSWB) problem that jointly optimizes the retrieved set and its ranking order. The authors mianly reslove the rank fusion problem of various rankers. The problem is interesting and worthy researching. Transfering the problem to RSWB problem is a good direction. The paper presents comprehenseive proofs and experimental results. Overall, the quality of the paper is good. However, my main concern is that its accuracy limit is constrained by the existing rankers, and the approximate search decreases accuracy.

Critical strengths
  1. The paper is well-written, and it addresses an interesting, timely problem in rank fusion for multi-source retrieval pipelines. The limitation of classical pointwise fusion is clearly identified.
  2. The theoretical proofs are comprehensive and the empirical studies are solid. The submodularity analysis provides sound theoretical grounding for the greedy solver, and the experiments demonstrate the method’s ability to balance ranking quality and inference latency.
  3. Transferring the rank fusion problem to the Restricted Support Wasserstein Barycenter (RSWB) problem is novel. It offers a principled way to jointly optimize the retrieved set and ranking order, different from existing fusion paradigms.
Critical weaknesses
  1. The accuracy upper bound of the approach is constrained by the performance of the input base rankers, as the method only performs fusion on top of fixed pre-trained rankers. Jointly considering the update of base rankers together with the fusion process would make the overall solution more solid and expressive.
  2. I am concerned about the potential accuracy loss caused by approximate search techniques adopted to speed up the greedy steps. It is important to better characterize how ANN approximation errors affect the marginal gain calculation and the final rank fusion results.
  3. I am curious whether this fusion framework can be extended to other retrieval problems like vision retrieval (dense &parse or quantization&hashing). Since visual retrieval exhibits distinct embedding distributions and ranking properties compared with text retrieval, it is worth exploring whether the core RSWB formulation and greedy approximation strategy still hold effective in such settings.
Questions for authors

Please see the weaknessses.

6 comments
AuthorsOpenReview ↗

Response from Authors Part 1

We thank the reviewer for their suggestions, which helped us improve our paper. We added the suggestions in the paper.

Jointly considering the update of base rankers together with the fusion process would make the overall solution more solid and expressive.

This is a superb suggestion. In fact, we did think about this. However, during our experiments, we did not see much advantage of such joint training. This might be because the network of barycenter (ν)(\nu) is expressive enough that it learns to capture the signal that the trained base rankers might capture, via RSWB optimization and supervised fine tuning.

NDCG@10

MethodMS-MarcoNF-CorpusHotpot-QAFeverSciFact
WBFusion (frozen base rankers)0.6730.3830.7280.8460.748
WBFusion (joint training)0.6660.3520.7220.8390.810

MAP@10

MethodMS-MarcoNF-CorpusHotpot-QAFeverSciFact
WBFusion (frozen base rankers)0.1630.1450.6470.8140.712
WBFusion (joint training)0.1630.1260.6390.8010.781

We notice that in four out of five datasets,frozen base rankers are better or comparable.

A motivating use case is enterprise search, where different teams handle different rankers; and due to organizational policy, the models for different rankers are never shared across teams. Instead, they only share the scores. Such access control prevents joint training. Of course, as the reviewer pointed out joint training of barycenter and rerankers is really a solid direction. Therefore, we included them in the paper.

I am concerned about the potential accuracy loss caused by approximate search techniques adopted to speed up the greedy steps. It is important to better characterize how ANN approximation errors affect the marginal gain calculation and the final rank fusion results.

Our final efficient search method admits two approximations: (1) Marginal gain to dot product approximation and (2) approximate nearest neighbor (ANN) search from index built on the corpus vectors obtained in the dot product, which substitutes exact nearest neighbor search.

First, we isolate the effect of marginal gain to dot product approximation from ANN search, by performing exact NN search (compute exact minimum over distances) over the dot products. We obtain S^\hat{S} and we compare the corresponding performance given by S∗S^{*} obtained from exact greedy. Given a metric M (M can be NDCG and MAP), we report (a) relative error in MM as ∣M(S^)−M(S∗)∣/M(S∗)|M(\hat{S})-M(S^{*})|/M(S^{*}) (lower is better), (b) spearman rank correlation between M(S^)M(\hat{S}) and M(S∗)M(S^{*}) (higher is better) and ( c ) Kendall Tau between M(S^)M(\hat{S}) and M(S∗)M(S^{*}) (higher is better). Following table shows the results.

MetricMS-MarcoNF-CorpusHotpot-QAFeverSciFact
NDCG@10: relative error (%)5.961.412.120.960.77
NDCG@10: Spearman rank correlation0.9760.9850.9310.9520.963
NDCG@10: Kendall Tau0.8790.9300.8980.9350.954
MAP@10: relative error (%)6.091.952.211.050.74
MAP@10: Spearman rank correlation0.9790.9770.9340.9520.963
MAP@10: Kendall Tau0.8850.9300.9040.9370.954

We observe that the relative error is very low and rank correlation metrics are very high. Therefore, items retrieved by maximizing exact marginal gains and exact NN search is close. Such high accuracy is possible because the dot product is only used to order the items. Hence, as long as the marginal gains and the dot products have similar order, our method performs well, even if dot products do not mimic the scores.

Next, we compare performance of (1) SS obtained by ANN search of the index and (2) corresponding performance given by S^\hat{S} obtained from exact NN. Following table shows the results, which show that ANN search well approximates exact NN search.

MetricMS-MarcoNF-CorpusHotpot-QAFeverSciFact
NDCG@10: relative error (%)1.283.741.693.463.06
NDCG@10: Spearman rank correlation0.9410.9470.8190.9400.958
NDCG@10: Kendall Tau0.8840.9150.8180.9350.957
MAP@10: relative error (%)4.515.581.233.302.98
MAP@10: Spearman rank correlation0.8930.9410.8190.9390.958
MAP@10: Kendall Tau0.8460.9170.8180.9350.957
AuthorsOpenReview ↗

Response from Authors Part 2

I am curious whether this fusion framework can be extended to other retrieval problems like vision retrieval (dense &parse or quantization&hashing). Since visual retrieval exhibits distinct embedding distributions and ranking properties compared with text retrieval, it is worth exploring whether the core RSWB formulation and greedy approximation strategy still hold effective in such settings.

We ran our method and baselines on the MS-COCO dataset. Our method is focused on ANN design for wasserstein barycenter. Hence, we considered 113,287 images as corpus and their captions as query, with 8000 training, 1024 validation and 512 test queries. Our base rankers were Dense (CLIP ViT-L/14), Sparse (BLIP-D2S), PQ (SigLIP ViT-B/16 with 96 eight-bit subquantizers fitted on embeddings from 16,000 images) and Hashing (Kakao Brain's ALIGN base model with 2048-bit Gaussian hyperplane hashing). We train all rank fusion methods such that they achieve approximately similar RSWB objective. We report numbers for two combinations: {Dense, Sparse}, and {Dense, Sparse, Hashing, PQ}. Following tables show the numbers which show that we are better.

Dense+Sparse

MethodNDCG@10 ↑MAP@10 ↑RSWB ↓
WBFusion0.1160.109-1.093
Ensemble0.0610.056-1.049
Hybrid0.0600.058-1.047
MoE0.0640.060-1.049
NeuralRRF0.0640.060-1.048

All four

MethodNDCG@10 ↑MAP@10 ↑RSWB ↓
WBFusion0.0840.079-1.129
Ensemble0.0240.020-1.078
Hybrid0.0550.052-1.077
MoE0.0560.051-1.082
NeuralRRF0.0580.052-1.081

Here, rank fusion needs to preserve the ranking performance under the pressing challenge that the query caption has one labeled positive item in the entire corpus of 100K+ images. This makes the rank fusion problem (under low RSWB objective) quite challenging, resulting in low NDCG and MAP.

AuthorsOpenReview ↗

Further results on vision retrieval

In the above, we presented our results on MS COCO in response to the reviewer's question about the possibility of extending the results to vision retrieval tasks. We now put our results on Flickr30k images. The corpus consisted of 31783 images and the goal was to find the image corresponding to a caption, as in MS COCO. Like COCO, each test query had exactly one labeled postive. Following tables show the results. Our method performs better.

Dense+Sparse

MethodNDCG@10 ↑MAP@10 ↑RSWB ↓
WBFusion0.3500.326-1.046
Ensemble0.2170.200-0.987
Hybrid0.2190.204-0.988
MoE0.1950.178-0.986
NeuralRRF0.2130.195-0.987

Dense+Sparse+PQ+Hashing

MethodNDCG@10 ↑MAP@10 ↑RSWB ↓
WBFusion0.2200.213-2.114
Ensemble0.1790.169-2.043
Hybrid0.1930.179-2.052
MoE0.2040.186-2.052
NeuralRRF0.2160.200-2.051

Comments on the paper

1 comment

We are sorry to bother again. Since the rebuttal is going to end soon, we would appreciate a response from the reviewers. We addressed all the concerns of the reviewers and added all the discussions in the paper.

It would be great if the reviewers kindly get back.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.