Towards Optimal Evaluation Efficiency for Large Language Models

Guohong Li, Deyi XiongEMNLP 2025

TL;DR

Evaluating large language models (LLMs) is computationally expensive. This paper proposes an efficient evaluation framework that intelligently selects a subset of questions from a benchmark to reduce costs while maintaining reliability. Their combinatorial optimization approach outperforms existing methods in balancing evaluation efficiency and accuracy.

What Problem Does This Paper Address?

The rapid advancement of Large Language Models (LLMs) has led to impressive capabilities, but comprehensively evaluating them is a significant challenge. Standard evaluation benchmarks, like MMLU and GSM8K, require vast amounts of data and computational resources, making them costly and time-consuming. This cost barrier hinders rapid iteration and widespread evaluation of new LLM developments. Existing methods for reducing evaluation costs, such as clustering-based subset selection, often rely on heuristics and may not optimally balance efficiency with the reliability of the evaluation results. The paper aims to bridge this gap by developing a more principled and efficient approach to LLM evaluation.

Methods

The core of the paper's contribution lies in framing the question subset selection problem as a combinatorial optimization task. Instead of relying on heuristic clustering, they directly optimize an objective function that quantifies the difference between the evaluation results of the full benchmark and the selected subset.

Key methods include:

  • Objective Function: They define a loss function, $Q(S, S', L)$, which measures the L2 norm of the difference between the overall evaluation vectors of the full question set ($S$) and the selected subset ($S'$). Minimizing this function maximizes the reliability of predicting full evaluation scores.
  • Optimization Algorithms: To solve this combinatorial optimization problem, they employ two main strategies:
  • Optimal Random Sampling: This involves multiple rounds of random sampling, selecting the subset that yields the minimum objective function value.
  • Simulated Annealing: This metaheuristic algorithm starts with a random subset and iteratively perturbs it. New solutions are accepted based on their quality and a "temperature" parameter that decreases over time, allowing for exploration of the solution space while gradually converging to an optimal subset.
  • Semantic Analysis: To ensure the selected subsets preserve the original benchmark's semantic information, they use Wasserstein distance and Sentence-BERT embeddings followed by PCA dimensionality reduction for visualization.

Datasets

The paper evaluates their proposed framework on several widely-used LLM benchmarks:

  • MMLU (Massive Multitask Language Understanding): A comprehensive benchmark covering a wide range of subjects.
  • GSM8K (Grade School Math 8K): A dataset of grade school math problems.
  • HellaSwag: A benchmark for common sense reasoning.

These datasets were chosen because they have abundant pre-tested model results available, which is crucial for their evaluation framework that leverages existing data.

Key Insights and Ideas

  • Optimization over Heuristics: Directly formulating subset selection as an optimization problem, rather than relying on clustering heuristics, leads to more reliable and efficient evaluations.
  • Trade-off Between Efficiency and Reliability: The paper demonstrates that it's possible to achieve significant cost reductions (higher compression rates) without a proportional loss in evaluation reliability, as measured by the L2 norm of score differences.
  • Semantic Preservation Matters: While optimizing for evaluation accuracy is key, preserving the semantic distribution of the original benchmark is also important. The paper shows a correlation between semantic preservation and evaluation accuracy.
  • Method-Specific Strengths: Different optimization methods have varying strengths. For instance, random sampling can be stable but sensitive to seeds, while simulated annealing offers a more systematic exploration.

Key Results

  • Improved Reliability: The proposed combinatorial optimization methods (optimal random sampling and simulated annealing) consistently achieved lower error metrics (L2 norm of difference) compared to pure random sampling and clustering-based methods across various compression rates and benchmarks.
  • Efficiency Gains: The framework allows for significant reduction in the number of questions needed for evaluation (e.g., subsets as small as 19% of the original dataset were tested) while maintaining high reliability.
  • Semantic Preservation: The Wasserstein distances indicate that while random sampling might preserve semantics slightly better in some cases, the optimization methods still maintain a good balance, demonstrating that semantic fidelity can be achieved alongside efficiency. Figure 1 visually supports the claim that their "anneal" method (simulated annealing) achieves better accuracy-vs-true-accuracy alignment than "sample" or "pca" at a low compression rate.

Limitations and Future Work

  • Correlation Not Absolute: The paper acknowledges that the correlation between semantic retention and evaluation accuracy is not absolute. The simulated annealing method, for example, slightly underperforms random sampling in semantic retention, suggesting that for tasks demanding extremely high semantic fidelity, their approach might need further refinement.
  • Future Directions:
    • Refining the Objective Function: Exploring different evaluation criteria and subset requirements to enhance the generalizability of the combinatorial optimization approach.
  • Combined Optimization and Semantic Analysis: Investigating methods that jointly optimize for evaluation accuracy and semantic information.
  • Exploring Other Optimization Techniques: Potentially applying other advanced optimization algorithms.

Summary updated

BibTeX
@inproceedings{li2025towards,
  author = {Guohong Li and Deyi Xiong},
  title = {{Towards Optimal Evaluation Efficiency for Large Language Models}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure