Sparse Pairwise Re-ranking with Pre-trained Transformers

Lukas Gienapp, Maik Fröbe, Matthias Hagen, Martin PotthastarXiv 2022 · DOI · arXiv

TL;DR

Pairwise re-ranking with transformers is highly effective but computationally prohibitive due to its $O(k^2)$ complexity. This paper demonstrates that by using Skip-Window sampling and Greedy aggregation, researchers can achieve competitive retrieval effectiveness while performing an order of magnitude fewer comparisons, effectively breaking the quadratic bottleneck.

What Problem Does This Paper Address?

In modern Information Retrieval (IR), we often use a multi-stage pipeline. First, a fast but "dumb" model like BM25 pulls a thousand candidates. Then, a pointwise transformer (like monoT5) scores each document individually to find the top 50. Finally, a pairwise transformer (like duoT5) compares pairs of these top documents to determine which is more relevant.

While pairwise models are the gold standard for accuracy—because they capture relative differences between documents—they are incredibly slow. Comparing every possible pair in a set of 50 documents requires 2,450 transformer inferences. This quadratic growth makes pairwise re-ranking impractical for real-time search. The authors ask: Can we "sparsify" these comparisons by sampling only a few pairs without losing the accuracy gains?

Methods

The authors investigate the "mono-duo" design pattern (Figure 1) and focus on two specific levers: Sampling (which pairs to compare) and Aggregation (how to turn those comparison results into a final ranked list).

Figure 1: The mono-duo design pattern for re-ranking. Parts investigated in this paper are highlighted in orange. Com- parisons omitted by sampling are striped.

Sampling Strategies

They tested three ways to pick pairs (visualized in Figure 2):

  1. Global Random (G-Random): Randomly selecting a fraction of all possible pairs.
  2. Neighborhood Window (N-Window): Comparing each document only to its immediate neighbors in the initial ranking.
  3. Skip-Window (S-Window): A hybrid approach that compares a document to successors at fixed intervals (e.g., every 3rd document). This ensures a mix of "local" and "global" context.

Aggregation Methods

Once you have sparse, potentially noisy comparison data, how do you rank the documents? The authors evaluated five methods, including KwikSort (a randomized sorting baseline), Additive (summing win probabilities), and Greedy Aggregation (iteratively picking the document with the highest "potential" to win remaining matches).

Datasets

The study used three standard large-scale retrieval benchmarks:

  • MS MARCO (Passage): A massive dataset of Bing search queries and web passages.
  • ClueWeb09 & ClueWeb12: Large-scale web crawls used in TREC (Text REtrieval Conference) tracks.

Key Insights and Ideas

  • Transformers are Inconsistent: A major "aha" moment was discovering that pairwise models like duoT5 are not perfectly transitive or consistent. If the model says $A > B$ and $B > C$, it might still say $C > A$. Furthermore, $P(A > B)$ does not always equal $1 - P(B > A)$.
  • Sorting Fails, Aggregation Wins: Because of this inconsistency, standard sorting algorithms like KwikSort performed poorly—often worse than the pointwise baseline. Robust aggregation methods that "work around" these contradictions are essential.
  • Locality is a Trap: N-Window sampling (only comparing close neighbors) performed the worst. The authors found that "global" context—comparing documents that are far apart in the initial ranking—is crucial for the model to understand the overall relevance landscape.
  • The Power of Sparsity: You don't need all the data. The effectiveness curves (Figure 4) show that performance stays relatively flat until you drop below 15-30% of total comparisons.
Effectiveness vs. Sampling Rate for different aggregators.

Key Results

  • The Winning Combo: Skip-Window sampling paired with Greedy aggregation was the most effective.
  • Efficiency Gains: On the MS MARCO dataset, this combination achieved competitive effectiveness with only 30% of the comparisons.
  • Speedup: By tolerating a very slight loss in nDCG@10 (only 0.04), they could use 10% of the comparisons—a 10x speedup over the exhaustive approach.
  • Scalability: The authors suggest that instead of just saving time, this efficiency could be used to re-rank deeper. For the same computational budget as a standard top-50 pairwise re-rank, a sparse approach could re-rank the top 157 documents.

Limitations and Future Work

  • Static Sampling: The pairs are chosen before any inferences are made. The authors suggest dynamic sampling—where the choice of the next pair depends on the results of previous comparisons—as a promising next step.
  • Domain Specificity: The improvements were most pronounced on MS MARCO (the dataset the models were trained on). Performance on the ClueWeb datasets was positive but less dramatic, likely due to the gap between passage-level ranking and document-level evaluation.
  • Inference Overhead: While the number of inferences is reduced, the overhead of the transformer itself remains high. Combining this sampling with model distillation or early-exiting techniques could yield even faster systems.

Summary updated

Abstract

Pairwise re-ranking models predict which of two documents is more relevant to a query and then aggregate a final ranking from such preferences. This is often more effective than pointwise re-ranking models that directly predict a relevance value for each document. However, the high inference overhead of pairwise models limits their practical application: usually, for a set of $k$ documents to be re-ranked, preferences for all $k^2-k$ comparison pairs excluding self-comparisons are aggregated. We investigate whether the efficiency of pairwise re-ranking can be improved by sampling from all pairs. In an exploratory study, we evaluate three sampling methods and five preference aggregation methods. The best combination allows for an order of magnitude fewer comparisons at an acceptable loss of retrieval effectiveness, while competitive effectiveness is already achieved with about one third of the comparisons.
BibTeX
@misc{gienapp2022sparse,
  author = {Lukas Gienapp and Maik Fröbe and Matthias Hagen and Martin Potthast},
  title = {{Sparse Pairwise Re-ranking with Pre-trained Transformers}},
  year = {2022},
  eprint = {2207.04470},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.04470},
}
Figure