Paper review · November 7, 2026
Is Random Almost Enough? Stable, Low-Cost Benchmark Compression with BestRand
Random Is Almost Enough? Stable and Low-Cost Benchmark Compression via BestRand
The authors develop a theory that errors in estimating benchmark scores from subsets follow a long-tailed distribution. Their method, BestRand, uses probe models to choose the best subset among several random candidates and halves the risk of large errors.
Problem
Benchmark compression reduces evaluation cost by estimating the full score from a small subset. However, it was not well known how accurate and reliable these estimates are. Random sampling is usually accurate but sometimes produces large errors, which makes it unstable.
Method
The authors derive an analytical approximation of the distribution of subset estimation errors. They show that the error is long-tailed, that the risk of large errors grows as the behavioral correlation between models (ρ) increases, and that this risk does not go away when more models are evaluated. Based on this, they propose BestRand. It randomly samples an item pool and scores it once with a few probe models. It then picks, from several random candidate subsets, the one whose mean probe score is closest to the pool mean. The candidate search only averages cached scores, so no extra model calls are needed.
Results
- The authors report that, compared with competing methods, it reduced large-error risk by 50.2% and estimation error by 16.4% on average, at 51.3% of the construction cost.
- Across 44 text benchmarks, mean MAE was 2.92%, lower than Random (3.47%), ZipBench (3.23%) and TinyBenchmarks (3.65%).
- Mean MAE was 5.43% across 10 agent benchmarks (Random 6.14%) and 2.87% across 16 multimodal benchmarks (Random 3.24%).
- Under out-of-distribution (OOD) conditions, such as shifts in score range, model family and time period, the authors report that estimation error fell by 21.8% on average. They also extended the method to VLA evaluation.
Limitations
The theory relies on asymptotic approximations and on simplifying assumptions that model scores have equal variance and a constant pairwise correlation. The authors themselves call it a useful approximation, not an exact description. The residual component that the probes cannot explain (1−R²) cannot be reduced. Suitable probe models are also required.
Why it matters
As evaluating large models becomes more expensive, adding one lightweight selection step to simple random sampling can greatly improve stability. The theory gives an estimate of how subset size relates to expected error, so it can also help plan evaluation budgets.
Key terms
- Benchmark compression
- A way to estimate a model's full benchmark score by evaluating it on a representative subset instead of the whole benchmark.
- Common shift
- An error component that arises when the chosen subset is on average easier or harder than the full set, so all model scores shift in the same direction.
- Probe model
- A cheap reference model that is run only once on a small item pool to judge how representative candidate subsets are.
- MAE P95
- The 95th percentile of mean absolute error over many samplings. It shows the risk of rare, large errors.
Original
Authors: George Ling, Shanshan Zhong, Lijin Yang, Hao Yang, Nanxiang Li, Zhongzhan Huang · Posted 2026-10-31 · License arXiv 비독점 배포 라이선스 · Based on the full text
This review is an AI-written summary of the paper. Please treat the original paper as the reference.