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

Random Is Almost Enough? Stable and Low-Cost Benchmark Compression via BestRand. By George Ling and five others, from Bosch Research and Carnegie Mellon University. Published on the thirty-first of October.

Evaluating a model on a full benchmark is often prohibitively slow and expensive. Benchmark compression cuts that cost by evaluating on a small subset chosen so that its results closely match the full benchmark. The question this work starts from is how much error such a subset introduces, and how that error is distributed across the subsets one might pick. A compressed benchmark is only useful if its estimate can be trusted, and an average error says little about how bad the worst draw can be.

The authors derive an accurate analytical approximation to the error distribution when full-benchmark scores are estimated from a subset. Its shape is long-tailed. Most subsets yield small errors, and a few produce much larger ones. That cuts both ways. Random sampling alone can perform surprisingly well with high probability, yet it stays unstable, because now and then it lands in the tail. The authors further show that this instability is inherent to modern foundation models and persists even as more models are evaluated, so it does not simply wash out with scale.

BestRand is built on that diagnosis. It keeps the efficiency of random sampling while substantially reducing its high-error tail, aiming to be both stable and cheap to construct. The abstract does not spell out the construction step by step; what it fixes is the target. Random sampling is already good most of the time, so the job is not to beat it on typical subsets but to stop it landing in the rare bad ones. BestRand is validated on more than seventy text, multimodal and agent benchmarks, and further extended to VLA evaluation.

Compared with competitive methods, BestRand reduces high-error risk by fifty point two percent and estimation error by sixteen point four percent on average. It does so at only fifty-one point three percent of the construction cost. The first of those numbers is the one the method was designed around: the high-error tail that made plain random sampling risky shrinks by roughly half, and accuracy and construction cost improve along with it.

Under distribution shift the gains hold. Across shifts in score range, in model family, and over time, BestRand reduces out-of-distribution estimation error by twenty-one point eight percent on average. Those three shifts mirror how a compressed benchmark gets used: it is expected to keep scoring models that differ in strength, in lineage, and in when they were released.

The title's question gets a qualified yes. Random is almost enough, and the theory explains both halves of that phrase: why a random subset usually works, and why it occasionally fails badly. The theory is offered as practical guidance for predicting how accurate and reliable a compressed benchmark will be, and BestRand is the part that closes the remaining gap at low cost.