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

• URL: http://arxiv.org/abs/2601.19622v1
• Date: Tue, 27 Jan 2026 13:55:58 GMT
• Title: Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search
• Authors: Thomas Bömer, Nico Koltermann, Max Disselnmeyer, Bastian Amberg, Anne Meyer,
• Abstract summary: Heuristic functions are essential to the performance of tree search algorithms as A*, where their accuracy and efficiency directly impact search outcomes.<n>Recent advances in large language models (LLMs) and evolutionary frameworks have opened the door to automated design.<n>We introduce a novel domain-agnostic prompt augmentation strategy that includes the A* code into the prompt to leverage in-context learning.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Landscape-aware Automated Algorithm Design: An Efficient Framework for Real-world Optimization [32.203665659052845]
  Large Language Models (LLMs) have opened new frontiers in automated algorithm design.<n>LLMs require extensive evaluation of the target problem to guide the search process.<n>This research proposes an innovative and efficient framework that decouples algorithm discovery from high-cost evaluation.
  arXiv  Detail & Related papers  (2026-02-04T13:18:45Z)
• Barbarians at the Gate: How AI is Upending Systems Research [58.95406995634148]
  We argue that systems research, long focused on designing and evaluating new performance-oriented algorithms, is particularly well-suited for AI-driven solution discovery.<n>We term this approach as AI-Driven Research for Systems ( ADRS), which iteratively generates, evaluates, and refines solutions.<n>Our results highlight both the disruptive potential and the urgent need to adapt systems research practices in the age of AI.
  arXiv  Detail & Related papers  (2025-10-07T17:49:24Z)
• Experience-Guided Reflective Co-Evolution of Prompts and Heuristics for Automatic Algorithm Design [124.54166764570972]
  Combinatorial optimization problems are traditionally tackled with handcrafted algorithms.<n>Recent progress has highlighted the potential of automatics design powered by large language models.<n>We propose the Experience-Evolution Reflective Co-Guided of Prompt and Heuristics (EvoPH) for automatic algorithm design.
  arXiv  Detail & Related papers  (2025-09-29T09:24:09Z)
• Evolving Prompts In-Context: An Open-ended, Self-replicating Perspective [65.12150411762273]
  We show that pruning random demonstrations into seemingly incoherent "gibberish" can remarkably improve performance across diverse tasks.<n>We propose a self-discover prompt optimization framework, PromptQuine, that automatically searches for the pruning strategy by itself using only low-data regimes.
  arXiv  Detail & Related papers  (2025-06-22T07:53:07Z)
• Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models [52.538586230181814]
  Recent studies exploited Large Language Models (LLMs) to autonomously generates for solving Combinatorial Optimization Problems (COPs)<n>The absence of task-specific knowledge in prompts often leads LLMs to provide unspecific search directions, obstructing derivation of well-performings.<n>We propose the Hercules algorithm, which leverages our designed Core Abstraction Prompting (CAP) method to abstract the core components from elite HGs and incorporate them as prior knowledge in prompts.
  arXiv  Detail & Related papers  (2025-05-19T02:20:46Z)
• Leveraging Large Language Models to Develop Heuristics for Emerging Optimization Problems [0.0]
  Combinatorial optimization problems often rely on algorithms to generate efficient solutions.<n>Recent advances in artificial intelligence have demonstrated the potential to automate generation through evolutionary frameworks.<n>We propose the Contextual Evolution of Heuristics framework, which incorporates problem-specific descriptions to enhance in-context learning.
  arXiv  Detail & Related papers  (2025-03-05T10:22:49Z)
• QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution [14.131178103518907]
  Quality-Uncertainty Balanced Evolution (QUBE) is a novel approach that enhances LLM+EA methods by redefining the priority criterion within the FunSearch framework.<n>QUBE employs the Quality-Uncertainty Trade-off Criterion (QUTC), based on our proposed Uncertainty-Inclusive Quality metric.<n>Through extensive experiments on challenging NP-complete problems, QUBE demonstrates significant performance improvements over FunSearch and baseline methods.
  arXiv  Detail & Related papers  (2024-12-30T04:05:22Z)
• Enhancing LLM Reasoning with Reward-guided Tree Search [95.06503095273395]
  o1-like reasoning approach is challenging, and researchers have been making various attempts to advance this open area of research.<n>We present a preliminary exploration into enhancing the reasoning abilities of LLMs through reward-guided tree search algorithms.
  arXiv  Detail & Related papers  (2024-11-18T16:15:17Z)
• Contractual Reinforcement Learning: Pulling Arms with Invisible Hands [68.77645200579181]
  We propose a theoretical framework for aligning economic interests of different stakeholders in the online learning problems through contract design. For the planning problem, we design an efficient dynamic programming algorithm to determine the optimal contracts against the far-sighted agent. For the learning problem, we introduce a generic design of no-regret learning algorithms to untangle the challenges from robust design of contracts to the balance of exploration and exploitation.
  arXiv  Detail & Related papers  (2024-07-01T16:53:00Z)
• Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model [22.64392837434924]
  EoH represents the ideas of thoughts in natural language, termed thoughts. They are translated into executable codes by Large Language Models (LLMs) EoH significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.
  arXiv  Detail & Related papers  (2024-01-04T04:11:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.