DGA$_2$D: Directed Graph-Guided Automated Algorithm Design with Large Language Models

• URL: http://arxiv.org/abs/2608.00700v1
• Date: Sat, 01 Aug 2026 14:59:38 GMT
• Title: DGA$_2$D: Directed Graph-Guided Automated Algorithm Design with Large Language Models
• Abstract summary: This paper proposes a Directed Graph-Guided Automated Design framework, DGA$D.<n>It structures the open-ended program space as a directed graph, where each node represents a functional operator that can be instantiated.<n>It reduces the average normalized gap by up to 10.96 percentage points compared to state-of-the-art LLM baselines.
• Score: 1.8062322656999443
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Unifying Temporal and Structural Credit Assignment in LLM-Based Multi-Agent Prompt Optimization [10.37712840622514]
  Multi-Agent Systems (MAS) empower Large Language Models to tackle complex reasoning computation tasks.<n>Existing black-boxs struggle to attribute trajectory-level failure to specific local components.<n>We argue that tractable MAS optimization needs structural inductive biases to disentangle error signals.
  arXiv  Detail & Related papers  (2026-05-28T16:57:57Z)
• FrontierOR: Benchmarking LLMs' Capacity for Efficient Algorithm Design in Large-Scale Optimization [61.43300970020897]
  Large language models (LLMs) are increasingly used for optimization modeling and solver-code generation.<n>Existing benchmarks are limited to small or simplified examples far below real-world scale and complexity.<n>We introduce FrontierOR, among the first benchmarks to evaluate LLM-based efficient algorithm design for realistic large-scale optimization problems.
  arXiv  Detail & Related papers  (2026-05-24T20:10:42Z)
• HMACE: Heterogeneous Multi-Agent Collaborative Evolution for Combinatorial Optimization [19.90781293176099]
  HMACE is a Heterogeneous Multi-Agent Collaborative Evolution framework.<n>It decomposes each evolutionary generation into an autonomous, role-specialized loop with four coordinated agents.<n>It guides the search toward diverse and promising behaviors while avoiding redundant evaluations.
  arXiv  Detail & Related papers  (2026-05-08T04:02:28Z)
• A2DEPT: Large Language Model-Driven Automated Algorithm Design via Evolutionary Program Trees [8.49373236378493]
  Large Language Model (LLM)-based Automated Heuristic Design (AHD) has shown promise in autonomously generating components with minimal human intervention.<n>To enable open-ended solver beyond rigid templates, we propose Automated Evolutionary Program Trees (A2DEPT)<n>A2DEPT explores the vast program space via a tree-structured evolutionary search with hybrid selection and hierarchical operators, enabling iterative refinement of complete algorithms.
  arXiv  Detail & Related papers  (2026-04-27T05:07:10Z)
• BEAM: Bi-level Memory-adaptive Algorithmic Evolution for LLM-Powered Heuristic Design [49.50107918295052]
  Large Language Model-based Hyper Heuristic (LHH) has recently emerged as an efficient way for automatic design.<n>We propose textbfBEAM (Bi-level Memory-adaptive Algorithmic Evolution) to address this problem.<n>We show that BEAM significantly outperforms existing LHHs, notably reducing the optimality gap by 37.84% on aggregate.
  arXiv  Detail & Related papers  (2026-04-14T15:46:47Z)
• Dynamic Generation of Multi-LLM Agents Communication Topologies with Graph Diffusion Models [99.85131798240808]
  We introduce a novel generative framework called textitGuided Topology Diffusion (GTD)<n>Inspired by conditional discrete graph diffusion models, GTD formulates topology synthesis as an iterative construction process.<n>At each step, the generation is steered by a lightweight proxy model that predicts multi-objective rewards.<n>Experiments show that GTD can generate highly task-adaptive, sparse, and efficient communication topologies.
  arXiv  Detail & Related papers  (2025-10-09T05:28:28Z)
• LLM4CMO: Large Language Model-aided Algorithm Design for Constrained Multiobjective Optimization [54.35609820607923]
  Large language models (LLMs) offer new opportunities for assisting with algorithm design.<n>We propose LLM4CMO, a novel CMOEA based on a dual-population, two-stage framework.<n>LLMs can serve as efficient co-designers in the development of complex evolutionary optimization algorithms.
  arXiv  Detail & Related papers  (2025-08-16T02:00:57Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization.<n>We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution.<n>Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. We propose a gradient coordinate coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes.
  arXiv  Detail & Related papers  (2022-06-06T09:25:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.