CS Paper Radar

Deal With It: On Better Schedules for Listwise Reranking

Benjamin Clavié, Herumb Shandilya, Hanna Lichtenberg, Aamir Shakir, Makoto P. Kato

cs.IR cs.AI ·submitted 2026-11-17 08:42 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Can System-1-Style Decision Models Replace Dedicated Rerankers in RAG? A Systems Evaluation

cs.LG ·2026-10-26 ·Qiaomu Li, Ying Xie
similarity 0.65
Abstract

Retrieval-augmented generation (RAG) systems often use a dedicated reranker to choose which retrieved candidates reach the language model. Reranking improves relevance but adds latency, so teams look for faster alternatives. System-1style decision models make direct, structured predictions instead of generating long responses. Could one provide comparable reranking quality with less inference overhead? We first screen 21 open-weight models on 11 benchmarks, then compare a promising decision model with a dedicated reranker on identical candidate lists. The default decision-model setup fails on many long candidate sets, so scoring only the requests it completes gives a misleading ranking. Limiting candidate text length largely restores reliability and makes some configurations competitive. A frozen evaluation on new retrieval data supports the reliability and ranking results, but confirms the latency requirement for only one of the two selected configurations. Across workloads, which model ranks better changes, and a tuned reranker remains faster and uses far less GPU memory. A decision model can perform competitive reranking, but replacing a reranker requires weighing quality, latency and memory together, and teams should tune the reranker they already run first.

0.41

Beating One Half for Online Bipartite Matching with Reusable Resources

cs.DS ·2026-10-01 ·Xiaohui Bei, Zhihao Gavin Tang, Wenhao Wu
benchmarktheory similarity 0.64
Abstract

We study online bipartite matching with unit-inventory reusable resources, where requests arrive in an adversarially fixed order, and each use of a resource makes it unavailable for an independent duration drawn from a resource-dependent distribution. The benchmark knows all requests in advance but cannot observe a duration before choosing the corresponding use. The classical Ranking algorithm of Karp, Vazirani, and Vazirani (STOC 1990) fixes a uniformly random priority order of the resources and matches each arriving request to its highest-priority available neighbor. It achieves the optimal competitive ratio $1-1/e$ for unweighted nonreusable resources, but whether it beats $1/2$ for reusable resources has remained open. We prove that, for unweighted resources with resource-dependent stochastic durations, Ranking achieves a competitive ratio of $(5-2\sqrt3)/3\approx0.511966$. We also give a black-box reduction from unweighted Ranking to resource-weighted matching: any unweighted competitive ratio $α>1/2$ yields a weighted ratio strictly above $1/2$. With independent sampling access to the duration distributions, the reduction gives a weighted ratio of $0.500034$. These results resolve two questions left open by Delong et al. (MOR 2024): whether Ranking beats $1/2$, and whether one can beat $1/2$ under stochastic durations. We analyze Ranking resource by resource, rather than request by request. For deterministic durations, this gives a reduction to random-order greedy for a coverage function. We then extend the analysis to stochastic durations by comparing the residual schedules of Ranking and a greedy algorithm, and apply a finer analysis of the random ranks to obtain the stated $0.511$ bound. For the weighted reduction, we apply Ranking within groups of similar weights and uses weighted greedy to control the loss between groups.

0.28

List Update with Per-Page Maximum Delay

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
similarity 0.63
Abstract

We study list update with per-page maximum delay. Requests may wait, and one access clears all pending requests of a page at its current list rank, paying their maximum waiting penalty. Each service can change the permutation and therefore the cost of later accesses. We give a strictly $5$-competitive deterministic algorithm: serve a page when the oldest waiting time reaches two thirds of its current rank, then move it to the front. Our main tool is an asynchronous marked-rank coupling that compares different list orders and different service histories. A temporal transfer principle separates this permutation argument from two waiting-cost inequalities. It gives factor $5$ for page-specific superadditive penalties, common calendar rates, and additional hard deadlines; deadlines alone admit factor $3$. Two structural conditions on request-specific penalties give factor $3+2κ$. In particular, nonincreasing request severity retains factor $5$ even with unbounded weight ratios. For linear delay, offline optimization is NP-complete but fixed-parameter tractable in the number of pages. We characterize fixed-list batching, show an $Ω(m)$ gap between the best static order and dynamic reordering, and prove that the optimal deterministic factor for one page is exactly $2$. Counterexamples delineate the threshold rule's scope.

0.20

Top-K Is Not a Budget for Hybrid Retrieval

cs.IR ·2026-09-14 ·Chunran Zhang
code/data similarity 0.63
Abstract · 5 pages, 2 figures, 3 tables. Code: https://github.com/ln-one/top-k-is-not-a-budget

Modern hybrid retrieval for RAG typically fuses the Top-$L$ results from dense and sparse retrievers, but a fixed truncation depth may not transfer across changing queries and corpora. Exact fusion removes the dependence on a fixed depth, yet completing a specified Top-$K$ still incurs variable access costs. We present DiBud, which takes an access budget directly as input and incrementally certifies and returns an exact prefix of the RRF ranking over the full lists. Selective access increases certified output within the budget, while budgeted stopping bounds accesses per request. Experiments on five query sets reveal long-tailed costs for completing exact Top-20. At a budget of 2048 accesses, DiBud increases mean certified output within the first 100 positions by 7.86% over balanced access. After budget calibration for 95% quality retention, held-out queries retain 95.05%--97.68% of mean nDCG@20 while using 65.92%--99.53% fewer accesses than completing exact Top-20.

0.43

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.60
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

The Recall Ceiling of LLM Recommendation Reranking

cs.IR cs.LG ·2026-08-27 ·Zhaohui Wang
top venuetheory similarity 0.60
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

Incremental Pooled LLM Evaluation for Cost-Effective Retrieval Model Selection

cs.IR cs.CL ·2026-09-02 ·Max Nelson, Hanoz Bhathena, Aviral Joshi, Saket Sharma
benchmark similarity 0.60
Abstract · 10 pages, 1 figure

Selecting a retrieval model for a production RAG system requires reliable comparative evaluation, but obtaining relevance judgments at scale is expensive and difficult to repeat as new candidate systems arrive. We study pooled LLM evaluation, in which an LLM judges the union of documents retrieved by the current set of candidate systems, and the pool is then expanded incrementally as new systems are introduced by judging only the new documents they contribute. These judgments are reused to evaluate all systems on a common basis. We validate this approach on four retrieval benchmarks with 11 systems spanning dense, sparse, and hybrid configurations, and deploy it to compare 62 retrieval configurations for a financial news QA system. Pooled LLM rankings correlate strongly with gold-standard evaluation across datasets, and 97% of pairwise system orderings are preserved once bootstrap uncertainty in the qrels is taken into account. In production, document overlap yields 65-80% judgment reuse and up to 4.9x lower evaluation cost, allowing teams to benchmark new retrieval candidates without re-judging previously assessed documents. These results suggest pooled LLM evaluation is a practical and cost-effective workflow for incremental retrieval model selection in deployed systems.

0.15

Bounding Queue Waits for Fair Scheduling of Bursty HPC Workloads via Hierarchical Algorithms

cs.DC ·2026-10-23 ·Karaen Senthilkumar, Suman Raj, Maxime Gonthier, Kyle Chard, Donpaul Stephens +1 more
hot direction similarity 0.59
Abstract · 12 pages, 9 figures, 4 tables

HPC clusters are shared among many projects, each holding an allocation of node-hours, and ensuring fairness is becoming harder. Foundation models workflows and automated pipelines have made job submissions bursty and concentrated among a few heavy users, so occasional users absorb queueing delays created by frequent ones, with no indication of how long their jobs will wait. Existing schedulers either forget past usage, protect only the job at the head of the queue, or assume that running jobs can be preempted. We propose HyDRA, a Hybrid Deadline and Ranking-Aware scheduler that enforces fairness among users while bounding the queue wait of every job. HyDRA assigns each job a deadline on arrival based on its size, the priorities of its project and user, the current backlog, and how far its project and user are from their entitled share. It ranks waiting jobs by a priority score that grows with waiting time, serves jobs close to their deadlines first, and backfills a job only when no deadline, or fairness limit is violated. We evaluate HyDRA on workloads derived from a year of ALCF Polaris job traces, against conventional schedulers and variants inspired by PCS, Themis, and the PBS job-sort formula used at ALCF. HyDRA achieves $2\times$ the project-level Jain's fairness of the best baseline, starts 47\% of jobs by their deadlines compared with at most 36\% for the baselines even for largest workloads, and lowers the 95th-\%ile bounded slowdown by 4.2$\times$ relative to the next best baseline, at a moderate cost in utilization.

0.38