Can Large Language Models Be Trusted as Evolutionary Optimizers for Network-Structured Combinatorial Problems?

• URL: http://arxiv.org/abs/2501.15081v3
• Date: Sat, 26 Jul 2025 01:17:55 GMT
• Title: Can Large Language Models Be Trusted as Evolutionary Optimizers for Network-Structured Combinatorial Problems?
• Authors: Jie Zhao, Tao Wen, Kang Hao Cheong,
• Abstract summary: Large Language Models (LLMs) have shown strong capabilities in language understanding and reasoning across diverse domains.<n>In this work, we propose a systematic framework to evaluate the capability of LLMs to engage with problem structures.<n>We adopt the commonly used evolutionary (EVO) and propose a comprehensive evaluation framework that rigorously assesses the output fidelity of LLM-based operators.
• Score: 8.082897040940447
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Language Models (LLMs) have shown strong capabilities in language understanding and reasoning across diverse domains. Recently, there has been increasing interest in utilizing LLMs not merely as assistants in optimization tasks, but as primary optimizers, particularly for network-structured combinatorial problems. However, before LLMs can be reliably deployed in this role, a fundamental question must be addressed: Can LLMs iteratively manipulate solutions that consistently adhere to problem constraints? In this work, we propose a systematic framework to evaluate the capability of LLMs to engage with problem structures. Rather than treating the model as a black-box generator, we adopt the commonly used evolutionary optimizer (EVO) and propose a comprehensive evaluation framework that rigorously assesses the output fidelity of LLM-based operators across different stages of the evolutionary process. To enhance robustness, we introduce a hybrid error-correction mechanism that mitigates uncertainty in LLMs outputs. Moreover, we explore a cost-efficient population-level optimization strategy that significantly improves efficiency compared to traditional individual-level approaches. Extensive experiments on a representative node-level combinatorial network optimization task demonstrate the effectiveness, adaptability, and inherent limitations of LLM-based EVO. Our findings present perspectives on integrating LLMs into evolutionary computation and discuss paths that may support scalable and context-aware optimization in networked systems.

Related papers

• Discrete Tokenization for Multimodal LLMs: A Comprehensive Survey [69.45421620616486]
  This work presents the first structured taxonomy and analysis of discrete tokenization methods designed for large language models (LLMs)<n>We categorize 8 representative VQ variants that span classical and modern paradigms and analyze their algorithmic principles, training dynamics, and integration challenges with LLM pipelines.<n>We identify key challenges including codebook collapse, unstable gradient estimation, and modality-specific encoding constraints.
  arXiv  Detail & Related papers  (2025-07-21T10:52:14Z)
• Large Language Models for Design Structure Matrix Optimization [4.513609458468522]
  In complex engineering systems, the interdependencies among components or development activities are often modeled and analyzed using Design Structure Matrix (DSM)<n>Reorganizing elements within a DSM to minimize feedback loops and enhance modularity or process efficiency constitutes a challenging optimization problem in engineering design and operations.<n>In this study, we explore the potential of Large Language Models (LLMs) for helping solve such CO problems by leveraging their capabilities for advanced reasoning and contextual understanding.
  arXiv  Detail & Related papers  (2025-06-11T13:53:35Z)
• Heterogeneous Group-Based Reinforcement Learning for LLM-based Multi-Agent Systems [25.882461853973897]
  We propose Multi-Agent Heterogeneous Group Policy Optimization (MHGPO), which guides policy updates by estimating relative reward advantages.<n>MHGPO eliminates the need for Critic networks, enhancing stability and reducing computational overhead.<n>We also introduce three group rollout sampling strategies that trade off between efficiency and effectiveness.
  arXiv  Detail & Related papers  (2025-06-03T10:17:19Z)
• Visual Evolutionary Optimization on Combinatorial Problems with Multimodal Large Language Models: A Case Study of Influence Maximization [7.890526174400841]
  Graph-structured problems in complex networks are prevalent in many domains, and are computationally demanding.<n>Traditional evolutionary algorithms (EAs) often face obstacles due to content-shallow encoding limitations and lack of structural awareness.<n>We introduce an original framework, Visual Evolutionary Optimization (VEO), leveraging multimodal large language models (MLLMs) as the evolutionary backbone.
  arXiv  Detail & Related papers  (2025-05-11T05:23:02Z)
• Make Optimization Once and for All with Fine-grained Guidance [78.14885351827232]
  Learning to Optimize (L2O) enhances optimization efficiency with integrated neural networks. L2O paradigms achieve great outcomes, e.g., refitting, generating unseen solutions iteratively or directly. Our analyses explore general framework for learning optimization, called Diff-L2O, focusing on augmenting solutions from a wider view.
  arXiv  Detail & Related papers  (2025-03-14T14:48:12Z)
• COSMOS: A Hybrid Adaptive Optimizer for Memory-Efficient Training of LLMs [81.01082659623552]
  Large Language Models (LLMs) have demonstrated remarkable success across various domains. Their optimization remains a significant challenge due to the complex and high-dimensional loss landscapes they inhabit.
  arXiv  Detail & Related papers  (2025-02-24T18:42:19Z)
• Are Language Models Up to Sequential Optimization Problems? From Evaluation to a Hegelian-Inspired Enhancement [0.0]
  Large Language Models (LLMs) have demonstrated impressive capabilities across numerous fields.<n>This paper explores the proficiency of LLMs in handling Sequential Optimization Problems (SOPs)<n>We introduce WorldGen, a dynamic framework for generating unseen SOPs with controllable complexities.<n>Inspired by the influential framework of Hegelian Dialectics, we propose ACE, demonstrating how the performance of LLMs in SOP contexts can be significantly improved.
  arXiv  Detail & Related papers  (2025-02-04T18:47:31Z)
• An LLM-Empowered Adaptive Evolutionary Algorithm For Multi-Component Deep Learning Systems [17.78934802009711]
  Multi-objective evolutionary algorithms (MOEAs) are widely used for searching optimal solutions in complex multi-component applications. This paper proposes $mu$MOEA, the first adaptive evolutionary search algorithm to detect safety violations in MCDL systems. Experimental results show that $mu$MOEA can significantly improve the efficiency and diversity of the evolutionary search.
  arXiv  Detail & Related papers  (2025-01-01T13:19:58Z)
• Optima: Optimizing Effectiveness and Efficiency for LLM-Based Multi-Agent System [75.25394449773052]
  Large Language Model (LLM) based multi-agent systems (MAS) show remarkable potential in collaborative problem-solving. Yet they still face critical challenges: low communication efficiency, poor scalability, and a lack of effective parameter-updating optimization methods. We present Optima, a novel framework that addresses these issues by significantly enhancing both communication efficiency and task effectiveness.
  arXiv  Detail & Related papers  (2024-10-10T17:00:06Z)
• FactorLLM: Factorizing Knowledge via Mixture of Experts for Large Language Models [50.331708897857574]
  We introduce FactorLLM, a novel approach that decomposes well-trained dense FFNs into sparse sub-networks without requiring any further modifications. FactorLLM achieves comparable performance to the source model securing up to 85% model performance while obtaining over a 30% increase in inference speed.
  arXiv  Detail & Related papers  (2024-08-15T16:45:16Z)
• Large Language Model as a Catalyst: A Paradigm Shift in Base Station Siting Optimization [62.16747639440893]
  Large language models (LLMs) and their associated technologies advance, particularly in the realms of prompt engineering and agent engineering.<n>Our proposed framework incorporates retrieval-augmented generation (RAG) to enhance the system's ability to acquire domain-specific knowledge and generate solutions.
  arXiv  Detail & Related papers  (2024-08-07T08:43:32Z)
• Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning [53.6472920229013]
  Large Language Models (LLMs) have demonstrated impressive capability in many natural language tasks. LLMs are prone to produce errors, hallucinations and inconsistent statements when performing multi-step reasoning. We introduce Q*, a framework for guiding LLMs decoding process with deliberative planning.
  arXiv  Detail & Related papers  (2024-06-20T13:08:09Z)
• LLM as a Complementary Optimizer to Gradient Descent: A Case Study in Prompt Tuning [69.95292905263393]
  We show that gradient-based and high-level LLMs can effectively collaborate a combined optimization framework.<n>In this paper, we show that these complementary to each other and can effectively collaborate a combined optimization framework.
  arXiv  Detail & Related papers  (2024-05-30T06:24:14Z)
• Towards Efficient LLM Grounding for Embodied Multi-Agent Collaboration [70.09561665520043]
  We propose a novel framework for multi-agent collaboration that introduces Reinforced Advantage feedback (ReAd) for efficient self-refinement of plans. We provide theoretical analysis by extending advantage-weighted regression in reinforcement learning to multi-agent systems. Experiments on Over-AI and a difficult variant of RoCoBench show that ReAd surpasses baselines in success rate, and also significantly decreases the interaction steps of agents.
  arXiv  Detail & Related papers  (2024-05-23T08:33:19Z)
• Large Language Model-Aided Evolutionary Search for Constrained Multiobjective Optimization [15.476478159958416]
  We employ a large language model (LLM) to enhance evolutionary search for solving constrained multi-objective optimization problems. Our aim is to speed up the convergence of the evolutionary population.
  arXiv  Detail & Related papers  (2024-05-09T13:44:04Z)
• Exploring the True Potential: Evaluating the Black-box Optimization Capability of Large Language Models [32.859634302766146]
  Large language models (LLMs) have demonstrated exceptional performance in natural language processing tasks. This paper endeavors to offer deep insights into the potential of LLMs in optimization. Our findings reveal both the limitations and advantages of LLMs in optimization.
  arXiv  Detail & Related papers  (2024-04-09T13:17:28Z)
• Large Language Model-Based Evolutionary Optimizer: Reasoning with elitism [1.1463861912335864]
  Large Language Models (LLMs) have demonstrated remarkable reasoning abilities. This paper asserts that LLMs possess the capability for zero-shot optimization across diverse scenarios. We introduce a novel population-based method for numerical optimization using LLMs.
  arXiv  Detail & Related papers  (2024-03-04T13:57:37Z)
• Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark [166.40879020706151]
  This paper proposes a shift towards BP-free, zeroth-order (ZO) optimization as a solution for reducing memory costs during fine-tuning. Unlike traditional ZO-SGD methods, our work expands the exploration to a wider array of ZO optimization techniques. Our study unveils previously overlooked optimization principles, highlighting the importance of task alignment, the role of the forward gradient method, and the balance between algorithm complexity and fine-tuning performance.
  arXiv  Detail & Related papers  (2024-02-18T14:08:48Z)
• Are Large Language Models Good Prompt Optimizers? [65.48910201816223]
  We conduct a study to uncover the actual mechanism of LLM-based Prompt Optimization. Our findings reveal that the LLMs struggle to identify the true causes of errors during reflection, tending to be biased by their own prior knowledge. We introduce a new "Automatic Behavior Optimization" paradigm, which directly optimize the target model's behavior in a more controllable manner.
  arXiv  Detail & Related papers  (2024-02-03T09:48:54Z)
• Large Language Models as Evolutionary Optimizers [37.92671242584431]
  We present the first study on large language models (LLMs) as evolutionarys. The main advantage is that it requires minimal domain knowledge and human efforts, as well as no additional training of the model. We also study the effectiveness of the self-adaptation mechanism in evolutionary search.
  arXiv  Detail & Related papers  (2023-10-29T15:44:52Z)
• Large Language Models as Optimizers [106.52386531624532]
  We propose Optimization by PROmpting (OPRO), a simple and effective approach to leverage large language models (LLMs) as prompts. In each optimization step, the LLM generates new solutions from the prompt that contains previously generated solutions with their values. We demonstrate that the best prompts optimized by OPRO outperform human-designed prompts by up to 8% on GSM8K, and by up to 50% on Big-Bench Hard tasks.
  arXiv  Detail & Related papers  (2023-09-07T00:07:15Z)

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.