AcuRank: Uncertainty-Aware Adaptive Computation for Listwise Reranking

Soyoung Yoon, Gyuwan Kim, Gyu-Hwung Cho, Seung-won Hwang · 2025

Read AcuRank: Uncertainty-Aware Adaptive Computation for Listwise Reranking by Soyoung Yoon, Gyuwan Kim, Gyu-Hwung Cho, Seung-won Hwang (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-2505-18512.txt.

Introduction

Soyoung Yoon and co-authors present in 2025 a smarter way to rerank search results with large language models. Reranking is usually done on fixed small groups, since long lists are costly and exceed model limits. That fixed effort wastes work on easy queries and may skimp on hard ones.

Their method tracks how unsure the system is about each document's relevance, using a Bayesian skill model. It keeps refining scores until confidence is high enough, and leaves firm scores alone. On standard search benchmarks, the method gave a better trade between accuracy and cost than fixed methods, and it scaled better as more computing was added.

Catalog record

CREATORSoyoung Yoon, Gyuwan Kim, Gyu-Hwung Cho, Seung-won Hwang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-18512

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

AcuRank: Uncertainty-Aware Adaptive Computation for Listwise Reranking Soyoung Yoon, Gyuwan Kim, Gyu-Hwung Cho, Seung-won Hwang Abstract Listwise reranking with large language models (LLMs) enhances top-ranked results in retrieval-based applications. Due to the limit in context size and high inference cost of long context, reranking is typically performed over a fixed size of small subsets, with the final ranking aggregated from these partial results. This fixed computation disregards query difficulty and document distribution, leading to inefficiencies. We propose AcuRank, an adaptive reranking framework that dynamically adjusts both the amount and target of computation based on uncertainty estimates over document relevance. Using a Bayesian TrueSkill model, we iteratively refine relevance estimates until reaching sufficient confidence levels, and our explicit modeling of ranking uncertainty enables principled control over reranking behavior and avoids unnecessary updates to confident predictions. Results on the TREC-DL and BEIR benchmarks show that our method consistently achieves a superior accuracy–efficiency trade-off and scales better with compute than fixed-computation baselines. These results highlight the effectiveness and generalizability of our method across diverse retrieval tasks and LLM-based reranking models. 1 1 1 https://github.com/soyoung97/AcuRank 1 Introduction Modern information retrieval pipelines, such as web search and retrieval-augmented generation (RAG) systems, typically adopt a fast first-phase retriever, selecting a set of broadly relevant documents, like BM25 [ 1 ] or dense encoders [ 2 ] optimized for recall and speed. As they often produce noisy or suboptimal rankings, reranking is critical in applications where precision at the top is essential, including conversational agents and reasoning with large language models (LLMs) [ 3 , 4 ] . Reranking methods can be broadly categorized by how they model document interactions and handle relative relevance. Pointwise methods [ 5 ] independently assign scores to each document, offering scalability but failing to consider the competitive context among candidates. Pairwise methods [ 6 ] improve upon this by comparing document pairs to capture local preferences, but often struggle to maintain coherent global rankings. Listwise methods [ 7 , 8 ] instead evaluate a group of documents jointly, particularly effective for out-of-domain [ 9 ] or low-resource [ 10 ] settings. Recent work has shown that LLMs are especially effective as listwise rerankers, due to their ability to capture complex reasoning and fine-grained distinctions across documents [ 7 , 11 , 12 ] . Despite their effectiveness, applying LLMs in listwise reranking is computationally expensive. As each LLM reranker call can process only a small group of candidates due to input length limits, covering the full list typically requires multiple calls. Prior work has proposed fixed-computation strategies such as sliding windows [ 13 ] and tournament-style reranking [ 14 ] to balance ranking effectiveness with computational cost. While these fixed strategies improve efficiency, they suffer from rigidity and lack of adaptivity by assigning a fixed number of reranker calls to predetermined candidate positions, regardless of the complexity or ambiguity of the query. As a result, documents ranked low in early iterations may never be reconsidered, even when initial decisions are based on limited or noisy context. Moreover, these methods do not leverage intermediate signals from previous reranking steps and cannot dynamically focus computation on uncertain cases where refinement is most needed. To address these limitations, we propose AcuRank , a framework for listwise reranking with U ncertainty-aware A daptive C omputation (rearranged for pronunciation). Our method adaptively allocates computation based on each document’s relevance uncertainty relative to the top- k boundary, rather than treating all documents equally. As illustrated in Figure 1 , we adopt TrueSkill [ 15 ] , a Bayesian rating system, to maintain probabilistic relevance estimates (Figure 1 (a)) and iteratively update them as reranking results are observed. At each step, only uncertain candidates are selected for reranking (Figure 1 (b)), while confident ones are skipped. This targeted refinement continues until convergence (Figure 1 (c)), improving both accuracy and computational efficiency by focusing resources on the most ambiguous cases. We evaluate our method on the TREC Deep Learning [ 16 ] and BEIR [ 17 ] benchmarks using multiple LLM-based rerankers. Our approach consistently improves ranking quality while requiring fewer reranker calls across diverse datasets and reranker models, including both in-domain and out-of-domain settings. These results demonstrate the effectiveness of uncertainty-aware adaptive computation and the broad applicability of our method. Figure 1 : Overview of AcuRank. (a) : Each retrieved document’s relevance is initialized as a Gaussian distribution using a TrueSkill-based model, with its mean and variance representing estimated relevance and uncertainty. (b) : We estimate the probability of a document being in the top- k as the chance its score exceeds a threshold such that the expected number of documents above it equals k . Documents with uncertain rankings are selected and reranked in groups, and their relevance estimates are updated. (c) : The process repeats until stopping criteria are met. The final ranking is based on the updated relevance estimates. Our contributions are as follows: • We introduce probabilistic relevance modeling based on TrueSkill, which enables estimation of uncertainty in document rankings. • Building on this, we develop a novel listwise reranking framework that supports adaptive computation by selectively reranking uncertain candidates through iterative refinements. • Through extensive experiments, our method consistently improves the accuracy–efficiency trade-off across benchmarks and generalizes well across datasets and reranker models. 2 Related work 2.1 Fixed-computation reranking strategies Pointwise, pairwise, and setwise. Pointwise methods [ 18 , 19 , 20 , 21 ] score each document independently, treating reranking as a classification problem. They are efficient and compatible with neural encoders and LLMs but cannot model cross-document dependencies, limiting their effectiveness in complex scenarios. Pairwise methods [ 22 , 6 , 23 ] compare two documents at a time to model pairwise dependency, but require n^{2} number of reranker calls to rank n documents. Setwise methods [ 24 ] are typically compared against pairwise methods, which rerank small fixed-size sets to balance between pointwise simplicity and listwise interaction. While efficient, they typically view only one or two passages at a time, limiting their ability to model subtle inter-document relationships visible only in larger listwise contexts. A concurrent OpenReview submission explores a budget-constrained pairwise reranking strategy that selects informative comparisons using TrueSkill-based uncertainty sampling; unlike our approach, it operates under a fixed pairwise budget rather than allocating computation adaptively over listwise contexts [ 25 ] . Listwise - sliding windows. Sliding window methods rerank overlapping subsets of candidates iteratively, starting from the bottom window of the list and progressively moving to the next window, merging top results upward. This approach has been widely adopted in LLM-based reranking systems such as LRL [ 13 ] , RankGPT [ 11 ] , RankVicuna [ 8 ] , and RankZephyr [ 12 ] , which use zero-shot prompts to perform reranking over windowed chunks. While effective, fixed window sizes and traversal paths lead to inefficiencies, by incurring over-computation for simple queries with little ambiguity and under-computation for complex queries. Listwise - tournament-style. Tournament-style methods rerank by partitioning candidates into small groups and performing listwise reranking in iterative rounds. TDPart [ 26 ] employs a top-down partitioning strategy to minimize redundant inference and enhance parallel processing. In each round, listwise reranking is applied to the groups,

Read the complete text