AcuRank: Uncertainty-Aware Adaptive Computation for Listwise Reranking
Authors: Soyoung Yoon
Gyuwan Kim
GYU-HWUNG CHO
seung-won hwang
Venue: NeurIPS 2025 poster ()
Keywords: Listwise Reranking
Large Language Models
Adaptive Computation
Uncertainty Estimation
Inference Efficiency
Primary area: deep_learning
TL;DR: AcuRank adaptively reranks documents using uncertainty, improving ranking accuracy with fewer LLM calls.

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.

AcuRank: Uncertainty-Aware Adaptive Computation for Listwise Reranking
Soyoung Yoon' Seoul National University soyoung. boyoung.yyonésnuu kc.
Gyuwan Kim University of California, Santa Barbara
gyuwankim@ucsb.ce
Gyu-Hwung Cho Scoul National University jgh081 1 5@snu. ac. kr
Seung-won Hwang Scoul National University seungwonhêsnu. ac
Abstract
Listwise reranking with large language models (LLMs) enhances top-ranked results in retrieval-brie biaievallbbeddddddee applications. Due to the limit in context size and high inference cost of long context, reranking typically performed over a fixed size small subsets, with the final ranking aggregated from these partial results. This fixed computation disregards query difficulty and document distribution, leading to ineffi ciencies. We propose AcuRank, adaptive reranking framework that dynamically adjusts both the amount and target of computation based on uncertainty estimates over document relevance. Using Bayesian TrueSkill model, we iteratively refine relevance estimates until reaching sufficient confidence levels, and our explicit modeling of ranking uncertainty enables principled control 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 accu- racy- racy-efficiency trade-off and scales better with compute than fixed-computation basclines. These results highlight the effectiveness and generalizability of our method across diverse retrieval tasks and -LM-b reranking models
Introduction
Modern information retrieval pipelines, such web search and retrieval-auummnnte generation (RAG) systems, typically adopt a fast first-phase retriever, selecting a set of broadly relevant documents, like BM25 [1] 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)
Reranking methods can be broadly categorized by how they model document interactions and handle relative relevance. Pointwise methods (5) independently assign scores each document, offering scalability but failing to consider the competitive context among candidates. Pairwise methods [6] improve upon this comparing document pairs capture local preferences, but often struggle maintain coherent global rankings. Listwise methods 77] g instead evaluate group of documents jointly, particularly effective for out-of-dommin [9] 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
[2]
Equul contribution. Author order is randomly determined via coin toss.
Connesonnding author.
httpss///giiuuu..cmmmoooo///////
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(b) Select documents with high ranking uncertainty, update scores
(a) Initialize with first-stage retrieval
(c) Final Ranking
Probability Density
T
Relevance
Relevance
Relevance
Figure 1: Overview of AcuRank. (a): Each retrieved document's relevance is initialized Gaussian distribution using a TrueSkill-based model, with its mean and variance representing estimated relevance and uncertainty. (b): We estimate the probability of document being in the top-k as the chance its score exceeds 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.
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 input length limits, covering the full list typically requires multiple calls. Prior work has proposed fixed-computation strategies such as sliding windows [I3] and tournament-style reranking [4] 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 predetermined candidate positions, regardless of the complexity or ambiguity of the query. As a result, documents ranked low in early iterations may never reconsidered, even when initial decisions are based on limited noisy context. Moreover, these methods do not leverage intermediate signals from previous reranking steps and cannot dynamically focus computation on uncertain cases where refinement most needed.
To address these limitations, we propose AcuRank, a framework for listwise reranking with Uncertainty-aware Adaptive Computation (rearranged for pronunciation). Our method adaptively allocates computation based on each document's 's relevance uncertainty relative to the top- boundary. rather than treating all documents equally. As illustrated in Figure [ we adopt TrueSkill [15], Bayesian rating system, to maintain probabilistic relevance estimates (Figure aa)) and iteratively update them reranking results are observed. At each step, only uncertain candidates are selected for reranking (Figure T(b)), while confident ones are skipped. This targeted refinement continues until convergence (Figure Ic)), 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 benchmarks using mul- tiple LLM-based rerankers. Our approach consistently improves ranking quality while requiring fewer reranker calls across diverse datasets and reranker models, including both in in-domain and out-of-domain settings. These results demonstrate the effectiveness of uncertainty-awee adaptive computation and the broad applicability of our method.
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 novel listwise reranking framework that supports adaptive compu- tation by selectively reranking uncertain candidates through iterative refinements. Through extensive experiments, our method consistently improves the accuracy accuracy-effieienge 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 [1821 score each document independently, treating reranking a classification problem. They are efficient and compatible with neural encoders and LLMs but cannot model cross-document dependencies, limiting their effectiveness in complex

---

compare two documents at a time to model pairwise dependency, but require n² number of reranker calls to rank 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 time, limiting their ability to model subtle inter-document relationships visible only in larger listwise contexts. A concurrent OpenReview submission explores a budget-constrained painwise reranking strategy that selects informative comparisons using TrueSkill- uncertainty sampling; unlike our approach, operates under a fixed pairwise budget rather than allocating computation adaptively over listwise contexts [25]
scenarios, Pairwise methods 22 6 23
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 [T3] RankGPT [TT], Rank Vicuna [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, and the top-ranked documents advance. This process repeats over progressively smaller pools until the final ranking is achieved. While TDPart focuses on efficiency, ListT5 (27] and TourRank [14] leverage T5 models and L.LSs for groupwise comparisons, achieving competitive ranking accuracy. However, like sliding window methods, they are limited by fixed schedules, leading to over-computation for straightforward queries and codputaimptt for complex, ambiguous ones.
Complementary scheduling-bee bbasd approaches, CoRanking 28 integrates rerankers of different model sizes to reduce end-to-end cost, while DemoRank [29] explores demonstration selection tailored for ranking tasks. Both are orthogonal to our uncertainty-driven adaptive computation, yet potentially compatible with it.
2.2 Uncertainty and adaptivity in retrieval
Uncertainty estimation in retrieval has emerged as a principled method for enhancing reliability in retrieval. Cohen al. 330 introduce Bayesian framework that interprets relevance scores in deep retrieval models as stochastic estimates rather than deterministic values. Using techniques like dropout-basee based variational inference, they capture predictive uncertainty, leading to improvements in robustness, calibration, and resilience to ad adversarial inputs. Their findings expose the risks associated with overconfident ranking models and highlight the need for uncertainty-awee mechanisms in downstream tasks, such as filtering and reweighting. While post-hoc calibration over static retrieval outputs is allowed in their problem context, our work requires online computation for the iterative reranking setting. Our distinction lies in integrating the rigor of Bayesian models, inspired by TrueSkill [15], into adaptive computation, thereby making our approach both theoretically grounded and practically efficient. Mcanwhile, prior udaptive computation methods (3I] in retrieval are largely confined to statistical ranking scenarios 32 that depend on separate estimators for judging relevance
thresholds or query difficulty R3 36)
In contrast, our method unifies uncertainty estimation and adaptive computation in a single framework: we use uncertainty not only as measure of model confidence, but also as a dynamic signal that guides the allocation of computation. This enables fine-grained reranking that selectively refines ambiguous documents while avoiding unnecessary inference on confident ones.
3 Method
We begin by formalizing the reranking task (s3.1) and introducing our approach to relevance modeling and uncertainty quantification using TrueSkill (3.2). Building on this foundation, we then describe the components of our reranking algorithm with adaptive computation, AcuRank ($3.3 Fig. I..
3

---

While conventional reranking methods rely on fixed number of reranker calls per query (.2.)) our method adaptively determines both which documents rerank and how much computation to allocate, based on evolving document-level uncertainty estimates. This enables focused refinmmen of uncertain candidates, improving both computational efficiency and ranking effectiveness by avoiding unnecessary updates to already confidently ranked documents.
3.1 Problem formulation
Given query q and of retrieved documents D (Di...., Dr from first-stage retriever such as BM25, the goal is to reorder the documents into ranked list [D,, > .... > Dr..] or to extract top-k list [Dr,
Dr.J. where (ri,..., Fnn is a permutation of {1..... nI........ nn..
We assume access to a listwise reranker g(D:; .M), where D' an ordered subset of D and M denotes the underlying reranking model. This is done by prompting instruction-tume LLM, and the reranker returns a new ordering over the documents D'.
zero-shot
In practice, is often large (e.g.. 100-1000), making it infeasible to rerank all retrieved documents at once due to input sequence length constraints. Instead, 9 is applied smaller subsets with [D' < n, where is typically 20, and the final ranking is approximated by aggregating local reranking results across multiple batches. The ranked result is then evaluated using metrics such as NDCG@ 10, which only considers the top-k documents in the ranking, so A is often set to small number like 10. In RAG systems, & can be determined by the number of documents intended for inclusion in the generated context.
3.2 TrueSkill-basee relevance modeling and ranking uncertainty quantification
At the core of our method is a probabilistic model of document relevance based on TrueSkill [T5]. a principled Bayesian ranking system originally developed for multiplayer games. It is known to produce well-calibrated estimates of both scores and uncertainty, and has been widely adopted in various applications where reliable uncertainty quantification is crucial 37:39 39. Similar to prior works, we recast documents as players, and when one document is ranked above another, it is treated as having won that match. Specifically, we model the latent relevance of each document D; as Gaussian variable x; ~ N(u,, of² + 8²). where μás represents the estimated relevance, o; captures epistemic uncertainty, and 3 is fixed global parameter representing observation noise. Here, epistemic uncertainty reflects the model's lack of confidence in its current estimate and is expected to decrease more reranking evidence accumulates through iterative updates. This probabilistic view aligns with the intuition of Cohen et al. [30]. who emphasize the importance of modeling uncertainty in relevance estimation for more effective ranking decisions.
Each document's 's relevance thus represented not as a point estimate but as a belief distribution, capturing both its expected value and uncertainty. Modeling document relevance as a distribution en- ables principled reasoning under uncertainty and supports more informed reranking decisions. Unlike traditional methods that rely solely on deterministic rankings, our approach maintains document-level belief distributions and quantifies their relative strength. This formulation allows the computation of informative quantities such as the probability that document appears in the top-k and the entropy of its rank distribution, which serve as signals for uncertainty-awe aware computation. The model can also incorporate external signals, such as retrieval confidence or prior knowledge of relevancy signals, when available.
To estimate rank probabilities, we express the rank of D, as = 1 Σj Lzy>z i.e., the number of documents more relevant than D, under their latent scores. Since each x; is Gaussian, the exact probability that D, has rank r can be computed via:
P(r: r) [ (T(2)
Σ
II Fx(2) Dje
(1 (i-F(()) dx (iED((SU(D.))
II
SCDV(D)
1----1
where P: is the probability density function of z; and F, is the the cumulative distribution function of a.j. The summation inside the integral can evaluated using dynamic programming with O(n²) complexity by tracking the distribution over how many documents are ranked above D,. However,

---

becomes costly and numerically unstable as n grows, due to the need to compute dense integrals and multiply small probabilities.
To improve scalability, we adopt a more efficient approximation. We define a threshold ((r) such that the expected number of documents whose relevance exceeds t(r) equals the target rank r, i.e., E; P2; > t(r)) r. The value of t(r) depends on each document's relevance distribution (pi, ox), and since t(r) is monotonic
efficiently compute t(r) via binary search. We then approximate the cumulative rank probability as P(r; I r) ~ P(x; > t(r)), which reflects the chance that x; exceeds the estimated top-r threshold.
3.3 AcuRank framework
Algorithm outlines AcuRank, a listwise reranking method that performs adaptive computation guided by probabilistic relevance modeling and uncertainty estimation. At each iteration, AcuRank identifies documents with uncertain rankings and focuses reranking efforts on them, updating their relevance estimates based on listwise reranker outputs.
Algorithm 1 AcuRank: Uncertainty-Awee Aware Adaptive Computation for Listwise Reranking
Input: Query q, retrieved documents D = {Di..... ]. listwise reranker g. target rank cutoff A: Output: Ranked list [D,, > ... > D.... with top-k used downstream 1: Initialize TrueSkill-based relevance scores oz) for all D, E D
2: repeat
3: Select candidate documents C C D with high ranking uncertainty
4: Partition C into ordered groups [ B
5: Apply listwise reranker y to each Bj and update TrueSkill scores accordingly
6: until [C] is small, top-k converges, computational budget is exhausted
Initialization (Line 1). Each document's relevance distribution (ps, σ:) is initialized using first-stage retrieval scores, with μæ prior than uniform defaults (Supplementary Section B.4). The observation noise parameter B remains constant throughout. In ablation experiments, we also compare with the standard TrueSkill initialization (#4: = 25, a; = 25/3).
the raw score and o; = uz/3. This provides more informative
Uncertainty-basse selection (Line 3). To identify uncertain documents, compute s; P(zz, > t(k)) for each document, where t(k)) is the expectation threshold (r = k) defined at Section 3.2 and Σ, 8 k by construction. All documents have s; = k/n for standard TrueSkill initialization, but when using first-stage retrieval scores, 8; values may deviate from uniformity based on score distribution. As reranking progresses, these values polarize toward 0 or We define the uncertain candidate set as C = {D; < 8; < 1 -1e] eJ using tolerance hyperparameter e, selecting documents with intermediate 8; values that are neither confidently in nor out of the top-k.
Partitioning (Line 4). When the number of uncertain documents exceeds the reranker's ' capacity m, we partition the candidate set C. into equally sized groups. We first sort C' in descending order of p.. resulting in [D.,,.. ........... D Da where (s,, 2 2 Pijer' Then, we partition into disjoint ordered lists By = [Dr, i [[j ()- m,, min (m, (C))). where j = 1...., [[C//m]. Comparing documents with similar relevance scores yields higher information gain, as their relative order is more uncertain. We report random partitioning strategies in ablation experiments.
Score refinement (Line 5). Each group By is passed to the reranker g, and the resulting rankings update TrueSkill parameters. Each outcome is interpreted as a multiplayer game among documents in By, where each document is assigned a rank based on its position in the reranked list. We apply the TrueSkill update using listwise ranking as input, using a uniform monotonic ranking score (e.g.. rank-based weights) to drive the update. Documents ranked higher than expected receive an increased (4s, while those ranked lower experience a decreased μ4. The magnitude reflects how surprising the outcome is relative prior beliefs. This iterative process gradually sharpens the model's 's belief in document relevance.
Stopping criteria (Line 6). Reranking continues until one or more of the following conditions are met: (i) the number of uncertain documents C falls below the threshold т, where 7 is the threshold at which the number of [C] satisfies the stopping criterion, (ii) the top-k set remains unchanged for
5

---

fixed number of iterations, or (iii) the number of loops exceed the maximum computation budget. We use condition (i) by default and (iii) for budget-aware variants, with results on (ii) presented for ablation.
Final ranking. Documents ranked by their 14, values produce the output. By selectively reranking uncertain candidates and refining their relevance estimates through iterative feedback, AcuRank improves accuracy while reducing unnecessary computation. This uncertainty-aware approach allocates effort where most needed, focusing on ambiguous cases and avoiding redundant updates confidently ranked documents. As a result, AcuRank provides both robust and scalable solutions for efficient listwise reranking under limited computation budgets.
4 Experimental setup
4.1 Evaluation protocol
Datasets. We evaluate reranking performance on two widely used retrieval benchmarks. For TREC Deep Learning (TREC-DL) [16), we use six standard tracks: DI.19 (43), DI.20 (54), DL211 (53), DL22 (76), DL.3 (82), and DarHard (50) 44). For BEIR [17, following Sun et al. [I. we select eight representative datasets: TREC-COVID (50), NFCorpus (323), Signal- IM (97), News (57), Robust04 (249), Touché (49), DBPedia (400), and SciFact (300). The numbers in parentheses indicate the number of queries in each dataset. These datasets span a wide range of domains, including web search, scientific literature, news articles, and argumentative retrieval.
Evaluation metries. We measure ranking accuracy using Normalized Discounted Cumulative Gain at rank 10 (NDCG@ 10) [4I. which reflects the quality of top-ranked documents and is the standard evaluation metric for both TREC-DL. and BEIR. To assess efficiency, we count the number of reranker calls per query, which serves as a practical proxy for end-to-end latency in real-world deployments. While our evaluation based on reranker call counts rather than actual latency, AcuRank supports parallel execution across calls of disjoint candidate groups, enabling faster computation compared to sequential reranking steps or improved ranking accuracy without increasing latency 4]
Retrievers and rerankers. We use BM25 with top-100 candidates as the default first-stage re- triever, and evaluate three additional settings: BM25 top-1000, to assess scalability with larger candidate pools, along with SPLADE++ED 42) top- 100-100 and Contriever [43] top-100 (using facebook/ contriever-msmaree with mean pooling), to evaluate performance with different first- stage signals. Since neural retrievers such as SPLADE and Contriever produce scores on a different scale from BM25, we normalize the top-100 first-stage scores to have mean of 10 and a standard deviation of per query before applying AcuRank. We perform retrieval from the pre-built Pyserini index 44. For reranking, we use RankZephyr [22 as the default model, and additionally evaluate RankGPT (gpt-4. 1 mimnn to assess generalization across model families. Both rerankers operate over candidate lists size m = 20, formatted as prompts containing the query and document list.
4.2 Baselines
We compare AcuRank against the following reranking baselines with fixed computation per query. All experiments were conducted single NVIDIA A6000 GPU (48GB VRAM).
Sliding windows (SW-z): A standard listwise reranking method that processes the candidate list in overlapping windows of size m. with each pass starting from the bottom of the list and progressively refining the ordering toward the top. Since SW-z uses fixed number of reranker calls per query regardless of ranking difficulty, we evaluate multiple pass configurations (SW-1, SW-2, SW-3) to match the computational cost of our method. We use the implementation from the RankLLM codebase Jusing the same prompt format, hyperparameters, and input size limits.
TourRank-s: A listwise reranking method that runs independent multi-stage tournaments over retrieved candidates 14] At each stage, documents are partitioned into groups based on initial
'In principle. it is also possible to rerank overlapping groups in parallel and aggregate their outputs, which may improve robustness noisy reranker predictions. We leave this a promising direction for future work.

---

order, then randomly shuffled. At each stage, an LLM selects the most relevant documents from each group, with survivors receiving stage-specific scores. The process repeats for multiple stages (e.g.. 100 50 - 20 - 10 10-55-2 2), and summing scores across z tournaments yields the final ranking. TourRank-1 uses a single tournament, while TourRank-5 employs five tournaments for lower variance at higher computational cost. For controlled comparison, we preserve the original algorithm but reuse the exact prompt configuration employed for sliding windows and AcuRank.
TrueSkill-Static (TS-c): A TrueSkill-based baseline that selects candidates solely based on their estimated relevance scores Pi, without modeling uncertainty. At each stage j. the top-(m cÿ) documents are selected and reranked, where c ci....,ca defines the reranker call allocation per stage. This baseline allows us to isolate the effect of uncertainty modeling in our full method.
4.3 AcuRank configurations
Building on the general framework described in Section 3.3 used as our default configuration, unless otherwise noted in the ablation studies (Table 4). The hyperparameters were selected based on empirical evaluation on a subset of TREC-DLI9 and DI.20, then applied consistently across all other datasets to ensure a fair comparison. We also provide an extended robustness analysis on how computation scales with the candidate-set size n and on ranking stability under document addition; see Supplementary Section F
we specify the experimental settings
Initialization: We initialize TrueSkill scores based on first-stage retrieval scores. Specifically, set the mean [4; to the raw retrieval score (e.g.. BM25 or SPLADE), and the standard deviation σ; = 14/3. This allows the model to prioritize high-confidence documents from the beginning. Analysis on different variance initialization and justification of the design choice are discussed in Supplementary Section B and Table
We select documents whose rank probability s, = Pax,, > t(k)) falls within the range (c, (e). We use 0.01 and k 10 in our default configuration, unless noted otherwise in variant-specific settings.
Uncertainty threshold:
Partitioning strategy: When the number of uncertain documents exceeds the reranker capacity m = 20, we divide them into equally sized groups using sequential partitioning. Otherwise, we rerank using a single batch. For ablation, we also evaluate random grouping variant.
Stopping criterion: We terminate reranking when the number of uncertain documents falls below = 10, or the reranker call budget is exhausted. Alternative stopping criteria, such as top-k stability, only used in ablation studies.
To evaluate the effectiveness of our method under different computational scenarios, we introduce variants of AcuRank that reflect distinct trade-off's between efficiency and accuracy. AcuRank-e a strict-budget variant that terminates reranking after a predefined number of reranker calls enabling fair comparison with baselines under matched computational budgets. AcuRank-(H, HH} are high-preed preciireiiionn variants designed for settings where ranking quality prioritized over efficiency. AcuRank-H adopts tighter tolerance parameter e 0.0001, and AcuRank-HH additionally applies a stricter stopping criterion (r = 5), enabling more thorough refinement of uncertain candidates. Extended analyses different choices of uncertainty thresholds are discussed Supplementary Section D.3 and Table
Adaptive variants:
5 Results and analysis
5.1 Effectiveness and efficiency vs. fixed baselines
Table reports NDCG@ 10 scores and reranker call counts across TREC-DL and BEIR datasets. Under comparable reranker budgets, AcuRank consistently outperforms fixed-computation baselines in terms of overall ranking accuracy. For example, AcuRank-9 matches the average call count SW-1 (8.8) but achieves slightly higher average NDCG@) @ 10, showing that uncertainty-awar aware allocation can yield better performance even with limited computation.
As more computation becomes available, AcuRank continues to outperform. AcuRank uses 19.7 calls on average, between the budgets of SW-2 (17.6) and SW-3 (26.4), yet exceeds both in accuracy. While the gains of Sliding Windows diminish with additional calls, AcuRank shows notably larger
7

---

Table 1: Results in NDCG@ 10 TREC-DL and BEIR using top-100 (top) and top-1000 (bottom)
documents on BM25 as first-stage retrieval with RankZephyr reranker. The top row in each block corresponds to the initial ranking without reranking, which serves lower-bound reference. Note that some queries retrieve fewer than 100 documents with BM25, slightly reducing average calls.
TREC-DL
BEIR
Method
DL19 DL20 DL21 DL22 DL23 DL-H COVID NFC Signal News R04 Touche DBP Seif Avg. # Calls
stagt retrieval: BM25 top 100
Reranker: RankZephyr-7B
BM25
50.6
48.0
44.6
26.9
26.2
30.4
59.5
32.2
33.0
39.5
40.7
44.2
31.8
67.9
41.1
0.0
SW-1
74.0
70.2
69.5
51.5
44.5
38.6
84.
36.8
32.0
52.3
54.0
32.4
44.5
75.5
54.3
8.8
SW-2
74.6
70.2
70.2
51.8
45.4
38.4
84,4
37.0
33.0
52.7
54,4
31.8
44,4
75.1
54,5
17.6
SW-3
74.4
71.1
70.6
52.1
45.4
39.5
84.4
37.2
32.0
52.1
54.4
32.0
44,5
74.9
54.6
26.4
TourRank-1
74.2
68.2
69.6
51.1
45.2
38.1
81.8
36.5
30.7
$1.9
54.5
31.2
43.2
71.3
53.4
12.7
TourRank-2
74.1
71.9
70.8
52.3
47.1
40.3
82.5
36.8
32.2
51.8
56.5
33.4
74.3
54,9
TourRank-5
74.9
72.0
71.8
52.6
47.9
40.0
83.3
36.8
31.0
52.0
57.2
31.9
45.0
75.3
55.1
63.7
TourRank-10 10
74.9
71.8
71.4
53.3
47.7
39.9
83.2
37.1
31.1
53.3
57.1
32.1
44.8
75.1
55.2
127.4
AcuRank-9
73.3
71.4
70.1
50.1
45.3
39.5
83.2
36.8
30.8
53.0
56.0
37.1
44.7
73.3
54.6
8.8
AcuRank
74.2
71.8
70.3
52.0
47.0
39.4
85.3
37.2
31.8
53,9
56.6
36.5
46.0
75.3
$5.5
19.7
AcuRank-H
74.6
70.8
70.5
52.2
47.3
40.4
85.8
37.4
32.1
53.7
56.8
37.5
46.0
75.4
55.7
41.7
AcuRank IIll
74.7
70.6
51.9
47.0
40.0
86.1
37.5
$4.4
57.8
36.1
75.4
55.8
First-stage retrieval: BM25
top 1000
Reranker:
RankZephyr- 7B
BM25
50.6
48.0
44.6
26.9
26.2
30.4
59.5
32.2
33.0
39.5
40.7
44.2
31.8
67.9
41.1
0.0
SW-1
75.1
78.8
71.5
57.5
49.5
40.9
80.7
38.0
28.9
51.0
48.0
30.9
48.0
76.4
56.2
94.6
TaurRank-1
75.4
76.6
71.7
56.6
49.8
42.1
82.7
36.6
50.9
59.9
33.0
45.5
72.8
56.0
117.1
AcuRank
76.7
75.3
73.1
59.3
53.5
41.0
85.0
37.0
30.7
56.5
63.2
36.2
48.8
76.0
58.0
68.4
56.0
AcuRank-Hie
AtuRant-11
100
55.5
TS-35
Spearman o -0.27
80
p-value 9.3e-10
Aug. NDCG@10 (9)
TS-14
Touraank3
55.0
AcuRank-10
burRankk2
15-10
60
AcuRank-3
54.5
40
Method family
54.0
Sliding Windows (SW)
TourRank
Trueskill-Staicc
53.5
MurRank-11
AcuRank
0.0
0.2
(lower harder)
Calls
Correlation be- tween WIG-based query dif- ficulty and # reranker calls (Section. (.3)
Figure 3:
Figure 2: Pareto curves showing the trade-off between accuracy (NDCG@ 10) and efficiency (# reranker calls) across reranking methods.
improvement from AcuRank-9 to full AcuRank despite similar increase in cost, highlighting the advantage of adaptively allocating computation based on uncertainty.
Beyond the number of reranker calls, we further evaluate efficiency (1) average window size, (2) input length, (3) end-to-end latency, and (4) floating-poin operations (FLOPs), as reported in Table Under comparable reranker budgets, AcuRank exhibits consistently higher efficiency across these measures, offering a more faithful assessment than call counts alone. In fact, the number of reranker calls disadvantage AcuRank over basclines. Since AcuRank adaptively partitions uncertain candidates with a maximum window size of C==20, this leads to shorter inputs with smaller context numbers some stages. Results in Table confirm that AcuRank achieves faster runtime and lower input length despite operating under a similar number of calls, with up to 20% reduction in input length and latency 19/2//0. and 15-00% fewer FLOPs average.
confiri
Figure 2 visualizes the accuracy-efficiency trade-off across systems. AcuRank consistently lies along the Pareto frontier, achieving stronger accuracy at given budget or using fewer calls to reach the same target. contrast, TourRank attains relatively strong performance only at much higher cost, resulting in less favorable trade-off.

---

Table 2: Efficiency analysis of AcuRank vs. Sliding Window baselines, on two different setups, under a similar number of reranking calls. We compared with SW-3 instead of SW-2 for COVID* to match the number of calls, and all efficiency scores are averaged per query. AcuRank demonstrates better efficiency across different measures.
SW-2 (left) vs. AcuRank (right)
SW-I (left) vs. AcuRank-9 (right)
Metric
DL19
DL20
COVID
News
DL19
DL.00
COVID
News
NDCG@ 10 (1)
74.6 / 74.2
70.2/71.8
84.4/85. 85,3
52.7/53,9
74.0/ 73.3
70.2/714
54.1/83.2
52.3 /3,0
Calls (U)
18.0 18.2
18.0/ 16.3
27.0/21. 21.8
18.0 18.5
9.0 8,9
9.088.9
9.0/9.0
9.0/9.0
Window size (L)
20.0/
20.0/ 16.7
20.0/16. 16.3
20.0/
20.0/ 18.9
20.0
20.0/ 18.8
20.0/18. 18.9
Input length (L)
2156 / 1831
2162/ 1822
3991 / 3757
3989
2149 /2558
2152 2262
3990 / 3865
3992
3987
Latency (6) (.)
126 106
196/93
213/142 142
/79/150 150
93/58
92/59
73 67
88 84
PetaFLOPs (U)
0.61 0.52
0.62
1.3
1
0.30/ 0.29 0.31 0.29
0,59 / 0.57
0.59 /0.59
Finally, AcuRank supports flexible deployment under varying computational budgets. Its high- compute variants, HcuRank-H and AcuRank- -HH, apply stricter uncertainty thresholds and use more reranker calls, yielding incremental but consistent gains without early saturation. This behavior suggests that AcuRank can function as an anytime prediction method, where users can select a variant according to their available test-time budget and desired accuracy -uuuracc--fficincyyy trade-off.
5.2 Robustness across retrieval scenarios
Table 3 shows that AcuRank maintains strong performance across varying retrieval settings with different first-stage retrievers and reranker models. AcuRank consistently outperforms the fixed- computation baseline SW-1 under comparable reranker call budgets. With SPLADE++ED as the strst retriever, AcuRank achieves higher accuracy than SW-3 while using a similar number of calls as SW-1, effectively leveraging strong initial rankings to improve performance without incurring high cost. AcuRank also generalizes well to different reranking models. When using RankGPT (gpt-4. 1 1-mini) instead of RankZephyr, it still achieves higher accuracy than SW-1, suggesting that eicertainty-guider allocation remains effective regardless of the underlying reranker.
5.3 Adaptive allocation behavior
We investigate how uncertainty-guidd method adaptively allocates computation across queries and whether this behavior contributes to performance gains. To isolate the effect of adaptive allocation, compare AcuRank to TrueSkill-Statis but selects candidates solely based on estimated relevance /4, without considering uncertainty. As shown in Figure TrueSkill-Statie outperforms both Sliding Windows and TourRank in terms of securacy-efficieee trade-off. Nonetheless, AcuRank achieves even higher accuracy with fewer or comparable reranker calls, demonstrating that ranking uncertainty critical in further improving performance beyond static scheduling.
static variant that uses the same probabilistic scoring
To further examine how AcuRank adjusts computation at the query level, analyze the correlation between reranker call counts and query difficulty measured by Weighted Information Gain (WIG) [45) over 612 queries TREC and BEIR. WIG is computed from BM25 top-100 scores using log transform with window size k = 50, where lower values indicate more ambiguous relevance distributions. Figure shows significant negative correlation between WIG and the number of reranker calls issued by AcuRank (p- = 0.27. p < 10-$), confirming that more compute is allocated harder queries. This adaptive behavior is further detailed in Supplementary Section E comparing with the Sliding Window variant, where we observe that AcuRank allocates more computation to difficult queries while reducing computation on easier ones. We also report qualitative example of Bayesian update in the Supplementary Section E.3
5.4 Impact of design choices
Table presents an ablation study evaluating how individual design choices in AcuRank affect its overall effectiveness. Initializing TrueSkill scores from first-stage retrieval improves accuracy over default initialization (55.5 vs. 54.8), though at the cost of more reranker calls. Sequential partitioning outperforms random grouping in both accuracy and efficiency, confirming that comparing documents with similar relevance estimates yields more informative updates. For the stopping criterion, uncertainty-basse based termination achieves similar accuracy to the top-k-unchanged strategy

---

Table Results in NDCG@10 on BEIR using top-100 documents from (top) SPLADE++ED and (middle) Contriever stast retrieval, and RankZephyr reranker and (bottom) BM25 first-stage retrieval and RankGPT (gpt-4.1-man 1-mini) reranker. The top row in each block corresponds to the initial ranking without reranking, which serves as a lower-bound reference. Note that some queries retrieve fewer than 100 documents with BM25, slightly reducing average # calls.
Method
COVID NFC
Signal
News
R04
Touche
DBP
Scif
Avg.
Calls
First-stage retrieval: SPLADE + EE top 100
Reranker: RunkZephyr-7B
SPLADE+ED
71.1
34,5
29.6
39.4
45.8
24.4
44.1
69.9
44.8
0.0
SW-1
85.2
37.5
29.7
50.1
62.0
28.9
49.3
75.7
52.3
9.0
SW-2
85.6
37.8
28.9
51.3
62.8
29.2
49.6
75.5
52.6
18.0
SW-3
85.2
37.7
28.8
51.3
62.9
30.1
49.7
75.4
52.6
27.0
TourRank-1
82.5
37.4
28.5
51.5
60.7
29.7
48.9
73.7
51.6
13.0
TourRank-2
84.6
37.6
29.5
52.5
61.7
28.4
50.0
74.0
52.3
26.0
AcuRank
86.2
38.1
28.6
53.1
64.0
32.7
51.3
76.8
53.8
20.9
First-stage retrieval:
Contriever top 1001 Reranker: RankZephyr-78
Contriever
48.0
32.0
23.8
35.3
37.7
21.7
33.0
65.1
33.1
0.0
SW-1
70.8
38.3
26.5
49.9
54.9
30.4
46.1
75.4
45.3
9.0
SW-2
72.3
26.8
50.4
55.0
31.0
75.3
45.8
SW-3
72.6
38.6
26.6
50.5
55.0
31.3
46.9
75.4
45.9
27.0
TourRank-1
67.5
36.8
25.8
49.3
54.6
28.2
45.5
72.2
44.0
13.0
TourRank-5
70.9
38.1
26.4
52.2
57.6
30.1
47.0
74.4
46.0
65.0
AcuRank
74.4
39.1
27.1
53.0
57.2
33.1
47.9
75.2
47.4
20.1
First-stage retrieval: BM25 top-100
Reranker:
RankGPT (gpt-4.1 1-mini)
BM25
59.5
32.2
33.0
39.5
40.7
44,2
31.8
67.9
43.6
0.0
SW-1
84.5
37.9
33.3
49.5
61.5
35.7
46.3
78.7
53.4
8.8
AcuRank 86.4
38.3
34.8
52.1
31.9
46.2
77.2
53.7
20.8
Table 4: Ablation study on AcuRank's 's design choices with average NDCG@ 10 on TREC, BEIR, and all datasets. Init (V/ x): Initialize TrueSkill scores using first-stage scores vs. default values. Partitioning: Method for grouping uncertain documents (sequential order vs. random). Stopping Criterion: Terminate iterations when uncertain documents fall below threshold ((C < 10) or when top-k rankings stabilize across iterations. "_" indicates the default configuration is used. See
Appendix for detailed results on individual datasets.
Init Partitioning
Stopping Criterion
TREC
BEIR
All
# Calls
59.1
52.8
55.5
19.7
59.0
51.7
54.8
13,4
Random
58.8
52.7
55.3
22.6
Top-k stability
58.8
52.4
55.2
22.7
while reducing the number of reranker calls (19.7 vs. 22.7). Taken together, these results show that each component of our method meaningfully contributes to the method's 's effectiveness and that the default configuration offers a strong balance between accuracy and computational efficiency.
6 Conclusion
We introduce AcuRank, novel listwise reranking method that performs adaptive computation guided by uncertainty-awarr relevance modeling. Our approach maintains probabilistic relevance estimates using TrueSkill and selectively allocates reranking effort to documents with high ranking uncertainty. By focusing computation on ambiguous candidates, AcuRank consistently outperforms fixedccopputation baselines across TREC-DL and BEIR, achieving better eocuracy-efficienn trade- offs. Beyond a single algorithm, AcuRank serves as a flexible framework for uncertainty-aware adaptive computation in listwise reranking, providing principled foundation based on probabilistic modeling. This formulation enables fine-grained control over the reranking process and opens opportunities for future research in uncertainty-guide retrieval.
10

---

Acknowledgement
Gyuwan Kim thanks Prof. Tao Yang and Prof. Xifeng Yan at UC Santa Barbara for their valuable feedback and insightful suggestions throughout the course of this work. Soyoung Yoon thanks Jinwoo Kim and the anonymous reviewers of our NeurIPS 2025 submission for giving constructive feedbacks to improve the quality of our paper.
This work was partly supported by Institute of Information communications Technology Planning & Evaluation (ITTP) grant funded by the Korea (evermmen((MSTT) [NO.RS-2021-15] 1343, Artificial Intelligence Graduate School Program (Seoul National University)). and the National Research Foundation of Korca(NRFF grant funded by the Korea government(MSIIT) (No. RS-2024-004 14981), and the Ministyyy of Science and ICT), Korea, under the ITIC((nfomaation Technology Research Center) support program(1ITP-201) SELLUUTP-225-2000 2025-2020-0-01788 supervised by the IITP(Inteetute for Information & Communications Technology Planning & Evaluation).
References
[1] Stephen Robertson, Hugo Zaragoza, al. The probabilistic relevance framework: Bm25 and beyond. Foundations and Trends@ in Information Retrieval, 3(4):333-389, 2009.
[2] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6769 6781,, 2020.
[3] Yutao Zhu, Huaying Yuan, Shuting Wang. Jiongnan Liu, Wenhan Liu, Chenlong Deng, Haonan Chen, Zheng Liu, Zhicheng Dou, and Ji-Rong Wen. Large language models for information retrieval: A survey. arXiv preprint arXiv: 2023.
[4] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Haofen Wang, and Haofen Wang. Setrieval-augmenteed generation for large language models: A survey, XrXiv preprini 2r 10997, 2, 2023.
[5] Rodrigo Nogueira and Kyunghyun Cho. Passage re-ranking with bert. arXiv preprint arXiv:1901.04085. 2019.
[6] Zhen Qin, Rolf Jagerman, Kai Hui, Honglei Zhuang, Junru Wu, Le Yan, Jiaming Shen, Tianqi Liu, Jialu Liu, Donald Metzler, Xuanhui Wang, and Michael Bendersky. Large language models are effective text rankers with pairwise ranking prompting. In Findings of the Association for Computational Linguistics: NAACL 2024, pages 1504-1518, 2024.
[7] Honglei Zhuang, Zhen Qin, Rolf Jagerman, Kai Hui, Ji Ma. Jing La, Jianmo Ni, Xuanhui Wang, and Michael Bendersky. Rankt5: Fine-tuning 15 for text ranking with ranking losses. In Proceedings of the 46th Internationall ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2308-23133 2313, 2023.
[8] Ronak Pradeep, Sahel Sharifymoghaddam, and Jimmy Lin. Rankvicuna: Zero-shot listwise document reranking with open-source large language models. arXiv preprint arXiv:2309. /5088, 2023.
[9] Ruicheng Xian, Honglei Zhuang, Zhen Qin, Hamed Zamani, Jing Lu, Ma, Kai Hui, Han Zhao, Xuanhui Wang, and Michael Bendersky. Learning list-level -innarnnn representations 10764
for ranking, 2023. URL
[10] Mofetoluwa Adeyemi, Akintunde Oladipo, Ronak Pradeep, and Jimmy Lin. Zero-shot cross- lingual reranking with large language models for low-resource languages. In Lun-Wa Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 650-656, Bangkok, Thailand, August 2024. A Association for Computational Linguisties. doi: 10. 10.18653/v122024 acl-short.59. URL ht /ccl http//olocnnoooooooooooooooooooe .or.lloooooorooooooooooo 2024. acl mollsshott.59.
11

---

[11] Weiwei Sun, Lingyong Yan, Xinyu Ma, Shuaiqiang Wang, Pengjie Ren, Zhumin Chen, Dawei Yin. and Zhaochun Ren. chatgpt good at search? investigating large language models as re-ranking agents. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 14918-14937, 2023.
[12] Ronak Pradeep. Sahel Sharilymoghaddam. and Jimmy Lin. Rankzephyr: Effective and robust zero-shot listwise reranking is breeze! arXiv preprint
2023.
[13] Xueguang Ma, Xinyu Zhang, Ronak Pradeep, and Jimmy Lin. Zero-shot listwise document reranking with a large language model. arXiv preprint arXiv:2305.0211 2023.
[14] Yiqun Chen, Qi Liu, Yi Zhang, Weiwei Sun, Xinyu Ma. Wei Yang, Daiting Shi, Jiaxin Mao, and Dawei Yin. Tourrank: Utilizing large language models for documents ranking with tournament-inspired strategy. arXiv preprint arXiv:2406. / 1678, 2024.
[15] Ralf Herbrich, Tom Minka, and Thore Graepel. TrueskilJTM; A bayesian skill rating system. Advances in Neural Information Processing Systems, 19, 2006.
[16] Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M Voorhees. Overview of the trec 2019 deep learning track. arXiv preprint arXiv:2003.07820, 2020.
[17] Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. Beir: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[18] Andrew Drozdov, Honglei Zhuang, Zhuyun Dai, Zhen Qin, Razieh Rahimi, Xuanhui Wang. Dana Alon, Mohit lyyer. Andrew McCallum, Donald Metzler, et al. Parade: Passage ranking using demonstrations with 1lms. In Findings of the Association for Computational Linguisties: EMNLP 2023, pages 14242-14252 2023.
[19] Xueguang Ma, Liang Wang, Nan Yang, Furu Wei, and Jimmy Lin. Fine-tuning Ilama for multi-stage text retrieval. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2421-2425, 2024.
[20] Devendra Sachan, Mike Lewis, Mandar Joshi, Armen Aghajanyan, Wen-tau Yih, Joelle Pineau, and Luke Zettlemoyer. Improving passage retrieval with zero-shot question generation. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing. pages 3781-3797, 2022.
[21] Honglei Zhuang, Zhen Qin, Kai Hui, Junru Wu, Le Yan, Xuanhui Wang, and Michael Bendersky. Beyond yes and no: Improving zero-shot IIm rankers via scoring fine peee-graied relevance labels. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 2: Short Papers), pages 358-370 2024.
[22] Ronak Pradeep. Rodrigo Nogueira, and Jimmy Lin. The expando-mono-duo design pattern for text ranking with pretrained sequence-to-squeeee models. arXiv preprint arXiv:2101.0566) 2021.
[23] Jian Luo, Xuanang Chen, Ben He, and Le Sun. Prp-graph: Pairwise ranking prompting to llms with graph aggregation for effective text re-ranking. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5766-5776. 2024.
[24] Shengyao Zhuang, Honglei Zhuang, Bevan Koopman, and Guido Zuccon. setwise approach for effective and highly efficient zero-shot ranking with large language models. Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 38-47, 2024.
[25] Anonymous. Budget-constrained document re-ranking with bayesian LM-based pairwise comparisons. OpenReview preppinn, ACI ARR 2025 February submission, 2025. URL Accessed: 2025-10-21.
12

---

[26] Andrew Parry, Sean MacAvaney, and Debasis Ganguly. Top-down partitioning for efficient list-wise ranking. arXiv preprint arXiv:2405. 14589, 2024.
[27] Soyoung Yoon, Eunbi Choi, Jiyeon Kim, Hyeongu Yun, Yireun Kim, and Seung seung-won won Hwang. Listt5: Listwise reranking with fusion- in-decoder improves zero-shot retrieval. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 2287-2308, 2024.
[28] Wenhan Liu, Xinyu Ma. Yutao Zhu, Lixin Su, Shuaiqiang Wang, Dawei Yin, and Zhicheng Dou. Coranking: Collaborative ranking with small and large ranking agents, 2025. URL
https://arxi..orr/abb/2250.. 23427
[29] Wenhan Liu, Yutao Zhu, and Zhicheng Dou. Demorank: Selecting effective demonstrations for large language models in ranking task, 2024. URL
16332
[30] Daniel Cohen, Bhaskar Mitra, Oleg Lesota, Navid Rekabsaz, and Carsten Eickhoff. Not all relevance scores are equal: Efficient uncertainty and calibration modeling for deep retrieval models. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 164-664, 2021.
[31] Alex Graves. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv: 1603. 08983, 2016.
[32] Andrei Broder, David Carmel, Michael Herscovici, Aya Soffer, and Jason Zien. Efficient query evaluation using two-level retrieval process. In Proceedings of the twelfth international conference on Information and knowledge management, pages 426-434, 2003.
[33] Debasis Ganguly and Emine Yilmaz. Query-specific variable depth pooling via query perfor- mance prediction. In Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2303-2307, 2023.
[34] Chuan Meng, Negar Arabzadeh, Arian Askari, Mohammad Aliannejadi, and Maarten de Rijke. Query performance prediction using relevance judgments generated by large language models. arXiv preprint arX1v:2404.01012, 2024.
[35] Negar Arabzadeh, Chuan Meng, Mohammad Aliannejadi, and Ebrahim Bagheri. Query per- formance prediction: From fundamentals advanced techniques. In European Conference on Information Retrieval, pages 381-388. Springer, 2024.
[36] Chuan Meng, Negar Arabzadeh, Arian Askari, Mohammad Aliannejadi, and Maarten de Rijke. Ranked list truncation for large language model- re-ranking. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 141-151, 2024.
[37] John Joon Young Chung, Wooseok Kim, Kang Min Yoo, Hwaran Lee, Eytan Adar, and Minsuk Chang. Talebrush: Sketching stories with generative pretrained language models. In Proceedings of the 2022 CHI Conference on Human Factors in Computing Systems, CHI '22, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 1488391557. doi: 241145/3491102.5500
URL http:://dooooc.oooo org/10. 1145/ 3491 102. 3501819
[38] Joon Sung Park, Joseph C. Brien, Carrie J. Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents: Interactive simulacra of human behavior, 2023, URL
https://arxiv www.:/ogggbb///eeeee 2304.03442
[39] Omar Shaikh, Valentino Chai, Michele Gelfand, Diyi Yang, and Michael S. Bernstein. Rehearsal: Simulating conffict to teach conflict resolution, 2024. /ttlhttts://arxi...o abs/2309 12309
[40] lain Mackie, Jeffrey Dalton, and Andrew Yates. How deep is your learning: the dl-hard annotated deep learning dataset. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2335-2341, 2021.
13

---

[41] Kalervo Järvelin and Jaana Kekäläänen. Cumulated gain- based evaluation of ir techniques. ACM Trans. Inf. Syst. 20(())422 446, oct 2002. ISSN 1046-8188, doi: 10.1145/5824155522418
/tt.htttp///dd..og///.... 111./11245555552222222 582418
[42] Thibault Formal, Carlos Lassance, Benjamin Piwowarski, and Stéphane Clinchant. From distillation to hard negative sampling: Making sparse neural ir models more effective, 2022.
/Rthttpss://arr
http::ttts///m /tttps:///axiv..... wwtrrriv.oorgabb////2/e 04733
[43] Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. Unsupervised dense information retrieval with contrastive learning, 2022. URL httptpss//aaxii..rr///////////// 09118
[44] Jimmy Lin, Xueguang Ma, Sheng-Chich Lin, theng-Homy Yang, Ronak Pradeep, and Rodrigo Nogueira. Pyserini: A Python toolkit for reproducible information retrieval research with sparse and dense representations. In Proceedings of the 44th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2021), pages 2356-2362, 2021.
[45] Yun Zhou and W Bruce Croft. Query performance prediction in web search environments. In Proceedings of the 30th annual international ACM SIGIR conference Research and development in information retrieval, pages 543-550, 2007.
[46] Meta AI. Llama 3.3 70B Instruct model card.
ww/eeto- aammeaalcaa/mmmmtalllaaaaa LIama- 3. 3-8 Instruct] 2024. Model release date: 6 Dec 2024. Accessed 23 May 2025.
[47] Harsh Trivedi, Niranjan Balasubramanian. Tushar Khot, and Ashish Sabharwal. Interleaving retrieval with chain-of-thought reasoning for knowledge-intensiee multi-step questions. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 10014-10037, 2023.
[48] SU Hongjin, Howard Yen, Mengzhou Xia, Weijia Shi, Niklas Muennighoff, Han-yu Wang, Liu Haisu, Quan Shi, Zachary Siegel, Michael Tang, et Bright: A realistic and challenging benchmark for reasoning-intensive retrieval. In The Thirteenth International Conference Learning Representations.
[49] Chenghao Xiao, Thomas Hudson, and Noura Al Moubayed. Rar-b: Reasoning as retrieval benchmark. arXiv preprint arXiv:2404.06347 2024.
[50] Yuelyu Ji, Zhuochun Li, Rui Meng, and Daqing He. Reasoningrank: Teaching student models rank through reasoning- knowledge distillation. arXiv preprint arXiv:2410.05/68, 2024.
[51] Tong Niu, Shafiq Joty, Ye Liu, Caiming Xiong, Yingbo Zhou, and Semih Yavuz. Judger- ank: Leveraging large language models for iintoinngittensivee reranking. arXiv preprint 1rXiv:2411.00144 2024.
[52] Orion Weller, Kathryn Ricci, Eugene Yang. Andrew Yates, Dawn Lawrie and Benjamin Van Durme. Rankl: Test-time compute for reranking in information retrieval. arXiv preprint arXiv:2502.18418, 2025.
[53] Shengyao Zhuang, Xueguang Ma, Bevan Koopman, Jimmy Lin, and Guido Zuccon. Rank- rl: Enhancing reasoning in llm-based document rerankers via reinforcement learning. arXiv preprint arXiv:2503. 06034, 2025.
[54] Wenhan Liu, Xinyu Ma. Weiwei Sun. Yutao Zhu, Yuchen Li, Dawei Yin, and Zhicheng Dou. Reasonrank: Empowering passage ranking with strong reasoning ability, 2025. URL https///axiiv.og/aab////// 07050
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract (lines 1-14) and Introduction explicitly state the core contribu- tions, which is (i) probabilistic relevance modeling with TrueSkill and (ii) uncertainty-aware
adaptive computation, and the empirical scope matches these claims.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We added the the limitations section at the Appendix, at Section
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We clearly state our problem formulation in Section 3.1 and the underlying theorem in Section 3.2 with algorithms at Algorithm
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 4 detail datasets, retriivaalrerannking models, hyper-parameters, stop- ping criteria and ablation settings, providing sufficient information for reproduction.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Public datasets (TREC-DL, BEIR) used, and public code repository is also linked, with the github url of /f/httpss//githuut Comm//oooong///Accumm
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Section 4.3 enumerates retriever/reranker configurations, window size m, uncertainty threshold e, stopping criterion T, and compute-budget variants.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report statistical significance (spearman p with p value for Fig.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed reproduce the experiments?
Question:
15

---

Answer: [Yes]
Justification: All experiments were conducted on a single NVIDIA A6000 GPU (48GB We also focus reporting the number of reranker calls show improved efficiency on our method.
VRAM) (Section 4.2
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics http::///eerrro..cccooooooccccca
Answer: [Yes]
Justification: This work builds on publicly available text corpora and complies with data-use licences; no personal or sensitive data are processed.
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work focuses on efficient and effective listwise reranking.
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: No new high-risk model or dataset is released.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite datasets and baseline code, and the license terms are explained in Supplementary Section C.2
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No new dataset, model checkpoint is introduced in the submission. Our method can be applied upon different listwise reranking models.
Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The study involves no human-subject crowdsourcing component.
15. Institutional review board (IRB) approvals or equivalent
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human-subject research conducted, so IRB approval is not applicable.
16. Declaration of LLM usage
16

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification:
Section 4 explain how large language models (RankZephyr, RankGPT)
used as listwise rerankers, including prompt size and grouping strategy.
17

---

Supplementary Materials for AcuRank: Uncerlainty-Aware Adaptive Computation for Listwise reranking
A Overview
This supplementary material provides additional details and extended results for our AcuRank framework. Specifically:
Section B describes the mathematical foundations of our Bayesian modeling approach, including the TrueSkill update equations and our efficient approximation of cumulative rank distributions. We also report the computational overhead of TrueSkill and additional experimental justification of the variance initialization.
specciies our experimental setup, including hardware specifications, software configura- tions, datasets, licenses, and modifications to baseline implementations.
Section D presents comprehensive experimental results, including dataset-wise performance metries omitted from the main paper due to space constraints. This includes extended results for all baselines (Tables 1-3), full numbers for the -raattill-Static variants shown in Figure 2, additional experiments with Rank Vicunaaen and L.ama-3.3-70B-Instrue demonstrating generalizability of our approach, and extended analysis on AcuRank's sensitivity to uncertainty thresholds.
Section E provides a deeper analysis of AcuRank's ' adaptive behavior, including query-level compute allocation patterns and a breakdown of performance on easy versus hard queries. Also, we provide a qualitative example of the Bayesian update of AcuRank.
Section discusses the AcuRank's robustness among scalability and ranking stability varying n. and document addition.
Section G discusses current limitations and potential future directions.
Section lists the exact prompt templates used with RankZephyr, Rank Vicuna, and Llama-3.3- 70B-Instruct for listwise reranking.
B
Supplement on Bayesian modeling and score updates in TrueSkill
B.1
TrueSkill as a Bayesian model
TrueSkill
[5 models the latent relevance (originally, "skill") of each document 2; Gaussian random variable, x, [N,,, of), starting with a prior and updating it iteratively via Bayesian inference. Each listwise reranker output, denoted (D) is treated noisy evidence about pairwise preferences among a subset D' of documents, where A is the reranking model. Using belicf' propagation on factor graph, TrueSkill analytically updates the posterior distribution to
p(z: ((':: = NN(,, (o.)²)
We denote the current update round by t. At t = 0, (4) ( ,0))) represents the prior initialized from first-stage retrieval scores. After observing the reranking output, the posterior is updated to (ng (++)) . ((+1).
B.2 Approximating the cumulative rank distribution
We approximate the probability that document D; ranks within the top positions as
P(r. S P(x, > t(r)). where P(a,>>t(n) t(r))(())))))))))))))))
The lent-hand side is the probability that at most r other documents outrank D, The right-hand side approximates this count by evaluating whether æ; exceeds a threshold ((r) calibrated such that the expected number of documents exceeding this threshold equals r. This approximation becomes accurate under two assumptions: (1) the latent scores I, follow independent Gaussian distributions with similar variances, and (2) the number of candidates is sufficiently large, that
18

---

Table 5: Ablations on initializing variance (BM25 top-100, RankZephyr) for AcuRank. p/3 corresponds to the final configuration used in AcuRank.
DL19
DL20
DL21
DL.22
DL23
DL-H COV.
NFC Sig. News R04 Tou. DBP Scif Avg.
Calls
8 (fixed)
74.1
72.6
70.5
51.3
46.9
39.5
85.5
36.9 31.1 52.5 56.2 33.3 45.1 76.4
13,1
n//
74.1
71.3
70.7
51.8
46.2
39,4
85.2
37.4 32.0
52.6 56.3 37.3
46.0 75.7
55,4
16.4
(/orr))))
74.2
71.8
70.3
52.0
47.0
39.4
85.3
37.2 31.8 53.9 56.6 36.5 46.0 75.3
55.5
19.2
the expected number of exceedances concentrates near its mean by the law of large numbers. This provides an efficient closed-form alternative to the expensive (nz²) dynamic programming approach for computing the full ranking distribution over permutations. Instead of enumerating all possible rankings, we approximate P(r: S r) using single Gaussian tail probability, 1 +(-).
B.3 TrueSkill score update equations
The reranking over each batch B is treated as multi- player game. The observed ranking outcome is given by gB,MM, For every adjacent document pair in this order, win-loss factor defined to model their pairwise preference. Applying message passing on the factor graph yields the following canonical update equations for each document D;:
(1-1) Pi
of X, = 14
(0
(o(14))2= = oo (1-22)))
c
where c -=VED,eslo 82). The values À and v are closed-form functions derived from the win probability between adjacent items (see Herbrich et al. [5] for a full derivation). Intuitively, when a document ranks higher than expected, its mean (4; increases. Unexpected outcomes also reduce o, reflecting greater confidence in the document's estimated relevance.
Side note on implementation. We employ the Python trueskill library The relevance of each candidate passage represented as a trueskill Rating class. After the listwise reranker outputs an ordering, we update all ratings by calling trueskill. rate function with the argument aeting_groups list of ratings, and ranks=[0, ......,,,, n]. where n is the number of passages. The function returns list of posterior ratings containing (μ, o), which serve as the priors for the next iteration
B.4 Proportional uncertainty initialization based on retrieval scores
We initialize each document's relevance score Gaussian distribution parameterized by its first- stage retrieval score. Specifically, for each document Dj with retrieval score 8;, we set the mean and standard deviation as 14 5; and a; p./3. This initialization preserves the relative scale of the retrieval scores while explicitly modeling their uncertainty. A higher retrieval score indicates greater expected relevance (14; 1), but it may also be more prone to overestimation. To reflect this, we assign proportionally larger prior uncertainty (a, 1) to such documents. The 1/3 ratio follows the standard μ: 0=31= default used in TrueSkill, and yields conservative displayed rating R, = μ44 3o, = 0. This provides a non negative lower bound (semantically natural for relevance), while leaving substantial headroom for upward revision reranking evidence arrives. Statistically. (n4 (4i As + s4s] = [0, 2p²,] corresponds to [14: + 30,] since 30; = 1ki enclosing s 99.7% of Gaussian mass; thus the prior is cautious yet flexible, centered the retrieval signal but amenable change. Using a larger multiple (e.g. a; = pz/2) makes the prior overly diffuse and weakens the retrieval signal, whereas a smaller multiple would risk overconfidence and slower correction; the three-sigma choice strikes a practical middle ground that is widely adopted in TrueSkill deployments.
Experimental justification. To further support this design, we conduct ablation study comparing three initialization variants: (1) fixed uncertainty (a=8), (2) more conservative variant (a, /2). and (3) our default setting (a, /333). As shown in Table the default configuration performs best overall, while all variants preserve the same qualitative trends. This indicates that AcuRank is robust the specific choice of initialization and supports the effectiveness of the three-sigma prior.
http:://russkll.or//ttuwkkkl
19

---

Table 6:
Comparing per-query end-to-end latency with the TrueSkill computational overhead, on
four selected benchmarks.
News (AcuRank-9) (AcuRank) (AcuRank-9) (AcuRank) (AcuRank-9) (AcuRank) (AcuRank-9) (AcuRank)
DL19
DL19
DL20
DL20
COVID
COVID
News
Total (8)
58.28
105.98
59.28
93.30
67.32
142.08
83.65
149.58
TrueSkill (S)
0.06
0.11
0.06
0.10
0.06
0.13
0.06
0.11
TrueSkill ratio (%)
0. 1.10
0.10%
0.10%
0.11%
0.09%
0.09%
0.07%
0.08%
B.5
Score refinement (Algorithm 1, Line
After each reranker call, perform the following update procedure:
Convert the returned ranking over the current batch B into set of pairwise win-loss observations.
2.
Run one round TrueSkill message passing to update each document's parameters (14, as) B based on these observations.
Recompute the ankkin-unncertinng scores 8; = P(æ: > (())) guide selection in the next iteration.
This iterative posterior refinement progressively sharpens the relevance estimates. As a result, the uncertainty values naturally decrease over time. Documents whose ranks stabilize early tend to exit the uncertain set, allowing us to avoid unnecessary reranker calls and reduce overall computation.
B.6 Computational overhead of TrueSkill
We additionally measured and reported the computational overhead of TrueSkill at Table which was negligible compared to the cost LLM reranker calls. On the DL19 benchmark, the total runtime of AcuRank was approximately 58.28 seconds, among which the cumulative time spent TrueSkill updates was only 0.06 seconds (0. 1)). The portion of running Trueskill versus the total process was consistent (0.1%) across subsets of data (DL19, DL20, TREC-COVIE AcuRank. This was measured using time. t time () around the call to trueskill. rate (), which can be further observed the official codehase. The trueskill rate function performs lightweight updates to the mean and variance of document scores based on closed-form Gaussian updates, which efficiently computed CPU. This confirms that nearly all computation time in AcuRank is spent on LLM calls, with minimal overhead from the uncertainty modeling.
News) and for AcuRank-9 and
C Implementation Details
C.1 Hardware specifications and software configurations
Experiments were conducted on either (i) an ASUS ESC8000-E11 server equipped with dual 4th -en Intel Xeon processors, 64 CPU threads, 1.1 TB RAM, and eight NVIDIA A6000 GPUs (48 GB each), (ii) workstation with eight RTX 3090 GPUs (24 GB each).
Compute nodes:
Inference stack: All LLM inference was performed using the transformers library, without acceleration backends such vLLM or FastChat. Greedy decoding was used throughout, with fixed random seed to ensure reproducibility.
We release a complete end-to-end reproduction script, packaged as a .zip archive, which replicates reported experiments.
Reproducibility:
Token limits:
Following the RankLLM codebase d all inputs were truncated to a maximum of 4,096
tokens.
Default hyperparameters: Unless otherwise specified, we adopt the default hyperparameter settings provided by the RankLLM implementation.
20

---

C.2 Datasets and licenses
Abbreviations. For brevity, we use the following shorthands throughout our tables: DL19-DL23 (TREC-DI. 2019-2023), DL-H (DL-Hard), COVID (TREC-COVID), NFC (NFCorpus), Signal (Signal- (M), News (TREC-News), R04 (Robust04), Touche Tobbis-Touche2220), DBP (DBPedia), and Sci (SciFact).
TREC-DL (2019-2023 tracks). The Topics and Qrels are in the public domain as U.S. Gov- ermment work 10 The underlying corpus (MS MARCO + ORCAS) is released by Microsoft for non-commercial research purposes only, with no IP rights to the documents and "as-is" usage at the user's own risk
DI-HARD [40]. We use the annotation files and BM25 retrieval result files hosted on GitHub The repository does not specify formal license. Following author guidance consistent with MS MARCO terms (see footnote TT), we use the data strictly for non-commercial academic research.
(https://g thub. com/ coom/grill-labDL-...
The framework code for BEIR under the Apache 2.0 license Each constituent dataset retains the license of its original source (e.g., public-domain for TREC-COVID). For our experiments, we use pre-computed BM25 and SPLADE top-1000 1000 retrieval runs (included in our anonymized supplementary code), which are released under the BigScience OpenRAIL-M license.
BEIR 177.
TrueSkill rating algorithm. We rely on the open-source Python package trueskill 11 (v0.4.5) distributed under the permissive BSD 3-Clause License. The TrueSkil/ trademark and the original Bayesian rating system remain the property of Microsoft, who permits the name and algorithm be used only in Xbox Live titles or non-commercial projects 14 Our usage complies with these terms, as is strictly limited to non-profit academic research.
C.3 Evaluation protocol
All reported metric values are rounded to one decimal place for consistency, For each method, we first compute the mean number of reranker calls within each dataset. Specifically, we calculate average across all queries belonging to a given dataset, resulting in one mean value per dataset. We then compute the overall value reported in our tables by taking simple unweighted average of these 14 per-dataset means. This ensures that each dataset contributes equally, regardless of the number of queries contains. Note that this a datasct-level macro average, not a micro average computed over all individual queries pooled together.
C.4 Sliding windows baseline
The sliding windows baselines rerank the top-100 candidates using fixed-size windows of size 20 and stride of 10. This configuration results in nine overlapping windows per query. When the list length is not divisible by 20, we form a final, smaller window containing the remaining documents. This ensures full coverage of all retrieved candidates.
C.5 TourRank baseline
We adapted the public TourRank implementation 15 to handle candidate sets with fewer than 100 passages. The original code assumes (D] = 100 and executes five tournament stages. However, for some queries in certain datasets (e.g., NFCorpus), the query text is extremely short, BM25 retrieves fewer than 100 candidate documents (DD) < 100). To handle such cases, we added the simple stage-skip rule below and one-line boundary check to the original grouping function, in order to avoid redundant inference and out-of-range errors. Our modifications are twofold:
"https://trec.nist..r
https::/miccrooff..giitii
http:/githuuu.oommmmmme.e io/msmarco/
htttss///iitubbbcc////beeeerrrrt
https://rrusskillorrg////
21

---

Table 7: Full results corresponding to Table of the main paper, with annotated avg_ calls per dataset. Only SW-1 and TourRank-1 are shown because these variants used fixed computation per query; the counts for SW-N TourRank-N for N > 1 can be obtained by multiplying the reported numbers by N. Slightly lower values on NFCorpus, DBPedia, and SciFaat reflect queries that retrieve fewer than 100 documents with BM25, which proportionally reduces the average number of calls.
TREC-DL. D1.19 D1.20 D1.11 D1.22 DL.23 DL.H COVID NFC Signal News R04 Touche DBP Seif Avg. # Calls
BEIR
Method
stat- retrieval: BM25 top Reranker: RankZephy--BB
BM25 (no rerank)
48.0
44.6
26.9
26.2
30.4
59.5
32.2
33.0
39.5
40.7
31.8
41.1
0.0
aalls
0
0
0
0
0
0
0
0
0
0
0
0.0
0.0
SW-1
74.0
70.2
69.5
51.5
44.5
38.6
84.1
36.8
32.0
52.3
54.0
32.4
44.5
75.5
54.3
8.8
avg___ee calls
9.0
9.0
9.0
9.0
9.0
9.0
9.0
6.2
9.0
9.0
9.0
9.0
9.0
9.0
8.8
8.8
TourRank-1
74.2
68.2
69.6
51.1
45.2
38.1
81.8
36,5
30.7
51.9
54.5
31.2
43.2
71.3
53.4
12.7
-va__aalls calls
13.0
13.0
13.0
13.0
13.0
13.0
13.0
9.3
13.0
13.0
13.0
13.0
13.0
13.0
12.7
12.7
AcuRank-9
73.3
71,4
70.1
50.1
45.3
39.5
83.2
36.8
30.8
53.0
56.0
37.1
44.7
73.3
54.6
8.8
avg -ava__calll calls
9.0
8.9
9.0
9.0
9.0
9.0
9.0
6.7
8.9
9.0
8.9
9.0
8.9
8.9
8.8
8.8
AcuRank
74.2
71.8
70.3
52.0
47.0
39.4
85.3
37.2
31.8
53,9
56.6
36.5
46.0
75.3
55.5
19.7
avg culls
18.2
16.3
15.5
18.7
17.4
16.3
21.8
23.3
30.4
18.5
17.8
19.4
21.5
20.1
19.7
19.7
AcuRank-H
74.6
70.8
70.5
52.2
47.3
40.4
85.8
37.4
32.1
53.7
56.8
37.5
46.0
75.4
55.7
41.7
avg aava__calll calls
36.9
35.3
29.6
40.0
36.6
32.9
43.9
51.5
58.8
38.9
37.6
44.2
48.4 49.0
41.7
41.7
AcuRank-HH
74.7
718
70.6
51.9
47.0
40.0
86.1
37.5
31.3
54.4
57.8
36.1
46.0
75.4
55.8
$7.2
avg_calls
53.3
46.6
43.4
60.6
60.2
48.9
60.2
59.8
75.2
52.2
50.6
57.0
68.6
63.9
57.2
57.2
First-slage retrieval: BM25 top 1000
Reranker:
RankZephyr-78
BM25
50.6
48.0
44.6
26.9
26.2
30.4
59.5
32.2
33.0
39.5
40.7
44.2
318
67.9
41.1
0.0
+> avlg_alls
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0.0
0.0
SW-1
75.1
78.8
71.5
57.5
49.5
40.9
80.7
38.0
28.9
51.0
48.0
30.9
48.0
76,4
56.2
94.6
avg avg__aallll calls
99.0
99.0
99.0
99.0
99.0
99.0
99.0
40.1
99.0
99.0
99.0
99.0
98.4
97.0
94.6
94.6
AcuRunk
76.7
75.3
73.1
59.3
53.5
41.0
85.0
37.0
30.7
56.5
63.2
36.2
48.8
76.0
58.0
68.4
avl_calls
67.8
65.6
67.6
74.4
72.0
68.8
72.8
40.6
82.2
68.0
68.7
70.4
74.2
64.7
68.4
68.4
Table 8: Results in NDCG@ 10 on BEIR with two alternative first-stage reranker configurations, corresponding to Table 2 of our main paper. For every method that performs reranking, the dataset- wise average number of passes is given in the immediately following row (prefixed by -))
Method
COVID NFC
Signal
News
R04
Touche
DBP
Scif
Avg. Calls
stage retrieval: SPLADE+ + ED top-100
100
Reranker: RankZephyr
SPLADE+ED
71.1
34.5
29.6
39.4
45.8
24.4
44.1
69.9
44.8
0.0
SW-1
85.2
37.5
29.7
50.1
62.0
28.9
49.3
75.7
52.3
9.0
< avg__alll calls
9.0
9.0
9.0
9.0
9.0
9.0
SW-2
85.6
37.8
28.9
51.3
62.8
29.2
49.6
75.5
52.6
18.0
SW-3
85.2
37.7
28.8
51.3
62.9
30.1
49.7
75.4
52.6
27.0
AcuRank
86.2
38.1
28.6
53.1
64.0
32.7
51.3
76.8
53.8
20.9
aalls
17.7
17.4
28.4
28.4
18.5
18.1
20.4
18.2
20.9
20.9
First-stage retrieval: BM25 top-100
Reranker:
RankGPT (gpt- 4. 1-mini)
BM25
59.5
32.2
33.0
39,5
40.7
44,2
31.8
67.9
43.6
0.0
SW-1
84.5
37.9
33.3
49.5
61.5
35.7
46.3
78.7
53.4
8.6
+ avg calls
avl_calls
9.0
6.2
9.0
9.0
9.0
9.0
9.0
9.0
8.6
8.6
AcuRank
86.4
38.3
34.8
52.1
63.0
31.9
46.2
77.2
53.7
20.8
callsallss
20.9
25.0
22.0
18.3
18.8
19.4
20.0
21.7
20.8
20.8
Stage skip rule. We skip Stages 1 through when [D] is less than or equal to 50, 20, 10, and respectively. When [D] < 2, we return the BM25 order directly.
Boundary check (grouping). We retain the original index modulo grouping logic from the public implementation and insert a simple boundary check (if idx < (Dn) to prevent IndexError.
D Extended experimental results
D.1 Average number of reranker calls per dataset
We report the number reranker calls per dataset with NDCG@ 10 scores, which correspond the Tables and Figures reported in the main paper. Table 7 the NDCG@ @ 10 scores for each dataset,
22

---

Table 3 in Table 9: Dataset-wise results in NDCG@ 10 of TrueSkill-taari with different configurations (BM25 top-100 100 + RankZephyr-7B), corresponding to Figure 2 of the main paper. TS-c represented as TS-N, where N = > Ci2 for short. The last two columns the macro average over 14 datasets and the macro mean number of reranker calls.
TREC-DL
BEIR
Avg. # Calls
Method
D1.19
D1.20
D1.21
DL.22
DL.23 DL.H
COVID
NHC Signal News R04
Touuce DBP
Seif
TS-10
74.4
71.2
69.9
45.7
39.8
82.6
37.0
31.9
52.5
55.8
37.2
45.4 74.6
54.9
[-1-2-]]
TS-14
75.0
71.8
70.2
51.1
45.6
40.5
83.6
37.0
31.3
53.8
56.2
36.7
45.7
74.8
55.2
13.8
[5333
TS-25
74.8
71.8
70.3
51.3
45.7
40.4
83.5
37.1
32.0
53.1
56.7
36.8
45.6
75.1
55.3
24.5
135-5555
TS-25
75.0
71.6
70.5
51.3
46.0
39.9
84.2
37.1
32.0
53.2
56.5
36.0
45.6
75.1
55.3
24.5
[5444444]
TS-35
75.5
72.0
70.7
51.5
45.8
40.1
84.4
37.0
31.1
53.9
56.1
35.9
45.3
75.8
55.4
34.4
Table 10: Dataset-wise NDCG@ 10 for the AcuRank design-choice ablation, corresponding to Table 3 of our main paper. For every variant the second line (prefixed by ->) reports the dataset-specific average number of passes.
TREC-DI.
BEIR
Variant
DL19
DL20
DL21
DL22
DL23
DL-H
COVID
NFC
Signal News
R04
Touche DBP
Seif
Avg.
Calls
AcuRank (default)
74.2
71.8
70.3
52.0
47.0
39.4
85.3
37.2
31.8
53,9
56.6
36.5
46.0
75.3
55.5
19.7
avg_ avg_calls
18.2
16.3
15.5
18.7
21.8
30.4
18.5
17.8
19.4
21.5
20.1
19.7
19.7
No Ist-stage init
74.1
70.8
70.9
52.0
47.3
38.8
84.3
36.8
30.5
52.1
55.3
33.5
44,9
75.8
54.8
13,4
5-) avg_calls
12.5
12.7
12.3
12.5
13.3
12.9
12.9
21.4
13.8
13.3
13.0
14.1
13.4
13.4
13.4
Random chunking
74.2
71.2
70.8
51.8
47.2
37.6
87.0
37.3
31.6
53,9
56.8
34.5
46.0
74.8
55.3
22.6
avg calls
17.4
17.4
19.6
18.1
25.7
34.4
19.6
19.6
23.4
23.7
22.6
22.6
Top-k stability stop
75.2
69.5
70.0
51.4
46.5
40.1
84.7
37.0
31.7
52.5
56.1
37.6
45.4
74.5
55.2
22.7
avgg_allls 22.3
20.3
18.0
22.8
20.7
20.1
23.7
21.6
29.3
22.1
22.2
24.4
24.5
25.3
22.7
22.7
along with the average number of reranker calls. These results complement Table T in the main paper by providing dataset-level breakdowns. Additionally, Table Table repoots the complete per-dataset results for TrueSkill-Static with different configurations shown in Figure 2. Table X summarizes dataset-wise results for the SPLADE++ED first-stage retrieval results and results with RankGPT (gpt-4.1 1-mini) as reranker, including the average number of passes, corresponding the main paper. Finally, Table 10 reportss the per-dataset average number of reranker calls and the resulting NDCG@ 10 for each design-choice variant, corresponding with Table 4 in our main paper.
key observation from these extended results that, unlike static approaches such as sliding windows or TourRank, method exhibits varying numbers of calls across different datasets. This adaptive behavior reflects our uncertainty-awe aware framework's ability to allocate computational resources based on the inherent difficulty and characteristics of each dataset.
D.2 Generalization across rerankers
To evaluate the generalizability of AcuRank across different reranking models and scales, we conduct comprehensive experiments using both RankVicuna- Vicuna-
g and 1imma--.--7B--nnttii 46) models.
Evaluation with Rank Vicuna-7B. We first test AcuRank using Rank Vicuna-7B (huggingface identifier of castorini irtr/anniinnii/eee warrranniannaaaaaaaaaaaa vicuna_7b. _bo_1] on BM25 top-100 retrieval results. As shown in Table II while Vicuna achieves lower absolute NDCG@ 10 scores than RankZephyr, AcuRank maintains its effectiveness pattern. Specifically, AcuRank-9 achieves +0.7 improvement over SW-1 that uses same number of calls (8.8). Meanwhile, AcuRank achieves +1.8 NDCG@ 10 improvement over SW-1 and +1.2 improvement over SW-3 despite using fewer calls (19.5 vs 26.4), and +1.5 improvement over 'ourRaak-22 using similar number of calls (25.5 vs 26.4). In summary, AcuRank consistently outperforms both sliding windows and TourRank baselines while requiring fewer reranker calls.
Evaluation with Llama-3.3 70B as a zero-shot reranker. To test whether AcuRank continues to yield benefits for larger. purely zero-shot rerankers, replaced our 7B parameter RankZephyr
23

---

Table 11: Results in NDCG@ 10 using BM25 top-100 first-stage retrieval with Rank Vicuna-7B reranker. For every variant the second line (prefixed by ->) reports the dataset-specific average number of passes. Lower call counts some datasets (NFCorpus, DBPedia, SciFact) reflect queries retrieving fewer than 100 documents with BM25.
TREC-DL DL19 DL20 DL21 DL22 DL23 DL-H COVID NFC Signal News R04 Touche DBP
BEIR
Method
Seif Avg. # Calls
First-stage retrieval: BM25
top-100
Reranker:
RankVicuna-88
BM25
50.6
48.0
44.6
26.9
26.2
30.4
59.5
32.2
33.0
39.5
40.7
44.2
31.8
67.9
41.1
0.0
avg. calls
0
0
0
0
0
0.0
0.0
SW-1
66.4
62.5
60.4
40.9
38.2
35.1
77.4
33.0
33.7
45.2
46.9
33.7
43.6
69.5
49.0
8.8
avg calls
9.0
9.0
9.0
9.0
9.0
9.0
9.0
6.2
9.0
9.0
9.0
9.0
9.0
9.0
8.8
8.8
SW-2
67.4
63.2
60.5
40.8
38.1
36.2
78.6
33.3
33.5
45.4
47.1
33.7
43.5
70.6
49.4
17.6
avg aalls calls
18.0
18.0
18.0
18.0
18.0
18.0
18.0
12.4
18.0
18.0
18.0
18.0
18.0
18.0
17.6
17.6
SW-3
67.5
63.2
60.6
41.0
38.2
35.9
78.7
33.5
33,9
45.6
47.2
34.8
43.9
69.9
49.6
26.4
avg_ calls
27.0 27.0
27.0
27.0
27.0
27.0
27.0
18.6
27.0
27.0
27.0
27.0
27.0
26.4
SW-4
67.5 63.2
60.6
41.0
37.3
36.2
78.7
33.4
33.8
45.9
47.4
34.4
43.8
70.3
49.5
35.2
calls
36.0 36.0
36.0
36.0
36.0
36.0
36.0
24.9
36.0
36.0
36.0
36.0
35.9
36.0
35.2
35.2
TourRank-1
65.7
63.4
61.2
42.5
35.4
35.5
76.7
31.6
31.6
43.9
46.7
29.2
39.8
62.2
47.5
12.7
9 avg calls
13.0
13.0
13.0
13.0
13.0
13.0
13.0
9.3
13.0
13.0
13.0
13.0
13.0
13.0
12.7
12.7
TourRank-2
67.1
64.5
61.1
40.8
36.8
34.7
78.4
31.2
34.3
47.6
48.5
33.5
44.0
67.4
49.3
25.5
avg calls
26.0
26.0
26.0
26.0
26.0
26.0
26.0
18.7
26.0
26.0
26.0
26.0
25.94
25.01
25.5
TourRank-5
67.1
64.5
62.2
42.7
38.1
35.1
78.5
32.5
32.8
46.3
48.9
28.3
42.8
66.5
49.0
63.7
avg calls
65.0
65.0
65.0
65.0
65.0
65.0
65.0
46.7
65.0
65.0
65.0
65.0
64.9
65.0
63.7
63.7
AcuRank-9 9
66.4
63.4
60,9
41.1
37.7
35.8
77.9
34.4
33.1
49.2
47.5
35,2
42.6
70.8
49.7
8.8
+ avg avl_calls calls
9.0
9.0
9.0
8.9
8.9
9.0
8.9
6.7
9.0
9.0
8.9
8.9
8.9
8.9
8.8
8.8
AcuRank
66.4
65.5
61.4
43.0
38.5
36.9
80.7
35.3
33.7
49.7
49.6
35.4
44.4
71.3
50.8
19.5
avg calls
18.2
16.4
15.7
18.3
17.7
17.5
22.4
25.1
18.5
18.1
18.7
23.3
20.1
22.8
19.5
AcuRank-H
67.4
65.8
61.7
43.3
39.0
36.5
81.1
35.1
33.5
34.2
71.8
51.0
25.1
avg calls
23.7
21.7
21.8
23.9
23.6
23.4
28.7
31.0
23.4
22.8
23.5
30.2
25.0
28.7
25.1
25.1
Table 12: Results in NDCG@ 10 for AcuRank with the zero-shot Llama-3.3-70B-Instte model. Averages are computed across the three datasets shown. Without any task-specific fine-tuning, AcuRank improves quality while keeping the number of reranker calls within reasonable range.
Method
DL23
TREC-COVID
News
Avg.
# Calls
BM25 (no rerank)
26.2
59.5
39.5
41.7
0
SW-1
47.0
84.6
50.1
60.6
9.0
AcuRank
47.7
86.1
53.0
62.2
19.4
model with Llama-3.3 70B Instruct [46 and reran the pipeline. Resource constraints limited us to three representative benchmarks: DL23, TREC-COVID, and TREC-NEWS, Results are reported in Table 12 Even for this stronger backbone AcuRank extracts additional +1.6 average NDCG @ 10 over the single-pass baseline, while keeping the number of calls bounded. This confirms that our framework continues provide a favorable accracc--efficiee trade-off as model capacity scales.
D.3 Extended analysis on sensitivity to uncertainty thresholds
For AcuRank, the uncertainty thresholds e and a are adjustable parameters that control the trade- off' between efficiency and accuracy. A relaxed setting (i.c., smaller or σ)) generally improves accuracy at the cost of increased computation, while stricter values reduce LLM usage with some performance degradation. This flexibility allows users to adapt the method to their specific resource and performance requirements. Our configurations were chosen reflect different trade-off points depending on user preference: AcuRank-H H and AcuRank-Hii favor accuracy, AcuRank-9 prioritizes efficiency, and the standard AcuRank strikes a practical balance. We report additional comprehensive ablation results at 13 illustrate how performance (in terms of NDCG@ 10) and computation vary with these thresholds. The results show that the trade-off curve is smooth and monotonic, suggesting that AcuRank is robust across wide range of hyperparameter choices.
24

---

Following Section 5.3 of the main paper ("Adaptive allocation behavior") and Figure we provide a Table 13: Analysis on sensitivity to uncertainty thresholds (BM25 100-100, RankZephyr) for AcuRank. (0.01, 10)*, (0.0001, 10)**, (0.0001, 5)*** is the configuration for AcuRank, AcuRank- AcuRank- HH, respectively.
(c,T)
DL19
DL20 DL21
DL22
DL23 DL-H COV.
NFC
Sig.
News
R04
Tou.
DBP
Scif
Avg.
# Calls
(0.01. 20)
74.6
70.5
70.1
51.8
46.0
39.7
84.8
36.9
32.3
54.2
56.6
37.7
45.5
75.2
55.4
16.0
(0.01, 10)*
74.2
71.8
70.3
52.0
47.0
39.4
85.3
37.2
31.8
53.9
56.6
36.5
46.0
75.3
55.5
19.2
(0.01, 5)
73.8
71.8
71.0
51.8
47.3
39.8
85.1
37.3
32.2
54.0
57.3
35.3
45.8
75.1
55.5
28.2
(0.0001, 10)**
74.6
70.8
70.5
52.2
47.3
40.4
85.8
37.4
32
53.7
56.8
37.5
46.0
75.4
55.7
41.7
(0.0001, 5y
74.7
71.8
70.6
51.9
47.0
40.0
86.1
37.5
31.3
54.4
57.8
36.1
46.0
75.4
55.8
57.2
Table 14: Corpus-wide query-level correlations (n= 612). Negative p for "# Calls" indicates that AcuRank issues more reranker calls on queries predicted as harder (lower WIG) or where its own NDCG is lower.
Variable pair
Spearman
p-value
# Calls vs. WIG
00.24
9.3 x 10
# Calls vs. NDCG (Ours)
-033
2.7 X 10-20
E Extended analysis on adaptive computation allocation
more fine-grained query-level analysis.
E.1 Correlations with WIG
This is an extended analysis of Figure in the main paper. On designing the experiment, we pool all datasets containing fewer than 100 queries to obtain reliable correlations. This includes every benchmark except DBPedia-Entiyy Entity, SciFact, NFCorpus, and Robust04. The resulting subset contains 612 queries drawn from 14 datasets. For each query, we compute the Weighted Information Gain (WIG) 455 over the BM2 top- 100 retrieval scores. We then measure two Spearman correlations: (i) between WIG and the number calls made by AcuRank to satisfy its stopping criterion, and (ii) between WIG and the final NDCG achieved by AcuRank. As shown in Table 14 both correlations are negative.
Calls versus WIG. Lower WIG, which reflects more ambiguous top-100 lists, leads to more reranker calls. This confirms that AcuRank allocates additional computation when the candidate set is uncertain.
Calls versus NDCG. Queries that result in lower final NDCG tend to receive more reranker calls. This indicates that AcuRank naturally focuses effort on harder queries.
E.2 Comparison with fixed sliding windows
We further compare AcuRank (with an average of 19.7 calls across 18 datasets) with a Sliding Windows baseline using similar compute budget (SW-2, 18 calls). For three challenging datasets (Touche, TREC-COVID, and DL-Hard), we split the queries into Easy (NDCG 2 μ)) and Hard (NDCG < μt,, where p is the dataset-level mean NDCG produced by SW-2. Table 15 shows consistent pattern:
Avg. # Reranker Calls: Hard > Easy. AcuRank spends more calls the Hard bucket (e.g. +6.2 on TREC-COVID) and sometimes even saves calls on the Easy bucket (c.g. DL-HARD).
NDCG Gains: Hard > Easy. The additional computation translates into larger NDCG improve- ments Hard queries (e.g. +7.0 TOUCHE, +1.7 TREC-COVIDE while improvements Easy queries are smaller than those for the Hard bucket queries.
These observations corroborate the claim that AcuRank adaptively directs compute the most uncertain and therefore most difficult queries, yielding a superior accuracy and efficiency trade-off compared with
baselines.
16 "meta- tenet-llaaman 1ww-m1ammaLLaa Laamaa/Laaaa..... 3-708-Instruce
25

---

Table 15: Per-query analysis comparing the Sliding-Window Window baseline (SW-2) with AcuRank. Queries are split into Easy and Hard halves using the baseline's own mean NDCG. AcuRank allocates more computation hard queries, which often results in larger NDCG gains, while occasionally reducing the number of calls for easy queries.
NDCG@N 10
# Calls
Dataset
Subset
Q
SW-2
AcuRank
A
SW-2
AcuRank
Easy (2 ())
23
50.5
52.7
+2.2
18.0
18.1
+0.1
Touche
Hard (< p0)
15.2
22.2
+7.0
18.0
20.5
+2.5
All (1x 31.8)
49
31.8
36.5
+4.7
18.0
19.4
+1.4
Easy (2 (M)
96.7
+0.6
18.0
20.2
+2.2
TREC-COVID
Hard (< (4)
20
66.7
68.4
+1.7
18.0
24.2
+6.2
All (1x = 84.4)
50
84.4
85.4
+1.0
18.0
21.8
+3.8
Easy (2 (t)
25
65.7
64.6
-1.1
18.0
15.8
-2.2
DL-Hard
Hard (< 14)
25
11.2
14.3
+3.1
18.0
16.8
-1.2
All (14 = 38.4)
38.4
39.4
+1.0
18.0
16.3
-1.7
Table 16: Example Per-iteration traces Bayesian update for contrasting passages. Net movement: Gold passage climbs 11 ranks out of 50 candidates (20 9), and Non-gold passage drops 14 ranks out of candidates (19 - 33).
Gold-relevant pid 4647186
Non-relevant pid 6337909
Pass
μ
Rank
Pass
0
Rank
13.44
2.96
20
13.77
3.14
19
15.48
2.46
14
2
9.50
2.66
33
17.06
2.15
10
3
9.50
2.66
33
18.27
1.94
10
9.50
2.66
33
19.02
1.78
9 (final)
9.50
2.66
33 (final)
E.3
Qualitative Example of the Bayesian Update process of AcuRank
Setup. Table 16) shows the trace for the first query of TREC-DL19 as AcuRank iterates five times over 50 candidate passages (n=50). We highlight two contrasting passages to make the dynamics clear.
Over-estimated early leader (pid 6337909). On the first iteration, this non-relevant passage holds a slightly higher mean score than the gold passage (μ = 13.77 13.44). After one unfavourable comparison, its mean collapses, confidence tightens, and because subsequent comparisons are unnecessary, the passage frozen rank 33.
Initially uncertain passage that surges (pid 4647186, gold). Starting lower than 6337909, this passage wins multiple pairwise contests. Each victory pushes its mean up and its o down until confidently enters the top- (rank 9).
The key takeaway is that uncertain winners surge, overestimated items pruned, and comparisons halt once confidence is high, saving compute.
This exemplifies how AcuRank's 's Bayesian evidence accumulation boosts performance while saving LLM calls by halting once posterior uncertainty is low.
F Extended robustness: scalability and ranking stability
This section extends our analysis of AcuRank's robustness along two axes that are important in practice. First, we study how the amount of computation evolves as the size of the candidate set n changes. Second, we assess the stability of rankings when the candidate pool is enlarged by adding new documents. Unless specified otherwise, we use the same default setup as in the main text (BM25 first-stage, RankZephyr listwise reranker, group size m=20, ==10, uncertainty tolerance c=0.01,
26

---

Table 17: Extended analysis of scalability and stability. Left: average number reranker calls
until convergence as candidate set size n varies (SW-1 for reference). Right: average TrueSkill mean I among the final top- (top-50 for n=50).
Average number of reranker calls
Average TrueSkill mean (n) AcuRank
Avg.
Avg.
DL19
DL20
COVID News
DL19
DL20
COVID
News
Avg.
(Ours)
(SW-1)
50
12.6
13.2
14.3
12.0
13.0
4.0
50
10.8
11.6
10.0
12.5
11.2
100
18.3
16.3
21.8
18.5
18.7
9.0
100
9.9
10.5
9.4
11.5
10.3
200
26.3
23.6
30.6
25.5
26.5
19.0
200
11.5
12.2
11.0
13.4
12.0
1000
67.8
65.6
72.8
68.0
68.6
99.0
1000
12.0
12.8
11.6
14.1
12.6
Table 18: Preserved ratio of pairwise relative rankings (in %) between reranking D (top-50) and
on D (top-100). AcuRank achieves better stability than the baseline sliding windows approach.
Method
DL19
DL20
COVID
News
D
AcuRank
86.6
88.7
85.6
86.8
D
SW-1
85.8
84.8
83.7
83.6
Gold
AcuRank
87.7
88.2
85.3
87.9
Gold
SW-1
88.7
86.2
81.9
86.0
stopping threshold 7=10), on the selected subset (DL19, DL200, TREC-COVID, TREC-News) of BEIR.
F1 Scalability with candidate-set size
We vary (50, 100, 200, 1000} and report the average number of reranker calls until convergence and the average posterior mean computed over the final top-100 (top-50 when n=50). Sliding Windows with single pass (SW-1) is included for reference. Table 17 (left) shows that the number of AcuRank calls grows sublinearly in n. For example, increasing from 100 to 1000 (10x) raises the average calls from 18.7 68.6 (==3.7x), while SW-1 scales almost linearly
99, ~ 11 x). Table 17 on the right shows mild increase in the average among the top set as grows, which is expected when a larger pool provides stronger candidates.
Overall, AcuRank focuses computation on the subset uncertain candidates near the top-k boundary and avoids redundant updates to confident items, which explains the sublinear growth in calls with larger n and indicates better scalability as n increases.
F.2 Ranking stability under document addition
We examine whether the relative order over an original set D= (D,, D.....Dr) is preserved after reranking extended set D+ 2 D. Concretely, take BM25 top-50 D and top-100 as D for each query, and independently run AcuRank and SW-1 on both sets. For a subset S S,D, we compute the ratio of preserved pairwise relations between the rankings. We report two choices of S: all items in DD and only the gold-relevant items in D. Results in Table 18 show that AcuRank preserves relative orderings more robustly over the full D, and is comparable better on the gold-only subset across three of four datasets, reflecting the algorithm's 's focus on accurately resolving the most relevant candidates.
In summary, compared with the sliding window baseline, AcuRank scales favorably with larger candidate pools and maintains stable ordering, particularly among truly relevant items, when additional documents are introduced.
G Limitations and Future Work
Latency optimization. Although AcuRank reduces the total number of reranker calls, further latency improvements may achieved through parallelization. Unlike sequential sliding windows, our use of disjoint candidate groups enables batched inference across groups within the same iteration.
27

---

In addition, cross query computation sharing could significantly reduce latency when processing multiple queries concurrently.
Hyperparameter adaptation. Our fixed global hyperparameters (j,, c, and stopping criteria) perform well overall, but may be suboptimal for certain domains. Query-aware domain-specific tuning could improve effectiveness. Automatic adaptation methods represent promising direction for future work.
Potential method enhancements. While AcuRank demonstrates strong performance, several promising directions remain for future research. Our current approach uses thresholded cumu- lative rank probabilities to guide reranking decisions. However, the full rank probability distri- bution offers richer source of uncertainty information. For example, rank entropy, defined as Hl(ri) = - Pr(r: r) log P(r; = r), quantifies the dispersion in a document's predicted rank and could support more expressive uncertainty-based filtering strategies [77 In addition, our current grouping strategy for uncertain documents is based simple heuristics. Clustering sestering-based or similarity-awe aware grouping methods may improve reranking efficiency by better capturing inter- document structure. Finally, modern LLMs may expose token-level generation-level confidence scores. These signals could be integrated to refine document-level uncertainty estimates or modulate the strength of score updates during reranking.
maasoning-wwars retrieval. A promising future direction is to extend the proposed uncertainty-awan adaptive reranking to reasoning aware retrieval [4] where the objective is not only to identify topically relevant documents but also to select those that meaningfully contribute to multi-step reasoning evidence aggregation. In such scenarios, reranking plays critical role 50)5,4,, the quality of reasoning often depends on the interaction and organization of supporting information rather than individual relevance scores. Modeling uncertainty over document's contribution to reasoning could enable adaptive allocation of computation to the most influential candidates, potentially improving both reasoning accuracy and overall retrieval efficiency across diverse tasks.
H Example input/output prompt format for listwise reranking
We provide concrete prompt examples for RankZephyr 12), Rank E4-70BIInntrue reranking models [46).
RankVicuna Vicuna
8 and zero-shot Llama-
H.1
RankZephyr
12 prompt example


You are RankLLM, intelligent assistant that can rank passages based on their relevancy to the query.


<|user||>
will provide you with 20 passages, each indicated by numerical identifier []. Rank
the passages based on their relevance search query: 2 promotes intestinal tumor growth by altering the expression of tumor suppressing and DNA repair genes..
[1] Title: Prostaglandin E2 promotes intestinal Content:
growth via DNA methylation Although aberrant DNA methylation is considered be one of the key ways by which Lumor-suppressor and DNA-repair genes are silenced during tumor initiation and progression, the mechanisms underlying DNA methylation alterations in cancer remain unclear. Here show that prostaglandin E2 (PGE2) silences certain tumor- suppressor and DNA-repair genes through DNA methylation promote tumor growth. These findings uncover a previously unrecognized role for PGE2 in the promotion of tumor progression.
[2] Title: Mole Patients were treated within clinical trials testing
[20] Title: DNA Damage and Repair Modify DNA Methylation and Chromatin Domain of the Targeted Locus
17The pointwise and cumulative rank probabilities mutually derivable. The cumulative probability is the sum of pointwise probabilities, Pr(r: r) E P(r: j), while the pointwise probability given by the P(r: 1).
difference between adjacent cumulative terms. P(r: P(r: r)
28

---

Content:
We characterize the changes in chromatin structure, DNA methylation and transcription during and after homologous DNA repair (HR). We find that HR modifies DNA methylation pattern H3 methylation as well as chromatin structure by inducing DNA-chromatin loops connecting the 5' and 3' ends of the repaired gene.
repaired segment. also alters local histone
Search Query: PGE promotes intestinal tumor growth by altering the expression of tumor suppressing and DNA repair genes...
Rank the 20 passages above based on their relevance to the search query. All the passages should be included and listed using identifiers, in descending order of relevance. The output format should be [] []. e.g., [2] [1]. Only respond wi th the ranking results; do not say any word or explain.

 <lassistant|>
Example Output:
[1] [3] [6] [11] [5] [8]
[20] >
[2]
[18] [15] [16] [19] [10]
[12] [13] > [4] [17] [7] [9] [14]
H.2 Rinkni prompt example
<>>
 <<SY>>>
You are RankLLM, an intelligent assistant that can rank passages based on their relevancy to the query.
<</SY5>>
will provide you with 20 passages, each indicated by a numerical identifier []. Rank the passages based on their relevance to the search query: what does prenatal care include.
[1] Pregnancy and prenatal care go hand in hand. During the first trimester, prenatal care includes blood tests, a physical exam, conversations about lifestyle and more. Prenatal care is an important part of a healthy pregnancy. Whether you choose a family physician, obstetrician, midwife or group prenatal care, here's 's what to expect during the first few prenatal appointments.
[2] Pregnancy and prenatal care go hand in hand. During the first trimester, prenatal care includes blood tests, a physical exam, conversations about lifestyle and more. Prenatal care is an important part of a healthy pregnancy. Whether you choose a family physician, obstetrician, midwife group prenatal
[3] Prenatal appointments typically
[4] Routine prenatal screening
[5] Standard tests include
[19] What is Prenatal Care: Prenatal care is the health that both the and the baby receive before giving birth. This more than just few doctor's visits and an ultrasound or two.
[20] Medicaid coverage for prenatal care provides another opportunity to illustrate the four pathways' differences and how each state determines what services to include. (1) Right away, know that the emergency pathway will not pay for prenatal care because preventive services are non-urgent by definition.
Search Query: what does prenatal care include. Rank the 20 passages above based their relevance the search query. All the listed using identifiers, descending order
passages should included relevance. The output format should be [] [], e.g., [2] [1]. Only respond with the ranking results, do not say any word or explain. 

Example Output:
[1] [2] [3] [5] > [6] [19] [8]
[15] [16] [14] [17] [4] [12] [13]
> [9] [10] > [18] [7] [11]
[20]
29

---

H.3 Llama-333-70B-IIstruue 46 (zero-shot) prompt example
</begin http:oo_.eeeetttssssaaaeeeeeedle s leweenddeee__id__eeeeeeee
Cutting Knowledge Date: December 2623
Today Date: 26 Jul 2024
are RankLLM, an intelligent assistant that can rank passages based on their relevancy to the
will provide you with 20 passages, each indicated by numerical identifier []. Rank the passages based their relevance the search query: much impact do masks have on preventing spread the COVID-19?.
[1] Title: Preparedness and response to COVID-19 in Saudi Arabia: Building MERS
experience
Content: Nearly four months have passed since the emergence SARS-CoV-2,
[2] Title: The effect of community masking on transmission rates
[3]
[19] Title: Comparative hydraphobicity of fabrics used for improvised masks
[20] Title: An exploration of how fake news taking over social media and putting
public health at risk. Recent statistics show that almost 1/4 million people have died
Content:
Search Query: How much impact masks have on preventing the spread of the COVID-19?.
Rank the 20 passages above based on their relevance to the search query.
All the passages should be included and listed using identifiers, in descending order of relevance.
The output format should be [], e.g., [2] [1].
Only respond with the ranking results; do not say any word or


Example Output:
[5] > [12] > [7] > [16] > [19] > [15] > [10] > [6] [9] [8]
[14] [4] [3] [2] [1] [18] [17] [13] [11] [20]
30


Reviews:
[{"review_id": "LjzLAK1rxd", "reviewer": "Reviewer_KzUm", "summary": "This paper proposes AcuRank, an uncertainty-based adaptive computation framework for listwise re-ranking. The main contributions are as follows:\n\n1. Introduction of a TrueSkill-based probabilistic relevance modeling approach, which enables the estimation of uncertainty in document ranking.\n2. Development of a novel listwise re-ranking framework that supports adaptive computation by iteratively refining and selectively re-ranking uncertain candidate documents.\n3. Extensive experimental validation across various benchmarks and datasets, demonstrating AcuRank’s superior trade-off between accuracy and efficiency, as well as its generalization capability in different retrieval tasks and LLM-based re-ranking models.\n\n\nAcuRank employs a Bayesian TrueSkill model to maintain probabilistic estimates of document relevance, iteratively refining these estimates until a sufficient confidence level is reached. By explicitly modeling ranking uncertainty, this approach allows for rational control of re-ranking actions and avoids unnecessary updates for predictions that are already highly certain. On the TREC-DL and BEIR benchmarks, AcuRank consistently achieves a better balance between accuracy and efficiency compared to fixed-computation baselines.", "questions": "Q1: AcuRank dynamically allocates computational resources to handle uncertain documents. However, in certain scenarios, could this dynamic adjustment lead to either over-allocation or under-allocation of resources? For example, when processing highly complex queries, is there a risk that the model may terminate computation prematurely and consequently overlook some important documents?\n\nQ2: AcuRank employs the TrueSkill model to estimate the uncertainty of document relevance. However, is this uncertainty estimation method sufficiently accurate?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. AcuRank is the first to introduce uncertainty modeling into listwise re-ranking tasks, enabling fine-grained control over uncertainty through dynamic allocation of computational resources, which demonstrates high originality.\n2. Across multiple benchmarks, AcuRank achieves a better trade-off between accuracy and efficiency. For example, on the TREC-DL and BEIR datasets, AcuRank consistently improves ranking quality under various re-ranking models while requiring fewer re-ranker invocations.\n3. The paper is well-written and easy to understand.\n\nWeaknesses:\n\nThe main limitation lies in insufficient experimental evaluation. The authors mention using TourRank and TrueSkill-Static as baselines; however, Table 1 does not report results for TrueSkill-Static, and the lower part of Table 1 lacks results for TourRank. Table 2 exhibits similar issues. To robustly assess AcuRank’s performance across retrieval scenarios, comprehensive comparisons with these baseline models are necessary. Additionally, a comparison with setwise methods is also needed.", "was_revised": true, "final_justification": "All my concerns have been addressed. I recommend acceptance.", "rebuttal": "We thank the reviewer for the encouraging and constructive feedback. We appreciate the recognition of the clarity and practicality of our framework. We would greatly appreciate it if you could review our comments and inform us if any further discussion or clarification is required.\n\n\n### 1. Missing Baseline Results\n- While it would be ideal to include all baseline results in every table, space limitations and computational costs led us to prioritize the most competitive and relevant baselines. Less impactful or redundant baselines were omitted to maintain clarity and focus. We include additional results below and are open to reporting others during the rebuttal period if time and resources allow.\n- **TrueSkill-Static** results on all datasets are already available in Supplementary Table 3. These were excluded from the main table due to space constraints and consistently underperform compared to AcuRank.\n- We additionally report **TourRank** baseline results missing from Table 1 and 2. We stopped at the point where TourRank-$x$ became significantly worse than AcuRank in terms of both the number of reranker calls and NDCG@10. Specifically, we include TourRank-1 in the lower part of Table 1 (BM25 top-1000), and both TourRank-1 and TourRank-2 in Table 2 (SPLADE++ED top-100). Thank you for pointing this out. We will incorporate these results in the final version.\n\n> Table 1: Additional baselines (TourRank-1) on the lower part of main paper Table 1 (BM25 top-1000, RankZephyr)\n\n| Method  | DL19 | DL20 | DL21 | DL22 | DL23 | DL-H | COVID | NFC | Signal | News | R04 | Touche | DBP | Scif |  Avg   |  #pass   |\n| ---------- | ---- | ---- | ---- | ---- | ---- | ------- | ----- | -------- | ------ | ---- | -------- | ------ | ------- | ------- | --- | --- |\n| SW-1 | 75.1 | 78.8 | 71.5 | 57.5 | 49.5 | 40.9 | 80.7  | 38.0  | 28.9   | 51.0 | 48.0  | 30.9   | 48.0 | 76.4 |  56.2   |  94.6   |\n| **TourRank-1** | 75.4 | 76.6 | 71.7 | 56.6 | 49.8 | 42.1 | 82.7  | 36.6  | 29.9   | 50.9 | 59.9  | 33.0   | 45.5 | 72.8   |  56.0 |   117.1  |\n| AcuRank | 76.7 | 75.3 | 73.1 | 59.3 | 53.5 | 41.0 | 85.0  | 37.0  | 30.7   | 56.5 | 63.2  | 36.2   | 48.8 | 76.0 |  **58.0**   |  **68.4**   |\n\n> Table 2: Additional baselines (TourRank-1,2) on the upper part of main paper Table 2 (SPLADE top-100, RankZephyr)\n\n| Method | COVID | NFC  | Signal | News | R04  | Touche | DBP  | Scif | Avg. | # Calls |\n|--------------|-------|------|--------|------|------|--------|------|------|------|---------|\n| SW-1   | 85.2  | 37.5 | 29.7   | 50.1 | 62.0 | 28.9   | 49.3 | 75.7 | 52.3 | 9.0  |\n| **TourRank-1**   | 82.5  | 37.4 | 28.5   | 51.5 | 60.7 | 29.7   | 48.9 | 73.7 | 51.6 | 13 |\n| **TourRank-2**   | 84.6  | 37.6 | 29.5   | 52.5 | 61.7 | 28.4   | 50.0 | 74.0 | 52.3 | 26 |\n| AcuRank   | 85.5  | 37.7 | 27.2   | 51.9 | 63.1 | 30.2   | 50.0 | 75.6 | **52.7** | **8.9**  |\n\n- We additionally report results on another different first-stage retriever (contriever) which also confirms that AcuRank's superior accuracy-efficiency trade-off with varying first-stage retrievals. Please refer to our response to Reviewer SkZp for details on these results (Table 3).\n- In the related work section, we categorize reranking approaches into pointwise, pairwise, setwise, and listwise paradigms, and our focus in this paper is specifically on listwise reranking. **Setwise methods** are typically compared against pairwise methods and not compared with listwise methods, so we considered them less relevant to our approach. Nonetheless, we appreciate the suggestion and acknowledge their potential interest to some readers. We will include a discussion and comparison in the camera-ready version.\n\n\n### 2. Possibility of Over- or Under-allocation of Computation\n- Since the ideal amount of computation for each case cannot be known in advance, adaptive computation may not guarantee optimal allocation of resources. However, AcuRank includes safeguards to reduce the risk of both over- or under-allocation. It adaptively allocates reranker calls based on estimated ranking uncertainty, focusing on documents whose inclusion in the top ranks remains uncertain, and stops when the system becomes sufficiently confident or reaches a predefined maximum number of iterations. \n- We also support our claim with two empirical analyses:\n  - In Section 5.3 (Figure 3) and Supplementary Section 5.1, we show there is a positive correlation between weighted information gain (WIG, accounting for complex, confusing candidate document scenarios) and the number of reranker calls (Lines 306-315). \n  - In Supplementary Section 5.2 (Table 8), we show that AcuRank tends to allocate more computation to harder queries (lower NDCG than the average) and less computation to easier ones, further validating the effectiveness of our strategy.\n- We also provide a **qualitative example of the bayesian update** at the response for reviewer nvvL (Number 2, Table 9,10).\n\n\n### 3. Justification for TrueSkill-based Uncertainty Estimation\n- TrueSkill is a principled Bayesian rating system originally developed for competitive games, where each player's skill is modeled as a Gaussian distribution that is updated through observed match outcomes. It is known to produce well-calibrated estimates of of both scores and uncertainty, and has been widely adopted in various applications where reliable uncertainty quantification is crucial [1,2,3]. \n- Similar to prior works, we recast documents as players and interpret the LLM reranker’s output rankings as pairwise comparisons. When one document is ranked above another within a batch, it is treated as having won that match. TrueSkill uses these outcomes to iteratively update each document’s relevance score (mean) and uncertainty (variance), enabling it to estimate both how relevant each document is and how confident it is in those estimates.\n- Although the accuracy of uncertainty estimates cannot be directly evaluated without ground-truths, the strong accuracy-efficiency trade-offs achieved by AcuRank demonstrate that the uncertainty signals derived from TrueSkill effectively guide adaptive computation.\n\n[1] Chung et al., CHI 2022, TaleBrush: Sketching Stories with Generative Pretrained Language Models\n\n[2] Park et al., UIST 2023, Generative Agents: Interactive Simulacra of Human Behavior\n\n[3] Shaikh et al., CHI 2024, Rehearsal: Simulating Conflict to Teach Conflict Resolution"}, {"review_id": "EMvwIYGrSb", "reviewer": "Reviewer_SkZp", "summary": "This paper proposes a novel adaptive reranking framework called AcuRank, aiming to improve the efficiency and accuracy of listwise reranking with large language models (LLMs). The core idea is to dynamically adjust computational resources (including computational effort and objectives) based on uncertainty estimates of document relevance. AcuRank employs a Bayesian TrueSkill model to iteratively refine relevance estimates until a sufficient confidence level is reached. This explicit modeling of ranking uncertainty enables principled control over the reranking behavior, avoiding unnecessary computations on already confident predictions. The authors conducted experiments on TREC-DL and BEIR benchmarks, across different retrieval tasks and LLM-based reranking models. The results demonstrate that AcuRank consistently outperforms fixed-computation baselines, exhibiting excellent accuracy-efficiency trade-offs and better scalability with computational resources.", "questions": "Basis for ϵ stop and σ target Selection and Sensitivity Analysis: I noticed that AcuRank's performance heavily depends on the setting of uncertainty thresholds. Could the authors provide the rationale for choosing these hyperparameters and a more detailed sensitivity analysis?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\n1.\tClear Motivation Statement: The introduction clearly articulates the limitations of existing fixed-computation reranking methods and the motivation behind adopting an adaptive approach, presenting a very logical flow. \n\n2.\tNovelty and Significance: The concept of uncertainty-aware adaptive computation for LLM reranking is highly novel, directly addressing critical practical challenges such as the high inference cost and fixed context lengths of current LLM rerankers. Specifically, the use of the Bayesian TrueSkill model for explicitly modeling uncertainty offers a theoretically rigorous approach. \n\n3.\tStrong Experimental Results: The consistent improvements in accuracy-efficiency trade-off and better computational scalability demonstrated on established benchmarks (TREC-DL and BEIR), and with different LLM rerankers (RankZephyr, RankGPT), provide strong empirical support for AcuRank's effectiveness and generality.\n\nWeaknesses: \n\n1.\tInsufficient Theoretical Depth: Complexity of Bayesian TrueSkill Model Integration: While the Bayesian TrueSkill model excels in game and competitive rankings, its application to the iterative process of document reranking, particularly the mapping of its inherent mechanisms and parameters (e.g., skill values, uncertainty, definition of \"match outcomes\"), is not immediately obvious. The paper could provide a deeper explanation of this part, for instance, how to precisely define the \"match\" results of documents during each reranking iteration, and how these results update the skill (relevance scores) and uncertainty in the TrueSkill model. \n\n2.\tInsufficient Theoretical/Empirical Basis for Uncertainty Thresholds: A core aspect of AcuRank lies in deciding when to stop based on uncertainty thresholds. However, the paper lacks sufficient theoretical guidance or sensitivity analysis regarding the selection of these thresholds (e.g., ϵstop and σtarget). \n\n3.\tLack of Generalization Analysis across Different LLM Behaviors: The paper uses RankZephyr and RankGPT as LLM rerankers and shows AcuRank's effectiveness for both. However, there is a lack of additional baselines; for example, considering the impact of first-stage retrieval models like monoBERT, or comparisons with models like GPT-4/GPT-3.5. \n\n4.\tUnreasonable Evaluation of Efficiency. This paper uses the “number of reranker calls” to evaluate model efficiency. However, this is not an appropriate metric, as the time cost depends not only on the number of reranker calls but also on the context length of each call.", "was_revised": true, "final_justification": "The new explanations and supplementary experiments have successfully resolved the key questions we raised. We now have a much better understanding of the work and are satisfied with the improvements. Based on these changes, we have updated our score for this paper from 2 to 4.", "rebuttal": "Thank you for providing valuable comments to improve our paper! We are especially encouraged by the recognition of AcuRank’s originality and its excellent trade-off between accuracy and efficiency. We hope our comments are sufficient enough to answer the questions raised and that you consider raising the overall rating of our work. We would greatly appreciate it if you could review our comments and inform us if any further discussions or clarification is required:\n\n\n### 1. Justification for TrueSkill-based Uncertainty Estimation\n- We appreciate the reviewer’s request for a deeper explanation of how the TrueSkill model is applied in our setting and why it is suitable for estimating uncertainty in document relevance. As we provide a detailed justification in our response to Reviewer KzUm #3, we kindly refer the reviewer to that section for further discussion.\n\n\n### 2. Choice of Uncertainty Thresholds\n- We thank the reviewer for raising this important point. In AcuRank, the uncertainty thresholds $\\epsilon$ and $\\sigma$ are **adjustable parameters** that control the trade-off between efficiency and accuracy. A relaxed setting (i.e., smaller $\\epsilon$ or $\\sigma$) generally improves accuracy at the cost of increased computation, while stricter values reduce LLM usage with some performance degradation. This flexibility allows users to adapt the method to their specific resource and performance requirements.\n- Our configurations were chosen to reflect different trade-off points depending on user preference: AcuRank-H and AcuRank-HH favor accuracy, AcuRank-9 prioritizes efficiency, and the standard AcuRank strikes a practical balance.\n- In response to the reviewer’s suggestion, we report additional ablation results to illustrate how performance (in terms of NDCG@10) and computation vary with these thresholds. These results show that the trade-off curve is smooth and monotonic, suggesting that AcuRank is robust across a wide range of hyperparameter choices.\n\n> Table 3. Analysis on sensitivity to uncertainty thresholds (BM25 top-100, RankZephyr).\n\n| $(\\epsilon, \\tau)$ | DL19 | DL20 | DL21 | DL22 | DL23 | DL-H | COVID | NFC | Signal | News | R04 | Touche | DBP | Scif | Avg. | # Calls |\n|---------------|------|------|------|------|------|---------|-------|----------|--------|------|----------|--------|---------|---------|------|---------|\n| $(0.01, 20)$  | 74.6 | 70.5 | 70.1 | 51.8 | 46.0 | 39.7 | 84.8 | 36.9  | 32.3   | 54.2 | 56.6  | 37.7   | 45.5 | 75.2 | 55.4 | 16.0 |\n| $(0.01, 10)$: **AcuRank** | 74.2 | 71.8 | 70.3 | 52.0 | 47.0 | 39.4 | 85.3 | 37.2  | 31.8   | 53.9 | 56.6  | 36.5   | 46.0 | 75.3 | **55.5** | **19.2** |\n| $(0.01, 5)$   | 73.8 | 71.8 | 71.0 | 51.8 | 47.3 | 39.8 | 85.1 | 37.3  | 32.2   | 54.0 | 57.3  | 35.3   | 45.8 | 75.1 | 55.5 | 28.2   |\n| $(0.0001, 10)$: AcuRank-H | 74.6 | 70.8 | 70.5 | 52.2 | 47.3 | 40.4 | 85.8 | 37.4  | 32.1   | 53.7 | 56.8  | 37.5   | 46.0 | 75.4 | 55.7 | 41.7 |\n| $(0.0001, 5)$: AcuRank-HH | 74.7 | 71.8 | 70.6 | 51.9 | 47.0 | 40.0 | 86.1 | 37.5  | 31.3   | 54.4 | 57.8  | 36.1   | 46.0 | 75.4 | 55.8 | 57.2 |\n\n\n### 3. Generalization across Different LLM Rerankers and Retrieval Setups\n- We thank the reviewer for raising this important point. One of the key advantages of AcuRank is its general applicability: it can be applied after any first-stage retriever and on any listwise reranker, regardless of the underlying architecture or scoring function.\n- In addition to **RankZephyr** (main Table 1 & 2) and **RankGPT** (main Table 2), we also evaluate AcuRank with a diverse set of listwise rerankers, including **RankVicuna** (Supple Table 5), and **Llama-3.3-70B-Instruct** (Supple Table 6) to demonstrate its generalization across different LLM backbones. Publicly available listwise reranking models are relatively scarce, and we believe these models span a sufficiently diverse range of model types and capabilities. While additional results with GPT-4/3.5 could offer further insight, their high API cost made them infeasible for inclusion in our experiments.\n- We also evaluate AcuRank under various first-stage retrieval settings: **BM25 top-100, BM25 top-1000**, and **SPLADE++ED top-100** (main Table 1 & 2). To consider the impact of first-stage retrieval models, as the reviewer requested, we **additionally** evaluate AcuRank on BEIR using **contriever** (`facebook/contriever-msmarco`, mean pooling and Pyserini indexing) as a first-stage retriever. As shown in **Table 4** below, AcuRank again achieves superior accuracy-efficiency trade-off over baselines.\n- We will include these results on the final revision, and will open-source all related code and configurations to support reproducibility.\n\n> Table 4: Results with first-stage retrieval using Contriever top-100\n\n| Method  | COVID | NFC  | Signal | News | R04 | Touche | DBP | Scif | Avg. | # Calls |\n|------------|-------|------|--------|------|----------|--------|---------|---------|------|--------|\n| Contriever | 48.0  | 32.0 | 23.8   | 35.3 | 37.7  | 21.7   | 33.0 | 65.1 | 33.1 | 0   |\n| SW‑1 | 70.8  | 38.3 | 26.5   | 49.9 | 54.9  | 30.4   | 46.1 | 75.4 | 45.3 | 9   |\n| SW‑2 | 72.3  | 38.7 | 26.8   | 50.4 | 55.0  | 31.0   | 46.8 | 75.3 | 45.8 | 18  |\n| SW‑3 | 72.6  | 38.6 | 26.6   | 50.5 | 55.0  | 31.3   | 46.9 | 75.4 | 45.9 | 27  |\n| TourRank‑1 | 67.5  | 36.8 | 25.8   | 49.3 | 54.6  | 28.2   | 45.5 | 72.2 | 44.0 | 13  |\n| TourRank‑5 | 70.9  | 38.1 | 26.4   | 52.2 | 57.6  | 30.1   | 47.0 | 74.4 | 46.0 | 65  |\n| AcuRank | 74.4  | 39.1 | 27.1   | 53.0 | 57.2  | 33.1   | 47.9 | 75.2 | **47.4** | **20.1** | \n| AcuRank‑H  | 74.3  | 39.2 | 27.6   | 52.4 | 58.0  | 32.1   | 48.0 | 76.4 | **47.4** | 43.4  |\n\n\n### 4. Using the Number of Reranker Calls as an Efficiency Metric\n- We thank the reviewer for raising this point. The number of reranker calls was originally chosen as the efficiency metric since it is a practical proxy for end-to-end latency in real-world deployments (L. 209-213).\n- In fact, the number of reranker calls disadvantages AcuRank over baselines. Since AcuRank partitions uncertain candidates with maximum size of $C(=20)$, this leads to shorter inputs with smaller context numbers in some stages (L. 174-179). Therefore, AcuRank tends to get shorter inputs and runs faster compared to the fxed-computation baselines with similar number of reranker calls. Despite this potential disadvantage, AcuRank consistently demonstrates better efficiency.\n- To further support this point, we compare AcuRank and sliding window baselines (SW-1 and SW-2) using sampled queries with a similar number of reranker calls, and report both query-wise **window size**, **input length**, **FLOPs**, and **end-to-end runtime latency** across four sampled datasets (DL19, DL20, TREC-COVID, and News) at Table 5 and 6. These results confirm that AcuRank achieves comparable or better efficiency given similar number of reranker calls. Thank you for your suggestion, and we will additionally include the evaluation on our next revision.\n- In addition, as discussed in Supplementary L. 205–209, AcuRank can support parallel processing across disjoint candidate groups. This enables further latency reductions in practice beyond what is captured by reranker call counts alone.\n\n> Table 5: Additional evaluation of average per‑query efficiency — SW-2 vs. AcuRank\n\n| Metric  | DL19 (SW‑2) | DL19 (AcuRank) | DL20 (SW‑2) | DL20 (AcuRank) | TREC‑COVID (SW‑3) | TREC‑COVID (AcuRank) | News (SW‑2) | News (AcuRank) |\n| ------------- | ----------- | -------------- | ----------- | -------------- | ----------------- | -------------------- | ----------- | -------------- |\n| NDCG\\@10    | 74.6 | 74.2 | 70.2 | 71.8 | 84.4 | 85.3 | 52.7 | 53.9 |\n| # Calls     | 18.0 | 18.2 | 18.0 | 16.3 | 27.0 | 21.8 | 18.0 | 18.5 |\n| Window size | 20.0 | 16.6 | 20.0 | 16.7 | 20.0 | 16.3 | 20.0 | 16.2 |\n| Input length| 2156 | 1831 | 2162 | 1822 | 3991 | 3757 | 3992 | 3989 |\n| Latency (s) | 126 | 106 | 126 | 93 | 213 | 142 | 179 | 150 |\n| petaFLOPs   | 0.61  | 0.52  | 0.62  | 0.46  | 1.8  | 1.3  | 1.2  | 1.2  |\n\n> Table 6: Additional evaluation of average per‑query efficiency — SW-1 vs. AcuRank-9\n\n| Metric  | DL19 (SW‑1) | DL19 (AcuRank‑9) | DL20 (SW‑1) | DL20 (AcuRank‑9) | TREC‑COVID (SW‑1) | TREC‑COVID (AcuRank‑9) | News (SW‑1) | News (AcuRank‑9) |\n| ------------- | ----------- | ---------------- | ----------- | ---------------- | ----------------- | ---------------------- | ----------- | ---------------- |\n| NDCG\\@10    | 74.0 | 73.3 | 70.2 | 71.4 | 84.1 | 83.2 | 52.3 | 53.0 |\n| # Calls     | 9.0  | 9.0  | 9.0  | 8.9  | 9.0  | 9.0  | 9.0  | 9.0  |\n| Window size | 20.0 | 18.9 | 20.0 | 18.9 | 20.0 | 18.8 | 20.0 | 18.9 |\n| Input length| 2149 | 2058 | 2152 | 2062 | 3990 | 3865 | 3992 | 3987 |\n| Latency (s) | 93   | 58   | 62  | 59    | 73  | 67    | 88 | 84   |\n| petaFLOPs   | 0.30 | 0.29 | 0.31  | 0.29 | 0.59 | 0.57 | 0.59 | 0.59 |"}, {"review_id": "rhm0n1ZakX", "reviewer": "Reviewer_ki4C", "summary": "This paper proposes an approach for information retrieval via second-stage reranking using LLMs. The limited context length of LLMs necessitates breaking down large first-stage candidate sets into small batches, and the high inference cost motivates minimizing the number of LLM calls. Existing approaches like sliding-window and tournament-style methods apply a fixed computational budget. The proposed approach models uncertainty in document relevance scores using the TrueSkill model (represents relevance not as a single point value, but as a Gaussian distribution) and uses it to decide which documents need to be reranked by the LLM. This allows dynamic choice of documents for comparison and early stopping when the uncertainty for top ranked documents is small. The approach shows promise in terms of accuracy-efficiency trade-off on several retrieval benchmarks (TREC-DL and BEIR).", "questions": "* Is t(k) needed for the algorithm? Is it computed from the \\mu_i’s? This was not clear to me.\n* Can you please comment on the computational cost of the TrueSkill overhead (outside LLM calls)?\n* Please detail how your approach relates to [Budget-Constrained Document Re-ranking with Bayesian LM-Based Pairwise Comparisons](https://openreview.net/pdf?id=3m34mqglmh)\n\nMinor / Typos\n* Line 80: missing space “TDPart[25]”\n* Line 149: “the the”\n* Line 189: was \\tau defined?", "limitations": "See Weaknesses/Questions above.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* The proposed approach is principled and well justified.\n* Using relevance uncertainty to select documents for reranking with TrueSkill is an elegant solution.\n* The approach serves as a meta-framework using the LLM as a black-box reranker, making it a practical and broadly applicable approach.\n* Empirical evaluation shows compelling results in terms of accuracy-efficiency trade-off.\n\nWeaknesses:\n* Unaddressed computational overhead from TrueSkill (see detailed questions below).\n* Closely related paper needs to be added to related work.", "was_revised": true, "final_justification": "The authors adequtely addressed my concerns by providing detailed data showing the negligible computational overhead of TrueSkill and agreeing to add a missing related work. I would like to keep my recommendation (Accept).", "rebuttal": "We thank the reviewer for the positive and supportive comments. We are glad the reviewer found our probabilistic modeling approach effective and appreciated the reproducibility of our results. Minor concerns raised by the reviewer are addressed below.\n\n\n### 1. Computational Overhead of TrueSkill\n\n- We thank the reviewer for raising this point. We measured and reported the computational overhead of TrueSkill at Table 7 (below), which was negligible compared to the cost of LLM reranker calls. On the DL19 benchmark, the total runtime of AcuRank was approximately 58.28 seconds, among which the cumulative time spent on TrueSkill updates was only 0.06 seconds (0.1%). The portion of running Trueskill versus the total process was consistent (0.1%) across subsets of data (DL19, DL20, TREC-COVID, News) and for AcuRank-9 and AcuRank. This was measured using `time.time()` around the call to `trueskill.rate()` (line 170 of `run.py` in the supplementary material). \n- The `trueskill.rate()` function performs lightweight updates to the mean and variance of document scores based on closed-form Gaussian updates (see Supplementary Section 2.3), which are efficiently computed on CPU. This confirms that nearly all computation time in AcuRank is spent on LLM calls, with minimal overhead from the uncertainty modeling.\n\n> Table 7: Comparing per-query end-to-end Latency with the TrueSkill overhead\n\n| Latency    | DL19 (AcuRank‑9) | DL19 (AcuRank) | DL20 (AcuRank‑9) | DL20 (AcuRank) | TREC‑COVID (AcuRank‑9) | TREC‑COVID (AcuRank) | News (AcuRank‑9) | News (AcuRank) |\n| ------------------ | ---------------- | -------------- | ---------------- | -------------- | ---------------------- | -------------------- | ---------------- | -------------- |\n| **Total (s)**  | 58.28    | 105.98 | 59.28    | 93.30  | 67.32    | 142.08  | 83.65    | 149.58  |\n| **TrueSkill (s)** | 0.06  | 0.11   | 0.06  | 0.10   | 0.06  | 0.13   | 0.06  | 0.11   |\n| **TrueSkill ratio (%)**   | 0.10 %  | 0.10 %   | 0.10 %  | 0.11 %   | 0.09 %  | 0.09 %   | 0.07 %  | 0.08 %   |\n\n\n### 2. Usage and Computation of $t(k)$\n- We thank the reviewer for the clarification request. The threshold $t(k)$ is indeed used in our algorithm. As described in Section 3.3, it is part of the Uncertainty-based Selection step (Line 3 of Algorithm 1), where it helps identify documents whose inclusion in the top-$k$ set is uncertain.\n- The formal definition of $t(r)$ is provided in L. 154–157. It is the threshold for which the expected number of documents exceeding it in relevance equals $r$, i.e., $\\sum_i \\mathbb{P}(x_i > t(r)) = r$. Each document's relevance $x_i$ is modeled as a Gaussian distribution determined by its current estimated mean $\\mu_i$ and variance $\\sigma_i^2$, so the value of $t(r)$ depends on these parameters across all documents. While this equation does not admit a closed-form solution, we exploit its monotonicity to efficiently compute $t(k)$ via binary search. We will clarify this explanation in the final version.\n\n\n### 3. Related Work: Budget-Constrained Bayesian Pairwise Reranking\n- We thank the reviewer for bringing this work to our attention. To the best of our knowledge, the paper was made public shortly before our submission, and was under review and not yet publicly visible during the time of our research, so we were unable to cite the paper.\n- While both methods adopt TrueSkill-based uncertainty modeling, the objectives and settings differ significantly. That work uses a fixed-budget pairwise reranking strategy, whereas our approach performs listwise reranking with adaptive computation, dynamically allocating effort based on ranking uncertainty. This enables AcuRank to achieve both high efficiency and accuracy in zero-shot reranking scenarios.\n- Nontheless, since the paper is relevant to our work, we will include a discussion in the related work section of the final version.\n\n\n### 4. Minor Issues\n- We thank the reviewer for pointing out the minor issues. We will correct the typos on Line 80 and Line 149. As for $\\tau$ in Line 189, we define it as the threshold at which the number of uncertain documents $|C|$ satisfies the stopping criterion. We will make this definition more explicit in the final version."}, {"review_id": "NirEc6ducW", "reviewer": "Reviewer_nvvL", "summary": "The existing methods for listwise reranking using large language models are computationally expensive. While there have been various attempts to address these issues, they still suffer from problems of rigidity and lack of adaptability. To overcome these challenges, this paper proposes AcuRank, an uncertainty-aware reranking method, which utilizes the TrueSkill Bayesian rating system for reranking.", "questions": "See the Weaknesses section.", "limitations": "See the weaknesses section.\n\nI am willing to increase the rating based on the authors response on my questions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper is well written and easy to follow.\n- Using uncertainty as for the reranking metric is an interesting attempt.\n- Experimental results prove the efficacy of the proposed method.\n\nWeaknesses\n\n- It is not trivial to understand the motivation for setting the initialization variance to $\\sigma^2/3$. It would be helpful to have either an ablation experiment or more motivation to clarify this.\n- It would be great to have a qualitative example showing how the predictive mean and ranking of the retrieved documents change during the Bayesian update. For instance, documents that initially had high scores but were uncertain might have their scores decrease and uncertainty reduce, leading to a lower rank after the update, or vice versa.\n- It would be helpful for readers if there exist the ablation experiments on the uncertainty threshold.\n- It would be helpful to analyze how the scale of the updated mean and the number of updates required for the final update change as the number of retrieved documents, $n$, varies. This would provide a clearer understanding of how the method operates as $n$ changes.\n- Let’s consider a document set ${\\mathcal{D}_1, \\ldots, \\mathcal{D}_n}$. After reranking this set, we obtain the result ${\\hat{\\mathcal{D}}_1, \\ldots, \\hat{\\mathcal{D}}_n}$. Now, suppose a new set of documents ${\\bar{\\mathcal{D}}_1, \\ldots, \\bar{\\mathcal{D}}_m}$ is added to the collection. The task is to examine whether the reranked result of the combined set ${\\mathcal{D}_1, \\ldots, \\mathcal{D}_n, \\bar{\\mathcal{D}}_1, \\ldots, \\bar{\\mathcal{D}}_m^*}$ preserves the relative order of the original documents \\${\\mathcal{D}\\_1, \\ldots, \\mathcal{D}\\_n}\\$ as \\${\\hat{\\mathcal{D}}\\_1, \\ldots, \\hat{\\mathcal{D}}\\_n}\\$. An experiment focusing on this could help verify whether the method maintains the relative ranking robustly, regardless of the composition of the document set. This would ensure that the method is consistent in preserving the order of the original documents even when new documents are added.", "was_revised": true, "final_justification": "They provide additional explanations and experiments which are reasonable to increase the score.", "rebuttal": "Thank you for providing valuable comments to improve our paper! We are especially encouraged by the recognition of our adaptive computation strategy in listwise reranking. We hope our comments are sufficient to answer the questions raised and that you consider raising the overall rating of our work. We would greatly appreciate it if you could review our comments and inform us if any further discussions or clarification is required.\n\n\n### 1. Variance Initialization\n- We appreciate the reviewer’s question. As described in Supplementary Section 2.4, we provide motivation for our choice of initializing each document’s relevance estimate with a standard deviation proportional to its retrieval score ($\\sigma_i = \\mu_i / 3$). This setting reflects the idea that documents with higher initial scores may carry greater uncertainty due to potential overestimation. The 1/3 ratio is adopted from the original TrueSkill configuration and maintains a statistically meaningful spread around the prior mean.\n- To further support this design, we conduct an ablation study comparing three initialization variants: (1) a fixed uncertainty ($\\sigma_i = 8$), (2) a more conservative variant ($\\mu_i / 2$), and (3) our default setting ($\\mu_i / 3$). As shown in the table below, the default configuration performs best overall, though all variants preserve the same qualitative trends. This confirms that AcuRank is robust to the specific choice of initialization and supports the effectiveness of our design.\n\n> Table 8: Ablations on initializing variance (BM25 top-100, RankZephyr)\n\n| $\\sigma$    | DL19 | DL20 | DL21 | DL22 | DL23 | DL-H | COVID | NFC | Signal | News | R04 | Touche | DBP | Scif | Avg. | # Calls |\n|----------------------|------|------|------|------|------|---------|------------|----------|--------|------|----------|--------|---------|---------|------|--------|\n| 8 (fixed)   | 74.1 | 72.6 | 70.5 | 51.3 | 46.9 | 39.5 | 85.5 | 36.9  | 31.1   | 52.5 | 56.2  | 33.3   | 45.1 | 76.4 | 55.1 | 13.1   |\n| $\\mu / 2$   | 74.1 | 71.3 | 70.7 | 51.8 | 46.2 | 39.4 | 85.2 | 37.4  | 32.0   | 52.6 | 56.3  | 37.3   | 46.0 | 75.7 | 55.4 | 16.4   |\n| $\\mu / 3$ (AcuRank)  | 74.2 | 71.8 | 70.3 | 52.0 | 47.0 | 39.4 | 85.3 | 37.2  | 31.8   | 53.9 | 56.6  | 36.5   | 46.0 | 75.3 | 55.5 | 19.2   |\n\n\n### 2. Qualitative Example of Bayesian Update\n- We appreciate the reviewer’s request for a qualitative walk-through.\n- **Setup**. The table below shows the trace for the first query of TREC-DL19 as AcuRank iterates five times over **50** candidate passages (n = 50). We highlight two contrasting passages to make the dynamics clear.\n- **Over-estimated early leader (pid 6337909)**: On the first iteration this non-relevant passage holds a slightly higher mean score than the gold passage ($\\mu$ = 13.77 > 13.44). After one unfavourable comparison its mean collapses, confidence tightens, and because subsequent comparisons are unnecessary, the passage is frozen at rank 33.\n- **Initally uncertain passage that surges (pid 4647186, gold)**. Starting lower than 6337909, this passage wins multiple pairwise contests. Each victory pushes its mean up and its σ down until it confidently enters the top-10 (rank 9).\n- The key take-away is that, uncertain winners can surge, over-estimated items are pruned, and edits stop once the confidence is high, saving compute.\n\n> Table 9. Per-iteration trace for Gold-relevant pid 4647186\n\n| Pass |     μ     |     σ    |      Rank     |\n| :--: | :-------: | :------: | :-----------: |\n|   1  |   13.44   |   2.96   |       20      |\n|   2  |   15.48   |   2.46   |       14      |\n|   3  |   17.06   |   2.15   |       10      |\n|   4  |   18.27   |   1.94   |       10      |\n|   5  | **19.02** | **1.78** | **9 ← final** |\n\n> Table 10. Per-iteration trace for Non-relevant pid 6337909\n\n| Pass |     μ    |     σ    |      Rank      |\n| :--: | :------: | :------: | :------------: |\n|   1  |   13.77  |   3.14   |       19       |\n|   2  |   9.50   |   2.66   |       33       |\n|   3  |   9.50   |   2.66   |       33       |\n|   4  |   9.50   |   2.66   |       33       |\n|   5  | **9.50** | **2.66** | **33 ← final** |\n\n\n**Net movement:**\n\n- Gold passage **climbs 11 rank** out of 50 candidates (20 → 9).\n- Non-gold passage **drops 14 ranks** out of 50 candidates(19 → 33).\n\nThis examplifies how AcuRank's Bayesian evidence accumulation boosts performance while saving LLM calls by halting once posterior uncertainty is low.\n\n### 3. Ablations on Uncertainty Threshold\n- Please see our detailed response to Reviewer SkZp under the \"Choice of Uncertainty Thresholds\" section. We had already explored the impact of different uncertainty thresholds through our original configurations (AcuRank-H, AcuRank-HH, and AcuRank-9), which represent varying trade-offs between accuracy and efficiency. In response to the reviewer’s suggestion, we additionally conducted ablation experiments by varying the thresholds $\\epsilon$ and $\\tau$. These results exhibit smooth and monotonic performance-efficiency trade-offs and confirm the robustness of AcuRank across a wide range of settings.\n\n\n### 4. Impact on Update Dynamics over Varying n\n- We thank the reviewer for this insightful suggestion. While our current experiments fix $n$ based on the first-stage retriever (e.g., top-100 or top-1000), we discuss here how varying $n$ could affect the TrueSkill update process in AcuRank. \n- In general, increasing $n$ leads to a larger candidate pool and potentially more reranker calls. However, AcuRank's adaptive computation adjusts the number of updates based on the model's uncertainty. Even as $n$ increases, AcuRank still focuses reranker calls on a relatively small subset of uncertain documents, which can result in sublinear growth in total computation.\n- We conduct and report additional experiment upon reviewer's request. With varying $n$ to 50, 100, 200, and 1000, we measure (1) the average number of updates unitl convergence and (2) the average updated mean ($\\mu$) among the top-100 candidates. (top-50 for $n = 50$).\n- From the result tables shown below, we find that the adaptive behavior of AcuRank helps maintain **scalability** (lower # calls on increased $n$) compared with the sliding window baselines, especially as the the candidate pool size **$n$** grows. For example, when $n$ increases from 100 to 1000 (10x), the average number of calls of AcuRank only triples (68.6 / 18.7 = **3.7x**). In contrast, the sliding windows baselines increase almost linearly (e.g., SW-1: 99 / 9 = **11x**). Also, we notice a mild increase in the average updated $\\mu$ scores as $n$ increases, which is expected since we measured over the top-100. \n- We appreciate the reviewer for highlighting the insightful direction of analysis, and we will include those empirically analyzed results in the revised version.\n\n>  Table 11: AcuRank, # Calls to Converge (rightmost is for SW-1)\n\n| $n$  | DL19 | DL20 | COVID | News | Avg | SW-1 Avg |\n|------|------|------|-------|------|----------|-----------|\n| 50   | 12.6 | 13.2 | 14.3  | 12.0 | **13.0** | **4.0** |\n| 100  | 18.3 | 16.3 | 21.8  | 18.5 | **18.7** | **9.0** |\n| 200  | 26.3 | 23.6 | 30.6  | 25.5 | **28.0** | **19.0** |\n| 1000 | 67.8 | 65.6 | 72.8  | 68.0 | **68.6** | **99.0** |\n\n> Table 12: AcuRank, $\\mu$ Mean (max top-100)\n\n| $n$  | DL19 | DL20 | COVID | News |  Avg | SW-1 Avg |\n|------|------|------|-------|------|----------|-----------|\n| 50   | 10.8 | 11.6 | 10.0  | 12.5 | **11.2** | -   |\n| 100  | 9.9  | 10.5 | 9.4   | 11.5 | **10.3** | -   |\n| 200  | 11.5 | 12.2 | 11.0  | 13.4 | **12.2** | -   |\n| 1000 | 12.0 | 12.8 | 11.6  | 14.1 | **12.6** | -   |\n\n\n\n### 5. Stability of Rankings after Document Addition\n- We thank the reviewer for this interesting suggestion. AcuRank is currently designed to identify the top-$k$ most relevant documents through adaptive reranking. While it can, in principle, produce a full ordering over the candidate set based on estimated relevance scores, its computational focus is on accurately ranking the most promising candidates. As a result, documents identified early as unlikely to belong in the top-$k$ typically receive fewer updates, and their relative ordering may be less reliable.\n- To examine the stability of ranking under document addition, we conduct experiments using a document set $\\mathcal{D}$ and its extended version $\\mathcal{D}^{+}$, where $\\mathcal{D}^{+} \\supseteq \\mathcal{D}$. Specifically, we use the top-50 and top-100 documents from BM25 first-stage retrieval as $\\mathcal{D}$ and $\\mathcal{D}^{+}$, respectively ($|\\mathcal{D}| = 50$, $|\\mathcal{D}^{+}| = 100$). We apply listwise reranking (AcuRank and SW-1 as a baseline) to both sets independently. Then, for a subset $\\mathcal{S} \\subset \\mathcal{D}$, we compute the proportion of preserved pairwise relative rankings across the two reranked results.\n- We consider two variants of $\\mathcal{S}$: (1) the full set $\\mathcal{D}$, which corresponds to the global ranking stability considered by the reviewer, and (2) the subset of relevant documents within $\\mathcal{D}$ based on gold labels. The latter better reflects our practical focus: since AcuRank prioritizes ranking accuracy for top-$k$ candidates, documents deemed irrelevant early on are unlikely to receive sufficient updates, and their mutual ordering may not be reliable. In both cases, AcuRank consistently **preserves relative rankings more robustly than SW-1**, as shown in the table below.\n\n> Table 13: Preserved ratio of pairwise relative ranking \n\n| $\\mathcal{S}$ | Method  | DL19  | DL20  | TREC-Covid | News  |\n| ------------- | ------- | ----- | ----- | ---------- | ----- |\n| $\\mathcal{D}$ | AcuRank | **86.6%** | **88.7%** | **85.6%**      | **86.8%** |\n| $\\mathcal{D}$ | SW-1    | 85.8% | 84.8% | 83.7%      | 83.6% |\n| Gold          | AcuRank | 87.7% | **88.2%** | **85.3%**      | **87.9%** |\n| Gold          | SW-1    | **88.7%** | 86.2% | 81.9%      | 86.0% |"}]

Author rebuttal:

Meta-review: This work addresses the problem of listwise ranking of documents with LLMs. Specifically, it highlights a key limitation of listwise rankers that attempt to balance ranking effectiveness with computational cost. It claims that listwise rankers are inflexible as they  do not adapt to query complexity/ambiguity and assign fixed number of LLM reranking calls to predetermined number of candidates irrespective of complexity/ambiguity. It proposes a remedy to this limitation by adaptively allocating LLM reranking calls to candidates based on the candidate's uncertainty relative to the top-k boundary. Towards this end, it maintains a probabilistic relevance estimate of each candidate using a Bayesian rating system and iteratively updating the estimates based on the observed reranking results. Until convergence, it works with only the uncertain candidates in each iteration while skipping the more certain candidates and thereby allocating  LLM reranking call to only the most uncertain candidates. It claims that this adaptive uncertainty-aware allocation of computation and reranking improves both accuracy and computational efficiency. The proposed approach is tested on TREC Deep Learning and BEIR  benchmarks showing improvement in ranking quality while simultaneously requiring fewer LLM reranking calls compared to the chosen baseline reranking algorithms.


Unlike prior work in document relevance that use point estimates for the relevance of candidates, the current work  models the relevance of each candidate as a Gaussian variable whose mean is the estimated relevance and variance captures both the epistemic uncertainty and global noise in the estimation. While the global noise factor is independent of the candidate and remains constant throughout, the epistemic uncertainty factor is expected to go down iteratively as the model becomes more confident about the relevance of the candidate. This is an interesting and potentially  useful approach for document reranking but is a straightforward adaptation of a well-known prior work, TrueSkill to document retrieval task. The key innovation in the current work is to employ the document relevance distributions to derive useful signals for adaptive resource allocation. Specifically, the probability that a document has rank r and therefore is in the top-k can be computed. However, as this computation is expensive, a computationally more efficient approximation is used by defining a threshold  t(r) such that the expected number of candidates whose relevance exceeds this threshold equals the target rank r and then computing the probability that the current candidate's relevance exceeds the threshold. 

The algorithm for reranking with adaptive computation works in iterations. In each iteration, the algorithm selects a subset of candidates based on their ranking uncertainty. To compute a candidate's uncertainty, the algorithm computes the probability that its relevance exceeds a threshold for rank. If this probability is within a range determined by a hyperparameter, the candidate is regarded as uncertain. The subset of candidates selected in this manner are then partitioned into equal sized groups based on their relevance. Candidates with similar relevance are highly likely to fall in the same group and it is argued that reranking candidates with similar relevance scores yields higher information gain. The algorithm passes each group of candidates to LLM for reranking and uses the resulting ranking to update TrueSkill parameters. The distributions of candidates whose ranking improved/worsened substantially relative to their relevance based ranking are updated substantially. The iterative refining of the distributions continues till any of the stopping criteria is met. The algorithm produces the final ranking of the candidates according to the decreasing order of their final  relevance estimate.

Experimental study is centered around TREC-DL and BEIR benchmarks, retrieval effectiveness is reported using NDCG@10 metric and efficiency is measured as number of reranker calls per query. BM25-Top100, BM25-Top100 and SPLADE++ED-Top100 are used as the first stage retrievers. RankZephyr and RankGPT are used as the rerankers with a candidate list size of 20. Sliding windows, TourRank and TrueSkill-Static are used as the listwise ranking baselines.

At the lowest #Calls setting reported (Table 1), the proposed algorithm achieves the same or better NDCG@10 on 8 datasets and worse NDCG@10 on 6 datasets compared to the strongest performing baseline SW-1. The average gain in NDCG@10 over all the datasets is 0.3 relative to SW-1. As #Calls increases, the algorithm demonstrates better retrieval effectiveness than the baselines but the improvement is incremental. Ablative study demonstrates the effect of the design choices (TruSkill Score Initialization, Partitioning and Stopping Criteria) on effectiveness and efficiency.


The paper is well-motivated and well-written. The idea of adaptively allocating reranker calls to documents based on their uncertainty is interesting and novel. Use of TrueSkill to iteratively refine candidate relevance is sensible though straightforward. Experimental study is designed reasonably well to demonstrate the benefits of the proposed algorithm over the baselines. Improvement in retrieval effectiveness over the baselines is incremental though not consistent across the datasets. Authors were responsive to the concerns and questions fielded by the reviewers in the review as well as rebuttal discussions and the concerns were largely addressed. Overall, the work presents an interesting approach to adaptive computation with promising results.
Decision: Accept (poster)