How Hard is it to Rig a Benchmark? A Social Choice Analysis of Leaderboard Robustness

Technical Summary: "How Hard is it to Rig a Benchmark? A Social Choice Analysis of Leaderboard Robustness"

Problem Definition
The paper addresses the growing incentive for "benchmark gaming," specifically the strategic inclusion of benchmark data in model training to artificially inflate leaderboard rankings. While data contamination and leakage are well-documented phenomena, the authors argue that the extent of manipulation is difficult to verify due to proprietary training data in closed-source models. Instead of focusing on detection, the paper investigates the robustness of benchmarks to such manipulation by construction. The core question is: given a fixed suite of datasets and a set of competing models, how many tasks must a developer include in a target model's training to guarantee that the target model becomes the top-ranked entry?

Methodology: Social Choice and Computational Complexity
The authors formalize multi-task benchmarking as a social choice problem, treating datasets as "voters" and models as "candidates." Under this framework, benchmark-specific training is identified as a form of election manipulation, specifically corresponding to shift bribery with all-or-nothing prices. In this analogy, an external agent (the model developer) pays a cost to shift a preferred candidate (the target model) upward in the rankings of specific voters (datasets).

The paper leverages computational social choice to analyze the difficulty of this manipulation:

1. Complexity Analysis: The authors prove that for any ordinal benchmark operator, the problem of selecting the optimal subset of datasets to train on is equivalent to shift bribery. Consequently, they demonstrate that finding the cheapest way to rig a benchmark is NP-hard under the Borda count and mean win rate aggregation rules.
2. Instance-Level Robustness: To complement the worst-case complexity analysis, the authors introduce a metric called instance-level robustness ($k_B$). This is defined as the minimum number of datasets a developer must include in training to make a specific target model top-ranked. They derive exact mathematical expressions for $k_B$ under four common aggregation rules:
   • Arithmetic Mean: The robustness is determined by the "mean deficit" (the gap between the target and the leader) and the maximal possible gains on individual tasks. The optimal strategy is a greedy selection of tasks with the largest potential gains.
   • Median: Robustness depends on the number of tasks required to push the target model's median score above the highest median of competing models. Only tasks where the target can cross a specific threshold contribute to reducing the deficit.
   • Mean Win Rate: This requires solving an integer linear program (ILP) to find the minimum set of tasks that simultaneously closes the pairwise win-rate deficits against all competing models.
   • Pairwise Majority: Similar to mean win rate, this involves an ILP to ensure the target model wins a majority of pairwise comparisons against all other models.

Experimental Evaluation
The authors evaluate these robustness expressions on two major benchmark suites:

1. MMLU (Massive Multitask Language Understanding): Evaluated via the HELM framework, involving 22 models across 57 subject datasets.
2. BIG-Bench Hard (BBH): Evaluated via the Open LLM Leaderboard, involving 4,507 models across 24 reasoning tasks.

For each suite, they compute the instance-level robustness for every model in the set, treating each in turn as the target. They report the median robustness (the number of tasks required to rig the leaderboard for a "typical" target model) and the fraction of models that can be made top-ranked by training on a small number of tasks (e.g., $K \le 5$).

Key Results
The empirical analysis reveals significant disparities in robustness across aggregation rules:

• Mean Win Rate is Most Robust: Across both suites, the mean win rate rule is consistently the hardest to manipulate.
  • On BBH, the median robustness for mean win rate is 22 tasks (92%), meaning a typical target model must be trained on nearly the entire suite to top the leaderboard. In contrast, the arithmetic mean requires only 13 tasks (54%), and median/pairwise majority require 12 tasks (50%).
  • On MMLU, the median robustness for mean win rate is 44.5 subjects (78%), compared to 16 (28%) for the arithmetic mean.
• Vulnerability of Arithmetic Mean: The arithmetic mean is the least robust rule. A small number of high-gain tasks can significantly alter the leaderboard, allowing a substantial fraction of models to be boosted to the top with minimal manipulation.
• Statistical Significance: Paired Wilcoxon signed-rank tests confirm that these differences in robustness are systematic across the target models and not driven by outliers.
• Normalized Robustness: Even after normalizing for the amount of "room to improve" available to a model (accounting for the fact that weaker models have more potential gain), mean win rate remains the most robust rule.

Significance and Claims
The paper claims that aggregation rules are a primary determinant of benchmark vulnerability. The authors argue that robustness to benchmark-specific training should be treated as a central criterion in benchmark design.

• Trade-offs: While mean win rate offers high robustness by requiring broad manipulation across the suite, it depends on the set of models being compared (sensitivity to the model pool). Conversely, pairwise majority is invariant to the model set but can induce cyclic rankings (Condorcet cycles), though the authors note that Condorcet winners exist in the top ranks of the studied suites.
• Implications: The results suggest that current reliance on arithmetic mean aggregation (common in suites like GLUE and SuperGLUE) creates a low barrier to entry for manipulation. Shifting to more robust rules like mean win rate raises the cost of manipulation, requiring developers to improve performance across a much broader set of tasks to achieve a top rank.
• Limitations: The authors acknowledge that their manipulation model is favorable to the developer (assuming training only improves the target model and never degrades performance elsewhere). In practice, data leakage might have partial or negative effects. However, even under these strong assumptions, the choice of aggregation rule sharply dictates the difficulty of rigging the benchmark.

The paper concludes that while no aggregation rule is immune to manipulation (per the Gibbard-Satterthwaite theorem), the computational and structural difficulty of manipulation varies drastically, providing a quantitative basis for designing more reliable leaderboards.