Random Is Almost Enough? Stable and Low-Cost Benchmark Compression via BestRand

AI summary

Overview

Research area: Natural Language Processing / efficient model evaluation (benchmark compression), spanning text LLMs, vision-language models, agent benchmarks, and vision-language-action (VLA) models.

Technical level: Advanced. The paper builds a theoretical framework (finite-population sampling, multivariate normal approximations, correlation structure across models) alongside a large empirical study, though the resulting method is simple enough to explain without the math.

Scope (one sentence): The paper derives an analytical approximation of the error distribution when a small random subset of a benchmark is used to estimate full-benchmark model scores, explains why random sampling is usually good but occasionally badly wrong, and introduces BestRand, a probe-guided random selection method that cuts the high-error tail at roughly half the construction cost.

What This Paper Is About

Evaluating models on full benchmarks is expensive, so researchers evaluate on a small subset and treat the subset score as an estimate of the full score. This paper asks how reliable that estimate is: it characterizes the distribution of the estimation error, shows that random subsets usually land very close to the true score but a rare few land far away, and traces that instability to the fact that modern foundation models behave similarly and therefore fail on the same items. It then proposes BestRand, which draws many random candidate subsets and uses a handful of cheap "probe" models to pick the one that best matches the benchmark's overall difficulty profile.

Key Contributions

1. An analytical error distribution for benchmark compression. The authors approximate the error vector of subset-based estimates as approximately zero-mean multivariate normal with covariance c(k)²C, where c(k) = sqrt((N−k)/[k(N−1)]) is a finite-population factor, and derive a closed-form lower bound on the probability of large error, Pr(MAE > t) ≥ 2Φ(−t/s), governed by a single scale s.

2. An explanation of why random sampling is "almost enough" but unstable. They show the mode of the MAE distribution converges to the lower endpoint y₀ = sqrt(2/π)·c(k)·σ·sqrt(1−ρ) at rate C₀/sqrt(M) with C₀ ≈ 0.578, so the typical subset is excellent — but the correlation ρ among models drives a long right tail that does not vanish as more models are added.

3. A theoretical result that moving more models does not fix instability. As M → ∞ with fixed k < N and ρ > 0, s → c(k)σ sqrt(ρ) > 0, so expanding the model panel alone cannot remove the shared error; the paper attributes this to shared backbones, overlapping training corpora, and distillation among foundation models.

4. BestRand, a stable, low-cost compression method. It draws a pool of min(nk, N) items, scores only p probe models on it, generates m candidate k-subsets from the pool, and returns the candidate whose probe mean is closest (L2) to the pool reference. The paper validates it on 70 text/multimodal/agent benchmarks plus VLA evaluation.

Main Findings

• Most subsets are very good, a few are very bad. Empirical MAE distributions match the theoretical predictions closely on representative LLM, VLM, and VLA benchmarks; the mode sits near the lower end of the observed distribution, while a long right tail carries a small but non-negligible fraction of high-error draws.

• Instability is intrinsic, not a small-sample artifact. Because s = c(k)σ sqrt(ρ + (1−ρ)/M) increases in ρ, and the (1−ρ)/M term vanishes as M grows, higher behavioral correlation between models lengthens the error tail and cannot be averaged away by evaluating more models. Empirically, ρ and s strongly predict empirical MAE P95 (the long-tail risk measure).

• BestRand improves accuracy across all three benchmark categories at every retention ratio (2%, 5%, 10%, 15%, 20%, 50%). Averaged across all benchmarks and ratios, mean ± std MAE is 2.92 ± 2.80 (text, 44 benchmarks), 2.87 ± 2.43 (multimodal, 16 benchmarks), and 5.43 ± 5.44 (agent, 10 benchmarks), versus Random at 3.47 ± 3.46, 3.24 ± 2.66, and 6.14 ± 5.91 respectively. ZipBench reaches 3.23 ± 2.85 on text and TinyBenchmarks 3.65 ± 3.37; the learned SparseEval variants are far worse (SparseEval Linear 20.98 ± 8.67 on text).

• Aggregate gains versus strong baselines. Against Random, ZipBench, and TinyBenchmarks, BestRand reduces high-error risk by 50.2% and estimation error by 16.4% on average, while using only 51.3% of the construction cost — and just 8.0% of data-dependent baselines' construction records at 2% retention.

• The high-error tail is visibly suppressed. Error-distribution plots on six representative benchmarks at 20% retention show Random with a pronounced right tail and BestRand concentrated near zero.

• Low cost per unit accuracy. Under a normalized construction cost Cost = R/N (where R is the total number of observed model-item scores and N the benchmark size), BestRand achieves lower MAE at the same cost and needs less cost to reach the same MAE; it remains accurate at Cost < 1, while learnable baselines require Cost ≥ 1.

• Robustness to distribution shift. Under score-range shifts (Mid→Tails, Low→High, High→Low), model-family shift (held-out families), and temporal shift (past→future), methods that learn from historical records perform worse than Random in every setting, while BestRand achieves the lowest error in all five listed settings — average MAE 1.69 ± 0.88 versus Random 1.95 ± 0.95 — a 21.8% average OOD error reduction.

• Design choices are robust. More probes, more candidates, and a larger pool all help, with diminishing returns beyond the defaults p = 5, m = 128, n = 4. Probe selection (uniform, random, low, high) and matching norm (L1, L2, L∞) show no significant differences by two-sided Wilcoxon signed-rank tests, except that uniform probes beat low-only probes — so probes should not be restricted to low-scoring models.

• BestRand wins most when construction data are scarce. With only five construction models it performs best; learning-based methods close the gap as they accumulate hundreds or thousands of model records, but BestRand stays comparable even then.

• Theoretical assumption checks hold as approximations. The Gaussian approximation requires min{k, N−k} to be large, and the probe-regression assumption requires positive explained variance R²; the authors report empirical checks across benchmarks in the appendix, presenting these as useful approximations rather than exact descriptions.

Methodology in Plain English

The authors start by fixing a matrix of scores: N benchmark items by M models. They consider drawing a subset of k items uniformly without replacement and use the subset mean as the estimate of the full mean. All randomness comes from that draw. They then ask what the distribution of the average absolute error across models looks like.

Their key move is to decompose the error into a "common shift" — whether the subset happened to be easier or harder than the benchmark on average — plus model-specific deviations. The common shift has a standard deviation s that depends on three things: how small the subset is relative to the benchmark (through c(k)), how much item difficulty varies (σ), and how correlated the models' errors are (ρ). They assume a simple correlation structure (equal variances, a single average pairwise correlation ρ) and a probe regression in which item difficulty is predicted from a few cheap probe models' scores with explained variance R².

From this they prove that the error vector is approximately multivariate normal, that the average absolute error is at least the absolute common shift, and therefore that the probability of exceeding any threshold t is bounded below by 2Φ(−t/s). A second result shows the mode of the MAE distribution sits very close to the lower endpoint y₀ for large M. Together these explain both the high-probability success and the rare failure. A third result shows that the common shift splits into a probe-explained part and a residual part with variances R²s² and (1−R²)s², so matching the probe means controls the explained part directly.

BestRand operationalizes this in four steps: (1) draw a pool of min(nk, N) items and score p probe models on it; (2) compute the pool's average probe vector H as a reference; (3) draw m candidate k-subsets from the pool and compute each one's probe mean and L2 distance to H; (4) return the closest candidate and evaluate all target models on that subset only. Because the candidate draws reuse cached probe scores, they add no model calls and run as a single batched GPU operation. The pool reference lets probes avoid a full-benchmark pass when nk < N.

Experiments strictly separate construction models (five per benchmark) from test models, so compression must transfer to unseen models. Baselines are Random, SparseEval (linear and MLP predictors), Anchor Points, TinyBenchmarks, and ZipBench. Random and BestRand are run with 10,000 seeds, other methods with three. MAE is the primary metric, with Spearman rank correlation reported in the appendix.

Why This Matters

Impact on research. The paper reframes benchmark compression from "find smarter item representations" to "understand and control the error distribution." It supplies a closed-form, checkable prediction of compression error as a function of subset size, item-difficulty variance, and inter-model correlation — quantities anyone can estimate from a small pilot. The finding that instability is rooted in model similarity, and persists as more models are added, argues against the intuition that broader model panels stabilize subset estimates, and it gives a quantitative basis for choosing subset size against an accuracy target.

Real-world applications:

• Cheap regression testing for model releases, where a small curated subset must reliably rank models without running the full suite.
• Leaderboard and evaluation-hub maintenance, where hundreds of models must be scored under a fixed compute budget and a single bad subset can misplace a model.
• Agent and multimodal evaluation, where per-item cost is highest (browsing, tool use, long documents) and the 51.3% construction-cost reduction is most valuable.
• Autonomous-driving and robotics (VLA) evaluation, where the paper demonstrates that the same probe-matching ideas extend to Bench2Drive and Fail2Drive style settings.

Industry relevance. The method is deliberately cheap to deploy: five probe models, a pool of four times the target size, and 128 candidate subsets computed as one batched tensor operation. It needs no learned estimator, no embedding model, and no full-benchmark responses — the practical bottleneck for teams that cannot afford to re-run every historical model. Its advantage is largest exactly where industry teams sit: few construction models available.

Future Directions

• Handling high-correlation regimes more aggressively. The theory bounds what probe matching can remove (the residual (1−R²)s² remains), so the question is what design could attack the unexplained common shift without expensive full-benchmark responses.
• Adaptive budget allocation. Since c(k) and s predict the error scale, a natural next step is choosing subset size and pool multiplier per benchmark automatically to hit a target error, rather than fixing p = 5, m = 128, n = 4 across all 70 benchmarks.
• Extending to multi-metric and VLA settings at scale. The paper reports multi-metric analysis and two VLA benchmarks in the appendix; scaling the approach to jointly optimize several metrics, and to longer-horizon embodied evaluation, remains open.
• Theory beyond the simplified correlation assumption. The analysis assumes equal variances and a single average pairwise correlation ρ across all models; relaxing this to structured, family-specific correlation (and checking how the Gaussian approximation degrades for small min{k, N−k}) is a clear theoretical next step.

Target Audience

Researchers and engineers working on LLM/VLM evaluation infrastructure, benchmark design, and leaderboard operations; practitioners who need to cut evaluation cost without losing ranking fidelity; and theoretically inclined readers interested in finite-population sampling arguments applied to model benchmarking. The method section is accessible to a general ML audience, while the theorem statements and appendix proofs are aimed at readers comfortable with normal approximations and covariance decompositions.

Authors’ abstract

Benchmark compression reduces the often prohibitive time and cost of model evaluation by evaluating models on a small benchmark subset that closely matches full-benchmark results. To quantify estimation error, we derive an accurate analytical approximation to the error distribution when estimating full-benchmark scores from a subset, showing that most subsets yield small errors, while a few produce much larger errors, resulting in a long-tailed distribution. This means random sampling alone can achieve surprisingly strong performance with high probability, but remains unstable due to rare large errors. We further show that this instability is inherent to modern foundation models and persists even as more models are evaluated. Based on these findings, we introduce BestRand, a stable and low-cost benchmark compression method that preserves the efficiency of random sampling while substantially reducing its high-error tail. We validate BestRand on 70+ text, multimodal, and agent benchmarks, and further extend it to VLA evaluation. Compared with competitive methods, BestRand reduces high-error risk by 50.2% and estimation error by 16.4% on average, while requiring only 51.3% of the construction cost. It further reduces OOD estimation error by 21.8% on average across score-range, model-family, and temporal shifts. Together, our theory provides practical guidance for understanding and predicting the accuracy and reliability of benchmark compression, while BestRand enables stable and accurate compression at low cost. The code and data are publicly available onhttps://github.com/George-Ling3/BestRand.