ParetoEvo: Pareto-Guided Evolutionary Tree Search for Automatic Heuristic Design with LLM Agents

Combinatorial optimization (CO) generally relies on human-designed heuristics to obtain high-quality solutions when exact search is computationally prohibitive. Large language model (LLM)-based automatic heuristic design (AHD) reduces this reliance by iteratively generating, evaluating, and revising executable heuristics. However, evaluating heuristics primarily by average solution quality can overlook execution cost and difficult-instance performance. Moreover, attained objective values do not necessarily reveal a heuristic’s potential for further evolution. To address these limitations, we propose ParetoEvo, a Pareto-guided evolutionary tree-search framework that combines objective trade-offs with evidence of search potential. We develop Pareto-dominance Monte Carlo tree search (PD-MCTS) to allocate evaluations through vector-valued subtree returns over average quality, execution time, and worst-instance quality. To complement descendant-based evidence with earlier indications of search potential, we propose adaptive productivity control (APC) to grant additional expansions when productive creation empirically predicts productive subsequent search. To adapt revisions to search experience, reflection-conditioned Actor and Reflector LLM agents use evaluated transitions to update guidance for subsequent heuristic generation. Experiments across diverse CO tasks demonstrate improvements in solution quality, execution efficiency, and worst-instance performance over LLM-based AHD baselines, alongside faster convergence and higher final Pareto-front quality.