# Breaking Validity-Induced Boundaries to Expand Algorithm Search Space: A Two-Stage AST-Based Operator for LLM-Driven Automated Heuristic Evolution

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 22 references that are in the map.
- First posted on arXiv 3 Apr 2026.

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

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Does Prompt Formatting Have Any Impact on LLM Performance?](https://mlsanity.com/paper/2411.10541/) (2024)
- [Unleashing the potential of prompt engineering for large language models](https://mlsanity.com/paper/2310.14735/) (2023)
- [Multi-objective Evolution of Heuristic Using Large Language Model](https://mlsanity.com/paper/2409.16867/) (2024)
- [EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design](https://mlsanity.com/paper/2508.03082/) (2025)
- [Revisiting Code Similarity Evaluation with Abstract Syntax Tree Edit Distance](https://mlsanity.com/paper/2404.08817/) (2024)
- [HiFo-Prompt: Prompting with Hindsight and Foresight for LLM-based Automatic Heuristic Design](https://mlsanity.com/paper/2508.13333/) (2025)
- [The Heuristic Core: Understanding Subnetwork Generalization in Pretrained Language Models](https://mlsanity.com/paper/2403.03942/) (2024)
- [LLMs as Repositories of Factual Knowledge: Limitations and Solutions](https://mlsanity.com/paper/2501.12774/) (2025)
- [Abstract Syntax Tree for Programming Language Understanding and Representation: How Far Are We?](https://mlsanity.com/paper/2312.00413/) (2023)
- [TIDE: Tuning-Integrated Dynamic Evolution for LLM-Based Automated Heuristic Design](https://mlsanity.com/paper/2601.21239/) (2026)
- [From Heuristic Selection to Automated Algorithm Design: LLMs Benefit from Strong Priors](https://mlsanity.com/paper/2603.02792/) (2026)

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

- [UnitBoost: Managing Compound LLM Systems with a Merge Operator, Not a Model](https://mlsanity.com/paper/2609.09815/) (2026)

## Abstract (arXiv)

Large Language Model (LLM) based automated heuristic design (AHD) has shown great potential in discovering efficient heuristics. Most existing LLM-AHD frameworks use semantic evolutionary operators that rely entirely on the LLM's pre-trained knowledge. These one-stage methods strictly require the generated code to be valid during the operation and often rely on a ``thought-code'' representation. We argue that this end-to-end generation fundamentally limits the exploration ability within the algorithm search space. In this paper, we propose a two-stage, structure-based evolutionary operator for LLM-AHD. In the first stage, our approach directly performs crossover and mutation on the Abstract Syntax Trees (ASTs) of the heuristic code, intentionally generating diverse but often invalid structural variants. In the second stage, the LLM is employed to repair these invalid heuristics into executable, high-quality code. Depending on the underlying framework, either the raw invalid variants or the repaired heuristics are integrated into the population to preserve potential structural patterns. We demonstrate that the proposed operator can significantly enhance the search ability of state-of-the-art LLM-AHD algorithms, such as EoH-S. Experimental results on the Traveling Salesman Problem (TSP) and the Online Bin Packing Problem (OBP) show that our method effectively improves both optimization performance and convergence speed.