🤖 machine learning

Heuristic Search as Language-Guided Program Optimization

This paper proposes a structured, modular framework for Large Language Model-driven Automated Heuristic Design that decomposes the discovery process into distinct evaluation, feedback, and refinement stages, enabling systematic improvements and outperforming existing methods across diverse combinatorial optimization domains.

Original authors: Mingxin Yu, Ruixiao Yang, Chuchu Fan

Published 2026-02-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mingxin Yu, Ruixiao Yang, Chuchu Fan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart, but slightly chaotic, robot chef how to cook the perfect meal for a thousand different customers. Each customer has weird dietary restrictions (constraints) and wants the meal to be as cheap and tasty as possible (optimization).

In the past, we tried to teach this robot by just saying, "Here's a recipe, try to make it better," and then hoping it accidentally stumbled upon a genius idea. Sometimes it worked, but often the robot just kept making the same mistakes or got stuck trying to fix one tiny detail while ignoring the whole meal.

This paper introduces a new, structured way to teach the robot, called LaGO (Language-Guided Optimization). Think of it as turning the robot's cooking process from a game of "guess and check" into a professional, three-step training program.

Here is how LaGO works, using our kitchen analogy:

1. The Old Way: The "Black Box" Guess

Previously, researchers would ask the AI (the robot chef) to write a whole new recipe from scratch.

The Problem: If the recipe failed, the AI just got a score like "6/10." It didn't know why it failed. Was the salt too salty? Did it forget the oven? Was the timing wrong?
The Result: The AI would randomly tweak the recipe, hoping to get lucky. It was like trying to fix a broken car by randomly hitting it with a hammer until it started.

2. The New Way: The LaGO Framework

The authors realized that to get better, the AI needs a structured process. They broke the learning loop into three distinct roles, like a professional kitchen team:

Step A: The Taste Test (Forward Pass)

The AI writes a new recipe (a computer program/heuristic) and tries to cook the meal on a few test customers.

What happens: The robot doesn't just get a score. It records a "trace" of what happened. Did the oven burn the bread? Did the chef run out of time? Did the customer get a stomach ache because of a hidden nut?
The Analogy: This is like a food critic eating the dish and writing a detailed log of every bite, noting exactly where the flavor went wrong.

Step B: The Expert Analyst (Backward Pass)

This is the biggest innovation. Instead of just giving the AI a number, a second AI (the Analyst) reads the "trace" log and writes a diagnostic report.

What happens: The Analyst says, "You failed on the spicy dishes because you didn't adjust the heat for large batches," or "Your recipe works for small groups but falls apart for big ones."
The Analogy: This is like a head chef looking at the food critic's notes and saying, "Ah, I see the problem! You're adding the salt too early. Here is a specific rule to fix that." It turns vague failure into actionable advice.

Step C: The Creative Chef (Update Step)

Now, the main AI (the Generator) takes the original recipe, the test results, and the Analyst's specific advice to write a new version of the recipe.

What happens: It doesn't just guess randomly. It uses the advice to make a "directed jump" toward a better solution.
The Analogy: The chef reads the head chef's notes and says, "Okay, I'll try adding the salt at the end and doubling the heat for large orders."

3. The Secret Sauce: Co-Evolving the Team

The paper also mentions that they don't just optimize the "cooking" part; they optimize the "prep" part too.

The Analogy: Imagine the robot has two jobs: Prep (chopping veggies, getting ingredients ready) and Cooking (frying, baking).
The Innovation: In the past, people only tried to improve the cooking while keeping the prep random. LaGO improves both at the same time. It realizes that if the prep is bad, the cooking can't be good. By training them together, they learn to work in sync, like a well-oiled kitchen team.

4. Why This Matters

The researchers tested this on four very difficult real-world problems:

Delivery Routes: Figuring out how to deliver packages to hundreds of houses without running out of gas or time.
Airline Crews: Scheduling pilots and flight attendants so everyone gets enough rest and follows strict safety laws.
Chip Design: Arranging tiny electronic parts on a computer chip to make it run faster.
Supercomputer Scheduling: Deciding how to split a giant math problem across many computers so it finishes quickly.

The Result: In all these tests, the LaGO method beat the previous best methods. It found better solutions, made fewer mistakes, and didn't get stuck in "local traps" (where it thinks it's done, but it's actually far from the best answer).

The Big Picture

Think of this paper as moving from random trial-and-error to systematic engineering.

Before: "Here is a problem. AI, guess a solution. If it's bad, guess again."
Now: "Here is a problem. AI, try a solution. Analyze exactly why it failed. Explain the failure to the AI. AI, use that explanation to build a smarter solution."

By separating the "doing," the "analyzing," and the "fixing" into clear steps, the authors created a system that learns faster, understands deeper, and solves harder problems than ever before. It's the difference between a student who just memorizes answers and a student who understands why the answers are what they are.

1. Problem Statement

Automated Heuristic Design (AHD) aims to automatically discover effective strategies for solving complex Combinatorial Optimization (CO) problems, reducing the need for manual domain expertise. While Large Language Models (LLMs) have advanced AHD by generating executable code, current state-of-the-art methods suffer from significant limitations:

Tightly Coupled Pipelines: Existing approaches often treat evaluation, feedback, and code updates as a single, intertwined loop. This "black box" nature makes it difficult to isolate the contribution of specific components or systematically improve the design process.
Limited Feedback: Many methods rely on scalar fitness values or coarse textual reflections, which fail to capture the structural reasons why a heuristic succeeds or fails.
Poor Generalization: Heuristics often overfit to training instances or fail to generalize to unseen, complex problem domains with strict feasibility constraints.
Mode Collapse: Evolutionary search processes driven by LLMs often converge prematurely to a single local optimum, losing diversity in the search space.

The authors propose reformulating AHD not as a stochastic evolutionary search, but as an explicit optimization problem over a discrete program space, drawing parallels to gradient-based learning in deep learning.

2. Methodology: The LaGO Framework

The authors introduce LaGO (Language-Guided Optimization), a modular framework that decomposes the heuristic discovery process into three distinct stages, analogous to the forward pass, backward pass, and parameter update in neural network training.

Core Architecture

Forward Pass (Evaluation):
- Takes a candidate heuristic program ( $\theta$ ) and injects it into a predefined algorithm skeleton.
- Executes the heuristic on a training set of problem instances ( $D_{train}$ ).
- Generates Execution Traces ( $\mathcal{E}$ ), which include runtime errors, generated solutions, and intermediate states.
Backward Pass (Analyst):
- Instead of returning a simple scalar score, an Analyst module (powered by an LLM) analyzes the execution traces.
- It synthesizes Structured Feedback ( $\Delta$ $Δ$ ), termed a "semantic gradient." This feedback can include:
  - Executable Feature Functions: The Analyst writes Python code to compute specific structural features (e.g., constraint violation patterns, solution density) that distinguish good solutions from bad ones.
  - Distributional Statistics: It returns tuples containing fitness, feature ranges, means, and signatures of best/worst performing instances.
- This decouples the feedback mechanism from the objective function, allowing for rich, qualitative insights to guide the search.
Update Step (Generator):
- A Generator module (LLM) receives the current population of heuristics and the structured feedback ( $\Delta$ ).
- It performs Reasoned Evolution: Instead of blind mutation, it uses the feedback to synthesize new candidates that conceptually represent a "directed jump" in the search space.
- Diversity-Aware Management: To prevent mode collapse, the generator employs a diversity-aware strategy. It selects parents based on behavioral diversity (Euclidean distance in performance vectors) rather than just fitness, and maintains a diverse population by balancing high-performing individuals with structurally distinct ones.

Key Design Choices

Co-evolution: LaGO jointly optimizes two components:
- Constructive Heuristic ( $\theta_{cons}$ ): Generates initial solutions to place the search in a promising region of the landscape.
- Refinement Heuristic ( $\theta_{ref}$ ): Performs local search (e.g., Large Neighborhood Search) to improve solutions.
- Benefit: This allows the discovery of synergistic strategies (e.g., a constructive heuristic that creates specific "gaps" the refinement heuristic is designed to fill).
Code-Writing Analyst: The Analyst dynamically generates feature functions to analyze the problem structure, providing feedback that is more precise than natural language reflection alone.

3. Key Contributions

Unified Framework (LaGO): Formalizes LLM-based AHD as a structured, language-guided optimization problem with explicit forward, backward, and update modules.
Modular Upgrades: Demonstrates that popular existing methods (EoH, ReEvo, LLM-LNS) are restricted instantiations of LaGO. By integrating LaGO's modules (e.g., code-based feedback, joint optimization) into these baselines, performance can be significantly upgraded.
Executable Feedback Mechanism: Introduces a novel backward pass where the LLM writes code to extract structural features, providing a "semantic gradient" that guides the generator more effectively than scalar rewards.
Diversity-Aware Population Management: A strategy to maintain behavioral diversity in the heuristic population, mitigating mode collapse and improving long-horizon exploration.

4. Experimental Results

The framework was validated on four diverse real-world CO domains from the HeuriGym benchmark:

Pickup and Delivery with Time Windows (PDPTW)
Airline Crew Pairing
Technology Mapping (EDA)
Intra-Operator Parallelism Scheduling

Performance Metrics:

Metric: Quality-Yield Index (QYI), a harmonic mean of solution quality and feasibility (yield).
Results: LaGO consistently outperformed state-of-the-art baselines (HeuriGen, EoH, ReEvo, LLM-LNS).
- On the highly constrained PDPTW task, LaGO achieved a QYI of 0.808 on the test set, significantly outperforming the best baseline (EoH at 0.314) by a large margin.
- On Airline Crew Pairing, LaGO achieved 0.918 vs. 0.853 for the best baseline.
- Generalization: LaGO showed a much smaller performance drop between training and testing sets (generalization gap of 0.07 vs. 0.24 for baselines), indicating better transferability.

Ablation Studies:

Joint Optimization: Optimizing both constructive and refinement heuristics together yielded massive gains (e.g., +0.3 QYI on EoH), solving the "cold start" problem where baselines get stuck in bad local minima.
Analyst Module: Adding the code-writing analyst significantly improved methods relying on scalar feedback (EoH, LLM-LNS) but had marginal effects on ReEvo (which already uses text reflection), confirming the value of structured feedback.
Diversity Management: Crucial for preventing mode collapse, especially in ReEvo.

5. Significance and Impact

Paradigm Shift: Moves the field from ad-hoc, tightly coupled evolutionary loops to a principled, modular optimization framework. This allows researchers to systematically analyze and improve specific components of the heuristic design pipeline.
Scalability: The framework is model-agnostic (tested on GPT-4.1-mini and Gemini-3-Flash) and shows positive scaling with more capable LLMs, suggesting it leverages the reasoning capabilities of next-generation models effectively.
Real-World Applicability: Unlike TSP (a well-studied problem where gains are marginal), LaGO excels in complex, under-explored domains with irregular constraints (logistics, EDA, compiler optimization), where hand-crafted heuristics are often insufficient.
Foundation for Future Research: Provides a common abstraction for comparing and extending AHD methods, paving the way for dynamic component selection and alternative feedback modalities.

In summary, LaGO transforms heuristic discovery from a "black box" evolutionary process into a transparent, structured optimization loop, leveraging the code-generation and reasoning capabilities of LLMs to solve complex, constrained real-world problems more effectively than previous methods.