Finding the top-K methods, without wasting comparisons

Suppose that you are interested in conducting a pairwise comparison experiment to identify which of several text-to-speech systems users like best. To save time and money, you would like to identify the most-preferred methods as efficiently as possible.

Designing this experiment is a lot like organizing a tournament. One of the simplest tournament designs (used, for example, in March Madness) is a single-elimination tournament bracket, which is highly comparison-efficient. However, if match outcomes are somewhat random (for example, say the superior basketball team only wins 75% of the time), then the tournament outcome is also random, and the tournament is not guaranteed to find the best contestant.

While this can make for interesting television, it’s an undesirable property in scientific experiments. Our new top-K selection strategy solves exactly this problem. First, the experimenter selects a value of K, which tells the strategy to find the K best methods in the dataset (e.g., top-1 or top-3). Top-K selection leverages our Bayesian Elo model to eliminate contestants we are highly confident are not in the winning set.

Top-K selection reliably finds this winning set faster than other selection strategies. To measure this, we ranked 27 image-compression methods from the CLIC 2024 dataset using an AI rater and pairwise comparisons, running the same experiment ten times with each strategy. Every top-K run found the true top 3. Our standard active-selection strategy found it in 8 of 10 runs, and random selection found it only 21% of the time on the same budget.

In the chart above, each line tracks how many experiments have stably locked in the true top 3 as comparisons are being added. Top-K is the only strategy to reach 100% within budget.

Top-K is now available in Mabyduck for all pairwise experiments. Since top-K spends its comparison budget separating out the winners, its Elo estimates are less accurate for methods below the top-K set. If you need a reliable ranking of every method, stick with random or active selection. If you only care about the best few methods, top-K is the right choice.