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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 42 references that are in the map.
- First posted on arXiv 5 Sep 2025.

## Builds on (most cited first, 17 of 17)

- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [A Survey on Large Language Models for Code Generation](https://mlsanity.com/paper/2406.00515/) (2024)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Large Language Models as General Pattern Machines](https://mlsanity.com/paper/2307.04721/) (2023)
- [LLaMEA: A Large Language Model Evolutionary Algorithm for Automatically Generating Metaheuristics](https://mlsanity.com/paper/2405.20132/) (2024)
- [A Systematic Survey on Large Language Models for Algorithm Design](https://mlsanity.com/paper/2410.14716/) (2024)
- [Large Language Models for Combinatorial Optimization: A Systematic Review](https://mlsanity.com/paper/2507.03637/) (2025)
- [BigO(Bench): Can LLMs Generate Code with Controlled Time and Space Complexity?](https://mlsanity.com/paper/2503.15242/) (2025)
- [Tabular Data Understanding with LLMs: A Survey of Recent Advances and Challenges](https://mlsanity.com/paper/2508.00217/) (2025)
- [Metaheuristics and Large Language Models Join Forces: Toward an Integrated Optimization Approach](https://mlsanity.com/paper/2405.18272/) (2024)
- [Combinatorial Optimization for All: Using LLMs to Aid Non-Experts in Improving Optimization Algorithms](https://mlsanity.com/paper/2503.10968/) (2025)
- [Improving Existing Optimization Algorithms with LLMs](https://mlsanity.com/paper/2502.08298/) (2025)
- [The Longest Run Subsequence Problem: Further Complexity Results](https://mlsanity.com/paper/2011.08119/) (2020)
- [A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem](https://mlsanity.com/paper/2508.14020/) (2025)

## Abstract (arXiv)

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.