EvoSpeak: Large Language Models for Interpretable Genetic Programming-Evolved Heuristics

Meng Xu, Jiao Liu, Yew Soon OngarXiv 2025 · arXiv · OpenReview

TL;DR

This paper introduces EvoSpeak, a novel framework that combines Genetic Programming (GP) with Large Language Models (LLMs) to create more interpretable, efficient, and adaptable heuristics for complex optimization problems. EvoSpeak leverages LLMs to extract knowledge from existing heuristics, generate better starting points for GP, and translate complex evolved rules into human-readable explanations, significantly improving usability and trust.

What Problem Does This Paper Address?

Genetic Programming (GP) is excellent at evolving complex, tree-structured heuristics for optimization tasks. However, these evolved heuristics often become so intricate that they are difficult for humans to understand (hindering interpretability), slow down the optimization process, and are hard to transfer to new, related problems. This complexity limits their practical adoption, especially in high-stakes domains where transparency and adaptability are crucial. The paper aims to bridge this gap by integrating the symbolic reasoning power of GP with the natural language understanding and generation capabilities of LLMs.

Methods

EvoSpeak is a novel framework that integrates LLMs into the GP workflow in an offline manner, avoiding the computational bottleneck of frequent LLM calls during evolution. The core components are:

  • Knowledge Extraction and Population Initialization: LLMs analyze a set of existing high-quality GP heuristics to extract underlying principles and patterns. This knowledge, combined with user-defined preferences, is used to generate a "warm-start" initial population for GP. This seeded population is more likely to contain effective heuristics, accelerating convergence.
  • Heuristic Evolution: Standard GP then evolves the population, but starting from a much better initial set, leading to faster and more efficient discovery of high-performing heuristics.
  • Interpretability Enhancement: After GP has evolved the final best heuristic, it's passed back to the LLM. The LLM translates the complex symbolic tree structure into a clear, natural-language explanation, detailing the heuristic's decision logic.
  • Knowledge Transfer: The framework also supports transferring knowledge across different but related tasks. LLMs can adapt knowledge learned from one problem domain to bootstrap the evolution process on a new one.

Datasets

The experiments were conducted using the Dynamic Flexible Job Shop Scheduling (DFJSS) simulation model. This model is described as a well-established and challenging benchmark for evaluating scheduling heuristics. The paper details its setup, including job characteristics, machine processing times, transportation delays, and various performance measures (tardiness, flowtime, weighted tardiness). The experiments involved training on 50 instances and testing on 30 unseen instances for each scenario.

Key Insights and Ideas

  • LLMs as "Heuristic Translators" and "Knowledge Miners": The most significant insight is the dual role of LLMs: not just generating text, but actively extracting latent knowledge from complex symbolic structures and translating them into human-understandable language. This moves beyond simple rule generation to a deeper understanding and communication of heuristic logic.
  • Offline LLM Integration for Scalability: By performing LLM tasks before and after the GP evolution loop, EvoSpeak avoids the prohibitive computational cost of real-time LLM queries, making the approach scalable to complex problems.
  • Warm-Starting GP Accelerates Convergence: A well-seeded initial population from LLM-derived knowledge significantly speeds up the evolutionary process and leads to better final solutions, especially for tasks closely related to the knowledge source.
  • Interpretability is a Feature, Not a Bug: EvoSpeak demonstrates that interpretability can be actively generated and enhanced, rather than just being a byproduct of simpler heuristics. This is crucial for building trust in AI-driven decision-making.
  • Generalization Beyond Single Tasks: The framework shows promise for transferring learned heuristic knowledge across different problem instances and even related tasks, paving the way for more continuous and adaptive learning systems.

Key Results

  • Improved Performance: EvoSpeak significantly outperformed standard GP in 3 out of 6 single-objective scenarios, particularly for mean-based objectives (mean flowtime, mean weighted tardiness). Across all scenarios, EvoSpeak consistently showed lower standard deviation, indicating greater performance stability.
  • Faster Convergence: The LLM-initialized populations led to quicker convergence in evolutionary runs.
  • Adaptability to User Preferences: In multi-objective scenarios, EvoSpeak demonstrated strong adaptability to different user-defined preference weights, often outperforming or matching methods trained under the same preference.
  • Enhanced Interpretability: The LLM successfully translated complex GP trees into structured, human-readable explanations, which were qualitatively assessed as clear and useful.
  • Higher Population Diversity: EvoSpeak maintained significantly higher phenotypic diversity throughout the evolutionary process compared to baseline GP, suggesting better exploration and reduced risk of premature convergence.

Limitations and Future Work

  • LLM Output Quality Dependency: The paper acknowledges that EvoSpeak's performance is dependent on the quality of the LLM's outputs, which could introduce biases or inaccuracies. However, they anticipate this will improve with LLM advancements.
  • Generalizability to Other Domains: While DFJSS is a complex benchmark, the authors suggest future work to extend EvoSpeak to other combinatorial and continuous optimization domains (e.g., vehicle routing, production planning, inventory management) to validate its generality.
  • Interactive Interfaces: The authors propose developing interactive LLM-powered interfaces to allow practitioners to guide heuristic generation and interpretation dynamically.
  • Real-World Applications: Applying EvoSpeak to large-scale, real-world problems like supply chain networks or financial portfolio optimization is suggested to further demonstrate its practical impact.

Summary updated

Abstract

Genetic programming (GP) has demonstrated strong effectiveness in evolving tree-structured heuristics for complex optimization problems. Yet, in dynamic and large-scale scenarios, the most effective heuristics are often highly complex, hindering interpretability, slowing convergence, and limiting transferability across tasks. To address these challenges, we present EvoSpeak, a novel framework that integrates GP with large language models (LLMs) to enhance the efficiency, transparency, and adaptability of heuristic evolution. EvoSpeak learns from high-quality GP heuristics, extracts knowledge, and leverages this knowledge to (i) generate warm-start populations that accelerate convergence, (ii) translate opaque GP trees into concise natural-language explanations that foster interpretability and trust, and (iii) enable knowledge transfer and preference-aware heuristic generation across related tasks. We verify the effectiveness of EvoSpeak through extensive experiments on dynamic flexible job shop scheduling (DFJSS), under both single- and multi-objective formulations. The results demonstrate that EvoSpeak produces more effective heuristics, improves evolutionary efficiency, and delivers human-readable reports that enhance usability. By coupling the symbolic reasoning power of GP with the interpretative and generative strengths of LLMs, EvoSpeak advances the development of intelligent, transparent, and user-aligned heuristics for real-world optimization problems.
BibTeX
@misc{xu2025evospeak,
  author = {Meng Xu and Jiao Liu and Yew Soon Ong},
  title = {{EvoSpeak: Large Language Models for Interpretable Genetic Programming-Evolved Heuristics}},
  year = {2025},
  eprint = {2510.02686},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.02686},
}
Figure