기술 요약: 진화적 탐색에서의 연산 할당

문제 정의

대형 언어 모델 (LLM) 기반 진화적 탐색 시스템 (예: FunSearch, AlphaEvolve, CodeEvolve) 은 수학적 발견과 조합 최적화 분야에서 최첨단 결과를 달성했습니다. 그러나 기존 문헌은 주로 지정되지 않은 횟수의 실행 중 단일 최상위 결과를 보고할 뿐, 실행 간 분포는 문서화되지 않았습니다. furthermore, 보고된 계산 비용은 수차례의 크기 차이가 발생하여 고정된 예산 하에서 단일 실행의 신뢰성을 평가하기 어렵게 만듭니다.

해결된 핵심 문제는 연산 할당입니다: 고정된 LLM 호출 예산 ($C$) 이 주어졌을 때, 이 예산을 깊이(단일 궤적의 순차적 정제) 와 너비(다중 궤적의 병렬 탐색) 사이에 어떻게 분배해야 할까요? 현재 시스템들은 종종 이러한 하이퍼파라미터 (예: 개체군 크기와 세대 수) 를 고정하는데, 할당이 기대 성능과 신뢰성에 미치는 영향을 체계적으로 이해하지 못합니다.

방법론

1. 깊이–너비 할당의 경험적 특성화

저자들은 세 가지 기하학적 최적화 작업 (원 패킹, MinMaxDist, Heilbronn 삼각형) 과 네 가지 모델 크기 (Qwen3-1.7B 에서 14B 까지, 그리고 Llama-3.1-8B 포함) 에 걸쳐 체계적인 경험적 연구를 수행했습니다. 그들은 예산 $C$를 $N$개의 병렬 자식 개체로 구성된 $T$세대로 분할하는 것을 할당 문제로 정의했습니다 ($C = T \times N$).

• 적합도–연산 포락선: 그들은 달성 가능한 적합도와 효과적 FLOPs(모델 크기와 캐시 효율성을 고려한) 간의 관계를 분석했습니다. 그들은 동일한 호출 수에서는 더 큰 모델이 우위를 점하지만, 모델 - 작업 쌍이 "유능하다"고 가정할 때 효과적 FLOPs 기준으로 측정하면 성능 순서가 크게 무너진다는 것을 관찰했습니다.
• 깊이–너비 규칙성: 그들은 적합도 지형에 매개변수 이선형 모델을 적합시켰습니다:
  $$\log(1 - V) = \beta_0 + a \log T + b \log N + c \log T \log N$$
  여기서 $V$는 적합도입니다. 상호작용 계수 $c$는 최적 할당의 기하학을 결정합니다:
  • 코너 최적점 ($|c| \approx 0$): 원 패킹과 같은 작업은 많은 할당이 유사한 결과를 산출하는 넓은 평탄 지대를 보이며, 종종 깊이를 선호합니다.
  • 내부 능선 ($c < 0$): MinMaxDist 와 같은 작업은 최적 성능을 위해 깊이와 너비의 균형 잡힌 혼합이 필요한 날카로운 능선을 보입니다.
  • 유능성 게이트: 이러한 규칙성은 특정 작업에 대한 유능성 임계값을 넘은 모델들에게만 유효합니다. 유능하지 않은 모델들은 구조화된 깊이–너비 트레이드오프를 보이지 못합니다.

2. BaSE: 밴디트 기반 자기 진화

LLM 의 돌연변이 과정의 확률성으로 인해 동일한 구성이 광범위하게 다른 최종 적합도 점수를 산출하는 높은 실행 변동성에 영감을 받아, 저자들은 BaSE를 제안했습니다.

• 메커니즘: BaSE 는 진화적 탐색을 멀티-암 밴디트 (MAB) 문제로 취급합니다. 전체 예산을 단일 궤적 (Greedy) 이나 고정된 섬 집합 (Island 프로토콜) 에 할당하는 대신, BaSE 는 $K$개의 병렬 궤적을 유지합니다.
• 적응적 할당: 각 단계에서 밴디트 알고리즘 (UCB, EXP3.P, 또는 톰슨 샘플링) 은 다음 LLM 호출로 확장할 궤적을 선택합니다. 이는 정체된 실행에서 유망한 실행으로 연산을 동적으로 라우팅합니다.
• 직교성: BaSE 는 기본 모델, 프롬프트, 또는 궤적 내 부모 샘플링 로직을 변경하지 않습니다. 이는 궤간 자원 할당 수준에서만 작동합니다.

주요 결과

1. 경험적 규칙성

• 유능성 붕괴: 유능한 모델들의 경우, 성능 포락선은 모델 크기 단독이 아닌 효과적 FLOPs 에 의해 결정됩니다.
• 작업 의존적 기하학: 최적의 깊이–너비 분할은 보편적이지 않습니다; 이는 작업의 "알고리즘 계열"(예: scipy와 같은 특정 라이브러리나 특정 분석적 구성이 필요한지 여부) 에 따라 달라집니다.
• 확률성: 고정된 할당으로도 개별 실행은 크게 변동합니다. 일부 실행은 높은 적합도로 수렴하는 반면, 다른 실행들은 비최적 알고리즘 계열에 고정되어 초기에 정체됩니다.

2. BaSE 의 성능

• 평균 적합도 개선: 8 개의 (모델, 작업) 셀에 걸쳐 BaSE 는 모델이나 프롬프트를 변경하지 않고 가장 강력한 섬 프로토콜 기반 (예: OpenEvolve, CodeEvolve, ShinkaEvolve) 대비 평균 최상위 적합도를 12.3% 개선했습니다.
• 신뢰성 향상: 가장 큰 개선은 높은 변동성 환경에서 관찰되었습니다. 예를 들어, Llama-3.1-8B 를 사용한 Heilbronn 삼각형 작업에서 비-BaSE 방법은 유효한 솔루션을 생성하지 못하는 경우가 많았습니다 (적합도 $\approx 0$), 반면 BaSE(톰슨 샘플링) 는 0.4387 의 평균 적합도를 달성했습니다.
• 샘플 효율성: BaSE 는 Greedy 또는 고정 할당 기반보다 목표 적합도 임계값에 훨씬 빠르게 도달했습니다 (더 적은 세대와 FLOPs). 예를 들어, MinMaxDist 에서 UCB 는 92 세대 만에 0.95 임계값에 도달한 반면, Greedy 기반은 485 세대가 필요했습니다.
• 어블레이션: 중간 규모의 암 풀 크기 ($K \in \{5, 10, 20\}$) 는 다양성과 정제 깊이 사이의 가장 좋은 트레이드오프를 제공했습니다.

중요성과 주장

이 논문은 연산 할당이 모델 확장이나 프롬프트 엔지니어링과 구별되는 LLM 기반 진화적 탐색 개선을 위한 고유하고 중요한 레버라고 주장합니다.

• 할당 대 엔지니어링: 저자들은 그들의 개선이 더 나은 프롬프트나 모델 때문이 아니라고 강조합니다. 실제로 그들은 일부 기반 (예: ShinkaEvolve) 이 특정 작업에서 높은 점수를 얻은 것이 부분적으로 프롬프트로 유도된 힌트 (예: scipy.optimize 제안) 때문이었다고 지적하는 반면, BaSE 는 적응적 자원 라우팅을 통해 순수하게 이득을 얻습니다.
• 신뢰성: 주요 기여는 "최상위 사례" 보고에서 "기대" 성능으로의 초점 전환입니다. BaSE 는 신뢰성 향상을 제공하여, 실무자가 이미 정체된 궤적에 고정된 예산을 낭비할 가능성을 줄여줍니다.
• 상호 보완성: BaSE 는 기존 실행 내 메커니즘 (예: 부모 샘플링) 과 상호 보완적으로 제시됩니다. 이는 기존 프로토콜 (Greedy, Island) 위에 계층화되어 특히 불안정하거나 높은 변동성 환경에서 성능을 추가로 개선할 수 있습니다.

이 연구는 모델 유능성이 달성 가능한 것의 상한선을 설정하지만, 할당은 그 방법이 그 상한선에 얼마나 효율적으로 접근하는지를 지배한다고 결론지으며, 밴디트를 통한 적응적 할당은 유한 예산 탐색을 위한 강력한 전략임을 시사합니다.