기술 요약: LLM 을 활용한 알고리즘 발견: 진화적 탐색과 강화학습의 만남

문제 제기

복잡한 문제, 특히 수학과 조합 최적화 분야에서 효율적인 알고리즘을 발견하는 작업은 역사적으로 상당한 인간의 전문성에 의존해 왔습니다. 최근 대규모 언어 모델 (LLM) 과 진화적 탐색 (예: FunSearch 방법) 을 결합한 발전은 이러한 발견을 자동화하는 데 가능성을 보여주었지만, 기존 접근법들은 LLM 을 정적 생성기로 취급합니다. 이러한 방법들은 이전의 성공 사례를 바탕으로 LLM 을 사용하여 새로운 프로그램을 제안하지만, 진화적 탐색 과정에서 얻은 신호에 기반하여 모델의 내부 매개변수를 업데이트하지는 못합니다. 결과적으로 이들은 시간이 지남에 따라 탐색 정책을 정제하기 위해 LLM 의 매개변수적 특성을 활용하는 기회를 놓치게 되어, 최적에 미치지 못하는 수렴이나 해 공간의 비효율적인 탐색으로 이어질 수 있습니다.

방법론: EvoTune

저자들은 LLM 탐색 연산자를 지속적으로 정제하기 위해 진화적 탐색과 강화학습 (RL) 을 긴밀하게 통합한 EvoTune이라는 프레임워크를 제안합니다. 이 방법은 두 개의 교차하는 단계로 구성된 반복 루프에서 작동합니다:

1. 진화적 탐색 (탐색):

   • LLM 은 이전 반복에서 발견된 고득점 프로그램으로 구성된 프롬프트를 기반으로 후보 Python 프로그램 (알고리즘) 을 생성합니다.
   • 이러한 프로그램들은 특정 조합 최적화 작업 (예: Bin Packing, Traveling Salesman Problem, Flatpack) 에서 평가되어 보상 점수 (일반적으로 최적성 갭의 음수) 를 얻습니다.
   • 유효한 프로그램과 그 점수는 다양성을 유지하고 조기 수렴을 방지하기 위해 '섬 (islands)'으로 조직된 프로그램 데이터베이스에 저장됩니다.
   • 탐색은 LLM 이 고성과 프로그램과 저성과 프로그램 간의 차이를 분석하여 새로운 후보 생성을 안내하는 '부트스트래핑 (bootstrapping)' 전략을 사용합니다.

2. RL 훈련 (정제):

   • 주기적으로 (매 $f_{RL}$ 반복마다), 진화적 탐색에서 축적된 데이터를 사용하여 LLM 의 생성 정책 ($\pi_\theta$) 이 업데이트됩니다.
   • 저자들은 이를 선호 최적화 (Preference Optimization) 문제로 공식화합니다. 그들은 프롬프트 $x$, 더 높은 보상을 가진 프로그램 $y^+$, 그리고 더 낮은 보상을 가진 프로그램 $y^-$로 구성된 삼중항 $(x, y^+, y^-)$으로 이루어진 선호 데이터셋 $D_{pref}$를 구성합니다.
   • 모델은 직접 선호 최적화 (Direct Preference Optimization, DPO) 를 사용하여 미세 조정됩니다. 표준 오프라인 DPO 와 달리 EvoTune 은 데이터가 진화하는 모델 자체에 의해 동적으로 생성되는 오프-폴리시 (off-policy) 설정에서 작동합니다.
   • 다양성 보존: 중요한 설계 선택은 DPO 목적 함수 내에서 더 일반적인 역 KL 대신 순방향 KL 정규화 (Forward KL regularization) 를 사용하는 것입니다. 이는 모델이 단일 모드로 붕괴되는 것을 방지하고 효과적인 진화적 탐색에 필수적인 출력 다양성을 보존하는 '매스 커버링 (mass-covering)' 행동을 장려합니다.

주요 기여

1. 진화적 탐색으로의 RL 통합: 이 논문은 LLM 기반 진화적 탐색과 RL 미세 조성을 루프 내에서 긴밀하게 통합한 잠재력을 최초로 입증했다고 주장합니다. LLM 을 정적 생성기로만 사용하는 이전 방법들과 달리 EvoTune 은 탐색에서 얻은 통찰력을 더 잘 활용하기 위해 모델 가중치를 업데이트합니다.
2. 가속화된 알고리즘 발견: RL 을 통해 탐색 정책을 정제함으로써, 이 방법은 우수한 알고리즘의 발견을 가속화합니다. 세 가지 지시어 튜닝 LLM (Llama3.2 1B, Phi 3.5 Mini, Granite 3.1 2B) 에 대한 실험은 기준선 FunSearch 방법보다 일관된 성능 향상을 보여줍니다.
3. 다양성 보존 정렬: 저자들은 출력 다양성을 보존하기 위해 수정된 정렬 목적 (순방향 KL 정규화 DPO) 을 사용하는 것의 이점을 입증합니다. 이는 진화 전략에 있어 중요하며, 모드 붕괴는 새로운 해의 발견을 방해할 수 있기 때문입니다.
4. 광범위한 적용 가능성: 이 방법은 표준 조합 문제 (Bin Packing, TSP, Flatpack), 실제 세계의 Google Hash Code 챌린지 (데이터센터 최적화, 자율 주행 승차), 그리고 기호 회귀 작업 (LLM-SR) 을 포함한 다양한 벤치마크에서 검증되었습니다.

실험 결과

저자들은 여러 작업과 모델에 걸쳐 EvoTune 을 모델 훈련이 없는 진화적 탐색 (FunSearch 스타일 기준선) 과 비교 평가했습니다:

• 성능 향상: EvoTune 은 발견된 상위 50 개 프로그램에 대해 기준선보다 일관되게 더 높은 최종 보상 점수 (더 낮은 최적성 갭) 를 달성했습니다. 성능 격차는 샘플링 예산이 증가함에 따라 종종 확대되어, 더 큰 예산이 이 방법의 장점을 증폭시킨다는 것을 시사합니다.
• 일반화: 진화된 프로그램은 동일한 분포에서 추출된 검증 교란 세트와 테스트 세트에서 견고성을 보여주어, 학습된 정책이 훈련 중 본 특정 인스턴스 너머로 일반화됨을 나타냅니다.
• 실제 세계 벤치마크:
  • Google Hash Code 데이터센터 최적화 작업에서 EvoTune 은 418점을 기록하여 407 점의 최고 인간 점수를 능가하고 FunSearch 기준선 (414 점) 을 상회했습니다.
  • 기호 회귀 작업 (LLM-SR) 에서 EvoTune 은 진화적 기준선을 능가했으며, 특히 더 크거나 독점적인 모델 (예: Mixtral 8x7B, GPT-3.5-turbo) 을 사용하는 기준선을 능가하면서도 더 작은 모델 (Phi-3.5 Mini, 38 억 파라미터) 을 사용했습니다.
• 절대 실험 (Ablation Studies):
  • 순방향 vs 역방향 KL: 실험은 역 KL 에 비해 순방향 KL 정규화가 더 높은 보상과 더 많은 고유한 해를 산출함을 확인하여 다양성 보존의 중요성을 검증했습니다.
  • 대안 RL: 저자들은 DPO 의 대안으로 고득점 출력에 대한 지도 미세 조정 (ReSTEM) 을 테스트했습니다. 결과는 DPO 가 ReSTEM 을 일관되게 능가하며 하이퍼파라미터 튜닝에 덜 민감함을 나타냈습니다.

중요성과 주장

이 논문은 탐색과 학습이 시너지를 낸다는 '쓴 교훈 (Bitter Lesson, Sutton, 2019)'을 해결함으로써 자동화된 알고리즘 설계에서의 중요한 진전으로 EvoTune 을 위치시킵니다. 저자들은 다음과 같이 주장합니다:

• 시너지: 탐색은 새로운 데이터를 생성하고, 학습은 그 데이터에서 패턴을 정제하여 미래의 탐색을 더 효과적으로 안내합니다.
• 효율성: RL 을 통합함으로써 시스템은 단순히 집단의 평균 점수를 높이는 것을 넘어, 상위-k 성능으로 측정된 우수한 해를 향해 진화적 탐색을 적극적으로 안내하면서도 혁신에 필요한 다양성을 유지합니다.
• 확장성: 데이터센터 최적화 및 응력 - 변형률 모델링과 같은 복잡하고 비합성적인 문제에서의 성공은 이 방법이 실제 세계 설정으로 확장될 잠재력을 보여줍니다.

저자들은 모델 크기와 샘플링 예산의 추가 확장이 이 방법의 잠재력을 완전히 이해하는 데 필요하다는 점을 noting 하여, 10 억에서 38 억 파라미터 범위의 모델을 사용하여 실험이 수행되었음을 겸손하게 인정합니다. 또한 RL 훈련 단계의 추가 컴퓨팅 비용과 추론 효율성 및 해 품질의 향상 사이의 트레이드오프를 강조합니다.