이종 편집 재조합을 통한 LLM 기반 프로그램 최적화에서 발생하는 약한 고리 효과 극복

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

대규모 언어 모델(LLM)은 복잡한 문제를 해결하기 위해 프로그램 공간을 탐색하는 데 점점 더 많이 사용되고 있으며, 이는 자연스럽게 프로그램으로 표현되고 해결될 수 있는 과학 문제에 대한 일반적인 패러다임을 제공합니다. 최근의 발전에도 불구하고 후보 프로그램에 대한 효과적인 최적화 방향을 식별하는 것은 여전히 어려운 과제입니다. 자동 미분과 유사하게, 기존 방법은 일반적으로 텍스트 기반 "기울기"를 사용하여 검색을 안내하는데, 이는 텍스트 편집으로 표현된 1차 업데이트 방향입니다. 이러한 기울기는 이전 평가 프로그램에서 추론되거나 LLM이 생성한 피드백을 통해 암시적인 프로그램-점수 매핑으로부터 추론됩니다. 그러나 프로그램-점수 매핑이 복잡해짐에 따라 이러한 추정치는 점점 더 신뢰성이 떨어지므로 실제 유용성이 제한됩니다. 우리는 효과적인 프로그램 최적화를 위해서는 명시적인 기울기가 필수적이지 않다고 주장합니다. LLM은 사전 지식을 활용하여 현재 프로그램에서 직접 타당한 원자 편집을 제안할 수 있으며, 이를 통해 0차 최적화 전략을 가능하게 합니다. 그러나 0차 검색은 "약한 고리 효과"를 겪습니다. 즉, 일련의 편집이 전체적으로 수락되거나 거부될 때, 하나의 유해한 편집은 나머지 모든 편집의 이점을 상쇄할 수 있습니다. 이러한 문제를 해결하기 위해, 우리는 LLM에게 다양한 중복되지 않는 원자 편집을 생성하도록 지시하고, 평가 점수를 사용하여 이를 체계적으로 선택하고 조립하여 일관된 프로그램 개선을 수행하는 프로그램 최적화기인 HERO를 소개합니다. 우리는 알고리즘 문제, 전략 게임, LLM 기반 에이전트 시스템 설계 및 로봇 경로 계획 분야에서 HERO를 평가했습니다. 이러한 모든 영역에서 HERO는 기존의 LLM 기반 최적화기에 비해 더 높은 점수를 가진 프로그램을 지속적으로 발견하고 훨씬 빠르게 수렴하며, 토큰 사용량도 줄입니다.

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.