From Heuristic Selection to Automated Algorithm Design: LLMs Benefit from Strong Priors

This paper demonstrates that integrating high-quality prior benchmark algorithms as strong priors significantly enhances the performance, efficiency, and robustness of Large Language Models in automated black-box optimization, surpassing existing methods that rely primarily on adaptive prompt designs.

The Gist

Imagine you are trying to teach a very smart, but slightly confused, robot how to build the perfect car engine. You have a library of blueprints for thousands of different engines (some fast, some fuel-efficient, some rugged).

This paper is about how to talk to that robot (a Large Language Model, or LLM) so it doesn't just guess randomly, but actually learns to build a better engine than anyone has ever seen before.

Here is the story of their discovery, broken down into simple parts:

1. The Problem: The Robot is Listening to the Wrong Things

In the past, researchers tried to teach these robots by giving them long, complicated instructions in plain English. They would say things like, "Please be creative and invent a new way to solve this math problem."

The researchers in this paper decided to put on "X-ray glasses" (a tool called AttnLRP) to see exactly what the robot was paying attention to when it wrote its code.

The Analogy: Imagine you are giving a student a test. You write a long paragraph of instructions, but the student only reads the last sentence where you wrote, "Here is a sample essay." The student ignores your fancy instructions and just copies the style of the sample essay.

The Finding: The researchers discovered that the robot was almost entirely ignoring the "fancy instructions" and the "task descriptions." Instead, it was laser-focused on the code examples provided in the prompt. If you gave it a bad example, it wrote bad code. If you gave it a strong, high-quality example, it wrote a great algorithm.

2. The Solution: The "Mentor" Strategy

Since the robot learns best by looking at examples, the researchers changed their strategy. Instead of just saying, "Go make something new," they started acting like a coach with a highlight reel.

They created a method called BAG (Benchmark-Assisted Guided).

The Analogy:

• Old Way: You tell the robot, "Build a car." The robot guesses and builds a tricycle.
• New Way (BAG): You say, "Here is a blueprint for a Ferrari (a top-performing benchmark algorithm). Now, look at this blueprint and try to tweak it to make it even faster."

The robot takes that "Ferrari blueprint" (a known, strong algorithm) and uses it as a starting point. It doesn't start from scratch; it starts from a place of strength.

3. The Experiment: The Race

To prove this worked, they set up a massive race. They pitted their new "Mentor" method (BAG) against five other famous AI methods that try to design algorithms automatically.

They tested them on two different types of "obstacle courses":

1. The "PBO" Course: A maze made of binary switches (On/Off).
2. The "BBOB" Course: A smooth, rolling hill landscape where you have to find the highest peak.

The Result:
The "Mentor" method (BAG) won almost every time.

• It found better solutions faster.
• It was more consistent (it didn't have "bad days").
• It worked well even when they used different "brains" (different AI models like Google's Gemini, OpenAI's GPT, and Alibaba's Qwen).

4. Why This Matters: The "Strong Priors"

The paper's title mentions "Strong Priors." In everyday language, this just means "Strong Starting Points."

Think of it like learning to play chess.

• Weak Prior: You tell a beginner, "Just play randomly and see what happens." They will likely lose.
• Strong Prior: You show them a famous game played by a Grandmaster, and say, "Start with this opening move, then try to improve on it." They will learn much faster and play much better.

The paper proves that for AI to design complex algorithms, we shouldn't just ask it to "be creative." We should feed it the best existing solutions first, let it study them, and then ask it to refine them.

Summary

• The Insight: AI models don't care much about your long English instructions; they care deeply about the code examples you show them.
• The Fix: Give the AI a "cheat sheet" of the best existing algorithms to use as a starting point.
• The Outcome: This simple trick makes AI-designed optimization tools significantly smarter, faster, and more reliable than before.

It's a reminder that sometimes, the best way to innovate isn't to start from zero, but to stand on the shoulders of the giants (the benchmark algorithms) that came before.

Technical Summary

1. Problem Statement

The paper addresses the challenges in Automated Algorithm Design (AAD) using Large Language Models (LLMs). While LLMs have shown promise in evolving heuristics for black-box optimization (BBO), current approaches suffer from two main issues:

1. Lack of Interpretability: Search strategies in LLM-driven optimization are often guided by intuitive prompt designs (e.g., "create a novel algorithm") without a systematic understanding of which prompt components actually influence the generated code.
2. Inefficient Search: Existing methods often rely on massive sampling or population-based evolution without leveraging established prior knowledge (benchmark algorithms), leading to inefficient exploration of the algorithmic search space.

The core question is: How can we understand the influence of prompt elements on LLM-generated code, and how can we leverage this to guide LLMs toward more robust and efficient optimization?

2. Methodology

The authors propose a three-pronged methodology:

A. Token-wise Attribution Analysis (AttnLRP)

To understand why LLMs generate specific code, the authors apply AttnLRP (Attention-aware Layer-wise Relevance Propagation).

• Mechanism: They decompose the contribution of every input token in the prompt to the generated output tokens.
• Prompt Decomposition: Prompts are split into five components: Task Description, Strategy, Expected Output, Note (fitness values), and Parent Heuristics (Code + Description).
• Finding: The analysis reveals that code-related content (specifically the "Parent Heuristic" code and the "Strategy" instruction to refine it) has the strongest influence on the generated algorithm. Conversely, linguistic descriptions of tasks and fitness values (scores) have negligible impact on the code generation behavior.

B. Guiding Search with Strong Priors

Based on the finding that code examples are the primary driver of LLM behavior, the authors hypothesize that providing strong prior benchmark algorithms as examples can constrain the LLM's search to promising regions of the algorithmic space.

• Refinement Strategy: Instead of asking the LLM to "create" from scratch, they prompt it to "refine" a specific, high-performing benchmark algorithm.
• Hypothesis: This acts as a neighborhood search, where the LLM explores variations of a known good solution rather than wandering randomly.

C. Benchmark-Assisted Guided Evolutionary Approach (BAG)

The authors propose BAG, a new framework that integrates benchmark knowledge into the evolutionary loop:

1. Initialization: Instead of random sampling, the initial algorithm is selected from a set of top-performing benchmark algorithms ($A_{bench}$).
2. Variation: The LLM is queried to either:
   • Refine the current best algorithm ($A^*$).
   • Create a novel algorithm based on $A^*$.
   • Periodic Injection: Every $q$ iterations, the LLM is explicitly asked to refine a different algorithm randomly selected from $A_{bench}$. This prevents the search from getting stuck in a local pattern and reintroduces diversity from proven benchmarks.
3. Search Strategy: BAG utilizes a $(1+1)$ elitist search strategy (generating one offspring per iteration), contrasting with population-based methods used in other works (like EoH).

3. Key Contributions

1. First Token-wise Analysis in LLM-Driven AAD: The paper provides the first systematic analysis of prompt contributions in LLM-driven algorithm design using AttnLRP. It empirically proves that embedded code examples are the most critical factor, outweighing linguistic instructions or fitness scores.
2. Demonstration of Search Region Control: The authors demonstrate that by providing specific example codes, they can effectively steer LLMs toward specific regions of the algorithmic search space, acting as a form of "heuristic neighborhood search."
3. The BAG Framework: They introduce a benchmark-guided approach that outperforms state-of-the-art LLM-driven methods. BAG is simple, robust, and effectively fuses classical benchmarking practices with modern LLM capabilities.

4. Experimental Results

The methods were evaluated on two standard Black-Box Optimization (BBO) suites:

• PBO (Pseudo-Boolean Optimization): 23 discrete problems (100-dimensional).
• BBOB (Continuous Black-Box Optimization): 24 continuous problems (5-dimensional).

Performance Metrics:

• Metric: Area Under the ECDF Curve (AUC), normalized to the best possible performance.
• Models Tested: Three LLMs (Gemini 2.0 Flash, GPT-5 Nano, Qwen3 Coder Flash).
• Baselines: Compared against EoH, LHNS, LLaMEA, MCTS-AHD, and ReEvo.

Key Findings:

• Superior Performance: BAG consistently achieved the highest or near-highest performance across both suites and all three LLMs.
  • On PBO, BAG outperformed all baselines with Gemini and Qwen, and was only 0.5% behind the best (EoH) with GPT.
  • On BBOB, BAG showed a significant advantage, achieving an average 14% improvement over the second-best approach across all LLMs.
• Efficiency: BAG requires only a single LLM query per iteration to generate a candidate, whereas some baselines (like EoH) require multiple prompts to generate a single candidate.
• Convergence & Diversity: Analysis using CodeBLEU (a code similarity metric) showed that when BAG injects a new benchmark algorithm, the generated code shifts significantly (low similarity to previous generations), confirming that the benchmark injection successfully diversifies the search. Subsequent generations then converge on this new promising region.

5. Significance

• Paradigm Shift: The paper shifts the focus from "prompt engineering via natural language" to "prompt engineering via code examples." It suggests that the most effective way to guide an LLM in algorithm design is to show it how to code, not just what to code.
• Bridging Classical and Modern AI: It successfully integrates decades of classical optimization research (benchmark suites, algorithm selection) with the emerging field of LLM-driven design. This suggests that LLMs do not need to "reinvent the wheel" but can be highly effective when guided by existing human knowledge.
• Robustness: The method is robust across different LLM architectures and problem types (discrete and continuous), offering a practical, unified strategy for future automated algorithm design systems.

In conclusion, the paper argues that strong priors (high-quality benchmark algorithms) are essential for unlocking the full potential of LLMs in automated algorithm design, transforming them from random code generators into efficient, guided search engines.