Pith. sign in

REVIEW 4 major objections 5 minor 49 references

An LLM that reads four per-run statistics can output a bias vector that improves a Biased Random-Key Genetic Algorithm on the Longest Run Subsequence problem, with the strongest gains on the most complex, large-alphabet instances.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

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.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection A careful, honest transfer of the OptiPattern idea to a string problem, with modest but real gains on complex instances; the 'instance-driven' part is less proven than the abstract claims because a simple static bias baseline is missing. the 4 major comments →

arxiv 2509.09707 v1 pith:WIN4MYTQ submitted 2025-09-05 cs.NE cs.AIcs.CL

LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm

Camilo Chac\'on Sartori , Mart\'in Isla Pino , Pedro Pinacho-Davidson , Christian Blum This is my paper
classification cs.NE cs.AIcs.CL
keywords Large Language ModelsMetaheuristicsBiased Random-Key Genetic AlgorithmLongest Run SubsequenceInstance-Driven Heuristic BiasCombinatorial OptimizationAlpha-Beta Parameters
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to show that a large language model can act as a cheap, one-shot advisor for a genetic algorithm on an NP-hard string problem. Instead of generating code, the LLM reads a small table of instance-derived statistics and returns eight numbers that bias the search before it starts. On 1,050 synthetic instances of the Longest Run Subsequence problem, the best hybrid beats the plain BRKGA on the hardest groups, and the paper argues the gain is not random noise because randomized bias vectors actually hurt. The practical payoff would be a zero-training way to inject instance awareness into metaheuristics.

Core claim

The paper's central claim is that a single LLM call can turn four cheap per-run statistics — normalized length, opportunity, distance to the next same-character run, and global character frequency — into an instance-specific bias vector that improves BRKGA's final solution quality on the Longest Run Subsequence problem. The LLM is asked to set four alpha weights and four beta ideals in a sigmoid influence equation; converting those into a desirability per run and multiplying it into the random keys reorders the greedy decoder so promising runs are considered earlier. In the authors' experiments all four LLM hybrids beat the baseline overall, the top-performing open-weight hybrid ranks first

What carries the argument

The alpha-beta mechanism: four alpha weights (summing to one) and four beta ideals are fed into the prompt's sigmoid influence formula, producing a per-run desirability vector L. The modified decoder sorts runs by the product of random key and desirability, v_i · L_i, before greedy construction, so the LLM's reading of the feature matrix steers which runs come early. The four co-designed metrics form the feature matrix F the LLM analyzes; their extraction is deliberately separated from the LLM because direct LLM computation of features proved unreliable.

Load-bearing premise

The central claim depends on an LLM being able to read a small table of per-run statistics and output alpha/beta weights that capture genuine instance structure; the paper's only control is uniform random bias, so the possibility that any fixed sensible bias would work just as well is left open.

What would settle it

Run the exact pipeline but replace the LLM's alpha/beta output with a fixed consensus vector, such as high alpha on normalized length and opportunity with beta ideals at the medians reported for the top model, across the same 1,050 instances; if the fixed vector matches the LLM's solution quality, the instance-driven component is unsupported. Separately, rerun the benchmark on non-uniform, structured strings meant to mimic biological sequences; a disappearance of the gains would show the uniform random benchmark was carrying the effect.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • On the 1,050-instance benchmark, all four BRKGA+LLM hybrids rank above the plain BRKGA on average solution quality, and the top hybrid wins the global Friedman/Nemenyi comparison.
  • The top hybrid beats the baseline with statistical significance in 15 of 35 length-by-alphabet groups (42.86%), and the significant groups are mostly large-alphabet instances.
  • Random bias vectors — static or refreshed every generation — score below the standard BRKGA, so the LLM's fixed bias is doing more than adding noise.
  • Curated metrics precompute in about 8 seconds at n=5000 while a randomly chosen LLM-suggested set took about 300 seconds, with similar solution quality, making human curation a computational-efficiency filter.
  • Token usage grows super-linearly with instance length, from about 1.9k tokens at n=100 to 90k at n=5000, so API cost and latency scale with the feature-table size; the free small model remains viable but slower.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the gain comes mainly from a smooth non-random bias rather than from instance-specific reading, a fixed hand-coded alpha/beta vector might match the LLM's result; the paper's ablation, which pits the LLM only against uniform random vectors, does not settle this.
  • The benchmark is uniform i.i.d. strings, so the stated bioinformatics motivation is untested; real DNA or protein strings have biased alphabets and long-range structure, where instance-driven bias could behave differently.
  • Because the top model's alpha/beta distributions for secondary metrics shift with instance scale, a cheap distilled model trained on its outputs might reproduce much of the benefit without per-instance API calls.
  • The multiplicative-key mechanism should transfer to other BRKGA-applied string problems with run-like structure, such as longest common subsequence variants, as long as the same static pre-analysis applies.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes a framework that uses an LLM to analyze a per-instance table of four run metrics for the Longest Run Subsequence (LRS) problem and to output eight coefficients (four alpha weights, four beta ideals). These coefficients define a fixed bias vector L that multiplies the random keys in a BRKGA decoder, biasing the construction order before evolution begins. Four LLM variants are compared against a standard BRKGA on 1,050 uniformly random instances with lengths 100-5000 and alphabets 2-32. Each variant is tuned separately with irace. The best variant, BRKGA+Llama-4-Maverick, achieves an average score of 313.07 versus 311.85 for the baseline, with statistically significant superiority in 15 of 35 instance groups, concentrated in large-alphabet instances. Ablation studies with random bias vectors and with alternative metric sets, STN behavioral analysis, parameter-distribution analysis, and cost/latency analysis are also reported.

Significance. If the result holds, the paper provides evidence for a cheap, zero-shot way to inject instance-specific structure into BRKGA and extends the authors' earlier OptiPattern paradigm to a string-based combinatorial problem. The empirical apparatus is careful: per-variant irace tuning, honest disclosure that 20 of 35 instance groups show no significant improvement, a random-bias control showing the LLM signal is informative, and a behavioral analysis. The paper ships code and the experiments are reproducible. However, the central 'instance-driven' claim is not fully separated from a generic 'non-random bias helps BRKGA' effect, and the prompt used in Phase 3 describes two metrics in a way that conflicts with their formal definitions. These issues do not invalidate the measured performance but do require additional controls and clarification before the paper's main claims are fully supported.

major comments (4)
  1. [§4.7, Table 6; §4.9, Figure 8] The only ablation isolating the LLM's contribution is §4.7/Table 6, which compares the LLM-generated bias vector against uniform random vectors. This controls for 'non-random' but not for 'instance-driven': it does not exclude the possibility that any fixed, sensible bias--e.g., using the consensus alpha/beta values visible in Figure 8, or setting L_i proportional to the normalized run length--yields the same ~313 average. If a static bias matches or beats 313.07, the improvement is due to adding a smooth bias to BRKGA, not to the LLM's per-instance analysis. Please add a static-bias control (e.g., median alpha/beta from Figure 8, or a hand-coded L_i = ML_i) and report the comparison.
  2. [§3.3.1 vs §3.2] The Phase 3 prompt's [BEGIN EVALUATION SEQUENCE] describes Normalized_length as 'Length of the run divided by the total string length' and Opportunity as '1/(1+gap)', whereas §3.2 defines ML(R_i)=l_i/l_max and MO(R_i)=|Σ_{>i}|/|Σ|. The table inserted in the prompt uses the formal definitions, so the LLM sees values whose column labels have incorrect semantics. This does not necessarily invalidate the empirical gains, but it undermines the interpretability analysis of §4.9 and the claim of a cleanly co-designed metric set. Correct the prompt descriptions (or the formal definitions), or explicitly document the mismatch and its possible effect on the LLM's outputs.
  3. [§4.2] The benchmark consists exclusively of iid uniform random strings. The introduction and Section 2.2 motivate the work by string-based bioinformatics problems, but no structured, non-uniform, or biological strings are tested. The generalization in Section 6 and the abstract's 'complex optimization domains' is therefore an extrapolation. Add a small set of structured/biological instances (or clearly delimit the claims to uniform random strings).
  4. [§4.6, Table 5 (Case 2)] The random 4-metric set achieves an average of 312.94, essentially tied with the curated set's 313.07. Thus the human-LLM curation is shown to matter only through pre-computation cost (Figure 6), not solution quality. The authors acknowledge this honestly, but Section 1.1 presents the co-design process as a contribution without noting this quality-neutrality. Please adjust the framing so that the claimed contribution of the human-LLM metric co-design is stated as computational feasibility, not improved solution quality.
minor comments (5)
  1. [§4.4] The text says 'with a budget of 3000 runs over 70 instances' but the preceding description defines 42 tuning instances (35 + 7). Correct the count.
  2. [Algorithm 2] The header uses [0,1]^n for the random-key vector and [0,1]^m for L, but n should be m (the number of runs) for consistency with Algorithm 1 and Section 2.4.
  3. [Tables 2, 5, 6] The lightning-bolt icon appears as '/bol◎' in several places; this is likely a LaTeX/PDF rendering artifact and should be fixed.
  4. [§3.3.3] The parenthetical 'e.g., an LRS sequence with 'length=5000'' is oddly placed; consider rephrasing.
  5. [Figure 8 caption] The caption says '1050 instances' but the subplots show distributions for 30 instances per configuration. Clarify the aggregate.

Circularity Check

0 steps flagged

No significant circularity: LLM bias is generated a priori from instance metrics and validated against random controls; minor self-citation of the foundational framework is not load-bearing.

full rationale

The paper's central claim — that an LLM-generated a priori bias vector improves BRKGA — is not circular. The bias vector L is computed once from alpha/beta output by the LLM after analyzing the instance's metric matrix, before any search begins. It is never fitted to the measured solution qualities; the BRKGA parameters are tuned separately with irace on a tuning set, and the LLM's alpha/beta are not adjusted based on outcomes. The ablation in Section 4.7/Table 6 compares the LLM bias against static and dynamic uniform random bias vectors, and the LLM's vector wins. This is a genuine out-of-sample comparison, not a fitted-input-called-prediction. The alpha-beta mechanism and prompt template are inherited from the authors' prior OptiPattern paper [35], but the paper's own experiments on 1,050 new instances provide independent evidence for the effectiveness of the mechanism; the self-citation is not load-bearing. The main methodological gap is the absence of a fixed, sensible static bias (e.g., consensus alpha/beta values from Figure 8) as a control, so the 'instance-driven' component is not fully isolated from the generic benefit of a smooth metric-based bias. However, that is an experimental control deficiency, not a circular derivation. No equation in the paper defines the predicted improvement in terms of fitted parameters, and no fitted parameter is renamed as a prediction. The prompt inconsistencies noted by the skeptic (e.g., Normalized_length described as divided by total string length vs. formal li/lmax) affect interpretability but do not make the derivation circular.

Axiom & Free-Parameter Ledger

4 free parameters · 4 axioms · 0 invented entities

The paper is a method transfer, so the ledger is dominated by imported mechanism and experimental choices rather than derived quantities. The 8 alpha/beta values are treated as given per-instance LLM judgments, not derived and not fitted to outcomes; the metric set (k=4) and candidate pool (nmetrics=10) are hand choices whose quality impact is small per the authors' own ablation; the BRKGA parameters are irace-tuned per variant. No new entities are postulated. The main independence burden is that the benchmark, baseline, framework, and visualization tool all originate within the same author group.

free parameters (4)
  • k (number of curated metrics) and nmetrics (candidate pool) = k=4, nmetrics=10
    Human choices in Phase 1 (Section 3.1). The paper's own ablation (Table 5) shows k=2 achieves 312.88 and a random k=4 set achieves 312.94 vs 313.07 for the curated set, so this choice is not quality-critical.
  • Per-instance LLM outputs alpha_1..4, beta_1..4 (8 values) = e.g., Fig. 2: alpha=(0.4,0.3,0.2,0.1), beta=(1.0,1.0,1.0,0.5)
    Produced in Phase 3 as arbitrary per-instance judgments; they deterministically define the bias vector L and are never derived from first principles or fitted to search outcomes. Their informativeness is tested only against uniform random bias vectors (Section 4.7).
  • irace-tuned BRKGA parameters (population, elite/mutant proportions, elite inheritance) = baseline (16,0.25,0.17,0.56); Maverick (17,0.12,0.30,0.69); see Table 1b
    Tuned per algorithm variant on a dedicated 42-instance set (Section 4.4). Standard algorithm configuration, but it means each variant is compared with its own optimal settings.
  • Per-instance time budget n/5 seconds = 20 to 1000 seconds
    Experimental budget choice shared by all variants (Section 4.5).
axioms (4)
  • domain assumption LRS is NP-hard; the run-decomposition representation and the all-or-nothing property of runs are valid reductions
    Loaded from Dondi-Sikora [15] and the authors' own BRKGA paper [5] (Sections 2.3-2.4); no derivation appears in this paper.
  • ad hoc to paper Uniform iid random strings over alphabets of size 2-32 are a representative benchmark class for the intended string-based/bioinformatics domain
    Section 4.2 states that no public LRS instances exist and generates 1,050 uniform random strings; no biological or structured strings are tested, so the domain-transfer claim is an assumption.
  • ad hoc to paper A single unseeded LLM call over a 4-column numeric table yields stable and instance-specific guidance
    Section 3.3.3 states this as the central hypothesis; it is validated only against uniform random bias vectors (Section 4.7), not a fixed-bias control, and LLM inference is stochastic with default temperature.
  • domain assumption The greedy decoder's validity check (adding a run preserves contiguity of same-character runs) is correctly implemented
    Algorithm 2 references the check without specifying it; the prose in Section 2.4 says 'each run in the solution must consist of a unique character', which contradicts the paper's own optimal example containing two Z runs.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm." pith.science (2026). https://pith.science/paper/WIN4MYTQ

@misc{pith2026250909707,
  author       = {Pith},
  title        = {Pith review of: LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WIN4MYTQ}},
  note         = {Machine review of arXiv:2509.09707}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Integrating Large Language Models (LLMs) within metaheuristics opens a novel path for solving complex combinatorial optimization problems. While most existing approaches leverage LLMs for code generation to create or refine specific heuristics, they often overlook the structural properties of individual problem instances. In this work, we introduce a novel framework that integrates LLMs with a Biased Random-Key Genetic Algorithm (BRKGA) to solve the NP-hard Longest Run Subsequence problem. Our approach extends the instance-driven heuristic bias paradigm by introducing a human-LLM collaborative process to co-design and implement a set of computationally efficient metrics. The LLM analyzes these instance-specific metrics to generate a tailored heuristic bias, which steers the BRKGA toward promising areas of the search space. We conduct a comprehensive experimental evaluation, including rigorous statistical tests, convergence and behavioral analyses, and targeted ablation studies, comparing our method against a standard BRKGA baseline across 1,050 generated instances of varying complexity. Results show that our top-performing hybrid, BRKGA+Llama-4-Maverick, achieves statistically significant improvements over the baseline, particularly on the most complex instances. Our findings confirm that leveraging an LLM to produce an a priori, instance-driven heuristic bias is a valuable approach for enhancing metaheuristics in complex optimization domains.

Figures

Figures reproduced from arXiv: 2509.09707 by Camilo Chac\'on Sartori, Christian Blum, Mart\'in Isla Pino, Pedro Pinacho-Davidson.

Figure 1
Figure 1. Figure 1: Example of the process to find a Longest Run Subsequence (LRS) in the string [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Overview of the proposed BRKGA-LLM framework for the LRS problem. The process consists of four [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Phase 1 of the BRKGA-LLM Framework: A human-in-the-loop process where the researcher first sets key [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Critical Difference (CD) diagram of the average ranks of five BRKGA variants evaluated on the complete [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Convergence speed comparison of the four LLM-hybrids on a challenging ( [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Pre-computation time comparison for metric sets. The analysis contrasts the total time required to compute [PITH_FULL_IMAGE:figures/full_fig_p024_6.png] view at source ↗
Figure 8
Figure 8. Figure 8: Consensus on Primary Metrics. A clear consensus emerges for the primary metrics, α1 (Normalized Length) and α2 (Opportunity), especially for large instances (n = 5000). For these parameters, most LLM variants, including Llama-4-Maverick, exhibit very low variance, producing tall, narrow violin plots. This indicates a strong, unanimous agreement that these two metrics are fundamentally the most important fo… view at source ↗
Figure 7
Figure 7. Figure 7: Five images generated with STNWeb [9] comparing the search behavior of BRKGA+Llama-4-Maverick and the standard BRKGA on an instance with n = 5000 across varying alphabet sizes (|Σ|). (a) For a small alphabet (|Σ| = 2), both algorithms initially locate a best solution (red nodes). However, as |Σ| increases, BRKGA+Llama-4- Maverick exhibits enhanced exploration capabilities, while the standard BRKGA tends to… view at source ↗
Figure 8
Figure 8. Figure 8: Violin plots showing the distribution of estimated parameters by four LLMs. The analysis compares parameter [PITH_FULL_IMAGE:figures/full_fig_p030_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: API latency (seconds) comparison for four LLM variants—GPT-4.1-mini, Gemini-2.5-Flash, Llama-3.2-3b, [PITH_FULL_IMAGE:figures/full_fig_p032_9.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

49 extracted references · 30 canonical work pages · 2 internal anchors

  1. [1]

    A systematic literature review of adaptive parameter control methods for evolutionary algorithms

    Aldeida Aleti and Irene Moser. A systematic literature review of adaptive parameter control methods for evolutionary algorithms. ACM Comput. Surv., 49(3), October 2016. ISSN 0360-0300. doi: 10.1145/2996355. URL https://doi.org/10.1145/2996355

    work page doi:10.1145/2996355 2016

  2. [2]

    Approximation algorithms for the longest run subsequence problem

    Yuichi Asahiro, Hiroshi Eto, Mingyang Gong, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Shunichi Tanaka. Approximation algorithms for the longest run subsequence problem. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023), pages 2–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023

    work page 2023

  3. [3]

    A survey of longest common subsequence algorithms

    Lasse Bergroth, Harri Hakonen, and Timo Raita. A survey of longest common subsequence algorithms. In Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000 , pages 39–48. IEEE, 2000

    work page 2000

  4. [4]

    Metaheuristics for String Problems in Bio-informatics, volume 6

    Christian Blum and Paola Festa. Metaheuristics for String Problems in Bio-informatics, volume 6. John Wiley & Sons, 2016

    work page 2016

  5. [5]

    A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem

    Christian Blum and Pedro Pinacho-Davidson. A biased random key genetic algorithm for solving the longest run subsequence problem, 2025. URL https://arxiv.org/abs/2508.14020

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  6. [6]

    Metaheuristics in combinatorial optimization: Overview and conceptual comparison

    Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv., 35(3):268–308, September 2003. ISSN 0360-0300. doi: 10.1145/937503. 937505. URL https://doi.org/10.1145/937503.937505

    work page arXiv 2003

  7. [7]

    Hyper-heuristics: A survey of the state of the art

    Edmund K Burke, Michel Gendreau, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender Özcan, and Rong Qu. Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society , 64(12): 1695–1724, 2013

    work page 2013

  8. [8]

    On the role of metaheuristic optimization in bioinformatics

    Laura Calvet, Sergio Benito, Angel A Juan, and Ferran Prados. On the role of metaheuristic optimization in bioinformatics. International Transactions in Operational Research, 30(6):2909–2944, 2023

    work page 2023

  9. [9]

    STNWeb: A new visualization tool for analyzing op- timization algorithms

    Camilo Chacón Sartori, Christian Blum, and Gabriela Ochoa. STNWeb: A new visualization tool for analyzing op- timization algorithms. Software Impacts, 17:100558, 2023. ISSN 2665-9638. doi: https://doi.org/10.1016/j.simpa. 2023.100558. URL https://www.sciencedirect.com/science/article/pii/S2665963823000957

    work page arXiv 2023

  10. [10]

    Bigo(bench) – can llms generate code with controlled time and space complexity?, 2025

    Pierre Chambon, Baptiste Roziere, Benoit Sagot, and Gabriel Synnaeve. Bigo(bench) – can llms generate code with controlled time and space complexity?, 2025. URL https://arxiv.org/abs/2503.15242

    Pith/arXiv arXiv 2025

  11. [11]

    Evolutionary Computation and Large Language Models: A Survey of Methods, Synergies, and Applications

    Dikshit Chauhan, Bapi Dutta, Indu Bala, Niki van Stein, Thomas Bäck, and Anupam Yadav. Evolutionary computation and large language models: A survey of methods, synergies, and applications, 2025. URL https: //arxiv.org/abs/2505.15741

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  12. [12]

    Gonzalez, and Ion Stoica

    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

    Pith/arXiv arXiv 2024

  13. [13]

    Probing LLMs on Optimization Problems: Can They Recall and Interpret Problem Features? In Pablo García-Sánchez, Emma Hart, and Sarah L

    Francesca Da Ros, Luca Di Gaspero, and Kevin Roitero. Probing LLMs on Optimization Problems: Can They Recall and Interpret Problem Features? In Pablo García-Sánchez, Emma Hart, and Sarah L. Thomson, editors, Applications of Evolutionary Computation, pages 353–371, Cham, 2025. Springer Nature Switzerland. ISBN 978-3-031-90065-5

    work page 2025

  14. [14]

    Large Language Models for Combinatorial Optimization: A Systematic Review

    Francesca Da Ros, Michael Soprano, Luca Di Gaspero, and Kevin Roitero. Large Language Models for Combinatorial Optimization: A Systematic Review. arXiv preprint arXiv:2507.03637, 2025. 34 LLM-Based Instance-Driven Heuristic Bias In the Context of a Biased Random Key Genetic Algorithm

    arXiv 2025

  15. [15]

    The Longest Run Subsequence Problem: Further Complexity Results

    Riccardo Dondi and Florian Sikora. The Longest Run Subsequence Problem: Further Complexity Results. In Paweł Gawrychowski and Tatiana Starikovskaya, editors, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), volume 191 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1– 14:15, Dagstuhl, Germany, 2021. Schloss Dagstu...

    work page doi:10.4230/lipics.cpm.2021.14 2021

  16. [16]

    Combinatorics of genome rearrangements

    Guillaume Fertin. Combinatorics of genome rearrangements. MIT press, 2009

    work page 2009

  17. [17]

    Hirschberg

    Daniel S. Hirschberg. Algorithms for the longest common subsequence problem. J. ACM, 24(4):664–675, October

    work page

  18. [18]

    A survey on large language models for code generation, 2024

    Juyong Jiang, Fan Wang, Jiasi Shen, Sungju Kim, and Sunghun Kim. A survey on large language models for code generation, 2024. URL https://arxiv.org/abs/2406.00515

    Pith/arXiv arXiv 2024

  19. [19]

    Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art

    Maryam Karimi-Mamaghan, Mehrdad Mohammadi, Patrick Meyer, Amir Mohammad Karimi-Mamaghan, and El-Ghazali Talbi. Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art. European Journal of Operational Research, 296(2):393–422, 2022. ISSN 0377-

    work page 2022

  20. [20]

    The longest letter-duplicated subsequence and related problems

    Wenfeng Lai, Adiesha Liyanage, Binhai Zhu, and Peng Zou. The longest letter-duplicated subsequence and related problems. Acta Informatica, 61(3):315–329, 2024

    work page 2024

  21. [21]

    Evolution of heuristics: Towards efficient automatic algorithm design using large language model, 2024

    Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model, 2024. URL https://arxiv.org/abs/2401.02051

    Pith/arXiv arXiv 2024

  22. [22]

    A systematic survey on large language models for algorithm design

    Fei Liu, Yiming Yao, Ping Guo, Zhiyuan Yang, Zhe Zhao, Xi Lin, Xialiang Tong, Mingxuan Yuan, Zhichao Lu, Zhenkun Wang, et al. A systematic survey on large language models for algorithm design. arXiv preprint arXiv:2410.14716, 2024

    arXiv 2024

  23. [23]

    Large language models as evolutionary optimizers, 2024

    Shengcai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew-Soon Ong. Large language models as evolutionary optimizers, 2024. URL https://arxiv.org/abs/2310.19046

    Pith/arXiv arXiv 2024

  24. [24]

    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,

    work page

  25. [25]

    Large language models: A survey, 2025

    Shervin Minaee, Tomas Mikolov, Narjes Nikzad, Meysam Chenaghlu, Richard Socher, Xavier Amatriain, and Jianfeng Gao. Large language models: A survey, 2025. URL https://arxiv.org/abs/2402.06196

    Pith/arXiv arXiv 2025

  26. [26]

    Large language models as general pattern machines, 2023

    Suvir Mirchandani, Fei Xia, Pete Florence, Brian Ichter, Danny Driess, Montserrat Gonzalez Arenas, Kanishka Rao, Dorsa Sadigh, and Andy Zeng. Large language models as general pattern machines, 2023. URL https: //arxiv.org/abs/2307.04721

    Pith/arXiv arXiv 2023

  27. [27]

    An enhanced beam search algorithm for the Shortest Common Supersequence Problem

    Sayyed Rasoul Mousavi, Fateme Bahri, and Farzaneh Sadat Tabataba. An enhanced beam search algorithm for the Shortest Common Supersequence Problem. Engineering Applications of Artificial Intelligence, 25(3): 457–467, 2012. ISSN 0952-1976. doi: https://doi.org/10.1016/j.engappai.2011.08.006. URL https://www. sciencedirect.com/science/article/pii/S0952197611001497

    work page doi:10.1016/j.engappai.2011.08.006 2012

  28. [28]

    AlphaEvolve : A coding agent for scientific and algorithmic discovery

    Alexander Novikov, Ngân V~u, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, S Shirobokov, Borislav M Kozlovskii, Francisco J R Ruiz, Abbas Mehrabian, M P Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, Matej Balog, and Google Deepmind. AlphaEvolve : A coding agent for scientific a...

    work page 2025

  29. [29]

    Malan, and Christian Blum

    Gabriela Ochoa, Katherine M. Malan, and Christian Blum. Search trajectory networks: A tool for analysing and visualising the behaviour of metaheuristics. Applied Soft Computing, 109:107492, 2021. ISSN 1568-4946. doi: https://doi.org/10.1016/j.asoc.2021.107492. URL https://www.sciencedirect.com/science/article/ pii/S1568494621004154

    work page arXiv 2021

  30. [30]

    GPT-4 Technical Report, 2024

    OpenAI et al. GPT-4 Technical Report, 2024. URL https://arxiv.org/abs/2303.08774

    Pith/arXiv arXiv 2024

  31. [31]

    A biased random key genetic algorithm for solving the longest common square subsequence problem

    Jaume Reixach, Christian Blum, Marko Djukanovi´c, and Günther R Raidl. A biased random key genetic algorithm for solving the longest common square subsequence problem. IEEE Transactions on Evolutionary Computation, 29(2):390–403, 2024

    work page 2024

  32. [32]

    Pawan Kumar, Emilien Dupont, Francisco J

    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, and Alhussein Fawzi. Mathematical discoveries from program search with large language models. Nature, 625(7995): 35 LLM-Based Instance-Driven Heuristic Bia...

    doi:10.1038/s41586-023-06924-6 2024

  33. [33]

    Combinatorial Optimization for All: Using LLMs to Aid Non-Experts in Improving Optimization Algorithms, 2025

    Camilo Chacón Sartori and Christian Blum. Combinatorial Optimization for All: Using LLMs to Aid Non-Experts in Improving Optimization Algorithms, 2025. URL https://arxiv.org/abs/2503.10968

    Pith/arXiv arXiv 2025

  34. [34]

    Improving Existing Optimization Algorithms with LLMs, 2025

    Camilo Chacón Sartori and Christian Blum. Improving Existing Optimization Algorithms with LLMs, 2025. URL https://arxiv.org/abs/2502.08298

    Pith/arXiv arXiv 2025

  35. [35]

    Metaheuristics and large language models join forces: Toward an integrated optimization approach

    Camilo Chacón Sartori, Christian Blum, Filippo Bistaffa, and Guillem Rodríguez Corominas. Metaheuristics and large language models join forces: Toward an integrated optimization approach. IEEE Access, 13:2058–2079,

    work page 2058

  36. [36]

    Heuristics for genome rearrangement distance with replicated genes

    Gabriel Siqueira, Klairton Lima Brito, Ulisses Dias, and Zanoni Dias. Heuristics for genome rearrangement distance with replicated genes. IEEE/ACM transactions on computational biology and bioinformatics , 18(6): 2094–2108, 2021

    work page 2094

  37. [37]

    A greedy approximation algorithm for constructing shortest common superstrings

    Jorma Tarhio and Esko Ukkonen. A greedy approximation algorithm for constructing shortest common superstrings. Theoretical computer science, 57(1):131–145, 1988

    work page 1988

  38. [38]

    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,

    work page

  39. [39]

    Llama: Open and efficient foundation language models, 2023

    Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023. URL https: //arxiv.org/abs/2302.13971

    Pith/arXiv arXiv 2023

  40. [40]

    LLaMEA: A Large Language Model Evolutionary Algorithm for Automatically Generating Metaheuristics

    Niki van Stein and Thomas Bäck. LLaMEA: A Large Language Model Evolutionary Algorithm for Automatically Generating Metaheuristics. IEEE Transactions on Evolutionary Computation, pages 1–1, 2024. doi: 10.1109/ TEVC.2024.3497793

    arXiv 2024

  41. [41]

    Tabular data understanding with llms: A survey of recent advances and challenges, 2025

    Xiaofeng Wu, Alan Ritter, and Wei Xu. Tabular data understanding with llms: A survey of recent advances and challenges, 2025. URL https://arxiv.org/abs/2508.00217

    Pith/arXiv arXiv 2025

  42. [42]

    An improved adaptive genetic algorithm for job-shop scheduling problem

    Yingjie Xing, Zhentong Chen, Jing Sun, and Long Hu. An improved adaptive genetic algorithm for job-shop scheduling problem. In Third International Conference on Natural Computation (ICNC 2007), volume 4, pages 287–291, 2007. doi: 10.1109/ICNC.2007.202

    work page doi:10.1109/icnc.2007.202 2007

  43. [43]

    Le, Denny Zhou, and Xinyun Chen

    Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V . Le, Denny Zhou, and Xinyun Chen. Large Language Models as Optimizers, 2024. URL https://arxiv.org/abs/2309.03409

    Pith/arXiv arXiv 2024

  44. [44]

    Reevo: Large language models as hyper-heuristics with reflective evolution

    Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models as hyper-heuristics with reflective evolution. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors,Advances in Neural Information Processing Systems, volume 37, pages 43571–43...

    work page 2024

  45. [1977]

    doi: 10.1145/322033.322044

    ISSN 0004-5411. doi: 10.1145/322033.322044. URL https://doi.org/10.1145/322033.322044

    work page arXiv

  46. [2016]

    doi: 10.1016/j.orp.2016.09.002

    doi:10.1016/j.orp.2016.09.002 2016

  47. [2024]

    URL https://arxiv.org/abs/2403.05530

    Pith/arXiv arXiv

  48. [2025]

    doi: 10.1109/ACCESS.2024.3524176

    work page arXiv 2024

  49. [2217]

    URL https://www.sciencedirect.com/science/ article/pii/S0377221721003623

    doi: https://doi.org/10.1016/j.ejor.2021.04.032. URL https://www.sciencedirect.com/science/ article/pii/S0377221721003623

    work page doi:10.1016/j.ejor.2021.04.032 2021

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.