Contextual Relevance and Adaptive Sampling for LLM-Based Document Reranking
Jerry Huang, Siddarth Madala, Cheng Niu, Julia Hockenmaier, Tong Zhang · 2025
Read Contextual Relevance and Adaptive Sampling for LLM-Based Document Reranking by Jerry Huang, Siddarth Madala, Cheng Niu, Julia Hockenmaier, Tong Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01208.txt.
Introduction
Jerry Huang and colleagues rethink document reranking, the step that reorders search results using a large language model's relevance judgments. For hard queries that need deep reasoning, relevance depends on context: which other documents are being ranked alongside, and in what order they are shown.
They define contextual relevance as the probability a document is relevant, averaged over those ranking contexts. Earlier work handled the order effect, but they show the batch composition matters just as much. Their algorithm, TS-SetRank, samples contexts to estimate contextual relevance while tracking uncertainty. On the BRIGHT and BEIR benchmarks it improved ranking quality over retrieval and reranking baselines. The margins ran from six to twenty five percent. That is evidence that relevance is genuinely context dependent.
Catalog record
| CREATOR | Jerry Huang, Siddarth Madala, Cheng Niu, Julia Hockenmaier, Tong Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-01208
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Contextual Relevance and Adaptive Sampling for LLM-Based Document Reranking Jerry Huang, Siddarth Madala, Cheng Niu, Julia Hockenmaier, Tong Zhang Abstract Reranking algorithms have made progress in improving document retrieval quality by efficiently aggregating relevance judgments generated by large language models (LLMs). However, identifying relevant documents for queries that require in-depth reasoning remains a major challenge. Reasoning-intensive queries often exhibit multifaceted information needs and nuanced interpretations, rendering document relevance inherently context dependent. To address this, we propose contextual relevance , which we define as the probability that a document is relevant to a given query, marginalized over the distribution of different reranking contexts it may appear in (i.e., the set of candidate documents it is ranked alongside and the order in which the documents are presented to a reranking model). While prior works have studied methods to mitigate the positional bias LLMs exhibit by accounting for the ordering of documents, we empirically find that the compositions of these batches also plays an important role in reranking performance. To efficiently estimate contextual relevance, we propose TS-SetRank , a sampling-based, uncertainty-aware reranking algorithm. Empirically, TS-SetRank improves nDCG@10 over retrieval and reranking baselines by 15–25% on BRIGHT and 6–21% on BEIR, highlighting the importance of modeling relevance as context-dependent. 1 Introduction Figure 1: An overview of the Setwise prompting approach for document reranking. Here, we draw batches of size three from the initial list of retrieved documents and prompt an LLM to identify all relevant documents in each batch (highlighted in green). The final reranking list is formed by aggregating all relevance judgments across batches. Large language models (LLMs) have shown strong performance in zero-shot document reranking Chen et al. 2025 ; Ma et al. 2024 , with the Setwise prompting approach Zhuang et al. 2024 offering a favorable trade-off between the number of LLM inference calls necessary for reranking and final reranking quality. As illustrated in Figure 1 , in this approach, smaller subsets or batches of documents are drawn from the initial set of retrieved documents and presented to an LLM trained for reranking, which in turn generates per-document binary judgments of relevance to a given query. Final rankings are then constructed by aggregating the model’s relevance judgments across batches using aggregation or well-known sorting algorithms such as bubble sort or heap sort. Final reranking quality is thus determined by the ability of a reranking model to identify all relevant documents in each batch, while constrained by a fixed inference budget. While past work has investigated the positional bias LLMs exhibit when making relevance judgments Tang et al. 2024 ; Vardasbi et al. 2025 ; Li et al. 2024 , we find that the context in which documents are presented to LLMs also impacts their ability to identify all relevant documents. This phenomenon is particularly evident in queries that require deeper levels of reasoning, have multi-faced information needs, and/or contain nuanced interpretations Zeng et al. 2024 ; Gienapp et al. 2022 . As highlighted by BRIGHT Su et al. 2025 , a benchmark for reasoning-intensive retrieval, both first-stage retrievers and reranking models struggle to retrieve the set of all relevant documents in such cases. As a descriptive example, consider the following prompt: Judge the relevance of the following passages to the query, “What is the primary ecological role of sea otters in kelp forest ecosystems?” (1) Sea otters are considered a keystone species because they control sea urchin populations, which in turn helps maintain healthy kelp forests. (2) Unchecked sea urchin populations can devastate kelp forests, making predator control essential for ecosystem stability. (3) Marine mammals such as seals, whales, and dolphins play critical roles in ocean nutrient cycling. Passage (1) is consistently judged relevant, as it directly connects sea otters to the query. Passage (2) is also relevant but its relevance is dependent on the context of (1). Passage (3) is irrelevant. Thus, a reranking model might incorrectly judge all the documents in a batch formed by documents (2) and (3) as irrelevant. To capture these effects, we define contextual relevance as the probability that a document is judged relevant given a query marginalized over all batches in which it may appear, where each batch is defined by both its contents and the ordering of its documents. Although this formulation assumes independence across documents, for tractability, marginalizing over all possible batches allows us to recover each document’s expected relevance across diverse contexts. This effectively captures contextual dependencies in expectation even when individual batch judgments are interdependent. A natural approach to rerank a list of documents is to enumerate all possible batches in which each document may appear. However, to more efficiently estimate contextual relevance, we propose Thompson Sampling for Setwise Reranking (TS-SetRank), a two-phase Bayesian reranking algorithm that first samples document batches uniformly to collect unbiased relevance feedback, and then adaptively constructs batches using Thompson sampling Agrawal and Goyal 2012 . We evaluate TS-SetRank on BRIGHT Su et al. 2025 and BEIR Thakur et al. 2021 , two benchmarks for evaluating retrieval capabilities, and compare its Normalized Cumulative Discount Gain (nDCG@k; Järvelin and Kekäläinen 2002 ) performance against deterministic reranking and statistical retrieval baselines. Our contributions are as follows: • We propose the notion of contextual relevance , which takes into account both the contents and ordering of retrieved documents within each batch for Setwise reranking. • We show that variance in LLM-based setwise relevance judgments arises from LLM sampling variability and contextual dependencies, and empirically quantify the share of each. • We propose TS-SetRank and show that it outperforms deterministic reranking algorithms in nDCG@10 under comparable inference budgets on BRIGHT and BEIR. 2 Estimating Contextual Relevance 2.1 Problem Formalization Objective. Let \mathcal{Q} denote the space of user queries and \mathcal{D} the document corpus. For each query q\in\mathcal{Q} , a first-stage retriever returns an ordered list of candidate documents: D=\bigl(d_{(1)},d_{(2)},\dots,d_{(N)}\bigr)\subseteq\mathcal{D}, where d_{(1)} is the highest-scoring document and N\ll|\mathcal{D}| . The reranking objective is to select an ordered subset of D that maximizes the final reranking quality as measured by a specified retrieval metric such as nDCG@k. Reranking Model. A setwise reranking model is an LLM that takes a query q and a small batch of documents S=(d_{1},\dots,d_{b}) where b\ll N , and makes a binary relevance judgment for each document. Contextual Relevance. We define the contextual relevance of a document d_{i} with respect to a query q as its probability of being judged relevant, marginalized over all batches in which it may appear: \theta_{i,q}=\mathbb{E}_{S\sim D_{b}(d_{i})}\Bigl[\Pr\bigl(d_{i}\text{ is judged relevant}\mid q,S\bigr)\Bigr] where D_{b}(d_{i}) denotes the distribution over size- b batches that include d_{i} , and D_{b}(D) denotes the distribution over all size- b batches drawn from D . We use \theta_{i} interchangeably with \theta_{i,q} , as the query q is fixed within each reranking task. Modeling Assumptions. This formulation assumes conditional independence across documents: each document’s judgments are modeled as independent draws following a Bernoulli distribution with mean \theta_{i,q} . While this simplification is reasonable when documents do not exhibit strong dependencies, more complex models (e.g., structured bandits or Plackett–Luce) would be required in domains such as multi-hop question answering Mavi et al. 2024 or citation retrieval Qian et al. 2024 , where relevance depends on prerequisite evidence. Benchmarks like BRIGHT and BEIR