기호형 AI 계획을 위한 LLM 진화 도메인 독립적 휴리스틱
LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning
한국어 초록
휴리스틱 탐색(heuristic search)은 기호형(symbolic) AI 계획에서 지배적인 패러다임이며, 가장 강력한 휴리스틱(heuristics)은 계획 연구자들의 수십 년간의 작업 결과물입니다. 최근 연구에서는 대규모 언어 모델(LLM)이 개별 계획 도메인(planning domains)에 대한 휴리스틱을 설계할 수 있음을 보여주었으나, 임의의 계획 작업(planning tasks)에서 작동하는 LLM 생성 휴리스틱은 아직 없습니다. 본 논문에서는 우리는 진화 탐색(evolutionary search)을 사용하여 수작업으로 설계된 최신 기술(state of the art)을 능가하는 최초의 LLM 생성 도메인 독립적 휴리스틱(domain-independent heuristics)을 생성합니다. 우리는 C++로 작성된 상위 휴리스틱(parent heuristics)을 LLM이 변이(mutation)하도록 하고, 후보들을 정보성(informedness)과 속도를 키로 하는 MAP-Elites 아카이브에 저장하며, 적합도 점수(fitness scores)는 커버리지(coverage)와 해결 시간(solving time)을 혼합하여 계산합니다. 진화된 프로그램들을 맥락에 맞게 배치하기 위해, 우리는 추가로 다양한 수작업 휴리스틱(hand-engineered heuristics) 세트를 그들의 정보성-속도 트레이드오프(informedness-speed tradeoff)에 대해 벤치마킹(benchmark)했는데, 이는 우리가 아는 한 이전에 수행된 적이 없습니다. 보이지 않는 테스트 도메인(unseen testing domains)에서, 우리의 최고 진화 휴리스틱은 가장 강력한 기준선(baseline)조차 능가하여 더 많은 작업을 해결하며, 우리의 전체 휴리스틱 스위트(heuristic suite)는 해당 트레이드오프의 파레토 프론티어(Pareto frontier)를 포괄합니다. 또한 우리는 사소한 맹목 휴리스틱(blind heuristic)에서 진화를 시드(seeding)하는 것이 강력한 FF 휴리스틱에서 시드하는 것보다 성능이 좋다는 것을 발견했는데, 결과 프로그램 자체가 FF 변형인 경우에도 마찬가지입니다. 또한 LLM 추론(reasoning) 노력은 컴파일되는 후보들의 빈도에 품질보다 훨씬 더 큰 영향을 미칩니다. 진화된 프로그램들은 순수 C++이기 때문에, 기존 계획기(planners)에 드롭인 교체(drop-in replacements)로 장착될 수 있으며 기본 탐색(underlying search)의 건전성(soundness)과 완전성(completeness) 보장을 상속받습니다.
원문 초록
Heuristic search is the dominant paradigm in symbolic AI planning, and the strongest heuristics are the result of decades of work by planning researchers. Recent work has shown that large language models (LLMs) can design heuristics for individual planning domains, but no LLM-generated heuristic has so far worked on arbitrary planning tasks. In this paper, we use evolutionary search to produce the first LLM-generated domain-independent heuristics that exceed the hand-engineered state of the art. We let an LLM mutate parent heuristics written in C++, store candidates in a MAP-Elites archive keyed on informedness and speed and calculate fitness scores by blending coverage with solving time. To place the evolved programs in context, we additionally benchmark a broad set of hand-engineered heuristics on their informedness-speed tradeoff, which to our knowledge has not been done before. On unseen testing domains, our best evolved heuristic solves more tasks than even the strongest baseline, with our full heuristic suite spanning the Pareto frontier of said tradeoff. We also find that seeding evolution from the trivial blind heuristic outperforms seeding from the strong FF heuristic, even when the resulting program is itself an FF variant, and that LLM reasoning effort affects how often candidates compile much more than the quality of those that do. Because the evolved programs are plain C++, they slot into existing planners as drop-in replacements and inherit the soundness and completeness guarantees of the underlying search.
요약
대규모 언어 모델(LLM)이 C++ 휴리스틱을 변이하도록 하는 진화 탐색과 MAP-Elites 아카이브를 통해, 임의 계획 작업에 적용 가능한 도메인 독립적 휴리스틱을 수작업 최신 기술을 넘어서는 수준으로 최초 생성했다. 보이지 않는 테스트 도메인에서 최고 진화 휴리스틱은 가장 강한 기준선보다 더 많은 작업을 해결하고, 전체 휴리스틱 스위트는 정보성-속도 트레이드오프의 파레토 프론티어를 포괄하며 순수 C++로 기존 계획기에 드롭인 교체가 가능하다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2605.29649v2제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
작지만 강력하게: 자기 진화 에이전트를 위한 개선 신호로서의 테스트 스위트
Small but Mighty: Test Suites as Improvement Signals for Self-Evolving Agents
자기 진화 에이전트(self-evolving agent)는 자신의 하네스(harness)를 재작성하며 어떤 재작성본을 유지할지 결정해야 하므로, 에이전트의 개선 신호는 재작성본이 통과해야 하는 검증이 됩니다. 에이전트 롤아웃(rollout)으로 재작성을 검증하는 것은 비용이 많이 들고 주관적인 반면, 저장소 자체의 테스트와 같은 실행 가능한 검증은 동작을 변화시키는 재작성을 포착하기에는 너무 희소하여 그중 4분의 1만을 거부합니다. 우리는 그 대신 테스트 피드백을 실행 가능한 신호로 삼고, 신호가 조밀하고 유익할 수 있도록 품질-다양성(quality-diversity) 진화 알고리즘을 통해 작으면서도 강력한 테스트 스위트(test suite)를 탐색합니다. TeSearch는 스위트 크기를 행동 기술자(behavior descriptor)로 취급하여 모든 크기에서 품질을 추구하고 작고 강력한 스위트에 도달할 수 있도록 하며, 해당 기술자에 대한 액추에이터로서 대규모 언어 모델(LLM)의 노이즈를 제거하는 전이 커널(transition kernel)을 탐색 과정에서 학습합니다. 129개의 실제 모듈과 세 가지 백본에 걸쳐, TeSearch는 LLM 기반 진화 탐색을 포함해 비교된 모든 방법 중 가장 높은 품질의 스위트를 제공하며, LLM 기반 방법 중 가장 작은 크기를 달성합니다. 자기 진화 에이전트의 개선 신호로 사용되었을 때, 이는 4.0%의 오경보율(false-alarm rate)과 결정당 3.5초의 속도로 동작을 변화시키는 재작성의 59.9%를 거부하여 저장소 자체 테스트의 25.3%와 대비를 이룹니다. 코드와 데이터는 https://github.com/ccsnow127/TeSearch 에서 확인할 수 있습니다.
ARC-AGI-2를 위한 LLM과 유전 탐색의 결합
Combining LLMs and Genetic Search for ARC-AGI-2
LLM은 ARC-AGI-2 과제를 위한 프로그램을 생성할 수 있지만, 주어진 연산 자원으로는 해결책을 생성하고 디버깅하고 검증하는 시도를 소수만 할 수 있다. 유전 알고리즘(genetic algorithm)은 훨씬 더 많은 프로그램을 탐색하고 테스트할 수 있지만, 무작위 탐색은 해 공간에서 유용한 이웃 영역에서 시작하는 경우가 드물다. 우리는 간결한 도메인 특화 언어(DSL)를 통해 이 두 방법을 결합한다. 먼저, 양자화된 Qwen3.5-4B LLM이 각 ARC-AGI-2 과제에 대한 초기 프로그램 집합을 생성한다. 그런 다음 이 프로그램들을 시작 프로그램의 초기 집단(population)을 구성하는 시드로 사용하고, 유전 알고리즘을 이용해 이 프로그램들이 주어진 과제의 해에 가까워지도록 진화시킨다. DSL은 변이(mutation)된 모든 프로그램이 유효하고 실행 가능하도록 설계되었다. LLM이 제안한 초기 프로그램은 ARC-2 공개 평가 세트의 처음 60개 과제 중 2개(3.3%)를 해결한다. 유전 알고리즘은 추가로 4개를 해결하여, 정답 테스트 출력이 총 6개(10.0%)가 된다. 이러한 LLM 시딩 없이 진화하는 해를 사용해 보면, 어떠한 해에도 도달하지 못한다. 이 결과는 유전 탐색이 LLM이 생성한 프로그램을 개선하고 추가적인 정답을 만들어 낼 수 있음을 보여 준다.
LLM으로 진화하는 검사 가능한 O-RAN 슬라이싱 xApp
Evolving Inspectable O-RAN Slicing xApps with LLMs
오픈 RAN(O-RAN) 슬라이싱 xApp은 채널 조건과 트래픽 수요 변화에 맞춰 자원 할당을 조정하면서 서비스 수준 협약(SLA)을 충족해야 한다. 심층 강화학습은 적응형 정책을 만들 수 있지만, 할당 규칙은 신경망 파라미터에 인코딩된 채로 남는다. 우리의 목표는 이러한 적응성을 유지하면서 컨트롤러의 의사결정 논리를 운영자가 직접 검사하고 편집할 수 있게 하는 것이다. 우리는 대규모 언어 모델(LLM)을 사용해 슬라이싱 컨트롤러를 최적화 이후에도 의사결정 논리가 읽기 쉽고 편집 가능한 컴팩트한 Python 프로그램으로 진화시킨다. LLM은 오프라인으로 후보를 제안하고 수정하며, 보정된 시뮬레이터가 이를 채점하고, 선택된 의사결정 모듈은 O-RAN 제어 경로에서 변경 없이 실행된다. NSF POWDER 5G 테스트베드에서, 진화된 컨트롤러는 지속적인 채널 페이드 하에서 처리량 목표 달성이 불가능해진 보장 슬라이스(guaranteed slice)에서 자원을 해제하여, best-effort 처리량을 158.2 Mbps에서 228.6 Mbps로 개선했으며, 이는 최상의 정적 할당 대비 44.5% 향상이다. 컨트롤러가 읽을 수 있는 소스 코드이므로, 방정식으로부터 동작을 예측할 수 있고, 코드를 읽어 결함을 진단할 수 있으며, 한 줄 편집으로 보정 오류를 수정할 수 있다. 한 사례에서는 SLA 미달을 79.9%에서 2.2%로 줄였고, 다른 사례에서는 적합도(fitness)를 두 배 이상 높였다. 동일 테스트베드에 보정된 4-슬라이스 trace 기반 시뮬레이션에서, 진화적 탐색은 동일한 제안 예산에서 독립적 프롬프팅보다 더 높은 평균 평가 점수를 달성했으며, held-out trace에서의 평균 정규화 이득은 프롬프팅만 16.3%, 처음부터의 진화 32.1%, 시작 프로그램으로부터의 진화 51.0%였다.
대규모 언어 모델을 활용한 온라인 자동 알고리즘 설계
Online Automated Algorithm Design with Large Language Models
대규모 언어 모델(LLM)은 추론과 코드 합성을 통해 자동 알고리즘 설계(AAD)를 가능하게 한다. 그러나 기존의 LLM 기반 AAD 방법 대부분은 알고리즘 설계와 대상 최적화를 분리하여, 최적화 상태가 변화하는 동안에도 고정된 설계를 그대로 배포한다. 기존의 적응형 옵티마이저는 이러한 변화에 대응할 수 있지만, 그 조정은 사전에 정의된 파라미터, 연산자 또는 전략의 범위에 국한된다. 이러한 한계를 해결하기 위해, 본 논문은 알고리즘 자체를 상태 의존적 결정 변수로 취급하는 새로운 최적화 패러다임인 온라인 LLM 기반 AAD를 제안한다. 각 단계에서 LLM 에이전트는 현재의 최적화 상태로부터 새로운 동작 로직을 갖춘 알고리즘을 합성한다. 생성된 알고리즘을 실행하면 탐색이 진행되고 이후 설계를 위한 피드백이 제공되므로, 별도의 오프라인 알고리즘 사전학습 단계 없이도 알고리즘 설계와 대상 최적화가 결합된다. 이 패러다임을 구현하기 위해 본 논문은 상충하는 설계 관점을 조율하여 실행 가능한 알고리즘을 합성하고, 실행 피드백을 활용해 이후 설계를 위해 런타임 증거를 해석하는 방식을 개선하는 멀티 에이전트 프레임워크인 OnDesign을 제안한다. 우리는 두 가지 주류 블랙박스 최적화 패러다임에 걸친 세 가지 시나리오, 즉 베이지안 최적화, 진화적 연속 최적화, 진화적 혼합 변수 최적화에서 OnDesign을 평가한다. 여섯 개의 벤치마크 스위트와 하나의 공학 문제에 대해 다양한 문제 차원에서 수행한 광범위한 실험을 통해, 기존 옵티마이저와 오프라인 LLM 기반 AAD 방법보다 우수한 전반적 성능을 보임을 입증한다.
LLM에게 자기 진화를 가르치기: 강화학습으로 핵심 메타 스킬 함양
Teaching LLMs to Self-Evolve: Cultivating Core Meta-Skills with Reinforcement Learning
AlphaEvolve에서 보여주듯, 환경 피드백을 활용한 반복적 자기 진화를 통한 테스트 시점 스케일링(test-time scaling)은 놀라운 성능 향상을 보인다. 우리는 이러한 진화 프레임워크의 성공이 환경 피드백을 통한 자기 성찰(self-reflection)과 같은 메타 스킬(meta-skills)에 달려 있으며, 이는 효과적인 다중 라운드 정제를 가능하게 하지만 기존 사후 학습에서는 대체로 간과된다고 가정한다. 이 격차를 메우기 위해 데이터 합성 파이프라인, 진화 인식(evolution-aware) 강화학습, 그리고 추론 시점 진화 탐색을 통해 이러한 메타 스킬을 개발하도록 설계된 MetaEvolve 프레임워크를 제안한다. 구체적으로 MetaEvolve를 코딩에 그라운딩(grounding)하였으며, 여기서 프로그램 실행은 이진 정확성을 넘어 자연스럽고 연속적인 보상 신호를 제공한다. 이러한 신호를 바탕으로 각각 현재 프로그램, 적합도 점수(정확성과 효율성의 결합), 그리고 이전 시도 기록을 포함하는 진화 궤적을 학습 데이터로 합성하고, 테스트 케이스 실행에서 도출된 검증 가능한 보상으로 강화학습을 통해 모델을 학습한다. 대규모 코드 데이터로 학습함으로써, 풍부한 학습 신호가 부족한 개방형(open-ended) 문제에 광범위하게 전이할 수 있는 일반화 가능한 도메인 무관(domain-agnostic) 메타 스킬을 기대한다. 7개의 코딩 벤치마크에서 MetaEvolve는 분포 내(in-distribution) 과제에서 가장 강력한 기준선을 절대 10.01%p 초과하고, 분포 외(out-of-distribution) 과제에서는 24.12%p 초과한다. 학습 도메인을 완전히 벗어난 개방형 알고리즘 최적화 문제에서도 46.9%의 상대적 향상을 달성한다. 이러한 결과는 자기 진화 메타 스킬을 명시적으로 함양하는 것이 더 유능하고 자율적으로 자기 진화하는 AI를 향한 원칙적인 경로를 제공함을 보여준다.
MEMENTO: 메모리 유도 멤틱 Code-as-Policy 진화
MEMENTO: Memory-Guided Memetic Code-as-Policy Evolution
장기 호라이즌(long-horizon) 체화(embodied) 태스크는 태스크 성공을 관찰하기 전에 많은 종속적 액션을 실행하는 정책(policy)이 필요하다. 정책을 실행 가능한 제어 프로그램(code-as-policy)으로 표현하면, 롤아웃 평가 후 의사결정 로직을 검사하고 수정할 수 있다. 수정된 프로그램은 롤아웃 성능으로 실행·비교될 수 있으며, 이는 정책 개선을 실행 유도 프로그램 탐색으로 규정한다. 대규모 언어 모델(LLM)이 구동하는 진화적(evolutionary) 방법은 변이를 생성하고 고성능 후보를 선택함으로써 이러한 탐색을 위한 자연스러운 메커니즘을 제공한다. 그러나 기존 접근법은 주로 독립적으로 생성된 변이들 중에서 선택하며, 순차적 국소 개선 단계가 부족하다. 우리는 code-as-policy 진화를 위한 메모리 유도 단일 엘리트(single-elite) 멤틱(memetic) 프레임워크인 MEMENTO를 제안한다. MEMENTO는 먼저 정책 롤아웃을 스칼라 적합도(fitness)와 구조화된 피드백 지표로 매핑하는 롤아웃 평가자(evaluator)를 진화시킨다. 적합도는 수락된 후보와 다음 엘리트를 선택하고, 피드백 지표는 메모리 유도 힐클라이밍(hill-climbing), 거시 돌연변이(macro-mutation), 교차(crossover)로 생성된 정책 제안을 조건화한다. 우리는 Robosuite Franka Tower-of-Hanoi 조작과 AI2-THOR 가정 내 상호작용이라는 두 장기 호라이즌 체화 도메인에서 MEMENTO를 평가한다. MEMENTO는 code-as-policy 진화 베이스라인으로 적용한 Eureka 및 REvolve를 태스크 성공과 보류(hold-out) Robosuite 객체 구성 및 미관측 AI2-THOR 장면에 대한 일반화(generalization) 면에서 능가한다. 소거 실험(ablation)은 제로샷(zero-shot) 생성과 미진화 평가자가 두 도메인 모두에서 해결에 실패하며, 정책 탐색 분기를 제거하면 성능이 저하됨을 보여준다. 마지막으로, 우리는 최고로 진화된 Robosuite 정책을 물리적 Franka 로봇에 배포하여, 진화된 code-as-policy의 sim-to-real 전이 가능성을 입증한다. 코드, 프롬프트(prompt), 동영상은 https://github.com/sygkounas/MEMENTO 에서 확인할 수 있다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.