Dual-Surrogate Method Guides LLMs to Better Heuristic Search
Two surrogates predict the best parent and operator before each LLM query.
Large language models (LLMs) have made automated heuristic design (AHD) more practical by generating executable heuristic code from task descriptions and evaluator feedback. However, under limited query and evaluation budgets, search efficiency hinges on a critical pre-generation decision: which archived heuristics to reuse as parents and which generation operator should transform them. Existing methods rely on predefined rules that only indirectly model the expected outcome of each operator-parent action. To address this, researchers from Sun Yat-sen University and related institutions propose Dual-Surrogate, a surrogate-guided action-selection module that scores pre-generation actions with two complementary models.
The transition surrogate predicts the latent distribution of the child representation induced by an operator-parent action, while an instance-conditioned utility surrogate estimates the expected performance of sampled child latents. An uncertainty-aware acquisition rule combines predicted utility, utility uncertainty, and transition uncertainty to select the next LLM generation action. Across a diverse heuristic-design suite, Dual-Surrogate is competitive with strong LLM-AHD baselines, and ablation analyses show its behavior goes beyond simple archive ranking or fixed operator preferences.
- Dual-Surrogate uses two surrogate models: a transition surrogate (predicts child representation distribution) and a utility surrogate (estimates child performance).
- An uncertainty-aware acquisition rule balances predicted utility, utility uncertainty, and transition uncertainty to select the next LLM action.
- The method outperforms existing LLM-AHD baselines across diverse heuristic-design tasks, without relying on predefined rules.
Why It Matters
Makes LLM-driven automated heuristic design more sample-efficient, crucial for optimization under tight query budgets.