Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search

AI summary

Overview

Research area: Automated heuristic design using large language models, applied to A* search for combinatorial optimization — specifically the Unit-Load Pre-Marshalling Problem (UPMP) and the Sliding Puzzle Problem (SPP).

Technical level: Intermediate. Readers need basic familiarity with A* search (g, h, f values), heuristics, and how LLM prompting/evolutionary loops work, but the paper is written accessibly.

Scope: The paper introduces A-CEoH, a prompt-augmentation strategy that embeds A* algorithm code into the LLM prompt, and benchmarks it against the base Evolution of Heuristics (EoH) framework and a problem-context variant (P-CEoH) across two problem domains and three LLMs.

Publication details: arXiv:2601.19622v1 [cs.AI], 27 Jan 2026, licensed CC BY 4.0. Authors are affiliated with Karlsruhe Institute of Technology and TU Dortmund University. Code is available at https://github.com/tb-git-tud/a-ceoh-evolution-of-heuristics.

What This Paper Is About

A* search depends heavily on a heuristic function that estimates the cost from a state to the goal; good heuristics make search fast and accurate, bad ones make it slow or unable to find solutions. Traditionally these heuristics are handcrafted by experts with deep domain knowledge. This paper asks whether LLMs inside an evolutionary loop can automatically write high-quality A* guiding heuristics, and whether showing the LLM the actual A* source code in the prompt (rather than only describing the problem) makes that generation substantially better.

Key Contributions

1. New application field: Demonstrating that LLM-based automated heuristic design can evolve an A* guiding heuristic, both for a niche optimization problem (UPMP) and a canonical benchmark (SPP).
2. Algorithmic-Contextual Evolution of Heuristics (A-CEoH): A domain-agnostic prompt augmentation that embeds key elements of the A* algorithm code into the prompt, leveraging in-context learning so the LLM generates heuristics aligned with A*'s search dynamics.
3. Performance boost for small models: Showing that algorithmic context enables a small, locally deployable model (Qwen2.5-Coder:32b) to outperform a much larger general-purpose model (GPT4o:2024-08-06).
4. Outperforming handcrafted heuristics: Comparing LLM-generated heuristics against hand-crafted and optimal A* implementations from the literature, showing superiority for the target instance configurations.

Main Findings

• UPMP results: A-CEoH consistently outperforms the EoH baseline in both the best-found heuristic and median fitness across all evaluated models. The combined variant PA-CEoH delivers the best overall results across all tested models, and multiple runs reach a best reachable fitness value of 0.0815.
• SPP results: Qwen2.5-Coder:32b benefits most from A-CEoH, producing the best SPP heuristic in the study with a fitness value of 0.445. P-CEoH did not improve heuristic quality for Qwen2.5-Coder:32b on SPP. GPT4o:2024-08-06 achieved only moderate improvements through prompt augmentation and failed to surpass a fitness value of 0.6, suggesting convergence to a local optimum. Gemma2:27b struggled to produce competitive SPP heuristics except in a few isolated runs in the P-CEoH setup.
• Smaller beats larger: The smaller, coding-oriented Qwen2.5-Coder:32b generated significantly stronger heuristics than the larger GPT4o:2024-08-06, especially with the A-CEoH prompt context.
• Convergence behavior (UPMP, Qwen2.5-Coder:32b): A-CEoH produced reasonably good heuristics early in the evolutionary process but showed difficulty converging toward better fitness values. P-CEoH runs began similarly to base EoH but allowed the model to identify improvements more reliably. PA-CEoH combined both strengths — early quality plus reliable improvement.
• Versus optimal A on UPMP (Table 2):* On training seeds 0–9, both the PA-CEoH Qwen2.5-Coder:32b and GPT4o:2024-08-06 heuristics solved 10 of 10 instances with fitness 0.0815, matching the optimal implementation's 10 of 10 and 0.0815, while solving faster (0.0888 s and 0.1953 s versus 0.2773 s). On 30 additional test instances (seeds 10–39), the LLM-generated heuristics each solved 30, while the optimal implementation solved 27.
• Versus human heuristics on SPP (Table 3): The A-CEoH Qwen2.5-Coder:32b heuristic solved 10 of 10 instances for seeds 0–9, whereas the hybrid heuristic solved 5 and the optimal implementation solved 5. Restricted to the five instances solved by both the optimal approach and the LLM-generated heuristic, the LLM heuristic reached a fitness of 0.281, a 0.031 gap to the optimal value of 0.252.
• Token cost: Adding contextual information substantially increases input tokens. PA-CEoH uses roughly twice the input tokens of EoH while generally reducing output tokens, indicating more focused generation. For Qwen2.5-Coder:32b on UPMP, input tokens go from 1046 (EoH) to 2223 (PA-CEoH); on SPP, from 1477 to 3330.

Methodology in Plain English

The researchers build on the Evolution of Heuristics (EoH) framework, which evolves candidate heuristics over generations. Each heuristic is a pair: a "thought" (natural-language reasoning) and executable Python code with a defined input–output interface. A pretrained LLM is prompted using five strategies — an initialization prompt (I1), two exploration prompts (E1, E2), and two modification prompts (M1, M2) — and the resulting heuristics are scored on problem instances by a fitness function that measures average relative deviation from a lower bound. Top performers are retained into the next generation.

The paper varies what goes into the prompt across four configurations, all sharing the same evolutionary procedure and heuristic representation:

• EoH: the base framework only.
• P-CEoH: adds an "additional problem description" — expected input data structure, interpretation of problem components, problem-specific constraints, and illustrative input/output examples.
• A-CEoH (new): adds an "algorithmic context" instead — the complete A* driver procedure (open list initialization, node expansion, goal detection, the f(n) = g(n) + h(n) combination, timeout and node-cap checks), plus the core methods that define the search space: is_goal(), get_neighbors(), reconstruct_path(), and get_objective_value(). Because this structure is domain-agnostic, the same prompt format applies to different problems by substituting the corresponding functions.
• PA-CEoH: includes both augmentations.

Prompts also contain a task description, parent heuristic code with thoughts (except for I1), strategy-specific output instructions, and additional instructions including a self-consistency requirement that the code match its stated thought.

Experimental setup: Each framework version was run ten times per LLM for the UPMP and five times per LLM for the SPP. I1 was called 40 times, with the 20 best heuristics forming the initial population. Heuristics evolved over 20 generations, with E1, E2, M1, and M2 each invoked 20 times per generation, yielding 20 × 4 × 20 = 1600 prompts per run. The number of parent heuristics for E1 and E2 was set to 5.

Evaluation: For the UPMP, a 60 s time limit and a 100,000-node limit per instance, with unsolved instances penalized at m_max = 100; instances use a single-bay 5 × 5 layout (one tier, north access), five priority classes, and a 60 % fill rate. For the SPP, a 60 s time limit and a 1,000,000-node limit, with unsolved instances penalized at m_max = 200; the study uses large 20 × 20 puzzles generated by 200 random moves, a scale where pattern-database heuristics become impractical. Both problems use ten training instances (seeds 0–9). Experiments ran on an AMD EPYC 7401P with 64 GB RAM. For the human-comparison experiments, solution time was limited to 600 seconds, and fitness and solution time are reported as averages over solved instances.

Why This Matters

Impact on research: This work shifts LLM-based automated heuristic design away from constructive greedy heuristics (where TSP and Online Bin Packing have become standard benchmarks) toward structured tree search with A*. It shows that the algorithmic environment itself — not just the problem description — is a valuable prompt ingredient, and that prompt design can matter more than model scale. It also isolates the effect of prompt augmentation by holding the EoH base framework constant, preserving comparability with prior work such as P-CEoH.

Real-world applications:

• Warehouse logistics: sorting unit loads in block-stacking warehouses served by autonomous robots, where blocking items must be shuffled without new loads entering or leaving.
• Maritime port operations: the conceptually related Container Pre-Marshalling Problem, where containers in a bay are rearranged until target stacks are free of blockages.
• Large-scale state-space planning: puzzle-style and grid-based reconfiguration tasks too large for memory-heavy pattern-database heuristics, such as 20 × 20 sliding puzzles.
• Automated algorithm engineering more broadly, where experts are scarce and handcrafted heuristics perform poorly on specific instance configurations.

Industry relevance: The finding that a smaller, locally deployable model (Qwen2.5-Coder:32b) matches or beats a large general-purpose model matters for companies that cannot or prefer not to send data to external LLM providers. The token-cost trade-off is also commercially relevant: contextual prompting roughly doubles input tokens but reduces output tokens and produces more focused generation.

Future Directions

• Extending the problem-agnostic idea of algorithmic context to additional combinatorial optimization problems beyond the UPMP and SPP.
• Applying the approach to other algorithmic frameworks, such as large neighborhood search, as the authors explicitly state.
• Investigating why A-CEoH on the UPMP produces good heuristics early but struggles to converge toward better fitness values, and whether other evolutionary operators or reflection mechanisms could close that gap.
• Testing whether the model-size-versus-prompt-structure trade-off observed with Qwen2.5-Coder:32b, GPT4o:2024-08-06, and Gemma2:27b generalizes to other LLMs.

Target Audience

Researchers and practitioners in automated algorithm design, heuristic search, and LLM-driven code generation; operations research and logistics engineers interested in warehouse pre-marshalling and container terminal optimization; and machine learning engineers who want to apply LLMs to generate domain-specific heuristics without large-scale fine-tuning. Readers with a basic grasp of A* search and prompt engineering will get the most from it.

Authors’ abstract

Heuristic functions are essential to the performance of tree search algorithms such as A*, where their accuracy and efficiency directly impact search outcomes. Traditionally, such heuristics are handcrafted, requiring significant expertise. Recent advances in large language models (LLMs) and evolutionary frameworks have opened the door to automating heuristic design. In this paper, we extend the Evolution of Heuristics (EoH) framework to investigate the automated generation of guiding heuristics for A* search. We introduce a novel domain-agnostic prompt augmentation strategy that includes the A* code into the prompt to leverage in-context learning, named Algorithmic - Contextual EoH (A-CEoH). To evaluate the effectiveness of A-CeoH, we study two problem domains: the Unit-Load Pre-Marshalling Problem (UPMP), a niche problem from warehouse logistics, and the classical sliding puzzle problem (SPP). Our computational experiments show that A-CEoH can significantly improve the quality of the generated heuristics and even outperform expert-designed heuristics.