Random Is Almost Enough: BestRand Cuts High-Error Risk by 50.2%

Evaluation cost is becoming the line item nobody wants to audit. Models ship weekly, while benchmarks pack thousands of items; running MMLU or OSWorld end to end eats serious time and compute. So the industry leans on benchmark compression: draw a small subset of k items from N, and estimate the full-benchmark score from the subset average. The basic question, though, has stayed open: how accurate is that estimate — and is plain random sampling good enough?

Why random sampling is "almost enough"

The paper closes the theory gap first. The Hugging Face paper page carries a Carnegie Mellon University org badge; first author George Ling, together with Shanshan Zhong and four co-authors, derives an analytical approximation to the error distribution of subset-based estimates. In one sentence: most subsets give small errors, a few give much larger ones — the distribution is long-tailed. As the number of evaluated models M grows, the mode of the MAE distribution approaches the lower endpoint at a universal rate of C0/√M with C0≈0.578. Random subsets land in the low-error region with high probability; "almost enough" is a theorem, not a slogan. Numerical experiments, the authors report, closely track the theoretical predictions.

The tail comes from model homogeneity

The real problem is not the average error but the tail: occasionally you draw a batch of items that is systematically harder or easier, and every model's score moves together. The paper calls this the common shift; its scale grows with the behavioral correlation ρ across models — and ρ is exactly what foundation-model homogeneity produces: similar or identical backbones, overlapping training corpora, and distillation aligning behavior further. The sharpest result: for fixed ρ>0, even as the number of evaluated models goes to infinity, this variance component converges to c(k)σ√ρ>0. Averaging over more models cannot wash out shared errors. The more alike we train our models, the harder the ceiling on sampling-based evaluation.

BestRand: five probe models to dodge unlucky subsets

The method is disarmingly simple. Draw a candidate pool of min(4k,N) items; score 5 probe models on that pool only; generate 128 random candidate subsets of size k from the pool; pick the subset whose mean probe-score vector is closest in squared L2 distance to the pool mean, and evaluate target models on that subset alone. Random probe selection and L2 matching are the defaults. All 128 candidates reuse the same cached probe scores, so selection is a single batched tensor operation — the paper's computational resources statement notes that subset selection runs on CPU in under 0.1 seconds with parallel execution, and all compression experiments fit on a single GPU. There is a theoretical guarantee too: with sufficiently accurate probe matching, the common-shift variance converges to a level strictly below random sampling. Versus response-based methods that need large archives of past evaluations, the only construction overhead is one small probe pass.

Numbers and boundaries

The evaluation spans 70 benchmarks — 44 text, 16 multimodal, 10 agent — from MMLU, GSM8K, and HumanEval to MMMU, MathVista, and MME, to OSWorld and tau-bench; six retention ratios from 2% to 50%; six representative baselines including Random, SparseEval, Anchor Points, TinyBenchmarks, and ZipBench, with 10,000 seeds each for Random and BestRand versus three for the others. Against three strong baselines (Random, ZipBench, TinyBenchmarks), BestRand cuts average MAE by 16.4%; with high error defined as exceeding Random's 70th percentile or mean, it cuts high-error probability by 50.2%; construction records average 51.3% of data-dependent baselines (down to 8.0% at 2% retention); under score-range, model-family, and temporal shifts, OOD estimation error drops by another 21.8% on average, and the method extends to VLA evaluation. The limitations section stays honest: compression cannot guarantee zero estimation error, full-benchmark runs are still recommended for final evaluations, and probe inference cost is nonzero — just small.

Code is open-sourced under MIT, and the GitHub repo bundles roughly 86 MiB of BestRand-Data: full prompts and model-item score matrices for 12 benchmarks including GPQA, BBH, TruthfulQA, HellaSwag, IFEval, MMLU-Pro, MMLU, MuSR, and WinoGrande; fixed splits of 5 construction models plus 20 held-out test models; reproducible with NumPy and SciPy on CPU alone.

So what

The quiet contribution here is quantifying model homogeneity: when every model fails on the same items, even statistical averaging cannot save you. Next time a "lite" leaderboard crosses your feed, ask who picked those items and how many models calibrated the pick. If the answer is "just sampled randomly," you now know exactly which tail is waiting.