GAE: Graph-Augmented Evolution for Scientific Discovery via Reinforcement Optimization

Motivation

• Known: FunSearch와 AlphaEvolve 등은 LLM을 mutation 연산자로, evaluator를 fitness 판정자로 활용하는 evolutionary program search로 수학적 객체 발견 및 코드베이스 최적화에서 성과를 보였으나, 이들 시스템은 정적인 LLM weight와 fitness rank 기반의 비구조적 parent selection에 의존한다.
• Gap: 기존 방법들은 reward sparsity(전체 프로그램 실행 후 단일 이진 개선 신호만 제공), uninformed parent selection(프로그램 집단의 구조적 유사성 무시), static mutation operator(탐색 경험 축적에도 LLM weight 고정)라는 세 병목을 동시에 해결하지 못하며, EvoTune·Quality-Diversity RL·ShinkaEvolve 등은 각각 최대 한 가지 문제만 개별적으로 다룬다.
• Why: 과학적 발견을 위한 자동화된 진화적 탐색의 효율성과 방향성을 근본적으로 개선함으로써, symbolic regression과 같은 복잡한 물리계 방정식 발견 문제에서 stochastic search를 directed, self-improving trajectory로 전환할 수 있음을 보여주는 것은 AI 기반 과학 발견의 확장성에 중요한 의미를 가진다.
• Approach: OpenEvolve 백본 위에 relational GNN encoder, discrete SAC 기반 meta-controller, online GRPO fine-tuning 루프를 결합한 tightly coupled 3-pillar 아키텍처를 제안하며, 공유된 구조 임베딩을 매개로 parent selection과 mutation 방향 결정, LLM 정책 업데이트가 상호 연동되도록 설계했다.

Achievement

Figure 2. Performance trajectory of the GAE method on the Non-

1. 구조 인식 임베딩 생성: relational GNN이 프로그램의 AST를 typed computation graph로 파싱하여 structure-aware embedding을 온라인으로 학습하며 fitness를 예측한다.
2. directed parent/mutation 선택 정책: discrete SAC meta-controller가 GNN 임베딩을 조건으로 task-score 개선, 임베딩 공간 novelty, 복잡도 패널티를 균형 있게 반영해 mutation-type hint를 생성함으로써 blind sampling을 대체한다.
3. test-time LLM 적응: online GRPO fine-tuning이 group-normalized reward와 부모 GNN 임베딩을 variance-reduction baseline으로 활용해 LLM mutation operator를 탐색 중 지속적으로 업데이트한다.
4. 경험적 성능 검증: LLM-SR 벤치마크의 nonlinear oscillator symbolic regression 과제에서 GAE가 static LLM 기반 baseline과 동등하거나 우수한 성능을 보이며, out-of-distribution 상황에서 state-of-the-art 성능을 달성했다.

How

Figure 1. GAE framework overview. A relational GNN encoder parses each program’s abstract syntax tree into a typed compu

• MAP-Elites 기반 archive와 OpenEvolve의 island 병렬 진화 구조를 기반 프레임워크로 채택.
• 프로그램의 AST를 typed computation graph로 변환한 뒤 relational GNN으로 인코딩하여 구조적 임베딩 z를 생성하고, 이를 fitness 예측 학습에 활용.
• discrete Soft Actor-Critic(SAC) meta-controller가 임베딩 z를 입력받아 mutation-type hint를 출력하며, task score·novelty·complexity로 구성된 3요소 보상과 automatic entropy regularization으로 정책을 학습.
• LLM이 생성한 G개의 child 그룹에 대해 group-relative advantage(부모 대비 reward 차이)를 계산하고, 이를 PPO-clip 방식의 online GRPO 업데이트에 사용해 LLM weight를 진화 중단 없이 갱신.
• LLM-SR 벤치마크의 nonlinear oscillator 데이터셋으로 symbolic regression 실험을 수행하고 static LLM 기반 baseline과 비교.

Originality

• 구조적 정보(GNN embedding), 선택 정책(RL meta-controller), mutation 연산자(online GRPO) 세 가지를 하나의 공유 임베딩으로 tightly coupled하게 통합한 최초의 시도로 보임.
• 기존 quality-diversity RL 방법들이 요구하는 dense per-step reward의 한계를 프로그램 population 전반에 전파되는 graph-structured signal로 우회한 접근.
• GRPO의 group-normalized reward와 GNN 임베딩을 variance-reduction baseline으로 결합해 test-time에 LLM mutation operator를 적응시키는 방식은 기존 ThetaEvolve, ShinkaEvolve 등 개별적 접근과 차별화됨.

Limitation & Further Study

• 발췌된 본문에서는 symbolic regression(nonlinear oscillator)이라는 단일 과학적 과제 도메인에 대한 평가만 제시되어, 코드 최적화나 수학적 객체 발견 등 더 넓은 AlphaEvolve/FunSearch 스타일 과제에 대한 일반화 가능성은 불명확함.
• GNN, SAC meta-controller, GRPO fine-tuning이라는 세 개의 학습 컴포넌트가 동시에 온라인으로 상호작용하면서 발생할 수 있는 학습 안정성, 계산 비용, 하이퍼파라미터 민감도에 대한 분석이 발췌 부분에서는 충분히 다뤄지지 않음.
• baseline 대비 성능 향상의 폭과 통계적 유의성, 그리고 GNN/SAC/GRPO 각 구성요소의 개별 기여도를 분리하는 ablation 결과가 본문 발췌에서 확인되지 않아 각 pillar의 실질적 기여도 검증이 필요함.

Evaluation

총평: LLM 기반 evolutionary program search의 세 가지 근본적 병목을 하나의 통합된 구조로 해결하려는 시도는 참신하고 잘 설계되어 있으나, 제공된 발췌만으로는 단일 도메인 실험 결과와 ablation 분석의 충분성을 판단하기 어려워 추가 검증이 필요하다.