Surprise-Guided MergeSort: Budget-Efficient Human-in-the-Loop Ranking via Adaptive Comparison Scheduling

• URL: http://arxiv.org/abs/2606.15623v3
• Date: Tue, 23 Jun 2026 04:34:02 GMT
• Title: Surprise-Guided MergeSort: Budget-Efficient Human-in-the-Loop Ranking via Adaptive Comparison Scheduling
• Abstract summary: We propose a framework to identify which comparisons genuinely require human judgment.<n>The proposed textbfSurprise-Guided MergeSort (SGS) framework achieves this through three integrated components.<n> Validation was conducted on six diverse benchmarks spanning text similarity (STS-B, BIOSSES, SICKR-STS) and image quality assessment (KonIQ-10k, TID2013, LIVE Challenge)
• Score: 0.5861893391102716
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Pairwise comparison is the gold standard for subjective ranking tasks; however, exhaustive annotation requires a massive number of human comparisons ($O(n^2)$). While sorting-based methods have reduced this burden to $O(n\log n)$, they still require expensive human judgment for every single comparison. To further improve annotation efficiency, we propose leveraging a Vision-Language Model (VLM) not as an annotator replacement, but as a \emph{question prioritizer} to identify which comparisons genuinely require human judgment. The proposed \textbf{Surprise-Guided MergeSort (SGS)} framework achieves this through three integrated components: (1) a bottom-up MergeSort scheduler that structures comparisons and exploits transitivity, (2) a composite Surprise Scorer -- combining position-bias-cancelled VLM confidence, Elo gap, and vote entropy -- to quantify comparison ambiguity, and (3) an adaptive budget allocator that routes high-surprise pairs to humans while automating low-surprise pairs via transitivity inference. Validation was conducted on six diverse benchmarks spanning text similarity (STS-B, BIOSSES, SICKR-STS) and image quality assessment (KonIQ-10k, TID2013, LIVE Challenge). SGS effectively identified and skipped up to 535 non-informative comparisons per session. Consequently, it achieved Kendall's $τ{\times}100$ improvements of $+6$ to $+12$ over Active Elo under the same total budget. These results demonstrate that combining VLM-guided surprise metrics with algorithmic sorting provides a generally consistent accuracy-efficiency trade-off across diverse domains.

Related papers

• Prompt Perturbation for Reliable LLM Evaluation over Comparison Graphs [10.095945693317079]
  evaluating large language models (LLMs) is important for understanding their capabilities, comparing competing systems, and supporting the deployment of reliable models in practice.<n>For open-ended tasks, pairwise evaluation has become a popular paradigm, in which two responses to the same prompt are compared and the resulting judgments are aggregated into an overall ranking.<n>A central challenge of this paradigm is intransitivity: the induced comparison outcomes may fail to support any coherent global ranking.
  arXiv  Detail & Related papers  (2026-06-16T07:44:45Z)
• Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
  We formalize this question as *budgeted heteroskedastic multi-judge estimation*.<n>Given $K$ prompt-response pairs, $J$ judges with known costs, and unknown query-judge variances, the goal is to estimate a bounded score vector while minimizing an $ell_p$-error.<n>We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget.
  arXiv  Detail & Related papers  (2026-05-22T08:26:08Z)
• $V_1$: Unifying Generation and Self-Verification for Parallel Reasoners [69.66089681814013]
  $V_$ is a framework that unifies generation and verification through efficient pairwise ranking.<n>$V_$-Infer improves Pass@1 by up to $10%$ over pointwise verification.<n>$V_$-PairRL achieves $7$--$9%$ test-time scaling gains over standard RL and pointwise joint training.
  arXiv  Detail & Related papers  (2026-03-04T17:22:16Z)
• K-Sort Eval: Efficient Preference Evaluation for Visual Generation via Corrected VLM-as-a-Judge [51.93484138861584]
  The rapid development of visual generative models raises the need for more scalable and human-aligned evaluation methods.<n>We propose K-Sort Eval, a reliable and efficient VLM-based evaluation framework that integrates posterior correction and dynamic matching.<n>Experiments show that K-Sort Eval delivers evaluation results consistent with K-Sort Arena, typically requiring fewer than 90 model runs.
  arXiv  Detail & Related papers  (2026-02-10T05:07:46Z)
• BLITZRANK: Principled Zero-shot Ranking Agents with Tournament Graphs [14.085089126904101]
  We introduce a tournament graph framework that provides a principled foundation for $k$-wise ranking.<n>Each $k$-item comparison reveals a complete tournament of $binomk2$ pairwise preferences.<n>We formalize when an item's rank is certifiably determined and design a greedy query schedule that maximizes information gain.
  arXiv  Detail & Related papers  (2026-02-05T08:41:00Z)
• EZ-Sort: Efficient Pairwise Comparison via Zero-Shot CLIP-Based Pre-Ordering and Human-in-the-Loop Sorting [0.5861893391102716]
  Pairwise comparison is often favored over absolute rating or ordinal classification in subjective or difficult annotation tasks.<n>Recent work has greatly reduced the annotation burden (O(n log n)) by actively sampling pairwise comparisons using a sorting algorithm.<n>We further improve annotation efficiency by (1) roughly pre-ordering items using the Contrastive Language-Image Pre-training (CLIP) model hierarchically without training, and (2) replacing easy, obvious human comparisons with automated comparisons.
  arXiv  Detail & Related papers  (2025-08-29T12:06:49Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Sorting with Predictions [1.7042264000899532]
  We explore the fundamental problem of sorting through the lens of learning-augmented algorithms. We design new and simple algorithms using only $O(sum_i log eta_i)$ exact comparisons. We prove that the comparison complexity is theoretically optimal with respect to the examined error measures.
  arXiv  Detail & Related papers  (2023-11-01T18:00:03Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  This paper studies the problem of contextual dueling bandits, where the binary comparison of dueling arms is generated from a generalized linear model (GLM) We propose a new SupLinUCB-type algorithm that enjoys computational efficiency and a variance-aware regret bound $tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$. Our regret bound naturally aligns with the intuitive expectation in scenarios where the comparison is deterministic, the algorithm only suffers from an $tilde O(d)$ regret.
  arXiv  Detail & Related papers  (2023-10-02T08:15:52Z)
• Rank-based Non-dominated Sorting [0.0]
  We introduce Rank Sort, a non-dominated sorting approach exploiting sorting stability and ordinal information to avoid expensive dominance comparisons. Two algorithmic variants are proposed: the first one, RankOrdinal (RO), uses ordinal rank comparisons in order to determine dominance and requires O(N) space; the second one, RankIntersect (RS), uses set intersections and bit-level parallelism and requires O(N2) space. We demonstrate the efficiency of the proposed methods in comparison with other state of the art algorithms in empirical simulations using the NSGA2 algorithm as well as synthetic benchmarks.
  arXiv  Detail & Related papers  (2022-03-25T13:59:42Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.