AcuRank: Uncertainty-Aware Adaptive Computation for Listwise Reranking

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.

1. Variance Initialization

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

Table 8: Ablations on initializing variance (BM25 top-100, RankZephyr)

2. Qualitative Example of Bayesian Update

• We appreciate the reviewer’s request for a qualitative walk-through.
• 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.
• 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.
• 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).
• 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.

Table 9. Per-iteration trace for Gold-relevant pid 4647186

Table 10. Per-iteration trace for Non-relevant pid 6337909

Net movement:

• Gold passage climbs 11 rank out of 50 candidates (20 → 9).
• Non-gold passage drops 14 ranks out of 50 candidates(19 → 33).

This examplifies how AcuRank's Bayesian evidence accumulation boosts performance while saving LLM calls by halting once posterior uncertainty is low.

3. Ablations on Uncertainty Threshold

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

4. Impact on Update Dynamics over Varying 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.
• 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.
• 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$).
• 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.
• We appreciate the reviewer for highlighting the insightful direction of analysis, and we will include those empirically analyzed results in the revised version.

Table 11: AcuRank, # Calls to Converge (rightmost is for SW-1)

Table 12: AcuRank, $\mu$ Mean (max top-100)

5. Stability of Rankings after Document Addition

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

Table 13: Preserved ratio of pairwise relative ranking

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.

1. Computational Overhead of TrueSkill

• 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).
• 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.

Table 7: Comparing per-query end-to-end Latency with the TrueSkill overhead

2. Usage and Computation of $t(k)$

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

3. Related Work: Budget-Constrained Bayesian Pairwise Reranking

• 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.
• 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.
• Nontheless, since the paper is relevant to our work, we will include a discussion in the related work section of the final version.

4. Minor Issues

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

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:

1. Justification for TrueSkill-based Uncertainty Estimation

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

2. Choice of Uncertainty Thresholds

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

Table 3. Analysis on sensitivity to uncertainty thresholds (BM25 top-100, RankZephyr).

3. Generalization across Different LLM Rerankers and Retrieval Setups

• 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.
• 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.
• 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.
• We will include these results on the final revision, and will open-source all related code and configurations to support reproducibility.

Table 4: Results with first-stage retrieval using Contriever top-100

4. Using the Number of Reranker Calls as an Efficiency Metric

• 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).
• 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.
• 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.
• 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.

Table 5: Additional evaluation of average per‑query efficiency — SW-2 vs. AcuRank

Table 6: Additional evaluation of average per‑query efficiency — SW-1 vs. AcuRank-9

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.

1. Missing Baseline Results

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

Table 1: Additional baselines (TourRank-1) on the lower part of main paper Table 1 (BM25 top-1000, RankZephyr)

Table 2: Additional baselines (TourRank-1,2) on the upper part of main paper Table 2 (SPLADE top-100, RankZephyr)

• 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).
• 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.

2. Possibility of Over- or Under-allocation of Computation

• 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.
• We also support our claim with two empirical analyses:
  • 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).
  • 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.
• We also provide a qualitative example of the bayesian update at the response for reviewer nvvL (Number 2, Table 9,10).

3. Justification for TrueSkill-based Uncertainty Estimation

• 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].
• 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.
• 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.

[1] Chung et al., CHI 2022, TaleBrush: Sketching Stories with Generative Pretrained Language Models

[2] Park et al., UIST 2023, Generative Agents: Interactive Simulacra of Human Behavior

[3] Shaikh et al., CHI 2024, Rehearsal: Simulating Conflict to Teach Conflict Resolution