Deal With It: On Better Schedules for Listwise Reranking

Benjamin Clavié, Herumb Shandilya, Hanna Lichtenberg, Aamir Shakir, Makoto P. KatoarXiv 2026 · arXiv

TL;DR

LLM-based listwise reranking is highly effective but struggles with latency when scaling to hundreds of documents. This paper demonstrates that the standard practice of splitting documents into contiguous chunks for parallel processing is suboptimal; instead, "dealing" documents round-robin by their initial retriever rank significantly reduces the loss of relevant documents and eliminates the need for expensive "repair" calls, leading to massive speedups (up to 11x) with no loss in ranking quality.

What Problem Does This Paper Address?

Large Language Models (LLMs) are excellent at reranking search results, but they have a "context window" problem: they can't reliably rank hundreds of documents in a single prompt. To handle large sets (e.g., the top 100 or 1,000 documents from a retriever), researchers use schedules—orchestrated sequences of LLM calls.

A common approach is to split documents into groups, rank each group in parallel, and advance a fixed quota (e.g., the top 4 from a group of 20) to a final round. The challenge is that if a group contains more relevant documents than its quota allows, those "good" documents are lost forever. Existing solutions like BlitzRank use expensive "certification" rounds to try and recover these lost documents, which increases latency.

Methods

The authors propose a simple but mathematically grounded change to how documents are partitioned: Dealing.

Instead of splitting the retriever's list into contiguous chunks (e.g., documents 1-20, 21-40, etc.), they "deal" them like a deck of cards. Hand 1 gets documents 1, 6, 11, 16...; Hand 2 gets 2, 7, 12, 17... and so on.

Figure 1. (a) Dealing against contiguous chunks. (b) Median Gemini API latency and nDCG@10 gap to DealRank

Based on this, they introduce DealRank, a schedule that:

  1. Deals the initial candidates into parallel "hands."
  2. Ranks hands concurrently and advances a fixed quota from each.
  3. Performs a final ranking call on the winners.
  4. For very large sets (e.g., 1,000 documents), it uses a hierarchical 3-round version of this process.

Datasets

The authors evaluated their approach using standard Information Retrieval (IR) benchmarks:

  • TREC-DL19 and DL20: Built on the MS MARCO passage collection.
  • BEIR Collection: 8 diverse datasets (including COVID, SciFact, etc.) totaling 1,622 queries.
  • Retriever Models: They tested against both traditional BM25 and modern dense retrievers (Qwen3-Embedding-4B).
  • LLM Rerankers: Evaluation spanned six models, including Gemini 3 Flash, DeepSeek V4-Flash, and Qwen3.8-27B.

Key Insights and Ideas

  • The "Better Retriever" Paradox: In contiguous chunking, a better retriever actually makes the schedule worse. If a retriever is very accurate, the top 10 relevant documents will all be clustered in the first chunk. If the quota for that chunk is only 4, you lose 6 highly relevant documents immediately.
  • Dealing is Optimal: The authors prove that under a simple retriever model, no split with equal quotas cuts fewer of the true top-10 documents on average than dealing. Dealing ensures that relevant documents (which the retriever likely placed near the top) are spread across different parallel calls, allowing them all to advance.
  • Predictability Matters: Unlike schedules that trigger "repair" rounds based on uncertainty, DealRank has a fixed number of rounds. This makes latency predictable, which is crucial for production systems.

Key Results

  • Efficiency: DealRank is 1.1x to 1.4x faster than a concurrent version of BlitzRank. When scaling to 1,000 candidates, it is 11 times faster than the traditional sliding window approach.
  • Quality: Across six different LLMs, DealRank stays within 0.1 nDCG@10 points of the best (but much slower) schedules.
  • Reduced Overhead: In existing schedules like BlitzRank, switching to a "dealt" input reduced the need for expensive certification calls from 59% of queries down to just 14%.
  • Scaling: For 1,000 documents, DealRank achieves its results in just 3 rounds, whereas a sliding window requires 99 rounds.

Limitations and Future Work

  • Consistent Ranker Assumption: The theoretical proof assumes a "consistent ranker" (one that would produce the same relative ordering regardless of the window). While LLMs are generally consistent, they can be sensitive to list composition.
  • Fixed Quotas: The study focuses on equal quotas for all groups. The authors suggest that exploring variable quotas or different "dealing" patterns (like a snake draft) could be a path for future optimization.
  • LLM Specifics: While tested across several models, the "concavity" of a model's ranking ability (how well it picks the top $x$ documents) can affect the ideal quota size.

Summary updated

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.
BibTeX
@misc{clavie2026deal,
  author = {Benjamin Clavié and Herumb Shandilya and Hanna Lichtenberg and Aamir Shakir and Makoto P. Kato},
  title = {{Deal With It: On Better Schedules for Listwise Reranking}},
  year = {2026},
  eprint = {2611.22392},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22392},
}
Figure