Efficiently evaluate algorithms designed by large language models
AdaEva: Accelerating LLM-Driven Algorithm Design with Adaptive Partial Evaluation
Machine LearningNeural and Evolutionary Computing
Summary
Evaluating many candidate algorithms created by large language models (LLMs) can be very slow because each one is tested on all training examples. The authors introduce AdaEva, a method that tests candidates progressively on growing subsets of examples and quickly drops those that look bad. This lets the process spend less time on weak algorithms without needing any changes to the existing setup or prior knowledge about problem difficulty. AdaEva showed better efficiency and reliability in various algorithm design tasks compared to fixed evaluation approaches.
What this means in practice
- •For machine learning engineers: Speed up automated algorithm tuning systems by adaptively testing candidates on fewer examples.
- •For optimization software developers: Integrate adaptive candidate evaluation to improve search efficiency in combinatorial and continuous problem solvers.
Authors
Tai Nguyen, Fei Liu, Phong Le, Carola Doerr, Nguyen Dang
Abstract
Large Language Models (LLMs) are increasingly used for automated algorithm design. However the computational cost of evaluating the generated algorithms can be excessive. We consider the common LLM-driven automated algorithm design (LLM4AD) setting in which a candidate algorithm is evaluated by aggregating its performance over a shared set of training instances. This instance-wise structure raises a natural question: must every candidate be evaluated on the entire instance set before deciding whether it remains competitive? Taking inspiration from algorithm configuration, we introduce AdaEva, a drop-in adaptive partial-evaluation framework that progressively evaluates candidates on larger subsets of the same instance pool and eliminates unpromising candidates as evidence accumulates. Importantly, AdaEva leaves the underlying LLM4AD procedure and per-instance evaluator unchanged and requires no prior knowledge about instance difficulty. We instantiate this idea using successive halving (AdaEva-S) and statistical racing (AdaEva-R), and evaluate both mechanisms across three representative LLM4AD frameworks, multiple LLM backbones, and optimization domains spanning combinatorial and continuous black-box optimization. Under matched evaluation budgets, AdaEva more reliably balances evaluation effort across candidates than fixed partial-evaluation strategies, yielding strong search efficiency and anytime performance together with improved held-out generalization across the evaluated settings.