00 / ADAPTIVE PARTIAL EVALUATION FOR LLM4AD
Exhaustive benchmark evaluation consumes over 90% of compute in LLM-driven algorithm design. AdaEva is a drop-in evaluation layer that eliminates unpromising candidates early—saving 50–80% compute and exploring up to 4.4x more algorithms without modifying generators or prompts.
1 
University of St Andrews, UK
2 
Sorbonne Université, 
CNRS, 
LIP6, France
3 
University of Zurich & 
ETH Zurich, Switzerland
01 / The Core Problem
Large Language Models (LLMs) are great at creating candidate algorithms (LLM4AD), but exhaustive evaluation across massive instance pools creates an excessive computational bottleneck—often consuming the vast majority of optimization time.
"Must every candidate algorithm be evaluated on the entire instance set before deciding whether it remains competitive?"
On benchmarks with high instance agreement like Online Bin Packing, testing heuristics on just 5 instances reliably eliminates clearly inferior candidates, saving over 70% of evaluation compute without discarding competitive contenders.
On complex problem landscapes where performance varies widely across instances, rigid evaluation shortcuts (like Fixed-1 or Fixed-50%) cause catastrophic misranking. Adaptive statistical racing is necessary to scale evaluation depth dynamically.
02 / The Solution
AdaEva operates purely as an evaluation layer for evolutionary algorithm design. It leaves candidate generation, prompting, evolutionary operators, and per-instance evaluators completely unchanged. Instead of wasting uniform compute on clearly inferior candidates, AdaEva progressively evaluates heuristics across expanding instance subsets, eliminating unpromising candidates early and concentrating resources on competitive contenders.
Progressively allocates geometrically increasing evaluation budgets to exponentially smaller sets of promising candidates across scheduled elimination rounds.
Accumulates per-instance evaluation evidence and eliminates uncompetitive heuristics dynamically as soon as non-parametric statistical tests prove they cannot win.
03 / Key Findings & Performance Highlights
Under matched budgets, fixed partial strategies (Fixed-1, Fixed-50%) fail to maintain robust performance across changing landscapes. AdaEva maintains strong search efficiency and ranking consistency.
AdaEva consistently discovers heuristics that rank best or near-best on unseen, out-of-distribution instances across shifted problem scales, capacities, TSPLIB, and Taillard benchmarks.
Full-pool evaluation buys precision on single candidates at the cost of a severely shortened search horizon. AdaEva dynamically finds the sweet spot—evaluating many candidates shallowly and few deeply.
Held-out generalization mean rank · 0–6 axis (lower is better)
Table 2 · Mean held-out generalization ranks across five budget checkpoints (20% to 100%) and 5 random seeds. Lower rank indicates superior performance on held-out test instances. Full Pool is the default in existing LLM4AD frameworks.
| Evaluation Strategy | Avg Rank | FSSP (Taillard) | OBP | TSP (TSPLIB) | BBOB (24 Funcs) |
|---|
Mean ranks computed across held-out instance groups, then averaged across checkpoints. ± denotes cross-seed standard deviation. FSSP: Flow Shop Scheduling. OBP: Online Bin Packing. TSP: Traveling Salesperson. BBOB: Black-Box Optimization.
AdaEva-R achieves the best mean rank in 8 out of 14 framework–benchmark–LLM settings and ranks among the top two in 13. Full-pool evaluation, the standard in prior work, is the worst or second-worst strategy in almost every setting because it wastes budget on unpromising candidates.
04 / Broad Applicability
AdaEva functions as a general, drop-in evaluation layer across diverse search paradigms, model architectures, and problem landscapes without modifying underlying search workflows.
Build on this work
@article{nguyen2026adaeva,
title = {AdaEva: Accelerating LLM-Driven Algorithm Design with Adaptive Partial Evaluation},
author = {Nguyen, Tai and Liu, Fei and Le, Phong and Doerr, Carola and Dang, Nguyen},
journal = {arXiv preprint arXiv:2610.03896},
year = {2026},
url = {https://arxiv.org/abs/2610.03896}
}