Evolutionary Multi-Task Optimization for LLM-Guided Discovery

Motivation

• Known: FunSearch, AlphaEvolve 등 LLM 기반 진화적 코드 탐색은 반복적 program mutation을 통해 강력한 알고리즘이나 수학적 구성을 발견할 수 있음이 알려져 있다. 또한 evolutionary multitasking 분야에서는 고정된 벡터 표현이나 genetic programming 표현 공간에서 공유 population을 활용해 여러 태스크를 함께 최적화하는 선행 연구들이 존재한다.
• Gap: 기존 LLM 기반 진화적 탐색 방법들은 관련 태스크들이 재사용 가능한 구조를 공유함에도 불구하고 각 태스크를 독립적으로 최적화하여 compute를 비효율적으로 사용하며, evolutionary multitasking 문헌은 고정 표현 공간에 초점을 맞춰 LLM이 생성하는 open-ended text 기반(실행 가능한 프로그램) 멀티태스킹 문제는 다루지 않는다.
• Why: LLM 기반 진화적 탐색은 수십 라운드가 필요한 고비용 프로세스이므로, 관련 태스크 간 구조를 재사용해 compute 효율성과 일반화 성능(특히 학습 데이터가 적은 low-evidence 상황에서의 과적합 방지)을 동시에 높이는 방법은 실용적·과학적으로 중요하다.
• Approach: 공유 진화 단계에서 하나의 통합 프로그램 인터페이스를 사용해 태스크 패밀리 전체에 대한 family-level aggregate objective로 archive를 진화시키고, 이후 세 가지 적응 전략(Warmstart, Best-Shared, Best-Local) 중 하나로 각 타겟 태스크에 대해 로컬 적응 진화를 수행한다.

Achievement

Figure 2. Compute-allocation results for EMO-STA on two K = 4 task families. Grouped bars compare STA Warmstart, STA Bes

1. EMO-STA 프레임워크 제안: 공유 진화(archive 구축)와 태스크별 적응을 분리한 2단계 shared-then-adapt 구조를 처음으로 LLM 기반 프로그램 진화에 도입했다.
2. 다양한 적응 전략 비교: Warmstart, Best-Shared, Best-Local 세 가지 초기화 전략을 제시하고, STA Best-Local이 in-distribution 적응에서 가장 강력하며 STA Best-Shared가 미지 태스크로의 전이(transfer)에 강건함을 규명했다.
3. 8개 태스크 패밀리에서 실증적 개선: 연속 최적화, 기하학적 구성, 모델링, 알고리즘 최적화 등 다양한 영역에서 matched-compute 단일 태스크 진화 대비 대부분의 설정에서 성능 향상을 보였다.
4. Compute 배분 분석: family-level budget 중 상당 부분(대략 균형 잡힌 비율)을 shared evolution에 할당하는 것이 일관되게 유리함을 실험적으로 규명했다.
5. 과적합 완화 효과 입증: ARC, 시계열 특징 공학 등 학습 데이터가 적은 low-evidence 상황에서 shared evolution이 태스크에 특화된 취약한 아티팩트 대신 일반화 가능한 프로그램을 선호하도록 유도해 과적합을 완화함을 보였다.

How

Figure 3. Held-out task-size evaluation at fixed 60 / 15 / 120 compute allocation across three domains: circle packing,

• Circle packing, function minimization, Heilbronn triangle, signal processing 등 8개 태스크 패밀리에 대해 동일 entry-point 인터페이스(예: construct_packing(n), process_signal(...))를 정의하고 LLM이 해당 형식을 구현하도록 프롬프트를 구성
• 공유 진화 단계에서 family-level aggregate objective s_shared(p) = (1/K)Σ s_i(p)를 사용해 archive A_shared를 구축
• 적응 단계에서 세 가지 초기화 전략(전체 archive 이관, 평균 최고 성능 프로그램 선택, 타겟 태스크 최고 성능 프로그램 선택) 중 하나로 task-local 진화 지속
• Haiku-4.5, Sonnet-4.5, Opus-4.5, Sonnet-4.6, Opus-4.6 등 다수의 LLM 백본에 걸쳐 matched-compute 단일 태스크 진화와 비교 실험 수행
• Shared iteration 수(S)와 adaptation iteration 수(A) 배분을 바꿔가며 compute-allocation 실험 수행
• ARC 태스크, 시계열 feature engineering 등 low-evidence(소량 학습 데이터) 설정에서 과적합 완화 효과를 별도로 검증

Originality

• LLM 기반 진화적 프로그램 탐색에 evolutionary multitasking 개념을 최초로 명시적으로 도입해, 고정 표현 공간이 아닌 open-ended executable program 공간에서의 멀티태스크 최적화 문제를 정의
• 단순한 population 공유가 아니라 shared-then-adapt라는 명확한 2단계 구조와 세 가지 구체적 초기화 전략(Warmstart, Best-Shared, Best-Local)을 체계적으로 비교 설계
• Compute 효율성뿐 아니라 low-evidence 설정에서의 과적합 완화라는 부가적 이점을 실험적으로 규명하여, 공유 진화가 단순한 탐색 예산 증가 이상의 구조적 이점(더 나은 search space bias)을 제공함을 논증

Limitation & Further Study

• 워크숍 논문 형태의 발췌본으로 실험 세부사항(태스크별 evaluator 설계, 하이퍼파라미터, 통계적 유의성 검정 등)이 충분히 제시되지 않아 재현성 및 엄밀성 평가가 제한적임
• 8개 태스크 패밀리가 서로 얼마나 이질적인지, 그리고 태스크 간 구조적 유사성이 낮은 경우(패밀리 설계가 실패하는 경우)에 대한 실패 사례 분석이 부족함
• 사용된 LLM 백본이 모두 상용 Anthropic 계열(Haiku/Sonnet/Opus) 모델에 한정되어 있어, 오픈소스 또는 타 계열 모델에 대한 일반화 가능성이 검증되지 않음
• 후속 연구로 태스크 패밀리를 자동으로 클러스터링하거나 발견하는 방법, 그리고 shared-then-adapt 전략을 반복적으로 순환(iterative shared-adapt loop)시키는 확장 등을 고려할 수 있음

Evaluation

총평: LLM 기반 진화적 탐색에 멀티태스크 최적화 개념을 참신하게 접목한 실용적이고 설득력 있는 워크숍 논문으로, 특히 compute 효율성과 과적합 완화라는 두 가지 실질적 이점을 동시에 보여준 점이 인상적이나 발췌본 특성상 세부 실험 검증의 완전성은 추가 확인이 필요하다.