DGA$_2$D: Directed Graph-Guided Automated Algorithm Design with Large Language Models
Proposes DGA₂D, a directed graph-guided framework for automated algorithm design, reducing normalized gaps by up to 10.96 percentage points across 12 COPs.
Key Findings
Methodology
DGA₂D models the algorithm space as a directed graph where nodes are operators and edges define connections. The LLM performs three actions: editing operator code, rearranging connections, and selecting implementations. A path-dependent credit mechanism evaluates contributions based on topology. Iteratively, the framework refines both structure and code, guided by performance feedback. Experiments across 12 diverse COP problems show that DGA₂D reduces normalized gaps by up to 10.96 percentage points, outperforming existing LLM-based methods.
Key Results
- In FJSP, TSP, MIS, and 3D-CLP, DGA₂D consistently outperforms baselines, with the largest gap reduction of 10.96 percentage points. It demonstrates strong cross-domain generalization and robustness.
- Compared to traditional heuristics and semi-autonomous methods, DGA₂D's flexible structure and credit-guided optimization lead to faster convergence and higher solution quality.
- Ablation studies confirm that the directed graph structure significantly improves performance over linear or DAG structures, especially in complex scheduling and graph problems.
Significance
This work advances automated algorithm design by integrating directed graph structures and path-dependent credit evaluation, enabling the system to generate complex, high-quality algorithms autonomously. It addresses longstanding challenges of reliability, search space size, and credit assignment, making automated, system-level solutions feasible. The framework's scalability and adaptability promise broad impact in industrial scheduling, routing, and resource allocation, pushing the frontier of AI-driven optimization.
Technical Contribution
The core innovation lies in representing algorithms as directed graphs, allowing cyclic and complex structures, combined with a path-dependent credit mechanism that finely evaluates contributions. The LLM-driven three-step process (edit, rearrange, select) facilitates flexible, multi-operator optimization. The dual-level evolution, guided by credit feedback, enhances both structure and implementation, resulting in superior performance over state-of-the-art methods. The approach provides theoretical guarantees of structural flexibility and practical improvements in solution quality.
Novelty
This is the first work to embed algorithmic structures within a directed graph framework for automated design, coupled with a path-dependent credit mechanism. Unlike prior template-based or isolated module approaches, it enables end-to-end, system-level optimization of complex algorithms, representing a significant paradigm shift in AI-driven heuristic development.
Limitations
- The method relies heavily on frequent LLM calls, which incurs high computational costs, especially for large-scale problems or real-time applications.
- The credit mechanism, while detailed, may be sensitive to noise or inaccuracies in performance evaluation, affecting stability in highly complex or noisy environments.
- Generalization to highly heterogeneous or unseen problem domains remains challenging, requiring further research into adaptive and robust credit evaluation strategies.
Future Work
Future directions include integrating reinforcement learning and meta-learning to improve credit robustness and generalization, exploring multi-modal data fusion for richer algorithm representations, and deploying the framework in real-world industrial settings to validate practical benefits. Additionally, efforts will focus on reducing computational overhead and enhancing scalability for large problem instances.
AI Executive Summary
The rapid evolution of large language models (LLMs) has opened new horizons for automated heuristic design (AHD), especially in tackling NP-hard combinatorial optimization problems (COPs). Traditional approaches rely heavily on human-crafted heuristics and static templates, which are labor-intensive and lack scalability. Recent advances leverage LLMs to generate heuristics and algorithms automatically, but these methods often operate within rigid frameworks, limiting their ability to produce complex, system-level solutions.
This paper introduces DGA₂D, a novel framework that models the open-ended algorithm space as a directed graph. Each node represents a functional operator, with multiple candidate implementations, and edges define the connections forming complete algorithms. The LLM guides this process through three core actions: editing operator code, rearranging the graph topology, and selecting optimal implementations. A path-dependent credit mechanism evaluates the contribution of each code variation based on its topological context, enabling fine-grained, performance-driven optimization.
Extensive experiments across 12 diverse COP problems—including scheduling, routing, and graph optimization—demonstrate that DGA₂D consistently outperforms existing LLM-based methods. It reduces the normalized solution gap by up to 10.96 percentage points, with notable improvements in convergence speed and solution quality. The framework's flexibility allows it to adapt across problem domains, showcasing its potential as a universal tool for automated algorithm design.
The significance of this work lies in its ability to generate complex, high-performance algorithms autonomously, addressing key limitations of prior methods such as low reliability and limited structural expressiveness. By integrating a directed graph structure with a path-dependent credit system, DGA₂D offers a scalable, robust, and versatile approach that could revolutionize automated heuristic development in both academia and industry.
Looking ahead, future research will focus on enhancing the efficiency of the framework, improving its generalization to unseen problems, and deploying it in real-world industrial scenarios. This work marks a substantial step toward fully autonomous, system-level algorithm synthesis driven by AI, promising to accelerate innovation in combinatorial optimization and beyond.
Deep Dive
Key Concepts
Directed Graph (有向图)
一种图结构，用于表示算法中操作符的连接关系，支持复杂结构和循环，增强表达能力。
Path-dependent Credit (路径依赖信用)
根据算法路径的拓扑结构动态评估操作符和连接的贡献，指导优化过程。
Algorithm Pipeline (算法管道)
由操作符按序连接形成的完整算法流程，作为搜索和优化的基本单元。
LLM (大语言模型)
预训练的深度学习模型，具备自然语言理解和代码生成能力，用于驱动算法结构和代码优化。
信用分配机制
根据性能反馈，为操作符和连接赋予信用值，指导后续的结构和实现优化。
Open Questions Unanswered questions from this research
- 1 如何进一步降低大规模复杂问题的计算成本，提升信用机制在高噪声环境中的鲁棒性，以及实现更强的跨域泛化能力。
Abstract
The rapid development of Large Language Models (LLMs) has opened new avenues for Automated Heuristic Design (AHD) for solving NP-hard combinatorial optimization problems (COPs). However, existing LLM-driven AHD methods are largely confined to rigid solver templates, relegating the search process to isolated module tuning. Transitioning to fully autonomous, system-level algorithm design is essential but fraught with low reliability of generated operators, extremely large search spaces, and ineffective credit assignment. To overcome these drawbacks, this paper proposes a Directed Graph-Guided Automated Algorithm Design framework, termed DGA$_2$D. It structures the open-ended program space as a directed graph, where each node represents a functional operator that can be instantiated using one of multiple candidate code implementations, while directed walks constitute complete algorithmic pipelines. A first-order path-dependent credit assignment mechanism is introduced to evaluate code variations strictly based on their topological context. Extensive experiments across 12 distinct COPs, ranging from complex scheduling to routing, demonstrate the consistent empirical advantages of DGA$_2$D. It reduces the average normalized gap by up to 10.96 percentage points compared to state-of-the-art LLM baselines.