One-sentence Summary

Researchers from Bosch Research and Carnegie Mellon University introduce BestRand, a stable and low-cost benchmark compression method grounded in an analytical approximation showing long-tailed subset estimation errors, which preserves the efficiency of random sampling while reducing high-error risk by 50.2%, estimation error by 16.4%, and out-of-distribution error by 21.8% across more than 70 text, multimodal, agent, and VLA benchmarks at only 51.3% of the construction cost.

Key Contributions

• An analytical approximation is derived for the error distribution of benchmark compression, showing that subset-based estimates follow a long-tailed distribution where most subsets yield small errors but rare subsets produce large errors, and that this instability arises from similarity among foundation models.
• BestRand is proposed as a stable and low-cost benchmark compression method that generates multiple random subsets and uses a few probe models to select the best candidate, preserving random sampling efficiency while reducing the high-error tail.
• Experiments on 70+ text, multimodal, and agent benchmarks and VLA evaluation show that 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 of competitive methods, and further reduces out-of-distribution estimation error by 21.8% across score-range, model-family, and temporal shifts.

Introduction

Evaluating large language models and vision-language models on benchmarks can be costly because benchmarks often contain many or redundant examples, making benchmark compression valuable for approximating full results from small subsets. Prior work lacked a precise characterization of how accurate and reliable these approximations are, and random sampling, while often effective, remains unstable because of rare large errors driven by similarity among foundation models. The authors derive an analytical approximation to the error distribution for benchmark compression, explaining both the high-probability effectiveness and the tail instability of random subsets. They also introduce BestRand, a probe-guided random selection method that reduces high-error risk and estimation error at low construction cost, with validation across 70+ text, multimodal, agent, and vision-language-action benchmarks.

Method

The authors observe that while random sampling is highly efficient for benchmark compression, it suffers from instability due to a long tail of high error rates. This instability is fundamentally rooted in the behavioral correlation among foundation models, which share similar backbones and training corpora. To formalize this, the authors model the estimation error vector as approximately following a zero mean multivariate normal distribution. The primary source of large errors is identified as the common shift, which measures whether a sampled subset is globally easier or harder than the full benchmark.

As shown in the figure below:

The theoretical analysis demonstrates that the variance of this common shift scales with the behavioral correlation. Consequently, even as the number of evaluated models increases, the shared errors do not average out, leaving a non vanishing risk of high error draws. This insight establishes the core objective for the proposed method: to preserve the low computational cost of random sampling while actively mitigating the risk of selecting subsets with large common shifts.

To achieve stable and low cost benchmark compression, the authors introduce BestRand. The core mechanism leverages a small set of cheap probe models to evaluate and select the most representative candidate subset from a larger pool. The procedure operates in four distinct steps.

First, the algorithm draws a pool of items uniformly without replacement from the full benchmark. It then evaluates the probe models exclusively on this pool, recording the probe scores for each item. Second, it computes a reference vector representing the average probe score across the entire pool. This pool mean serves as a proxy for the full benchmark mean, eliminating the need to run probes on all items.

Third, the method generates multiple candidate subsets of the target size by drawing uniformly without replacement from the pool. For each candidate, it calculates the average probe score and measures the imbalance, defined as the squared distance $d_j = \|h_j - H\|^2$dj​=∥hj​−H∥2 between the candidate mean and the pool reference. Finally, BestRand selects the candidate subset that minimizes this imbalance and evaluates all target models solely on this chosen subset.

The effectiveness of this design is grounded in the orthogonal decomposition of the common shift. The authors prove that the common shift can be split into a probe explained component and a residual component. By selecting the candidate that best matches the reference probe mean, BestRand directly minimizes the probe explained component of the common shift variance.

Because the candidate search reuses the cached probe scores from the initial pool pass, the computational overhead is minimal. The search process itself can be executed as a single batched tensor operation, making the selection virtually instantaneous. The pool size controls the accuracy of the reference approximation, while the number of candidates controls the search quality.

As shown in the figure below:

By targeting the probe explained variance, the method successfully suppresses the upper tail of the error distribution. The empirical results confirm that BestRand concentrates the mean absolute error near zero and significantly reduces the probability of high error outcomes compared to standard random sampling, thereby delivering a highly stable and efficient compression pipeline.

Experiment

BestRand is evaluated on 70 text, multimodal, and agent benchmarks across retention ratios from 2% to 50%, compared with random sampling and learning or clustering baselines using mean absolute error and high-error risk. The main experiments show that probe-guided candidate selection improves accuracy and stability over random sampling while requiring less construction data. Ablations indicate that performance improves with more probes, candidates, and pool size but with diminishing returns, that BestRand remains competitive or better with limited construction models and under score-range, model-family, and temporal shifts, and that it is robust to probe selection and matching norm. Overall, the results support BestRand as a low-cost, stable benchmark compression method with better accuracy-cost trade-offs than existing approaches.

For the text benchmark group, ZipBench and TinyBenchmarks are the strongest listed methods, with mean errors that fall substantially as retention ratio increases. Anchor Points also improves with larger retention ratios but remains less accurate, while SparseEval predictors stay comparatively high-error and variable across budgets. ZipBench and TinyBenchmarks achieve the lowest average errors among the listed methods on text benchmarks, with ZipBench leading overall and at most retention ratios. Higher retention ratios reduce error most clearly for Anchor Points, TinyBenchmarks, and ZipBench, whereas SparseEval methods remain relatively flat and higher-error across budgets.

BestRand achieves the lowest average error across all evaluated out-of-distribution shifts, including score-range, model-family, and temporal changes. In contrast, methods that fit historical performance records perform worse than Random under these shifts. BestRand attains the lowest error in every OOD setting: middle-to-tails, low-to-high, high-to-low, held-out families, and past-to-future shifts. Learning-based methods that use historical performance records underperform Random across all tested distribution shifts. BestRand reduces average OOD error by 21.8% relative to competitive baselines.

The text benchmark evaluation compares prediction methods across retention ratios, showing that ZipBench and TinyBenchmarks achieve the lowest errors and improve most as retention increases, while Anchor Points improves but stays less accurate and SparseEval remains flat and high-error. In out-of-distribution tests covering score-range, model-family, and temporal shifts, BestRand consistently attains the lowest error in every setting, whereas methods that fit historical performance records underperform Random across all shifts, with BestRand reducing average OOD error substantially relative to competitive baselines.