ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolution

Motivation

• Known: LLM을 진화 에이전트로 활용하여 과학적 발견을 자동화하는 접근이 수학 최적화, 경쟁 프로그래밍, 에이전트 설계 등 다양한 분야에서 효과를 입증했음
• Gap: 기존 방법들(AlphaEvolve, OpenEvolve 등)은 수천 개의 샘플을 요구하는 심각한 샘플 비효율성과 폐쇄 소스 문제로 인해 광범위한 채택과 확장이 어려움
• Why: 이전 세대의 누적된 지식을 효과적으로 활용하지 못하는 순진한(naive) 탐색 전략으로 인해 불필요한 평가가 낭비되고 있으며, 높은 비용으로 인해 접근성이 제한됨
• Approach: 탐색(exploration)과 활용(exploitation)의 균형을 맞추는 적응형 부모 샘플링, 코드 임베딩 유사도 기반 신규성 검증, 성능 기반 LLM 앙상블 선택 전략을 통합

Achievement

원 패킹 작업에서 ShinkaEvolve는 AlphaEvolve를 150개 샘플로 능가

1. 획기적인 샘플 효율성: 원 패킹 문제에서 단 150개 샘플로 새로운 최첨단 솔루션 발견 (기존 방법 대비 수십 배 개선)
2. 다양한 도메인 검증:
   • 수학 최적화(원 패킹)
   • AIME 수학 추론 작업용 고성능 에이전트 설계
   • ALE-Bench 경쟁 프로그래밍 문제 개선
   • 혼합전문가(MoE) 로드 밸런싱 손실함수 발견
3. 오픈소스 공개: Apache 2.0 라이센스 하에 전체 코드와 대화형 시각화 도구 공개로 민주화 추진

How

부모 샘플링 전략: 균일 샘플링(순수 탐색)에서 언덕오르기(순수 활용)까지 다양한 선택지 제공

1. 적응형 부모 및 영감 프로그램 샘플링

• 아일랜드 모델: 독립적인 부분모집단으로 다양성 증대 및 조기 수렴 방지
• 파워 법칙 샘플링: 랭크 $r_i$에 따라 $p_i = \frac{r_i^{-\alpha}}{\sum_j r_j^{-\alpha}}$ 확률로 선택 (α로 활용 강도 제어)
• 가중 샘플링: 성능과 신규성 결합
  • 성능 성분: $s_i = \sigma(\lambda(F(P_i) - \alpha_0))$ (중앙값 대비 정규화)
  • 신규성 성분: $h_i = \frac{1}{1+N(P_i)}$ (자손 수 기반)
  • 최종 확률: $p_i = \frac{w_i}{\sum_j w_j}$ 여기서 $w_i = s_i \cdot h_i$

2. LLM 유도 프로그램 변이 및 신규성 평가

코드 신규성 거절 샘플링: 임베딩 유사도 계산 → 임계값 초과 시 LLM 재평가

• 세 가지 변이 전략:
  1. Diff 기반 편집 (SEARCH/REPLACE 블록 사용)
  2. 전체 재작성 (불변 블록 보호)
  3. 교배 변이 (두 프로그램 결합)
• 코드 신규성 거절 샘플링:
  • 변이 가능한 코드 부분을 임베딩 모델로 벡터화
  • 아일랜드 부분모집단 내 코사인 유사도 계산
  • 최대 유사도가 임계값(η=0.95) 초과 시 LLM에 의미적 차별성 재판정
  • 비효율적 변이 거절로 탐색 공간 효율화

3. 실행 및 세계 피드백

• 다목적 평가: 스칼라 적응도(fitness) + 공개 메트릭 + 텍스트 피드백 저장
• 적응형 LLM 샘플링: 진화 중 각 LLM의 성공률 추적 후 성능 기반 확률 조정
• 메타 스크래치패드: 개별 프로그램 요약과 글로벌 발견 패턴 문서화로 지식 확산 촉진

Originality

• 부모 선택의 탐색-활용 균형: 단순한 power law 샘플링에서 벗어나 성능과 신규성을 명시적으로 결합하는 가중 샘플링 전략은 직관적이면서도 효과적
• 코드 신규성 거절 샘플링: 임베딩 기반 1차 필터와 LLM 기반 의미적 재검증의 이층 구조로 계산 효율성과 품질을 동시에 확보
• 성능 기반 LLM 앙상블 선택: 온라인 밴딧(bandit) 알고리즘으로 여러 LLM의 확률을 동적으로 적응시켜 모델 간 성능 편차를 활용
• 체계적 통합: 세 가지 혁신이 시너지를 이루어 기존 AlphaEvolve 대비 획기적 샘플 효율성 달성
• 오픈소스 공개: 연구 재현성과 커뮤니티 기여를 촉진하는 적극적 개방 자세

Limitation & Further Study

• 계산 비용 간접 분석 부족: 샘플 수는 감소하나, 각 샘플당 LLM 쿼리 수(변이 제안 재샘플링 포함) 및 실제 벽시계 시간(wall-clock time) 분석이 제시되지 않음
• 초매개변수 민감도: 임계값 η, power law 지수 α, 온도(temperature), 추론 예산 등 다양한 초매개변수의 최적화 방법 및 민감도 분석 부재
• 도메인 특이성: 네 가지 평가 도메인이 모두 제한된 규모(150-수천 샘플)로 초대형 문제에서의 확장성 검증 필요
• 적응형 LLM 선택의 상세 기술: 밴딧 알고리즘 구현(Thompson sampling vs. UCB 등)과 수렴 특성에 대한 구체적 기술 부족
• 후속 연구 방향:
  • 신경망 기반 아키텍처 진화, 하이퍼매개변수 최적화 등 더 복잡한 문제로 확장
  • 지역 프롬프팅(in-context learning)과 메타 스크래치패드 활용의 심화 연구
  • 다중 목표 환경과 제약 조건 하의 진화 전략 개발

Evaluation

총평: ShinkaEvolve는 LLM 기반 프로그램 진화에서 부모 선택, 신규성 검증, 적응형 앙상블의 세 가지 혁신을 통해 샘플 효율성을 획기적으로 개선한 실용적 프레임워크이다. 오픈소스 공개로 재현성과 확장성을 보장하며, 다양한 도메인 검증도 인상적이나, 초매개변수 분석과 대규모 문제 확장성 검증을 통해 더욱 강화될 수 있다.