REVIEW 3 major objections 6 minor 2 cited by
Improving Existing Optimization Algorithms with LLMs
T0 review · 3 major / 6 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read An LLM-proposed heuristic that uses CMSA's age parameter outperforms the expert-designed heuristic, with the gap widening on larger and denser graphs.
desk verdict A solid proof-of-concept showing GPT-4o can propose a better construction heuristic for CMSA on MIS, with an honest experimental setup and one protocol-ambiguity soft spot. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the LLM-modified `generate_solution()` function, the probabilistic greedy construction phase of CMSA. In the original, each step selects the minimum-degree feasible vertex with probability equal to the determinism rate and otherwise draws from a candidate list; the age parameter plays no role. The LLM's variant computes for each feasible vertex a composite weight $w(v) = 1/(2 + \mathrm{age}(v)) + 1/(1 + \mathrm{degree}(v))$, normalizes these weights into probabilities, and uses roulette-wheel selection, with the greedy choice replaced by the argmin of the weights under the determinism rate. This is carried by an in-context prompting loop: the researcher shows the full C++ code, asks for a heuristic that uses age, receives code, fixes a division-by-zero bug (age values are initialized to $-1$), and iterates. The machinery also includes an entropy-adjusted variant where each probability is shifted by an entropy term, which the experiments show does not pay off.
What would settle it
Run the identical prompting protocol with the interaction instances explicitly disjoint from the evaluation instances, then compare LLM-CMSA-V1 against standard CMSA on a new set of graphs, for example different sizes, densities, or graph families; if the advantage disappears or reverses outside the reported benchmark distribution, the central claim of a generalizable improvement is falsified.
Extended reading notes
Core claim
The central discovery is that the LLM's new construction heuristic is better than the expert's. Formally, the LLM replaced the rule 'pick the minimum-degree vertex (with a probabilistic candidate list)' with a roulette-wheel selection over weights $w(v) = 1/(2 + \mathrm{age}(v)) + 1/(1 + \mathrm{degree}(v))$, so that vertices with lower age and lower degree are preferred. The age parameter had previously been used only to remove stale components from the subproblem, not to influence which vertices are built into new solutions. With this change, LLM-CMSA-V1 outperforms the original CMSA on Barabási-Albert, Watts-Strogatz, and Erdős-Rényi graphs; LLM-CMSA-V2, which further adds an entropy term to the selection probabilities, also outperforms the original but is worse than V1. The low-level optimized variants are statistically equivalent to their non-optimized counterparts.
Load-bearing premise
The comparison assumes the feedback used to steer the LLM during development was not based on the same benchmark instances used for the final evaluation, so the reported improvement reflects a generalizable heuristic rather than overfitting to the test set.
Editorial extensions
If this is right
- If the claim holds, optimization researchers can treat LLMs as assistants that improve already-implemented algorithms, not only as generators of new ones.
- The age parameter's success in construction suggests that internal CMSA state variables carry information worth exploiting in the heuristic, a lesson that may transfer to other matheuristics.
- The growing advantage on larger and denser graphs implies the LLM-discovered heuristic matters most in hard, high-exploration regimes.
- The entropy adjustment's failure shows that LLM suggestions need empirical validation and are not uniformly beneficial.
- The statistically equivalent performance of the C++-optimized variants indicates that low-level code changes can be adopted for other reasons, such as memory or readability, without sacrificing solution quality.
Reading between the lines
- Editorial inference: the same interactive pattern—show complete code, name an internal parameter, ask for a construction heuristic that uses it—could be applied to other hybrid metaheuristics whose construction phase ignores parameters the solver phase already maintains.
- Editorial inference: the reported gain is trustworthy as a generalizable discovery only if the feedback given to the LLM during revision did not come from the test instances; the paper does not state which instances informed that feedback, so a holdout-style replication is the natural next check.
- Editorial inference: because only one LLM was tested, the result may reflect GPT-4o's specific pretraining exposure to CMSA literature; comparing open-weight models on the same prompts would separate model-capability claims from method claims.
- Editorial inference: testing the same LLM-proposed heuristic on other NP-hard problems solvable by CMSA, such as the minimum dominating set problem, would show whether the age-aware construction idea generalizes or is MIS-specific.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper investigates whether large language models (LLMs) can improve existing optimization algorithms, using the Construct, Merge, Solve & Adapt (CMSA) metaheuristic for the Maximum Independent Set (MIS) problem as a case study. The authors feed the original C++ implementation of CMSA to GPT-4o, which proposes a new heuristic for the solution-construction phase that incorporates CMSA's age parameter. This yields two heuristic variants, LLM-CMSA-V1 and LLM-CMSA-V2 (the latter with an entropy adjustment), plus efficiency-optimized versions. On synthetic Barabási–Albert, Watts–Strogatz, and Erdős–Rényi graph benchmarks with 1,440 test instances, the authors report that the LLM-proposed heuristics outperform the expert-designed degree-based heuristic, with the performance gap widening on larger and denser graphs. Critical-difference plots are used to claim statistical significance. The paper also provides a public website with a chatbot implementing the same prompts for reproducibility.
Significance. If the results hold, this is a valuable proof-of-concept that a general-purpose LLM can understand a complex metaheuristic's source code and propose a nontrivial, effective heuristic variation—something that had not occurred to the algorithm's own designers. The paper's strengths include a clean separation of tuning and test instances for algorithm parameters, the use of critical-difference plots for statistical comparison, and the release of reproducible prompts and a chatbot. The scope is, however, narrow: one algorithm, one problem, and one LLM, as the authors acknowledge. The main methodological gaps—single-run evaluation and undisclosed data used during LLM interaction—currently limit the strength of the headline claim.
major comments (3)
- [Section 4.2] Each of the five algorithms was applied exactly once to each testing instance. Because CMSA's construction phase is stochastic (the determinism rate is below 1), a single run per instance means that the reported differences may be partly due to random seed variation rather than algorithmic superiority. The critical-difference plots in Figure 5 are computed from average ranks of these single runs, with no confidence intervals or repeated-run statistics. The authors should either run each algorithm multiple times per instance (e.g., 10–30 runs) and report mean/median performance, or explicitly justify why a single run is sufficient for these stochastic algorithms. This is load-bearing for the claim that the LLM-generated variants outperform CMSA with statistical significance.
- [Section 3.4 and Figure 3(b)] The iterative refinement loop shows the researcher telling the LLM 'the new heuristic does not generate better solutions than the original heuristic' and later 'Now it works better.' The manuscript never states which benchmark instances were used to generate this performance feedback. If test instances were used, the PERF variants evaluated in Figure 5 would be partially in-sample, and the reported equivalence between PERF and non-PERF variants could be biased. Even though the main V1/V2 heuristics appear to have been proposed before this feedback loop, the paper must explicitly disclose which instances informed every LLM interaction, and ideally restrict any performance-based feedback to the tuning instances. Without this disclosure, the out-of-sample interpretation of the results is not fully established.
- [Section 4.2] The abstract and Section 4.2 state that the LLM-generated variants outperform CMSA 'with growing graph size and density.' This interaction claim is supported only by visual inspection of the box plots in Figure 4. The critical-difference plots aggregate over all graph sizes and densities and provide no test for an interaction effect. Please provide a formal analysis (e.g., stratified significance tests by size/density, or a regression of performance on instance features) or explicitly soften the claim to a descriptive observation rather than a quantitative result.
minor comments (6)
- [Section 3.5] The subsection title 'Reproducility' is a typo; it should be 'Reproducibility.'
- [Section 2.1] 'HUMAN EVAL' should be written as 'HumanEval', which is the standard name of the benchmark.
- [Section 3.3.1, Eq. (1)] The notation is slightly redundant: the normalized probability is denoted P_w(v_j) while the raw weight is w(v). Please clarify in the text that w(v) is the raw weight and P_w is the normalized probability used in roulette-wheel selection.
- [Figure 6(b)] The x-axis label 'Erdos (n2000, 020705)' appears to be a typesetting artifact; it should read 'Erdos (n2000, edge prob.: 0.020705)' for consistency with Figure 4(c).
- [Listing 2 caption] The caption 'Fragment code optimization suggested by LLM' should be 'Fragment of code optimization suggested by the LLM' or similar.
- [Section 3.3.1] The claim that 'this use of the age values never occurred to anyone working on CMSA algorithms' is strong and unverifiable; consider softening it to a statement about the authors' knowledge.
Circularity Check
No significant circularity: the LLM-proposed heuristic is evaluated on separate testing instances, and the paper's claims do not reduce to their inputs.
full rationale
The paper's central claim is empirical: GPT-4o proposed a modified generate_solution() that incorporates CMSA's age parameter, and the resulting LLM-CMSA variants outperform the original CMSA on synthetic benchmarks. No equation defines the proposed heuristic in terms of the measured objective, and no fitted parameter is later renamed as a prediction. The CMSA parameters of all variants were tuned with irace on 48 tuning instances, while the reported comparisons use 1,440 separate testing instances (Section 4.1). The LLM interaction in Section 3.4 and Figure 3(b) includes performance feedback ('the new heuristic does not generate better solutions than the original heuristic'), but the paper does not state that this feedback was computed on the testing instances; absent such a statement, this is a potential data-leakage and correctness risk rather than a demonstrated circular reduction. The authors' self-citations to Blum's CMSA work define the baseline algorithm and are not used as evidence for the improvement; the comparison is self-contained against the provided code. Therefore the derivation chain does not reduce to its inputs, and no circularity is established.
Assumptions & free parameters
free parameters (3)
- CMSA parameters (agemax, na, drate) =
not reported (irace-tuned)
- Heuristic weight constants (2 and 1 in w(v) = 1/(2+age(v)) + 1/(1+degree(v))) =
2, 1
- Time limits (150, 300, 450, 600 CPU seconds) =
150/300/450/600
assumptions (4)
- domain assumption The generated synthetic graphs and the pooling of results in CD plots provide a valid statistical basis for comparing algorithms.
- standard math irace tuning produced appropriate, representative parameter settings for each variant.
- domain assumption The original CMSA implementation is a competent expert baseline.
- domain assumption The LLM's stochastic output, with temperature 0.7, yields a representative heuristic for the given prompts.
Cite this review
Pith. "Pith review of Improving Existing Optimization Algorithms with LLMs." pith.science (2026). https://pith.science/paper/OIGEXHH2
@misc{pith2026250208298,
author = {Pith},
title = {Pith review of: Improving Existing Optimization Algorithms with LLMs},
year = {2026},
howpublished = {\url{https://pith.science/paper/OIGEXHH2}},
note = {Machine review of arXiv:2502.08298}
}
read the original abstract
The integration of Large Language Models (LLMs) into optimization has created a powerful synergy, opening exciting research opportunities. This paper investigates how LLMs can enhance existing optimization algorithms. Using their pre-trained knowledge, we demonstrate their ability to propose innovative heuristic variations and implementation strategies. To evaluate this, we applied a non-trivial optimization algorithm, Construct, Merge, Solve and Adapt (CMSA) -- a hybrid metaheuristic for combinatorial optimization problems that incorporates a heuristic in the solution construction phase. Our results show that an alternative heuristic proposed by GPT-4o outperforms the expert-designed heuristic of CMSA, with the performance gap widening on larger and denser graphs. Project URL: https://imp-opt-algo-llms.surge.sh/
Figures
Figures from the paper (3 more)
Forward citations
Cited by 2 Pith papers
-
EALG: Evolutionary Adversarial Generation of Language Model-Guided Generators for Combinatorial Optimization
EALG uses LLMs in an evolutionary adversarial loop to generate increasingly hard TSP instances and heuristics that beat existing LLM-designed solvers on those instances and on TSPLIB.
-
LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm
An LLM-generated, per-instance bias vector improves a BRKGA on the NP-hard Longest Run Subsequence problem, with statistically significant gains on 15 of 35 instance groups, concentrated on complex instances.
Reference graph
Works this paper leans on
-
[1]
C. Blum. Construct, Merge, Solve & Adapt: A Hybrid Metaheuristic for Combinatorial Optimization. Computa- tional Intelligence Methods and Applications. Springer Nature Switzerland, 2024. ISBN 9783031601026. URL https://books.google.es/books?id=ENCt0AEACAAJ
work page 2024
-
[2]
Christian Blum, Jakob Puchinger, Günther R. Raidl, and Andrea Roli. Hybrid metaheuristics in combina- torial optimization: A survey. Applied Soft Computing , 11(6):4135–4151, 2011. ISSN 1568-4946. doi: https://doi.org/10.1016/j.asoc.2011.02.032. URL https://www.sciencedirect.com/science/article/ pii/S1568494611000962
-
[3]
Christian Blum, Pedro Pinacho, Manuel López-Ibáñez, and José A. Lozano. Construct, merge, solve & adapt a new general algorithm for combinatorial optimization. Computers & Operations Research, 68:75–88, 2016. ISSN 0305-0548. doi: https://doi.org/10.1016/j.cor.2015.10.014. URL https://www.sciencedirect.com/ science/article/pii/S0305054815002452
-
[4]
Improving code generation by training with natural language feedback
Angelica Chen, Jérémy Scheurer, Tomasz Korbak, Jon Ander Campos, Jun Shern Chan, Samuel R Bowman, Kyunghyun Cho, and Ethan Perez. Improving code generation by training with natural language feedback. arXiv [cs.SE], March 2023
work page 2023
-
[5]
A survey on evaluating large language models in code generation tasks, 2024
Liguo Chen, Qi Guo, Hongrui Jia, Zhengran Zeng, Xin Wang, Yijiang Xu, Jian Wu, Yidong Wang, Qing Gao, Jindong Wang, Wei Ye, and Shikun Zhang. A survey on evaluating large language models in code generation tasks, 2024. URL https://arxiv.org/abs/2408.16498
arXiv 2024
-
[6]
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian...
arXiv 2021
-
[7]
Wei-Lin Chiang, Lianmin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos, Tianle Li, Dacheng Li, Hao Zhang, Banghua Zhu, Michael Jordan, Joseph E. Gonzalez, and Ion Stoica. Chatbot arena: An open platform for evaluating llms by human preference, 2024. URL https://arxiv.org/abs/2403.04132
arXiv 2024
-
[8]
Large language models for compiler optimization
Chris Cummins, V olker Seeker, Dejan Grubisic, Mostafa Elhoushi, Youwei Liang, Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Kim Hazelwood, Gabriel Synnaeve, and Hugh Leather. Large language models for compiler optimization. arXiv [cs.PL], September 2023
work page 2023
Show all 38 references
-
[9]
Deepseek-v3 technical report, 2024
DeepSeek-AI et al. Deepseek-v3 technical report, 2024. URL https://arxiv.org/abs/2412.19437
2024 arXiv
-
[10]
A survey on in-context learning, 2024
Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Jingyuan Ma, Rui Li, Heming Xia, Jingjing Xu, Zhiyong Wu, Tianyu Liu, Baobao Chang, Xu Sun, Lei Li, and Zhifang Sui. A survey on in-context learning, 2024. URL https://arxiv.org/abs/2301.00234
2024 arXiv
-
[11]
Evolving code with a large language model, 2024
Erik Hemberg, Stephen Moskal, and Una-May O’Reilly. Evolving code with a large language model, 2024. URL https://arxiv.org/abs/2401.07102
2024 arXiv
-
[12]
A survey on large language models for code generation
Juyong Jiang, Fan Wang, Jiasi Shen, Sungju Kim, and Sunghun Kim. A survey on large language models for code generation. arXiv [cs.CL], June 2024
2024
-
[13]
Self- planning code generation with large language models
Xue Jiang, Yihong Dong, Lecheng Wang, Zheng Fang, Qiwei Shang, Ge Li, Zhi Jin, and Wenpin Jiao. Self- planning code generation with large language models. ACM Trans. Softw. Eng. Methodol., 33(7):1–30, September 2024
2024
-
[14]
A survey on LLM-based code generation for low-resource and domain-specific programming languages
Sathvik Joel, Jie J W Wu, and Fatemeh H Fard. A survey on LLM-based code generation for low-resource and domain-specific programming languages. arXiv [cs.SE], October 2024
2024
-
[15]
Sathvik Joel, Jie JW Wu, and Fatemeh H. Fard. A survey on llm-based code generation for low-resource and domain-specific programming languages, 2024. URL https://arxiv.org/abs/2410.03981
2024
-
[16]
Kamath, K
U. Kamath, K. Keenan, G. Somers, and S. Sorenson. Large Language Models: A Deep Dive: Bridging Theory and Practice. Springer Nature Switzerland, 2024. ISBN 9783031656477. URL https://books.google.es/ books?id=kDobEQAAQBAJ
2024
-
[17]
Unsupervised translation of programming languages
Marie-Anne Lachaux, Baptiste Roziere, Lowik Chanussot, and Guillaume Lample. Unsupervised translation of programming languages. arXiv [cs.CL], June 2020
2020
-
[18]
Large language model-aware in-context learning for code generation
Jia Li, Ge Li, Chongyang Tao, Jia Li, Huangzhao Zhang, Fang Liu, and Zhi Jin. Large language model-aware in-context learning for code generation. arXiv [cs.SE], October 2023
2023
-
[19]
Llm4ad: A platform for algorithm design with large language model, 2024
Fei Liu, Rui Zhang, Zhuoliang Xie, Rui Sun, Kai Li, Xi Lin, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Llm4ad: A platform for algorithm design with large language model, 2024. URL https://arxiv.org/abs/ 2412.17287
2024
-
[20]
The irace package: Iterated racing for automatic algorithm configuration
Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez Cáceres, Thomas Stützle, and Mauro Birattari. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58,
-
[21]
Gpt-4 technical report, 2024
OpenAI et al. Gpt-4 technical report, 2024. URL https://arxiv.org/abs/2303.08774
2024 arXiv
-
[22]
Lost in translation: A study of bugs introduced by large language models while translating code
Rangeet Pan, Ali Reza Ibrahimzada, Rahul Krishna, Divya Sankar, Lambert Pouguem Wassi, Michele Merler, Boris Sobolev, Raju Pavuluri, Saurabh Sinha, and Reyhaneh Jabbarvand. Lost in translation: A study of bugs introduced by large language models while translating code. arXiv [...
2023
-
[23]
Leveraging large language models for the generation of novel metaheuristic optimization algorithms
Michal Pluhacek, Anezka Kazikova, Tomas Kadavy, Adam Viktorin, and Roman Senkerik. Leveraging large language models for the generation of novel metaheuristic optimization algorithms. In Proceedings of the Companion Conference on Genetic and Evolutionary Computation, GECCO ’23 ...
2023
-
[24]
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, Alhussein Fawzi, Josh Grochow, Andrea Lodi, Jean-Baptiste Mouret, Talia Ring...
2023
-
[25]
Beyond the hype: Benchmarking llm-evolved heuristics for bin packing, 2025
Kevin Sim, Quentin Renau, and Emma Hart. Beyond the hype: Benchmarking llm-evolved heuristics for bin packing, 2025. URL https://arxiv.org/abs/2501.11411. 14 Improving Existing Optimization Algorithms with LLMs
2025 arXiv
-
[26]
Introducing Claude 3.5 Sonnet — anthropic.com
Anthropic Team. Introducing Claude 3.5 Sonnet — anthropic.com. https://www.anthropic.com/news/ claude-3-5-sonnet , 2024. [Accessed 02-11-2024]
2024
-
[27]
Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context,
Gemini Team and et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context,
-
[28]
The llama 3 herd of models, 2024
Meta Team. The llama 3 herd of models, 2024. URL https://arxiv.org/abs/2407.21783
2024 arXiv
-
[29]
Llamea: A large language model evolutionary algorithm for automatically generating metaheuristics, 2024
Niki van Stein and Thomas Bäck. Llamea: A large language model evolutionary algorithm for automatically generating metaheuristics, 2024. URL https://arxiv.org/abs/2405.20132
2024 arXiv
-
[30]
Gomes, and Shir
Hanchen Wang, Tianfan Fu, Yuanqi Du, Wenhao Gao, Kexin Huang, Ziming Liu, Payal Chandak, Shengchao Liu, Peter Katwyk, Andreea Deac, Anima Anandkumar, Karianne Bergen, Carla P. Gomes, and Shir. Sci- entific discovery in the age of artificial intelligence. Nature, 620(7972):47–6...
2023
-
[31]
Grounding data science code generation with input-output specifications, 2024
Yeming Wen, Pengcheng Yin, Kensen Shi, Henryk Michalewski, Swarat Chaudhuri, and Alex Polozov. Grounding data science code generation with input-output specifications, 2024. URL https://arxiv.org/abs/2402. 08073
2024
-
[32]
Wolpert and W.G
D.H. Wolpert and W.G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):67–82, 1997. doi: 10.1109/4235.585893
1997
-
[33]
Prototype2code: End-to- end front-end code generation from ui design prototypes, 2024
Shuhong Xiao, Yunnong Chen, Jiazhi Li, Liuqing Chen, Lingyun Sun, and Tingting Zhou. Prototype2code: End-to- end front-end code generation from ui design prototypes, 2024. URL https://arxiv.org/abs/2405.04975
2024 arXiv
-
[34]
Large language models meet nl2code: A survey, 2023
Daoguang Zan, Bei Chen, Fengji Zhang, Dianjie Lu, Bingchao Wu, Bei Guan, Yongji Wang, and Jian-Guang Lou. Large language models meet nl2code: A survey, 2023. URL https://arxiv.org/abs/2212.09420
2023 arXiv
-
[35]
CodeAgent: Enhancing code generation with tool-integrated agent systems for real-world repo-level coding challenges
Kechi Zhang, Jia Li, Ge Li, Xianjie Shi, and Zhi Jin. CodeAgent: Enhancing code generation with tool-integrated agent systems for real-world repo-level coding challenges. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the A...
2024 doi
-
[36]
Large language models are human-level prompt engineers, 2023
Yongchao Zhou, Andrei Ioan Muresanu, Ziwen Han, Keiran Paster, Silviu Pitis, Harris Chan, and Jimmy Ba. Large language models are human-level prompt engineers, 2023. URL https://arxiv.org/abs/2211.01910. 15
2023 arXiv
-
[2016]
doi: 10.1016/j.orp.2016.09.002
2016 doi
-
[2024]
URL https://arxiv.org/abs/2403.05530
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.