Active Learners as Efficient PRP Rerankers

Jeremías Figueiredo Paschmann; Juan Kaplan; Francisco Nattero; Santiago Barron; Juan Wisznia; Luciano del Corro

Source-linked AI summary

Active Learners as Efficient PRP Rerankers

Jeremías Figueiredo Paschmann, Juan Kaplan, Francisco Nattero, Santiago Barron, Juan Wisznia, Luciano del Corro

arXiv:2605.14236v2May 14, 2026cs.LGcs.AIcs.CL

TL;DR

PRP reranking relies on noisy, order-sensitive pairwise judgments, while classical sorting is poorly matched to call-budgeted top-K selection. The paper reframes reranking as active learning with noise-robust pairwise oracles, finding higher NDCG@10 in the call-constrained regime and up to 7× fewer calls for comparable quality.

Problem
Noisy, order-sensitive, and sometimes intransitive LLM preferences make classical sorting a limited fit for call-efficient top-K reranking.
Method
The paper adaptively selects uncertain pairwise comparisons and uses randomized prompt directions to convert position bias into zero-mean noise with one call per pair.
Results
Active rankers outperform sorting throughout B=200–450, reaching 66.1 versus 56.4 NDCG@10 at B=300 and comparable quality with up to 7× fewer calls.
Takeaways & Limitations
Active ranking is preferable to sorting above the warm-up threshold, while sorting remains preferable at very small or very large budgets.
Takeaways & Limitations
Results may vary with prompt design, model family, and decoding settings, and the call-based cost metric omits system-level overheads and is not fully end-to-end.

Abstract

from arXiv · show

Pairwise Ranking Prompting (PRP) elicits pairwise preference judgments from an LLM, which are then aggregated into a ranking, usually via classical sorting algorithms. However, judgments are noisy, order-sensitive, and sometimes intransitive, so sorting assumptions do not match the setting. Because sorting aims to recover a full permutation, truncating it to meet a call budget does not produce a dependable top-K. We thus reframe PRP reranking as active learning from noisy pairwise comparisons and show that active rankers are drop-in replacements that improve NDCG@10 per call in the call-constrained regime. Our noise-robust framework also introduces a randomized-direction oracle that uses a single LLM call per pair. This approach converts systematic position bias into zero-mean noise, enabling unbiased aggregate ranking without the cost of bidirectional calls.

1 Introduction

The paper reframes PRP reranking as active learning from noisy pairwise comparisons because sorting assumptions fail under stochastic, order-sensitive LLM judgments. It introduces randomized-direction prompting to improve call efficiency and reports stronger NDCG@10–cost trade-offs for active rankers.

Motivation: LLM reranking in RAG makes call efficiency important because invocations dominate cost and latency while systems seek a high-quality sorted prefix.Reranking strongly affects downstream answer quality, and major cloud providers offer it as a managed service.
Problem: Classical sorting is mismatched to PRP because LLM comparisons are stochastic, can violate transitivity, and waste budget refining an unstable full permutation instead of the top-K.PRP supplies noisy preferences, while sorting determines which pairs to query.
Problem: Standard PRP uses 2 calls per pair to address presentation-order effects, yet preference cycles persist when swapping document order changes judgments.Order sensitivity further undermines sorting-based assumptions.
Approach: The proposed framework adaptively selects noisy pairwise comparisons to maximize top-K quality within a budget and evaluates a one-call randomized-direction oracle.Randomizing prompt direction converts position bias into zero-mean noise, enabling cheaper preference estimates.
Results: 44% reduction in calls accompanies Mohajer’s randomized-direction quality ceiling rising from 66.96 to 68.0 while required budget falls from B=450 to B=250.Across BEIR-style tasks, active rankers reach NDCG@10 comparable to QuickSort (Avg. 56.8 for Flan-T5-XL) with up to 7× fewer calls.

2 Related Work

Prior PRP work elicits pairwise LLM preferences and aggregates them with sorting algorithms designed for transitive, complete rankings. This paper instead focuses on improving scheduling within pairwise PRP, whose fine-grained signal and constrained-output reliability support its continued deployment.

Pairwise LLM reranking: PRP aggregates pairwise LLM preferences into rankings, typically using sorting algorithms that assume transitivity and target an unbudgeted complete order.Pairwise comparisons are also direction-sensitive, motivating attention to order effects.
Setwise and listwise methods: Setwise and listwise methods reduce cost by processing multiple documents per call, but they change the prompting primitive.Pairwise and listwise calls differ in token cost, context length, and bias, so raw call counts are not directly comparable.
Paper positioning: The paper improves scheduling within pairwise PRP, which remains widely deployed for its fine-grained signal and constrained-output reliability.The two directions are presented as complementary rather than as interchangeable accounting units.

3 Reranking from Noisy Comparisons

The reranking problem selects an ordered top-K list from N retrieved candidates using only noisy pairwise preference outcomes. Its cost is measured in LLM inference calls, with pairwise judgments modeled through win probabilities and pair-consistency.

Problem setup: Given query q, the reranker maps N retrieved candidates, with N ≥ K, to an ordered top-K list R_K(q).The output list contains items from the candidate set D(q).
Pairwise oracle interface: Each unordered candidate pair yields a noisy binary outcome X_ij(q), where X_ij(q) = 1 means d_i is judged more relevant than d_j.The preference relation is written d_i ≻ d_j.
Pairwise oracle interface: Pairwise outcomes are characterized by win probabilities p_ij(q) and enforce pair-consistency, p_ij(q) = 1 − p_ji(q).Pair-consistency holds for distinct candidates and is enforced through oracle design.
Call-centric cost: Reranking efficiency is evaluated by counting LLM inference calls, distinguishing bidirectional and randomized-direction pairwise querying.Bidirectional querying uses two calls per pair, while randomized-direction querying is introduced in the oracle interface.

4 Selecting Active Rankers for Call-Budgeted Top-K Reranking

This section reframes call-budgeted top-K reranking as active comparison scheduling: rankers focus calls on uncertain or likely-contending candidates while tolerating noisy, non-global-order preferences and producing useful prefixes anytime.

Motivation: Active rankers concentrate comparisons on uncertain candidates, improving the schedule without model training or extra forward passes while leaving LLM calls as the dominant cost.This replaces sorting’s uniformly informative comparison assumption with lightweight bookkeeping for the same comparator.
Selection criteria: The selection criteria are best-K or prefix identification, noise tolerance without assuming a global order, and competitive anytime outputs.These criteria define the target behavior under a strict call budget B and pairwise-oracle interface.
Active rankers: The benchmark compares tournament-based and anchor-based active rankers, omitting methods that assume transitivity or target a full global ranking.The two families are chosen as complementary approaches to comparison scheduling under call constraints.
Tournament-based ranker: Tournament-based heap extraction identifies best-K by focusing comparisons on likely contenders and uses one oracle call per match.This approach follows Mohajer et al. (2017) and is evaluated against the anchor-based alternative.

5 Results

Across BEIR-style and TREC reranking with N=100 candidates and K=10, active rankers improve call efficiency in the constrained regime, while sorting catches up at larger budgets. Randomized-direction prompting reaches peak quality sooner, and within-query parallelism may reduce wall-clock time.

Setup: Experiments rerank the top N=100 BM25 candidates into K=10 lists and report NDCG@10 under budgets B ∈{100, 150, . . . , 500}.The pairwise oracle uses Flan-T5-L/XL with bidirectional or randomized-direction prompting.
Main findings: In the call-constrained regime (B ≈200–450), Mohajer outperforms PRP rerankers under the same oracle.
Main findings: Randomized-direction compresses time-to-quality, with Mohajer reaching peak quality by B=250.
Budget effects: At high budgets, sorting catches up as global refinement pays off; HeapSort surpasses Mohajer at B=300 (68.50 vs. 68.00) and reaches 68.71 at B=500.Below the warm-up threshold (∼100 calls for N=100, K=10), sorting is preferable; at B ∈{100, 150}, QuickSort reaches ≈55.9 NDCG@10 while Mohajer is at 30.1.
End-to-end efficiency: Both active rankers support within-query parallelism through independent tournaments or anchor comparisons, potentially reducing wall-clock time by an order of magnitude.

6 Conclusion

The paper reframes PRP reranking as budgeted learning from noisy pairwise comparisons rather than deterministic sorting. Active rankers improve low-budget NDCG@10, while randomized-direction prompting improves efficiency by covering roughly twice as many pairs as bidirectional prompting at the same budget.

PRP reranking is better modeled as budgeted learning from noisy pairwise comparisons than as deterministic sorting.
Active rankers yield higher NDCG@10 at low budgets, whereas sorting helps mainly when large budgets make global refinement affordable.
At the same budget, randomized-direction prompting covers roughly twice as many pairs as bidirectional prompting.

Limitations

The study’s conclusions are limited by reliance on elicitable pairwise LLM comparators, incomplete cost and latency accounting, and unimplemented parallel execution. Key empirical and theoretical uncertainties remain around randomized-direction gains, PAC+Bubble’s multiplier m, and oracle-output independence.

Scope and measurement: Results may vary with prompt design, model family, and decoding settings because the study assumes a reliable pairwise LLM comparator with constrained outputs.The cost metric counts LLM calls but omits system-level overheads, latency is not fully end-to-end, and parallel execution was not implemented.
Theoretical support: Randomized-direction oracles yield empirically consistent NDCG@10 gains, but their advantage lacks a theoretical explanation.The proposed explanation that independent single-direction samples benefit adaptive algorithms more than correlated bidirectional samples remains plausible but unproven.
Hyperparameter selection: PAC+Bubble uses a candidate-pool multiplier hyperparameter m, default m = 3, to trade comparison cost against coverage of the prior ranking.No systematic ablation was performed; the optimal value likely depends on prior quality and dataset characteristics, motivating data-driven or adaptive selection.
Assumptions: Active-ranking theory often assumes conditionally independent oracle outputs, an assumption real LLM APIs may violate through hidden state, caching, or nonstationarity.These API behaviors may undermine the independence assumptions used in the theoretical framing.

A Parallelization Opportunities

Both active ranking algorithms offer substantial parallelization opportunities that could reduce wall-clock latency. Mohajer parallelizes tournaments, heap construction, and same-depth comparisons, while optimized PAC parallelizes anchor comparisons and uses lightweight aggregation.

Both proposed active ranking algorithms exhibit substantial potential for parallel execution and reduced wall-clock latency.
Mohajer: Mohajer parallelizes K independent tournaments, heap construction, and pairwise comparisons at identical tree depths.Parallel heapify can achieve O(log n) depth, while same-depth comparisons can be batched for simultaneous LLM inference.
Optimized PAC: Optimized PAC parallelizes independent candidate-anchor comparisons, with O(K2) comparisons subject primarily to LLM inference throughput.Winner-set construction and greedy accumulation are lightweight relative to comparison costs.
Latency implications: O(log Q · log K) parallel rounds could replace Mohajer’s O(n log K) sequential comparisons, while PAC could use O(√n) rounds with batch size K.These theoretical reductions assume high-throughput LLM inference through batched GPU inference or distributed serving; experiments used approximately 350 Mohajer and 185 PAC comparisons.

C Supplementary Graphs

This section presents supplementary latency figures comparing NDCG@10 with estimated task time across GPUs. The figures cover two TREC Deep Learning datasets and two LLMs, showing randomized and bidirectional oracles and convergence points.

Flan-T5-XL: For Flan-T5-XL, Figure 2 covers TREC DL 2019 and DL 2020 and shows randomized and bidirectional oracles.Solid lines represent randomized oracles, dotted lines represent bidirectional oracles, and X marks indicate convergence.
Latency experiments: The supplementary figures report NDCG@10 against estimated time per task across GPUs for latency experiments.These figures supplement the latency experiments referenced in the main text.
Qwen3-4B-Instruct-2507: For Qwen3-4B-Instruct-2507, Figure 3 covers TREC DL 2019 and DL 2020 with randomized and bidirectional oracle curves.Solid lines are randomized, dotted lines are bidirectional, and X marks show when an algorithm has converged.

D Statistical Significance

The paper assesses result stability and significance with two complementary non-parametric bootstrap analyses: seed-resampling confidence intervals and paired query-level significance tests. These analyses use 10,000 resamples and evaluate NDCG@10 differences at each budget.

Seed-resampling uncertainty: Seed-resampling uncertainty is measured across 8 oracle seeds using 95% confidence-interval half-widths for mean NDCG@10.The randomized-direction oracle reports these intervals in Table 1; the bidirectional oracle is deterministic given pairwise outcomes.
Paired significance tests: Paired bootstrap tests resample queries to determine whether each mean NDCG@10 difference between methods differs significantly from zero at p < 0.05.Tests are conducted separately for each budget with 10,000 query resamples.
Paired significance tests: Table A.8 tests Mohajer+Bubble against BubbleSort on TREC DL19+DL20 using Flan-T5-XL, marking significant direction with ↑ or ↓ and nonsignificance with =.Each cell reports the direction and mean ∆NDCG@10 difference.
Paired significance tests: Table A.9 applies the same paired-bootstrap comparison to Mohajer+Bubble versus HeapSort on TREC DL19+DL20 using Flan-T5-XL.Cells report the direction and mean ∆NDCG@10 (A−B), with ↑ or ↓ for significance and = otherwise.

E Proof of Aggregate Unbiasedness for Randomized-Direction Oracle

The randomized-direction oracle removes input-order dependence in aggregate pairwise preferences, despite order bias in individual LLM calls. Its randomization makes the aggregate estimator reciprocal in expectation and symmetric with respect to document order.

Order independence: The oracle’s probability of preferring document A over B is independent of comparator input order, satisfying Pr[Vij = 1] = 1 − Pr[Vji = 1].Here, Vij denotes the randomized-direction oracle’s output.
Aggregate reciprocity: Randomizing the comparator direction converts position-specific bias in individual LLM inferences into reciprocal aggregate comparisons.The resulting comparison probabilities are symmetric with respect to document order.
Unbiasedness: The aggregate estimator is symmetric and unbiased with respect to document order, even when a single inference is biased toward a specific position.The proof expresses the reciprocal comparison probability as an average of the two randomized input directions.