Overcoming the Weakest-Link Effect in LLM-Driven Program Optimization via Heterogeneous Edit Recombination

• URL: http://arxiv.org/abs/2607.28947v1
• Date: Fri, 31 Jul 2026 02:05:45 GMT
• Title: Overcoming the Weakest-Link Effect in LLM-Driven Program Optimization via Heterogeneous Edit Recombination
• Abstract summary: HERO is a program that generates diverse, non-overlapping atomic edits and then systematically selects and composes them into coherent program improvements using evaluator scores.<n>We evaluate HERO across algorithmic problems, strategy games, the design of LLM-based agentic systems, and robotic path planning.
• Score: 59.679182823718556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language models (LLMs) are increasingly used to solve complex problems by searching over program space, offering a general paradigm for scientific problems that can be naturally represented and solved as programs. Despite recent progress, identifying effective optimization directions for a candidate program remains challenging. By analogy with automatic differentiation, existing methods typically guide the search using a textual ``gradient'': a first-order update direction expressed as textual edits. Such gradients are inferred either from previously evaluated programs or from LLM-generated feedback on the implicit program-score mapping. However, these estimates become increasingly unreliable as the program--score mapping grows more complex, limiting their practical utility. We argue that explicit gradients are not essential for effective program optimization. Leveraging their prior knowledge, LLMs can propose plausible atomic edits directly from the current program, thereby enabling a zeroth-order optimization strategy. However, zeroth-order search suffers from a \textit{weakest-link effect}: when a bundle of edits is accepted or rejected as a whole, a single harmful edit can negate the benefits of all remaining edits. To address this issue, we introduce HERO, a program optimizer that prompts an LLM to generate diverse, non-overlapping atomic edits and then systematically selects and composes them into coherent program improvements using evaluator scores. We evaluate HERO across algorithmic problems, strategy games, the design of LLM-based agentic systems, and robotic path planning. Across these domains, HERO consistently discovers higher-scoring programs and converges substantially faster than prior LLM-based optimizers, while consuming fewer tokens.

Related papers

• Property-Guided LLM Program Synthesis for Planning [6.88204255655161]
  Instead of scoring programs after evaluation, we check whether a candidate satisfies a formally defined property.<n>This feedback drastically reduces both the number of program generations and the evaluation cost.
  arXiv  Detail & Related papers  (2026-05-15T16:23:35Z)
• LLM-Guided Genetic Improvement: Envisioning Semantic Aware Automated Software Evolution [39.24798235257764]
  Genetic Improvement (GI) of software automatically creates alternative software versions that are improved according to certain properties of interests.<n>Large Language Models (LLMs) offer semantic-aware edits, yet lack goal-directed feedback and control.<n>We propose the investigation of a new research line on AI-powered GI aimed at incorporating semantic aware search.
  arXiv  Detail & Related papers  (2025-08-25T14:49:29Z)
• Grammar-Guided Evolutionary Search for Discrete Prompt Optimisation [63.97051732013936]
  We propose an evolutionary search approach to automated discrete prompt optimisation consisting of two phases.<n>In the first phase, grammar-guided genetic programming is invoked to synthesise prompt-creating programmes.<n>In the second phase, local search is applied to explore the neighbourhoods of best-performing programmes.
  arXiv  Detail & Related papers  (2025-07-14T14:34:15Z)
• LLM Program Optimization via Retrieval Augmented Search [71.40092732256252]
  We propose a blackbox adaptation method called Retrieval Augmented Search (RAS) that performs beam search over candidate optimizations.<n>We show that RAS performs 1.8$times$ better than prior state-of-the-art blackbox adaptation strategies.<n>We also propose a method called AEGIS for improving interpretability by decomposing training examples into "atomic edits"
  arXiv  Detail & Related papers  (2025-01-31T06:34:47Z)
• Counterexample Guided Program Repair Using Zero-Shot Learning and MaxSAT-based Fault Localization [0.0]
  Automated Program Repair (APR) for introductory programming assignments (IPAs) is motivated by the large number of student enrollments.<n>We propose a novel approach that combines the strengths of both FM-based fault localization and Large Language Models (LLMs)<n>Our method uses MaxSAT-based fault localization to identify buggy parts of a program, then presents the LLM with a program sketch devoid of these buggy statements.
  arXiv  Detail & Related papers  (2024-12-19T12:08:44Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  Large language models (LLMs) have achieved great success across diverse tasks, and fine-tuning is sometimes needed to further enhance generation quality.<n>To handle these challenges, a direct solution is to generate high-confidence'' data from unsupervised downstream tasks.<n>We propose a novel approach, pseudo-supervised demonstrations aligned prompt optimization (PAPO) algorithm, which jointly refines both the prompt and the overall pseudo-supervision.
  arXiv  Detail & Related papers  (2024-10-04T03:39:28Z)
• LLM as a Complementary Optimizer to Gradient Descent: A Case Study in Prompt Tuning [69.95292905263393]
  We show that gradient-based and high-level LLMs can effectively collaborate a combined optimization framework.<n>In this paper, we show that these complementary to each other and can effectively collaborate a combined optimization framework.
  arXiv  Detail & Related papers  (2024-05-30T06:24:14Z)
• Can You Improve My Code? Optimizing Programs with Local Search [25.436793960409926]
  Program Optimization with Locally Improving Search (POLIS) exploits the structure of a program, defined by its lines. POLIS improves a single line of the program while keeping the remaining lines fixed, using existing brute-force synthesis algorithms, and continues iterating until it is unable to improve the program's performance.
  arXiv  Detail & Related papers  (2023-07-10T20:39:41Z)
• Automatic Prompt Optimization with "Gradient Descent" and Beam Search [64.08364384823645]
  Large Language Models (LLMs) have shown impressive performance as general purpose agents, but their abilities remain highly dependent on prompts. We propose a simple and nonparametric solution to this problem, Automatic Prompt Optimization (APO) APO uses minibatches of data to form natural language "gradients" that criticize the current prompt. The gradients are then "propagated" into the prompt by editing the prompt in the opposite semantic direction of the gradient.
  arXiv  Detail & Related papers  (2023-05-04T15:15:22Z)

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.