Random Is Almost Enough? Stable and Low-Cost Benchmark Compression via BestRand
George Ling, Shanshan Zhong, Lijin Yang, Hao Yang, Nanxiang Li, Zhongzhan Huang
cs.CL
2026-10-31
BestRand picks a random subset using five probe models. On 70+ benchmarks it cuts estimation error 16.4% and high-error risk 50.2%, at 51.3% of typical construction cost.
A full benchmark pass is slow. Compression scores a small subset and treats that average as the full-benchmark score. The missing piece is how stable the estimate is: how far a typical random draw lands, and how far the bad draws go.
The mode of MAE, the average absolute error across models, sits near the small-error end, and the right tail is long. The tail is the common shift. When the subset is easier or harder than the full set, every model's estimate moves together, the way a hard exam drops the whole class. The scale s of that shift grows with ρ, the average correlation of model errors. Foundation models share backbones and training data, and distillation pulls their behavior into line, so they pass and fail the same items. In Figure 1 every estimated ρ is positive: minimum 0.07, median 0.33, mean 0.35. As the number of models goes to infinity, s stays proportional to √ρ. It does not vanish.
Random sampling is accurate on most draws. The open problem is the long tail.
There are N items and M models. A model's error is its subset mean minus its full-set mean. The subset is drawn uniformly without replacement.
Item difficulty is that item's average score across models. The common shift is the gap between subset difficulty and full-set difficulty. Theorem 1 lower-bounds the tail: the chance that MAE exceeds t is at least the chance that the common shift exceeds t, about 2Φ(-t/s). Under equicorrelation, s rises with ρ and with shorter subsets. Extra models remove only the (1-ρ)/M term. For large M the mode approaches the lower end of the distribution, with a relative gap of about 0.578/√M.
BestRand still draws subsets at random. It only keeps the candidate whose common shift looks smallest.
The probe pass costs five times the pool size and is paid once. The 128 comparisons reuse cached vectors and add no model calls.
Theorem 3 says matching the probe mean shrinks the part of the common shift that the probes can explain, without knowing the regression weights and without running the target models. The variance contraction is a limit as reference error goes to zero. A finite pool does not get that guarantee.
At 20% retention, more probes, more candidates, and a larger pool all lower MAE, and the last two flatten quickly. The default is 5, 128, and 4. L1, L2, and L∞ land at 1.715%, 1.713%, and 1.714%, with no significant difference. Uniform, random, and high-score probes are close. Low-score probes are worse than uniform sampling (p<0.001), moving MAE from 1.703% to 1.756%.
The main test has 70 benchmarks: 44 text, 16 multimodal, 10 agent. Retention runs from 2% to 50% in six steps. Each benchmark uses five construction models and a disjoint test set. Random and BestRand use 10,000 seeds; the other methods use three. Entries below are MAE in percentage points, averaged over the six ratios:
| Method | Text | Multimodal | Agent |
| SparseEval (Linear) | 20.98 | 23.25 | 22.70 |
| SparseEval (MLP) | 11.87 | 13.67 | 11.74 |
| Anchor Points | 6.52 | 6.53 | 8.26 |
| TinyBenchmarks | 3.65 | 3.40 | 6.27 |
| ZipBench | 3.23 | 3.19 | 6.01 |
| Random | 3.47 | 3.24 | 6.14 |
| BestRand | 2.92 | 2.87 | 5.43 |
Random already sits with ZipBench and TinyBenchmarks. Clustering plus IRT does not beat uniform sampling. BestRand has the lowest group average in all three groups. Against those three baselines it lowers MAE by 16.4% and the chance of landing in the high-error region by 50.2%. That region is defined two ways: above Random's 70th percentile, and above Random's mean. BestRand is lowest on both, for text, multimodal, and agent benchmarks. On text its cross-benchmark standard deviation is 2.80 against a mean of 2.92, so benchmarks differ by more than the methods do.
On text at 20% retention, MAE is 1.73 for BestRand, 2.11 for Random, 2.02 for ZipBench, 2.26 for TinyBenchmarks, and 11.74 for SparseEval MLP. Figure 2 marks P95 drops of 57% on HellaSwag, 47% on TruthfulQA, 45% on OCRBench, 37% on MMMU-Pro, 43% on ACEBench, and 36% on BFCL. One cell goes the other way: multimodal at 2% retention, ZipBench 6.10 versus BestRand 6.16.
Construction cost is observed model-item scores divided by the number of items. One means a full pass of one model. Probes see only the pool, so BestRand uses 8.0% as much construction data as a full-record method at 2% retention, and 51.3% averaged over the six ratios. On 12 text benchmarks, learned methods need cost at least 1. BestRand is already usable below 1.
BestRand has the lowest MAE in all five out-of-distribution settings. Averaging the three shift types with equal weight gives 1.69 for BestRand, 1.95 for Random, 2.19 for ZipBench, and 2.36 for TinyBenchmarks, 21.8% below those three. The five settings are middle-score models tested on the tails, low to high, high to low, held-out families, and older models tested on newer ones. Predictors fit on historical scores lose to Random in every setting.
On CommonsenseQA, OCRBench, and Bench2Drive, the theoretical and empirical modes differ by 1.4%, 0.7%, and 0.7%. ρ predicts the P95 of MAE with R²=0.938. The common-shift scale s does so with R²=0.993.
When only a few models have full scores, BestRand is a better default than training a subset-to-full predictor. Once the subset is fixed, a new model's estimate is its subset average. On 12 text benchmarks, giving the learned methods hundreds or up to 1,000 construction models lets them catch up, and BestRand stays in the same band.
On average error it only tightens Random. The useful part is fewer subsets that shift every model at once. Spearman rank correlation among the strong methods is already high, so a leaderboard that only needs order may not move.
A finite pool leaves reference error, and the variance contraction is not a finite-sample guarantee. Equicorrelation is an approximation. The normal approximation needs min(k, N-k) to be large. AIME has 60 items, Terminal-Bench 89, and tau-bench 165. At 2% retention the subset can be one or two items, outside the theorem. Those small sets are averaged in with MMLU, which has over ten thousand items. Agent MAE averages 5.43 with a standard deviation of 5.44.
Random and BestRand use 10,000 draws. The other methods use three seeds, so 50.2% is not estimated at a matched budget. On six benchmarks with ten seeds per ratio, combining worse-than-average and worst-30% rates, BestRand is still 68.06% below Random, ZipBench, and TinyBenchmarks.
Shared backbones and corpora explain why ρ stays high. The paper does not regress overlap onto ρ. Multi-metric benchmarks contribute one metric in the main table. VLA numbers are not in that table. BestRand cannot start with no historical scores. What it saves is a full probe pass.