🤖 AI

Submodular Benchmark Selection

This paper formalizes the selection of a small, informative subset of correlated benchmarks for evaluating large language models as a submodular maximization problem under a multivariate Gaussian model, demonstrating that a greedy mutual information approach outperforms entropy-based methods for imputation at small subset sizes.

Original authors: Alexander Smola

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander Smola

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a food critic trying to taste every dish at a massive, endless buffet to decide which chef is the best. You have 57 different dishes (benchmarks) to try. But tasting every single one takes forever, costs a fortune, and your stomach can only handle so much.

The problem? Many dishes taste very similar. If you love the spicy pasta, you'll probably love the spicy noodles too. They are "correlated." So, the big question is: Which small handful of dishes do you actually need to taste to know the whole story?

This paper, by Alex Smola, offers a mathematical recipe to solve that exact problem. It treats the scores of different AI models on different tests like ingredients in a giant soup, using a branch of math called submodular optimization (which is just a fancy way of saying "diminishing returns") to pick the best subset.

Here is the breakdown of their approach using simple analogies:

1. The Two Strategies: "The Diverse Sampler" vs. "The Connector"

The authors propose two different ways to pick your small subset of benchmarks. Think of them as two different shopping lists for that buffet.

Strategy A: The "Diverse Sampler" (Entropy Maximization)
- The Goal: Pick dishes that are all very different from each other.
- The Analogy: You want one spicy dish, one sweet dish, one savory dish, and one sour dish. You don't want three different types of spicy pasta because they all tell you the same thing.
- How it works: This method looks for the "most unique" benchmarks. It's like picking the pivot points of a map. The paper notes this is mathematically identical to a standard technique called "pivoted Cholesky," which is a way of breaking down a big matrix into smaller, manageable pieces.
- The Result: This is great for getting a broad overview, but it might miss the specific details that link the dishes together.
Strategy B: "The Connector" (Mutual Information)
- The Goal: Pick dishes that tell you the most about the other dishes you didn't pick.
- The Analogy: Imagine you pick a "master key" dish. If you know how the chef handles this one specific dish, you can accurately guess how they handle the other 50 dishes, even if you never tasted them. You aren't just looking for variety; you are looking for the dish that is the best "hub" or "bridge" to the rest of the menu.
- How it works: This method calculates how much information one benchmark gives you about the rest of the unselected benchmarks.
- The Result: The paper found that for small budgets (tasting only 1 to 5 dishes), this "Connector" strategy is the winner. It predicts the missing scores much better than the "Diverse Sampler."

2. The "Missing Menu" Problem

In the real world, not every AI model has been tested on every benchmark. It's like a menu where some chefs haven't cooked some dishes yet. The data is incomplete.

The Fix: The authors use a statistical trick called EM (Expectation-Maximization).
The Analogy: Imagine you are trying to guess the recipe of a soup, but you only have a few spoonfuls of it. You take a guess at the missing ingredients based on what you do have, taste the "guess," and then adjust your recipe. You repeat this process over and over until your guess becomes a very accurate estimate of the full soup. This allows them to build a complete picture even with messy, incomplete data.

3. The "Surrogate Gap" (Why the Winner Wins)

The paper discovered a fascinating quirk they call the "surrogate gap."

The Observation: The "Diverse Sampler" (Entropy) actually does a better job at reducing the mathematical error of the remaining dishes (residual variance). It picks the most statistically independent items.
The Twist: However, when it comes to predicting the scores of the dishes you didn't pick, the "Connector" (Mutual Information) wins, especially when you can only pick a few.
Why? Because the "Diverse Sampler" picks items that are unique but might not be very helpful for guessing the others. The "Connector" picks items that are tightly linked to the rest of the group. If you want to guess the future, you need the hub, not just the outliers.

4. The Results: How Many Do You Need?

The authors tested this on real data from ten different AI leaderboards (like MMLU, which has 57 subjects, and MTEB, which has 56 tasks).

The Good News: You don't need to test everything.
The Numbers:
- On the MMLU dataset (57 subjects), picking just 5 carefully chosen benchmarks allowed them to predict the scores of the other 52 with 91% accuracy.
- Even on a messy, incomplete dataset, picking 15 benchmarks captured more than half the information of the whole set.
The Visual: They looked at the "spectrum" of the data (like looking at the colors in a rainbow). They found that the information is packed into a very small number of "colors" (dimensions). Once you pick the right few, the rest is just noise.

Summary

If you want to evaluate AI models without breaking the bank or your patience:

Don't just pick random tests.
Don't just pick the most "different" tests.
Pick the tests that act as the best "connectors" to the rest of the group.
If you only have a tiny budget (1–5 tests), use the Mutual Information method. If you have a larger budget, the "Diverse Sampler" catches up.

The paper provides a mathematical "shopping list" to help researchers stop wasting time on redundant tests and focus on the few that actually matter.

Technical Summary: Submodular Benchmark Selection

Problem Statement

Evaluating Large Language Models (LLMs) comprehensively requires running them on a vast and growing set of benchmarks. This process is computationally expensive and time-consuming. However, empirical evidence suggests that many benchmarks are highly correlated; strong performance on one often predicts strong performance on another. This redundancy implies that a small, well-chosen subset of benchmarks could capture most of the information contained in the full set. The core challenge is identifying which specific subset to select and determining the optimal subset size to maximize information gain while minimizing evaluation costs.

Methodology

The authors formalize benchmark selection as a submodular optimization problem. Given a score matrix $B \in \mathbb{R}^{M \times N}$ representing $M$ models evaluated on $N$ benchmarks, the scores are modeled as independent draws from a multivariate Gaussian distribution $\mathcal{N}(\mu, \Sigma)$ . The goal is to select a subset $A \subseteq \{1, \dots, N\}$ of size $k$ to optimize one of two objectives:

Entropy Maximization ( $H(X_A)$ ): Maximizing the joint uncertainty of the selected benchmarks. Under the Gaussian model, this is equivalent to maximizing $\log \det(\Sigma_{AA})$ . This objective is monotone submodular (with appropriate shifting) and coincides with pivoted Cholesky decomposition. The greedy algorithm for this objective selects benchmarks that maximize the residual conditional variance, providing a diagnostic tied to the covariance spectrum.
Mutual Information Maximization ( $I(X_A; X_{\bar{A}})$ ): Maximizing the information the selected benchmarks provide about the unselected complement. This objective is submodular but generally non-monotone. The authors observe that for small subset sizes $k$ , the marginal gain remains positive, allowing the use of a greedy heuristic. This approach combines forward Cholesky updates with complement refactorization to compute the marginal gain efficiently.

Handling Missing Data:
Real-world score matrices are often incomplete (not all models have been run on all benchmarks). The authors employ the Expectation-Maximization (EM) algorithm to estimate the mean vector $\mu$ and covariance matrix $\Sigma$ from partially observed entries, treating missing values as latent variables under the Missing At Random (MAR) assumption.

Imputation:
Once a subset $A$ is selected, unobserved scores for new models are imputed using the conditional expectation of the Gaussian distribution:
$E[B_{i\bar{A}} | B_{iA}] = \mu_{\bar{A}} + \Sigma_{\bar{A}A} \Sigma_{AA}^{-1} (B_{iA} - \mu_A)$

Key Contributions

The paper presents an end-to-end pipeline for benchmark selection with the following specific contributions:

Submodular Objectives: The formulation of two submodular objectives (Entropy and Mutual Information) for benchmark selection, along with efficient, numerically stable greedy algorithms for both.
EM-Based Estimation: A method for estimating the covariance matrix from incomplete score matrices using EM, enabling the application of these methods to real-world, sparse leaderboard data.
Spectral Diagnostic: A diagnostic tool utilizing eigenvalue decay and the pivoted-Cholesky residual trace to determine the appropriate subset size $k$ . Fast empirical spectral decay indicates that small subsets are likely to be effective.
Empirical Validation: Experiments on three score matrices derived from ten public leaderboards (MMLU, MTEB, and a merged heterogeneous set).

Experimental Results

The authors evaluated their approach using 10-fold cross-validation on three datasets:

MMLU (5,452 models, 57 tasks, fully observed): With just $k=5$ selected benchmarks, the Mutual Information (MI) selection achieved an imputation $R^2$ of 0.91. Entropy selection reached 0.89. Both methods significantly outperformed random selection.
MTEB (263 models, 56 tasks, 77% observed): MI selection outperformed entropy for small $k$ (e.g., $k \le 3$ ), with a gap of roughly 10 $R^2$ points.
MERGED (118 models, 114 tasks, 31% observed): This sparse, heterogeneous dataset was the most challenging. MI selection maintained a clear advantage over entropy for larger $k$ , achieving $R^2 \approx 0.59$ at $k=15$ compared to 0.55 for entropy.

Key Findings:

The "Surrogate Gap": While entropy selection minimizes the residual variance of the selected set (a property of pivoted Cholesky), it does not always maximize the predictive power for the unselected benchmarks. MI selection, which explicitly rewards coupling with the complement, yields superior imputation quality for small subset sizes.
Scalability: For well-conditioned datasets, entropy selection eventually catches up to or overtakes MI as $k$ increases. However, for budget-constrained scenarios (small $k$ ), MI is the preferred objective.
Robustness: Despite formal normality tests rejecting the Gaussian assumption on all datasets, the Gaussian conditional mean (the best linear predictor) provided highly accurate imputations, validating the Gaussian model as a practical working approximation.

Significance and Claims

The paper claims to provide a principled, information-theoretic framework for prescriptive benchmark selection. Unlike prior work that focuses on reducing redundancy within a single benchmark or learning latent skills, this approach selects entire benchmarks to run and imputes the rest without training a complex predictive model beyond covariance estimation.

The authors emphasize that:

MI is superior for small budgets: Mutual Information selection is the recommended strategy when computational resources are limited and the goal is to impute scores for the remaining benchmarks.
Entropy is useful for diversity: Entropy selection remains valuable for maximizing the diversity of the selected set or reducing residual variance in well-conditioned, larger subsets.
Spectral analysis is diagnostic: The eigenvalue decay of the score covariance serves as a reliable indicator for when small benchmark subsets will be effective.

The work concludes that a small number of carefully chosen benchmarks can capture a disproportionate share of evaluative information, potentially reducing the computational cost of LLM evaluation while maintaining high fidelity in performance estimation.