Summary

• Novel measure-based perspective on benchmarks: The paper formalizes a benchmark as an empirical measure over item difficulty, enabling rigorous mathematical treatment of two fundamental failure modes: measure mismatch (difficulty distribution differing from intended target) and coverage gaps (uncovered difficulty regions that hide localized model improvements).
• Two diagnostic metrics with theoretical guarantees: The authors propose DDM (Difficulty Distribution Mismatch) based on the 1-Wasserstein distance, and Max Gap (maximum adjacent difficulty gap), both backed by theorems establishing their direct relationship to score distortion, rank stability, and detectability of localized training improvements.
• Widespread empirical issues across 25 benchmarks: Analysis of benchmarks spanning 7 domains reveals that 40% have DDM ≥ 0.10, 32% have Max Gap ≥ 0.10, and 36% have Top-5 gap sums ≥ 0.30, indicating both failure modes are prevalent in current benchmarks.
• BENCHFILL algorithm: A difficulty-targeted rewrite-and-annotate evolutionary search that fills coverage gaps. With only 3 inserted items per benchmark, it reduces the sum of top-3 gaps by 21.09%–38.88%, close to the oracle upper bound.
• Curated gap-filled benchmark variants: The paper releases AMC23-BenchFill, AIME24-BenchFill, AIME25-BenchFill, and AIME26-BenchFill as community resources with substantially improved difficulty coverage.

Introduction and Theoretical Foundation

Background and Motivation

Benchmark evaluation is widely used for two main purposes: leaderboard comparison (comparing models) and training progress monitoring. However, the paper identifies that conclusions drawn from benchmark scores depend not only on model performance but critically on how benchmark questions are distributed along a difficulty axis.

Two failure modes are identified:

1. Measure mismatch: If a benchmark emphasizes easy questions where models perform similarly, while the target difficulty distribution weights harder questions where models differ substantially, the benchmark may suggest models are nearly tied when they are actually clearly separated. This can even flip the induced ordering.

2. Coverage gaps: If a model improves substantially over a localized difficulty range but the benchmark has few or no questions in that region, the benchmark score may barely change—causing meaningful training progress to be missed.

Formalization

The paper represents a benchmark $B = \{x_i\}_{i=1}^n$ as an empirical measure over difficulty:

$$\nu_{B} = \frac{1}{n}\sum_{i=1}^{n}\delta_{z_{i}}$$

where $z_i \in [0,1]$ is the difficulty of item $x_i$ and $\delta_z$ is a point mass at difficulty $z$. The benchmark score becomes an integral:

$$S_B(\theta) = \int s_{\theta}(z)\,d\nu_B(z)$$

For two models $\theta$ and $\theta'$, the performance difference is:

$$D_B(\theta',\theta) = S_B(\theta') - S_B(\theta) = \frac{1}{n}\sum_{i=1}^{n}\Delta(z_i) = \int \Delta(z)\,d\nu_B(z)$$

where $\Delta(z) := s_{\theta'}(z) - s_{\theta}(z)$ is the difficulty-conditioned performance difference.

Theoretical Foundation: Measure Mismatch

A target distribution $\mu \in \mathcal{P}([0,1])$ represents the intended evaluation distribution. The Difficulty Distribution Mismatch (DDM) is defined as:

$$\mathrm{DDM}(B;\mu) := W_1(\nu_{B},\mu) = \inf_{\pi \in \Pi(\nu_{B},\mu)}\int_{[0,1]^2}|u-v|\,d\pi(u,v)$$

Theorem 2.1 (Distribution mismatch controls score distortion and rank stability): If the performance difference function $\Delta$ is $L$-Lipschitz, then:

$$\left|D_B(\theta',\theta) - D_{\mu}(\theta',\theta)\right| \leq L\,W_1(\nu_{B},\mu)$$

Consequently, if $|D_{\mu}(\theta',\theta)| > L\,W_1(\nu_{B},\mu)$, then $\operatorname{sign}(D_B(\theta',\theta)) = \operatorname{sign}(D_{\mu}(\theta',\theta))$, so no rank flip can occur.

Theorem 2.2 (Uniform target as unique maximin choice): Under complete uncertainty about where performance differences occur along the difficulty axis, the uniform distribution $\lambda = \mathrm{Unif}[0,1]$ is the unique maximin target. For $\rho \in (-1,1)$:

$$\sup_{\mu \in \mathcal{P}([0,1])}V_{\rho}(\mu) = \rho$$

where the unique maximizer is the uniform distribution. This justifies the uniform distribution as a principled default when no prior information is available.

Theoretical Foundation: Coverage Gaps

The maximum gap of benchmark $B$ is defined as:

$$G(B) := \max_{0 \leq j \leq n}\left(z_{(j+1)} - z_{(j)}\right) \tag{1}$$

where $z_{(0)} := 0$, $z_{(n+1)} := 1$, and $\{z_{(j)}\}$ are the ordered difficulty points.

Theorem 2.3 (Maximum gap as exact asymptotic minimax detection boundary): For testing $H_0: s^- = s^+$ versus $H_1$ (existence of an interval $I$ with $|I| = w$ where improvement ≥ $a$):

1. If $w \leq G(B)$, then $\Pi_{\alpha}^{*}(B;w,a,k) = \alpha$ for every $k \in \mathbb{N}$ — the improvement is completely invisible in the worst case, regardless of the number of repeated evaluations.
2. If $w > G(B)$, then $\lim_{k \to \infty}\Pi_{\alpha}^{*}(B;w,a,k) = 1$ — repeated evaluation makes the signal detectable.

This establishes a sharp phase transition: the maximum gap $G(B)$ characterizes the intrinsic local resolution limit of a benchmark.

Methodology

Difficulty Estimation via Item Response Theory (IRT)

Rather than using simple failure rates (which are relative to model ability), the paper uses 1PL IRT model:

$$\Pr(Y_{ij} = 1) = \sigma(\theta_j - b_i)$$

where $\theta_j$ is the ability of model $j$, $b_i$ is the difficulty of item $i$, and $\sigma(\cdot)$ is the logistic function. Items with larger $b_i$ require higher model ability.

Experimental setup:

• Models: 12 LLMs (1.7B–397B parameters) selected via stratified sampling from leaderboard rankings for non-agentic benchmarks; 15–66 state-of-the-art closed-source models from HAL [24] for agentic tasks
• Rollouts: Up to 32 rollouts per item with model-recommended temperature and top-p
• Fitting: Bayesian inference via MCMC with 7 diagnostic checks (4 pre-fit: informativeness, structural consistency; 3 post-fit: Gelman–Rubin statistic $\hat{R}$, ESS, divergent transitions)
• Robustness: Leave-one-out (LOO) analysis confirms 12 models suffice for stable difficulty estimation

Metric Calculation

• Difficulties normalized to $[0,1]$, ECDF computed
• DDM = 1-Wasserstein distance between empirical benchmark measure and same-size uniform reference (equivalently $L_1$ distance between ECDFs)
• Max Gap computed per Eq. (1); Top-5 Sum of largest adjacent gaps reported as reference

BENCHFILL Algorithm

Given the largest gap $[z_L, z_R]$ with target difficulty $z^* = (z_L + z_R)/2$, BENCHFILL:

1. Memory initialization: Maintains memory $M$ of annotated item–difficulty pairs initialized with items closest to the gap
2. Parent retrieval: At each round, retrieves parent items from $M$ with difficulties closest to $z^*$
3. Rewriting: An LLM rewrites parents into children conditioned on target difficulty and a reference list of nearby item–difficulty pairs
4. Difficulty annotation: Each child is annotated via online calibration:

$$\hat{b}(x) = \arg\max_{b}\sum_{j=1}^{m}\left[c_j\log\sigma(\hat{\theta}_j - b) + (K_j - c_j)\log(1 - \sigma(\hat{\theta}_j - b))\right]$$

5. Adaptive memory update: Children closer to $z^*$ become more likely parents in later rounds
6. Selection: After $T$ rounds, selects the valid child minimizing $|\hat{z} - z^*|$; final items reviewed by human experts

Empirical Validation / Results

Key Findings on Benchmark Diagnosis

Measure mismatch findings (from Table 1):

• 40% (10/25) of benchmarks have DDM ≥ 0.10, indicating strong implicit difficulty weighting
• Benchmarks with highest DDM: ScienceQA (0.178), IFEval (0.159), MedQA (0.157), MATH-500 (0.164), MBPP+ (0.163), HumanEval (0.148)
• Low-DDM benchmarks include CORE-Bench Hard (0.036) and SWE-bench-Mini (0.053)

Coverage gap findings:

• 32% (8/25) of benchmarks have Max Gap ≥ 0.10
• 36% (9/25) of benchmarks have Top-5 Sum ≥ 0.30
• AMC23 has the largest Max Gap (0.217) and Top-5 Sum (0.539)
• AIME24–26 have Top-5 sums close to 0.5 despite widespread use in RLVR training monitoring
• Coverage gaps are not merely a small-benchmark artifact: HumanEval (164 items) and BBH-5 objects (250 items) also exhibit substantial gaps

BENCHFILL Results (from Table 2)

Key observations:

• BENCHFILL reduces Top-3 gap sum by 21.09%–38.88% with only 3 inserted items
• Average reduction (32.67%) is close to the oracle upper bound (35.06%) and nearly double the uniform-parent baseline (17.52%)
• On AIME24/25/26, BENCHFILL achieves the oracle reduction
• Target deviation consistently below 0.01, indicating high precision in producing items at intended difficulty levels

Curated Gap-Filled Benchmarks

Four math benchmarks (AMC23, AIME24, AIME25, AIME26) expanded:

• AMC23: 40 → 80 items
• AIME24: 30 → 50 items
• AIME25: 30 → 52 items
• AIME26: 30 → 53 items

All generated items manually reviewed; low-quality/incorrect items discarded. Released as AMC23-BenchFill, AIME24-BenchFill, AIME25-BenchFill, AIME26-BenchFill.

Theoretical and Practical Implications

Theoretical Contributions

1. Formalization of benchmark-as-measure: The measure-theoretic view recasts benchmarks from question collections into empirical measures, making previously implicit notions (e.g., implicit difficulty weighting) precise and analyzable. This is the first work to formally identify measure mismatch and coverage gaps as fundamental failure modes.

2. Sharp theoretical guarantees:

   • Theorem 2.1 establishes that $W_1(\nu_B,\mu)$ directly bounds score distortion and rank stability
   • Theorem 2.3 provides an exact minimax detection boundary — no level-α test can achieve nontrivial worst-case power for improvements narrower than the maximum gap, regardless of sample size

3. Principled default target: Theorem 2.2 justifies the uniform distribution as the unique maximin choice under uncertainty, providing a neutrality criterion for benchmark design when no prior is available.

Practical Contributions

1. Benchmark diagnosis: DDM and Max Gap provide simple, interpretable diagnostics. High-DDM benchmarks' leaderboard conclusions carry implicit difficulty weighting that users must interpret with caution. Large-gap benchmarks may miss meaningful training progress, causing premature abandonment of promising runs.

2. BENCHFILL as a tool: The algorithm demonstrates that gap-filling is practical and efficient — near-oracle performance with just 3 LLM-rewritten, human-validated items per benchmark.

3. Community resources: Released difficulty estimates for 25 benchmarks and 4 gap-filled benchmark variants support more reliable future evaluation.

4. Interpretive caution: The paper notes non-uniformity is not inherently problematic when it matches intended evaluation objectives — but when no objective is specified, high-DDM leaderboard results reflect benchmark-weighted comparisons, not difficulty-neutral ones.

Conclusion

This work introduces a measure-based view of benchmark evaluation, representing benchmarks as empirical measures over difficulty. This perspective enables formal treatment of two failure modes—measure mismatch and coverage gaps—with rigorous theoretical guarantees connecting them to concrete diagnostic metrics:

• DDM (1-Wasserstein distance to a target distribution) bounds score distortion and rank flips
• Maximum gap serves as the exact asymptotic minimax detection boundary for local improvements

Empirical analysis of 25 benchmarks shows both issues are widespread. The proposed BENCHFILL algorithm effectively addresses coverage gaps with minimal inserted items, achieving near-oracle reductions.

Future Directions

The authors suggest the empirical-measure view opens new avenues for rigorously studying benchmark evaluation, including further refinement of gap-filling approaches, extension to other domains, and deeper investigation of how difficulty alignment interacts with model comparison validity.