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

arXiv: https://arxiv.org/abs/2501.15081 · HTML: https://mlsanity.com/paper/2501.15081/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 83 references that are in the map.
- First posted on arXiv 25 Jan 2025.

## Builds on (most cited first, 30 of 38)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [A Survey of Large Language Models](https://mlsanity.com/paper/2303.18223/) (2023)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [LLM Lies: Hallucinations are not Bugs, but Features as Adversarial Examples](https://mlsanity.com/paper/2310.01469/) (2023)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [Evolution through Large Models](https://mlsanity.com/paper/2206.08896/) (2022)
- [Large Language Models as Evolutionary Optimizers](https://mlsanity.com/paper/2310.19046/) (2023)
- [Language Model Crossover: Variation through Few-Shot Prompting](https://mlsanity.com/paper/2302.12170/) (2023)
- [Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap](https://mlsanity.com/paper/2401.10034/) (2024)
- [Automated Repair of Programs from Large Language Models](https://mlsanity.com/paper/2205.10583/) (2022)
- [Parsel: Algorithmic Reasoning with Language Models by Composing Decompositions](https://mlsanity.com/paper/2212.10561/) (2022)
- [Large Language Models As Evolution Strategies](https://mlsanity.com/paper/2402.18381/) (2024)
- [Algorithm Evolution Using Large Language Model](https://mlsanity.com/paper/2311.15249/) (2023)
- [Do LLMs Know about Hallucination? An Empirical Investigation of LLM's Hidden States](https://mlsanity.com/paper/2402.09733/) (2024)
- [Large Language Model-Based Evolutionary Optimizer: Reasoning with elitism](https://mlsanity.com/paper/2403.02054/) (2024)
- [The Importance of Directional Feedback for LLM-based Optimizers](https://mlsanity.com/paper/2405.16434/) (2024)
- [When Large Language Models Meet Evolutionary Algorithms: Potential Enhancements and Challenges](https://mlsanity.com/paper/2401.10510/) (2024)
- [LLM Guided Evolution -- The Automation of Models Advancing Models](https://mlsanity.com/paper/2403.11446/) (2024)
- [Large Language Models as Surrogate Models in Evolutionary Algorithms: A Preliminary Study](https://mlsanity.com/paper/2406.10675/) (2024)
- [Exploring the True Potential: Evaluating the Black-box Optimization Capability of Large Language Models](https://mlsanity.com/paper/2404.06290/) (2024)
- [SPELL: Semantic Prompt Evolution based on a LLM](https://mlsanity.com/paper/2310.01260/) (2023)
- [GA Based Q-Attack on Community Detection](https://mlsanity.com/paper/1811.00430/) (2018)
- [Enhancing Genetic Improvement Mutations Using Large Language Models](https://mlsanity.com/paper/2310.19813/) (2023)
- [Deep Insights into Automated Optimization with Large Language Models and Evolutionary Algorithms](https://mlsanity.com/paper/2410.20848/) (2024)

## Built on by (most cited first, 3 of 3)

- [A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving](https://mlsanity.com/paper/2509.08269/) (2025)
- [DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization](https://mlsanity.com/paper/2601.06502/) (2026)
- [Structure-Aware Cooperative Ensemble Evolutionary Optimization on Combinatorial Problems with Multimodal Large Language Models](https://mlsanity.com/paper/2510.21906/) (2025)

## Abstract (arXiv)

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.