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).
Sampling Strategies
They tested three ways to pick pairs (visualized in Figure 2):
- Global Random (G-Random): Randomly selecting a fraction of all possible pairs.
- Neighborhood Window (N-Window): Comparing each document only to its immediate neighbors in the initial ranking.
- 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.
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