MeLA: A metacognitive LLM-driven architecture for automatic heuristic design

Zishang Qiu, Xinan Chen, Long Chen, Wenjie Yi, Ruibin Bai

In the world of combinatorial optimization, heuristics are the workhorses that solve everything from delivery routes to chip design. Traditionally, these algorithms were hand-crafted by experts—a slow, "artisanal" process. Recently, Large Language Models (LLMs) have entered the fray, automating the design of these heuristics. However, most current approaches treat LLMs like a digital version of natural selection: they generate a bunch of code, keep the best ones, and "mutate" them.

A new paper, MeLA: A Metacognitive LLM-Driven Architecture for Automatic Heuristic Design, argues that we are missing the point. Instead of evolving the code, why not evolve the reasoning process that creates the code?

TL;DR

MeLA introduces "Prompt Evolution," a paradigm shift that evolves the instructional prompts guiding an LLM rather than the heuristic code itself. By using a metacognitive framework to analyze its own successes and failures, MeLA generates more robust, interpretable, and high-performing heuristics, significantly outperforming current state-of-the-art methods on complex real-world problems.

What Problem Does This Paper Address?

Designing high-performance heuristics is hard. The "No Free Lunch" theorem tells us that no single heuristic is perfect for every problem, meaning we constantly need new ones. While automated tools like Genetic Programming (GP) exist, they are often "tethered" to human-defined primitives.

Current LLM-based systems like FunSearch or ReEvo have made great strides by evolving populations of code. However, the authors of MeLA point out a fundamental flaw: these systems treat the LLM as a static generator. They don't help the LLM "learn to learn." Furthermore, when faced with messy, ill-defined real-world problems, these systems often struggle with syntax errors or poor problem formulations, leading to a "failure to launch" for the evolutionary process.

Methods

MeLA (Metacognitive LLM-Driven Architecture) shifts the focus from the product (the code) to the process (the prompt). It operates through a "metacognitive search engine" inspired by cognitive science.

The difference between traditional nature-inspired evolution and MeLA's metacognitive prompt evolution.

The architecture consists of three specialized roles:

  1. NP-hard Problem Analysis Expert: Instead of relying on manual problem descriptions, this module analyzes the raw source code of a problem to identify key parameters and challenges, building a solid foundation for design.
  2. Elite Code Debugger: To prevent the evolutionary process from stalling due to buggy code, this system autonomously detects and rectifies programming flaws (like out-of-bounds errors) while preserving the original design intent.
  3. Metacognitive Reflector: This is the "brain." It looks at the entire causal chain—from the strategy in the prompt to the performance of the resulting heuristic. It then systematically refines the prompt for the next generation.
The full flowchart of the MeLA architecture, showing the interaction between generation, error diagnosis, and metacognition.

Datasets

The researchers evaluated MeLA across four distinct challenges:

  • TSP50 (Traveling Salesperson Problem): A classic benchmark for path optimization.
  • BPP500 (Bin Packing Problem): A black-box combinatorial problem focused on resource allocation.
  • ACS (Adaptive Curriculum Sequencing): A complex, multi-objective real-world problem involving personalized learning paths for students.
  • WSN (Wireless Sensor Network) Deployment: A high-dimensional real-world problem involving sensor placement and power management.

Key Insights and Ideas

  • Prompt Evolution vs. Code Evolution: By evolving the prompt, MeLA internalizes the principles of what makes a heuristic "good." This leads to strategies that are more generalizable across different problem instances.
  • Interpretability is a Feature: Unlike evolved code, which can be cryptic, MeLA produces an optimized prompt. This prompt is a human-readable strategy that engineers can understand, manually refine, or adapt to other domains.
  • Closing the Loop on Errors: The "Elite Code Debugger" is vital. In real-world scenarios (like ACS), baseline models often fail to produce even a single runnable heuristic. MeLA’s ability to self-correct code ensures the evolutionary process continues.
  • Cognitive Science as a Blueprint: The success of the "metacognitive" approach suggests that AI architecture can benefit significantly from mimicking higher-order human thought processes like self-reflection and strategic planning.

Key Results

MeLA consistently outperformed state-of-the-art LLM-driven architectures (EoH and ReEvo) and traditional metaheuristics (GA, PSO, etc.).

  • Success Rates: In the WSN problem, MeLA achieved a 99.21% success rate, compared to ~53-56% for EoH and ReEvo.
  • Optimization Quality: For the complex ACS problem, MeLA achieved a final fitness score of 589.60, which is 52.94% better than EoH and 68.11% better than ReEvo.
  • Convergence: As shown in the convergence plots, MeLA (the red dashed line) typically finds better solutions faster and continues to improve where other models plateau.
Convergence plots showing MeLA's superior performance across all four problem domains.

Limitations and Future Work

While MeLA is a significant step forward, the authors note that its performance is still inherently linked to the capabilities of the underlying LLM (they used DeepSeek-V3).

Future directions include: * Testing MeLA with a wider variety of LLMs to further validate its model-agnostic nature. * Exploring the trade-offs between different model sizes and the computational cost of the metacognitive loop. * Applying the framework to even more diverse and "ill-defined" industrial optimization tasks.

Summary updated

Abstract

This paper introduces MeLA, a Metacognitive LLM-Driven Architecture that presents a new paradigm for Automatic Heuristic Design (AHD). Traditional evolutionary methods operate directly on heuristic code; in contrast, MeLA evolves the instructional prompts used to guide a Large Language Model (LLM) in generating these heuristics. This process of "prompt evolution" is driven by a novel metacognitive framework where the system analyzes performance feedback to systematically refine its generative strategy. MeLA's architecture integrates a problem analyzer to construct an initial strategic prompt, an error diagnosis system to repair faulty code, and a metacognitive search engine that iteratively optimizes the prompt based on heuristic effectiveness. In comprehensive experiments across both benchmark and real-world problems, MeLA consistently generates more effective and robust heuristics, significantly outperforming state-of-the-art methods. Ultimately, this research demonstrates the profound potential of using cognitive science as a blueprint for AI architecture, revealing that by enabling an LLM to metacognitively regulate its problem-solving process, we unlock a more robust and interpretable path to AHD.
BibTeX
@article{qiu2026mela,
  author = {Zishang Qiu and Xinan Chen and Long Chen and Wenjie Yi and Ruibin Bai},
  title = {{MeLA: A metacognitive LLM-driven architecture for automatic heuristic design}},
  journal = {Expert Systems with Applications},
  year = {2026},
  doi = {10.1016/j.eswa.2026.133022},
}
Figure