# Active Sampling for Pairwise Comparisons via Approximate Message Passing and Information Gain Maximization

arXiv: https://arxiv.org/abs/2004.05691 · HTML: https://mlsanity.com/paper/2004.05691/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Apr 2020.

## Built on by (most cited first, 17 of 17)

- [Towards Open-ended Visual Quality Comparison](https://mlsanity.com/paper/2402.16641/) (2024)
- [A Setwise Approach for Effective and Highly Efficient Zero-shot Ranking with Large Language Models](https://mlsanity.com/paper/2310.09497/) (2023)
- [ColorVideoVDP: A visual difference predictor for image, video and display distortions](https://mlsanity.com/paper/2401.11485/) (2024)
- [Perceptual Quality Assessment of NeRF and Neural View Synthesis Methods for Front-Facing Views](https://mlsanity.com/paper/2303.15206/) (2023)
- [An Image Quality Assessment Dataset for Portraits](https://mlsanity.com/paper/2304.05772/) (2023)
- [NeRF-NQA: No-Reference Quality Assessment for Scenes Generated by NeRF and Neural View Synthesis Methods](https://mlsanity.com/paper/2412.08029/) (2024)
- [Measuring Scalar Constructs in Social Science with LLMs](https://mlsanity.com/paper/2509.03116/) (2025)
- [X2HDR: HDR Image Generation in a Perceptually Uniform Space](https://mlsanity.com/paper/2602.04814/) (2026)
- [HDRSDR-VQA: A Subjective Video Quality Dataset for HDR and SDR Comparative Evaluation](https://mlsanity.com/paper/2505.21831/) (2025)
- [GitRanking: A Ranking of GitHub Topics for Software Classification using Active Sampling](https://mlsanity.com/paper/2205.09379/) (2022)
- [Efficiency-Effectiveness Reranking FLOPs for LLM-based Rerankers](https://mlsanity.com/paper/2507.06223/) (2025)
- [Are Optimal Algorithms Still Optimal? Rethinking Sorting in LLM-Based Pairwise Ranking with Batching and Caching](https://mlsanity.com/paper/2505.24643/) (2025)
- [MemRerank: Preference Memory for Personalized Product Reranking](https://mlsanity.com/paper/2603.29247/) (2026)
- [Pairwise Comparisons Are All You Need](https://mlsanity.com/paper/2403.09746/) (2024)
- [ICME 2025 Generalizable HDR and SDR Video Quality Measurement Grand Challenge](https://mlsanity.com/paper/2506.22790/) (2025)
- [Improving Maximum Likelihood Difference Scaling method to measure inter content scale](https://mlsanity.com/paper/2203.13186/) (2022)
- [Towards Standardized Light Field Quality Assessment: Hybrid Subjective Benchmarking and Objective Metric Evaluation](https://mlsanity.com/paper/2607.03494/) (2026)

## Abstract (arXiv)

Pairwise comparison data arise in many domains with subjective assessment experiments, for example in image and video quality assessment. In these experiments observers are asked to express a preference between two conditions. However, many pairwise comparison protocols require a large number of comparisons to infer accurate scores, which may be unfeasible when each comparison is time-consuming (e.g. videos) or expensive (e.g. medical imaging). This motivates the use of an active sampling algorithm that chooses only the most informative pairs for comparison. In this paper we propose ASAP, an active sampling algorithm based on approximate message passing and expected information gain maximization. Unlike most existing methods, which rely on partial updates of the posterior distribution, we are able to perform full updates and therefore much improve the accuracy of the inferred scores. The algorithm relies on three techniques for reducing computational cost: inference based on approximate message passing, selective evaluations of the information gain, and selecting pairs in a batch that forms a minimum spanning tree of the inverse of information gain. We demonstrate, with real and synthetic data, that ASAP offers the highest accuracy of inferred scores compared to the existing methods. We also provide an open-source GPU implementation of ASAP for large-scale experiments.