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

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 27 Jan 2026.

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

- [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 Evolutionary Optimizers](https://mlsanity.com/paper/2310.19046/) (2023)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design](https://mlsanity.com/paper/2508.03082/) (2025)
- [Beyond Accuracy: Evaluating Self-Consistency of Code Large Language Models with IdentityChain](https://mlsanity.com/paper/2310.14053/) (2023)
- [CALM: Co-evolution of Algorithms and Language Model for Automatic Heuristic Design](https://mlsanity.com/paper/2505.12285/) (2025)
- [Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem](https://mlsanity.com/paper/1709.09972/) (2017)
- [Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2505.12627/) (2025)
- [LLM-Driven Instance-Specific Heuristic Generation and Selection](https://mlsanity.com/paper/2506.00490/) (2025)
- [Beyond the Hype: Benchmarking LLM-Evolved Heuristics for Bin Packing](https://mlsanity.com/paper/2501.11411/) (2025)
- [Solving the unit-load pre-marshalling problem in block stacking storage systems with multiple access directions](https://mlsanity.com/paper/2207.09118/) (2022)
- [Sorting multibay block stacking storage systems](https://mlsanity.com/paper/2405.04847/) (2024)
- [Optimizing Photonic Structures with Large Language Model Driven Algorithm Discovery](https://mlsanity.com/paper/2503.19742/) (2025)
- [The Fifteen Puzzle- A New Approach through Hybridizing Three Heuristics Methods](https://mlsanity.com/paper/2302.02985/) (2023)

## Built on by (most cited first, 1 of 1)

- [CoupleEvo: Evolving Heuristics for Coupled Optimization Problems Using Large Language Models](https://mlsanity.com/paper/2605.06341/) (2026)

## Abstract (arXiv)

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.