CS Paper Radar

When Greedy Is Sorting: Exact and Certified Ideal Rankings for Novelty Metrics

Kehan Liu, Zhaoyun Chen, Xianquan Yan

cs.IR ·submitted 2026-11-07 08:30 UTC · v1

Abstract

The ideal ranking that normalizes novelty metrics is NP-hard to compute in general, so widely used $α$-nDCG evaluators approximate its denominator with a greedy rule that rescans every remaining document at each rank. We identify a regime in which this ideal ranking is exact and cheap for both $α$-DCG and intent-aware expected reciprocal rank (ERR-IA). When each document is positively judged for at most one intent, each metric reduces to the classical allocation of a fixed budget across chains of decreasing marginal gains. A metric-specific virtual-score transformation followed by a multiway merge, which we call ChainMerge, returns the globally optimal top-$K$ ranking in $O(G+K\log G)$ time from $G$ preordered intent groups, or in $O(n+K\log G)$ time from $n$ globally preordered candidates, instead of the $Θ(nK)$ of the greedy rule. When intent judgments overlap, exact $α$-DCG optimization is NP-hard under the standard logarithmic discount and $α=0.5$, even when every document has three intents and every intent occurs in two documents. For arbitrary overlap, a polynomial-size LP over nested ranking prefixes upper-bounds the ideal score and certifies the optimality gap of any feasible ranking. In the official TREC Web 2009-2012 judgments, 64.8% of positive documents serve a single intent, yet only 20 of 198 complete queries do so throughout. Beyond this exact regime, the LP certifies 189 of the 198 greedy denominators as globally optimal, and the resulting score intervals preserve the winner in all eight matched comparison groups. On 65,238 MIND-small candidates, ChainMerge returns identical optimal objectives 17-1,011 times faster than the greedy rule. For $α$-DCG, these results trace the hardness of the ideal ranking to intent overlap.

Closest papers

Nearest neighbours by meaning across the whole index.

Rank-Deviation Quality: A Distance-Aware Metric for Multi-Answer Retrieval and Ranking Evaluation

cs.IR ·2026-08-26 ·Xiaokun Zhou, Alessandro Moschitti, Danielle Class
similarity 0.59
Abstract

We introduce Rank-Deviation Quality (RDQ), an evaluation metric for retrieval and ranking systems that adapts to queries with varying numbers of reference items, from a single correct answer to many valid results. RDQ scores a candidate ranking against an ordered reference list (ORL): each retrieved reference item contributes its output-position weight multiplied by a rank-deviation penalty, and items outside the ORL receive zero credit. Application-specific parameters control tolerance to misordering. Larger values emphasize retrieving valid reference items, whereas smaller values place more weight on matching their reference order. The output-position weights can reflect visibility in the application's interface, such as a vertical list or a carousel. Unlike metrics that require absolute relevance grades, RDQ operates on ordinal rankings, which annotators can produce through pairwise or listwise judgments. Unlike rank-correlation measures such as Kendall's tau, RDQ accounts for both which items are returned and how they are ordered. On a 5,000-query point-of-interest (POI) dataset with 12 systems, RDQ has the highest median empirical power@100 among the 13 evaluated metric configurations. It reaches mean tau >= 0.8 agreement with its own full-query ordering at 200 queries; RBP(0.9), the strongest tested non-RDQ configuration, reaches the same threshold at 250. On TREC Deep Learning benchmarks, where NDCG uses native graded labels and RDQ uses ordinal tiers derived from them, RDQ reaches comparable median power at n=25, while NDCG is higher at n=100.

0.54

The Recall Ceiling of LLM Recommendation Reranking

cs.IR cs.LG ·2026-08-27 ·Zhaohui Wang
top venuetheory similarity 0.59
Abstract · 11 pages, 1 figure, 8 tables. Accepted for oral presentation at CIKM 2026

Some LLM-based recommendation rerankers are evaluated under an oracle protocol that guarantees the ground-truth item is present in the scored set, either by injecting it into the candidate list or by scoring it against sampled negatives. Across three primary Amazon datasets, we show that this protocol overestimates realistic NDCG@10 by 92--95%. The cause is a recall ceiling: realistic retrieval covers only 2--19% of relevant items at $K=100$ across eight datasets in three domains, imposing a deterministic upper bound on any closed-candidate reranker's top-$k$ NDCG. Under leave-one-out evaluation, $\mathbb{E}[\mathrm{NDCG}@k] \leq \mathrm{Recall}@|W_π|$, where $W_π$ is the reranker's candidate window. Under realistic retrieval, none of the tested optimisation strategies significantly improves over the collaborative-filtering baseline on our primary Amazon datasets. These strategies include prompt engineering, model scaling over a 168$\times$ parameter range, sequential models, supervised neural rerankers, LoRA fine-tuning, hybrid retrieval, score-aware prompting, and LLM+CF fusion. Text-aware retrieval increases recall on one dataset but does not improve end-to-end NDCG, while providing upstream CF scores mainly makes the LLM reproduce the CF order. We therefore propose the Recall-Aware Evaluation Protocol (RAEP): first classify the retrieval-recall regime, then evaluate reranking where the ceiling permits meaningful differentiation. In the low-recall regimes measured here, improving retrieval is more consequential than increasing reranker sophistication; this ordering need not hold in production systems with higher recall, richer features, or online feedback.

0.43

Equal Ranking Quality, Different Decisions: Measuring and Reducing Order Dependence in LLM Scorers

cs.CL cs.IRcs.LG ·2026-08-27 ·Markus Frohmann, Mahdiyar Ali Akbar Alavi, Elizabeth Lingg, Navid Rekabsaz
code/datahot direction similarity 0.59
Abstract · 9 pages main text, 45 pages total

In passage reranking, response ranking and multi-document question answering, LLMs can score several candidate documents or responses together in one prompt, each still receiving its own score. Such scorers are selected on ranking quality, but their scores determine a decision: what a score threshold retains, a reader answers, or which chosen/rejected pair enters preference training. Because the candidates share that prompt, reordering them changes their scores. The same query over the same candidates should still yield the same decision. However, equal ranking quality does not imply equal decisions: on passage reranking, five trained scorers within 0.010 nDCG@10 retain sets that overlap by only 0.66-0.84 when reordered. No prompt-time change we test resolves that dependence: the only one that improves ranking quality does not measurably improve decision stability. We introduce order-consistency SFT (OC-SFT), which attenuates it in the weights by penalizing disagreement between a candidate's scores across orderings. It holds ranking quality and leads every decision-stability measure among trained scorers on all three tasks. It is also more stable on 12 base models than order-averaged distillation, which trains on labels averaged across permutations. One OC-SFT permutation retains sets that overlap more than ten averaged off-the-shelf permutations. A comparison of such scorers should therefore report what a threshold retains and a reader answers, not ranking quality alone. Code is available at https://github.com/thomsonreuters/presentation-dependence.

0.68

BoundaryMORPH: Budgeted Reranking via Active Set Selection for Diffuse Retrieval

cs.IR ·2026-09-23 ·Eylon Caplan, Shamik Roy, Shib Sankar Dasgupta, Yingfan Wang, Rashmi Gangadharaiah
similarity 0.58
Abstract · Under review

Open-ended queries in modern Retrieval-Augmented Generation (RAG) are increasingly "diffuse," requiring a large set of documents to be assembled into a finite LLM context window. To ensure retrieval quality, systems use fast dual-encoders and more expensive cross-encoders (CEs) to score candidates. However, the CE budget $B$ is strictly bounded by latency and is often smaller than the context window capacity $k$. This mismatch makes standard reranking structurally flawed: it wastes compute verifying obvious top candidates while ignoring relevant documents further down the initial ranking. To address this, we introduce BoundaryMORPH, a novel algorithm that allocates CE budget specifically for the LLM's context capacity $k$. Using a Gaussian Process, BoundaryMORPH treats the initial dual-encoder ranking as a structural prior and intelligently spends CE calls on resolving top-$k$ set membership at the boundary, rather than seeking a single most-relevant document. Information from each CE call propagates to unscored documents, maximizing the utility of the budget. We demonstrate that BoundaryMORPH achieves state-of-the-art set retrieval quality across multiple models and datasets with open-ended queries ($+5.4$ nCG@100 over the strongest baseline).

0.15

Rubric-Calibrated Preferences: Cross-Query Calibration of LLM Judgments via Item Response Theory

cs.IR ·2026-09-28 ·Fabian David Schmidt, Donato Crisostomi, Carlos Lassance, Nils Reimers
benchmarkcode/data similarity 0.58
Abstract · 51 pages. Code and data: https://github.com/cohere-ai/rcp-ndcg

Rerankers decide which documents users and LLMs see, yet their standard metric, nDCG, relies on human relevance labels that are costly, sparse, noisy, and discretely graded. As rerankers approach each other in quality, nDCG on these labels therefore increasingly fails to separate them. LLM judges could supply dense labels. Relative judgments within one query tell even close candidates apart, yet their scores share no scale across queries. Absolute grades share one scale but are too coarse to distinguish documents of similar relevance. We propose Rubric-Calibrated Preferences (RCP), which combine both kinds of judgment. A listwise Bradley-Terry tournament orders each query's documents, and a rubric of yes/no criteria of increasing stringency provides an absolute standard. Item Response Theory (IRT), which scores test-takers based on their answers to common questions, then uses the shared criteria to put all queries' tournament scores on one scale. RCP's retrieval metric, RCP-nDCG, replaces nDCG's discrete labels with the resulting calibrated relevance probabilities. Against blind grades from 46 external annotators, calibration raises the correlation between a query's mean score and its mean human grade from 0.538 to 0.795. The probabilities rank a useful document above a non-useful one with probability 0.910 (AUC, chance 0.5), versus 0.651 for the benchmark labels. When the annotators' grades prefer one of two rerankers and exactly one metric agrees, that metric is RCP-nDCG in 72.4% of 185 comparisons (chance about 53%). On TREC-DL, RCP-nDCG sides with NIST assessors' grades on every reranker pair that these grades separate significantly. RCP-nDCG also resolves many of nDCG's ties and separates 1.9 times as many reranker pairs on NanoBEIR. Rubric calibration thus turns relative LLM judgments into dense relevance labels that are comparable across queries and agree with human judgment.

0.28

Yuanbao-Reranker: Document-Grounded Synthesis and Preference Distillation for Text Reranking

cs.IR ·2026-11-07 ·Hongyuan Xu, Dezhi Ye, Jiahao Cao, Jie Liu, Haijin Liang +2 more
similarity 0.57
Abstract · 23 pages, 6 figures, 7 tables

High-precision text reranking is a critical component in modern search, recommendation, and agentic retrieval-augmented generation (RAG) systems. We present Yuanbao-Reranker, a family of general-purpose dense rerankers spanning 0.6B, 4B, and 8B parameter scales built upon the Qwen3 backbone. To construct diverse and reliable ranking supervision at scale, we pair answer-first and query-type-guided document-grounded synthesis with a three-stage curation funnel that verifies positive support, eliminates semantic redundancy, and enforces balanced source-by-length quotas. For each curated pair, we screen real retrieval pools with a teacher score margin to filter out potential false negatives and sample Hard, Medium, and Moderate negative tiers, yielding 2.75M $1{:}3$ ranking groups. We train the models by jointly optimizing pointwise relevance cross-entropy and a bounded minimum-gap hinge objective over both positive--negative and negative--negative pairs. This formulation transfers fine-grained teacher preferences across candidate tiers without over-constraining well-separated predictions, supporting both cross-scale and same-scale distillation followed by layerwise adaptive model merging. Across five comprehensive benchmarks spanning Chinese (CMTEB-R), multilingual (MMTEB-R), English (BEIR), long-document (MLDR), and code (MTEB-Code) retrieval, Yuanbao-Reranker consistently leads every parameter tier: the 0.6B variant reaches 70.96 Avg. to surpass 1B--4B active-parameter baselines, the 4B variant reaches 73.63 Avg. to outperform the 8B teacher (72.68), and the 8B variant achieves a state-of-the-art 74.21 Avg., with substantial gains generalizing across distinct first-stage retrievers.

0.24

OneTrans-GSR: A Generative Slate Ranking Paradigm Unifying Reranking and Mix-Ranking with One Autoregressive Transformer

cs.IR ·2026-11-03 ·Feng Cheng, Yu-Hsuan Huang, Fengyi Wang, Chaofan Zhou, Zhennan Zhu +11 more
community pick similarity 0.57
Abstract · 26 pages, 6 figures, 11 tables

Industrial recommender systems allocate substantial computation to pointwise candidate scoring, yet separate reranking and mix-ranking stages still assemble the final exposure slate using hand-crafted rules and specialized low-capacity models. Mix-ranking combines product cards, short videos, livestreams, and advertising cards supplied by distinct upstream business channels. Although these rules and models encode valuable domain knowledge, they are inherently limited in leveraging additional data and computation. They constrain the combinatorial space of candidate slates and determine objective trade-offs through manual tuning. To enable scalable and effective slate generation, we reformulate reranking and mix-ranking as a unified learning problem whose performance can improve with computation. Specifically, we instantiate this formulation across the reranking and mix-ranking stages and propose OneTrans-GSR, a single decoder-only policy that extends our deployed OneTrans backbone to generate the exposure slate end-to-end. During training, a reward model evaluates complete slates and guides reinforcement learning toward slate-level and long-term objectives. During decoding, business constraints are explicitly enforced. Offline evaluation shows that slate quality consistently improves as reward-model and policy compute increase. Deployed in a large-scale industrial recommendation system, OneTrans-GSR mixes heterogeneous content types within a unified slate. In online A/B tests, it improves GMV/u by 2.63%, advertiser value by 2.06%, and repurchase rate by 2.03%, while reducing end-to-end latency across the reranking and mix-ranking stages by 13%. These results mark a paradigm shift in slate generation: moving beyond human-engineered heuristics toward a general learned policy creates a scalable path for further algorithmic optimization and compute-driven improvement.

0.38

Deal With It: On Better Schedules for Listwise Reranking

cs.IR cs.AI ·2026-11-17 ·Benjamin Clavié, Herumb Shandilya, Hanna Lichtenberg, Aamir Shakir, Makoto P. Kato
theory similarity 0.57
Abstract

Listwise LLM rerankers cannot reliably rank hundreds of documents in a single call, and rely on schedules to orchestrate their calls. Parallel schedules split candidates into groups and advance a fixed quota from each. When a group holds more of the top passages than its quota, some are cut, and expensive repair calls become required. We show that the way candidates are split matters where such a quota can bind, and that, in expected cuts, the best split there deals them round-robin by retriever rank, like cards. Although not conceptually new, dealing has remained unanalyzed. We prove that, under a simple retriever model, no split with equal quotas cuts fewer of the true top ten on average, and that contiguous chunks cut more as the retriever improves. DealRank, the simplest schedule our analysis allows, is on average within 0.1 nDCG@10 points of the best schedules over six LLMs, in two rounds. It is consistently 1.1 to 1.4 times faster than BlitzRank with concurrent first calls up to a thousand candidates. There, it needs three rounds and is eleven times faster than the sliding window. In existing schedules such as BlitzRank, dealing reduces repair calls from 59% of queries to 14%, improving latency with no significant change in quality. Random partitioning appears equivalent at a quota of four, as predicted, but ties results to the seed and trails by 1.3 nDCG@10 points at a quota of one over a dense retriever.

0.27